簡易檢索 / 詳目顯示

回結果列表
研究生： 林柏筠
Lin, Bo-Yun
論文名稱： 運用分群法在時間及空間上的視訊物件切割
Spatio-temporal Video SegmentationUsing Clustering
指導教授： 李國君
Lee, Gwo Giun
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2007
畢業學年度： 95
語文別： 英文
論文頁數： 96
中文關鍵詞： 視訊物件切割 、分群法 、數學型態學 、分水嶺法
外文關鍵詞： mathematical morphology, morphological watershed, clustering, video segmentation
相關次數： 點閱：92  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 視訊物件切割為視訊領域中的一項重要技術；在新一代的視訊壓縮方法、電腦視覺及機器視覺等應用裡，視訊物件切割都被視為不可或缺的前端處理。好的視訊切割演算法，能以較低的運算量，切割出與真實視訊物件較為一致的視訊區域。本論文提出一個以分類法為基礎的視訊物件切割之初步架構。在針對數個不同的分群方法分析比較後，選定了k-means分群演算法建立一個完整的視訊物件切割演算法。運用視訊訊號在空間及時間上的相關性，給定一個接近自然分群的起始分群，以降低傳統以亂數起始之k-means分群演算法運算所需的運算量、提高其準確度、以及切割結果在時域上的連續度。這篇論文所提出的視訊切割演算法，除了使用分群法，也配合數學型態學中分水嶺方法的原理，劃分影像中不連接的分群區域。由於視訊在使用分群法的處理後，已提供一個初步的分群標籤，此時再以分水嶺法的原理處理，就可以避免原始分水嶺法過度切割的缺點，並大量的簡化複雜的分水嶺法。實驗分析所提出演算法中的分群法，由較少的遞迴次數可看出效率上的提升；而由影像切割結果可看出較佳的效能。最後，我們並把這些分析結果與切割後的視訊物件圖，同時列於實驗結果。

    Video segmentation is a very important technology in video signal processing. It is an indispensable front-end procedure in the domain of second generation video compression, computer vision, machine recognitions, and many other multimedia applications. Better video segmentation algorithm needs less computation with its result obtaining better goodness-of-fit to the true object. In this thesis, we introduce a classification-based infrastructure for video segmentation algorithm. After analyzing the clustering algorithms, we proposed a video segmentation algorithm based on k-means clustering. By studying the spatial and temporal correlation of a video sequences, we develop a method by assigning proper initial partitions to improve the accuracy and the efficiency of the traditional k-means algorithm. In addition to the clustering, we applied the principle of morphological watersheds to split the unconnected regions. Since the video signals are already labeled by the clustering mechanism before object detection, over-segmentation problem of the original morphological watersheds will not occur and the procedure becomes simpler. Finally, experimental results demonstrated in this thesis confirm that the proposed clustering algorithm requires less number of iterations and achieve good segmentation results.

    考試合格證明 I CERTIFICATION II 運用分群法在時間及空間上的 視訊物件切割 III 摘 要 III SPATIO-TEMPORAL VIDEO SEGMENTATION USING CLUSTERING V ABSTRACT V 誌 謝 VII TABLE OF CONTENT VIII LIST OF FIGURES X LIST OF TABLES XIII CHAPTER 1 INTRODUCTION 1 1.1. Background 1 1.2. Motivation 2 1.3. Organization of this Thesis 2 CHAPTER 2 SEGMENTATION ALGORITHMS 4 2.1. Edge-detection-based Segmentation Algorithms 4 2.1.1. Basic Edge Detection Method 5 2.2. Morphology-based Segmentation Algorithms 9 2.2.1. Morphological Watersheds Algorithms 9 2.3. Motion-based Segmentation Algorithms 11 2.3.1. Change Detection Methods 12 2.3.2. Parameter Methods 13 2.3.3. Block/Object Motion Estimation 16 2.4. Spatio-temporal-based Segmentation Algorithms 18 2.5. Classification-based Segmentation Algorithms 19 CHAPTER 3 INFRASTRUCTURE OF THE PROPOSED ALGORITHM 22 3.1. Clustering for Segmentation 23 3.2. Similarity Measurement 24 3.3. Clustering Algorithms 30 3.3.1. Exclusive Clustering Algorithms 30 3.3.2. Overlapping Clustering Algorithms 32 3.3.3. Hierarchical Clustering Algorithms 34 3.3.4. Model-based Clustering Algorithms 38 CHAPTER 4 PROPOSED VIDEO SEGMENTATION ALGORITHM 39 4.1. Clustering 40 4.1.1. k-means Clustering Algorithm 41 4.1.2. First Frame Initialization 42 4.1.3. Temporal Initialization 47 4.2. Object Detection 47 CHAPTER 5 EXPERIMENTAL RESULT 55 5.1. Comparison and Analysis for Clustering 55 5.2. Video Segmentation Algorithms 60 5.2.1. Simulation Results of First Frame Initialization 62 5.2.2. Simulation Results of Temporal Initialization 69 5.2.3. Object Detection and Final Segmentation Results 77 CHAPTER 6 CONCLUSION AND FUTURE WORKS 88 6.1. Conclusion 88 6.2. Future Works 89 REFERENCES 90 作 者 簡 歷 96

    [1] ISO/IEC 14996-2, "Amendment1, Information technology - coding of audio-visual objects - part2: Visual," 2001.
    [2] Rafael C. Gonzalez and Richard E. Wood, Digital image processing, Prentice-Hall: Eaglewood Cliffs, New Jersey, 2002.
    [3] D. Marr and E. Hildereth, "Theory of edge detection," Proceeding of Royal Society London, pp. 187-217, 1980
    [4] R. Deriche, "Optimal edge detection using recursive filtering," International Journal of Computer Vision, pp. 501-505, 1987.
    [5] J. Shen and S. Castan, "An optimal linear operator for edge detection," Proceedings IEEE International Conference on Computer Vision and Pattern Recognition, pp. 109-114, 1986.
    [6] V. Torre and T. Poggio, "On edge detection," IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 8, no. 4, pp. 147-163, 1986.
    [7] J. Canny, "Computational approach to edge detection," IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 8, pp. 679-698, Nov.1986
    [8] M.Gokmen and A.K. Jain,"λ -space representation of images and generalized edge detector," IEEE International Conference on Computer Vision and Pattern Recognition, pp.764-769, June 18-20, 1996.
    [9] A. P. Wikin, "Scale-space filtering," Proceedings on International Joint Conference on Artificial Intelligence, Karlsruhe, Germany., pp. 1019-1022, 1983.
    [10] Serra J. "Automatic scanning device for analyzing textures", France. Patented in: Belgium, Canada, Great-Britain, Japan, Sweden, USA, July 2, 1965a(23 273).
    [11] Serra, J., Image Analysis and Mathematical Morphology, London UK: Academic Press. 1982.
    [12] J. W. Klingler, C. L. Vaughan, T. D. Fraker, L. T. Andrews, "Segmentation of echocardiographic images" IEEE Transactions Biomedical Engineering, vol. 35, no. 11, Nov. 1988.
    [13] P. Solle "Morphological image compositing" IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 28, no. 5, pp. 673-683, May 2006
    [14] Q. Shen, S. Li and J. Kwork, "Page segmentation using mathematical morphology," Proceeding of ISPCS 2005, pp. 89-92, Dec. 2005.
    [15] F. Meyer and S. Beucher, "Morphological segmentation," Journal of Visual Communication Image Representation, vol. 1, no. 1, pp. 21-46, Sept. 1990.
    [16] S. Beucher and C. Lantuejoul, "Use of watersheds in contour detection," Proceeding International Workshop Image Processing, Real-Time Edge and Motion Detection/ Estimation, Rennes, France, Sept. 17-21, 1979.
    [17] S. Beucher, "Watersheds of functions and picture segmentation," IEEE International Conference on ICASSP, Acoustics, Speech, and Signal Processing, Paris France, May 1982, pp.1928-1931.
    [18] J.B.T.M. Roerdink and A. Meijster, "The Watershed Transform: Definitions, Algorithms and Parallelization Strategies," Fundamenta Informaticae, vol. 41, pp. 187-228, 2000.
    [19] S.-Y. Chien, Y.-W. Huang, S.-Y. Ma, L.-G. Chen, "Predictive Watershed for image sequences segmentation," IEEE Proceedings of ICASSP '02, vol. 3, pp. 3196-3199, May 2002.
    [20] S.-Y. Chien, S.-Y Ma, and L.-G Chen, "Predictive Watershed: A fast watershed algorithm for video segmentation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 5 pp. 453-461 July 2003.
    [21] F. Meyer, "Color image segmentation," Proceeding International Conference Image Processing and its Applications, 1992, pp. 303-306.
    [22] L. Vincent and P.Soille, "Watersheds in digital space: an efficient algorithm based on immersion simulations," IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 13, pp. 583-598, June 1991.
    [23] D. Hagyard, M. Razaz, and P. Atkin, "Analysis of watershed algorithms for grey scale images," Proceeding of International Conference on Image Processing, 1996, pp. 41-44.
    [24] M. Hoetter and R. Thoma, "Image segmentation based on object oriented mapping parameter estimation," Signal Processing, vol. 15, pp.315-334, 1988.
    [25] S.-Y. Chien, S.-Y Ma, and L.-G Chen, "Efficient moving object segmentation algorithm using background registration technique," IEEE Transactions on Circuits and Systems for Video Technology, vol. 12 pp. 577-586, July 2002.
    [26] S.-Y. Chien, S.-Y Ma, and L.-G Chen, "Efficient moving object segmentation algorithm using background registration technique," IEEE Transactions on Circuits and Systems for Video Technology, vol. 12 pp. 577-586, July 2002.
    [27] M.-F. Fu, O. Au and W.-C Chan, "Fast global motion estimation based on local motion segmentation," Proceeding of ICIP 2003, vol. 2, pp. 367-370, Sept. 2003.
    [28] S.-C. Cheng, "Visual pattern matching in motion estimation for object-based very low bit-rate coding using moment preserving Edge detection," IEEE Transactions on Multimedia, vol. 7, no. 2, April 2005.
    [29] T. Meier and K. N. Ngan, "Automatic segmentation of moving objects for video object plane generation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, no. 5, pp. 525-538, Sept. 1998.
    [30] T. Meier and K. N. Ngan, "Automatic video sequence segmentation using object tracking," Proceedings of IEEE on Speech and Image Technologies for Computing and Telecommunications', IEEE Region 10 Annual Conference, TENCON '97, no.1, pp. 283-286, Dec. 1997
    [31] T. Meier and K. N. Ngan, "Video object segmentation using a morphological motion filter and Hausdroff object tracking," IEEE International Conference of Image Processing, vol. 2 pp 652-656, Sept. 1998.
    [32] Di. Zhong and S.-F Cheng, "An integrated approach for content-based video object segmentation and retrieval," IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, no. 8, Dec. 1999.
    [33] C. Cu and M. C. Lee, "Semantic video object segmentation and tracking using mathematical morphology and perspective motion model," IEEE International Conference of Image Processing, ICIP'97, Santa Barbara, CA, Oct. 1997, vol. II, pp. 514-517.
    [34] T. Pappas, "An adaptive clustering algorithm for image segmentation," IEEE Transactions on Signal Processing, vol. 40, no. 4, Apr. 1992.
    [35] A. M. Tekalp, Ed., Digital Video Processing, Upper Saddle River, NJ: Prentice-Hall, 1995.
    [36] A.-R. Mansouri and J. Konard, "Multiple motion segmentation with level sets" IEEE Transactions on Image Processing, vol. 12, no. 2, Feb. 2003
    [37] N. Vasconcelos and A. Lippman, "Empirical Bayesian motion segmentation" IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 23, no. 2, Feb. 2001.
    [38] P. Salembie and F. Marques, "Classification-based representations of image and video: Segmentation tools for multimedia services," IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, no.8 Dec. 1999.
    [39] L. Liu, G. Fan, "Combined key-frame extraction and object-based video segmentation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 7 pp. 689-882, July 2005.
    [40] P. H. S. Torr, R. Szelisiki, and P. Anandan, "An integrated Bayesian approach to layer extraction from image sequences," IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 23, no. 2, pp. 296-303, Feb. 2001.
    [41] Y. Wang, K.-F. Loe, T. Tan, and J.-K.Wu, "Spatiotemporal video segmentation based on graphical models," IEEE Transactions on Image Processing, vol. 14, no. 7, July 2005.
    [42] S. Khan and M. Shah, "Object based segmentation of video using color, motion and spatial information," IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, pp. 746-751, Sept 2001.
    [43] J. Goldberger and H. Green span, "Context-based segmentation of image sequences," IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 28, no. 3, March 2006.
    [44] Y. Cheng, "Mean Shift, mode seeking and clustering," IEEE Transactions on Pattern Analysis Machine Intelligence, vol.17, no. 8, pp. 790-799, Aug. 1995.
    [45] D. Comaniciu, and P. Meer, "Mean shift: A robust approach toward feature space analysis," IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 24, no. 5, May 2002.
    [46] Naber, Gregory L., The Geometry of Minkowski Spacetime, Springer-Verlag: New York, 1992.
    [47] P.C. Mahalanobis, "On the generalized distance in statistics", Proceedings of the National Institute of Science of India, vol. 12, pp. 49-55, 1936
    [48] M. G. Kendall, "A new measure of rank correlation," Biometrika, vol. 30, no. 1/2, pp. 81-93, June 1938
    [49] University of California - Irvine, "UCI Repository Of Machine Learning Databases and Domain Theories," ftp://ftp.ics.uci.edu/pub/machine-learning-databases
    [50] J. B. Mcqueen, "Some methods for classification and analysis of multivariate observations," Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, pp. 281-297, 1967.
    [51] R. O. Duda and P. E. Hart, D. G. Stork, Pattern Classification, 2th edition,Wiley: New York, 2001.
    [52] S. P. Lloyd, "Least squares quantization in PCM," IEEE transactions on Information Theory, vol. 28, pp. 129-137, 1982
    [53] G. G. Lee, Ming-Jiun Wang, He-Yuan Lin, Drew Wei-Chi Su and Bo-Yun Lin, "Algorithm/Architecture co-design of 3D spatio-temporal motion estimation for video coding," IEEE Transactions on Multimedia, vol.9, no. 3, April 2007.

    下載圖示 校內：2012-08-10公開
    校外：2012-08-10公開
    QR CODE