Popularity
4.2
Growing
Activity
3.7
-
738
17
110

Description

Genetic Algorithm based solver for large jigsaw puzzles with piece size auto-detection.

Programming language: Python
License: MIT License

gaps alternatives and similar packages

Based on the "Computer Vision" category.
Alternatively, view gaps alternatives based on common mentions on social networks and blogs.

Do you think we are missing an alternative of gaps or a related project?

Add another 'Computer Vision' Package

README

Genetic Algorithm based solver for jigsaw puzzles with piece size auto-detection.

Build Status

Installation

Clone repo:

$ git clone https://github.com/nemanja-m/gaps.git
$ cd gaps

Install requirements:

$ pip install -r requirements.txt
$ sudo apt-get install python-tk

Install project in editable mode:

$ pip install -e .

Creating puzzles from images

To create puzzle from image use create_puzzle script.

i.e.

$ create_puzzle images/pillars.jpg --size=48 --destination=puzzle.jpg

[SUCCESS] Puzzle created with 420 pieces

will create puzzle with 420 pieces from images/pillars.jpg where each piece is 48x48 pixels.

           

Run create_puzzle --help for detailed help.

NOTE Created puzzle dimensions may be smaller then original image depending on given puzzle piece size. Maximum possible rectangle is cropped from original image.

Solving puzzles

In order to solve puzzles, use gaps script.

i.e.

$ gaps --image=puzzle.jpg --generations=20 --population=600

This will start genetic algorithm with initial population of 600 and 20 generations.

Following options are provided:

Option Description
--image Path to puzzle
--size Puzzle piece size in pixels
--generations Number of generations for genetic algorithm
--population Number of individuals in population
--verbose Show best solution after each generation
--save Save puzzle solution as image

Run gaps --help for detailed help.

Size detection

If you don't explicitly provide --size argument to gaps, piece size will be detected automatically.

However, you can always provide gaps with --size argument explicitly:

$ gaps --image=puzzle.jpg --generations=20 --population=600 --size=48

NOTE Size detection feature works for the most images but there are some edge cases where size detection fails and detects incorrect piece size. In that case you can explicitly set piece size.

Termination condition

The termination condition of a Genetic Algorithm is important in determining when a GA run will end. It has been observed that initially, the GA progresses very fast with better solutions coming in every few iterations, but this tends to saturate in the later stages where the improvements are very small.

gaps will terminate:

  • when there has been no improvement in the population for X iterations, or
  • when it reachs an absolute number of generations

References

BibTeX entry:

@article{Sholomon2016,
  doi = {10.1007/s10710-015-9258-0},
  url = {https://doi.org/10.1007/s10710-015-9258-0},
  year = {2016},
  month = feb,
  publisher = {Springer Science and Business Media {LLC}},
  volume = {17},
  number = {3},
  pages = {291--313},
  author = {Dror Sholomon and Omid E. David and Nathan S. Netanyahu},
  title = {An automatic solver for very large jigsaw puzzles using genetic algorithms},
  journal = {Genetic Programming and Evolvable Machines}
}

License

This project as available as open source under the terms of the MIT License


*Note that all licence references and agreements mentioned in the gaps README section above are relevant to that project's source code only.