@techreport{TR-IC-01-04,
number = {IC-01-04},
author = {Helena Cristina da Gama LeitÃ£o and Jorge Stolfi},
title = {A Multi-Scale Technique for Computer Assisted Re-Assembly of Fragmented Objects},
month = {March},
year = {2001},
institution = {Institute of Computing, University of Campinas},
note = {In English, 23 pages.
\par\selectlanguage{english}\textbf{Abstract}
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).}
}
}