Jigsaw puzzle solver

[jumpjack]

I have a huge (6000 piecese) jigsaw puzzle I'm not able to finish, so I was thinking about getting some help from my PC.
I was thinking about splitting the sample image:



into a grid, based on pieces size:


and then to compare each remaining piece to each square, of course rotating the piece in 4 positions. But I'm not quite sure if any existing free "duplicate images finder" would be able to determine that these two images are actually the "same":




So I think I'd need to use a different kind of grid which gets rid of "cavities" and "projections":


How can I obtain such a grid from an image using ImageMagick?

And, once I have it, is it possibile to create several different files from it (one per piece)?

And, finally, does it exist an ImageMagick function to "fuzz compare" two images?



But actually, being able to create such a program would be really cool!
http://www.youtube.com/watch?v=BnGu3t5oNdA

In this video, OpenCV is used rather than ImageMagick; it's also free and opensource... but I can't find any source of the jigsaw solver!
Could imagemagick be used to create such a program?

[glennrp]

Code: Select all

convert -crop 200x200 jigsaw.jpg tile%04d.ppm
mogrify -frame 20x20 tile*.ppm

Then do whatever you want with the tiles. Someone else
will have to suggest how to compare the pieces with the
tiles.

[fmw42]

For cropping into multiple pieces, see above from glennrp and http://www.imagemagick.org/Usage/crop/#crop_tile

Add +repage if you do not need to keep the virtual canvas position, which may cause other problems with further processing.


IM has a compare function for two images the same size or for two different size images. But note that it is rotation sensitive. So any rotation may cause the compare to mismatch. Any way see

http://www.imagemagick.org/script/compare.php
http://www.imagemagick.org/script/comma ... age-search
http://www.imagemagick.org/Usage/compare/
http://www.imagemagick.org/Usage/compare/#statistics

For two same-sized images:
compare -metric rmse image1 image2 null:

other metrics are available (such as fuzz if transparency is involved) as well

For comparing two different size images, see

viewtopic.php?f=1&t=14613&p=51076&hilit ... ric#p51076

but add -subimage-search, since the above was created, the compare function for different size images has changed and requires this option to tell it to look for the best match of the smaller image in the larger one.

[anthony]

There are many methods of comparing images. But for a jigsaw, I do not think just simply rotating the piece in 4 (90 degree) units will be enough. Can you be sure you actually get the 'piece' with exactly the right rotation?

As such you will need to look at a rotation invarient method of determining a pieces location.

This is not very simple, and involves transforming the images into a special form to do the search.
Including Polar transforms, Log transforms, and fourier transforms.

I have planned to look at this, but never see to get around to it.


Also in jigsaw puzzles you often get areas of blank or similarity (repeated parts). This type of search even if you have a copy of the final image, will only give you multiple possible locations, not a definitive location, which can only be determined by how the pieces join together, perhaps with some orientation help from small texture effects in the piece.

[jumpjack]

There are many methods of comparing images. But for a jigsaw, I do not think just simply rotating the piece in 4 (90 degree) units will be enough. Can you be sure you actually get the 'piece' with exactly the right rotation?

why not?

As such you will need to look at a rotation invarient method of determining a pieces location.

The method used in above video would be indeed cool!

Also in jigsaw puzzles you often get areas of blank or similarity (repeated parts).

Of course images comparison is totally useless for single-color pieces, but I have a puzzle with hundreds of pieces (out of 6000) with plenty of lines and colors, but I can't position after months of "work".

[jumpjack]

Does ImageMagick have any SIFT/SURF feature/implementation?

I found this cool SW... but I can't get it working in windows (can't get the .key files)

http://www.cs.ubc.ca/~lowe/keypoints/

Resources:
http://en.wikipedia.org/wiki/Speeded_Up_Robust_Features

[el_supremo]

It works in Win7 Pro for me. In a DOS window just use the command:

Code: Select all

siftwin32 <book.pgm >book.key

Pete

[jumpjack]

It works in Win7 Pro for me. In a DOS window just use the command:

Code: Select all

siftwin32 <book.pgm >book.key

Pete

This is very weird: of course I tried this example, but I always got a PGM file inside the .key file, and the program output itself said "PGM file created" or something like that.
Now I just tried... and it works properly.

I can't understand.

[jumpjack]

Damn, I added (erroneously) the -display switch!!! RTFWM!!! (W=Whole )

[fmw42]

You could try using the plugin for Surf in ImageJ

[jumpjack]

Since I installed Nokia OVI Suite I can't run any java program, as .JAR is nowassociated to "installation on phone"!

[whugemann]

Your problems with Java aside -- I also think that ImageJ is the right program for ready-made solutions on special problems like this. I used its SIFT tools to settle a very shaky video and found them doing amazingly well.