現今許多新式之影像壓縮技術如MPEG-4與MPEG-7，皆支援以物件為基礎(object-based)之多媒體編碼方式，使得視訊影像中的物件可支援互動、搜尋、以及交換等功能。在支援這些功\能的同時，針對視訊影像中所有物件的切割與追蹤則為非常重要的關鍵技術。本文將提出一套具系統性之演算法，分別結合了邊緣偵測(edge detection)、影像切割(image segmentation)、以及軌跡預測(trajectory estimation)之技術，來完成影像物件追蹤之功能。
    
　　本文所提出之切割影像方法是以物件輪廓為基礎。為了切割出更精確的影像物件，一般舊有的影像輪廓偵測技術並不敷需求；例如Sobel演算法可以有效地偵測明顯物件之輪廓，但許多細緻之邊緣與背景邊緣則無法順利萃取；或如DoE(difference of exponential)演算法，雖然可以偵測出更強烈的邊緣，但仍舊無法偵測細緻的邊緣，然而，細緻邊緣在影像中時常扮演著極重要角色，卻也因為細緻之故，以致於普遍被忽略或是無法處理。本文採用型態影像學(mathematical morphology)之理論，發展出具有加強描繪細微特徵之輪廓偵測演算法。利用邊緣存在之背景之平均灰階值以及標準差，我們可以判斷該邊緣是否應該被強化，以便在對整個影像使用全域閥值時，得以成功的萃取出該細緻邊緣。

　　影像物件切割的部份，過去有許多影像切割演算法被提出，例如蛇模型(snake energy model)以及分水嶺演算法(watershed algorithm)等。蛇模型初始時需要一個初始輪廓，並且利用其內部能量(internal energy)與外部能量(external energy)來引導蛇模型之輪廓去逼近需要切割物體之輪廓。而其中內部能量乃為蛇模型之輪廓曲張之程度，而外部能量則為輪廓所經過位置之影像梯度，當兩個能量達到平衡收斂時，蛇模型之輪廓即達到理想狀態。分水嶺演算法則是模擬淹水的原理，在影像低點開始注入水，當兩個注水來源相遇時，該分界線則為分水嶺。而然，分水嶺演算法確有著過度分割的問題存在。本文所提出之影像切割演算法，可適用於全域影像分割，或使用於特定影像物件分割。利用在影像中植入區域生長點(growing seed)，使所有點蔓延(region growing)整張圖或特定影像物件後，進行區域結合(region merging)，即可將影像或物件萃取出來。而區域生長點之生長規則，則是由一個類似蛇模型之能量公式控制，使得生長過程中得以萃取出具有意義之物件邊緣。

　　由於本文切割影像物件的方式是採用植入區域生長點的方法，所以若是要達成影像追蹤的任務，則必須開發一個能夠自行產生新的生長點予下一個畫面做影像切割。故本文提出一簡易之自動軌跡預測模式，當每頁面(frame)處理完成後，即會自動擇定下一個頁面之生長點位址。如此，即可在視訊影像中連續地萃取出相同之物件，以達成影像物件追蹤之目的。

　　最後，本文結合了邊緣偵測、影像切割、以及軌跡預測之三項演算法，在實驗結果中，確實有效地使用邊緣偵測後所得到之資訊，達到影像的切割與偵測。

