Learning semantic distance from community-tagged media collection

ABSTRACT

This paper proposes a novel semantic-aware distance metric for images by mining multimedia data on the Internet, in particular, web images and their associated tags. As well known, a proper distance metric between images is a key ingredient in many realistic web image retrieval engines, as well many image understanding techniques. In this paper, we attempt to mine a novel distance metric from the web images by integrating their visual content as well as the associated user tags. Different from many existing distance metric learning algorithms which utilize the dissimilar or similar information between images pixels or features in signal level, the proposed scheme also takes the associated user-input tags into consideration. The visual content of images is also leveraged to respect an intuitive assumption that the visual similar images ought to have a smaller distance. A semi-definite programming is formulated to encode the above two aspects of criteria to learn the distance metric and we show such an optimization problem can be efficiently solved with a closed-form solution. We evaluate the proposed algorithm on two datasets. One is the benchmark Corel dataset and the other is a real-world dataset crawled from the image sharing website Flickr. By comparison with other existing distance learning algorithms, competitive results are obtained by the proposed algorithm in experiments.

REFERENCES

• 1: A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning distance functions using equivalence relations. In Proc. of International Conference on Machine Learning, 2003.
• 2: L. Bregman. The relaxation method of find the common point of convex sets and its application to the solution of problems in convex programming. In USSR Comp. Mathematics and Mathematical Physics, 1967.
• 3: T.-S. Chua, J. Tang, R. Hong, H. Li, Z. Luo, and Y. Zheng. Nus-wide: A real-world web image database from national university of singapore. In Proc. of ACM International Conference on Image and Video Retrieval, 2009.
• 4: R.L. Cilibrasi and P.M. Vitanyi. The google similarity distance. IEEE Transactions on Knowledge and Data Engineering, 19(3):370--383, March 2007.
• 5: J.V. Davis, B. Kulis, P. Jain, S. Sra, and I.S. Dhillon. Information-theoretic metric learning. In Proc. of International Conference on Machine Learning, 2007.
• 6: I.S. Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In Proc. of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001.
• 7: S.C.H. Hoi, W. Liu, and S.-F. Chang. Semi-supervised distance learning for collaborative image retrieval. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2008.
• 8: G.H.J. Goldberger, S. Roweis and R. Salakhutdinov. Neighbourhood components analysis. In Proc. of Advanced Neutral Information Processing System, 2004.
• 9: K. Jarvelin and J. Kekalainen. Ir evaluation methods for retrieving highly relevant documents. In Proc. of International ACM SIGIR Conference on Research and Development on Information Retrieval, 2000.
• 10: B. Long, X. Wu, Z. Zhang, and P.S. Yu. Unsupervised learning on k-partite graphs. In Proc. of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006.
• 11: G.-J. Qi, X.-S. Hua, Y. Rui, J. Tang, T. Mei, and H.-J. Zhang. Correlative multi-label video annotation. In Proc. of International ACM Conference on Multimedia, Augsburg, Germany, September 2007.
• 12: G.-J. Qi, X.-S. Hua, Y. Rui, J. Tang, and H.-J. Zhang. Two-dimensional multi-label active learning with an efficient online adaptation model for image classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008.
• 13: M. Rege, M. Dong, and J. Hua. Graph theoretical framework for simultaneously integrating visual and textual features for efficient web image clustering. In Proc. of International Conference on World Wide Web, 2008.
• 14: M. Schultz and T. Joachims. Learning a distance metric from relative comparisons. In Proc. of Advanced Neutral Information Processing System, 2004.
• 15: J. Shawe-Taylor and N. Cristianini. Kernel Methods for Pattern Recognition. Cambridge University Press, 2004.
• 16: L. Si, R. Jin, S.C. Hoi, and M.R. Lyu. Collaborative image retrieval via regularized metric learning. ACM Multimedia Systems Journal, 2006.
• 17: A.W.M. Smeulders, M. Worring, S. Santini, A. Gupta, and R. Jain. Content-based image retrieval at the end of the early years. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000.
• 18: I.W. Tsang, P.-M. Cheung, and J.T. Kwok. Kernel relevant component analysis for distance metric learning. In Proc. of International Joint Conference on Neural Networks, 2005.
• 19: C. Wang, L. Zhang, and H.-J. Zhang. Learning to reduce the semantic gap in web image retrieval and annotation. In Proc. of the 31st Annual International ACM SIGIR Conference on Research and Development on Information Retrieval, Singapore, July 2008.
• 20: X.-J. Wang, L. Zhang, F. Jing, and W.-Y. Ma. Annosearch: Image auto-annotation by search. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2006.
• 21: K.Q. Weinberger, J. Blitzer, and L.K. Saul. Distance metric learning for large margin nearest neighbor classification. In Proc. of NIPS, 2005.
• 22: Q. Weinberger, M. Slaney, and R.V. Zwol. Resolving tag ambiguity. In Proc. of International ACM Conference on Multimedia, 2008.
• 23: E.P. Xing, A.Y. Ng, M.I. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In Proc. of Advanced Neutral Information Processing System, 2003.
• 24: J. Yu and Q. Tian. Semantic subspace projection and its application in image retrieval. IEEE Transactions on Circuits and Systems for Video Technology, 18(4):544--548, April 2008.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms

Keywords:
distance metric learning, web image search