Solving archaeological puzzles. (November 2021) - Derech, Niv; Tal, Ayellet; Shimshoni, Ilan
Highlights: In the paper we propose a novel approach for solving puzzles whose pieces are of general shape, which need not necessarily match precisely due to erosion, and which have degraded unevenly over time. We define the notion of valid transformations and propose a method of sampling them. This method may find uses in other domains. We define a novel dissimilarity score that takes into account the special characteristics of the domain. We introduce the notion of confidence in the dissimilarity scores, which depends not only on the value of the dissimilarity, but also on those of the competing matches. Confidence may be used not only in re-assembly, but also in other applications that are based on dissimilarity. Abstract: This paper focuses on the re-assembly of an archaeological artifact, given images of its fragments. This problem can be considered as a special challenging case of puzzle solving. The restricted case of re-assembly of a natural image from square pieces has been investigated extensively and was shown to be a difficult problem in its own right. Likewise, the case of matching "clean" 2D polygons/splines based solely on their geometric properties has been studied. But what if these ideal conditions do not hold? This is the problem addressed in the paper. Three unique characteristics of archaeological fragments make puzzle solving extremely difficult: (1) The fragments are of general shape; (2) They are abraded, especially at the boundaries (where the strongest cues for matching should exist); and (3) The domain of valid transformations between the pieces is continuous. The key contribution of this paper is a fully-automatic and general algorithm that addresses puzzle solving in this intriguing domain. We show that our approach manages to correctly reassemble dozens of broken artifacts and frescoes.