Deepzzle: Solving Visual Jigsaw Puzzles with Deep Learning andShortest Path Optimization

Marie-Morgane Paumard, David Picard, Hedi Tabia

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

Traditional jigsaw puzzle solvers rely heavily on edge-matching—finding contours or color patterns that continue perfectly from one piece to the next. However, in archaeology, this is rarely possible. Fragments are often eroded, leaving wide gaps between them, or are missing entirely. Deepzzle addresses this "image reassembly problem with wide space" by forcing an algorithm to learn from the internal content of fragments rather than their borders.

Individual fragments showing the wide gaps and cropped borders used to simulate erosion.

Methodology

The Deepzzle framework operates in two distinct stages:

1. Relative Position Prediction

A Siamese Neural Network, acting as a Feature Extraction Network (FEN), compares a "central" fragment with a "lateral" fragment. The network is trained to output a probability distribution across 9 classes: the eight possible neighboring positions in a $3 \\times 3$ grid, plus a ninth "outsider" class for fragments that do not belong to the puzzle. By cropping fragments with significant 48-pixel margins, the model is forced to identify semantic features (e.g., the top of a head vs. a torso) to determine placement.

2. Graph-Based Reassembly and Branch-Cuts

To transition from pairwise predictions to a global layout, the problem is modeled as finding the most probable joint configuration. Assuming a Markov Chain relationship between neighbors, the joint probability is simplified into a product of pairwise probabilities. This is mapped onto a graph where nodes represent placement decisions and edge weights are negative log-probabilities.

To handle the NP-complete complexity of the full graph, the authors introduce branch-cuts. This technique prunes paths in the graph that fall below a probability threshold (\theta). Setting \theta = 0.05$ achieved a three-order-of-magnitude speedup (from ~20,000 seconds to ~20 seconds per puzzle) with minimal impact on accuracy.

A $3 \\times 3$ grid of fragments (left) and the resulting reassembly (right) demonstrating the challenge of wide spacing.

Datasets and Evaluation

The model was primarily trained and tested on the MET Dataset, containing 2,000 high-resolution images of artifacts and paintings from the Metropolitan Museum of Art. ImageNet was used for cross-dataset validation to ensure generalization.

The authors observed that paintings are significantly more difficult to reassemble than artifacts or text. This "semantic difficulty" arises from large areas of uniform background (like sky or shadows), where fragments are visually interchangeable, leading to technically incorrect but "visually plausible" swaps.

Key Results

  • Accuracy: Deepzzle achieved 44.4% accuracy for full image reassembly and 89.9% for individual fragment positioning when the center was known.
  • Robustness: The system successfully handled "patchwork" puzzles from different photographs of the same object and maintained a 60% perfect placement rate even when three "outsider" fragments were introduced.
  • Efficiency: The branch-cut optimization makes the solver tractable for real-world applications where pieces may be missing or mixed.

Conclusion and Future Work

While Deepzzle shows promise for cultural heritage applications, limitations remain. The current $96 \\times 96$ resolution per fragment can be too low for fine-grained alignment, particularly in text. Future work will aim to scale the graph optimization logic beyond fixed $3 \\times 3$ grids to accommodate the irregular shapes and larger piece counts found in actual archaeological sites.

Summary updated

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. Keywords: image reassembly, jigsaw puzzle, deep learning, graph, branch-cut, cultural heritage
BibTeX
@article{paumard2020deepzzle,
  author = {Marie-Morgane Paumard and David Picard and Hedi Tabia},
  title = {{Deepzzle: Solving Visual Jigsaw Puzzles with Deep Learning andShortest Path Optimization}},
  journal = {IEEE Trans. Image Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=iLtzlhOal4},
}
Figure