臺灣博碩士論文加值系統

本篇論文提出了一個以鏈碼為基礎且為最理想的編碼法用於壓縮輪廓圖。在鏈碼的表示方法中, 每一個連結方向都需要至少兩個位元來紀錄, 而本篇論文所提出的編碼法只需要一個位元就可以表示每一個連結方向。此外, 這個編碼法能夠很簡易地延伸至具可延展性的表示方式。此表示方式把輪廓圖組織為一個基本層 (base layer) 以及兩個延伸層 (enhancement layer), 如此更適合應用於網路上分層傳輸。本篇論文也提出可容忍失真的壓縮方法, 提供給網路上頻寬或資源較不足的系統或應用程式。
為了表示輪廓圖具可延展性的表現方式, 我們進一步地提出了兩個設計方法。在抽點取樣的方法中, 輪廓的可延展性能夠應用在圖片的尺寸或是圖片的解析度上。而另一輪廓圖近似法則把壓縮比率以及失真程度之間的衡量納入了基本層的設計。根據無失真, 可失真以及具可延展性的輪廓圖壓縮方法, 我們設計了幾個實驗。在無失真的輪廓圖壓縮方面, 我們的編碼法與MPEG-4採用的CAE方法以及差分鏈編碼比較。我們的編碼法不但有較高的壓縮率, 而且可擴充至具可延展性的表示法。在與另一可延展漸次多邊形編碼法做比較, 我們提出的方法簡單卻更有效率。在失真程度Dn = 0.02的情況下, 我們在基本層的表示上可節省約20~30% 的位元量。 換句話說, 我們的方法能夠得到一個所需位元數較少的基本層, 而這正是網路上分層式傳輸重要的一項需求。

In this thesis, we present an optimal chain-code-like representation to code contour shapes; in addition, this representation can be easily extended to as a scalable form which structures shape data as the base layer followed by two enhancement layers. Lossy coding scheme is also presented for low-bit-rate applications.
Two schemes are further presented to achieve scalable coding with two downsized strategies. In the first one, the down-sampling scheme, the scalability can be recognized in both spatial and quality-wise. Another one, called the contour approximation scheme, the tradeoff between encoding cost and resulting distortion is considered. We conducted several experiments for the lossless, lossy and scalable methods. Comparing to the block-based CAE method in MPEG-4 and DCC with arithmetic coder, our lossless method not only has the higher compression ratio with less computation steps, but also can be applied to layered transmission. Comparing to the novel scalable shape coding one, the progressive polygon encoding method, in case of the base layer with distortion Dn = 0.02, our scheme saves about 20~30% amount of bits. That is, we have a smaller size base layer, which is important in layered transmission.

Table of Contents iv
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
Chapter 2 Two-Dimension Shape Coding 3
2.1 Bitmap Coding 3
2.1.1 Context-Based Arithmetic Encoding 4
2.1.2 Modified MMR Shape Coder 5
2.2 Contour Coding 7
2.2.1 Chain Coding 7
2.2.2 Baseline Shape Coding 8
2.2.3 Polygon Approximation 10
2.2.4 Skeleton-Based Shape Coding 11
Chapter 3 Ideal-Segmented Chain Coding 13
3.1 IsCC Shape Representation 13
3.2 Turning Points Classification for Lossy Coding 17
3.3 Shape Reconstruction Using Contour Filling 19
Chapter 4 Scalable IsCC Representation 20
4.1 Down-Sampling Scheme 20
4.1.1 Reduced Ideal Chains 21
4.1.2 Contour Refinements 22
4.2 Rate-Distortion-Based Contour Approximation Scheme 22
4.2.1 Approximated Chains 23
4.2.2 Refinements for Approximated Chains 27
Chapter 5 Experimental Results 28
Chapter 6 Conclusions 35
References 36

