Efficiently matching sets of features with random histograms

ABSTRACT

As the commonly used representation of a feature-rich data object has evolved from a single feature vector to a set of feature vectors, a key challenge in building a content-based search engine for feature-rich data is to match feature-sets efficiently. Although substantial progress has been made during the past few years, existing approaches are still inefficient and inflexible for building a search engine for massive datasets. This paper presents a randomized algorithm to embed a set of features into a single high-dimensional vector to simplify the feature-set matching problem. The main idea is to project feature vectors into an auxiliary space using locality sensitive hashing and to represent a set of features as a histogram in the auxiliary space. A histogram is simply a high dimensional vector, and efficient similarity measures like L₁ and L₂ distances can be employed to approximate feature-set distance measures.

We evaluated the proposed approach under three different task settings, i.e. content-based image search, image object recognition and near-duplicate video clip detection. The experimental results show that the proposed approach is indeed effective and flexible. It can achieve accuracy comparable to the feature-set matching methods, while requiring significantly less space and time. For object recognition with Caltech 101 dataset, our method runs 25 times faster to achieve the same precision as Pyramid Matching Kernel, the state-of-the-art feature-set matching method.

REFERENCES

• 1: http://www.cs.princeton.edu/cass.
• 2: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 3: C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 4: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 5: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 6: Yining Deng , b. s. Manjunath, Unsupervised Segmentation of Color-Texture Regions in Images and Video, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.8, p.800-810, August 2001 [doi>10.1109/34.946985]
• 7: W. Dong, M. Charikar, and K. Li. High dimensional similarity search with sketches. In Proceedings of the 31st Annual International ACM SIGIR Conference on Research & Development on Information Retrieval, Singapore, July 2008.
• 8: Li Fei-Fei , Rob Fergus , Pietro Perona, Learning Generative Visual Models from Few Training Examples: An Incremental Bayesian Approach Tested on 101 Object Categories, Proceedings of the 2004 Conference on Computer Vision and Pattern Recognition Workshop (CVPRW'04) Volume 12, p.178, June 27-July 02, 2004
• 9: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 10: K. Grauman and T. Darrell. Pyramid match hashing: Sub-linear time indexing over partial correspondences. Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE Conference on, pages 1--8, 17-22 June 2007.
• 11: Kristen Grauman , Trevor Darrell, The Pyramid Match Kernel: Discriminative Classification with Sets of Image Features, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1458-1465, October 17-20, 2005 [doi>10.1109/ICCV.2005.239]
• 12: K. Grauman and T. Darrell. Approximate correspondences in high dimensions. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems 19, pages 505--512. MIT Press, Cambridge, MA, 2007.
• 13: Kristen Grauman , Trevor Darrell, The Pyramid Match Kernel: Efficient Learning with Sets of Features, The Journal of Machine Learning Research, 8, p.725-760, 5/1/2007
• 14: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 15: P. Indyk and N. Thaper. Fast image retrieval via embeddings. In 3rd International Workshop on Statistical and Computational Theories of Vision, 2003.
• 16: Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150429]
• 17: Y. Ke and R. Sukthankar. Pca-sift: A more distinctive representation for local image descriptors. cvpr, 02:506--513, 2004.
• 18: A. Kirsch and M. Mitzenmacher. Distance-sensitive bloom filters. In ALENEX '06: Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments, pages 41--50, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics.
• 19: Svetlana Lazebnik , Cordelia Schmid , Jean Ponce, Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.2169-2178, June 17-22, 2006 [doi>10.1109/CVPR.2006.68]
• 20: B. Leibe and B. Schiele. Analyzing appearance and contour based methods for object categorization. cvpr, 02:409, 2003.
• 21: 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]
• 22: Qin Lv , Moses Charikar , Kai Li, Image similarity search with compact data structures, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031213]
• 23: Qin Lv , William Josephson , Zhe Wang , Moses Charikar , Kai Li, Ferret: a toolkit for content-based similarity search of feature-rich data, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 24: S. Lyu. A kernel between unordered sets of data: The gaussian mixture approach. In European Conference on Machine Learning (ECML), Porto, Portugal, 2005.
• 25: Siwei Lyu, Mercer Kernels for Object Recognition with Local Features, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.223-229, June 20-26, 2005 [doi>10.1109/CVPR.2005.223]
• 26: A. Opelt, M. Fussenegger, A. Pinz, and P. Auer. Weak Hypotheses and Boosting for Generic Object Detection and Recognition, volume 3022/2004 of Lecture Notes in Computer Science, pages 71--84. Springer Berlin / Heidelberg, 2004.
• 27: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, The Earth Mover's Distance as a Metric for Image Retrieval, International Journal of Computer Vision, v.40 n.2, p.99-121, Nov. 2000 [doi>10.1023/A:1026543900054]
• 28: James Z. Wang , Jia Li , Gio Wiederhold, SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.9, p.947-963, September 2001 [doi>10.1109/34.955109]
• 29: Xiao Wu , Alexander G. Hauptmann , Chong-Wah Ngo, Practical elimination of near-duplicates from web video search, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291280]
• 30: J. Zhang , M. Marszałek , S. Lazebnik , C. Schmid, Local Features and Kernels for Classification of Texture and Object Categories: A Comprehensive Study, International Journal of Computer Vision, v.73 n.2, p.213-238, June 2007 [doi>10.1007/s11263-006-9794-4]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding

General Terms:
Algorithms, Experimentation

Keywords:
locality sensitive hashing, random histogram, set of features