Slashdot Mirror
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."
Oh, but I bet it uses a bunch of libraries post.
Hunt your preferred prey at Aliens vs Predator MUD. Join the war at avpmud.com port 4000
Facial recognition? Or, was this a by-product of same?
Take the 90-Day Challenge! http://rwmurker.bodybyvi.com/
exactly where the 'h' and 'o' keys are.
70e808a22cb027cde4a6abddf6435d55
Shouldn't this news be under programming instead of software? The image for programming is a jigsaw getting solved!
Here's a one line puzzle solver
[user@localhost] perl -e '`python glyphsaw`'
Yes, very nice.
But the important question is, can it assemble the puzzle faster than Gary Kasparov?
Google Search: sgiws
Did you mean: shows
The shareholder is always right.
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...
Mirrordot to the rescue http://mirrordot.org/stories/df4be4026318903e35238 c9e48d22bff/index.html
A "jigsaw" is a nifty tool that dances around a pattern in a sheet of wood, a narrow saw band that cuts like a laser along curves (OK, compared to its 19th Century prececesors). A "jigsaw puzzle" is a puzzle made by jigsawing a picture, and putting it back together along its deceptively simple interlocking contours. This device substitutes an AI scanner for the saw, in inverse operation to the jigsaw. So, if anything, it's a "Jiglyph", not a "Glyphsaw" - unless they mean that it "saw" the "glyph".
--
make install -not war
200 lines of Python? At least this time they mentioned the additional external libraries, unlike with that "15-line" P2P program a while back...
R.Mo
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 I was mentioning.
Si la vida me da palo, yo la voy a soportar Si la vida me da palo, yo la voy a espabilar
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.
"The Glyphsaw Puzzle solver is implemented in less than 200 lines of Python code by making good use of the PARC DataGlyph Toolkit, the Python Imaging Library (PIL), and Numerical Python."
^ I bet you'd win that bet.
The technology is that they can embed arbitrary digital information into arbitrary images, and do it in such a way that it's resistant to errors, damage, blurriness and other rigors of the real world.
If you have a jigsaw made using this technology where the embedded data indicates the location within the original image, you can use this software to decode that data and display where the piece should go. It doesn't look at the actual image at all, and thus wouldn't help you solve any 'normal' jigsaws, or do any sort of general image recognition.
It does use some similar techniques to facial recognition to identify the intersection points and enable the glyph decoding, but that's all.
Finally ... something on Slashdot to interest my grandmother !!
-- "It's not stalking if you're married!" My Wife.
If you hold a piece of their Slashdotted Web server up to the camera, will this program be able to reassemble it?
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
For when the server melts down, here it is...
b reiden/glyphsaw/
http://www2.parc.com.nyud.net:8090/istl/members/j
Interesting article, but it's using a special digitally encoded pattern to "help" the software identify the pieces. You can't just input the picture from a puzzle box, then start showing it pieces, and have it solve them for you.
Willie...
...overlay a two-dimensional bar code over the image?
Tell me if I'm mistaken, but didn't the summary imply that it was identifying the puzzle piece by the picture on it? Now that would be cool.
So much for using this to make a face-scanner, unless we tattoo bar codes on everyone's faces.
I guess this is an interesting academic exercise, but I don't see how they've really done anything new.
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. 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.
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
I liked them better when they were called "two-dimensional bar codes".
/. 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.
This
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!
I wrote a version of this library originally as a contractor for PARC when I was in grad school, to use as the error correction coding for their data glyphs. This is bsaically the same algorithm used for audio and CD-ROM data.
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.
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.
bite my glorious golden ass.
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
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.
PARC (and others) have already tackled that problem. Here's my favorite research paper on the topic.
Goldberg, D.; Malon, C.; Bern, M. W. A global approach to automatic solution of jigsaw puzzles. Computational Geometry. 2004 June; 28 (2): 165-174.
Yep, and it's not only closed source, it's proprietary; to develop for it, you need to buy the eval kit and license the technology.
Furthermore, not a single slashdot reader seems to have noticed that the article is one giant piece of astroturf. The submitter's website plainly lists his address in Palo Alto, which just happens to be the site of PARC, the Xerox research center that developed the technology. Coincidence? I seriously doubt it.
Oh, and this technology is mostly used in color copiers for printing out the machine's serial number in pure yellow so you can't see it..but the document can be traced back to you (this is supposedly for the Secret Service to chase down people making color copies of US currency and whatnot, but that's a bullshit excuse now that these copiers all have currency detectors and refuse to copy currency). They don't point it out specifically, but there are various hints dropped in the FAQ about it.
Please help metamoderate.