Ranking with local regression and global alignment for cross media retrieval

ABSTRACT

Rich multimedia content including images, audio and text are frequently used to describe the same semantics in E-Learning and Ebusiness web pages, instructive slides, multimedia cyclopedias, and so on. In this paper, we present a framework for cross-media retrieval, where the query example and the retrieved result(s) can be of different media types. We first construct Multimedia Correlation Space (MMCS) by exploring the semantic correlation of different multimedia modalities, during which multimedia content and co-occurrence information is utilized. We propose a novel ranking algorithm, namely ranking with Local Regression and Global Alignment (LRGA), which learns a robust Laplacian matrix for data ranking. In LRGA, for each data point, a local linear regression model is used to predict the ranking values of its neighboring points. We propose a unified objective function to globally align the local models from all the data points so that an optimal ranking value can be assigned to each data point. LRGA is insensitive to parameters, making it particularly suitable for data ranking. A relevance feedback algorithm is proposed to improve the retrieval performance. Comprehensive experiments have demonstrated the effectiveness of our methods.

REFERENCES

• 1: http://encarta.msn.com/.
• 2: A. D. Bimbo and P. Pala. Content-based retrieval of 3d models. ACM Transactions on Multimedia Computing, Communications and Applications, 2(1):20--43, 2006.
• 3: L. Bottou and V. Vapnik. Local learning algorithms. Neural Computation, 4(6):888--900, 1992.
• 4: F. R. K. Chung. Spectral Graph Theory. AMS Bookstore, 1997.
• 5: E. Datta, D. Joshi, J. Li and J. Wang. Image retrieval: Ideas, influences, and trends of the new age. ACM Computing Surveys, 40(2) 2008.
• 6: J. Fan et al. Classview: hierarchical video shot classification, indexing, and accessing. IEEE Transactions on Multimedia, 6(1):70--86, 2004.
• 7: J. Han and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2000.
• 8: J. He et al. Manifold-ranking based image retrieval. In ACM international conference on Multimedia, pages 9--16, 2004.
• 9: X. He, W.-Y. Ma, and H.-J. Zhang. Learning an image manifold for retrieval. In ACM international conference on Multimedia, pages 17--23, 2004.
• 10: J. Huang et al. Image indexing using color correlograms. In IEEE international conference on Computer Vision and Pattern Recognition, pages 762--768, 1997.
• 11: A. N. Langville and C. D. Meyer. Survey: Deeper inside pagerank. Internet Mathematics, 1(3): 335--380,2003.
• 12: D. Kelly and N Belkin. Reading Time, Scrolling and Interaction: Exploring Implicit Sources of User Preferences for Relevant Feedback. In SIGIR 2001.
• 13: M. S. Lew et al. Content-based multimedia information retrieval: State of the art and challenges. ACM Transactions on Multimedia Computing, Communications and Applications, 2(1):1--19, 2006.
• 14: J. Luo, M. Boutell, and C. Brown. Pictures are not taken in a vacuum - an overview of exploiting context for semantic scene content understanding. IEEE Signal Processing Magazine, 23(2):101--114, 2006.
• 15: J. Luo et al. Photo-centric multimedia authoring enhanced by cross-media retrieval. In SPIE International Symposium on Visual Communication and Image Processing, pages 9--16, 2005.
• 16: N. C. Maddage et al. Content-based music structure analysis with applications to music semantics understanding. In ACM international conference on Multimedia, pages 112--119, 2004.
• 17: M. Müller, T. Röder, and M. Clausen. Efficient content-based retrieval of motion capture data. ACM Transactions on Graphics, 24(3):677--685, 2005.
• 18: S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323--2326, 2000.
• 19: Y. Rui and T. S. Huang. Optimizing learning in image retrieval. In IEEE international conference on Computer Vision and Pattern Recognition, pages 236--243, 2000.
• 20: C. Snoek, M. Worring and A. Smeulders. Early versus Late Fusion in Semantic Video Analysis. In ACM MM, 2005.
• 21: D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In ACM symposium on Theory of computing, pages 81--90, 2004.
• 22: F. Wang and C. Zhang. Label propagation through linear neighborhoods. IEEE Transaction Knowledge Data Engineering, 20(1):55---67, 2008.%
• 23: M. Wu and B. Schölkopf. Transductive classification via local learning regularization. In International Conference on Artificial Intelligence and Statistics , 2007.
• 24: Y. Yang, Y. Zhuang, F. Wu and Y. Pan. Harmonizing hierarchical manifolds for multimedia document semantics understanding and cross-media retrieval. IEEE Transactions on Multimedia, 10(3):437--446, 2008.
• 25: Y. Yang, Y. Zhuang and W. Wang. Heterogeneous Multimedia Data Semantics Mining using Content and Location Context. ACM MM, 2008.
• 26: R. Zhang and Z. Zhang. Effective image retrieval based on hidden concept discovery in image database. IEEE Transactions on Image Processing, 16(2):562--572, 2007.
• 27: Z. Zhang and H. Zha. Nonlinear dimension reduction via local tangent space alignment. In Intelligent Data Engineering and Automated Learning, 477--481, 2003.
• 28: D. Zhou et al. Learning with local and global consistency. In Advances in Neural Information Processing Systems, 2003.%
• 29: D. Zhou et al. Ranking on data manifolds. In Advances in Neural Information Processing Systems, 2003.
• 30: H. Zhang Y. Zhuang and F. Wu. Cross-modal correlation learning for clustering on image-audio dataset. In ACM MM 2007.
• 31: Y. Zhuang, Y. Yang, and F. Wu. Mining semantic correlation of heterogeneous multimedia data for cross-media retrieval. IEEE Transactions on Multimedia, 10(2):221--229, 2008.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
content-based multimedia retrieval, cross-media retrieval, ranking algorithm, relevance feedback