In consequence the descriptor must be able to distinguish 2000 edges requiring at least 11 bits.ĭividing one piece into a 3 x 3 check board pattern with nine fields will give three colors per edge - with eight bits per channel we already have 72 bits. Given a puzzle with 1000 pieces, there are 4000 edges and always two must be equal (ignoring the border of the puzzle). The descriptor must contain information about the rough shape and the color of the piece respectively the four edges. Given a set of images of all pieces I would try to derive a simple descriptor for every piece or edge. I don't think that the human way would be that helpful for an implementation - a computer can look at all pieces many times a second and I see no (big) win by categorizing the pieces into corner, edge, and inner pieces, especially because there are only three categories and they have very different sizes. Pieces that match should have mirror-image contour maps. Using the four corner pieces originally identified, we should now be able to reconstruct the dimensions and positions of all of the pieces in the puzzle.Ī convenient data structure for representing edge shapes may be a contour map - essentially a set of integers representing the incremental deltas in distance from the opposing side of the image to the last non-transparent pixel in each of the four sides of the puzzle piece. This is somewhat tricky because it requires a level of fuzzy matching - since not every pixel-to-pixel boundary will necessarily have a smooth color transition. Now we can prune this adjacency matrix to identify just those pieces that have smooth color transitions in their adjacent configuration. This information can be used to build an adjacency matrix indicating which pieces fit together. Next, I would build information about the shape of each of the four edges of a puzzle piece.
These would have exactly two edges that have flat contours (see contour map below).
So what kind of information will the program will be supplied - let's assume that each puzzle piece is an small rectangular image with transparency information used to identify the portion of the puzzle piece that represent non-rectangular edges.įrom this, it is relatively easy to identify the four corner pieces (in a typical jigsaw).
0 kommentar(er)
