Abstract
We tackle the image reassembly problem with wide space between the fragments, in such a way that the patterns and colors continuity is mostly unusable. The spacing emulates the erosion of which the archaeological fragments suffer. We crop-square the fragments borders to compel our algorithm to learn from the content of the fragments. We also complicate the image reassembly by removing fragments and adding pieces from other sources. We use a two-step method to obtain the reassemblies: 1) a neural network predicts the positions of the fragments despite the gaps between them; 2) a graph that leads to the best reassemblies is made from these predictions. In this paper, we notably investigate the effect of branch-cut in the graph of reassemblies. We also provide a comparison with the literature, solve complex images reassemblies, explore at length the dataset, and propose a new metric that suits its specificities.
Introduction
Reassembling fragmented objects is a critical task in archaeology, yet it is fraught with difficulties. Fragments are rarely pristine; they suffer from erosion, which creates significant gaps between pieces, and are often mixed with "outsider" fragments from other objects. Traditional jigsaw puzzle solvers typically rely on edge-matching or local feature continuity. However, when erosion is severe, these methods fail because the borders no longer match.
Deepzzle addresses this "wide-gap" problem by forcing a model to learn from the semantic content of fragments—understanding, for instance, that a fragment containing an eye should be positioned above one containing a mouth. The framework utilizes a Siamese neural network for relative position prediction and a graph-based shortest-path optimization to ensure a globally coherent reassembly.
Methodology
The Deepzzle framework operates in two primary stages:
1. Relative Position Prediction
A Siamese neural network, acting as a Feature Extraction Network, compares a designated "central" fragment with various "lateral" fragments. The network outputs a probability distribution across nine classes: the eight possible neighboring positions in a 3x3 grid and a ninth "outsider" class for fragments that do not belong to the puzzle. This inclusion of an outsider class is vital for real-world applications where datasets are noisy.
2. Graph-Based Optimization
To resolve potential conflicts—such as multiple fragments being predicted for the same location—the reassembly is modeled as a pathfinding problem. A graph is constructed where nodes represent placement decisions, and edge weights are derived from the negative log-likelihoods of the neural network's predictions. The optimal reassembly corresponds to the shortest path from the start node (S) to the terminal node (T).
To manage the combinatorial complexity, the authors implement "branch-cuts." By pruning paths with low-probability predictions, they reduced computation time by a factor of 1,000 with negligible impact on accuracy. In cases where the central fragment is unknown, the algorithm iteratively tests each fragment as the center and selects the configuration with the highest overall probability.
Experimental Results and Datasets
The model was evaluated using the MET Dataset, comprising 12,000 images of art pieces (artifacts, engravings, and paintings) from the Metropolitan Museum of Art, and ImageNet to test generalization.
- Performance: Deepzzle achieved 65% accuracy in relative position prediction on the MET dataset, surpassing baselines like Noroozi & Favaro (57%).
- Robustness: With an unknown central fragment, the system maintained a 91.5% accuracy for puzzles with 10 possible permutations.
- Generalization: Without retraining, the MET-trained model achieved 78.6% well-placed fragments on ImageNet, indicating it learned generalizable visual features rather than dataset-specific biases.
Discussion and Conclusion
Deepzzle demonstrates that deep learning can solve complex reassembly tasks by prioritizing semantic understanding over simple edge-matching. The introduction of the "outsider" class and branch-cut optimization makes the system both robust and efficient.
However, limitations remain. The current 96x96 pixel resolution may be too low for fine-grained tasks like matching brushstrokes. Furthermore, the reliance on a rigid 3x3 grid does not yet account for the irregular shapes found in actual archaeological fragments. Future work will focus on increasing resolution and adapting the model to non-grid-based, irregular fragmentations.
Summary updated