A Multi-Scale Technique for Computer Assisted Re-Assembly of Fragmented Objects

We describe here an efficient algorithm for reassembling one or more unknown objects that have been broken or torn into a large number $N$ of irregular fragments. The algorithm works by comparing the curvature-encoded fragment outlines, using a modified dynamic programming sequence-matching algorithm. By comparing the outlines at progressively increasing scales of resolution, we manage to reduce the cost of the search from $\theta(N^2 L^2)$ (where $L$ is the mean number of samples per fragment) to about $O(N^2 L)$; which, in principle, allows the method to be used for problems of practical size ($N = 10^3$ to $10^5$ fragments, $L = 10^3$ to $10^4$ samples). The performance of the algorithm is illustrated with an artificial but realistic example. \par {\em A shorter version of this report was presented at the British Machine Vision Confrence (BMVC) in Bristol, UK (September 2000).}

2001