隨選視訊服務是最熱門的多媒體應用之一。不管在什麼時間或地點，使用者都可以透過隨選視訊服務看到電視影片、電影及新聞等。然而，隨著影片的數量達上千個小時，在查詢後我們仍會得到許多符合的影片。為了要在短時間內挑選出我們最想要的影片，我們需要一個有效率的影片摘要方法以萃取影片的概要內容。
考慮到影片是由一些故事單元所組成，我們提出一個影片摘要方法，從影片的每個故事單元中擷取出最重要的影片片段，並把這些片段合成一個影片摘要。這個影片摘要大約只有原來影片長度的十分之一，但重要的是，使用者在看過這段影片摘要後，便能快速的瞭解到原來影片的大致內容及架構。為了開發這個影片摘要系統，我們提出一些視訊處理的技術，包括先將影片做切割的視訊切割方法，將視訊片段叢聚成故事單元的視訊叢聚方法及從故事單元中擷取重要片段的方法。我們提出一個以GOP為基礎的視訊切割方法，這個方法比一般以frame為基礎的視訊切割方法節省相當多時間。在視訊叢聚上，我們的演算法可以有效率的將影片片段叢聚成故事單元。最後我們也定義了重要影片片段以及從故事單元中擷取這些片段的演算法。另外，我們也提供了一個整合的影片摘要環境，包括視訊影音分離系統、視訊編輯系統、影片摘要系統和視訊影音整合系統。系統的全部工作都是自動的不需人工介入，而且透過實驗，我們也得到令人滿意的結果。

Video on Demand ( VOD ) service is one of the most popular multimedia applications. By VOD services people can watch TV programs, movies, or news whenever they want or somewhere far away from server. However, with the volume of videos growing to thousands of hours, there may be lots of matched videos in the query result. For getting the most desired video in a short time, we need an effective approach to summarize the video for providing the overall view of videos.
Considering that the video is composed of story units, we propose a video summary system which extracts the significant segments from each story unit of the video and combines them into an abstracted video. This abstracted video is about one-tenth of the original video in time-length and more importantly, presents the critical information such that users can rapidly realize the synopsis and have an overall view of the original video. To implement the video summary system, some techniques of video processing have been proposed in our system, including segmenting the video as shots, clustering the shots into story-units and selecting the significant shots from each story-unit. In shot segmentation, we propose GOP-based scene change detection approach, which saves more processing time than scene change detection frame by frame. In shot clustering, we design a shot clustering algorithm to effectively cluster shots into story units. We also define the significant shots and present the algorithms to extract the significant shots in a video. In addition, we provide an integrated environment for video summary system, such as audio-video splitter, audio-video editor, video summary and audio-video combiner. All tasks in this system are done automatically and the results of experiment prove to be justifiable and satisfactory.

Abstract in Chinese……………………………………………………………………i
Abstract……………………………………………………………………………….iii
Acknowledgement……………………………………………………………………v
Table of Contents……………………………………………………………………..vi
List of Figures……………………………………………………………………….viii
List of Tables………………………………………………………………………..x
List of Algorithms………………………………………………………………xi
Chapter 1 Introduction……………………………………………......1
1.1 Motivation……………………………………………………………………1
1.2 Organization………………………………………………………………….3
Chapter 2 Background…………………………………………………………………5
2.1 Overview of MPEG-II standard……………………………………………...5
2.1.1 Structure of coded video data…………………………………………6
2.1.2 Picture layer of coded video data……………………………………..7
2.2 Scene change detection method……………………………………………...9
2.2.1 Pixel-domain scene change detection…………………………………9
2.2.2 Histogram comparison.……………………………………………...10
2.2.3 DCT coefficients and motion-vector based approach……………….11
2.2.4 Feature-based approach……………………………………………...12
2.3 Clustering method……………………………………………………...13
2.4 Other video summary method………………………………………………16
Chapter 3 Video summary based on story-unit………………………………………20
3.1 Overview of video summary based on story-unit…………………………..20
3.2 Shot segmentation…………………………………………………………..22
3.2.1 Non-sequential scene change detection approach…………………..22
3.2.2 GOP-based scene change detection approach………………………23
3.2.2.1 Detecting the possible scene change by the unit of GOP……25
3.2.2.2 Finding out the actual scene change in the GOP…………….27
3.2.3 Evaluation of GOP-based scene change detection approach………..30
3.3 Shot clustering………………………………………………………….32
3.3.1 Definition in shot clustering……………………………………….33
3.3.2 Algorithm of shot clustering……………………………………….35
3.4 Shot selection……………………………………………………………….39
3.4.1 Shot characterization………………………………………………...39
3.4.1.1 Detecting dialogue shots..…..………………………………40
3.4.1.2 Detecting action shots………………………………………42
3.4.1.3 Detecting still shots…………………………………………43
3.4.2 Shot selection rule…………………………………………………...44
Chapter 4 System architecture and experiment……………………………………..46
4.1 Overview of video summary system………………………………………46
4.2 Audio-Video splitter module………………………………………………49
4.3 Audio-Video combiner module……………………………………………50
4.4 Video summary module……………………………………………………51
4.4.1 Component of video segmentation ………………………………….51
4.4.2 Component of video clustering .…………………………………53
4.4.3 Components of video characterization and representative selection ..53
4.5 Audio-Video editor module………………………………………………56
4.5.1 Video editor module…………………………………………………56
4.5.2 Audio editor module…………………………………………………57
4.6 Experiment and analysis…………………………………………………….59
Chapter 5 Conclusion and future work……………...……………………………….66
Bibliography………………………………………………………………………….68

