Deepzzle: Solving Visual Jigsaw Puzzles With Deep Learning and Shortest Path Optimization

Marie-Morgane Paumard (1) , David Picard (2) , Hedi Tabia (3)

1 ETIS - UMR 8051 - Equipes Traitement de l'Information et Systèmes
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 IBISC - Informatique, BioInformatique, Systèmes Complexes

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: Deep learning; Branch-cutcultural heritage; GraphImage reassembly; Jigsaw puzzle

Domains: Machine Learning [cs.LG]; Computer Vision and Pattern Recognition [cs.CV]

Marie-Morgane Paumard, David Picard, Hedi Tabia. Deepzzle: Solving Visual Jigsaw Puzzles With Deep Learning and Shortest Path Optimization. IEEE Transactions on Image Processing, 2020, 29, pp.3569--3581. ⟨10.1109/TIP.2019.2963378⟩. ⟨hal-02494602⟩