在視訊處理中，抽取視訊物件 (video object) 是一個活躍的研究主題。在此篇論文中，我們提出的方法是先從視訊資料中抽取出三維分水嶺體積 (3D watershed volume)，再用貝斯方法(Bayesian approach) 來合併它們。我們的方法分成兩個階段。在第一階段中，我們發展兩種不同的技術來產生三維分水嶺體積。第一種是以三維分水嶺轉換為基礎，而三維分水嶺轉換是從二維分水嶺轉換直接延伸而來。第二種方法是結合了二維影像切割與追蹤程序。在第二階段中， 我們使用了馬可夫隨機場 (Markov Random Field) 來建立從第一階段取得三維分水嶺體積的時間與空間上關係，再用貝斯方法來將具有類似運動特徵的三維分水嶺體積合併成所預期的物件。我們方法的優點是能夠考慮每一塊三維分水嶺體積所包含的整體運動資訊。從實驗中顯示出，我們提出的視訊物件抽取技術是十分具有潛力的方法。

Extracting video objects from a video sequence is an active research topic in digital video proc-essing. In this thesis, we proposed a method for video object segmentation by first extracting 3D wa-tershed volumes from the video data, and then merging them with a Bayesian approach. Our method consists of two stages. For the first stage, we have developed two different techniques to partition the video data into a set of 3D watershed volumes. The first one is based on a 3D watershed transforma-tion that is directly extended from the 2D watershed transformation. The second one combines an ini-tial 2D image segmentation with a temporal tracking procedure. For the second stage, we use a Markov random field to model the spatio-temporal relationship among the 3D watershed volumes obtained from the first stage. Then, the desired video objects can be extracted by merging watershed volumes having similar motion characteristics within a Bayesian framework. The major advantage of this method is that it can take into account the global motion information contained in each watershed volume. Our experiments have shown that the proposed method has great potential in extracting mov-ing objects from a video sequence.

CHAPTER 1 INTRODUCTION 1
1.1 Previous Works 1
1.2 Overview of Our Work 3
CHAPTER 2 REVIEW OF WATERSHED TRANSFORMATION 4
2.1 Watershed Transformation 4
2.1.1 Definition of Watershed 5
2.1.2 Watershed Algorithm 6
2.1.3 The Oversegmentation Problem 7
2.2 The Solution to the Oversegmentation Problem 8
2.2.2 Marker-controlled Watersheds 9
2.2.3 Topographic Simplification 10
2.2.4 Hierarchical Watersheds 11
CHAPTER 3 GENERATION OF 3D WATERSHED VOLUMES USING THE 3D SEGMENTATION APPROACH 14
3.1 Previous Works of the 3D Segmentation Approach 15
3.2 The Proposed Algorithm 18
3.3 Experimental Results 24
CHAPTER 4 GENERATION OF 3D WATERSHED VOLUMES USING THE 2D-SEGMENTATION AND TRACKING APPROACH 29
4.1 Previous Works of the 2D Segmentation and Tracking Approach 29
4.2 The Proposed Algorithm 30
4.2.1 Initial Segmentation 31
4.2.2 Temporal Tracking 32
4.3 Experimental Results 36
CHAPTER 5 VIDEO OBJECT EXTRACTION VIA BAYESIAN MERGING OF 3D WATERSHED VOLUMES 41
5.1 Extracting of Features from 3D Watershed Volumes 42
5.2 The Proposed Method 43
5.3 Experimental Results 45
CHAPTER 6 CONCLUSION AND FUTURE WORK 50
6.1 Conclusion 50
6.2 Future Work 51

