I would like to solve a real jigsaw puzzle in Java of dimension n*m by running it through an algorithm. The actual output, i.e., the image is known beforehand. These are my thoughts so far. Align all puzzle pieces on a piece of paper that is of a color which the puzzle itself does not contain and take a picture. Crop all pieces to n*m subimages. Acquire RGB values for every pixel in every piece, disregard the pixels containing the color of the paper (to consider the special shape of every piece). Get n*m subimages from the actual output image. This is where I'm having trouble. If I would like to compare the pieces, how do I take the puzzle shape into consideration? To sum up, is comparing RGB values a promising approach? How would I continue? Are there better, simpler ways like FFT or some sort? Thank you for your input!

If your image is of sufficient quality, you can probably solve the problem looking at the pictures only when multiple pieces can fit into a given slot. The following pseudocode may work: aquire piece outlines, using the photograph-on-a-high-contrast-background approach, and making sure to compensate for any lens distortion. build the outer ring, by identifying all outer-ring-pieces (with one or two straight sides) and matching them shape-wise against all others. Consider a match when two pieces fit snug together: minimize (overlapArea + emptyArea) , where overlapArea is the amount of overlap when the pieces are placed one after the other, and emptyArea the amount of free space between the pieces when they are placed next to each other. Break ties(and near-ties) by using color information. Matching the initial 4-corners to the image on the box should be relatively simple. build successive rings by taking one existing ring-corner and finding the next piece to place into that corner (where a placed piece will have 2 neighbors). At the end of step 2, there will be 4 corners. After placing another piece in that corner, there will be 5. Simply continue placing pieces in corners until the last piece fits in the last space. The geometric part of this approach requires two ingredients: Acquire image outlines: correcting for distortion (cameras introduce spherical distortion near the sides; plus the perspective is probably off if the photo is not taken from straight above the pieces). This is not easy in general, ask in a separate question to get some image experts involved . use an outline-finding algorithm to find the outline-geometry for each piece. I have successfully used marching squares for this task. To match image outlines, you can take several short-cuts to filter out bad matches. For example, matching borders must have similar lengths , and opposite orientations . Match the two corners of each pair of pieces first (which must have the same separation); then use a geometry library (I recommend JTS ) to see how much they overlap, as defined by minimizing (overlapArea + emptyArea) . You can find code to mix JTS and vertex-sequences here . The image-matching part also requires two ingredients: Prepare images for matching: get the distortion fixed, both in piece-images and in the box-image. Also, make sure to take the box-image under the same lighting conditions as the piece-images, because otherwise the match will be more difficult. This is hard to do - again, ask in a different question if you need the details . take a histogram of the centre pixels of each piece, using a uniform radius that guarantees that no piece-border will be included. This is rotation-invariant. take the same histograms from a the centers-of-pieces according to the box image. Note that most jigsaws follow a fairly strict grid, with equally-spaced rows and columns. You will need to either input or detect the grid dimensions before you do this. When deciding if a piece matches at a certain point, check compare its centre's colour histogram against the expected box-histogram for that grid position. Use, for example, mean-squared-error as a match metric. That is, if you have two pairs of red, green and blue histograms (R1, R2, G1, G2, B1, B2) with 256 values per histogram (8bbp), each of them a floating-point value counting the fraction of pixels in the corresponding circle with that pixel intensity, then square all differences and add them up to come with an error value: error = (R1[0]-R2[0])*(R1[0]-R2[0]) + ... + (B1[255]-B2[255])*(B1[255]-B2[255]) . Going geometry-only will only work if all pieces are unique, something that is in general not the case (several puzzles re-use piece outlines over and over again). Going image-only will only work if there are no repeated motifs, such as large areas of sky or trees or windows or masonry. A general approach must use both sources of information to succeed. Edited to add in some image-matching, because geometry alone is not enough given the jigsaw examples linked by the OP

javaalgorithmpuzzle

marcopolo

Reputation: 13

Solving a real jigsaw puzzle with knowledge of the output

I would like to solve a real jigsaw puzzle in Java of dimension n*m by running it through an algorithm. The actual output, i.e., the image is known beforehand. These are my thoughts so far.

Align all puzzle pieces on a piece of paper that is of a color which the puzzle itself does not contain and take a picture.
Crop all pieces to n*m subimages.
Acquire RGB values for every pixel in every piece, disregard the pixels containing the color of the paper (to consider the special shape of every piece).
Get n*m subimages from the actual output image.
This is where I'm having trouble. If I would like to compare the pieces, how do I take the puzzle shape into consideration?

To sum up, is comparing RGB values a promising approach? How would I continue? Are there better, simpler ways like FFT or some sort?

Thank you for your input!

Upvotes: 1

Answers (3)

tucuxi

Reputation: 17945

If your image is of sufficient quality, you can probably solve the problem looking at the pictures only when multiple pieces can fit into a given slot. The following pseudocode may work:

aquire piece outlines, using the photograph-on-a-high-contrast-background approach, and making sure to compensate for any lens distortion.
build the outer ring, by identifying all outer-ring-pieces (with one or two straight sides) and matching them shape-wise against all others. Consider a match when two pieces fit snug together: minimize (overlapArea + emptyArea), where overlapArea is the amount of overlap when the pieces are placed one after the other, and emptyArea the amount of free space between the pieces when they are placed next to each other. Break ties(and near-ties) by using color information. Matching the initial 4-corners to the image on the box should be relatively simple.
build successive rings by taking one existing ring-corner and finding the next piece to place into that corner (where a placed piece will have 2 neighbors). At the end of step 2, there will be 4 corners. After placing another piece in that corner, there will be 5. Simply continue placing pieces in corners until the last piece fits in the last space.

