本論文提出一個能分割與追蹤影片中物體的演算法，我們提出了一種能建造出可信賴的背景的方法，利用未加工的背景可分離出移動的物體，再利用梯度向量流量(Gradient Vector Flow, GVF)的特性來分割移動物體的邊界，利用圖形主動輪廓 (Morphing Active Contours) 來做移動物體的追蹤，最後利用每個分割的結果建立影片的可信賴背景，本論文使得梯度向量流量(GVF)能在複雜背景下成功的分割目標物體，因為被分割出來的物體之面積僅是全影像的一部份，而我們只需要針對此部份做運算，因此可以減少部分的運算量，並因為建立了可信賴背景提昇了壓縮效率。
在本論文中做了多個真實影像的實驗，經由實驗結果知道，若物體呈像面積夠大而且移動速度不算太快下，所提的方法可以有效的分割與追蹤影片中之目標物體。

An algorithm of video segmentation and tracking based on background construction is proposed. Rough background can be constructed by using this algorithm. Applying rough background, the moving object can be segmented by using the characteristic of gradient vector flow (GVF). Morphing active contours is used to track the object that has been segmented. Finally, reliable background is constructed from the every segmentation result. In this thesis, the abilities of GVF in the complicate background have been improved by using construct reliable background. According the rough background, only the smaller area of moving object is used to segmentation. The area of tracking is reduced by motion estimation and the coding efficiency is improved because the construction of reliable background.
In this thesis, several real videos are experimented: Under the assumption of the size and speed of object, efficient segmentation and tracking on multi-objects can be implemented by the algorithm proposed in this thesis.

Contents
中文摘要 i
Abstract ii
Contents iv v
List of Figures vi vii vii
List of Tables vii
1 Introduction 1
1.1 Survey 1
1.2 Motivation 4
1.3 Organization of the Thesis 5
2 Cluster, Snakes, Gradient Vector Flow, and Morphing Active Contours 6
2.1 ISODATA Algorithm 7
2.2 Snakes 12
2.2.1 Definition 13
2.2.2 Numerical Computation 14
2.3 Gradient Vector Flow 15
2.3.1 Definition 15
2.3.2 Numerical Computation 16
2.4 Greedy Algorithm in Gradient Vector Flow 19
2.5 Morphing Active Contours 20
2.3.1 Definition 20
2.3.2 Numerical Computation 22
3 Background Construction, Segmentation with Complicate Background and Motion Estimation 25
3.1 Rough Background Construction 26
3.1.1 Frame Difference 27
3.1.2 Rough Background 33
3.2 Segmentation with Complicate Background 38
3.3 Motion Estimation 43
3.4 Reliable Background Construction 46
4 Experimental Results and Analysis 49
4.1 Experimental Environment and Flow 50
4.2 Experimental Results 52
4.3 Extra Fast Moving Objects 80
4.2 Analysis 84
5 Conclusions 92
Bibliography 94

[1] F. Marques and C. Molina, “Object tracking for content based functionalities,” in SPIE Vision Communication Image Processing, vol. 3024, San Jose, CA, pp. 190-199, 1997.
[2] C. Gu and M. C. Lee, “ Semantic segmentation and tracking of semantic video objects,” IEEE Transaction Circuits System Video Technology, vol. 8, no. 5, pp. 572-584, 1998.
[3] T. Aach, A. Kaup, and R. Mester, “Statistical model-based change detection in moving video,” Signal Processing, vol. 31, no.2, pp. 165-180, 1993.
[4] R. Mech and M. Wollborn, “A noise robust method for 2D shape estimation of moving objects in video sequences considering a moving camera,” Signal Processing, vol. 66, no. 2, pp. 203-217, 1998.
[5] A. Neri, S. Colonnese, G.. Russo, and P. Talone, “Automatic moving object and background separation,” Signal Processing, vol. 66, no. 2, pp. 219-232, 1998.
[6] M. Kass, A. Witkin, and D. Terzopoulos, “Snakes： Active contour models,” International Journal of Computer Vision, vol. 1, pp. 321-331, 1987.
[7] A. R. Mirhosseini and H. Yan, “An optimally fast greedy algorithm for active contours,” Proceedings of 1997 IEEE International Symposium on Circuits and systems, vol. 2, pp. 1189-1192, 1997.
[8] F. Leymarie and M. D. Levine, “Tracking deformable objects in the plane using an active contour model.” IEEE Transactions on Pattern Analysis Machine Intelligent, vol. 15, no.6, pp. 617-634, 1993.
[9] R. Durikovic, K. Kaneda, and H. Yamashita, “Dynamic contour: A texture approach and contour operations,” Vision Computer, vol. 11, pp. 277-289, 1995.
[10] D. J. Williams and M. Shah, “A fast algorithm for active contours and curvature estimation,” CVGIP：Image Understandings, vol. 55, no. 1, pp. 14-26, 1992.
[11] B. Leroy, I. Herlin, and L. D. Cohen, “Multi-resolution algorithms for active contour models,” Proceedings of the 12th International Conference on Analysis and Optimization of systems, pp. 58-65, 1996.
[12] L. D. Cohen, “On active contour models and balloons,” CVGIP：Image Understand, vol. 53, no. 11, pp. 211-218, 1991.
[13] L. D. Cohen and I. Cohen, “Finite-element methods for active contour models and balloons for 2-D and 3-D images,” IEEE Transaction Pattern on Analysis Machine Intelligent, vol. 15, no. 11, pp. 1131-1147, 1993.
[14] P. C. Yuen, Y. Y. Wong, and C. S. Tong, “Contour detection using enhanced snakes algorithm,” Electronics Letters, vol. 32, pp. 202-204, 1996.
[15] L. Ji and H. Yan, “An attractable snake model for contour extraction in MRI images,” Proceedings of the 20th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, vol. 2, pp. 609-612, 1998.
[16] C. Y. Xu and J. L. Prince, “Snakes, shapes, and gradient vector flow,” IEEE Transactions on Image Processing, vol. 7, no. 3, pp. 359-369, 1998.
[17] C. H. Chuang and W. N. Lie, “Fast and accurate active contours for object boundary segmentation.” Proceedings of IEEE Asia Pacific Conference on Circuits and Systems, pp. 473-476, 2000.
[18] C. H. Chuang and W. N. Lie, “Automatic snake contours for the segmentation of multiple objects.” Proceedings of IEEE International Symposium on Circuits and Systems, vol. 2, pp.389 -392, 2001.
[19] M. Bertalmio, G. Sapiro, and G. Randall, “ Morphing active contours.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no.7, pp. 733 —737, 2000.
[20] M. Bertalmio, G. Sapiro, and G. Randall, “Morphing active contours: a geometric approach to topology-independent image segmentation and tracking.” Proceedings of 1998 IEEE International Conference on Image Processing, vol. 3, pp. 318 —322, 1998.
[21] T. Aach, A. Kaup, and R. Mester, “Statistical model-based change detection in moving video,” Signal Processing, vol. 31, pp. 165-180, 1993.
[22] N. Mukawa and H. Kuroda, “Uncovered background prediction in inter-frame coding,” IEEE Transactions on Communication, vol. 33, pp. 1227-1231, 1985.
[23] D. Hepper, “Efficiency analysis and application of uncovered background prediction in a low bit rate image coder,” IEEE Transactions on Communication, vol. 38, pp. 1578-1587, 1990.