Department of Computer Science and Electrical Engineering

Jigsaw Puzzle Solver using Computer Vision

Wendy Cuvet

Abstract:
This paper documents a proposed solution to the problem of solving a jigsaw puzzle using images of the pieces and a computer. Before actually specifying the design used, this paper reviews related research and theory on this topic. The specific problem is how to obtain the individual pieces and match them together to achieve the correct puzzle picture.

Several distinctive steps were found when trying to match jigsaw puzzle pieces together.
These are: Acquiring the image of a piece from a digital source,

Establishing what is useless background information and what is actually the puzzle piece in the image,

Extracting the boundary points around the edge of the puzzle piece,

Identifying straight edges in the boundary so these can be ignored when the matching occurs,

Finding the internal angle around each boundary points,

Comparing the edges and colours of each boundary point to help match the pieces together.

The resolution of the images being used are 96 DPI in 24-bit colour. All the algorithms were implemented using Borland C++. Finally, conclusions are made as to the validity of such a process as it relates to jigsaw puzzle solving as well as other practical fields such as manufacturing and character recognition.

Complete thesis:
Thesis.pdf

Additional material:
code

Dept of Computer Science and ElectricalEngineering / Wendy Cuvet/ cuvet@pc.elec.uq.edu.au last mod 03/09/98