近來，Chien等人提出了一個有效的預測分水嶺式的視訊切割法。本篇論文提出了一個改良式預測分水嶺的方法來切割影像物件。歸因於從目前的視訊畫面繼承更多的分割結果，我們的改良演算法與Chien等人的方法相比需要較少的計算成本。此外，我們還提供了一個有效的區域融合策略來解決過度切割的問題。最後，我們提出一個新的自動更新方法，基於區域配對累積誤差標準，來中斷錯誤累積的問題。實驗結果顯示本改良方法在計算時間與切割品質的進步。在五組灰階視訊影像序列下，本方法的平均執行時間對應傳統的分水嶺切割法與Chien等人的方法的改良率分別為77.4%和41.8%。

Recently, Chien et al. presented an efficient predictive watershed-based video segmentation algorithm. This thesis presents an improved predictive watershed method for segmenting objects. Due to inheriting more segmentation results from the current frame, our proposed improved method needs less computation e®ort when compared to Chien et al.'s method. In addition, an e±cient region merging strategy is employed to alleviate the over-segmentation problem. Finally, a new efficient automatic renewal scheme, which is based on the integrated error of region-pairs accumulation error criterion, is presented to interrupt the error propagation. Experimental results demonstrate the execution time and quality advantages of our proposed improved algorithm. Under five video sequences, the execution-time improvement ratios of our proposed algorithm over the traditional watershed-based approach and the the previous algorithm by Chien et al. are 77.4% and 41.8%, respectively, in average.

[1] MPEG-4 Video Verification Model Version 18.0, ISO/IEC JTC1/SC29/WG11N3908, 2001.

[2] T. Sikora, "The MPEG-4 video standard verification model", IEEE Transactions on
Circuits and Systems for Video Technology, Vol.7(1), 1997, pp. 19-31.

[3] A. M. Tekalp, Digital Video Processing, Englewood Cliffs, NJ:Prentice-Hall, 1995.

[4] I. Pratikakis, I. Vanhamel, H. Sahli,B. Gatos, and S. J. Perantonis, "Unsupervised
watershed-driven region-based image retrieval", in IEE Proceedings Vision, Image
and Signal Processing, vol. 153, issue 3, 2002 ,pp. 313-322.

[5] 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(7), 2002, pp. 577-586.

[6] S. Y. Chien, Y. W. Huang, and L. G. Chen, "Predictive watershed: a fast watershed
algorithm for video segmentation", IEEE Transactions on Circuits and Systems for
Video Technology., Vol. 13(5), 2003, pp. 453-461.

[7] J. G. Choi, S. W. Lee, and S. D. Kim, "Spatio-temporal video segmentation using
a joint similarity measure", IEEE Transactions on Circuits and Systems for Video
Technology., Vol. 7(2), 1997, pp. 279-286.

[8] F. Dufaux, F. Moscheni, and A. Lippman, "Spatio-temporal segmentation based
on motion and static segmentation", in IEEE International Conference on Image
Processing, vol. 1, 1995 ,pp. 306-309.

[9] H. Gao, W. C. Siu, and C. H. Hou, "Improved techniques for automatic image
segmentation", IEEE Transactions on Circuits and Systems for Video Technology.,
Vol. 11(12), 2001, pp. 1273-1280.

[10] S. Herrmann, H. Mooshofer, H. Dietrich, and W. Stechele, "A video segmentation al-
gorithm for hierarchical object representations and its implementation", IEEE Trans-
actions on Circuits and Systems for Video Technology., Vol. 9(8), 1999, pp. 1204-
1215.

[11] T. Meier and K. N. Ngan, "Video segmentation for content-based coding", IEEE
Transactions on Circuits and Systems for Video Technology., Vol. 9(8), 1999, pp.
1190-1203.

[12] H. Park, T. Schoep°in, and Y. Kim, "Active contour model with gradient directional
information: directional snake", IEEE Transactions on Circuits and Systems for
Video Technology., Vol. 11(2), 2001, pp. 252-256.

[13] I. Patras, E.A. Hendriks, and R.L. Lagendijk, "Video segmentation by MAP label-
ing of watershed segments", IEEE Transactions on Pattern Analysis and Machine
Intelligence., Vol. 23(3), 2001, pp. 326-332.

[14] P. Salembier and , F. Marques, "Region-based representations of image and video:
segmentation tools for multimedia services", IEEE Transactions on Circuits and Sys-
tems for Video Technology., Vol. 9(8), 1999, pp. 1147-1169.

[15] S. Sun, D. R. Haynor, and Y. Kim, "Semiautomatic video object segmentation using
VSnakes", IEEE Transactions on Circuits and Systems for Video Technology., Vol.
13(1), 2003, pp. 75-82.

[16] Y. Tsaig and A. Averbuch, "Automatic segmentation of moving objects in video
sequence: a region labeling approach", IEEE Transactions on Circuits and Systems
for Video Technology., Vol. 12 (7), 2002, pp. 597-612.

[17] D.Wang and C. Labit, "Morphological spatio-temporal simpli‾cation for video image
segmentation", in Signal Processing: Image Communication., Vol. 11, 1997, pp. 161-
170.

[18] D. Wang, "Unsupervised video segmentation based on watersheds and temporal
tracking", IEEE Transactions on Circuits and Systems for Video Technology., 8 (5)
(1998) 539-546.

[19] A. Colombari, A. Fusiello and V. Murino, "Segmentation and tracking of multiple
video objects Pattern Recognition", Pattern Recognition, Vol. 40(4), 2007, pp. 1307-
1317.

[20] E. Y. Kim and K. Jung, "Genetic algorithms for video segmentation", Pattern Recog-
nition, Vol. 38(1), 2005, pp. 59-73.

[21] B. P. Dobrin, T. Viero, and M. Gabbouj, "Fast watershed algorithms: analysis and
extensions", in SPIE Conference on Nonlinear Image Processing V, vol. 2180, 1994,
pp. 209-220.

[22] J. M. Gauch, "Image segmentation and analysis via multiscale gradient watershed
hierarchies", IEEE Transactions on Image Processing., Vol. 8(1), 1999, pp. 69-79.

[23] A. Moga, B. Cramariuc, and M. Gabbouj, "An efficient watershed segmentation
algorithm suitable for parallel implementation", in International Conference on Image
Processing, vol. 2, No. 2, 1995, pp. 101-104.

[24] L. Vincent and P. Soille, "Watershed in digital space: an efficient algorithm based
on immersion simulations", IEEE Transactions on Pattern Analysis and Machine
Intelligence., Vol. 13(6), 1991, pp. 583-598.

[25] D.Wang, "A multiscale gradient algorithm for image segmentation using watershed",
Pattern Recognition, Vol. 30(12), 1997, pp. 2043-2052.

[26] W. H. Equitz, "A new vector quantization clustering algorithm", IEEE Transactions
on Acoustic, Speech, and Signal Processing., Vol. 37(10), 1989, pp. 1568-1575.