Webcam Jigsaw Solver in 200 Lines of Python

leighklotz writes "Jeff Breidenbach and 200 lines of Python code have brought us the Glyphsaw Puzzle solver. Hold a puzzle piece up to a webcam, and the display sgiws exactly where in the puzzle the piece belongs. The solver uses the Python Imaging Library (PIL), Numerical Python, and the PARC DataGlyph Toolkit. By the way, you can make your own DataGlyphs."

its

[mr_tommy]

It's amazing how beautiful code can be - it's simple, to the point, and functional. Bravo - a good lesson here for anyone who's thought about doing anything at code level.

Wrong section?

[NemesisStar]

Shouldn't this news be under programming instead of software? The image for programming is a jigsaw getting solved!

200 lines?

[PoopJuggler]

Big deal. I can write the same thing in C in a single line of code. Oh but you have to link in 100,000,000 lines of libraries and include files, but that doesn't seem to count...

External libraries

[R.Mo_Robert]

200 lines of Python? At least this time they mentioned the additional external libraries, unlike with that "15-line" P2P program [slashdot.org] a while back...

:)

like the tetris-playing bot

[bodrell]

Anyone remember that? It was pretty cool--the guy wrote a scoring algorithm and brute-forced all possible positions for whatever piece was about to fall.

Oh, and I also think it's pretty stupid to talk about how few lines it took to write the program when it's using a bunch of libraries. I could just write a one-liner that calls this program, by that rationale.

Here's the Artificial Intelligence Tetris [colinfahey.com] I was mentioning.

Puzzle

[Anonymous Coward]

This glyph thing is all very nice and all, but it CHEATS. The puzzle is specially printed and each piece has a unique address. Where's the challenge in that?

NOW if they could do this with an off the Walmart shelf puzzle, THAT would be something.

It's not image recognition

[Yobgod Ababua]

It reads digital information encoded into the image... it doesn't look at the actual image itself. It's still quite cool, but no good for what you are thinking.

I already explained more about this to a comment Here [slashdot.org]

This isn't as clever as you think

[Anonymous Coward]

Neat, but not amazing. You have to read the article to realize that the system only works if all the puzzle pieces have been printed with special marks, DataGlyphs [parc.com]. It's like printing registration marks on all the pieces. Sort of. The dataglyphs actually have more interesting properties, but the point is that this isn't the vision system you expect. It isn't even a general puspose puzzle solving system. As soon as the system recognizes the glyph marks it knows exactly where the piece belongs. It doesn't "solve" anything. It doesn't have to figure out where the pieces go. You couldn't show it pieces from a puzzle off the shelf and have it solve it.

It's a cheat

[Anonymous Coward]

They can only solve puzzles that have been printed with their special dataglyph patterns. So, matching the piece to its location is trivial.

The real challenge would to do this with a regular jigsaw puzzle, not a specially rigged one.

The computer vision technology necessary to do this exists today. It's just a matter of putting it together.

Lame!

[CyberVenom]

Somebody please amend the OP. When the site finishes melting down no one will have a clue what this is about:

Essentially it is just a bunch of puzzle pieces with 2-D barcodes printed on them, and a computer+webcam+python used as a barcode reader.

(oh, and as a bonus, the 2-D barcodes are somewhat colored so that it looks like a picture from a distance.)

It is no more a "Jigsaw Puzzle Solver" than a locomotive's wheels are an autopilot decive. They each achieve the end goal only when the rails have been laid in advance.

-CV

Oh yeah, GlyphMarks

[Anonymous Coward]

I liked them better when they were called "two-dimensional bar codes".

This /. post is a little misleading by the way... the webcam and software doesn't "solve" the jigsaw puzzle, it just reads the coordinates which are encoded on each piece.

You wanna repeat this experiment at home? Buy a small jigsaw puzzle. Solve it. Label each piece with it's (x,y) coordinate in the solved puzzle. For instance, top-left could be (1,1), the one to its immediate right could be (2,1), and so on.

Then take the puzzle apart and AMAZE your friends when you can deduce the position of each piece simply by HOLDING IT UP TO YOUR EYES!

This defeats the entire purpose of doing jigsaws.

[i41Overlord]

If you wanted the picture put together for you, you'd buy a poster, not a jigsaw puzzle.

When the entire purpose of buying a puzzle is to make you do some mental work, then having that work done automatically is self-defeating.

Re:its

[gfody]

this isn't a jigsaw solver. the puzzle needs to be created with the glyph marks already. its like each peice has an embedded watermark telling the program where it goes.

at first glance I thought it was a program that could solve jigsaw puzzles by analyzing each piece, its shape, the image on it and figure out where it goes in realtime. that would be really interesting as it would probably have to employ some crazy neural net algo to avoid exponential time.

Dataglyphs

[Anonymous Coward]

Recall the stories about how printers where marking reproductions of bills- well this is how it's done.
Fairly neat.

Re:This defeats the entire purpose of doing jigsaw

[psyconaut]

You're 100% missing the point. It's not about doing the jigsaw, but using glyphs to identify realworld objects and placing those in perspective.

-psy

so what?

[Anonymous Coward]

I was prepared to be impressed but then I read that each piece is basically pre-encoded so it's only a matter of reading the coding. Much less impressive than actually using the image on the piece to determine its proper position.

Re:200 lines?

[thedustbustr]

> What is a reliable means of counting LOC then?

Count every line of code written specifically for this project. Publically availabe libraries don't count; internal libraries written by the author (for use in this project or generalized internal code from a previous project does. This accurately reflects the complexity of the app from the coder's perspective.