Shanmukhappa Angadi; Vilas Naik

Dynamic Summarization of Video Using Minimum Edge Weight Matching in Bipartite Graphs

Full Text (PDF, 856KB), PP.9-18

Views: 0 Downloads: 0

Author(s)

Shanmukhappa Angadi ^1,* Vilas Naik ²

1. Department of Computer Science and Engineering,Centre for Post Graduate Studies, VTU. Belagavi, India

2. Department of Computer science and Engineering Basaveshwar Engineering College, Bagalkot, India.

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2016.03.02

Received: 6 Oct. 2015 / Revised: 25 Nov. 2015 / Accepted: 20 Jan. 2016 / Published: 8 Mar. 2016

Index Terms

Dynamic summarization, Graph representation of videos, Minimum edge weight matching, Hungarian Algorithm, Bipartite graph

Abstract

To select the long-running videos from online archives and other collections, the users would like to browse, or skim through quickly to get a hint on the semantic content of the videos. Video summarization addresses this problem by providing a short video summary of a full-length video. An ideal video summary would include all the important segments of the video and remain short in length. The problem of summarization is extremely challenging and has been a widely pursued subject of recent research. There are many algorithms presented in literature for video summarization and they represent visual information of video in concise form. Dynamic summaries are constructed with collection of key frames or some smaller segments extracted from video and is presented in the form of small video clip. This paper describes an algorithm for constructing the dynamic summary of a video by modeling every 40 consecutive frames of video as a bipartite graph. The method considers every 20 consecutive frames from video as one set and next 20 consecutive frames as second set of bipartite graph nodes with frames of the video representing nodes of the graph and edges connecting nodes denoting the relation between frames and edge weight depicting the mutual information between frames. Then the minimum edge weight maximal matching in every bipartite graph (a set of pair wise non-adjacent edges) is found using Hungarian method. The frames from the matchings which are represented by the nodes connected by the edges with weight below some empirically defined threshold and two neighbor frames are taken as representative frames to construct the summary. The results of the experiments conducted on data set containing sports videos taken from YOUTUBE and videos of TRECVID MED 2011 dataset have demonstrated the satisfactory average values of performance parameters, namely Informativeness value of 94 % and Satisfaction value of 92 %. These values and duration (MSD) of summaries reveal that the summaries constructed are significantly concise and highly informative and provide highly acceptable dynamic summary of the videos.

Cite This Paper

Shanmukhappa Angadi, Vilas Naik,"Dynamic Summarization of Video Using Minimum Edge Weight Matching in Bipartite Graphs", International Journal of Image, Graphics and Signal Processing(IJIGSP), Vol.8, No.3, pp.9-18, 2016. DOI: 10.5815/ijigsp.2016.03.02

Reference

[1]Boreczky JS, Rowe LA 1996 Comparison of video shot boundary detection techniques. Proc Int Conf Storage Retr Still Image Video Databases 5(2):170–179.

[2]Behzard S, Gibbon DS 1995 Automatic generation of pictorial transcripts of video programs. Proc SPIE Multimedia Computer Networking 2417:512–518.

[3]Y. Pritch, A. Rav-Acha, and S. Peleg,"Nonchronological Video Synopsis and Indexing," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 11, pp. 1971-1984, 2008.

[4]Won-il hwang, pyung-jun lee, bong-kyung chun, dong-sung ryu, hwan-gue cho 2006 "cinema comics : cartoon generation from video stream"in GRAPP 2006 - COMPUTER GRAPHICS THEORY AND APPLICATIONS.

[5]J. Kavitha, P. Arockia Jansi Rani 2015, "Design of a Video Summarization Scheme in the Wavelet Domain Using Statistical Feature Extraction" , International Journal of Image, Graphics and Signal Processing, 2015, Volume 4, PP 60-67.

[6]Yue Gao Wei-Bo Wang· Jun-Hai Yong · He-Jin Gu 2009 "Dynamic video summarization using two-level edundancy detection" in Spinger Multimed Tools Appl (2009) 42:233–250.

