Locality condensation: a new dimensionality reduction method for image retrieval

ABSTRACT

Content-based image similarity search plays a key role in multimedia retrieval. Each image is usually represented as a point in a high-dimensional feature space. The key challenge of searching similar images from a large database is the high computational overhead due to the "curse of dimensionality". Reducing the dimensionality is an important means to tackle the problem. In this paper, we study dimensionality reduction for top-k image retrieval. Intuitively, an effective dimensionality reduction method should not only preserve the close locations of similar images (or points), but also separate those dissimilar ones far apart in the reduced subspace. Existing dimensionality reduction methods mainly focused on the former. We propose a novel idea called Locality Condensation (LC) to not only preserve localities determined by neighborhood information and their global similarity relationship, but also ensure that different localities will not invade each other in the low-dimensional subspace. To generate non-overlapping localities in the subspace, LC first performs an elliptical condensation, which condenses each locality with an elliptical shape into a more compact hypersphere to enlarge the margins among different localities and estimate the projection in the subspace for overlap analysis. Through a convex optimization, LC further performs a scaling condensation on the obtained hyperspheres based on their projections in the subspace with minimal condensation degrees. By condensing the localities effectively, the potential overlaps among different localities in the low-dimensional subspace are prevented. Consequently, for similarity search in the subspace, the number of false hits (i.e., distant points that are falsely retrieved) will be reduced. Extensive experimental comparisons with existing methods demonstrate the superiority of our proposal.

REFERENCES

• 1: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 2: Y. Bengio, J.-F. Paiement, P. Vincent, O. Delalleau, N. L. Roux, and M. Ouimet. Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering. In NIPS, 2003.
• 3: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 4: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 5: Deng Cai , Xiaofei He, Orthogonal locality preserving indexing, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076039]
• 6: Deng Cai , Xiaofei He , Jiawei Han, Spectral regression: a unified subspace learning framework for content-based image retrieval, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291329]
• 7: Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002 [doi>10.1145/568518.568520]
• 8: Kaushik Chakrabarti , Sharad Mehrotra, Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces, Proceedings of the 26th International Conference on Very Large Data Bases, p.89-100, September 10-14, 2000
• 9: V. de Silva and J. B. Tenenbaum. Global versus local methods in nonlinear dimensionality reduction. In NIPS, pages 705--712, 2002.
• 10: S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391--407, 1990.
• 11: C. Elkan. Using the triangle inequality to accelerate k-means. In ICML, pages 147--153, 2003.
• 12: 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]
• 13: Xiaofei He , Deng Cai , Jiawei Han, Learning a Maximum Margin Subspace for Image Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.20 n.2, p.189-201, February 2008 [doi>10.1109/TKDE.2007.190692]
• 14: Xiaofei He , Deng Cai , Haifeng Liu , Wei-Ying Ma, Locality preserving indexing for document representation, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009012]
• 15: Xiaofei He , Wanli Min , Deng Cai , Kun Zhou, Laplacian optimal design for image retrieval, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277764]
• 16: X. He and P. Niyogi. Locality preserving projections. In NIPS, 2003.
• 17: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 18: A. Hyvärinen, J. Karhunen, and E. Oja. Independent Component Analysis. John Wiley & Sons, 2001.
• 19: H. V. Jagadish , Beng Chin Ooi , Kian-Lee Tan , Cui Yu , Rui Zhang, iDistance: An adaptive B⁺-tree based indexing method for nearest neighbor search, ACM Transactions on Database Systems (TODS), v.30 n.2, p.364-397, June 2005 [doi>10.1145/1071610.1071612]
• 20: I. T. Jolliffe. Principal Component Analysis. Springer-Verlag, second edition, 2002.
• 21: Daniel A. Keim , Benjamin Bustos, Similarity Search in Multimedia Databases, Proceedings of the 20th International Conference on Data Engineering, p.873, March 30-April 02, 2004
• 22: K. Mikolajczyk and J. Matas. Improving descriptors for fast tree matching by optimal linear projection. In ICCV, 2007.
• 23: S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323--2326, 2000.
• 24: Heng Tao Shen , Xiaofang Zhou , Aoying Zhou, An adaptive and dynamic dimensionality reduction method for high-dimensional indexing, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.2, p.219-234, April 2007 [doi>10.1007/s00778-005-0167-3]
• 25: J. B. Tenenbaum, V. d. Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, 2000.
• 26: M. E. Tipping and C. M. Bishop. Probabilistic principal component analysis. Journal of The Royal Statistical Society Series B, 61(3):611--622, 1999.
• 27: 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
• 28: Yi-Leh Wu , Divyakant Agrawal , Amr El Abbadi, A comparison of DFT and DWT based similarity search in time-series databases, Proceedings of the ninth international conference on Information and knowledge management, p.488-495, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354857]
• 29: A. Yavlinsky, E. Schofield, and S. M. Rüger. Automated image annotation using global features and robust nonparametric density estimation. In CIVR, pages 507--517, 2005.
• 30: F. W. Young and R. M. Hamer. Multidimensional Scaling: History, Theory and Applications. Lawrence Erlbaum Associates, 1987.
• 31: Jie Yu , Qi Tian, Learning image manifolds by semantic subspace projection, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA [doi>10.1145/1180639.1180710]
• 32: Xin Zheng , Deng Cai , Xiaofei He , Wei-Ying Ma , Xueyin Lin, Locality preserving clustering for image database, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027731]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
dimensionality reduction, locality condensation, top-k image retrieval