Signature quadratic form distances for content-based similarity

ABSTRACT

Determining similarity is a fundamental task in querying multimedia databases in a content-based way. For this challenging task, there exist numerous similarity models which measure the similarity among objects by using their contents. In order to cope with voluminous multimedia data, similarity models are supposed to be both effective and efficient. To this end, we introduce the Signature Quadratic Form Distance measure which allows efficient similarity computations based on flexible feature representations. Our new approach bridges the gap between the well-known concept of Quadratic Form Distances and feature signatures. Experimentation indicates that our similarity measure is able to compete with state-of-the-art similarity models regarding effectiveness of content-based similarity search. Moreover, our Signature Quadratic Form Distance outperforms the established Earth Mover's Distance in efficiency: we obtain a speed-up factor of greater than 50.

REFERENCES

• 1: T. Deselaers, D. Keysers, and H. Ney. Features for Image Retrieval: An Experimental Comparison. Information Retrieval, 11(2):77--107, 2008.
• 2: A. Dorado and E. Izquierdo. Fuzzy color signatures. In Proc. IEEE Int. Conf. on Image Processing, volume 1, pages 433--436, 2002.
• 3: C. Faloutsos, R. Barber, M. Flickner, J. Hafner, W. Niblack, D. Petkovic, and W. Equitz. Efficient and Effective Querying by Image Content. J. Intell. Inf. Syst., 3(3/4):231--262, 1994.
• 4: A. Ghias, J. Logan, D. Chamberlin, and B. C. Smith. Query by Humming: Musical Information Retrieval in an Audio Database. In ACM Multimedia, pages 231--236, 1995.
• 5: D. Huttenlocher, G. Klanderman, and W. Rucklidge. Comparing images using the Hausdorff Distance. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 15(9):850--863, 1993.
• 6: C. D. Manning, P. Raghavan, and H. Schütze. Introduction to Information Retrieval. Cambridge University Press, New York, NY, USA, 2008.
• 7: O. Marques and B. Furht. Content-based image and video retrieval. Multimedia systems and applications series. Kluwer, Boston, 2002.
• 8: Y. Rubner, C. Tomasi, and L. J. Guibas. The Earth Mover's Distance as a Metric for Image Retrieval. Int. J. Comput. Vis., V40(2):99--121, 2000.
• 9: J. Wang, J. Li, and G. Wiederhold. SIMPLIcity: Semantics-sensitive Integrated Matching for Picture LIbraries. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 23(9):947--963, 2001.

INDEX TERMS

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

General Terms:
Experimentation, Theory

Keywords:
content-based similarity search, feature signatures, quadratic form distance