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
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.
Facial recognition? Or, was this a by-product of same?
Take the 90-Day Challenge! http://rwmurker.bodybyvi.com/
However much money these people received in order to research this ...
I want it doubled. I'm going to research the effects on time consumption of playing online FPS games.
But that's like an automated crossword puzzle solver or maybe god mode. Where's the fun?
Wow 200 lines? I bet it has tons of includes though. If image recognition is this good in 200 lines of python how have those anit-spam boxes that make you copy an obscure string to prove you're human not been broken yet. Or maybe they just have?
- Cary
--Fairfax Underground: Where Fairfax County comes out to play
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
My Mom used to subscribe to some pretty kooky Religious Right publications (unfortunately, she quite possibly still does). I remember one of them was heavily pushing a Net-Nanny type program, and the advertisement claimed it could actually analyze the images and selectively block out sites where the images contained naughty bits but didn't have textual cues for other, competing pieces of software to pick up on. Of course, now that such things might actually be possible, they'll just block all the sites that have pictures of balloons. ;)
Save the galaxy!
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 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?
I wrote one in one line of code! It uses the PuzzleSolver8 library, I must mention :-)
Table-ized A.I.
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...
Could also use this technology for foolproof facial recogtion. Just need to have barcodes stamped on your face!
Engineering is the art of compromise.
...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.
ruggt gabd us ibe soace iver
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.
... that this page was indeed assembled by a herd of dyspeptic zebras or whatever. Are the editors so stupified by their jobs that glaring typos roll right past them now?
Yeah, 200 lines of code using a few libraries compiled from 50000 lines of code.
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 can't take any more Bill Cophbies.
The ______ Agenda
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 thought the whole point of jigsaws was to kill time without your brain sleeping on you. Or just have fun with family. What's next? Have a robot do your fishing while you and your father stay home?
Pointless in my opinion. And not technologically innovative either like some people have already said.
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.
Messagelabs has a product that will detect pornography in images. It works incredibly well. We've been using it to block emailed pornography here for a number of years.
Recall the stories about how printers where marking reproductions of bills- well this is how it's done.
Fairly neat.
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
It's certainly no 15 line p2p app!
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.
If a webcam and python had parts in this movie instead of the really bad actors they hired, it might have been a better movie.
http://www.rayn.net . Funny. Stuff.
then having that work done automatically is self-defeating.
Ask Jeff Breidenbach how self-defeated he feels
It would be worth it even at 1000 lines of code.
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.
Error correction codes are an important facet of DataGlyphs when one is trying to store a message. However, in this case there isn't any message stored - every glyphmark is devoted to purely positional information. This is called an address carpet, which is described in more detail in this
IEEE article.
neato.
My other first post is car post.
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.
Seriously the summary didn't fit the article at all.
So Jeff, please don't listen to these fools.
FOOLS... I know this is Slashdot... but go RTFA, and ignore the 200 line thing, it's a red herring.
Nothing in the world is more dangerous than sincere ignorance and conscientious stupidity.
funniest thing I've read all day.
spam();
spam();
spam();
egg();
spam();
spa
This is a harder problem than many people here seem to think. PARC have been working on this stuff for a long time to get it this robust.
Shame it's still a solution looking for a problem...
rt
Can someone who knows Numerical Python clue in those of us not familiar? Is this akin to Perl's PDL? Just curious. It's the first time I've come across the term.
In Perl, PDL is a wonderful tool, but it relies on some of those ancient fortran libraries that everyone (in the scientific community, anyway) has been dragging around since the dawn of time, and getting it to compile and install can be a bear.
If Numerical Python does essentially the same thing, and is slightly easier to get up and running, I might toy around with it.
From the title I thought this was actually going to solve the puzzle, not just do a lookup in a database. I was expecting something like a primitive version of the software Hiro used to reconstruct the tablet in Snow Crash.
I don't see anything that actually solves the puzzle. I don't see anything that is even close to 200 lines of code. What's up with that? When you have to severly exagerate your claims to get people to look, then perhaps it wasn't worth looking to begin with. You can only sucker people so long before they absolutely stop believing you. Perhaps people at Slashdot are a bit more gullible than most? Nah, I don't believe it.
What I want is a program that can scan in the picture on the box of the puzzle, along with some selected pieces, and then print out the piece that fell under the couch and was zapped into an alternate universe, never to be seen again. I think there would be some commercial potential for a "puzzle repair kit".
I find taking a jigsaw to stacks of old program code much more satisfying. I can make really cool paper dolls!
If the computer had access to the full image, the code I was using could probably be modified to indicate where any give piece went. It handled translation and rotation so in theory, you could supply the piece to the scanner/web can at in any position.
Used a hell of a lot more than 200 lines of code though and it wasn't pretty!
This way to the egress...
It's interesting and could be useful but I'm not sure how many people would actually use it. This is probably generalizing but anyone that has enough technical expertise to get a webcam and set it up, then set up this jigsaw solver might be a bit bored with solving jigsaw puzzles in the first place.
Just keep in mind that linecount is not a measure of program awesomeness or programmer leetness: it is a measure of effort, and not a great one at that (in one particular project I've worked on, I've started mostly from scratch twice, and I've probably written 3 times as many lines of code that are actually part of the current branch. Of course, I'm not a professional coder; I code for personal pleasure... if a professional wrote significantly more lines than made it into the project, he is wasting company resources...
This sig is false.
Jigsaw robot is
Genius solver of puzzles
Only with barcodes