Distance metric learning from uncertain side information with application to automated photo tagging

ABSTRACT

Automated photo tagging is essential to make massive unlabeled photos searchable by text search engines. Conventional image annotation approaches, though working reasonably well on small testbeds, are either computationally expensive or inaccurate when dealing with large-scale photo tagging. Recently, with the popularity of social networking websites, we observe a massive number of user-tagged images, referred to as "social images", that are available on the web. Unlike traditional web images, social images often contain tags and other user-generated content, which offer a new opportunity to resolve some long-standing challenges in multimedia. In this work, we aim to address the challenge of large-scale automated photo tagging by exploring the social images. We present a retrieval based approach for automated photo tagging. To tag a test image, the proposed approach first retrieves k social images that share the largest visual similarity with the test image. The tags of the test image are then derived based on the tagging of the similar images. Due to the well-known semantic gap issue, a regular Euclidean distance-based retrieval method often fails to find semantically relevant images. To address the challenge of semantic gap, we propose a novel probabilistic distance metric learning scheme that (1) automatically derives constraints from the uncertain side information, and (2) efficiently learns a distance metric from the derived constraints. We apply the proposed technique to automated photo tagging tasks based on a social image testbed with over 200,000 images crawled from Flickr. Encouraging results show that the proposed technique is effective and promising for automated photo tagging.

REFERENCES

• 1: A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning a mahalanobis metric from equivalence constraints. JMLR, 6:937--965, 2005.
• 2: J. C. Bezdek and R. J. Hathaway. Convergence of alternating optimization. Neural, Parallel Sci. Comput., 11(4):351--368, 2003.
• 3: G. Carneiro, A. B. Chan, P. Moreno, and N. Vasconcelos. Supervised learning of semantic classes for image annotation and retrieval. IEEE Tran. PAMI, pages 394--410, 2006.
• 4: G. Carneiro and N. Vasconcelos. Formulating semantic image annotation as a supervised learning problem. In IEEE CVPR, pages 163--168, 2005.
• 5: W.-Y. Chen, D. Zhang, and E. Y. Chang. Combinational collaborative filtering for personalized community recommendation. In Proc. 14th ACM SIGKDD Conference, pages 115--123, 2008.
• 6: J. V. Davis, B. Kulis, P. Jain, S. Sra, and I. S. Dhillon. Information-theoretic metric learning. In ICML, pages 209--216, 2007.
• 7: P. Duygulu, K. Barnard, J. de Freitas, and D. A. Forsyth. Object recognition as machine translation: Learning a lexicon for a fixed image vocabulary. In ECCV, pages 97--112, 2002.
• 8: J. Fan, Y. Gao, and H. Luo. Multi-level annotation of natural scenes using dominant image components and semantic concepts. In ACM Multimedia, pages 540--547, 2004.
• 9: K. Fukunaga. Introduction to Statistical Pattern Recognition. Elsevier, 1990.
• 10: A. Globerson and S. Roweis. Metric learning by collapsing classes. In NIPS'05, 2005.
• 11: J. Hayes and A. Efros. Scene completion using millions of photographs. In SIGGRAPH, pages 835--846, 2007.
• 12: X. He and R. S. Zemel. Learning hybrid models for image annotation with partially labeled data. In NIPS, pages 625--632, 2008.
• 13: C.-H. Hoi and M. R. Lyu. A novel log-based relevance feedback technique in content-based image retrieval. In Proceedings of ACM Multimedia Conference (MM2004), New York, NY, USA, 2004.
• 14: S. C. Hoi, W. Liu, and S.-F. Chang. Semi-supervised distance metric learning for collaborative image retrieval. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR2008), June 2008.
• 15: S. C. H. Hoi, W. Liu, M. R. Lyu, and W.-Y. Ma. Learning distance metrics with contextual constraints for image retrieval. In Proc. CVPR2006, New York, US, June 17-22 2006.
• 16: G. H. J. Goldberger, S. Roweis and R. Salakhutdinov. Neighbourhood components analysis. In NIPS17, 2005.
• 17: J. Jeon, V. Lavrenko, and R. Manmatha. Automatic image annotation and retrieval using cross-media relevance models. In SIGIR'03, pages 119--126, Toronto, Canada, 2003.
• 18: W. Li and M. Sun. Semi-supervised learning for image annotation based on conditional random fields. In CIVR, pages 463--472, 2006.
• 19: D. G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60:91--110, 2004.
• 20: M. Rege, M. Dong, and J. Hua. Graph theoretical framework for simultaneously integrating visual and textual features for efficient web image clustering. In WWW '08: Proceeding of the 17th international conference on World Wide Web, pages 317--326, New York, NY, USA, 2008. ACM.
• 21: B. C. Russell, A. Torralba, K. P. Murphy, and W. T. Freeman. Labelme: A database and web-based tool for image annotation. Int. J. Comput. Vision, 77(1-3):157--173, 2008.
• 22: S. Shalev-Shwartz and Y. Singer. Efficient learning of label ranking by soft projections onto polyhedra. J. Mach. Learn.Res., 7:1567--1599, 2006.
• 23: L. Si, R. Jin, S. C. H. Hoi, and M. R. Lyu. Collaborative image retrieval via regularized metric learning. ACM Multimedia Systems Journal, 12(1):34--44, 2006.
• 24: 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 Trans. PAMI, 22(12):1349--1380, 2000.
• 25: N. Snavely, S. Seitz, and R. Szeliski. Photo tourism: Exploring photo collections in 3d. In SIGGRAPH, pages 835--846, 2006.
• 26: A. Torralba, Y. Weiss, and R. Fergus. Small codes and large databases of images for object recognition. In CVPR, 2008.
• 27: C. Wang, L. Zhang, and H.-J. Zhang. Learning to reduce the semantic gap in web image retrieval and annotation. In SIGIR'08, pages 355--362, Singapore, 2008.
• 28: M. Wang, X. Zhou, and T.-S. Chua. Automatic image annotation via local multi-label classification. In ACM CIVR, pages 17--26, New York, NY, USA, 2008. ACM.
• 29: X.-J. Wang, L. Zhang, F. Jing, and W.-Y. Ma. Annosearch: Image auto-annotation by search. In CVPR'06, pages 1483--1490, 2006.
• 30: K. Weinberger, J. Blitzer, and L. Saul. Distance metric learning for large margin nearest neighbor classification. In NIPS, 2006.
• 31: L. Wu, X.-S. Hua, N. Yu, W.-Y. Ma, and S. Li. Flickr distance. In Proceeding of 16th ACM international conference on Multimedia (MM'08), pages 31--40, Vancouver, British Columbia, Canada, 2008.
• 32: E. P. Xing, A. Y. Ng, M. I. Jordan, and S. Russell. Distance metric learning with application to clustering with side-information. In NIPS2002, 2002.
• 33: R. Yan, A. Natsev, and M. Campbell. A learning-based hybrid tagging and browsing approach for efficient manual image annotation. In IEEE CVPR'08, 2008.
• 34: L. Yang, R. Jin, R. Sukthankar, and Y. Liu. An efficient algorithm for local distance metric learning. In AAAI, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement

General Terms:
Algorithms, Experimentation

Keywords:
automated photo tagging, distance metric learning, uncertain side information