Jigsaw Puzzle Solving Algorithm

Overview of the project

I implemented an algorithm that automatically solves jigsaw puzzles based on the shape of their pieces.

Introduction

It all started when I got a puzzle with 2000 pieces for Christmas a few years ago:

Initially I was very pleased with the new challenge - but after a while it became relatively boring and a little exhausting. Therefore, I decided to leave the puzzle the way it was and to one day continue puzzling. As the weeks passed, I slowly forgot about the puzzle as I put it directly under my bed. It all changed in 2020, when I suddenly had a lot of free time. I decided to finally finish the puzzle - but this time by using code.

You'll find the implementation and documentation of my code below and the full version on GitHub

The Idea

Originally, I tried some mashine learning based algorithms. Although I had some success, I wanted a simpler and somewhat more efficient solution for my problem. Instead of looking for patterns in the image itself shown by the puzzle, I wanted to create an algorithm that could find the matching pieces only based on the shape of the pieces.

The overarching goal was to create a brute force algorithm for the jigsaw puzzle. Hence, I needed to find solutions for the following problems:

• Scanning the Images
• Detecting the Edges
• Matching the puzzle pieces

I will cover each step in detail in the following paragraphs. For development, I used Python. You can find the code in a Jupyter Notebook (.ipynb) on Github.

1. Scanning the Images

First, I started to import some useful tools:

from __future__ import print_function
import cv2
import matplotlib.pyplot as plt
import numpy as np
import argparse
import math
import collections

I started off by scanning some images to start developing my algorithm:

# Scanning two sample Images

path_og = r' - enter path here -'
path_match = r' - enter path here -'

images_count = 2

img = cv2.imread(path_og)
img_match = cv2.imread(path_match)

For example, one of the images I scanned looked like this:

I defined some useful functions to reduce the data generated by the image by reducing it to a black / white scheme:

def thresholder(image):
    gray   = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    gray   = cv2.medianBlur(gray, ksize=5)
    thresh = cv2.threshold(gray, 190, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C)[1]
    thresh = cv2.blur(thresh, ksize=(3, 3))
    return thresh

def tresher(img):
    thresh = thresholder(img)
    return thresh

thresh_original = tresher(img)
thresh_match = tresher(img_match)

plt.imshow(thresh_match,"binary_r")

After reducing the threshold of the images, it now looked like this:

2. Detecting the Edges

For detecting the edges, I implemented an algorithm called Canny Edge Detection Algorithm. By using this algorithm, I was able to detect the edges of the puzzles pieces. Those could then later be used for matching the individual pieces.

First, i calculated the potential corners of the puzzle pieces using the Shi-Tomasi Corner Detection Algorithm

def executeFeatureToTrack(thresh):
    # Shi-Tomasi corner detection function
    corners = cv2.goodFeaturesToTrack(thresh, 40, 0.0001, 0.8)
    corners = np.int0(corners)

    return corners

After detecting the edges, all potential candidates for the edges of the puzzle piece are then filtered as currently not only the correct edges are found:

After filtering the edges based on the a formula depending on the inner degrees of the square (should all be relatively equal to 90°) and the total surface area, we now found the correct edges:

Now, we can actually begin detecting the edges of the pieces. As mentioned above, we use the Canny Edge Detection Algorithm:

# import the necessary packages
import argparse
import glob

def auto_canny(image, sigma=0.33):
    # compute the median of the single channel pixel intensities
    v = np.median(image)
    # apply automatic Canny edge detection using the computed median
    lower = int(max(0, (1.0 - sigma) * v))
    upper = int(min(255, (1.0 + sigma) * v))
    edged = cv2.Canny(image, lower, upper)
    # return the edged image
    return edged

After executing the algorithm on the mentioned images, we find the following:

Those edges were than separated based on the height of the images we scanned before and then converted to a point cloud:

3. Matching the puzzle pieces

For matching the puzzle pieces, I used an algorithm that for each puzzle pieces evaluates how similar the inverse of the current edge and any other edge look. As this requires looking through each edge individually (as their could potentially always be a better match) this algorithm reaches an ideal runtime of O(n^2).

For instance, a successful match looks like this:

Summary

By using this algorithm, puzzling those puzzle pieces can be realized much more efficient. Since scanning those images and also the computation of the puzzle piece matches takes quite some while for a large number of pieces, its not necessarily faster than solving the jigsaw puzzle on your own. However, it helped me out on some smaller amount of pieces that looked quite similar, as the algorithm depends on the shape of the puzzle piece and not its color.