Scalability of local image descriptors: a comparative study

ABSTRACT

Computer vision researchers have recently proposed several local descriptor schemes. Due to lack of database support, however, these descriptors have only been evaluated using small image collections. Recently, we have developed the PvS-framework, which allows efficient querying of large local descriptor collections. In this paper, we use the PvSframework to study the scalability of local image descriptors. We propose a new local descriptor scheme and compare it to three other well known schemes. Using a collection of almost thirty thousand images, we show that the new scheme gives the best results in almost all cases. We then give two stop rules to reduce query processing time and show that in many cases only a few query descriptors must be processed to find matching images. Finally, we test our descriptors on a collection of over three hundred thousand images, resulting in over 200 million local descriptors, and show that even at such a large scale the results are still of high quality, with no change in query processing time.

REFERENCES

• 1: L. Amsaleg and P. Gros. Content-based retrieval using local descriptors: Problems and issues from a database perspective. Pattern Analysis and Applications, 4(2/3), 2001.
• 2: Sid-Ahmed Berrani , Laurent Amsaleg , Patrick Gros, Approximate searches: k-neighbors + precision, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956870]
• 3: Sid-Ahmed Berrani , Laurent Amsaleg , Patrick Gros, Robust content-based image searches for copyright protection, Proceedings of the 1st ACM international workshop on Multimedia databases, November 07-07, 2003, New Orleans, LA, USA [doi>10.1145/951676.951690]
• 4: M. Brown and D. G. Lowe. Invariant features from interest point groups. In British Machine Vision Conf., 2002.
• 5: Y. Dufournaud, C. Schmid, and R. Horaud. Matching images with different resolutions. In CVPR, 2000.
• 6: Ronald Fagin , Ravi Kumar , D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872795]
• 7: L. M. J. Florack, B. M. ter Haar Romeny, J. J. Koenderink, and M. A. Viergever. General intensity transformation and differential invariants. Journal of Mathematical Imaging and Vision, 4(2), 1994.
• 8: M. Grabner, H. Grabner, and H. Bischof. Fast approximated SIFT. In ACCV, 2006.
• 9: C. Harris and M. Stephens. A combined corner and edge detector. In Alvey Vision Conf., 1988.
• 10: A. Joly, C. Fr'elicot, and O. Buisson. Robust content-based video copy identification in a large reference database. In CIVR, 2003.
• 11: Y. Ke and R. Sukthankar. PCA-SIFT: A more distinctive representation for local image descriptors. In CVPR, 2004.
• 12: Yan Ke , Rahul Sukthankar , Larry Huston, An efficient parts-based near-duplicate and sub-image retrieval system, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027729]
• 13: H. Lejsek, F. H. Asmundsson, B. Th. Jónsson, and L. Amsaleg. Efficient and effective image copyright enforcement. In BDA, 2005.
• 14: Tony Lindeberg, Feature Detection with Automatic Scale Selection, International Journal of Computer Vision, v.30 n.2, p.79-116, Nov. 1998 [doi>10.1023/A:1008045108935]
• 15: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 16: K. Mikolajczyk and C. Schmid. A performance evaluation of local descriptors. In CVPR, 2003.
• 17: Kim Steenstrup Pedersen , Mads Nielsen, The Hausdorff Dimension and Scale-Space Normalisation of Natural Images, Proceedings of the Second International Conference on Scale-Space Theories in Computer Vision, p.271-282, September 26-27, 1999
• 18: F. A. P. Petitcolas et al. A public automated web-based evaluation service for watermarking schemes: StirMark benchmark. In Electronic Imaging, Security and Watermarking of Multimedia Contents III, 2001.
• 19: A. P. Witkin. Scale-space filtering. In IJCAI, 1983.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Multimedia databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
PvS-framework, high-dimensional indexing, local image descriptors, median rank aggregation, scalability