Archaeological Fragment Reconstruction Using Curve-Matching

We present a novel approach to the problem of puzzle solving as it relates to archaeological fragment reconstruction. We begin with a set of broken fragments. In the first stage, we compare every pair of fragments and use partial curve matching to find similar portions of their respective boundaries. Partial curve matching is typically a very difficult problem because the specification of the partial curves are highly unconstrained and curve matching is computationally expensive. To address the first problem, we only consider matches which begin at fragment corners and then use curve-matching with normalized energy to determine how far the match extends. We also reduce computational cost by employing a multi-scale approach. This allows us to quickly generate many possible matches at a coarse scale and only keep the best ones to be matched again at a finer scale. In the second stage, we take a rank-ordered list of pairwise matches to search for a globally optimal arrangement. The search is based on a best-first strategy which adds fragments with the highest pairwise affinity first, but then evaluates their confidence as part of the global solution by rewarding the formation of triple junctions which are dominant in archaeological puzzles. To prevent failure due to the inclusion of spurious matches, we employ a standard beam-search to simultaneously expand on multiple solutions. Results on several cases are demonstrated.