[7]Yongliang Xiao, Limin Xia,2010, "Key Frame Extraction Based on Connectivity Clustering" in proceedings of Second International Workshop on Education Technology and Computer Science (ETCS), volume 1 pp 174 – 177.

[8]A.M. Ferman and A.M. Tekalp, 1998"Efficient Filtering and Clustering Methods for Temporal Video Representation and Visual Summarization", J. Visual Com. & Image Rep., vol. 9, pp.336-351.

[9]JeongKyu Lee JungHwan Oh Sae Hwang,2005, "Scenario based Dynamic Video Abstractions using Graph Matching" in ACMMM 05 , November 6–11, 2005, Singapore.

[10]Girgensohn and j. Boreczky, 2000 "Time-Constrained Keyframe Selection Technique," multimedia. Tools & appl, v.11, pp.347-358.

[11]Shi Lu ; Dept. Of Comput. Sci. & Eng., Chinese Univ. Of Hong Kong, China ; Lyu, M.R.; King, I. 2004," Video Summarization By Spatial-Temporal Graph Optimization" Published in: , 2004. ISCAS '04. Proceedings Of The 2004 International Symposium On Circuits And Systems.

[12]Yuxin Peng Chong-Wah Ngo 2005 "Hot Event Detection and Summarization by Graph Modeling and Matching" CIVR 2005, LNCS 3568, pp. 257 – 266, 2005. © Springer-Verlag Berlin Heidelberg 2005.

[13]Rong Pan , Yumin Tian , Zhong Wang 2010 Key-frame extraction based on clustering in proceedings of IEEE International Conference on Progress in Informatics and Computing (ICPIC), 10-12,Dec.2010,Volume:2pp:867-871 .

[14]Besiris, D. Fotopoulou, F. ; Economou, G.; Fotopoulos, S. 2008Video Summarization By A Graph-Theoretic FCM Based Algorithm in Proceedings Of 15th International Conference on Systems, Signals And Image Processing, 2008. IWSSIP 2008.

[15]Yue Gao, Wei-Bo Wang, Jun-Hai Yong,He-Jin Gu 2008 Dynamic Video Summarization Using Two-Level Redundancy Detection Multimedia Tools and Applications April 2009, Volume 42, Issue 2, pp 233-250.

[16]Chong-Wah Ngo, Yu-Fei Ma, Hong-Jiang Zhang, 2005 "Video Summarization And Scene Detection By Graph Modeling" Ieee Transactions On Circuits And Systems For Video Technology, Vol. 15, No. 2, February 2005.

[17]D. Besiris a. Makedonas 2009 "combining graph connectivity & dominant set clustering for video summarization"Journal of multimedia tools and applications volume 44 issue 2, september 2009 pages 161 – 186.

[18]Michel X.Goemans 2009 , "Lecture notes on bipartite matching Combinatorial Optimization" Massachusetts Institute of Technology .

[19]T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley and Sons, New York, 2006.

[20]R.E. Burkard, M. Dell'Amico, S. Martello: Assignment Problems SIAM, Philadelphia (PA.) 2012. ISBN 978-1- 61197-222-1 .

[21]Tasorn Sornnarong 2014 "Dynamic matching in crowdsourcing platform" Thesis submitted to School of Computer and Communication Sciences Swiss Federal Institute of Technology Lausanne, EPFL .

[22]H.W. Kuhn, On the origin of the Hungarian Method, History of mathematical programming; a collection of personal reminiscences (J.K. Lenstra, A.H.G. Rinnooy Kan, and A. Schrijver, eds.), North Holland, Amsterdam, 1991, pp. 77–81.

[23]Harold W. Kuhn The Hungarian Method for the Assignment Problem 2010 50 Years of Integer Programming 1958-2008 2010, pp 29-47.

[24]Stina Westman, 2011 Evaluation of visual video summaries: user-supplied constructsand descriptions, in the Proceedings of the 14th European Conference on Digital Libraries (ECDL 2010).

International Journal of Image, Graphics and Signal Processing (IJIGSP)