數位視訊產品及服務目前正以驚人的速度在民生電子、電腦以及通訊工業上積極發展中。在影像視訊儲存與傳輸上，工業界訂定的標準如早期的JPEG，JBIG，MPEG-1，H.261到MPEG-2，H.263等，開啟了多媒體與數位電視的時代。上述這些視訊壓縮標準是以傳統的波形編碼與以區塊為基礎的方式處理影像視訊。MPEG-4是ISO MPEG組織建立的一個通用且有效率的編碼標準，並於1998年 11 月已制訂了解碼端的國際標準規格。MPEG-4除了融合了MPEG-1 和 MPEG-2 影像編碼功能以外，並首先加入以內容為基礎的視訊編碼方式，其採用以物件為基礎的壓縮方法。影像畫面被分割成一些任意形狀的物件平面，並針對物件進行形狀編碼、移動估計與紋理編碼。使用形狀編碼的目的是為了得到較好的影像品質與增加編碼效益。其中，形狀編碼主要分為位元圖形狀編碼與輪廓形狀編碼兩個大方向。
這篇論文中，在輪廓形狀編碼方面，我們也提出了利用極座標方式來減少形狀點數的新技術。我們利用半徑與角度的關係，提出一種新的取點技巧，在失真性之編碼法方面，我們採取面積失真準則技術以達到重建影像品質與位元率之間的良好權衡。而另一方面方面，我們提出以四分樹為基礎的分割與編碼方式應用於位元圖形狀編碼上。位元圖影像本身具有許多相同圖素區域的關連性，所以，以大區塊為單位，再加上四分樹系統特性，可以簡單地將二位元形狀加以編碼。我們為了再進一步地降低編碼位元率，也提出改良式的四分樹形狀編碼的方法，此技巧不僅保留了四分樹系統的簡單性，在編碼效益上也大大的提升。並且我們在各項技術中做了電腦模擬實驗。從實驗結果驗證了我們提出的形狀編碼技術在失真，無失真，低位元率編碼效益與影像品質都比其他的形狀編碼方法好

Anticipating the rapid convergence of telecommunication, computer, and TV/film industries, the just finalized MPEG-4 standard from ISO standardizes algorithms and tools for coding and flexible representation of audio-visual data to meet the challenges of future multimedia applications. In addition to standard MPEG-1 or MPEG-2 like provisions for efficient coding of conventional image sequence, MPEG-4 enables an efficient coded representation of the video data that can be content based, with the aim to use and present the data in a highly flexible way. To enable the envisioned content-based interactive functionalities, the MPEG-4 video standard introduces the concept of video object planes (VOPs). It is assumed that each frame of an input video sequence is segmented into a number of arbitrarily shaped image regions- each of the regions may possibly cover particular image or video content of interest, i.e., describing physical objects or content within scenes. In contrast to the video source format used for the MPEG-1 and MPEG-2 standards, the video input to be coded by the MPEG-4 is thus no longer considered a rectangular region. The input to be coded can be a VOP image region of arbitrary shape and the shape and location of the region can vary from frame to frame. The concept of VOPs involves the problem of shape representation, motion estimation and texture coding. The purpose of using shape is to achieve better subjective picture quality, increased coding efficiency as well as an object-based video representation. There are mainly two categories for binary shape coding: bitmap-based and contour-based.
In this thesis, we propose the quadtree-based shape coding, which exploits the spatial redundancy for bitmap-based shape coding category. The hierarchical structure provides good performance. For contour-based category, the new scheme with polygon approximation in polar coordinates is conducted. The vertex selection and area distortion criterion techniques are included. Computer simulation is conducted. The proposed shape coding algorithms are expected to make compression more efficient and degradation due to errors more graceful. The proposed schemes provide good rate-distortion trading-off. The results indicate that the subjective quality is improved compared to other shape coding methods

