No Access

A NOVEL TECHNIQUE FOR SIZE CONSTRAINED VIDEO STORYBOARD GENERATION USING STATISTICAL RUN TEST AND SPANNING TREE

PARTHA PRATIM MOHANTA

Electronics and Communication Sciences Unit, Indian Statistical Institute, 203, B. T. Road, Kolkata 700108, India

Search for more papers by this author

SANJOY KUMAR SAHA

Computer Science and Engineering Department, Jadavpur University, Jadavpur, Kolkata 700032, India

Search for more papers by this author

, and

BHABATOSH CHANDA

Electronics and Communication Sciences Unit, Indian Statistical Institute, 203, B. T. Road, Kolkata 700108, India

Search for more papers by this author

https://doi.org/10.1142/S0219467813500010Cited by:5 (Source: Crossref)

Abstract

Storyboard consisting of key-frames is a popular format of video summarization as it helps in efficient indexing, browsing and partial or complete retrieval of video. In this paper, we have presented a size constrained storyboard generation scheme. Given the shots i.e. the output of the video segmentation process, the method has two major steps: extraction of appropriate key-frame(s) from each shot and finally, selection of a specified number of key-frames from the set thus obtained. The set of selected key-frames should retain the variation in visual content originally possessed by the video. The number of key-frames or representative frames in a shot may vary depending on the variation in its visual content. Thus, automatic selection of suitable number of representative frames from a shot still remains a challenge. In this work, we propose a novel scheme for detecting the sub-shots, having consistent visual content, from a shot using Wald–Wolfowitz runs test. Then from each sub-shot a frame rendering the highest fidelity is extracted as key-frame. Finally, a spanning tree based novel method is proposed to select a subset of key-frames having specific cardinality. Chronological arrangement of such frames generates the size constrained storyboard. Experimental result and comparative study show that the scheme works satisfactorily for a wide variety of shots. Moreover, the proposed technique rectifies mis-detection error, if any, incurred in video segmentation process. Similarly, though not implemented, the proposed hypothesis test has ability to rectify the false-alarm in shot detection if it is applied on pair of adjacent shots.

Keywords:

Remember to check out the Check out our Most Cited Articles!
Check out these titles on Image Analysis

References

