matching jigsaw puzzle pieces

Question

I have nothing useful to do and was playing with jigsaw puzzle like this:

alt text http://manual.gimp.org/nl/images/filters/examples/render-taj-jigsaw.jpg

and I was wondering if it'd be possible to make a program that assists me in putting it together.

Imagine that I have a small puzzle, like 4x3 pieces, but the little tabs and blanks are non-uniform - different pieces have these tabs in different height, of different shape, of different size. What I'd do is to take pictures of all of these pieces, let a program analyze them and store their attributes somewhere. Then, when I pick up a piece, I could ask the program to tell me which pieces should be its 'neighbours' - or if I have to fill in a blank, it'd tell me how does the wanted puzzle piece(s) look.

Unfortunately I've never did anything with image processing and pattern recognition, so I'd like to ask you for some pointers - how do I recognize a jigsaw piece (basically a square with tabs and holes) in a picture?

Then I'd probably need to rotate it so it's in the right position, scale to some proportion and then measure tab/blank on each side, and also each side's slope, if present.

I know that it would be too time consuming to scan/photograph 1000 pieces of puzzle and use it, this would be just a pet project where I'd learn something new.

Answer 1

Data acquisition

(This is known as Chroma Key, Blue Screen or Background Color method)

1. Find a well-lit room, with the least lighting variation across the room.
2. Find a color (hue) that is rarely used in the entire puzzle / picture.
3. Get a color paper that has that exactly same color.
4. Place as many puzzle pieces on the color paper as it'll fit.
   • You can categorize the puzzles into batches and use it as a computer hint later on.
   • Make sure the pieces do not overlap or touch each other.
   • Do not worry about orientation yet.
5. Take picture and download to computer.
   • Color calibration may be needed because the Chroma Key background may have upset the built-in color balance of the digital camera.

Acquisition data processing

1. Get some computer vision software
   • OpenCV, MATLAB, C++, Java, Python Imaging Library, etc.
2. Perform connected-component on the chroma key color on the image.
   • Ask for the contours of the holes of the connected component, which are the puzzle pieces.
3. Fix errors in the detected list.
4. Choose the indexing vocabulary (cf. Ira Baxter's post) and measure the pieces.
   • If the pieces are rectangular, find the corners first.
   • If the pieces are silghtly-off quadrilateral, the side lengths (measured corner to corner) is also a valuable signature.
   • Search for "Shape Context" on SO or Google or here.
   • Finally, get the color histogram of the piece, so that you can query pieces by color later.
5. To make them searchable, put them in a database, so that you can query pieces with any combinations of indexing vocabulary.