[1] MPEG-4 Video Verification Model Version 13.0, ISO/IEC JTC1/SC29/WG11 N2687, Mar. 1999.
[2] A. K. Katesagglos, L. P. Kondi, F. W. Meier, J. Ostermann, and G. M. Schuster, “MPEG-4 and ratio distortion based shape coding techniques,” Proc. IEEE, Vol. 86, pp.1126-1154, June 1998.
[3] H. Freeman, “On the ending of arbitrary geometric configurations,” IRE Trans. on Electronic Computers, Vol. EC-10, pp. 260-268, June 1961.
[4] T. Kaneko and M. Okudaria, “Encoding of arbitrary curves based on the chain code representation,” IEEE Trans. on Communications, Vol. 33, pp. 697-707, July 1985.
[5] R. Prasad, J. W. Vieveen, J. H. Bons, and J. C. Arnbak, “Relative vector probabilities in differential chain coded line-drawings,” Proc. IEEE Pacific Rim Conference on Communication, Computers and Signal Processing, pp. 138-142, June 1989.
[6] Jae-Won Chung, Joo-Hee Moon and Jae-Kyoon Kim, “Conditional differential chain coding for lossless representation of object contour,” Electronics Letters, Vol. 34, pp. 55-56, Jan. 1998.
[7] N. Brady, F. Bossen, and N. Murphy, “Context-based arithmetic encoding of 2D shape sequences,” Proc. ICIP97, pp. I-29—32, 1997.
[8] N. Yamaguchi, T. Ida, and T. Watanabe, “A binary shape coding method using modified MMR,” Proc. ICIP97, pp. I-504—508, 1997.
[9] ITU-T. Recommendation T.6: Facsimile coding schemes and coding control functions for group 4 facsimile apparatus, Geneva, 1998.
[10] ITU-T. Recommendation T.82 (03/93) — information technology — coded representation of picture and audio information — progressive bi-level image compression, Geneva, 1993.
[11] Shi Hwa Lee, Dae-Sung Cho, Yu-Shin Cho, Se Hoon Son, Jang, E.S., Jae-Seob Shin, and Yang Seock Seo, “Binary shape coding using baseline-based method,” IEEE Trans. on Circuits and Systems for Video Technology, Vol. 9, pp. 44-58, Feb. 1999.
[12] Guido M. Schuster and A. K. Katsaggelos, “An optimal polygonal boundary encoding scheme in the rate distortion sense,” IEEE Trans. on Image Processing, Vol. 7, pp.13 -26, Jan. 1998.
[13] D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proc. of the IRE, pp.1098-1101, 1951.
[14] I. H. Witten, R. M. Neal, and J. G. Clery, “Arithmetic coding for data compression,” Commun. of the ACM, Vol. 30, pp.520-540, June 1987.
[15] P. Nunes, F. Pereira, and F. Marques, “Multi-grid chain coding of binary shapes,” Proc. ICIP97, Vol. 3, pp. 114—117, 1997.
[16] Wang, H., Katsaggelos, A. K., and Pappas, T.N., “Rate-distortion optimal skeleton-based shape coding,” Proc. ICIP2001, Vol. 2, pp. 1001-1004, 2001.
[17] Guido M. Schuster, G. Melnikov and A. K. Katsaggelos, “Operationally optimal vertex-based shape coding,” IEEE Signal Processing Magazine, pp. 91-108, November 1998.
[18] Qian, R.J. and Sezan, M.I., “Content-scalable shape representation and coding,” Proc. ICIP97, Vol. 2, pp. 819-822.
[19] C. L. Jordan, F. Bossen, and T. Ebrahimi, “Scalable shape representation for content based visual data compression,” Proc. ICIP97, Vol. 1, pp. 512—515, 1997.
[20] Gerry Melnikov, and Aggelos K. Katesaggelos, “A rate-distortion optimal scalable vertex based shape coding algorithm,” Proc. ICASSP, Vol. 4, pp.1947-1950, 2000.
[21] S. W. Golomb, “Run-Length Encodings,” IEEE Trans. on Information Theory, pp.399-401, July 1966.