/ai-for-cross-stitching

This project aims to find the shortest path for cross stitching for each colour in a patten.

Primary LanguagePythonMIT LicenseMIT

AI for Cross Stitching

Requirements

pip install -r requirements.txt

Usage

You can run the project with

python main.py

use the -h option to check the allowed arguments.

Pattern Matching

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.

Finding template images

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.

Example

The following pattern[1]:

Has 5 different symbols, indicating 5 differente colours, and these are represented by the following symbols:

template1 template2 template3 template4 template5

Finding colour of each stitch

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.

Example:

The blue filled squares are the regions that matched the template1 template.

The blue path is the shortest path found by the genetic algorithm to pass through each points matching the template we used.

Path finding

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.

Genetic Algorithm

Parent Selection

For the parent selection we do the tournament selection.

Crossover

The crossover is carried out using the Edge Assembly Crossover (EAX) algorithm [2]

Mutation

The mutation rate was set to 0.01. The mutation works by randomly swapping elements in the permutation of nodes.

Next Generation Selection

The next generation is selected based on their aptitude, combining parents and children, and the n best individuals are chosen.

Observations

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.

References

[1] DMC - ROCKET SHIP 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.)