中文目錄
摘要…………….……………………………………………….I
誌謝…………………………………………………………...III
目錄…………………………………………………………...IV
第一章 簡介…………………………………………………..V
第二章 形狀編碼技術………………………………………VII
第三章 極座標形狀編碼與實驗結果……………………….XI
第四章 四分樹形狀編碼與實驗結果………………….….XIII
第五章 結論………………………………………………...XV
英文附錄……………………………………………………...XV
英文目錄
Contents
English Abstract………………………………………………………………………..i
Table of Contents……………………………………………………………………..iii
List of Figures…………………………………………………………………………v
List of Tables………………………………………………………………………...viii
1. Introduction….…………………………………………………………………….1
2. Review of Arbitrary Shape Coding Techniques…..………….……………………5
2.1 Basic Theory…………………………………………………………...…5
2.2 Bitmap-based Shape Coding……………………………………………...6
2.2.1 Context-Based Arithmetic Encoding (CAE) …………………….7
2.2.2 Modified MMR (Modified Modified Read) Coding ………….....9
2.3 Contour-based Shape Coding……………………………………………16
2.3.1 Vertex-based Shape Coding…………………………………….16
2.3.2 Object-Level Relative-Location Dynamic Range Adaptation….20
2.3.3 Vertex-Level Octant-Based Dynamic Range Adaptation……….22
2.2.4 Chain Coding …………………………………………………...24
3. Vertex-Based Shape Coding in Polar Coordinates (VBPC)………….…………..25
3.1 Transformation to Polar Coordinates……………………………………26
3.2 A New Vertex Selection Scheme for Polygon Approximation………….27
3.3 Vertex Subsampling with Area Distortion Criterion…………………….30
3.4 Entropy Coding………………………………………………………….32
3.5 Simulation……………………………………………………………….33
4. Quadtree-based Shape Coding Algorithm……………………………………...54
4.1 Quadtree-based Shape Coding Algorithm (QTSC)……………………...55
4.2 Improvement of the QT-based Shape Coding (IQTSC)…………………58
4.3 Simulation……………………………………………………………..…67
5. Conclusions……………………………………………………………………..77
Bibliography……………………………………………………………………….…79

