Pictorial and apictorial polygonal jigsaw puzzles: The lazy caterer model, properties, and solvers
This addresses the limitation of existing jigsaw puzzle solvers that focus on square pieces, offering a more realistic model for applications in computer vision and image processing, though it is incremental in extending puzzle types.
The authors tackled the problem of solving jigsaw puzzles with general convex polygon pieces, generated by straight cuts inspired by the Lazy caterer's sequence, and showed that such puzzles are solvable completely automatically through a multi-body spring-mass dynamical system with hierarchical constraints.
Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping unordered visual fragments, is fundamental to numerous applications and yet most of the literature of the last two decades has focused thus far on less realistic puzzles whose pieces are identical squares. Here we formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape/image with an arbitrary number of straight cuts, a generation model inspired by the celebrated Lazy caterer's sequence. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process. We define evaluation metrics and present experimental results on both apictorial and pictorial puzzles to show that they are solvable completely automatically.