Clip based video summarization and ranking

ABSTRACT

In this paper, we present a new algorithm for video clip summarization and ranking, which is mainly based on a clip based video similarity measure and the affinity propagation clustering (AP) algorithm. We propose a proportional max-weighted bipartite matching algorithm for clip similarity measure. This method first generates a basic frame set and a corresponding proportion value set from each clip. Then it models two clips as a weighted bipartite graph, where the weight values are determined by both the direct frame similarities and the proportion values. Then the max-weighted bipartite matching is employed to measure the similarity between two clips. This method achieves good retrieval performance when the length of two clips varies greatly. With these clip similarities, clips are clustered using affinity propagation. The clips in one cluster generally describe the same video event. Video ranking is based on the cluster size and the average information entropy of each event. Experimental results are given to illustrate the proposed algorithm.

REFERENCES

• 1: J. Calic, D. Gibson, and N. Campbell. Efficient layout of comic-like video summaries. IEEE Transactions on Circuits and Systems for Video Technology, 17(7):931 -- 936, 2007.
• 2: B. Frey and D. Dueck. Clustering by passing messages between data points. Science, 315:972 -- 976, 2007.
• 3: J. Gauch and A. Shivadas. Identification of new commercials using repeated video sequence detection. In Proceeding of IEEE International Conference on Image Processing, pages 1252 -- 1255, 2005.
• 4: S. Guimaraes and R. Kelly. Counting of video clip repetitions using a modified bmh algorithm: Preliminary results. In Proceeding of IEEE International Conference on Multimedia Expo, pages 1065 -- 1068, 2006.
• 5: A. Hanjalic. Adaptive extraction of highlights from a sport video based on excitement modeling. IEEE Transactions on Multimedia, 7(6):1114--1122, 2005.
• 6: Y. Ho, C. Lin, J. Chen, and H. Liao. Fast coarse-to-fine video retrieval using shot-level spatio-temporal statistics. IEEE Transactions on Circuits and Systems for Video Technology, 16(5):642 -- 648, 2006.
• 7: Anil K. Jain , Aditya Vailaya , Xiong Wei, Query by video clip, Multimedia Systems, v.7 n.5, p.369-384, September 1999 [doi>10.1007/s005300050139]
• 8: A. Joly, C. Frelicot, and O. Buisson. Content-based video copy detection in large data base. In Proceeding of IEEE International Conference on Image Processing, pages 505 -- 508, 2005.
• 9: S. Kim and R. Park. An efficient algorithm for video sequence matching using the modified hausdorff distance and the directed divergence. IEEE Transactions on Circuits and Systems for Video Technology, 12(7):592 -- 596, 2002.
• 10: Young-tae Kim , Tat-Seng Chua, Retrieval of News Video Using Video Sequence Matching, Proceedings of the 11th International Multimedia Modelling Conference, p.68-75, January 12-14, 2005 [doi>10.1109/MMMC.2005.63]
• 11: H. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2:83 -- 97, 1955.
• 12: Victor Kulesh , Valery A. Petrushin , Ishwar K. Sethi, Video Clip Recognition Using Joint Audio-Visual Processing Model, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 1, p.10500, August 11-15, 2002
• 13: JeongKyu Lee , JungHwan Oh , Sae Hwang, Scenario based dynamic video abstractions using graph matching, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101328]
• 14: Z. Li, G. Schuster, and A. Katsaggelos. Rate-distortion optimal video summary generation. IEEE Transactions on Image Processing, 14(10):1550 -- 1560, 2005.
• 15: T. Liu and R. Katpelly. Content-adaptive video summarization combining queueing and clustering. In Proceeding of IEEE International Conference on Image Processing, pages 145 -- 148, 2006.
• 16: C. Ngo, Y. Ma, and H. Zhang. Video summarization and scene detection by graph modeling. IEEE Transactions on Circuits and Systems for Video Technology, 15(2):296 -- 305, 2005.
• 17: Y. Peng and C. Ngo. Hot event detection and summarization by graph modeling and matching. Lecture Notes in Computer Science, 3568:257 -- 266, 2005.
• 18: Y. Peng and C. Ngo. Clip-based similarity measure for query-dependent clip retrieval and video summarization. IEEE Transactions on Circuits and Systems for Video Technology, 16(5):612 -- 627, 2006.
• 19: Fred Rothganger , Svetlana Lazebnik , Cordelia Schmid , Jean Ponce, Segmenting, Modeling, and Matching Video Clips Containing Multiple Moving Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.3, p.477-491, March 2007 [doi>10.1109/TPAMI.2007.57]
• 20: Peter Sand , Seth Teller, Video matching, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 21: Changsheng Xu , Xi Shao , Namunu C. Maddage , Mohan S. Kankanhalli, Automatic music video summarization based on audio-visual-text analysis and alignment, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076097]
• 22: Junsong Yuan , Qi Tian , Surendra Ranganath, Fast and Robust Search Method for Short Video Clips from Large Video Collection, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 3, p.866-869, August 23-26, 2004 [doi>10.1109/ICPR.2004.373]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Experimentation, Performance

Keywords:
clip similarity, ranking, summarization, video analysis