Jigsaw Puzzle Solving as a Consistent Labeling Problem

Abstract

The thesis aims to develop a methodology for solving complex puzzle problems. In the first part of the research, we explore the idea of abstracting the jigsaw puzzle problem as a consistent labeling problem, a classical concept introduced in the 1980s by Hummel and Zucker for which a solid theory and powerful algorithms are available. A formal theory of consistency developed by Hummel and Zucker turned out to have intimate connections with non-cooperative game theory. The theory generalizes classical (boolean) constraint satisfaction problems to scenarios involving ``soft'' compatibility measures and probabilistic (as opposed to ``hard'') label assignments. The problem amounts to maximizing a well-known quadratic function over a probability space which we solve using relaxation labeling algorithms endowed with matrix balancing mechanisms to enforce one-to-one correspondence constraints. The second part addresses the problem of puzzles with eroded borders, a special challenging case of puzzle-solving. Solving puzzles with eroded borders is a common situation when dealing with the re-assembly of archaeological artifacts or ruined frescoes. In this particular condition, the puzzle's pieces do not align perfectly due to the erosion gaps; a direct matching of the patches is consequently unfeasible due to the lack of color and line continuations. To tackle this issue, we propose JiGAN, a GAN-based method for solving puzzles with ruined borders. The experiments on commonly used benchmark datasets demonstrate that our approach is able to address the problem of eroded borders and produce plausible reconstruction results.