A Multistep Approach for Shape Similarity Search in Image Databases

Similarity search is a crucial task in image databases, particularly in the presence of errors induced by segmentation or scanning images. The resulting slight displacements or rotations have not been considered so far in the literature. We present a new similarity model that flexibly addresses this problem. By specifying neighborhood influence weights, the user may adapt the similarity distance functions to her or his requirements or preferences. Technically, the new similarity model is based on quadratic forms for which we present a multistep query processing architecture particularly for high dimensions as they occur in image databases. Our algorithm to reduce the dimensionality of quadratic form-based similarity queries results in a lower-bounding distance function that is proven to provide an optimal filter selectivity. Experiments on our test database of 10,000 images demonstrate the applicability and the performance of our approach even in high dimensions such as 1,024.

Authors: Ankerst M., Kriegel H.-P., Seidl T.
Published in: IEEE Transactions on Knowledge and Data Engineering (TKDE) 10(6)
Sprache: EN
Jahr: 1998
Seiten: 996-1004
Konferenz: TKDE
Typ: Zeitschriftenartikel