Automatic multimedia cross-modal correlation discovery

ABSTRACT

Given an image (or video clip, or audio song), how do we automatically assign keywords to it? The general problem is to find correlations across the media in a collection of multimedia objects like video clips, with colors, and/or motion, and/or audio, and/or text scripts. We propose a novel, graph-based approach, "MMG", to discover such cross-modal correlations.Our "MMG" method requires no tuning, no clustering, no user-determined constants; it can be applied to any multimedia collection, as long as we have a similarity function for each medium; and it scales linearly with the database size. We report auto-captioning experiments on the "standard" Corel image database of 680 MB, where it outperforms domain specific, fine-tuned methods by up to 10 percentage points in captioning accuracy (50% relative improvement).

REFERENCES

• 1: A. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the world wide web. Nature, 401:130--131, 1999.
• 2: Kobus Barnard , Pinar Duygulu , David Forsyth , Nando de Freitas , David M. Blei , Michael I. Jordan, Matching words and pictures, The Journal of Machine Learning Research, 3, 3/1/2003
• 3: K. Barnard, P. Duygulu, and D. A. Forsyth. Clustering art. In IEEE Conf. on Computer Vision and Pattern Recognition, volume 2, pages 434--441, 2001.
• 4: K. Barnard and D. A. Forsyth. Learning the semantics of words and pictures. In Int. Conf. on Computer Vision, pages 408--15, 2001.
• 5: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 6: P. G. Doyle and J. L. Snell. Random Walks and Electric Networks. Kluwer.
• 7: P. Duygulu , Kobus Barnard , J. F. G. de Freitas , David A. Forsyth, Object Recognition as Machine Translation: Learning a Lexicon for a Fixed Image Vocabulary, Proceedings of the 7th European Conference on Computer Vision-Part IV, p.97-112, May 28-31, 2002
• 8: Christos Faloutsos, Searching Multimedia Databases by Content, Kluwer Academic Publishers, Norwell, MA, 1996
• 9: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 10: J. Jeon , V. Lavrenko , R. Manmatha, Automatic image annotation and retrieval using cross-media relevance models, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860459]
• 11: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 12: Tamara G. Kolda , Dianne P. O'Leary, A semidiscrete matrix decomposition for latent semantic indexing information retrieval, ACM Transactions on Information Systems (TOIS), v.16 n.4, p.322-346, Oct. 1998 [doi>10.1145/291128.291131]
• 13: Jia Li , James Z. Wang, Automatic Linguistic Indexing of Pictures by a Statistical Modeling Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.9, p.1075-1088, September 2003 [doi>10.1109/TPAMI.2003.1227984]
• 14: L. Lovasz. Random walks on graphs: A survey. Combinatorics, Paul Erdos is Eighty, 2:353--398, 1996.
• 15: Oded Maron , Aparna Lakshmi Ratan, Multiple-Instance Learning for Natural Scene Classification, Proceedings of the Fifteenth International Conference on Machine Learning, p.341-349, July 24-27, 1998
• 16: Y. Mori, H. Takahashi, and R. Oka. Image-to-word transformation based on dividing and vector quantizing images with words. In First International Workshop on Multimedia Intelligent Storage and Retrieval Management, 1999.
• 17: C. R. Palmer and C. Faloutsos. Electricity based external similarity of categorical attributes. In PAKDD 2003, May 2003.
• 18: Jia-Yu Pan , Christos Faloutsos, VideoCube: A Novel Tool for Video Mining and Classification, Proceedings of the 5th International Conference on Asian Digital Libraries: Digital Libraries: People, Knowledge, and Technology, p.194-205, December 11-14, 2002
• 19: Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275505]
• 20: Shin'ichi Satoh , Yuichi Nakamura , Takeo Kanade, Name-It: Naming and Detecting Faces in News Videos, IEEE MultiMedia, v.6 n.1, p.22-35, January 1999 [doi>10.1109/93.752960 ]
• 21: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 22: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688 ]
• 23: Taher Haveliwala, S. Kamvar and G. Jeh. An analytical comparison of approaches to personalizing PageRank. Technical report, Stanford University, 2003.
• 24: George Tzanetakis , Perry Cook, MARSYAS: a framework for audio analysis, Organised Sound, v.4 n.3, p.169-175, December 1999 [doi>10.1017/S1355771800003071]
• 25: Howard D. Wactlar , Michael G. Christel , Yihong Gong , Alexander G. Hauptmann, Lessons Learned from Building a Terabyte Digital Video Library, Computer, v.32 n.2, p.66-73, February 1999 [doi>10.1109/2.745722 ]
• 26: L. Wenyin, S. Dumais, Y. Sun, H. Zhang, M. Czerwinski, and B. Field. Semi-automatic image annotation. In INTERACT2001, 8th IFIP TC.13 Conference on Human-Computer Interaction, Tokyo, Japan July 9-13, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Design, Experimentation

Keywords:
automatic image captioning, cross-modal correlation, graph-based model