Solving Jigsaw Puzzles in the Wild: Human-Guided Reconstruction of Cultural Heritage Fragments

AI summary

Overview

Research area: Computer vision and cultural heritage computing, specifically jigsaw puzzle solving (fragment reassembly) combined with human-in-the-loop interactive optimization.

Technical level: Intermediate. The paper assumes some familiarity with game-theoretic solvers, relaxation labeling and replicator dynamics, but the human-interaction contribution is conceptually accessible.

Scope: The paper proposes a hybrid human-in-the-loop framework that combines a relaxation-labeling game-theoretic solver with interactive human guidance, and evaluates it against fully automatic and fully manual reconstruction on three groups from the RePAIR archaeological fresco benchmark.

What This Paper Is About

Reassembling real archaeological artifacts from broken pieces is far harder than solving a normal jigsaw puzzle: fragments are eroded, irregular, sometimes have large missing regions, and can arrive in the thousands, as in the RePAIR benchmark, which aims to document over 10,000 fragments from mixed ceiling frescoes. Fully automatic solvers built for clean, synthetic puzzles tend to stall or settle into unstable, locally optimal configurations under these conditions.

The goal of this work is to keep the automatic solver in the loop but let a human steer it — by locking placements that are verified as correct, correcting mistakes, and thereby reshaping the optimization landscape so the solver converges toward globally coherent assemblies.

Key Contributions

1. Human feedback embedded directly in the optimization loop. The authors extend a relaxation-labeling solver so that user-verified placements are written into the solver's evolving probability distributions (locked via a Kronecker delta), forcing those fragments to remain fixed in all later iterations and allowing the probabilistic configuration to be updated dynamically.

2. Two complementary interaction strategies. Iterative Anchoring (IA) operates on a dynamically defined local neighborhood around locked fragments, ranking candidate neighbors by a neighbor suitability score and solving only over the top-k candidates; Continuous Interactive Refinement (CIR) keeps a global scope, letting the user pause, inspect, correct and resume the solver over all fragments.

3. Demonstrated superiority over automatic and manual baselines. On RePAIR Groups 1, 3 and 39, the hybrid strategies beat the fully automatic relaxation-labeling solver and the fully manual GUI-only reconstruction in accuracy and efficiency.

4. A working interactive interface. The system is implemented in Python using the Kivy library, supporting zooming, panning, one-click locking of verified pieces, and dragging of misaligned fragments, with a modular design intended for future extensions.

Main Findings

• HIL-CIR is the most accurate strategy on every tested group. It reaches Q-Pos 0.909 / RMSE 0.52 px on G1, 0.877 / 0.71 px on G3, and 0.906 / 0.68 px on G39. The authors attribute this to continuous refinement of the global structure.

• HIL-IA is competitive and scales better locally. It achieves Q-Pos 0.895 / RMSE 0.58 px on G1, 0.882 / 0.89 px on G3, and 0.886 / 1.61 px on G39, with faster individual loops because of its restricted local scope — though total reconstruction time can grow with the number of iterations.

• The fully automatic solver fails to produce stable assemblies. Auto RL scores 0.311 / 16.9 px on G1, 0.315 / 18.3 px on G3, and 0.197 / 15.6 px on G39, with run times of 87 s, 132 s and 120 s respectively.

• Hybrid methods cost more time than the automatic solver but far less than full manual work. HIL-IA took 355 s, 343 s and 451 s (G1, G3, G39); HIL-CIR took 336 s, 290 s and 267 s. Manual reconstruction took 500 s, 350 s and 460 s respectively.

• Manual baselines have no reported accuracy. For the Manual condition the Q-Pos and RMSE entries are listed as N/A in Table 1.

• Perfect scores are not achievable on real data. The authors note that all Q-Pos scores remain below 1, as expected given erosion and ambiguous fragment boundaries.

• Sparse human intervention is sufficient. The qualitative analysis reports that even minimal, non-expert feedback is enough to steer the relaxation-labeling solver away from unstable solutions toward a global reconstruction.

Methodology in Plain English

The authors start from an existing game-theoretic puzzle solver. Each fragment is treated as a "player" in a non-cooperative game; the possible placements of a fragment — its x, y coordinates and rotation angle — form its set of available strategies. How well two fragments fit together at given poses defines the payoff, computed here from a fused compatibility score combining boundary shape similarity, motif alignment and edge continuity. The solver searches for a Nash equilibrium, a configuration where no piece can improve its fit by moving on its own, using replicator dynamics: probabilities over placements are repeatedly shifted toward strategies with above-average payoff.

