A multi-step strategy for approximate similarity search in image databases

ABSTRACT

Many strategies for similarity search in image databases assume a metric and quadratic form-based similarity model where an optimal lower bounding distance function exists for filtering. These strategies are mainly two-step, with the inital "filter" step based on a spatial or metric access method followed by a "refine" step employing expensive computation. Recent research on robust matching methods for computer vision has discovered that similarity models behind human visual judgment are inherently non-metric. When applying such models to similarity search in image databases, one has to address the problem of nonmetric distance functions that might to have an optimal lower bound for filtering. Here, we propose a novel three-step "prune-filter-refine" strategy for approximate similarity search on these models. First, the "prune" step adopts a spatial access method to roughly eliminate improbable matches via an adjustable distance threshold. Second, the "filter" step uses a quasi lower-bounding distance derived from the non-metric distance function of the similarity model. Third, the "refine" stage compares the query with the remaining candidates by a robust matching method for final ranking. Experimental results confirmed that the proposed strategy achieves more filtering than a two-step approach with close to no false drops in the final result.

REFERENCES

• 1: Mihael Ankerst , Hans-Peter Kriegel , Thomas Seidl, A Multistep Approach for Shape Similarity Search in Image Databases, IEEE Transactions on Knowledge and Data Engineering, v.10 n.6, p.996-1004, November 1998 [doi>10.1109/69.738362 ]
• 2: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 3: Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.357-368, May 11-15, 1997, Tucson, Arizona, United States
• 4: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States
• 5: Paolo Ciaccia , Marco Patella, Searching in metric spaces with user-defined and approximate distances, ACM Transactions on Database Systems (TODS), v.27 n.4, p.398-437, December 2002 [doi>10.1145/582410.582412]
• 6: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 7: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 8: James Hafner , Harpreet S. Sawhney , Will Equitz , Myron Flickner , Wayne Niblack, Efficient Color Histogram Indexing for Quadratic Form Distance Functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.7, p.729-736, July 1995 [doi>10.1109/34.391417 ]
• 9: David W. Jacobs , Daphna Weinshall , Yoram Gdalyahu, Classification with Nonmetric Distances: Image Retrieval and Class Representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.6, p.583-600, June 2000 [doi>10.1109/34.862197 ]
• 10: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• 11: Kreutz, M., Volpel, B. and Janssen, H. (1996): Scale-Invariant Image Recognition Based on Higher Order Autocorrelation Features. Pattern Recognition 29 (1).
• 12: Kurita, T., Otsu, N. and Sato, T. (1992): A Face Recognition Method Using Higher Order Local Autocorrelation and Multivariate Analysis. In Proc. 11th IAPR International Conference on Pattern Recognition, The Hague, 213-216.
• 13: Kwan, P., Kameyama, K. and Toraich, K. (2003): On a relaxation-labeling algorithm for real-time contour-based image similarity retrieval. Image and Vision Computing. 21 (3):285-294.
• 14: Kwan, P., Torach, K., Kitagawa, H. and Kameyama, K. (2003): Approximate Query Processing for a Content-Based Image Retrieval Method. In: V. Malik et al.(Eds.): DEXA 2003, LNCS 2736, Springer-Verlag, 517-526.
• 15: McLaughlin, J. A. and Raviv, J. (1968): Nth-order autocorrelations in pattern recognition. Information and Control 12:121-142.
• 16: Nagashima, H., Tsubaki, S. and Nakajima, J. (2003): A Classification for Trademark Images Using the Auto-correlation Function Graph Figure. IEEJ Trans. EIS. 123 (9):1547-1554.
• 17: Davood Rafiei , Alberto Mendelzon, Similarity-based queries for time series data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.13-25, May 11-15, 1997, Tucson, Arizona, United States
• 18: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 19: System Product Co. Ltd. (2003), "Home Page", http://www.e-spc.co.jp/hp/product_3_ 3.htm
• 20: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Image databases

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Design, Performance

Keywords:
image databases, lower bound, multi-step strategy, non-metric distance, similarity search