3 ms·

Jigsolved: Computer Vision to Solve Jigsaw Puzzles

49 points by benryon 8y ago

petters 8y ago
Does not really solve puzzles. Just locates a single piece with sift.
- kjeetgill 8y ago
  I agree it's hardly a complete solution but it's like 70% of it, right? Especially if the goal was just to build a human aide. That said, it's going to fail hard if your puzzle is a magic eye puzzle.
  - floatrock 8y ago
    If the last 10% takes 90% of the time, well, this is only 70%.
  - lozenge 8y ago
    Do most people keep the solution visible while solving a jigsaw?
kjeetgill 8y ago
That has always been one of those pet projects I keep meaning to take another crack at. Once a year or so I spend a weekend toying around with opencv in python and see what I can do. Unlike the parent post I've always wanted to solve it geometrically, not visually. Think solving a puzzle from the backs of the pieces.
- mv4 8y ago
  I suspect that'd be much much harder - there's not that much variation between the shapes.
  - Tobani 8y ago
    And some puzzles (excluding borders might actually have their pieces cut identically.
- supermdguy 8y ago
  I actually did this once, with a 100 piece puzzle. It took about an hour. There were several pairs of pieces that looked like they fit, and even felt almost right, but weren't correct. It might be possible with computer vision, as long as you set the right tolerance of how tightly the pieces should fit together.
  - deleted 8y ago
    [deleted]
LyndsySimon 8y ago
Does this remind anyone else of Snow Crash? :)
tobinfricke 8y ago
Can it solve this? https://en.wikipedia.org/wiki/Eternity_II_puzzle https://en.wikipedia.org/wiki/Eternity_II_puzzle
- talltimtom 8y ago
  If you have a picture of the solution it can tell you how to put the pieces yes.
Someone 8y ago
This is a field of active research, with wildly varying approaches. For example, https://www.researchgate.net/publication/225796422_Solving_jigsaw_puzzles_by_computer https://www.researchgate.net/publication/225796422_Solving_j... uses puzzle shapes only, and http://webee.technion.ac.il/~ayellet/Ps/15-PT.pdf http://webee.technion.ac.il/~ayellet/Ps/15-PT.pdf works with square pieces. (both randomly picked from a google search; I don’t know what the state of the art is, and am still looking for the smartphone app that does this)
anfractuosity 8y ago
http://archive.darpa.mil/shredderchallenge/ http://archive.darpa.mil/shredderchallenge/ was pretty cool, in a related note.

49 points by benryon 8y ago

petters 8y ago

Does not really solve puzzles. Just locates a single piece with sift.

kjeetgill 8y ago
I agree it's hardly a complete solution but it's like 70% of it, right? Especially if the goal was just to build a human aide. That said, it's going to fail hard if your puzzle is a magic eye puzzle.
- floatrock 8y ago
  If the last 10% takes 90% of the time, well, this is only 70%.
- lozenge 8y ago
  Do most people keep the solution visible while solving a jigsaw?

kjeetgill 8y ago

That has always been one of those pet projects I keep meaning to take another crack at. Once a year or so I spend a weekend toying around with opencv in python and see what I can do. Unlike the parent post I've always wanted to solve it geometrically, not visually. Think solving a puzzle from the backs of the pieces.

mv4 8y ago
I suspect that'd be much much harder - there's not that much variation between the shapes.
- Tobani 8y ago
  And some puzzles (excluding borders might actually have their pieces cut identically.
supermdguy 8y ago
I actually did this once, with a 100 piece puzzle. It took about an hour. There were several pairs of pieces that looked like they fit, and even felt almost right, but weren't correct. It might be possible with computer vision, as long as you set the right tolerance of how tightly the pieces should fit together.
- deleted 8y ago
  [deleted]

LyndsySimon 8y ago

Does this remind anyone else of Snow Crash? :)

tobinfricke 8y ago

Can it solve this? https://en.wikipedia.org/wiki/Eternity_II_puzzle https://en.wikipedia.org/wiki/Eternity_II_puzzle

talltimtom 8y ago
If you have a picture of the solution it can tell you how to put the pieces yes.

Someone 8y ago

This is a field of active research, with wildly varying approaches. For example, https://www.researchgate.net/publication/225796422_Solving_jigsaw_puzzles_by_computer https://www.researchgate.net/publication/225796422_Solving_j... uses puzzle shapes only, and http://webee.technion.ac.il/~ayellet/Ps/15-PT.pdf http://webee.technion.ac.il/~ayellet/Ps/15-PT.pdf works with square pieces. (both randomly picked from a google search; I don’t know what the state of the art is, and am still looking for the smartphone app that does this)

anfractuosity 8y ago

http://archive.darpa.mil/shredderchallenge/ http://archive.darpa.mil/shredderchallenge/ was pretty cool, in a related note.