Abstract
Automated jigsaw puzzle solving is a classic NP-hard problem with significant applications in archaeology, forensics, and cultural heritage. Traditional solvers rely heavily on pictorial continuity and shape matching, both of which fail when fragments are eroded or faded. This paper introduces a novel framework that models the reassembly process as a non-cooperative multiplayer game. By leveraging Wertheimer’s law of good continuation, we demonstrate that linear geometric patterns can serve as a robust signal for reconstruction, achieving high accuracy in scenarios where state-of-the-art pictorial solvers fail.
Introduction
The reconstruction of fragmented objects—ranging from ancient frescoes to shredded documents—remains a significant challenge in computer vision. Most existing solvers utilize two primary cues: pictorial continuity (matching color and texture at the edges) and shape matching (fitting the interlocking boundaries of pieces). However, in real-world archaeological contexts, physical deterioration often erodes piece boundaries, and environmental factors fade original colors, rendering these traditional cues unreliable.
This research addresses this gap by formalizing a psychological principle known as Wertheimer’s law of good continuation. This principle suggests that humans perceive lines and curves as following the smoothest path. By focusing exclusively on the geometric continuity of lines traversing across pieces, the authors propose a method that remains robust even when the edges and surfaces of the pieces are severely degraded.
Methodology
The authors transform the puzzle-solving task into a non-cooperative multiplayer game, utilizing evolutionary game theory to find a consistent global solution.
1. Game Formulation
In this framework, each puzzle piece is treated as a "player." A player’s "pure strategy" consists of its potential placement—defined by its coordinates $(x, y)$ and its rotation $(\theta)$—on a two-dimensional plane. The objective is to find a configuration where all pieces are placed optimally relative to one another.
2. Payoffs and Linear Assignment
The "payoff" for a piece is determined by how well its internal geometric features align with those of its neighbors. To calculate this compatibility, the authors employ a Linear Assignment Problem (LAP). This allows the system to find the best one-to-one matching between sets of lines on adjacent pieces. The cost is minimized when lines continue smoothly, characterized by similar angles and proximity of endpoints.
3. Replicator Dynamics and Nash Equilibrium
Rather than employing a greedy search, which is prone to local optima, the system seeks a Nash equilibrium—a state in which no piece can improve its fit by changing its position or rotation unilaterally. To reach this equilibrium, the authors use multi-population replicator dynamics. This evolutionary approach iteratively updates the probability distributions of piece placements, favoring strategies with higher relative payoffs until a stable, consistent labeling emerges.
Experimental Evaluation
To test the efficacy of this line-based approach, the authors developed several new datasets designed to isolate geometric signals from pictorial ones.
- Synthetic Lines: Images containing 50 random lines, cut into various shapes (squared, polygonal, and irregular).
- Real-World Vector Maps: Sourced from OpenStreetMaps (Honolulu, Barcelona, and New York), these datasets provide complex, realistic networks of roads and buildings.
- Archaeological Case Study: A set of real fresco fragments with manually annotated patterns to simulate a "wild" reconstruction scenario.
Key Results
The proposed method significantly outperformed traditional state-of-the-art (SOTA) algorithms on line-heavy datasets:
- Synthetic Performance: On synthetic line puzzles with squared pieces, the game-theoretic approach achieved a Direct (D) accuracy of 0.99. In contrast, traditional pictorial solvers (such as Pomeranz et al.) collapsed to an accuracy of 0.014, as they could not find reliable color anchors.
- Complex Geometry: On real-world vector maps with irregular pieces, the method achieved an accuracy of 0.283, more than doubling the performance of specialized archaeological solvers (e.g., Derech et al., which achieved 0.11).
- Qualitative Success: The algorithm successfully solved abstract line puzzles that proved difficult for human subjects to solve at a glance, demonstrating the power of the mathematical optimization of Gestalt principles.
Discussion and Insights
The strength of this approach lies in its shift from local to global consistency. By modeling the puzzle as a polymatrix game, where the total payoff is the sum of pairwise interactions, the authors allow for efficient computation using classical game dynamics. This makes the model immune to the erosion and fading that typically hamper archaeological reconstruction.
However, limitations remain. The discretization of the search space for position and rotation $(x, y, \theta)$ is computationally intensive, leading to a "strategy space" explosion as the number of pieces increases. Furthermore, the algorithm is dependent on the presence of linear features; in "empty" regions of a puzzle (such as a clear sky in a fresco), the geometric signal disappears.
Conclusion
By merging the psychological insights of Wertheimer with the mathematical rigor of Nash, this paper provides a robust new tool for the reassembly of fragmented artifacts. Future work will focus on hybridizing this line-based game theory with traditional color and shape features, creating a comprehensive system capable of handling the diverse challenges of real-world reconstruction.
Summary updated