臺灣博碩士論文加值系統

在多媒體應用中，對於視訊影像中的各個物件分別做處理是非常需要的。因此，從視訊影像序列中萃取出物件的視訊切割技術，是一個非常重要的研究議題。
目前的視訊切割技術可以概分為兩大類：先時間後空間，及先空間後時間。在研究中發現，過去所提出的的技術有許多的缺點以及實行上的困難。在先時間後空間技術上的缺點有: １）運動參數的估測需要非常高的運算量，２）子物件的切割增加運算上的複雜度，３）無法確認物件切割的完整性。在先空間後時間技術上，利用空間資訊的區塊合併和區塊間相似性的測量，都非常難以處理。
本文提出一個先時間後空間的輪廓切割的新方法。在時間切割方面，我們定義了板塊運動活性(motion activity)以分離出背景(background)和非背景(non-background)的區域。為了使切割的結果更接近真實物件的邊緣，板塊的大小由大到小逐次遞減，並以遞迴方式逐步削去背景區域。
針對時間切割的粗略輪廓，我們進一步利用空間的資訊以削去屬於背景的區塊。本文發展了一個以最大事後機率(Maximum A Posteriori probability─MAP) 為準則的估測法則，並設計了五種區塊型態，藉著MAP準則，以判斷粗略輪廓上區塊之型態，以找出屬於背景的區塊。
實驗顯示本論文所提出的新方法，不論影像的複雜度如何，都可以得到非常好的切割結果，其計算成本也相當地低，同時也避免了人為訂定的臨界值。

Manipulating video objects individually from a video sequence is very desirable for multimedia applications. Therefore, video segmentation, which extracts an object from a video sequence, is a critical technique for these applications.
The current video segmentation algorithms can be roughly classified into two categories: temporal-to-spatial and spatial-to-temporal approaches. There are several problems in both approaches: 1) the estimation of motion parameters is high computation, 2) the segmentation of sub-objects increases considerable amount of computational complexity, 3) a complete segmentation of object is not guaranteed. In spatial-to-temporal approach, regions merging by spatial information and the similarity measure of regions are very difficult to process. This thesis presents a new temporal-to-spatial technique for silhouette segmentation to alleviate the problems.
In temporal segmentation, we use a motion activity for a patch to separate background and non-background regions. In order to achieve better accuracy, the size of a patch is reduced progressively, and the background areas are pared off iteratively.
After the temporal segmentation, we obtain the coarse contour. The spatial information is then used to further pare off the background regions. We develop a new estimation algorithm based on a MAP (Maximum A Posteriori probability) criterion. We design five patterns and use MAP criterion to classify the block types along the boundary of temporal segmentation result. The classification result is then used to extract the background areas.
The simulation results indicate that the new method achieve very good performance with low computational cost. In addition, the threshold values are calculated automatically rather than determined experimentally in the conventional techniques.

Acknowledgements.............................................I
摘要.........................................................II
Abstract.....................................................IV
Contents.....................................................VI
List of Figures..............................................VII
Chapter 1 Introduction.......................................1
1.1Development of Video Coding.........................1
1.2Motivation..........................................6
1.3Proposed Methods and Contributions..................8
1.4Organization of Thesis..............................11
Chapter 2 Previous Works of Video Segmentation...............13
2.1Temporal-to-Spatial Approach........................13
2.2Spatial-to-Temporal Approach........................17
2.3The Observations from Previous Works................21
Chapter 3 Proposed Mesh-Based Temporal-Spatial Silhouette
Segmentation.......................................23
3.1Overview of the Proposed Method.....................23
3.2Temporal Measure and Segmentation...................27
3.3Spatial Silhouette Segmentation Using MAP estimation....................................................38
3.4The Threshold Decision..............................53
3.5The Proposed Algorithm..............................56
Chapter 4 Simulation Results and Discussions.................61
Chapter 5 Conclusions and Future Researches..................68
5.1Conclusions.........................................68
5.2Future Works........................................70
5.2.1Advance Video Segmentation Technique................70
5.2.2Shape Description and Coding........................71
5.2.3Object Motion Estimation and Compensation...........71
5.2.4Construction of Object Video Coding System..........71
Reference....................................................72

