Match puzzle pieces

Question

I have nothing to do and played with a puzzle like:

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

and I was wondering if it is possible to make a program that helps me in combining it.

Imagine that I have a small puzzle, for example 4x3 pieces, but the small tabs and blanks are uneven - different pieces have these tabs of different heights of different shapes of different sizes. I would do to photograph all of these parts, let the program analyze them and store their attributes somewhere. Then, when I pick up the piece, I could ask the program to tell me which parts should be its “neighbors”, or if I have to fill in the blank, it will tell me how to look at the puzzle.

Unfortunately, I never did anything with image processing and pattern recognition, so I would like to ask you for some pointers - how do I recognize a piece of the puzzle (mostly a square with tabs and holes) in the picture ?

Then I will probably have to rotate it so that it is in the correct position, scale to some extent, and then measure the tab / workpiece on each side, as well as each lateral tilt, if present.

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

Answer 1

Data collection

(This is called the Chroma Key, Blue Screen or Background Color method)

• Find a well-lit room with minimal lighting in the room.
• Find a color (tint) that is rarely used throughout the puzzle / picture.
• Get colored paper that has the same color.
• Place as many puzzle pieces on the colored paper as it fits.
  • You can classify puzzles in a batch and use it as a computer tooltip later.
  • Make sure the pieces do not overlap or touch each other.
  • Do not worry about orientation.
• Take a picture and upload it to your computer.
  • Color calibration may be required as the Chroma Key background may interfere with the color balance of the digital camera.

Data collection processing

• Get Computer Vision Software
  • OpenCV, MATLAB, C ++, Java, Python Image Library, etc.
• Run a component connected to the color of the color in the image.
  • Define the outlines of the holes of the connected component, which are pieces of the puzzle.
• Correct errors in the detected list.
• Select the indexing dictionary (see Ira Baxter's post) and measure the fragments.
  • If the shapes are rectangular, first find the corners.
  • If the pieces are firmly quadrangular, the length of the side (measured angle to angle) is also a valuable signature.
  • Search for “Form Context" on SO or Google or.
  • Finally, get a histogram of the fragment color so that you can later request the fragments by color.
• To make them searchable, put them in a database so you can query snippets with any combination of indexing dictionary.

Answer 2

Step back to the problem itself. The problem of creating a puzzle can be easy (P) or hard (NP), depending on whether the pieces fit only one neighbor or many. If for each edge there is only one suitable, then you just find for each part / side of its neighbor, and you are done (O (# pieces * # sides)). If some parts allow multiple insertions into different neighbors, then you may need to retreat to complete the entire puzzle (because you made the wrong choice and you're stuck).

However, the first problem that needs to be solved is how to represent the shapes. If you want to represent arbitrary shapes, then you can probably use transparency or masks to represent which areas of the tile are actually part of the piece. If you use square shapes, the problem could be simpler. In the latter case, you can consider the last row of pixels on each side of the square and compare it with the most similar rows of pixels, which you will find in all other parts.

You can use the second approach to help you solve the real puzzle, even though you use square tiles. Real puzzles are usually built on an NxM grid. When scanning an image from a window, you break it into the same NxM square grid and get a system to solve this problem. The problem is to visually display the actual piece that you hold in your hand, with the tiles inside the system (when they are small and evenly colored). But you get the same problem if you arbitrarily represent arbitrary forms.