To: hop-discuss@plover.com Subject: Quilt block analysis Date: Wed, 31 Aug 2005 22:04:35 -0400 From: Mark Jason Dominus I just blew a lot of time writing this up for someone who contacted me privately, so I thought I'd send it off to the list in case anyone was interested. It concerns the analysis of the similarity of quilt blocks that is located at http://hop.perl.plover.com/quilt/analysis/ ------- Forwarded Message > you're also checking for rotations. If to make a block the 4 > patterns are rotated 90 degrees each time, a rotation of the entire > block should be equal to a non-rotated block, ie. they should be > equivalant. So, why do we need to check rotations? It might be an error. I haven't looked closely at that code since 1997, so I no longer remember what I was thinking. > My mother-in-law is into quilting as well, could you explain, or point me to > a link that explains, the lettering system being used in some of your > analysis work? I haven't thought about this for several years, so it's taken me quite some time to figure out what I was doing. Short answer: I was trying to come up with a way to get the computer to figure out which blocks looked similar to which others. http://hop.perl.plover.com/quilt/analysis/images/similarity-2.html shows the result of the classification. My idea was to try to find a way to get the computer to notice which blocks have distinctive sub-areas of one color. For example, lots of blocks have a diamond shape X XXX XXXXX XXX X in the center. Some have a pinwheel like this: X XX XXX XX XXX X XXX XXX XXX XXX X XXX XX XXX XX X which also has the diamond in the middle. Others have a different kind of pinwheel with no diamond: X XX XXX XXX XX XXX X XXX XXX X XXX XX XXX XXX XX X I wanted to enumerate such shapes and ask the computer to list which blocks contained which shapes; then group them by similarity, supposing that blocks with the same shapes are similar. The program suite uses a compact notation of blocks and of shapes that makes it easy to figure out which blocks contain which shapes. Since each block is made of four identical four-patches, it's enough just to examine the four-patches. Each of the half-square triangle patches can be oriented in two ways: +---+ +---+ |\ | | /| | \ | | / | | \| |/ | +---+ +---+ Here are two four-patches that are each in the upper-left corner of their respective blocks: +---+---+ +---+---+ |\ b|\ e| |a /|d /| | \ | \ | | / | / | |b \|f \| |/ c|/ g| +---+---+ +---+---+ |\ f|\ i| |d /|h /| | \ | \ | | / | / | |e \|i \| |/ g|/ j| +---+---+ +---+---+ Each triangle gets a name, and triangles that are equivalent under rotations or reflections get the same name. For example, the triangles marked with a "b" descriptor are equivalent under a reflection across the northwest-southeast diagonal. A block might, of course, have patches in different orientations: +---+---+ |\ b|d /| | \ | / | |b \|/ g| +---+---+ |\ f|\ i| | \ | \ | |e \|i \| +---+---+ Blocks with this orientation of diagonals get a descriptor that contains "bbdefghj". Once you have chosen one of the 12 ways to orient the diagonals, you still have to color the patches. A descriptor like "bbeeffii" describes the orientation of the diagonal lines in the squares, but a patch with that configuration of diagonal lines could be colored in several ways---between 4 and 8, depending on how the diagonals go. For example: XXXX XXXXXX XXXXXX XXXX XXXX XXXXXX XXXX XX XX XX XX XXXX XXXX XX XX XXXX X X X X XXXX XXXX X X XXXX XXXXXX X XXX X X X XXX XXXX XXXX XX XX XX XX XX XX XX XX XXXX XXXX X X XXX X XXXXXX XXX X XXXX In each case, all four diagonals run from northwest to southeast. We can describe a patch by listing the descriptors of the eight triangles, grouped by which triangles form connected regions. For example, the first block above is: XXXX XXXX XXXX XXXX XXXX XXXX b/bf/ee/fi/i because there's an isolated white "b" triangle, then a black rhombus made of a "b" and an "f" patch, then a white triangle made from the two white "e" patches, then another rhombus made from the black "f" and "i", and finally in the middle, the white "i". The other five are, in order: b/b/e/e/f/f/i/i b/bfi/ee/f/i bf/bf/e/e/i/i bfi/bfi/e/e b/b/e/e/fi/fi All six have "bbeeffii", but grouped differently depending on the colors. The second one has no regions with more than one triangle; the fifth has two large regions of three trianfles each, and two isolated triangles. I made up a list of the descriptors for all 72 blocks; I think I did this by hand. From this one can automatically extract a list of descriptors of interesting shapes: an interesting shape is two or more letters that appear together in some descriptor. (Or it's the letter "j", which is exceptional; see below.) For example, "bffi" is an interesting shape It can only occur in a patch that has a "b", two "f"s, and an "h", like this one: +---+---+ |\ b|\ e| | \ | \ | |b \|f \| +---+---+ |\ f|h /| | \ | / | |e \|/ j| +---+---+ and it will only be significant if the b, the two f's, and the h are the same color: +------+ |XXXX | | XXXX | | XXXX| |XXXXXX| | XXXX | | XX | +------+ in which case you get this distinctive and interesting-looking hook shape. There is only one block with this shape; it has descriptor b/bffh/ee/j. But some of the distinctive shapres are more common. A block with "ee" in its descriptor always looks like this: +------+ |...XXX| |... XX| |... X| |X ...| |XX ...| |XXX...| +------+ and the blocks formed from such patches always have half-diamonds on each edge, like this: +------------+ |...XXXXXX...| |... XXXX ...| |... XX ...| |X ...... X| |XX ...... XX| |XXX......XXX| |XXX......XXX| |XX ...... XX| |X ...... X| |... XX.....| |... XXXX....| |...XXXXXX...| +------------+ The blocks at http://hop.perl.plover.com/quilt/analysis/images/ee.html all have two e's. There are a lot of differences between them, but they have the half-diamonds in common. Other shapes have similar short descriptors. The two pinwheels I mentioned above are "gh" and "fi", respectively; if you look at http://hop.perl.plover.com/quilt/analysis/images/gh.html http://hop.perl.plover.com/quilt/analysis/images/fi.html you'll see all the blocks with each kind of pinwheel. "j" is an exception; it makes an interesting shape all by itself, because any block whose patches have "j" in their descriptor will have a distinctive-looking diamond in the middle; the four-patch looks like this: +------+ |......| |......| |......| |... X| |... XX| |...XXX| +------+ so the full sixteen-patch looks like this: +------------+ |............| |............| |............| |... XX ...| |... XXXX ...| |...XXXXXX...| |...XXXXXX...| |... XXXX ...| |... XX ...| |............| |............| |............| +------------+ Where the "..." parts can vary. A look at http://hop.perl.plover.com/quilt/analysis/images/j.html will confirm that they all have this basic similarity. So I had made a list of the descriptors for the 72 blocks; that's http://hop.perl.plover.com/quilt/analysis/blocks and from this I extracted a list of the descriptors for interesting shapes; that's http://hop.perl.plover.com/quilt/analysis/shapes and then it's only a matter of finding the shape descriptors in the block descriptors to know which blocks contain which shapes; if two blocks both have the descriptors for two different distinctive shapes, they probably look somewhat similar. The page at http://hop.perl.plover.com/quilt/analysis/images/similarity-2.html lists, for each block, which other blocks have at least two shapes in common with it. Such blocks do indeed tend to look quite similar. Going a little further, http://hop.perl.plover.com/quilt/analysis/images/similarity-3.html lists for each block the blocks that have *three* shapes in common; such blocks are so similar to each other that they are hard to distinguish from one another. This was actually the second thing I tried; the first thing didn't work out well. I was satisfied enough with this that I considered the project a success and stopped work on it. I hope this wasn't more than you wanted to know. ------- End of Forwarded Message