Abstract
This paper presents a novel optimization-based approach for video key frame selection. We define key frames to be a temporally ordered subsequence of the original video sequence, and the optimal k key frames are the subsequence of length k that optimizes an energy function we define on all subsequences. These optimal key subsequences form a hierarchy, with one such subsequence for every k less than the length of the video n, and this hierarchy can be retrieved all at once using a dynamic programming process with polynomial (On 3) computation time. To further reduce computation, an approximate solution based on a greedy algorithm can compute the key frame hierarchy in O(n·log(n)). We also present a hybrid method, which flexibly captures the virtues of both approaches. Our empirical comparisons between the optimal and greedy solutions indicate their results are very close. We show that the greedy algorithm is more appropriate for video streaming and network applications where compression ratios may change dynamically, and provide a method to compute the appropriate times to advance through key frames during video playback of the compressed stream. Additionally, we exploit the results of the greedy algorithm to devise an interactive video content browser. To quantify our algorithms’ effectiveness, we propose a new evaluation measure, called “well-distributed” key frames. Our experimental results on several videos show that both the optimal and the greedy algorithms outperform several popular existing algorithms in terms of summarization quality, computational time, and guaranteed convergence.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Edoardo Ardizzone and Mohand-Said Hacid. A Semantic Modeling Approach for Video Retrieval by Content. In IEEE International Conference on Multimedia Computing and Systems, pages 158–162, 1999.
J. Boreczky and L. Rowe. Comparison of Video Shot Boundary Detection Techniques. In Storage and Retrieval for Still Image and Video Databases, pages 170–179, 1996.
H. S. Chang, S. Sull, and Sang Uk Lee. Efficient Video Indexing Scheme for Content-based Retrieval. In IEEE Trans. on Circuits and Systems for Video Technology, pages 1269–1279, Dec. 1999.
Tat-Seng Chua and Li-Qun Ruan. A Video Retrieval and Sequencing System. In ACM Transactions on Information Systems, pages 373–407, Oct. 1995.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2001.
Madirakshi Das and Shih-Ping Liou. A New Hybrid Approach to Video Organization for Content-Based Indexing. In IEEE International Conference on Multimedia Computing and Systems, 1998.
Andreas Girgensohn and John Boreczky. Time-Constrained Keyframe Selection Technique. In IEEE International Conference on Multimedia Computing and Systems, pages 756–761, 1999.
I.Busse, B. Deffner, and H. Schulzrinne. Dynamic QoS Control of Multimedia Applications based on RTP. In Computer Communications, Jan. 1996.
F. Idris and S. Panchanathan. Review of Image and Video Indexing Techniques. In Journal of Visual Communication and Image Representation, pages 146–166, June 1997.
Jia-Ling Koh, Chin-Sung Lee, and Arbee L.P. Chen. Semantic Video Model for Content-based Retrieval. In IEEE International Conference on Multimedia Computing and Systems, pages 472–478, 1999.
M. K. Mandal, F. Idris, and S. Panchanathan. A Critical evaluation of image and video indexing techniques in compressed domain. In Image and Vision Computing, pages 513–529, 1999.
Myung-Ki Shin and Jin-Ho Hahm. Applying QoS Guaranteed Multicast Audio and Video to the Web. In IEEE International Conference on Multimedia Computing and Systems, pages 26–30, 1999.
Hugh M. Smith, Matt W. Mutka, and Eric Torng. Bandwidth Allocation for Layered Multicasted Video. In IEEE International Conference on Multimedia Computing and Systems, pages 232–237, 1999.
M. Smith and T. Kanade. Video Skimming and Characterization through the Combination of Image and Language Understanding. In Proceedings of the IEEE International Worksop on Content-based Access of Image and Video Databases (ICCV’98), 1998.
M. Yeung and B. Liu. Efficient Matching and Clustering of Video Shots. In Proceedings of the International Conference on Image Processing, pages 338–341, 1995.
M. Yeung and B.L. Yeo. Time-Constrained Clustering for Segmentation of Video into Story Units. In International Conference on Pattern Recognition, pages 375–380, 1996.
Yueting Zhuang, Yong Rui, Thomas S. Huang, and Sharad Mehrotra. Adaptive Key Frame Extraction Using Unsupervised Clustering. In IEEE International Conference on Image Processing, pages 866–870, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, T., Kender, J.R. (2002). Optimization Algorithms for the Selection of Key Frame Sequences of Variable Length. In: Heyden, A., Sparr, G., Nielsen, M., Johansen, P. (eds) Computer Vision — ECCV 2002. ECCV 2002. Lecture Notes in Computer Science, vol 2353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47979-1_27
Download citation
DOI: https://doi.org/10.1007/3-540-47979-1_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43748-2
Online ISBN: 978-3-540-47979-6
eBook Packages: Springer Book Archive