Jigsaw puzzle solver

Questions and postings pertaining to the usage of ImageMagick regardless of the interface. This includes the command-line utilities, as well as the C and C++ APIs. Usage questions are like "How do I use ImageMagick to create drop shadows?".
Post Reply
jumpjack
Posts: 69
Joined: 2010-12-10T05:29:16-07:00
Authentication code: 8675308

Jigsaw puzzle solver

Post by 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. 8)
I was thinking about splitting the sample image:
Image


into a grid, based on pieces size:
Image

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":
Image

Image

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

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?
Last edited by jumpjack on 2011-07-09T12:28:10-07:00, edited 1 time in total.
User avatar
glennrp
Posts: 1147
Joined: 2006-04-01T08:16:32-07:00
Location: Maryland 39.26.30N 76.16.01W

Re: Jigsaw puzzle soler

Post by 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.
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Jigsaw puzzle soler

Post by 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.
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: Jigsaw puzzle solver

Post by 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.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
jumpjack
Posts: 69
Joined: 2010-12-10T05:29:16-07:00
Authentication code: 8675308

Re: Jigsaw puzzle solver

Post by jumpjack »

anthony wrote: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?
anthony wrote: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
Posts: 69
Joined: 2010-12-10T05:29:16-07:00
Authentication code: 8675308

Re: Jigsaw puzzle solver

Post by 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
Posts: 1015
Joined: 2005-03-21T21:16:57-07:00

Re: Jigsaw puzzle solver

Post by 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
Sorry, my ISP shutdown all personal webspace so my MagickWand Examples in C is offline.
See my message in this topic for a link to a zip of all the files.
jumpjack
Posts: 69
Joined: 2010-12-10T05:29:16-07:00
Authentication code: 8675308

Re: Jigsaw puzzle solver

Post by jumpjack »

el_supremo wrote: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. :shock:

I can't understand. :shock:
jumpjack
Posts: 69
Joined: 2010-12-10T05:29:16-07:00
Authentication code: 8675308

Re: Jigsaw puzzle solver

Post by jumpjack »

Damn, I added (erroneously) the -display switch!!! :shock: RTFWM!!! (W=Whole :lol: )
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Jigsaw puzzle solver

Post by fmw42 »

You could try using the plugin for Surf in ImageJ
jumpjack
Posts: 69
Joined: 2010-12-10T05:29:16-07:00
Authentication code: 8675308

Re: Jigsaw puzzle solver

Post by jumpjack »

Since I installed Nokia OVI Suite I can't run any java program, as .JAR is nowassociated to "installation on phone"! :(
User avatar
whugemann
Posts: 289
Joined: 2011-03-28T07:11:31-07:00
Authentication code: 8675308
Location: Münster, Germany 52°N,7.6°E

Re: Jigsaw puzzle solver

Post by 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.
Wolfgang Hugemann
Post Reply