Solving Square Jigsaw Puzzle by Hierarchical Loop Constraints.

Area of Science:

• Computer Vision
• Computational Geometry
• Image Processing

Background:

• Solving jigsaw puzzles computationally is challenging, especially without prior information like piece orientation.
• Existing methods often rely heavily on pairwise compatibility, which can be uninformative for small image pieces.
• Reconstructing puzzles from small pixel blocks (e.g., 7x7) presents unique difficulties.

Purpose of the Study:

• To develop a novel computational puzzle solver for square-piece image jigsaw puzzles.
• To address the limitations of existing methods, particularly for small-scale puzzle pieces.
• To propose an algorithm that exploits geometric agreement rather than solely pairwise compatibility.

Main Methods:

• The algorithm identifies hierarchical piece loops by aggregating smaller loops of four pieces in a bottom-up manner.
• It focuses on maximum geometric consensus between pieces, reducing dependency on pairwise measures.
• An improved pairwise compatibility measure utilizing directional derivative information along piece boundaries is introduced.

Main Results:

• The proposed method successfully reconstructs challenging jigsaw puzzles, including those with small pixel blocks.
• The algorithm demonstrates reduced dependency on potentially uninformative pairwise compatibility measures.
• Mathematical analysis and reconstruction experiments validate the effectiveness of the algorithm and its components.

Conclusions:

• The novel approach using hierarchical piece loops offers a robust solution for computational jigsaw puzzle solving.
• Geometric consensus is a more effective strategy than pairwise compatibility for small-scale puzzle reconstruction.
• The developed algorithm and improved compatibility measure advance the field of computational image reconstruction.