Abstract:
Investigates the problem of retrieving similar shapes from a large database; in particular, we focus on medical tumor shapes (finding tumors that are similar to a given p...Show MoreMetadata
Abstract:
Investigates the problem of retrieving similar shapes from a large database; in particular, we focus on medical tumor shapes (finding tumors that are similar to a given pattern). We use a natural similarity function for shape matching, based on concepts from mathematical morphology, and we show how it can be lower-bounded by a set of shape features for safely pruning candidates, thus giving fast and correct output. These features can be organized in a spatial access method, leading to fast indexing for range queries and nearest-neighbor queries. In addition to the lower-bounding, our second contribution is the design of a fast algorithm for nearest-neighbor searching, achieving significant speedup while provably guaranteeing correctness. Our experiments demonstrate that roughly 90% of the candidates can be pruned using these techniques, resulting in up to 27 times better performance compared to sequential scanning.
Published in: IEEE Transactions on Knowledge and Data Engineering ( Volume: 10, Issue: 6, Nov.-Dec. 1998)
DOI: 10.1109/69.738356