pip install -r requirements.txt
You can run the project with
python main.py
use the -h option to check the allowed arguments.
Cross-stitch patterns typically utilize a grid with symbols to represent the color at each intersection. These diagrams are utilized in this context to determine the position of each stitch.
We utilize OpenCV to detect the grid that forms the pattern:
From this grid, we extract each symbol, ensuring that there are no repeated images by applying template matching.
The following pattern[1]:
Has 5 different symbols, indicating 5 differente colours, and these are represented by the following symbols:
Once again, we utilize OpenCV template matching to identify the coordinates of each colour. These coordinates will form the path that we follow when cross stitching each colour. To to that, we use a genetic algorithm. To speed things up, on this part we use multiple threads, and each template is a seperate thread.
The blue filled squares are the regions that matched the template.
The blue path is the shortest path found by the genetic algorithm to pass through each points matching the template we used.
Tries to find the most optimized path for cross stitching. Here we ignore the "cross" and treat each stitch as a point, so, depending on the way the cross is carried out, the optimal path may change.
This is a genetic algorithm, so it is not guaranteed that it'll find the best solution.
We use a genetic algorithm to solve a modified version of the traveling salesman problem, so that it is not necessary to go back to the starting point. This is also known as the shortest / minimum length hamiltonian path.
For the parent selection we do the tournament selection.
The crossover is carried out using the Edge Assembly Crossover (EAX) algorithm [2]
The mutation rate was set to 0.01. The mutation works by randomly swapping elements in the permutation of nodes.
The next generation is selected based on their aptitude, combining parents and children, and the n best individuals are chosen.
Big pattern images work better than small ones, and sometimes it has issues with low res images. The template images' size must be as close as possible to the size of the symbols on the actual pattern.
[2] Nagata, Y. (1997). Edge assembly crossover: A high-power genetic algorithm fot the traveling salesman problem. In Proceedings of the 7th International Conference on Genetic Algorithms, 1997.)