Zolver is a jigsaw puzzle solver written in python. This end-of-studies project was developed by 4 EPITA students. It solves computer generated and real jigsaw puzzles.
A short video presentation is available at https://www.youtube.com/watch?v=Oq36FtMg0-k
A jigsaw puzzle
This projects was developed on Linux distribution. Windows compatibility is absolutely not guaranteed.
To avoid compatibility issues, we recommend setting up a virtual environment and then using the command :
pip install -r requirements.txt
Use python3 main.py
Use python3 main_no_gui.py {-p} {-g} path/to/image
Options:
-g: enable green background-p: enable profiling
First, we apply a binary threshold to the processed image. The threshold is different if we process a real puzzle or a real one. We then apply some mathematical morphologies to link edges in case some edges have holes. Finally, we apply OpenCV contour detection.
We now need to find four edges of each puzzle piece. To do so, we compute the relative angle between adjacent points and we get local extrema. Once our edges have been splitted, we classify our edges into three categories: frame edges, indent padding edges and outdent padding edges by recognizing patterns with relative angle curves.
We use three different ways to match edges :
- Comparing the edge size to find edges with similar length.
- Using color to match edges. For every pixel on the edge, we take the median color of its neighboring pixels and we then compare the distance to the other edge pixel to pixel.
- Comparing shapes using a Euclidian distance along the edges.
We first solve the puzzle edge because once we have its frame, every puzzle piece can be matched using at least two edges. The more edges we have to check how likely is the piece to match, the less Zolver is likely to make an error. Zolver will always try to fill the empty space with the highest number of edges already filled.
SCIA 2018 - EPITA
- Cyril Cetre
- Denis Castéran
- Jérémy Lugand
- Hugo Rybinski