Bibliography
[Bea89] J.-M. Beaulieu and M. Goldberg, “Hierarchy in Picture Segmentation: A Stepwise Optimiza-tion Approach,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 11(2):150-163, February 1989.
[Bes86] J. Besag, “On the statistical analysis of dirty pictures,” J. Roy. Stat. B, 48(3):259-302, 1986.
[Beu82] S. Beucher, “Watersheds of functions and picture segmentation,” Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, May 1982.
[Cas98] R. Castagno, T.Ebrahimi and M. Kunt, “Video Segmentation Based on Multiple Features for Interactive Multimedia Applications,” IEEE Trans. Circuit Systems. Video Technology, 8(5):562-571, September 1998.
[Cha97] M. M. Chang, A. M. Tekalp, and M. I. Sezan, “Simultaneous Motion Estimation and Scene Segmentation,” IEEE Trans. on Image Processing, 6(9):1326-1333, September 1997.
[Gel00] M. Gelgon and P. Bouthemy, “A Region-Level Motion-Based Graph Representation and La-beling for Tracking a Spatial Image Partition,” Pattern Recognition, 30:725-740, 2000.
[GuL98] C. Gu and M.-C. Lee, “Semiautomatic Segmentation and Tracking of Semantic Video Ob-jects,” IEEE Trans. Circuit Systems. Video Technology, 8(5):572-584, September 1998.
[Hua00] H. C. Huang, C. C. Kao, Y. C. Lin and Y. P. Hung, “Disparity-based view interpolation for multiple-perspective stereoscopic displays,” Proceedings of SPIE Conference on Stereoscopic Dis-plays and Virtual Reality Systems VII, San Jose, California, vol.3957, pp.102-113, January 2000.
[Lio96] C.-Y. Liou and Q.-M. Chang, “Meshed Snakes,” Proc. IEEE Int. Conf. Neural Network (ICNN’96), vol.3, pp1516-1521, 1996.
[Mey94] F. Meyer, “Topographic Distance and Watershed Lines,” Signal Processing, 38, pp. 113-125, 1994.
[Mey90] F. Meyer and S. Beucher, “Morphological Segmentation”, Journal of Visual Communication and Image Representation, vol. 1, no. 1, pp. 21-46, 1990.
[Mur85] D. W. Murray and B. F. Buxton, “Scene Segmentation from Visual Motion Using Global Optimiztion,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 9:384-401, July 1985.
[Naj96] L. Najman and M. Schimitt, “Geodesic Saliency of Watershed Contours and Hierarchical Segmentation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 18(12):1163-1173, De-cember 1996.
[Ngu00] H. T. Nguyen, M. Worring and A. Dev, “Detection of Moving Objects in Video Using a Ro-bust Motion Similarity Measure,” IEEE Trans. on Image Processing, 9(1):137-141, January 2000.
[Pal93] N. R. Pal and S. K. Pal, “A Review of Image Segmentation Techniques,” Pattern Recognition, vol. 26, no. 9, pp. 1277-1294, 1993.
[Par93] M. Pardas, P. Salembier and L. Torres, “3D Morphological Segmentation for Image Sequence Processing”, IEEE Winter Workshop on Nonlinear Digital Signal Processing, pp.6.1.3.1-6.1.3.6, 1993.
[Par94] M. Pardas, P. Salembier, “3D Morphological Segmentation and Motion Estimation for Image Sequences,” Signal Processing, 38, pp. 31-43, 1994.
[Pat01] I. Patras, E. A. Hendriks and R. L. Lagendijk, “Video Segmentation by MAP Labeling of Watershed Segments,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 23(3):326-332, March 2001.
[Rou84] P.J. Rousseeuw, “Least Median of Squares Regression,” J. Amer. Statist. Assoc., 79, pp.871-880, 1984.
[Sal94] P. Salembier and M. Pardas, “Hierarchical Morphological Segmentation for Image Sequence Coding,” IEEE Trans. on Image Processing, 3(5):639-651, September 1994.
[Sch98] M. Schmitt, “Response to the Comment on ‘Geodesic Saliency of Watershed Contours and Hierarchical Segmentation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 20(7):764-768, July 1998.
[Vin93] L. Vincent, “Morphological Grayscale Reconstruction in Image Analysis: Applications and Efficient Algorithms,” IEEE Trans. on Image Processing, 2(2):176-201, April 1993.
[Vin91] L. Vincent and P. Soille, “Watersheds in Digital Spaces: An Efficient Algorithm Based on Immersion Simulations,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 13(6):583-598, June 1991.
[Wan97] D. Wang. “A Multiscale Gradient Algorithm for Image Segmentation Using Watersheds,” Pattern Recognition, 30(12):2043-2052, 1997.
[Wan98] D. Wang, “Unsupervised Video Segmentation Based on Watershed and Temporal Track-ing,” IEEE Trans. Circuit Systems Video Technology, 8(5):539-546, September 1998.
[Wan94] J. Y. A. Wang and E. H. Adelson, “Represent Moving Images with Layers,” IEEE Trans. on Image Processing, 3(5):625-637, September 1994.
[WuK93] S. F. Wu and J. Kittler, “A Gradient-Based Method for General Motion Estimation and Segmentation,” Journal of Visual Communication and Image Representation, Vol. 4, No. 1, pp22-38, March 1993.