Many video compression standards, such as MPEG-4 and MPEG-7, have supported object-based multimedia coding that allows user to interact, search and exchange the objects in the images or video sequences. For supporting these features, the object segmentation and tracking in the video sequences play an essential and important role. This thesis proposes a solution algorithm to track one or multiple moving objects in frames of a video sequence, including edge detection algorithm, image segmentation algorithm and trajectory estimation functions.

  The object segmentation algorithm proposed in this thesis is based on exploring contour of the image. Therefore, to extract the desired objects with more precisely, an effective method for extracting the contour of the image is needed. The conventional edge detection algorithm is no longer satisfy there requirements. For example, Sobel’s edge detector can successfully sketch out the apparently contour of the objects. However, most of the thin edges in the image normally be eliminated by Sobel’s edge detector. The DoE (difference of exponential) method is able to track the stronger edges of the image, but the performance of extracting thin edges is not acceptable. However, in many cases, thin edges represent important features in the image, and should not be eliminated or discarded. This thesis presents a novel mathematical morphology based edge detector to enhance the performance of extracting thin edges in a still image. According to the mean value and standard derivation of the pixel in the image, the proposed method can enhance thin edges in the image for extracting by a global threshold value.

  After the edge detection process, this thesis proposes for applying a novel object segmentation algorithm to the image for extracting objects of the image. There are several popular algorithm had been developed for image segmentation, such as snake energy model and watershed algorithm. For snake energy model, it requires a manually-drawn initial snake and adjusts weighting parameters in the snake model. The snake is controlled by two energies, which are internal energy and external energy. The snake iterations are converged when these two energies reach to a balanced state. As to the watershed algorithm, it has the drawback of over-segmentation problem. This thesis presents a novel edge-based image segmentation algorithm that is capable of performing global image segmentation or segmenting desired objects in an image. The proposed algorithm provides more effective segmentation result than other methods by region growing method. A snake-energy-like cost function is developed to control the growing process for the algorithm to produce better segmentation results. While the growing phase is completed, the algorithm combines homogeneous regions together to extract more meaningful image objects.

  The segmentation algorithm proposed in this thesis is initialized by planting growing seeds into the image. Therefore, to extent our algorithms to video object tracking, this study proposes a scheme based on the previously segmentation result for automatically planting growing seeds into following video frames to extract the same objects on the following frames by the proposed scheme. 

  Experimental results show that the proposed algorithms produce good performance on object segmentation and tracking.

目錄

中文摘要	I
英文摘要	III
致謝	V
目錄	VII
圖表目錄	IX
	
第一章 緒論	1
1.1	研究動機與目標	1
1.2	影像處理流程簡介	3
1.2.1	功能特性	4
1.2.2	靜態影像邊緣萃取（Edge Detection）	4
1.2.3	靜態影像物件切割（Object Segmentation）	5
1.2.4	動態影像自動追蹤（Video Tracking）	5
1.3	本文內容	7
第二章 靜態影像邊緣萃取演算法	8
2.1	概述	8
2.2	邊緣萃取的重要性	9
2.3	傳統邊緣萃取演算法	11
2.3.1	Sobel Edge Detector	11
2.3.2	Prewitt Edge Detector	13
2.3.3	Canny Edge Detector	14
2.4	新式加強型Morphological Residue Edge Detector	18
2.4.1	型態學理論（Mathematical Morphology）概述	18
2.4.1.1  Morphological Erosion and Dilation Operators	19
2.4.1.2  Morphological Opening and Closing Operators	22
2.4.1.3  Morphological White Top-Hat與Black Top-Hat Operators	25
2.4.1.4  Morphological Contrast Enhancement Operator	28
2.4.2	新式演算法概述	29
2.4.3	影像對比加強（Contrast Enhancement）	29
2.4.4	影像輪廓邊緣偵測（Edge Detection）	31
2.4.5	邊緣加強（Edge Enhancement）	32
2.4.6	雜訊去除（Noise Removal）	34
2.4.7	實驗結果與比較	35
2.5	結論	40
第三章 靜態影像物件切割演算法	41
3.1	概述	41
3.2	傳統物件切割演算法	42
3.2.1	Snake Energy Model	42
3.2.2	Watershed Algorithm	45
3.3	新式以邊緣為基礎之影像切割演算法	51
3.3.1	生長點植入（Growing Seeds Deployment）	51
3.3.2	區域生長（Region Growing）	53
3.3.3	區域生長控制規則（Boundary Condition）	54
3.3.4	區域結合（Region Merging）	57
3.3.5	實驗結果與比較	59
3.4	結論	63
第四章 動態影像多重物件追蹤規劃	64
4.1	概述	64
4.2	生長點自動植入規劃	65
4.2.1	植入點決策法	66
4.2.2	系統整合流程圖	68
4.2.3	實驗結果	69
4.2.3.1  例一: 移動式攝影機	70
4.2.3.2  例二: 複雜背景一	71
4.2.3.3  例三: 複雜背景二	72
4.2.3.4  例四: 移動式攝影機與移動中多重物件追蹤	73
4.3	結論	75
第五章 結論	76
5.1	總結	76
5.2	未來展望	78
附錄	79
附錄一  影像邊緣特徵擷取實驗結果	79
附錄二  影像追蹤實驗結果	84
參考文獻	90

