Embedded Files
Objective:
Objective:
I have always loved doing puzzles. One day, while working on a tricky puzzle, I became extremely frustrated by the large number of very similar colored sky pieces. At this moment, I started thinking about attempting to make an algorithm that harnessed image processing to solve the puzzle based on the shape of the pieces.
Brainstorming process:
Brainstorming process:
I was inspired by one of my favorite Youtubers “Stuff Made Here”, who made their own version of a puzzle solver that solved a 5000-piece blank puzzle. I determined that first, I would need to consistently determine the shape of each puzzle piece, then I would compare the edges to each other and identify pieces that fit together. Ultimately, I would reconstruct the puzzle in increasingly larger chunks.
The Algorithm:
The Algorithm:
Recognizing the puzzle piece + Image Clean up:
Recognizing the puzzle piece + Image Clean up:
Original Image.
2. Grey Scale.
3. If pixel is greater than threshold.
4. Eroding pixels from edges to eliminate noise.
5. Dilating remaining pixels to restore original geometry.
6. Bitwise function of Dilation and Threshold + Elliptical Kernel Morph to eliminate roughness.
Identifying the piece edge and splitting up edges
Identifying the piece edge and splitting up edges
Edge Canny of white pixels bordering black pixels.
Visualization of distance of edge from the center of the piece. Uniform sharp peaks are the corners.
Highs and lows are detected, and most uniform peaks are determined to be corners. Edge is split up into 4 edges.
Aligning and identifying matching pieces:
Aligning and identifying matching pieces:
Edges are aligned and positions converted to x, y array.
The optimized comparison algorithm determines a match score. Example of a bad match (high difference score).
Example of a good match (low difference score).
Final Solving algorithm:
Final Solving algorithm:
The final solution is generated by using a recursive algorithm. Using the edge matching data from the previous step, all possible matching 2×2 squares are generated. These 2×2 squares are then treated as bigger pieces and are fed back into the algorithm, generating 4×4, 8x8… until the puzzle is completely solved. This approach is able to account for false positives for matches since there is not too much uniqueness among lots of pieces.
Example of solved 4x4 chunk
Results:
Results:
The puzzle solver was able to help me solve the sky pieces in the puzzle in record time!
Page updated
Google Sites
Report abuse