טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentPaikin Genady
SubjectSolving Multiple Square Jigsaw Puzzles with Missing
Pieces
DepartmentDepartment of Electrical Engineering
Supervisor Professor Ayellet Tal
Full Thesis textFull thesis text - English Version


Abstract

Jigsaw-puzzle solving is necessary in many applications, including biology, archaeology, and every-day life. In this paper we consider the square jigsaw puzzle problem, where the goal is to reconstruct the image from a set of non-overlapping, unordered, square puzzle parts.

Our key contribution is a fast, fully-automatic, and general solver, which assumes no prior knowledge about the original image. It is general in the sense that it can handle puzzles of unknown size, with pieces of unknown orientation, and even puzzles with missing pieces.

Moreover, it can handle all the above, given pieces from multiple puzzles.

Our approach is based on four key ideas.

First it is greedy.

Second, it places pieces based on the compatibility between them, taking advantage both of the similarity between the pieces, and of the reliability of this similarity. Third, since greedy solvers are extremely vulnerable to the initial placement, we take special care when choosing the first piece.

Finally, rather than choosing the best piece for a specific location, we select the piece that minimizes the likelihood of erring, regardless of its location.

Through an extensive evaluation we show that our approach outperforms state-of-the-art methods on commonly-used datasets.

This is done while accelerating the running times by a factor of 60-120.