圖表目錄

圖目錄
圖1.1	影像處理流程	3
圖2.1	影像之輪廓邊緣偵測不完整之結果	9
圖2.2	Sobel演算法之乘積矩陣	11
圖2.3	Sobel演算法之虛迴旋運算子P	13
圖2.4	Sobel演算法之影像輪廓邊緣偵測結果	13
圖2.5	Prewitt演算法之乘積矩陣	14
圖2.6	Prewitt演算法之影像輪廓邊緣偵測結果	14
圖2.7	連續高斯分布圖形(σ=1.4)	15
圖2.8	高斯分布之離散逼近矩陣	16
圖2.9	Roberts交叉乘積遮罩	16
圖2.10	Canny演算法之影像輪廓邊緣偵測結果	17
圖2.11	Structuring element可呈現之架構種類	18
圖2.12	物件集合X對SE集合B進行Erosion transform示意圖	19
圖2.13	一維信號f之Erosion transform示意圖	20
圖2.14	物件集合X對SE集合B進行Dilation transform示意圖	20
圖2.15	一維信號f之Dilation transform示意圖	21
圖2.16	二維資訊之Erosion結果及Dilation結果	21
圖2.17	校園一景之Erosion結果及Dilation結果	21
圖2.18	物件集合X對SE集合B進行Opening示意圖	22
圖2.19	一維信號f之Opening示意圖	23
圖2.20	二維影像訊號之Opening示意圖	23
圖2.21	物件集合X對SE集合B進行Closing示意圖	23
圖2.22	一維信號f之Closing示意圖	24
圖2.23	二維影像訊號之Closing示意圖	25
圖2.24	一維信號f之WTH示意圖	25
圖2.25	一維信號f之BTH示意圖	26
圖2.26	使用WTH正規化不規則背景之應用示意圖	27
圖2.27	使用BTH去除不規則背景之應用示意圖	27
圖2.28	使用Top-hat進行對比加強之應用示意圖	28
圖2.29	靜態影像邊緣萃取步驟	29
圖2.30	本文在型態影像學中所使用之SE	30
圖2.31	型態影像學對比加強之結果（CameraMan）	30
圖2.32	型態影像學對比加強之結果（Miss America）	31
圖2.33	型態影像學影像輪廓邊緣偵測之結果	32
圖2.34	Quad decomposition示意圖	32
圖2.35	本文提出之影像邊緣加強法之效果	34
圖2.36	本文所提出之雜訊遮罩	35
圖2.37	本文提出之雜訊去除之效果	35
圖2.38	輪廓邊緣偵測性能比較（CameraMan）	37
圖2.39	輪廓邊緣偵測性能比較（Girl）	38
圖2.40	輪廓邊緣偵測性能比較（MRI）	39
圖3.1	灰階圖形轉換類似地形圖之示意圖	45
圖3.2	分水嶺演算法注水示意圖	46
圖3.3	蓄水池間擴展與碰撞示意圖	48
圖3.4	分水嶺演算法範例與結果：血球	49
圖3.5	分水嶺演算法範例與結果：別墅	49
圖3.6	分水嶺演算法範例與結果：桌球	49
圖3.7	靜態影像物件切割步驟	51
圖3.8	全域影像切割之生長點之植入示意圖	52
圖3.9	指定物件切割之生長點之植入示意圖	53
圖3.10	區域生長之八鄰居搜尋順序示意圖	53
圖3.11	區域生長之八鄰居搜尋結果示意圖	54
圖3.12	區域生長之邊緣控制之重要性示意圖	55
圖3.13	全域切割之區域生長結果範例	56
圖3.14	指定物件切割之區域生長結果範例	56
圖3.15	區域結合之佔據邊緣步驟結果範例	57
圖3.16	區域間之邊界示意圖	58
圖3.17	區域結合之結果範例	58
圖3.18	區域結合之結果範例：Table Tennis	60
圖3.19	區域結合之結果範例：Girl	61
圖3.20	區域結合之結果範例：MRI	62
圖4.1	動態影像物件追蹤步驟	65
圖4.2	計算基準點之切割示意圖	67
圖4.3	本文所提出之多重物件影像追蹤演算法流程圖	69
圖4.4	移動式攝影機影像追蹤範例	70
圖4.5	複雜背景影像追蹤範例一	72
圖4.6	複雜背景影像追蹤範例二	73
圖4.7	移動式攝影機情境之多重物件追蹤範例	74
圖6.1	Model原始圖像之邊緣特徵萃取範例(高斯雜訊)	80
圖6.2	Peppers原始圖像之邊緣特徵萃取範例(高斯雜訊)	81
圖6.3	Aquitaine原始圖像之邊緣特徵萃取範例(Salt & Peppers雜訊)	82
圖6.4	Lena原始圖像之邊緣特徵萃取範例(Salt & Peppers雜訊)	83
圖6.5	針對水平移動之臉進行追蹤	85
圖6.6	針對持續大幅度變化之臉進行追蹤	86
圖6.7	針對小幅度變化之臉進行追蹤	87
圖6.8	對於面積持續改變之物件進行追蹤	88
圖6.9	對於快速移動之物件進行追蹤	89

