Fast and effective similarity search in medical tumor databases using morphology

Philip Korn, Nicholaos D. Sidiropoulos, Christos Faloutsos, Eliot L. Siegel, Zenon Protopapas

Research output: Contribution to journalConference articlepeer-review

7 Scopus citations


We examine the problem of finding similar tumor shapes. The main contribution of this work is the proposal of a natural (dis-)similarity function for shape matching called the 'morphological distance'. This function has two desirable properties: a) it matches human perception of similarity, as we illustrate with precision/recall experiments; b) it can be lower-bounded by a set of features, leading to fast indexing for range queries and nearest neighbor queries. We use state-of-the-art methods from morphology both in defining our distance function and for feature extraction. In particular, we use the 'size-distribution', related to the 'pattern spectrum', to extract features from shapes. Following Jagadish and Faloutos et. al., we organize the n-d feature points in a spatial access method. We show that any Lp norm in the n-d space lower-bounds the morphological distance. This guarantees no false dismissals for range queries. In addition, we present a nearest neighbor algorithm that also guarantees no false dismissals. We implemented the method and tested it against a testbed of realistic tumor shapes generated by an established tumor- growth model. The response time of our method is up to 27 times faster than sequential scanning. Moreover, precision/recall experiments show that the proposed distance captures very well the dissimilarity as perceived by humans.

Original languageEnglish (US)
Pages (from-to)116-129
Number of pages14
JournalProceedings of SPIE - The International Society for Optical Engineering
StatePublished - 1996
Externally publishedYes
EventMultimedia Storage and Archiving Systems - Boston, MA, United States
Duration: Nov 18 1996Nov 18 1996


Dive into the research topics of 'Fast and effective similarity search in medical tumor databases using morphology'. Together they form a unique fingerprint.

Cite this