The geometric part of this approach requires two ingredients:

Acquire image outlines:
- correcting for distortion (cameras introduce spherical distortion near the sides; plus the perspective is probably off if the photo is not taken from straight above the pieces). This is not easy in general, ask in a separate question to get some image experts involved.
- use an outline-finding algorithm to find the outline-geometry for each piece. I have successfully used marching squares for this task.
To match image outlines, you can take several short-cuts to filter out bad matches. For example, matching borders must have similar lengths, and opposite orientations. Match the two corners of each pair of pieces first (which must have the same separation); then use a geometry library (I recommend JTS) to see how much they overlap, as defined by minimizing (overlapArea + emptyArea). You can find code to mix JTS and vertex-sequences here.

The image-matching part also requires two ingredients:

Prepare images for matching:
- get the distortion fixed, both in piece-images and in the box-image. Also, make sure to take the box-image under the same lighting conditions as the piece-images, because otherwise the match will be more difficult. This is hard to do - again, ask in a different question if you need the details.
- take a histogram of the centre pixels of each piece, using a uniform radius that guarantees that no piece-border will be included. This is rotation-invariant.
- take the same histograms from a the centers-of-pieces according to the box image. Note that most jigsaws follow a fairly strict grid, with equally-spaced rows and columns. You will need to either input or detect the grid dimensions before you do this.
When deciding if a piece matches at a certain point, check compare its centre's colour histogram against the expected box-histogram for that grid position. Use, for example, mean-squared-error as a match metric. That is, if you have two pairs of red, green and blue histograms (R1, R2, G1, G2, B1, B2) with 256 values per histogram (8bbp), each of them a floating-point value counting the fraction of pixels in the corresponding circle with that pixel intensity, then square all differences and add them up to come with an error value: error = (R1[0]-R2[0])*(R1[0]-R2[0]) + ... + (B1[255]-B2[255])*(B1[255]-B2[255]).

Going geometry-only will only work if all pieces are unique, something that is in general not the case (several puzzles re-use piece outlines over and over again). Going image-only will only work if there are no repeated motifs, such as large areas of sky or trees or windows or masonry. A general approach must use both sources of information to succeed.

Edited to add in some image-matching, because geometry alone is not enough given the jigsaw examples linked by the OP

Upvotes: 1

Kostas Kryptos

Reputation: 4111

You are looking for Template Matching (finding image (puzzle piece) inside another image (the original image)).

You can iterate over your pieces and slide each one to the original image (by a step of the piece size) comparing similarity of all pixels. If you need to rotate the pieces, you need to store 4 values (orientation per position).

The maximum similarity will give you the correct position-orientation. If the pieces were cropped from the original image (and are of the same quality, relative size), you will expect to find a perfect match for each piece.

For image comparison, the simplest way is to store the aggregated RGB distance of each pixel, see here, or pHash (on java here).

Due to the fact that in a normal jigsaw puzzle, pieces are not rectangles (somehow irregular shape), when comparing, ensure that the you compare only the overlaid part of the original image (various ways to achieve that).

FYI: Solving a Jigsaw puzzle is NP-complete (see a related paper here) (imagine a worst case scenario where the image is pure green at all, no shapes, nothing; thus the output may not provide any clues :)

FYI 2: There used to be the Eternity Puzzle contest with real money prize, where winners (mathematicians) solved it in 7 months using two domestic PCs. Then Eternity II, with no winners! So you understand this is a tough project!

Upvotes: 0

user1196549

Reputation:

First thoughts:

I would first try and add every piece in turn

geometrically (where does the piece fit tightly ?),
by colors (in case different pieces fit at the same place).

For this, you will maintain a picture where the previous pieces have been placed, with the background color being reserved.

Before trying a new piece, you have to obtain the boundary of the free area, which is a curve. (After adding a piece, the update of this curve can be made locally).

Then take a piece and choose a point on its outline. By sweeping this point on the curve, you can find a place where it fits, with a significant overlap. Keep the piece that realizes the longest fit.

In case of ties (or quasi-ties), check the colors with a similarity score such as SAD.

This will be horribly time consuming, though.

Second thought:

There is probably now way to know the exact orientation of the pieces (unless some part of the outline is guaranteed to be horizontal/vertical). Trying different angles will worsen the running time.

An alternative is to pick two points, some known distance apart on the outline of a piece. Then you slide the first point on the boundary curve and find the position of the other point, ahead on the outline and respecting the distance constraint.

Update:

If the pieces are all identical, the geometric search becomes irrelevant. But the good news is that the placement of the pieces becomes highly predictable (the pieces are just on a regular grid).

So every piece can be tried in turn at the desired place, and the correct match be based on the colors of the known image, or on the colors in the neighboring piece(s), along the common edge(s).

It is advisable to put the pieces that achieve the best match first, in order to minimize the probability of false matches.

Upvotes: 0

Solving a real jigsaw puzzle with knowledge of the output

Answers (3)

Related Questions