Ask Your Question
1

Analyze contour of jigsaw puzzle pieces

asked 2013-03-24 12:21:06 -0500

Sergey Shepelev gravatar image

updated 2013-03-25 17:22:02 -0500

Hello. As a pet project for learning OpenCV, i'm trying to make jigsaw puzzle solver that would work purely on shape (ignore colors). I found SimpleCV a great library. Thanks to everyone involved very much.

I found these posts to be very helpful:

Although, i'm stuck at finding holes and bulges.

Here's what i do:

  1. Take photo of pieces on chroma key (cropped)

  2. Simple threshold-like processing in Gimp, although i can imagine it could be automated using OpenCV

  3. SimpleCV.Image('pieces.png').findBlobs(minsize=40000, maxsize=90000) for each blob: .crop().save(distinct_file)

  4. That's where i'm stuck. How to measure pieces in useful way? When i try to apply img.findCorners(maxnum=4, mindistnace=200) i get this: red dots are detected by computer, green - by me in Gimp. I think i could draw straight lines connecting proper corners, then any white color outside that contour would be bulge and any black color inside would be hole. I believe they even would be detected by .findBlobs().

    Next thing i would like to do is calculate length of two continuous lines on each side (that is excluding any hole/bulge), as shown on image. I believe these lengths, normalized to length of side is enough hint to match majority of puzzle. Probably major problem here is that pieces are not perfect squares (red side is twisted clock wise, green side is rounded) and even worse, pieces as whole are slightly rotated relative to camera view.

Update 1 to my programmer's shame i used Gimp again to align all pieces on grid on a large canvas, but it could be easily done in SimpleCV (or even PIL for that matter). Having all pieces in static grid allows for a lot of simplifications in latter processing. Next, i threw a few hours at it and marked all corners, bulges and holes by hand.

Next (this part needs comments from SimpleCV experts) i tried but failed to enumerate all red/blue blobs on that image. Naive .findBlobs returns big white blobs, with maxsize=500 it does not 'see' anything. It would seem to me a perfect fit for .findBlobsFromPalette, but it yields AttributeError, so i called .getPalette but it does not recognize pure red and blue colors at all, (consequently?) does not find blobs by red color which is absent from palette. Even when i do .getPalette(centroids=[RED,BLUE,WHITE,BLACK]) and they're in result, it still does not 'see' any red/blue blobs by palette. Of course, all these tries were repeated on new Image object.

What has worked, although i feel this may be ugly:

corners = img.hueDistance((255,0,0)).threshold(1).invert().findBlobs(minsize=1, maxsize=1000)
features = img.hueDistance((0,0,255)).threshold(1).invert().findBlobs(minsize=1, maxsize=1000)

Smells delicious! Thanks to grid align, i can easily map each blob to corresponding puzzle piece by int(f ... (more)

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
1

answered 2013-03-25 09:59:04 -0500

kscottz gravatar image

This is a totally awesome question. Thanks for asking it.

The short answer to your question is that we don't have a super simple way to solve your problem but I can think of a few ways to approach the problem. If I were trying to solve this I would work by assuming that all puzzle pieces are roughly square, and try to find the lines that define the square that best fit the pieces. Once you have that you can define the convexity/concavity that defines the "dangly-ness" or "hole-ness" of each piece. For each piece I would extract the dangley/hole bits so that they are flat on one side, and rectify them so that all the flat sides face one way. I hope that makes sense. From that information I would then define a match function that tries to match the contours (hint Blobs.contour returns a list of (x,y) points for each contour). We hope to get a full suite of contour matching tools in our next release. If you get something that works well we would love to fold it back into the library.

About a year ago DARPA had a contest to reassemble shredded paper bits. You may want to go scour the web and see how other people approached a similar problem.

We just adjusted the karma required to post links, so please feel free to update us with your progress.

edit flag offensive delete link more
0

answered 2013-03-25 13:44:32 -0500

Sergey Shepelev gravatar image

On-topic. Thank you for answer. I don't get what specific (if any) kind of approach do you have in mind with this:

For each piece I would extract the dangley/hole bits so that they are flat on one side, and rectify them so that all the flat sides face one way. I hope that makes sense

Indeed it makes a lot of sense and i was asking close thing:

I think i could draw straight lines connecting proper corners, then any white color outside that contour would be bulge and any black color inside would be hole. I believe they even would be detected by .findBlobs().

But how? I can find exterior points using .contour and .boundingBox but can't easily tell apart corners from bulges because pieces may be rotated. Do you have any specific algorithm or direction in mind? It's not obvious to me. I guess i could make some analysis on angle of corner and select those closer to 90, but lacking that level of math skill it starts to be very complicated or probabilistic. I am all for probabilistic models but complicated ones tend to break.

Off-topic. Thanks for karma adjustment. I've updated post with links, hopefully it looks more attractive now. Next problem is that i can't comment your answer, so have to use new answer.

edit flag offensive delete link more

Comments

I think you are going to need to dig deep into the contour object to get this to work. You may also want to look at the blob.rectifyToMajorAxis command(). This command is kinda beta but it will rotate the image so that its major (longest) axis points in a certain direction.

kscottz gravatar imagekscottz ( 2013-03-26 16:15:05 -0500 )edit

Thank you. A friend has suggested sunshine (or pizza) algorithm to detect corners: while following contour, if we build a circle of certain radius and cut it to N sectors, like pizza, then sectors located at closer to 90⁰ would have more contour points than others.

Sergey Shepelev gravatar imageSergey Shepelev ( 2013-03-27 00:52:47 -0500 )edit

Also now i can comment your answer. Great!

Sergey Shepelev gravatar imageSergey Shepelev ( 2013-03-27 00:53:09 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2013-03-24 12:21:06 -0500

Seen: 2,723 times

Last updated: Mar 25 '13