表目錄
表2.1	邊緣加強模式	33

[1]	B.L. Tseng, C.T. Lin, and J.R. Smith, "Real-time video surveillance for traffic monitoring using virtual line analysis," Proc. of IEEE Int. Conf. Multimedia and Expo, vol. 2, pp. 541-544, 2002.

[2]	J. Wang, A. Trubuil, and C. Graffign, "3D biological object detection and labeling in multidimensional mocroscopy imaging," Proc. of IEEE Int. Conf. Image Analysis and Processing, pp. 215-220, 2001.

[3]	G.L. Foresti, L. Marcenaro, and C.S. Regazzoni, "Automatic detection and indexing of video-event shots for surveillance applications," IEEE Trans. Multimedia, vol. 4, pp. 459-471, 2002.

[4]	T. Sikora, "The MPEG-4 video standard verification model," IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 19-31, 1997.

[5]	F. Nack and A.T. Lindsay, "Everything you wanted to know about MPEG-7: Part 2," IEEE Trans. MultiMedia, vol. 6, pp. 64-73, 1999.

[6]	URL: http://wwwqbic.almaden.ibm.com

[7]	S. Kay and G. Lemay, "Edge detection using the linear model," Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing '84. , vol. 9, pp. 577-580, Mar. 1984. 

[8]	Y. Neuvo, P. Heinonen, and I. Defee, "Linear-median hybrid edge detectors," IEEE Trans. Circuit and Syst., vol. 34, no. 11, pp. 1337-1343, 1987.

[9]	X.D Song and Y. Neuvo, "Robust edge detector based on morphological filters," Proc. Int. Conf. Circuits and Syst., vol. 1, pp. 332-335, June 1991.