That solver alone is unstable on degraded real fragments, so the authors put a human inside the loop. The session begins with a seed fragment chosen from the top-k ranked by a composite score: a structural term from Hough Line Transform detection of perpendicular line pairs at 90° ± 5°, plus a color term measuring the ratio of non-zero bins to total bins in a 2D hue-saturation histogram over a boundary band in HSV space. That seed is fixed at the origin with zero rotation.

After that, the user watches the solver run, accepts correct placements (which are locked and excluded from further updates) and corrects wrong ones. Locked fragments form "meta-fragments" that act as new anchors. In Iterative Anchoring, the solver only optimizes over a top-k candidate neighbor set around the current anchors, keeping computation local and scalable; rejected candidates are skipped and the next one is proposed. In Continuous Interactive Refinement, the solver keeps optimizing globally and the user interrupts as needed. Evaluation uses the geometry-based Q-Pos metric from the RePAIR benchmark, which measures normalized overlap between predicted and ground-truth positions while remaining invariant to global transformations, with larger fragments weighted more heavily, plus pixel-level RMSE for Euclidean misalignment.

Why This Matters

Impact on research. The paper argues that purely automatic jigsaw solvers are not sufficient for real archaeological data at scale, and that interactive optimization is a practical middle ground. It provides a template for inserting human verification into a probabilistic, game-theoretic optimization process rather than treating human input as a separate preprocessing or postprocessing step. It also makes a case for evaluating interactive systems against both automatic and manual baselines, not just one.

Real-world applications.

• Museum and conservation work reassembling deteriorated frescoes, pottery and mosaics.
• Digital heritage projects digitizing and virtually restoring fragmented artifacts.
• On-site archaeological excavation workflows where thousands of fragments must be triaged and matched.
• Interactive exhibits or educational tools where a user participates in reassembling cultural heritage material.

Industry relevance. The framework's interface is built on the open-source Kivy library and the solver is described as modular, so it can potentially be swapped for other compatible solvers and extended with additional tools. The human-in-the-loop pattern — expert validation of machine proposals — is applicable beyond archaeology wherever automated matching is unreliable at scale.

Future Directions

• Inpainting integration. The authors explicitly name inpainting tools as a planned extension, which would address the missing regions that keep Q-Pos scores below 1.
• Adaptive ranking via reinforcement learning. The paper also names adaptive ranking strategies based on reinforcement learning as a possible extension, which would reduce the human effort needed to reject poor candidate neighbors.
• Scaling to the full benchmark. Only Groups 1, 3 and 39 were tested, while the RePAIR benchmark aims to document over 10,000 fragments; validating the approach across the broader collection, and characterizing how IA and CIR degrade as fragment counts grow, remains open.
• Formal evaluation of human effort. The paper reports run times but no measure of user time, number of user decisions, or user expertise; a structured user study would clarify how much and what kind of human input is actually required.

Target Audience

Researchers and practitioners in computer vision, cultural heritage computing and digital archaeology who work on fragment reassembly or puzzle solving; HCI researchers interested in human-in-the-loop optimization and interactive machine learning; museum conservators and heritage professionals evaluating tools for artifact reconstruction; and graduate students studying game-theoretic methods such as relaxation labeling and replicator dynamics applied to vision problems.

Authors’ abstract

Reassembling real-world archaeological artifacts from fragmented pieces poses significant challenges due to erosion, missing regions, irregular shapes, and large-scale ambiguity. Traditional jigsaw puzzle solvers, often designed for clean synthetic scenarios, struggle under these conditions, especially when the number of fragments grows into the thousands, as in the RePAIR benchmark. In this paper, we propose a human-in-the-loop (HIL) puzzle solving framework designed to address the complexity and scale of real-world cultural heritage reconstruction. Our approach integrates an automatic relaxation-labeling solver with interactive human guidance, allowing users to iteratively lock verified placements, correct errors, and guide the system toward semantically and geometrically coherent assemblies. We introduce two complementary interaction strategies, Iterative Anchoring and Continuous Interactive Refinement, which support scalable reconstruction across varying levels of ambiguity and puzzle size. Experiments on several RePAIR groups demonstrate that our hybrid approach substantially outperforms both fully automatic and manual baselines in accuracy and efficiency, offering a practical solution for large-scale expert-in-the-loop artifact reassembly.