[1] M. Flickner, et al., "Query by Image and Video Content: The QBIC System," IEEE Computer Magazine, Vol. 28, No. 9, pp. 23-32, 1995.
[2] J. R. Smith and S. F. Chang, "VisualSEEk: A Fully Automated Contend-Based Image Query System," Proceedings of ACM Multimedia, Boston, MA, pp. 87-98, 1996.
[3] J. K. Wu, A.Desai Narasimhalu, B. M. Mehtre, C. P. Lam, Y. J. Gao, "CORE: A Content-Based Retrieval Engine for Multimedia Information Systems," Multimedia Systems, Vol. 3, No. 1, pp. 25-41, 1995.
[4] Coding of Moving Pictures and Associated Audio-for Digital Storage Media at up to about 1.5Mbit/s, Committee Draft of Standard ISO11172: ISO/MPEG 90/176, November 1991.
[5] J. L. Mitchell, W. B. Pennebaker, Chad E.Fogg, and Didier J. LeGall, "MPEG VIDEO COMPRESSION STANDARD," Chapman&Hall, NY, USA, 1997.
[6] G. Ahanger and T. D.C. Little, "A Survey of Technologies for Parsing and Indexing Digital Video," Journal of Visual Communication and Image Representation, special issue on Digital Libraries, Vol. 7, No. 1, pp. 28-43, 1996.
[7] A. Nagasaka, and Y. Tanaka, "Automatic Video Indexing and Full-Video Search for Object Appearances," Visual Database Systems, II, Eds. E. Knuth, and L.M. Wegner, Elsevier Science Publishers B.B., IFIP, pp.113-127, 1992.
[8] H. J. Zhang, A. Kankanhalli, and S.W. Smoliar, "Automatic Partitioning of Full-Motion Viedo," Multimedia Systems, Vol. 1, No. 1, pp.10-28, 1993.
[9] F. Arman, A.Hsu, and M.Y. Chiu, "Image processing on Compressed Data for large Video Databases," Proc. 1st ACM Intl. Conf. On Multimedia, Anaheim CA, pp.267-272, 1993.
[10] J. Meng, Y. Juan, S.F. Chang, "Scene Change Detection in a MPEG Compressed Video Sequence," Proc. IS&T/SPIE, Vol. 2419, pp.14-25, 1995.
[11] R. Zabih, J. Miller, and K. Mai, "A Feature-Based Algorithm for Detecting and Classifying Scene Breaks," Proc. ACM Multimedia, pp.189-200, 1993.
[12] A. Hauptmann, and M. Smith, "Text, Speech, and Vision for Video Segmentation: The Informedia Project," AAAI Symposium on Computational Models for Integrating Language and Vision, 1995.
[13] S. W. Smoliar and H. J. Zhang, "Content-Based Video Indexing and Retrieval," IEEE Multimedia, Vol. 1, No. 2, pp.67-72, 1994.
[14] H. J. Zhang, S. Y. Tan, S. W. Smoliar, G. Yihong, "Automatic Parsing and Indexing of News Video," Multimedia Systems, Vol. 2, No. 6, pp.256-266, 1995.
[15] F. Arman, R. Depommier, A. Hsu, and M.Y. Chiu, "Content-based browsing of video sequences," Proc. ACM Multimedia, pp.97-103, 1994.
[16] 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.
[17] M. Christel, T. Kanade, M. Mauldin, R. Reddy, M. Sirbu, S. Stevens, H. Wactlar, "Informedia Digital Video Library," Communications of the ACM, Vol. 38 No. 4, pp. 57-58, 1995.
[18] S. Pfeiffer, R. Lienhart, S. Fischer, and W. Effelsberg, "Abstracting Digital Movies Automatically," Journal of Visual Communication and Image Representation, Vol.7, No.4, pp. 345-353, 1996
[19] B. L. Yeo and B. Liu, "Rapid Scene Analysis on compressed Video," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 5, No. 6, pp.533-544, 1995.
[20] H. C. Lin, "Distributed News Video Database System for VOD Environment," Master thesis, National Chiao Tung University, Dept. of CSIE, June 1997.
[21] Britannica Online, "http://www.eb.com:180/eb.html," November 1995.
[22] M. M. Yeung and B. L. Yeo, "Video Content Characterization and Compaction for Digital Library Applications," In IS&T/SPIE Electronic Imaging'97: Storage and Retrieval of Image and Video Database, VI SPIE 3022, pp. 310-321, 1997.
[23] MPEG Software Simulation Group, HTTP://www.mpeg.org.
[24] R. J. Chen, "Design of an MPEG-2 Video Editing System," Master thesis, National Chiao Tung University, Dept. of CSIE, June 1996.
[25] M. F. Shen, "Parsing and Browsing of Video Data for Video on Demand Services," Master thesis, National Chiao Tung University, Dept. of CSIE, June 1997.