A Multi-Scale Method for the Re-Assembly of Fragmented Objects

We describe here an efficient algorithm for re-assembling one or more un-known objects that have been broken or torn into a large number N of ir-regular fragments—a problem that often arises in achaeology, art restora-tion, forensics, and other disciplines. The algorithm compares the curvature-encoded fragment outlines, using a modified dynamic programming sequence-matching algorithm, at progressively increasing scales of resolution. The to-tal cost gets reduced from(N2L2) (whereL is the mean number of samples per fragment) to about O(N2L); which, in principle, allows the method to be used for problems of practical size (N = 103 to 105 fragments, L = 103 to 104 samples). The performance of the algorithm is illustrated with an artificial but realistic example.