Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Software Toys Science

Webcam Jigsaw Solver in 200 Lines of Python 199

Posted by timothy from the not-lines-of-coke dept.
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."
This discussion has been archived. No new comments can be posted.

Webcam Jigsaw Solver in 200 Lines of Python More

Webcam Jigsaw Solver in 200 Lines of Python

Comments Filter:

  • First (Score:5, Funny)

    by Anonymous Coward on Tuesday March 01, 2005 @07:42PM (#11818858)
    Oh, but I bet it uses a bunch of libraries post.

  • sgiws? (Score:5, Funny)

    by MaineCoon ( 12585 ) on Tuesday March 01, 2005 @07:43PM (#11818864) Homepage
    and the display
    sgiws exactly where in
    English, please?

  • its (Score:1, Insightful)

    by mr_tommy ( 619972 ) *
    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.

    • Re:its (Score:3, Insightful)

      by gfody ( 514448 )
      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.
    • Here's the source code to my awesome new FPS...

      #include "game.h"

      int do_game()
      {
      int dead=0;

      init_gamestate();

      while (!dead) {
      check_player_input();
      do_npc_update();
      update_screen();
      update_sounds();
      dead = is_player_dead();
      }
      }

      int main()
      {
      int done=0;

      init_stuff();
      main_menu(); // main_menu calls do_game()
      }

      Looks pretty good right? I just have to fill in a few unimplemented functions.

    • Re:its (Score:2)

      by m50d ( 797211 )
      The lesson is to code in Python :)

  • Other applications? (Score:3, Interesting)

    by RM6f9 ( 825298 ) <rwmurker@yahoo.com> on Tuesday March 01, 2005 @07:44PM (#11818879) Homepage Journal
    Facial recognition? Or, was this a by-product of same?

    • Not really, sadly. (Score:5, Informative)

      by Yobgod Ababua ( 68687 ) on Tuesday March 01, 2005 @08:00PM (#11819034)
      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.
    • Reconstruction of Mafia victims.

  • Needs DataGlyphs (Score:5, Informative)

    by commonchaos ( 309500 ) on Tuesday March 01, 2005 @07:45PM (#11818892) Homepage Journal
    This code will only work if the puzzle pieces are printed using DataGlyphs [parc.com]


    A Glyphsaw Puzzle starts out as a computer graphics file generated by the PARC DataGlyph Toolkit. The image is sent to a professional jigsaw puzzle manufacturing company, which creates cardboard puzzle pieces. From a distance, the pieces look similar to those from any other jigsaw puzzle. Up close, one can see individual glyphmarks.
    • Still, it's built with a surprising degree of intelligence - able to deal with motion and throw away uncertain glyphs.
      That's pretty damn impressive.
    • It's an advert for DataGlyphs, showing how:

      "PARC DataGlyphs are a robust and unobtrusive method of embedding computer-readable data on surfaces such as paper, labels, plastic, glass, or metal.

      Basic DataGlyphs are a pattern of forward and backward slashes representing ones and zeroes. This pattern forms an evenly textured field.

      Unlike most barcodes, DataGlyphs are flexible in shape and size. Their structure and robust error correction also make them suitable for curved surfaces and other situations where

    • closed source, proprietary, and astroturf (Score:5, Interesting)

      by SuperBanana ( 662181 ) on Wednesday March 02, 2005 @02:31AM (#11821314)

      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.

      • >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.

        Except I don't work for PARC. I do work for Xerox, and Xerox is the sole stockholder in PARC, though PARC is a separate company with its own business deals. I happen to have the privilege of wandering around and finding neat stuff (under non-disclosure)

  • Somone should sgiw them (Score:5, Funny)

    by amling ( 732942 ) <keith...amling@@@gmail...com> on Tuesday March 01, 2005 @07:47PM (#11818913)
    exactly where the 'h' and 'o' keys are.

  • Wrong section? (Score:5, Insightful)

    by NemesisStar ( 619232 ) on Tuesday March 01, 2005 @07:48PM (#11818920)
    Shouldn't this news be under programming instead of software? The image for programming is a jigsaw getting solved!

  • Since it can use anything it wants (Score:3, Funny)

    by Neil Blender ( 555885 ) <neilblender@gmail.com> on Tuesday March 01, 2005 @07:48PM (#11818922)
    Here's a one line puzzle solver

    [user@localhost] perl -e '`python glyphsaw`'
    • [user@localhost] perl -e '`python glyphsaw`'
      Bah! That must be a fake! Real Perl should be unspeakable and unreadable!
    • Since it can use anything it wants...

      I don't know about you, but when I code, I *never* use any useful libraries. Programming should never be about getting something done- rather, it should be about reinventing the all the wheels, gears, axels and windshield wipers that I could ever need... In other words, re-writing the OS for each and every app! WOOT! 152 thumbs up!
  • Yes, very nice.

    But the important question is, can it assemble the puzzle faster than Gary Kasparov?

    • Re:More importantly... (Score:3, Funny)

      by Anonymous Coward
      > can it assemble the puzzle faster than Gary Kasparov?
      No, Gary Kasparov takes a much longer time to assemble.

  • 200 lines? (Score:5, Insightful)

    by PoopJuggler ( 688445 ) on Tuesday March 01, 2005 @07:49PM (#11818930)
    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...
    • I thought this too, especially after looking at the page, seeing the libraries and components it uses to do this. 200 lines seems almost too much, but I suppose it's python, which can be a bit verbose, though nothing like languages outside of it's language class- c, c++, java, and others would prolly be more... But about all those 200 lines of python are doing:

      1. initialize DataGlyph, webcam.
      2. Get Webcam image. Hand off image of puzzle piece to DataGlyph library.
      3. DataGlyph library returns code. DataG

      • Re:200 lines? (Score:4, Insightful)

        by thedustbustr ( 848311 ) on Wednesday March 02, 2005 @12:48AM (#11820948)

        > 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.

      • >200 lines seems almost too much [blah, blah, blah]

        While not explicitly mentioned in the writeup, I also programmed the computer to beep when a piece was successfully processed. That added a line right there.

    • Bullshit. Let's see your code.

      You seem to have missed the whole point of this accomplishment.

  • slow already (Score:3, Informative)

    by Zenophran ( 139656 ) on Tuesday March 01, 2005 @07:49PM (#11818939)
    Mirrordot to the rescue http://mirrordot.org/stories/df4be4026318903e35238 c9e48d22bff/index.html [mirrordot.org]

  • Jiglyph (Score:5, Interesting)

    by Doc Ruby ( 173196 ) on Tuesday March 01, 2005 @07:50PM (#11818943) Homepage Journal
    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".

  • External libraries (Score:3, Insightful)

    by R.Mo_Robert ( 737913 ) on Tuesday March 01, 2005 @07:51PM (#11818947)

    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 (Score:5, Insightful)

    by bodrell ( 665409 ) on Tuesday March 01, 2005 @07:56PM (#11818996) Journal
    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.

    • 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.

      You are so correct, my man. What is the point of a library if you didn't write it yourself? Why, it would be utterly useless!

      I could just write a one-liner that calls this program, by that rationale.

      Well it's not the same, because you'd just be doing what someone has already done, now wouldn't you? This guy did something original, and he did with economy.
      • You are so correct, my man. What is the point of a library if you didn't write it yourself? Why, it would be utterly useless!

        First, you ought to know that sarcasm does not work well in ASCII.

        Second, who the fuck said libraries weren't useful? Python is great for many reasons (my favorite is that code can look like pseudocode if you don't use lambdas all over the place), and one reason is the great libraries available. I threw together a working curve-fitting program with NumPy [scipy.org], Numarray, and the bui

        • I'm just saying I'd be way more impressed if someone did the same thing in 200 lines of assembly.

          That would be trivial given the right processor and instruction set.
          • I'm just saying I'd be way more impressed if someone did the same thing in 200 lines of assembly.

            That would be trivial given the right processor and instruction set.
            And if we could each have our own chip fab, so we could create custom processors at whim, you would have a point.
        • Can I really take credit for all their work, and call it my own?

          Maybe talking about the small size of the application was meant as a complement to the supporting software libraries, rather than an attempt at "taking credit"

          • Maybe talking about the small size of the application was meant as a complement to the supporting software libraries, rather than an attempt at "taking credit"

            That would seem to be supported by the note at the bottom:

            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 don't doubt that he did make very good use of the libraries, but that doesn't detract from th

  • Puzzle (Score:5, Insightful)

    by Anonymous Coward on Tuesday March 01, 2005 @07:57PM (#11819004)
    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.
    • Pesky smallprint.

      Could also use this technology for foolproof facial recogtion. Just need to have barcodes stamped on your face!

    • You mean like this? (Score:4, Informative)

      by jab ( 9153 ) on Tuesday March 01, 2005 @11:54PM (#11820713) Homepage
      PARC (and others) have already tackled that problem. Here's my favorite research paper [xerox.com] 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.

    • This glyph thing is all very nice and all, but it CHEATS

      Indeed, and why use glyphs at all? As jigsaws are basically grids it'd be far simpler just to print the row,column coordinates on each piece - and it'd take even fewer lines of code to do the recognition, this ain't solving a jigsaw at all.

    • Re:Puzzle (Score:3, Informative)

      by m50d ( 797211 )
      The challenge is being able to be read the adress by using an ordinary webcam, with no need to carefully line up the piece. No, it's not as good as solving an arbitrary puzzle, but it's still pretty good.

  • Wow !!! (Score:2, Funny)

    by kabz ( 770151 )
    Finally ... something on Slashdot to interest my grandmother !!

  • A REAL puzzle (Score:3, Funny)

    by sburnett ( 540700 ) on Tuesday March 01, 2005 @08:01PM (#11819053)
    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 :-)

  • Coral link to this (Score:2, Informative)

    by Announcer ( 816755 )
    For when the server melts down, here it is...

    http://www2.parc.com.nyud.net:8090/istl/members/jb reiden/glyphsaw/ [nyud.net]

    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.

  • Didn't they just... (Score:2, Informative)

    by Chuckstar ( 799005 )
    ...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.

  • This isn't as clever as you think (Score:5, Insightful)

    by Anonymous Coward on Tuesday March 01, 2005 @08:16PM (#11819158)
    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.
  • Yeah, 200 lines of code using a few libraries compiled from 50000 lines of code.

  • Lame! (Score:5, Insightful)

    by CyberVenom ( 697959 ) on Tuesday March 01, 2005 @08:42PM (#11819348)
    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 (Score:4, Insightful)

    by Anonymous Coward on Tuesday March 01, 2005 @08:49PM (#11819425)
    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 uses Reed-Solomon coding for error correction (Score:3, Interesting)

    by hqm ( 49964 ) on Tuesday March 01, 2005 @09:01PM (#11819539)
    I made a C library of the Reed-Solomon error correction routines and published it as the rscode library on Sourceforge at http://rscode.sourceforge.net/ [sourceforge.net]

    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.

    • 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 [parc.com].

  • This defeats the entire purpose of doing jigsaws. (Score:3, Insightful)

    by i41Overlord ( 829913 ) on Tuesday March 01, 2005 @09:09PM (#11819594)
    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.

  • so what? (Score:2, Insightful)

    by 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.
  • A really interesting mental exercise with potential real world applications: The poster misrepresents it, the 'editors' don't edit it, and hundreds of uninformed people make comments which miss the whole point of the exercise.

    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.

  • 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 migh
  • 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.

  • Jigsaw robot is
    Genius solver of puzzles
    Only with barcodes

Slashdot Top Deals

Keep up the good work! But please don't ask me to help.

Close