Video rushes summarization using spectral clustering and sequence alignment

ABSTRACT

In this paper we describe a system for video rushes summarization. The basic problems of rushes videos are three. First, the presence of useless frames such as colorbars, monochrome frames and frames containing clapboards. Second, the repetition of similar segments produced from multiple takes of the same scene and finally, the efficient representation of the original video in the video summary. In the method we proposed herein, the input video is segmented into shots. Then, colorbars and monochrome frames are removed by checking their edge direction histogram, whereas frames containing clapboards are removed by checking their SIFT descriptors. Next, an enhanced spectral clustering algorithm that both estimates the number of clusters and employs the fast global k-means algorithm in the clustering stage after the eigenvector computation of the similarity matrix is used to extract the key-frames of each shot, to efficiently represent shot content. Similar shots are clustered in one group by comparing their key-frames using a sequence alignment algorithm. Each group is represented from the shot with the largest duration and the final video summary is generated by concatenating frames around the key-frames of each shot. Experiments on TRECVID 2008 Test Data indicate that our method exhibits good performance.

REFERENCES

• 1: A. Likas, N. Vlassis, and J. Verbeek. The global k-means clustering algorithm. Pattern Recognition, 36(6):451--461, Feb 2003.
• 2: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 3: B. Manjunath, J.-R. Ohm, V. Vasudevan, and A. Yamada. Color and texture descriptors. IEEE Transactions on Circuits and Systems for Video Technology, 11(6):703--715, Jun 2001.
• 4: A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm, 2001.
• 5: Paul Over , Alan F. Smeaton , George Awad, The trecvid 2008 BBC rushes summarization evaluation, Proceedings of the 2nd ACM TRECVid Video Summarization Workshop, p.1-20, October 31-31, 2008, Vancouver, British Columbia, Canada [doi>10.1145/1463563.1463564]
• 6: T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147:195--197, 1981.
• 7: E. P. Xing and M. I. Jordan. On semide definite relaxation for normalized k-cut and connections to spectral clustering. Technical Report UCB/CSD--03--1265, EECS Department, University of California, Berkeley, Jun 2003.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Experimentation, Performance

Keywords:
global k-means, key-frame extraction, spectral clustering, video summarization