[10]	X.F. Zhang and H. Burkhardt, "Grouping edge points into line segments by sequential Hough transformation," Proc. 15th Int. Conf. Pattern Recognition 2000, vol. 3, pp. 672-675, Sept. 2000.

[11]	T.H. Hong and A. Rusenfeld, “Compact Region Extraction Using Weighted Pixel Linking in a Pyramid,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, no. 2, pp. 222-229, Mar, 1984.

[12]	S. Menet, P. Saint-Marc, G. Medioni, "Active contour models: overview, implementation and applications," IEEE Int. Conf. Systems, Man and Cybernetics, pp. 194-199, Nov. 1990.

[13]	K. Vincent and P. Soille, "Watersheds in digital spaces: an efficient algorithm based on immersion simulations," IEEE Trans. Pattern Analysus and Machine Intelligence, vol. 13, no. 6, pp. 583-598, June 1991.

[14]	J.S. DaPonte and M.D. Fox, "Enhancement of chest radiographs with gradient operators," IEEE Trans. Medical Imaging, vol. 7, no. 2, pp. 109-117, June, 1988.

[15]	D. Lee, T. Pavlidis, and K. Huang, "Edge detection through residual analysis," Proc. Computer Society Conf. Computer Vision and Pattern Recognition, pp. 215-222, June 1988.

[16]	J. Serra, Image Analysis and Mathematical Morphology, New York: Academic. 1982.

[17]	M. Kass, A. Witkin, and D. Terzopoulos, "Snakes: active contour models," Int. J. Comput. Vision, vol. 1, pp. 321-331, 1988.

[18]	D.J. Williams and M. Shah, "A fast algorithm for active contours and curvature estimation," CVGIP: Image Understanding, vol. 55, no. 1, pp. 14-26, 1992.

[19]	K.-M. Lam and H. Yan, "Fast greedy algorithm for active contours," Electronics Lett., vol. 30, no. 1, pp. 21-23, 1994.

[20]	K.-M. Lam and H. Yan, "Locating head boundary by snakes," Proc. of Int. Symp. Speech, Image Processing and Neural Networks, vol. 1, pp. 17-20, 1994.

[21]	A.R. Mirhosseini and H. Yan, "A optimally fast greedy algorithm for active contours," Proc. of IEEE Int. Symp. Circuits and Systems, vol. 2, pp. 1189-1192, 1997.

[22]	C.P. Huang, “Real-time Image Process in the Small-size Robot Soccer System,” Master Thesis of Tamkang University, 2002.

[23]	Richardson and E.G. Iain, H.264 and MPEG-4 video compression : video coding for next-generation multimedia, Chichester: Wiley, 2003.

[24]	M. Ghanbari, Video coding : an introduction to standard codecs, London: Institution of Electrical Engineers, 1999.

[25]	Richardson and E.G. Iain, Video codec design : developing image and video compression systems, Chichester: Wiley, 2002.

[26]	W. K. Pratt, Digital Image Processing, New Tork: Wiley Interscience, 1978.

[27]	V. S. Nalwa, A Guided Tour of Computer Vision, AT&T Bell Laboratories, 1993.

[28]	R. C. Gonzalez and P. Wintz, Digital Image Processing, Addison-Wesley, England, 1992.

[29]	C. H. Henry Chu and E. J. Delp, "Impulsive noise suppression and background normalization of electrocardiogram signals using morphological operators," IEEE Trans. Biomedical Engineering, Vol. 36, No. 2, pp. 262-273, Feb. 1989.

[30]	T. Chen, Q. H. Wu, R. Rahmani-Torkaman, and J. Hughes, "A pseudo top-hat mathematical morphological approach to edge detection in dark region," Pattern Recognition 35, pp.199-210, 2002.

[31]	J. H. Bosworth and S. T. Acton, "Morphological Image Segmentation by Local Monotonicity," Proc. Conf. on Signals, Systems, and Computers, Vol 1 , pp.53-57, Oct. 1999.