G. Ciocca and R. Schettini, Real Time IP 1, 69 (2006). Web of Science, Google Scholar
Y. Rui, T. S. Huang and S. Mehrotra, Exploring video structures beyond the shots, Proc. IEEE Conf. on Multimedia Computing and Systems (1998) pp. 237–240. Google Scholar
Y. Tonomuraet al., Videomap and video space icon: Tools for automatizing video content, Proc. ACM INTERCHI (1993) pp. 131–141. Google Scholar
H. Ueda, T. Miyatake and S. Yoshizawa, An interactive natural-motion-picture dedicated multimedia authoring system, Proc. ACM CHI Conf. (1991) pp. 343–350. Google Scholar
A. Pentlandet al., IEEE MultiMed. 1(2), 73 (1994). Google Scholar
S. Zhonghua and P. Fu, Combination of color and object outline based method in video segmentation, Proc. SPIE5307 (2004) pp. 61–69. Google Scholar
W. Wolf, Key frame selection by motion analysis, Proc. ICASSP (1996) pp. 1228–1231. Google Scholar
S. H. Han, K. J. Yoon and I. S. Kweon, A new technique for shot detection and key frames selection in histogram space, Proc. 12th Workshop on Image Processing and Image Understanding (2000) pp. 475–479. Google Scholar
A. Hanjalic, R. L. Lagendijk and J. Biemond, Image Databases Multimed. Search (1998) pp. 97–107. Link, Google Scholar
M. Cooper and J. Foote, Discriminative techniques for keyframe selection, Proc. ICME (The Netherlands, 2005) pp. 502–505. Google Scholar
W. Abd-Almageed , Online, simultaneous shot boundary detection and keyframe extraction for sports video using rank tracing , Proc. ICIP ( USA , 2008 ) . Google Scholar
E. Spyrou and Y. Avrithis , Keyframe extraction using local visual semantics in the form of a region thesaurus , Proc. Int. Workshop on Semantic Media Adaptation and Personalization ( London , 2007 ) . Google Scholar
E. Spyrouet al., Multimed. Tools Appl. 41, 337 (2009), DOI: 10.1007/s11042-008-0237-9. Crossref, Web of Science, Google Scholar
P. P. K. Chanet al., A novel method to reduce redundancy in adaptive threshold clustering key frame extraction systems, Proc. Int. Conf. on Machine Learning and Cybernatics (Guilin, China, 2011) pp. 1637–1642. Google Scholar
S. Mukherjee and D. P. Mukherjee, Multimedia Tools and Applications 62(3), 847 (2011), DOI: 10.1007/s11042-011-0882-2. Crossref, Web of Science, Google Scholar
J. L. Lai and Y. Yi, J. Visual Commun. Image Representation 23(1), 114 (2012), DOI: 10.1016/j.jvcir.2011.08.005. Crossref, Web of Science, Google Scholar
P. Geetha, S. T. Pandeeswari and S. Mohanan, Comput. Sci. Inform. Technol. 2(2), 179 (2012). Web of Science, Google Scholar
Z. Sun, K. Jia and H. Chen, Video key frame extraction based on spatial-temporal color distribution, Proc. Int. Conf. on IIHMSP (2008) pp. 196–199. Google Scholar
A. M. Fermann, A. M. Tekalp and R. Mehrotra, IEEE Trans. IP 11(5), 497 (2002). Web of Science, Google Scholar
A. Girgensohn and J. Boreczky, Multimed. Tools Appl. 11, 347 (2000), DOI: 10.1023/A:1009630817712. Crossref, Web of Science, Google Scholar
Y. Gong and X. Liu, Generating optimal video summaries, Proc. IEEE ICME (San Jose, CA, USA, 2000) pp. 1559–1562. Google Scholar
Y. Zhuanget al., Adaptive key frame extraction using unsupervised clustering, Proc. ICIP (USA, 1998) pp. 866–870. Google Scholar
D. Borthet al., Keyframe extraction for video tagging and summarization, Proc. Informatiktage (Germany, 2008) pp. 45–48. Google Scholar
X. Xenget al., Key-frame extraction using dominant-set clustering, Proc. IEEE Int. Conf. Multimedia and Expo (2008) pp. 1285–1288. Google Scholar
B. Gunsel and A. M. Tekalp , Content-based video abstraction , Proc. ICIP ( USA , 1998 ) . Google Scholar
L. Zhaoet al., Key-frame extraction and shot retrieval using nearest feature line (NFL), Proc. Int. Workshop on Multimedia Info. and Rerieval (2000) pp. 217–220. Google Scholar
L. Pan, X. Wu and X. Shu, Key frame extraction based on sub-shot segmentation and entropy computing, Proc. Chinese Conf. on Pattern Recognition (IEEE Press, 2009) pp. 1–5. Google Scholar
L. Sun and Y. Zhou, A key frame extraction method based on mutual information and image entropy, Proc. Int. Conf. on Multimedia Technology (2011) pp. 35–38. Google Scholar
L. Liu, X. Wang and S. Zhou, Key frames extraction algorithm based on GA, Proc. Fourth Int. Joint Conf. on Computational Sciences and Optimization (2011) pp. 808–811. Google Scholar
P. J. Macer and P. J. Thomas, Video storyboards: Summarizing video sequences for indexing and searching of video databases, Proc. IEE Colloquium on Intelligent Image Databases (1996) pp. 2/1–2/5. Google Scholar
S. Uchihashi and J. Foote, Summarizing video using a shot importance measure and a frame-packing algorithm, Proc. ICASSP6 (1999) pp. 3041–3044. Google Scholar
G. Ciocca and R. Schettini, Dynamic storyboards for video content summarization, Proc. ACM Int. Workshop on Multimedia Information Retrieval (2006) pp. 259–268. Google Scholar
S. Sullet al., Scalable hierarchical video summary and search, SPIE Proc.4315 (2001) pp. 553–561. Google Scholar
P. Mundur, Y. Rao and Y. Yesha, Int. J. Digital Libraries 6(2), 219 (2003), DOI: 10.1007/s00799-005-0129-9. Crossref, Google Scholar
P. P. Mohanta, S. K. Saha and B. Chanda, IEEE Trans. Multimed. 14(1), 223 (2012), DOI: 10.1109/TMM.2011.2170963. Crossref, Web of Science, Google Scholar
P. P. Mohanta , S. K. Saha and B. Chanda , Detection of representative frames of a shot using multivariate Wald–Wolfowitz test , Proc. ICPR ( Florida, USA , 2008 ) . Google Scholar
P. P. Mohanta , S. K. Saha and B. Chanda , A novel key-frame detection technique using statistical run test and majority voting , Proc. ICVGIP ( Bhubaneswar, India , 2008 ) . Google Scholar
A. Wald and J. Wolfowitz, Annals Math. Statist. 11, 147 (1940), DOI: 10.1214/aoms/1177731909. Crossref, Google Scholar
J. H. Friedman and L. C. Rafsky, The Annals Statist. 7(4), 697 (1979), DOI: 10.1214/aos/1176344722. Crossref, Web of Science, Google Scholar
M. M. Yeung , B. L. Yeo and B. Liu , Extracting story units from long programs for video browsing and navigation , Proc. IEEE Conf. on Multimedia Computing and Systems ( 1996 ) . Google Scholar
P. P. Mohanta , S. K. Saha and B. Chanda , Generation of size constrained video storyboard using spanning tree , Proc. ICIMCS ( Kunming, Yunnan, China , 2009 ) . Google Scholar
R. C. Prim, Bell Syst. Tech. J. 36, 1389 (1957). Crossref, Web of Science, Google Scholar
B. S. Manjunath and W. Y. Ma, IEEE Trans. PAMI 18, 837 (1996), DOI: 10.1109/34.531803. Crossref, Web of Science, Google Scholar
C. R. Rao , S. K. Mitra and A. Matthai , Formula and Tables for Statistical Work ( Statistical Publishing Society , Kolkata , 1966 ) . Google Scholar