Bibliography
[1] R. C. Gonzalez and R. E. Woods, Digital Image Processing, Addison-Wesley, 1993.
[2] W. B. Pennebaker and J.L. Mitchell. JPEG: Still Image Data Compression Standard, New York, Van Nostrand Reinhold, 1993.
[3] International Telecommunication Union, "Video codec for audio visual services at p*64 Kbps", ITU-T Recommendation H.261, March 1993.
[4] "ISO/TEC 13818-2 Generic Coding of Moving Pictures and Associated Audio: Recommendation H.262", November 1993.
[5] ITU-T Study Group 15, Working Party 15/1, "Draft ITU-T recommendation H.263 - Video coding for narrow telecommunication channels at below 64 Kbps", Document-LBC-95-, 1995.
[6] ISO/IEC JTC1/SC29/WG11, "ISO/IEC CD 11172: Information Technology", MPEG-1 Committee Draft, December 1991.
[7] ISO/IEC JTC1/SC29/WG11, "ISO/IEC CD 13818: Information Technology", MPEG-2 Committee Draft, December 1993.
[8] ISO/IEC JTCI/SC29/WG11, "Coding of Moving Pictures and Associated Audio Information", MPEG-4 Committee Draft, November 1997.
[9] T. Ebrahimi, "MPEG-4 video verification model; A video encoding/decoding algorithm based on content representation", Signal Processing: Image Communication , pp. 367-384 1997.
[10] ISO/IEC JTCI/SC29/WGII/N2459, "Coding of Moving Pictures and Audio", MPEG-4 Overview, October, 1998
[11] T. Sikora, "The MPEG-4 Video Standard Verification Model ", IEEE Trans. Circuits and Systems for Video Technology, Vol. 7, No.1, pp.19-31, February 1997
[12] N. R. Pal and S. K. Pal, "A review on image segmentation techniques", Pattern Recognition, Vol.26, No.9, pp.1277-1294, 1993.
[13] T. N. Pappas, "An Adaptive Clustering Algorithm for Image Segmentation ", IEEE Trans. on Signal Processing, Vol.40, No.4, pp.901-914, April 1992.
[14] Jone Ostermann. "Methodologies used for evaluation of video tools and algorithms in MPEG-4", Image Communications, Special Issue on MPEG-4, May 1997.
[15] T. Sikora, "MPEG-4 Very Low Bit Rate Video", 1997 IEEE International Symposium on Circuits and System, pp.1440-1443, June 1997.
[16] T. Sikora and L. Chiariglione,"MPEG-4 Video and its Potential for Future Multimedia Services", 1997 IEEE International Symposium on Circuits and System , pp. 1468-1471, June 1997.
[17] P. Gerken, "Object-based analysis-synthesis coding of image sequenced at very low bit rates," IEEE Trans. Circuit and Systems for Video Technonlgy, Vol.4, No.5, pp.228-235, June 1994.
[18] T. Ebrahimi, Ed., "MPEG-4 video verification model version 8.0, International Standards Organization, ISO/IECJTC1/SC29/WG11 MPEG97/N1796, July, 1997.
[19] J. Ostermann, E. S. Jane, Jae-Seob Shin, T. Chen. "Coding of Arbitrarily Shaped Video Objects in MPEG-4", Vol. 1, No.1440, pp.496-499, ICIP 97.
[20] 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.
[21] H. Horie, T. Ozaki, H. Shirai, and Y. Iizuka, "Architectural Design of a Bi-Level Image High Speed CODEC", IEEE Transactions on Circuits and Systems for Video Technology, Vol.4, No.6, pp.527-535, December 1994.
[22] N. Brady. F. Bossen. N. Murphy, "Context-based arthmetic encoding of 2D shape sequences", Special session on shape coding ICIP 97,Santa Barbara, pp.29-31, 1997.
[23] R. J. Qian and M. I. Sezan, "Content-Scalable Shape Represen-tation and coding", Vol.2, No.641, pp.819-823, ICIP 1997.
[24] "Facsimile Coding Schemes and coding Functions for Group 4 Facsimile Apparatus", CCITT Recommendation T.6(1984)
[25] N. Yamaguchi. T. Ida. T. Watanabe. "A Binary Shape Coding Method Using Modified MMR", Special session on shape coding ICIP 97, Santa Barbara, pp.504-507, 1997.
[26] J. W. Stroming, Y. Kang, T. S. Huang, and S. M. Kang, "New architectures for modified MMR shape coding," in Proc. ISCAS'97, Hong Kong, June, pp.1205-1208, 1997.
[27] J. W. Stroming, Y. Kang, T. S. Huang, and S. M. Kang, "New architectures for M4R shape coding," IEEE Transactions on circuits and systems -II: Analog digital processing, Vol. 45, No. 5. pp.556-562, May 1998.
[28] F. W Meier, G. M. Schuster, and A. K. Katsaggelos, " An efficient boundary encoding scheme which is optimal in the rate-distortion sense, " in Proc. Int. Conf. Image Processing, Santa Barbara, CA, pp. II-9-12, 1997.
[29] G. M. Schuster, Gerry Melnikov, and A. K. Katsaggelos, "Vertex-Based Shape Coding", IEEE Signal Processing Magazine, pp.91-108, November 1998.
[30] R. J. Qian and M. I. Sezan, "Content-Scalable Shape Representation and coding",Vol.2, No.641, pp.819-823, ICIP 1997.
[31] K. J. O 'Connell, "Object-adaptive vertex-based shape coding method", IEEE Trans. On Circuits and Systems for Video Technology, Vol.7, No.1, pp.251-255, 1997.
[32] J. Kim and B. L. Evans, "Predicitive shape coding using generic polygon approximation, "in Proc. ISCAS'98. Monterrey, CA, to be published.
[33] J. W. Chung, J, H. Moon and J. K. Kin, "Conditional differential chain coding for lossless representation of object contour", Electronics Letters, Vol. 34, NO. 1, January 1998.
[34] T. Kaneko and M. Okudaira, "Encoding of arbitrary curves based on chain code representation", IEEE Trans Commun, Vol. COM-33, pp.697-707, July 1985.
[35] S. Lee, D. Cho, Y. Cho, S. Son, E. Jang, and J. Shin, "Binary shape coding using 1-D Distance values from baseline, " in Proc. Special Session on Shape Coding, ICIP97, Santa Barbara, CA, pp. I-508-511, 1997.
[36] S. Lee, D. Cho, Y. Cho, S. Son, E. Jang, and J. Shin, "Binary shape coding using Baseline-based Method, " IEEE Transactions on circuits and systems for video technology, Vol. 9, No. 1, pp.44-58, February 1999.
[37] F. H. P. Spaan, R. L. Lagendijk and J. Biemond,"Shape Coding Using Polar Coordinates and the Discrete Cosine Transform", Vol.1, No.1107, pp.516-520, ICIP 1997.
[38] E. Shusterman. and M. Feder, "Image Compression via Improved Quadtree Decomposition Algorithms ", IEEE Transactions on Image Processing. Vol.3, No2, pp.207-215, March 1994.
[39] G. M. Schuster. and A. K. Katsaggelos, "An Optimal Quadtree-Based Motion Estimation and Motion-Compensated Interpolation Scheme for Video Compression ", IEEE Transactions on Image Processing. Vol. 7, No.11, pp.1555-1523, November 1998.
[40] Chil-Cheang Ma and Mei-Juan Chen, "Vertex-based Shape coding in Polar coordinates for MPEG-4", Taiwan Area Network Conference, pp.2B-1-2B-8, Taiwan,R.O.C. November 1998.
[41] Chil-Cheang Ma and Mei-Juan Chen, "Quadtree-based Shape coding Algorithm for MPEG-4", 4th Multimedia Technology and Applications Symposium, pp.137-143, Taiwan, R.O.C. April, 1999.
[42] Chil-Cheang Ma, Mei-Juan Chen, and Po-Yuen Cheng, "Efficient Lossless/Lossy Vertex Selection Shape Coding for Object-based Video Coding", SPIE-The International Society for Optical Engineering, June 1999.
[43] Chil-Cheang Ma, Mei-Juan Chen, and Po-Yuen Cheng, "Efficient Shape Coding Algorithm for Object-Oriented Video in MPEG-4", International Conference on Consumer Electronics, June 1999.