Modeling video hyperlinks with hypergraph for web video reranking

ABSTRACT

In this paper, we investigate a novel approach of exploiting visual-duplicates for web video reranking using hypergraph. Current graph-based reranking approaches consider mainly the pair-wise linking of keyframes and ignore reliability issues that are inherent in such representation. We exploit higher order relation to overcome the issues of missing links in visual-duplicate keyframes and in addition identify the latent relationships among keyframes. Based on hypergraph, we consider two groups of video threads: visual near-duplicate threads and story threads, to hyperlink web videos and describe the higher order information existing in video content. To facilitate reranking using random walk algorithm, the hypergraph is converted to a star-like graph using star expansion algorithm. Experiments on a dataset of 12,790 web videos show that hypergraph reranking can improve web video retrieval up to 45% over the initial ranked result by the video sharing websites and 8.3% over the pair-wise based graph reranking in mean average precision (MAP).

REFERENCES

• 1: Sameer Agarwal , Kristin Branson , Serge Belongie, Higher order learning with graphs, Proceedings of the 23rd international conference on Machine learning, p.17-24, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143847]
• 2: Sameer Agarwal , Jongwoo Lim , Lihi Zelnik-Manor , Pietro Perona , David Kriegman , Serge Belongie, Beyond Pairwise Clustering, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.838-845, June 20-26, 2005 [doi>10.1109/CVPR.2005.89]
• 3: T.-S. Chua and et. al. Trecvid 2004 search and feature extraction task by NUS PRIS. In TRECVID Workshop, 2004.
• 4: 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]
• 5: Winston H. Hsu , Lyndon S. Kennedy , Shih-Fu Chang, Video search reranking through random walk over document-level context graph, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291446]
• 6: Lyndon S. Kennedy , Shih-Fu Chang, A reranking approach for context-based concept fusion in video indexing and retrieval, Proceedings of the 6th ACM international conference on Image and video retrieval, p.333-340, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282331]
• 7: Jingjing Liu , Wei Lai , Xian-Sheng Hua , Yalou Huang , Shipeng Li, Video search re-ranking via multi-graph propagation, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291279]
• 8: L. Page, S. Brin, L. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 9: Alan F. Smeaton , Paul Over , Wessel Kraaij, Evaluation campaigns and TRECVid, Proceedings of the 8th ACM international workshop on Multimedia information retrieval, October 26-27, 2006, Santa Barbara, California, USA [doi>10.1145/1178677.1178722]
• 10: Wikipedia. http://en.wikipedia.org/wiki/youtube.
• 11: Xiao Wu , Alexander G. Hauptmann , Chong-Wah Ngo, Practical elimination of near-duplicates from web video search, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291280]
• 12: R. Yan and A. G. Hauptmann. Multimedia search with pseudo-relevance feedback. In CIVR, 2003.
• 13: Y. H. Yang and W. H. Hsu. Video search reranking via online ordinal reranking. In ICME, 2008.
• 14: W. L. Zhao, C.-W. Ngo, H.-K. Tan, and X. Wu. Near-duplicate keyframe identification with interest point matching and pattern learning. In IEEE Trans. on Multimedia, volume 9, pages 1037--1048, Aug 2006.
• 15: J. Y. Zien, M. D. F. Schlag, and P. K. Chan. Multi-level spectral hypergraph partitioning with arbitrary vertex sizes. In IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, volume 18, pages 1389--1399, 1999.

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:
higher order relation, hypergraph, web video reranking