Jigsaw Puzzle Solving as a Consistent Labeling Problem

Abstract

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. The problem amounts to maximizing a well-known quadratic function over a probability space which we solve using standard relaxation labeling algorithms endowed with matrix balancing mechanisms to enforce one-to-one correspondence constraints. Preliminary experimental results on publicly available datasets demonstrate the feasibility of the proposed approach.