Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Multimedia search over distributed sources often result in recurrent images or videos which are manifested beyond the textual modality. To exploit such contextual patterns and keep the simplicity of the keyword-based search, we propose novel reranking methods to leverage the recurrent patterns to improve the initial text search results. The approach, context reranking, is formulated as a random walk problem along the context graph, where video stories are nodes and the edges between them are weighted by multimodal contextual similarities. The random walk is biased with the preference towards stories with higher initial text search scores - a principled way to consider both initial text search results and their implicit contextual relationships. When evaluated on TRECVID 2005 video benchmark, the proposed approach can improve retrieval on the average up to 32% relative to the baseline text search method in terms of story-level Mean Average Precision. In the people-related queries, which usually have recurrent coverage across news sources, we can have up to 40% relative improvement. Most of all, the proposed method does not require any additional input from users (e.g., example images), or complex search models for special queries (e.g., named person search).

REFERENCES

• 1: TRECVID: TREC Video Retrieval Evaluation. http://www-nlpir.nist.gov/projects/trecvid/.
• 2: John Battelle, The Search: How Google and Its Rivals Rewrote the Rules of Business and Transformed Our Culture, Portfolio Trade, 2006
• 3: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 4: M. Campbell and et al. IBM Research TRECVID-2006 Video Retrieval System. In NIST TRECVID workshop, Gaithersburg, MD, November 2006.
• 5: J. G. Carbonell and et al. Translingual information retrieval: A comparative evaluation. In International Joint Conference on Artificial Intelligence, 1997.
• 6: S.-F. Chang and et al. Columbia University TRECVID-2006 video search and high-level feature extraction. In TRECVID Workshop, Washington DC, 2006.
• 7: T.-S. Chua and et. al. TRECVID 2004 search and feature extraction task by NUS PRIS. In TRECVID Workshop, Washington DC, 2004.
• 8: Anind K. Dey, Understanding and Using Context, Personal and Ubiquitous Computing, v.5 n.1, p.4-7, February 2001 [doi>10.1007/s007790170019]
• 9: K. M. Donald and A. F. Smeaton. A comparison of score, rank and probability-based fusion methods for video shot retrieval. In International Conference on Content-based Image and Video Retrieval (CIVR), Singapore, 2005.
• 10: R. Fergus, P. Perona, and A. Zisserman. A visual category filter for google images. In Proceedings of the 8th European Conference on Computer Vision, Prague, Czech Republic, May 2004.
• 11: Alexander G. Hauptmann , Michael G. Christel, Successful approaches in the TREC video retrieval evaluations, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027681]
• 12: A. G. Hauptmann and et al. Multi-Lingual Broadcast News Retrieval. In NIST TRECVID workshop, Gaithersburg, MD, November 2006.
• 13: Xiaofei He , Wei-Ying Ma , Hongjiang Zhang, Imagerank: spectral techniques for structural analysis of image database, Proceedings of the 2003 International Conference on Multimedia and Expo, p.25-28, July 06-09, 2003
• 14: W. Hsu, L. Kennedy, S.-F. Chang, M. Franz, and J. Smith. Columbia-IBM news video story segmentation in trecvid 2004. Technical Report ADVENT #207-2005-3, Columbia University, 2005.
• 15: W. H. Hsu and S.-F. Chang. Topic tracking across broadcast news videos with visual duplicates and semantic concepts. In International Conference on Image Processing (ICIP), Atlanta, GA, USA, 2006.
• 16: Winston H. Hsu , Lyndon S. Kennedy , Shih-Fu Chang, Video search reranking via information bottleneck principle, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA [doi>10.1145/1180639.1180654]
• 17: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 18: Sepandar D. Kamvar , Taher H. Haveliwala , Christopher D. Manning , Gene H. Golub, Extrapolation methods for accelerating PageRank computations, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775190]
• 19: Amy N. Langville , Carl D. Meyer, A Survey of Eigenvector Methods for Web Information Retrieval, SIAM Review, v.47 n.1, p.135-161, 2005 [doi>10.1137/S0036144503424786]
• 20: M. Meila and J. Shi. Learning segmentation with random walk. In Neural Information Processing Systems Conference (NIPS), pages 873--879, 2001.
• 21: Apostol (Paul) Natsev , Milind R. Naphade , Jelena TešiĆ, Learning the semantics of multimedia queries and concepts from a small number of examples, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101288]
• 22: A. Y. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Neural Information Processing Systems Conference (NIPS), 2002.
• 23: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 24: J.-Y. Pan, H.-J. Yang, C. Faloutsos, and P. Duygulu. Gcap: Graph-based automatic image captioning. In International Workshop on Multimedia Data and Document Engineering, Washington, DC, USA, 2004.
• 25: 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]
• 26: Noam Slonim , Naftali Tishby, Document clustering using word clusters via the information bottleneck method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.208-215, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345578]
• 27: C. G. M. Snoek and et. al. The MediaMill TRECVID2006 Semantic Video Search Engine. In NIST TRECVID workshop, Gaithersburg, MD, Nov. 2006.
• 28: R. Yan, A. Hauptmann, and R. Jin. Multimedia search with pseudo-relevance feedback. In International Conference on Image and Video Retrieval, Urbana-Champaign, IL, USA, 2003.
• 29: A. Yanagawa, S.-F. Chang, L. Kennedy, and W. Hsu. Columbia university's baseline detectors for 374 LSCOM semantic visual concepts. Technical Report ADVENT #222-2006-8, Columbia University, 2007.
• 30: Yiming Yang , Jaime G. Carbonell , Ralf D. Brown , Thomas Pierce , Brian T. Archibald , Xin Liu, Learning Approaches for Detecting and Tracking News Events, IEEE Intelligent Systems, v.14 n.4, p.32-43, July 1999 [doi>10.1109/5254.784083]
• 31: Dong-Qing Zhang , Shih-Fu Chang, Detecting image near-duplicate by stochastic attributed relational graph matching with learning, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027730]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
multimodal fusion, power method, video search