[32]	M. Basu, "Gaussian-Based Edge-Detection Methods-A Survey," IEEE Trans. System, Man, and Cybernetics-Part C: Application and Reviews, Vol. 32, No. 3, pp.252-260, Aug. 2002.

[33]	A. Trujillo, "Thin Edge Detector,” Proc. Int. Conf. on Image Analysis and Processing, pp. 1051-1054, Sept. 1999.

[34]	M. M. Ratnam, "Automatic Edge Detection in Noisy Fringe Patterns," Proc. Int. Symp. Signal Processing and its Applications, Vol. 1, pp. 140-143, Aug. 2001.

[35]	S. Shah and P. S. Sastry, "Fingerprint Classification Using a Feed-back-Based Line Detector," IEEE Trans. Systems, Man and Cybernetics, Part B, Vol. 34, No. 1, pp. 85-94, Feb. 2004.

[36]	J. E. Abdou, "Quantitative methods of edge detection," USC Report, 830, July, 1978.

[37]	Soille, Morphological image analysis: principles and applications, Springer, 1999.

[38]	J. Yoo, C.A. Bouman, E.J. Delp, E.J. Coyle, "The nonlinear prefltering and difference of estimates approaches to edge detection," CVGIP: Graph. Models Image Process, pp. 140-159, 1993.

[39]	R.C. Hardie, C. Boncelet, "LUM filters: a class of rank-order-based filters for smoothing and sharpening," IEEE Trans. Signal Processing, vol. 41, No. 3, pp. 1061-1076, March 1993.

[40]	J. Huddleston and J. Ben-Arie, "Grouping edgels into structural entities using circular symmetry, The distributed Hough transform and probabilistic nonaccidentalness," J. Comput. Vis., Graph., Image Process: Image Understand, vol. 57, o. 2, pp. 227–242, Mar. 1993.

[41]	V. Murino, C. S. Regazzoni, and G. L. Foresti, "Grouping as a searching process for minimum-energy configurations of labeled random fields," Computer Vision Image Understanding. New York: Academic, 1996, pp. 157–174.

[42]	T. Kanungo, B. Dom, W. Niblac, and D. Steele, "A fast algorithm for MDL-based multi-band image segmentation," Proc. IEEE Computer Vision Pattern Recognition, Seattle, WA, June 1994, pp. 609–616.


[43]	J. Shi and J. Malik, "Normalized cuts and image segmentation," Proc. 1997 IEEE Computer Soc. Conf. Computer Vision Pattern Recognition, San Juan, Puerto Rico, June 1997, pp. 731–737.

[44]	B. Moghaddam and A. Pentland, "Probabilistic visual learning for object representation," IEEE Trans. Pattern Anal. Machine Intell., vol. 19, pp. 696–710, July 1997.

[45]	Y.-L. Chang and X. Li, "Adaptive image region-growing," IEEE Trans. Image Processing, vol. 3, pp. 868–872, 1994.

[46]	C. Chu and J. K. Aggarwal, "The integration of image segmentation maps using region and edge information," IEEE Trans. Pattern Anal. Machine Intell., vol. 15, pp. 1241–1252, 1993.

[47]	J. Haddon and J. Boyce, "Image segmentation by unifying region and boundary information," IEEE Trans. Pattern Anal. Machine Intell., vol. 12, pp. 929–948, 1990.

[48]	L. Leonardis, A. Gupta, and R. Bajcsy, "Segmentation of Range Images as the Search for Geometric Parametric Models," Int. J. Computer Vision, vol. 14, no. 3, pp. 253-277, 1995.

[49]	R.V. Babu, K.R. Ramakrishnan, and S.H. Srinivasan, "Video Object Segmentation: A Compressed Domain Approach," IEEE Trans. Circuits and Systems for Video Technology, vol. 14, no. 4, pp. 462-474 , April, 2004.