1.H.G. Musmann, M.H. Hotter and J. Ostermann, “Object-oriented analysis-synthesis coding of Moving image”, Signal Processing: Image Communication, Vol. 1, No. 2, Oct. 1989, pp. 117-158.
2.M. Hotter, “Object-oriented analysis-synthesis coding based on moving two-dimensional object”, Signal Processing: Image Communication, Vol. 2, No. 4, Dec. 1990, pp. 409-428.
3.N. Diehl, ” Object-oriented motion estimation and segmentation in image sequences”, Signal Processing: Image Communication, Vol. 3, No. 1, Feb. 1991, pp. 23-56.
4.F. Moscheni, S. Bhattacharjee and M. Kunt, ” Spatiotemporal segmentation based on region merging”, IEEE Trans. Pattern analysis and Machine Intelligence, Vol. 20, No. 9, Sept. 1998, pp. 897-915.
5.R. Szeliski and H. Shum, ” Motion estimation with quadtree splines”, IEEE Trans. Pattern analysis and Machine Intelligence, Vol. 18, No. 12, Dec. 1996, pp. 1199-1211.
6.P. salembier, L. Torres, F. Meyer and C. Gu, ” Region-based video coding using mathematical morphology”, Proc. IEEE, Vol. 83, No. 6, June 1995, pp. 843-857.
7.J.Y.A. Wang and E.H. Adelson, ” Spatiotemporal segmentation of video data”, SPIE Proc. Image and Video Processing II, Vol. 2182, San Joes, Calif., Feb. 1994.
8.J.W. Park and S.U. Lee, ” Joint image segmentation and motion estimation for low bit rate video coding”, Proc. ICIP’96, Vol. 2, Lausanne, Switzerland, Sept. 1996, pp.501-504.
9.C.S. Won, “ A Block-Based MAP Segmentation for Image Compressions”, IEEE Trans. Circuits and Systems Video Technology, Vol. 8, No. 5, Sept. 1998, pp.592-601.
10.C.S. Won and D.K. Park, “ Image block classification and variable block size segmentation using a model fitting criterion”, Opt. Eng., Vol. 35, Aug. 1997, pp. 2204-2209.
11.P. Salembier, P. Brigger, J.R. Casas and M. Pardas, ” Morphological Operators for image and video compression”, IEEE Trans. Image Processing, Vol. 5, No. 6, June 1996, pp.881-897.
12.L. Vincent and P. Soille, ”Watershed in digital space: an efficient algorithm based on immersion simulations”, IEEE Trans. Pattern analysis and Machine Intelligence, Vol. 13, No. 6, June 1991, pp. 583 -598.
13.P. Strobach, ” Tree-structured scene adaptive coder”, IEEE Trans. Communication, Vol. 38, Apr. 1990, pp. 477-486.
14.N. Doulamis, A. Doulamis, D. Kalogeras and S. Kollias, ” Low bit-rate coding of image sequences using adaptive regions of interest”, IEEE Trans. Circuits and Systems Video Technology, Vol. 8, No. 8, Dec. 1998, pp. 928-934.
15.D. Cortez, P. Nunes, M.M.D. Sequeira and F. Pereira, "Image segmentation towards new image representation methods", Signal Processing: Image Communication, Vol. 6, 1995, pp. 485-498.
16.N. Paragios and G. Triritas, ”Adaptive detection and localization of moving objects in image sequences”, Signal Processing: Image Communication, Vol. 14, 1999, pp. 277-296.
17.H. Derin and H. Elliott, “Modeling and Segmentation of noisy and textured image using Gibbs random field”, IEEE Trans. Pattern analysis and Machine Intelligence, Vol. PAMI-9, No. 1, 1987, pp. 39-55.
18.C.S. Won and H. Derin, “ Unsupervised segmentation of noisy and textured image using Markov random field”, CVGIP: Graphical models Image Processing, Vol. 54, No. 4, 1992, pp. 308-328.
19.S. Geman and D. Geman, ”Stochastic relaxation, Gibbs distributions, and Bayesian restoration of image”, IEEE Trans. Pattern analysis and Machine Intelligence, Vol. PAMI-6, Nov. 1984, pp.721-741.
20.H. Derin and W. Cole, ”Segmentation of textured image using Gibbs random field”, Computer Vision, Graphics and Image Processing, Vol. 35, 1986, pp. 72-98.
21.R. Koenen, F. Pereira, and L. Chiariglione, “ MPEG-4: Context and Objective”, Signal Processing: Image Communication Special Issue on MPEG-4, Part 1, Vol. 9, No. 4, May 1997, pp. 295-304.
22.L. Chiariglione, “ MPEG and multimedia communications”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 7, No.1, Feb. 1997, pp. 5-18.
23.C.M. Kuo, C.H. Hsieh and M.S. Hung, "A New Mesh-Based Motion Compensation Algorithm for Very Low Bit Rate Coding", International Conference on Image Processing 1999.
24.Michael M. Chang, A. Murat Tekalp, and M. Ibrahim Sezan, ” Simultaneous Motion Estimation and Segmentation”, IEEE Trans. on Image Processing, Vol. 6, No. 9, Sept. 1997, pp. 1326-1333.
25.Jae-Gark Choi, Si-Woong Lee, and Seong-Dae Kim, “Spatio-Temporal Video Segmentation Using a Joint Similarity Measure”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 7, No. 2, Apr. 1997, pp. 279-286.
26.Demin Wang, “Unsupervised Video Segmentation Based on Watersheds and Temporal Tracking”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 8, No. 5, Sept. 1998, pp. 539-546.
27.Rob Koenen, “MPEG-4 Overview - Dublin revision”, Source of Requirements/ Audio/Delivery/SNHC/Systems/Video/Test, ISO/IEC JTC1/SC29/WG11/N2323, July 1998.
28.Klaus Diepold, “MPEG-4 Applications Document - Dublin revision”, Source of Requirements Group, ISO/IEC JTC1/SC29/WG11/N2322, MPEG 98, July 1998.
29.“MPEG-4 Requirements, version 8 (Dublin revision)”, Source of Requirements Group, ISO/IEC JTC1/SC29/WG11/N2321, July 1998.
30.Stephan Herrmann, Hubert Mooshofer, Harald Dietrich, and Walter Stechele, “A Video Segmentation Algorithm for Hierarchical Object Representations and Its Implementation”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 8, Dec. 1999, pp. 1204-1215.
31.Philippe Salembire, Patrick Brigger, Josep R. Casas and Montse Pardas, “Morphological Operators for Image and Video compression”, IEEE Trans. On Image Process, Vol. 5, No. 6, June 1996, pp. 881 -898.
32.P. Salembier and F. Marques, “Region-based representations of image and video segmentation tools for multimedia services”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 8, Dec. 1999, pp. 1147 -1169.
33.Roberto Castagno, Touradj Ebrahimi and Murat Kunt, “Video Segmentation Based on Multiple Features for Interactive Multimedia Applications”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 8, No. 5, Sept. 1998, pp. 1190 -1203.
34.Thomas Meier and King N. Ngan, “Video Segmentation for Content-Based Coding”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 8, Dec. 1999, pp. 1190 -1203.
35.Seung Chul Yoon, Krishna Ratakonda and Narendra Ahuja, “Low Bit-Rate Video Coding with Implicit Multiscale Segmentation”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 7, Oct. 1999, pp. 1115 -1129.
36.Y. Altunbasak, E. Eren and A. Murat Tekalp, “Region-based affine motion segmentation using color information”, Graphical Models and Image Processing, Vol. 60, No. 1, Jan. 1998, pp. 13-23.
37.B. Gunsel, M. Ferman and A. Murat Tekalp, “Temporal video segmentation using unsupervised clustering and semantic object tracking”, J. Electronic Imaging, Vol. 7, No. 3, July 1998. pp. 592-604.
38.G. D. Borshukov, G. Bozdagi, Y. Altunbasak and A. Murat Tekalp, “Motion segmentation by multi-stage affine classification”, IEEE Trans. Image Processing, Vol. 6, No. 11, Nov. 1997, pp. 1591-1594.
39.E. Saber and A. Murat Tekalp, “Region-based affine shape matching for automatic image annotation and query-by-example”, Visual Comm. and Image Representation, Vol. 8, No. 1, Mar. 1997, pp. 3-20.
40.T. Sikora, “The MPEG-4 video standard verification model “, IEEE Trans. Circuits and Systems for Video Technology, Vol. 7, No. 1, Feb. 1997, pp 19 —31.
41.E.D. Scheirer, R. Vaananen and J. Huopaniemi, “AudioBIFS: Describing audio scenes with the MPEG-4 multimedia standard “, EEE Trans. Multimedia I, Vol. 1, No. 3, Sept. 1999, pp. 237 —250.
42.G.A. Abrantes and F. Pereira, “MPEG-4 facial animation technology: survey, implementation, and results “, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 2, Mar. 1999, pp. 290 —305.
43.R. Schafer, “MPEG-4: a multimedia compression standard for interactive applications and services”, Electronics & Communication Engineering Journal, Vol. 10, No. 6, Dec. 1998, pp 253—262.
44.N. Brady, “MPEG-4 standardized methods for the compression of arbitrarily shaped video objects”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 8, Dec. 1999, pp. 1170 —1189.
45.F. Pereira and T. Alpert, “MPEG-4 video subjective test procedures and results “, IEEE Trans. Circuits and Systems for Video Technology, Vol. 7, No. 1, Feb. 1997, pp. 32 —51.
46.Munchurl Kim, Jae-Gark Choi, Daehee Kim, Hyung Lee, Myoung-Ho Lee, Chieteuk Ahn and Yo-Sung Ho, “A VOP generation tool: automatic segmentation of moving objects in image sequences based on spatio-temporal information”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 8, Dec. 1999, pp. 1216 —1226.
47.R. Talluri, K. Oehler, T. Barmon, J.D. Courtney, A. Das and J. Liao, “A robust, scalable, object-based video compression technique for very low bit-rate coding”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 7, No. 1, Feb. 1997, pp. 221 —233.
48.J. Kneip, B. Schmale and H. Moller, “Applying and implementing the MPEG-4 multimedia standard”, IEEE Micro Vol. 19, No. 6, Nov.-Dec. 1999, pp. 64 —74.
49.T. Sikora, “MPEG digital video-coding standards “, IEEE Signal Processing, Vol. 14, No. 5, Sept. 1997, pp 82 —100.
50.J.R. Olm, “Encoding and reconstruction of multiview video objects”, IEEE Signal Processing, Vol. 16, No. 3, May 1999, pp. 47 —54.
51.P. Salembier and F. Marques, “Region-based representations of image and video: segmentation tools for multimedia services”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 8, Dec. 1999, pp. 1147 —1169.
52.A. Kaup, “Object-based texture coding of moving video in MPEG-4”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 1, Feb. 1999, pp. 5 —15.
53.P. Kauff and K. Schuur, “Shape-adaptive DCT with block-based DC separation and /spl Delta/DC correction”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 8, No. 3, June 1998, pp. 237 —242.
54.T. Sikora and B. Makai, “Shape-adaptive DCT for generic coding of video”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 5, No. 1, Feb. 1995, pp. 59 —62.
55.A.K. Katsaggelos, L.P. Kondi, F.W. Meier, J. Ostermann and G.M. Schuster, “MPEG-4 and rate-distortion-based shape-coding techniques”, Proceedings of the IEEE, Vol. 86, No. 6, June 1998, pp. 1126 —1154.
56.E.A. Edirisinghe, J. Jiang and C. Grecos, “Object boundary padding technique for improving MPEG-4 video compression efficiency”, Electronics Letters, Vol. 35, No. 17, Aug. 1999, pp. 1453 —1455.
57.J. Stander, R. Mech, and J. Ostermann, “Detection of moving cast shadows for object segmentation”, IEEE Trans. Multimedia, Vol. 1, No. 1, March 1999, pp. 65 —76.
58.E. Francois, J.-F. Vial and B. Chupeau, “Coding algorithm with region-based motion compensation “, IEEE Trans . Circuits and Systems for Video Technology, Vol. 7, No. 1, Feb. 1997, pp. 97 —108.
59.Weiping Li, H.Q. Cao, Shipeng Li, Fan Ling, S.A. Segan, Hongqiao Sun, J.P. Wus and Ya-Qin Zhang, “A video coding algorithm using vector-based techniques”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 7, No. 1, Feb. 1997, pp. 146 —157.
60.Joo-Hee Moon, Ji-Heon Kweon and Hae-Kwang Kim, “Boundary block-merging (BBM) technique for efficient texture coding of arbitrarily shaped object”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 9, No. 1, Feb. 1999, pp. 35 —43.
61.Yao Wang and Ouseb Lee, “Active mesh-a feature seeking and tracking image sequence representation scheme”, IEEE Trans. Image Processing, Vol. 3, No. 5, Sept. 1994, pp. 610 —624.
62.Yao Wang, O. Lee and A. Vetro, “Use of two-dimensional deformable mesh structures for video coding. II. The analysis problem and a region-based coder employing an active mesh representation”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 6, No. 6, Dec. 1996, pp. 647 —659.
63.Yao Wang and O. Lee, “Use of two-dimensional deformable mesh structures for video coding .I. The synthesis problem: mesh-based function approximation and mapping”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 6, No. 6 , Dec. 1996 , pp. 636 —646.
64.Yao Wang and Jorn Ostermann, “Evaluation of Mesh-Based Motion Estimation in H.263-Like”, IEEE Trans. Circuits and Systems for Video Technology, Vol. 8, No. 3, June 1998, pp. 243 —252.