Computer Vision Powers Automatic Jigsaw Puzzle Solver

Posted Apr 1, 2019

C++ computer vision image processing Lviv Ivan Franko National University Open CV OpenCV R&D science

Image Processing for Puzzle Solving

Classic jigsaw puzzles, while being a simple hobby and entertaining pastime, are of great educational value for the human brain as they train its pattern recognition abilities, improve coordination and develop spatial awareness. Since in computer science pattern recognition is typically solved by image processing, our R&D engineers decided to develop a computer vision program for the automatic assembly of a jigsaw puzzle. Despite being only a workshop project, our automatic jigsaw puzzle solver has a number of potential applications, among which reassembling of damaged documents and stitching satellite images into maps.

Jigsaw Puzzle Solving with Computer Vision

The developed program assembles a jigsaw puzzle from the image of its pieces laid out on the blue piece of paper as shown in Figure 1.

Note that we don’t use the image of a complete picture for a reference. The proposed method of automatic puzzle solving comprises the next modules:

1. Puzzle Cropper
2. Locks Searcher
3. Puzzle Aligner
4. Puzzle Rotator
5. Puzzle Joiner
6. Colour Descriptor
7. Animation Module

Let’s analyze each module to see how it contributes to the final result.

Module I. Cropping Out Puzzle Pieces

After converting the input image (Figure 2a) from BGR to HSV colour space our computer vision algorithm detects and removes the background colour that allows creating an inverted mask for the puzzles. Next, the algorithm performs a contour search and saves a vector of 54 separate contours as split puzzle pieces (Figure 2b).

Module II. Detecting Puzzles Locks

While the puzzles were split apart and cropped out in the previous module they are still chaotically rotated. In order to align them, our computer vision algorithm needs to locate the interlocking parts of puzzles – inner and outer locks. First, the program calculates the convex closure of the puzzle (blue line in Figure 3) and computes its convexity defects – the deepest points on the contour (red dots in Figure 3). If the distance from the convex hull to the defect is insubstantial, that is smaller than the error margin – epsilon, that point is not considered to be a defect.

Now it is obvious that each inner lock is described by one convexity defect and each outer lock – by two. Thus, the next step of the algorithm is to check whether the contour between the two consecutive defect points resembles a circle. For this purpose, we calculate the circularity rate for each of the contour parts, that is the area of the part divided by its perimeter squared. If this part of the contour resembles a circle, its circularity rate must be close to 0.08:

circularity = S/p² = πr²/(2πr)² = 1/4π ≈ 0.08

If so, that part of the contour is considered an outer lock and the adjacent convexity defect points are discarded.

To detect the outer locks the algorithm makes the next steps:

1. Chooses one of the convexity defect points left after detecting outer locks.
2. Selects the two neighboring convex hull points (blue dots in Figure 3).
3. Checks if the distance between the selected points is a local minimum. If no, adjusts them so they describe the narrowest part of the convexity defect (green dots in Figure 3).
4. Calculates the circularity rate of the contour between adjusted points and decides whether it is an inner lock.

Having pinpointed the inner and outer locks of the puzzles (Figure 4) we proceed with aligning puzzles in the upright position.

Module III. Aligning Puzzles in the Upright Position

In order to find the center of mass of a puzzle piece, the algorithm approximates the piece with a rectangle by filling its inner locks with white color and its outer locks – with black color. Then it calculates the width, height, and rotation angle α of the piece (Figure 5).

This information allows us to determine the transformation matrix for each of the puzzle pieces and align them in an orderly way (Figure 6).

Module IV. Puzzle Rotator

As the puzzles are still rotated randomly we need to consider any possible orientation they may take in the assembled mosaics. So the algorithm rotates and saves 4х7 copies of each puzzle: it rotates each piece by four quadrantal angles and additionally by ±3 degrees for every rotation.

Module V. Puzzle Joiner

Finally, we get down to assembling the puzzle from its preprocessed pieces. The program considers all 54х28 puzzle pieces and deletes the unnecessary copies only after finding the correct orientation of the piece and placing it in the final picture. To achieve this the algorithm makes the next steps:

1. Selects the position candidate for placing the next puzzle piece by choosing the position with maximum sides known. The first position candidate is the upper-left corner of the picture as shown in Figure 7a.
2. Calculates the measure of geometrical fit between the candidate position and all the remaining puzzle pieces:
   1. checks if the locks coincide;
   2. estimates the degree of geometrical fit by calculating the exclusive (XOR) of adjacent areas (Figure 7b);
   3. shifts the candidate puzzle left, right, up, and down by 10 pixels, calculates the geometrical fit for each of the adjustments, and defines the best position of the candidate puzzle.
3. Rates the puzzles according to their fit coefficient and shows the best 8 options to the user (Figure 8) who decides which puzzle to place in the selected position and eliminates the errors of the algorithm if any occur.

However, we can reduce the number of erroneous placements by adding another fit criterion. During this stage, we have taken into account only the geometry of the puzzles. Let’s now consider the colour of puzzle borders too.

Module VI. Colour Descriptor

To match the puzzles according to the colour of their borders the program first extracts the four borders from each puzzle piece. Then averages the colour values of several edge pixels along the perpendicular to the border and saves them in a vector of RGB values that are normalized to the uniform length (Figure 9). These vectors serve as colour descriptors for the puzzle pieces and since they don’t change with the rotation we only need to calculate and save 54х4 vectors.

Now the algorithm can also estimate the colour match while compiling a rating of the best-fit puzzles by calculating the difference between the corresponding values of colour descriptor vectors. However, due to the fact that the vectors were built by traversing the puzzle in a clockwise direction, we need to flip one vector prior to comparison, as shown in Figure 10.

Just like this our computer vision algorithm is able to solve the puzzle under user supervision shown in Figure 8.

Module VII. Animation Module

This last module does not contribute to solving the puzzle but rather creates a visual representation of the achieved result by defining the transformation function.

The transformation function describes the transition of puzzles from their initial position to the final position. For that, we need to save each transformation, applied to the puzzle piece, in a separate transformation matrix m_i. According to our computer vision algorithm, each puzzle piece undergoes seven transformations, hence the resulting transformation matrice m is the product of seven matrices m_i:

m = m₇ * m₆ * m₅ * m₄ * m₃ * m₂ * m₁

These computations produce 54 transformation matrices and allow us to visualize the path of puzzle pieces from their initial positions (Figure 2a) to the places they take in the final picture as shown in the video below.

Summary

Title

Jigsaw Puzzle Solver with Computer Vision

Description

Our R&D engineers developed a CV program for the automatic assembly of a jigsaw puzzle together with the students from our latest CV workshop.