1

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.

  1. 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.

  2. Crop all pieces to n*m subimages.

  3. 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).

  4. Get n*m subimages from the actual output image.

  5. 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!

Mike Samuel
  • 118,113
  • 30
  • 216
  • 245
marcopolo
  • 13
  • 4
  • 1
    You have several interesting problems in your question, from image preparation to border-finding to internal representation. Unless you know your way around image processing in java, this is *not* a simple project. – tucuxi Dec 27 '15 at 10:52
  • You're right, that's why I like it. However, I'm just not sure what the best way is to "identify" an image. I have heard about Fourier, wavelets etc in college, I just don't know how much of that is really necessary if I have two images that are -almost- the same (differences are probably slight RGB variation and the puzzle shape of course). – marcopolo Dec 27 '15 at 10:56
  • How are the pieces shaped ? –  Dec 27 '15 at 11:21
  • They are horizontally and vertically aligned like this: http://www.freevector.com/site_media/preview_images/FreeVector-Jigsaw-Puzzle.jpg – marcopolo Dec 27 '15 at 11:27
  • 1
    Do you mean that they all have exactly the same shape ?? (Except on edges and corners.) –  Dec 27 '15 at 11:40
  • A detailed description of the geometry of the pieces is critical to the selection of a solution. –  Dec 27 '15 at 11:45
  • I was focusing on the alignment, that is there are only 4 ways to rotate a piece. However, like with most jigsaws, the size may vary: http://previews.123rf.com/images/brunoilfo/brunoilfo1006/brunoilfo100600014/7168030-Background-Vector-Illustration-of-Blank-Jigsaw-Puzzle-each-piece-is-an-editable-blend--Stock-Vector.jpg – marcopolo Dec 27 '15 at 11:51
  • According to that last image, piece geometries are not unique - so you need to combine geometric and image-matching strategies. – tucuxi Dec 27 '15 at 16:23

3 Answers3

2

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:

  1. aquire piece outlines, using the photograph-on-a-high-contrast-background approach, and making sure to compensate for any lens distortion.

  2. 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.

  3. 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:

  1. 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.

  2. 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:

  1. 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.

  2. 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

tucuxi
  • 17,561
  • 2
  • 43
  • 74
  • Very interesting approach. My first thought was just that it should be easier if I could (and I can) use the output image without having to write a 'blind' solving algorithm. – marcopolo Dec 27 '15 at 11:29
  • Quick-and-dirty matching of images will only get you so far; only certain jigsaws will be entirely image-solvable (as in: a unique position for each piece-image by matching it against the box image); and then you will need a placement-and-matching strategy similar to the above, with geometry information being more dependable than pixel-values for border-matching. – tucuxi Dec 27 '15 at 11:39
  • After seeing lots of non-unique-piece-geometry jigsaws, I have added in some image-matching to the mix. Nice problem, but hard to crack in a general way. If I had the time, this would be fun to try to cram into a phone app... – tucuxi Dec 27 '15 at 16:49
  • Thanks for your efforts, tucuxi! I'm going to start using your latest edit with the image-matching approach. I accepted your answer for all the work you put into it! – marcopolo Dec 27 '15 at 18:53
0

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!

Community
  • 1
  • 1
Kostas Kryptos
  • 4,081
  • 2
  • 23
  • 24
  • Thank you for your answer. I haven't thought of the sliding method. On what parameters would you compare the 'similarity of all pixels'? – marcopolo Dec 27 '15 at 11:09
  • 1
    This is a good starting method. There are two issues: if the orientation of the pieces isn't well known, you will need to match with rotation; and if there are repeated patterns in the image (building with windows), some of the pieces will match at different places. The computational cost is also huge. –  Dec 27 '15 at 11:20
  • Also, patches of sky or tree or grass or shadow. Image matching is great for one-time features, but will eventually fail for parts of the image. – tucuxi Dec 27 '15 at 11:28
  • If it's a normal Jigsaw, i guess you can calibrate it to find the correct 4 horizontal-vertical positions (checking edge curvature). Even if not perfect matching, at the end you end up with some candidate positions. At this stage you have to check with your neighbors for edge matching (but now it's by far a more limited version of your problem). – Kostas Kryptos Dec 27 '15 at 11:29
0

First thoughts:

I would first try and add every piece in turn

  1. geometrically (where does the piece fit tightly ?),

  2. 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.

  • Regarding the second side, two pieces that fit together will have to share the same corners in their common edge. So the number of combinations is limited: each piece has 4 sides, and each of those sides can fit (or not) with the 4 sides of another piece. Therefore, you only have to test 16 orientations per piece-pair, which is not too bad. – tucuxi Dec 27 '15 at 11:26
  • @tucuxi: at the time of my writing, there was no information about the pieces. No even "four corneredness". –  Dec 27 '15 at 11:41