臺灣博碩士論文加值系統

隨著全球資訊網的出現，使得影像資料的使用與日俱增，通常這些影像資料的用量都非常巨大，為了能夠方便的儲存和傳送，這些影像資料就必須被有效地壓縮，因此為了能節省儲存空間和傳送時間，影像壓縮已經成為一個很重要的研究議題。而向量量化 (vector quantization,VQ) 已經成功的應用在各種語音、影像與視訊的編碼上，所以它是一個很有效地影像壓縮技術，也是一個非常熱門的研究議題。現將本篇論文的貢獻摘要如下：
在編碼過程，當一個輸入向量要進行編碼時，則從碼表 (codebook) 中找一個最匹配的碼字 (codeword) 來編它，這是一項非常耗時的工作，尤其是當碼表的大小很大時。為了能消減時間需求和保有與完全搜尋時相同的失真 (distortion) 效能，本篇論文提出二個碼表搜尋演算法去降低時間需求，其中一個搜尋演算法是使用 DCT 和三角不等式，另一個則是使用 Gabor filter 和三角不等式去拒絕不可能的碼字。其中使用DCT和三角不等式的搜尋演算法，不管是在失真計算的次數上或是在被需要的計算時間上都是較佳的。
Shannon's rate-distortion theory指出—VQ對於一靜止來源幾乎可以做到最佳編碼，然而在實際應用上，影像來源是很少靜止的，使得在理論效能與實際效能上存在一些許的差距，為了改善這個差距，本篇論文提出一改良式的適應性向量量化 (AVQ) 演算法，此一演算法與Shen等所提的AVQ演算法有著相似的PSNR效能，但在編解碼的時間上卻省很多。當碼表的大小是256，歷史區的搜尋大小也是256時，所提的AVQ演算法在編碼時間上可以改善大約75%；當碼表的大小是256，bit rate是大約0.5bpp時，所提的AVQ演算法在解碼時間上大約平均可以改善70%。
可逆變動長度碼 (RVLC) 可以正反向解碼，所以有一個較強的錯誤偵測和回復能力，已經被建議使用在H.263+、H.263++和MPEG-4等視訊標準中去加強它們的錯誤恢復力 (Error resilience)。因此本篇論文提出一個改良式的對稱可逆變動長度碼 (SRVLCs) 的建構演算法，比起利用Takishima等人所建構的對稱可逆變動長度碼，和 Tsai和 Wu二位作者所建構的對稱可逆變動長度碼，此一對稱可逆變動長度碼有一個較強的錯誤偵測和回復能力。
另本篇論文也提出二個快速的索引方法去解碼MPEG-4 B-23 表格中的可逆變動長度碼，在合理的時間需求下，我們所提的方法，一個不需要任何多餘的表格元素，而另一個僅需要一個額外的表格元素，相較於Webb的四個索引方式，至少需要11個額外的表格元素。

With the emergence of World Wide Web (WWW), the use of the images is growing with each passing day. The amount of these images is usually huge and these images need to be compressed for storage and transmission. Therefore, how to compress them is an important research issue for saving storage and transmission time. Vector quantization (VQ) is an important technique for image compression and has been successfully developed for speech, image, and video coding. The contributions of this thesis are summarized below.

In the encoding process, the encoder must find the closest codeword for each input vector from the codebook. This process is very time consuming for a large codebook. In order to reduce the time requirement for VQ and keep the same distortion performed by full search algorithm, the thesis presents two codebook search algorithms, one is using the DCT and triangular inequality and the other is using the Gabor filters and triangular inequality, to reduce the time requirement. The search algorithm using the DCT and triangular inequality is better than the search algorithm proposed by Lai and Liaw and the search algorithm using the Gabor filters and triangular inequality in terms of the average number of distortion computations and the required computing time.

Shannon's rate-distortion theory tells us that the VQ is asymptotically optimal for coding a stationary source. However, since the image source is rarely stationary in practice, there still exists a gap between the theoretical performance and the real performance. To improve this gap, this thesis presents an improved adaptive VQ (AVQ) algorithm based on the proposed hybrid codebook data structure. The proposed AVQ algorithm can improve the time performance significantly while preserving the similar PSNR performance as in the AVQ algorithm proposed by Shen et al. When the codebook size is set to 256 and the searching size of the history codebook is set to 256, the proposed AVQ algorithm has about 75% encoding time improvement ratio. When the codebook size is set to 256 and the bit rate is about 0.5bpp, the proposed AVQ algorithm has about 70% decoding time improvement ratio in average when compared to the AVQ algorithm proposed by Shen et al.

Since reversible variable length codes (RVLCs) can be decoded in forward and backward directions, the RVLCs have a stronger error detection and recovery capability, and have been suggested to use in H.263+, H.263++, and MPEG-4 to enhance their error resilience capabilities. Therefore, this thesis presents a modified algorithm to construct the symmetrical RVLCs (SRVLCs). The proposed SRVLCs have a stronger error detection and recovery capability when compared to the SRVLCs constructed by Takishima et al. and the SRVLCs constructed by Tsai and Wu.

In addition, we also present two new indexing methods for decoding RVLCs in the MPEG-4 RVLC B-23 table. Under reasonable execution time requirement, in our two methods, the first method has no redundancy in the table entries and the second method has only one extra row entry in the table. However, there are at least 11 extra table entries in any one of Webb's four methods.

Chapter 1. Introduction　　　1
1.1. Background　　　1
1.2. Motivation　　　3
1.3. Organization of the thesis　　　4
Chapter 2. Preliminary 6
2.1 Introduction 6
2.2 LBG algorithm 8
2.3 Pairwise nearest neighbor algorithm 13
2.4 Huffman coding 16
2.5 Arithmetic coding 19
Chapter 3. Fast Search Algorithms for Vector Quantization 24
3.1 Introduction 24
3.1 Full search algorithm 25
3.2 Fast search algorithm proposed by Ra and Kim 26
3.3 Fast search algorithm proposed by Lai and Liaw 29
3.4 Proposed fast search algorithm using DCT and triangular inequality 33
3.5 Proposed fast search algorithm using Gabor Filters and triangular inequality 42
3.6 Experimental results 46
Chapter 4. Adaptive Vector Quantization Algorithms 51
4.1 Introduction 51
4.2 Adaptive vector quantization algorithm proposed by Shen et al. 54
4.3 Proposed adaptive vector quantization algorithm 56
4.4 Experimental results 62
Chapter 5 Reversible Variable Length Codes Construction Algorithms 73
5.1 Introduction 73
5.2 Symmetrical RVLCs construction algorithm proposed by Takishima et al. 75
5.3 Symmetrical RVLCs construction algorithm proposed by Tsai and Wu 76
5.4 Proposed symmetrical RVLCs construction algorithm 79
5.5 Simulation results 80
Chapter 6 Reversible Variable Length Codes Decoding Algorithms 82
6.1 Introduction 82
6.2 RVLCs decoding algorithm proposed by Webb 84
6.3 Proposed RVLCs decoding algorithm 88
6.4 Experimental results 89
Chapter 7. Conclusions and future works　92
References 94

[1] Gray RM. Vector quantization. IEEE Acoust. Speech Signal Process. Mag. 1984;4-29.

[2] Nasrabadi NM, King RA. Image coding using vector quantization: A review. IEEE Trans. Commun. Aug. 1988;36:957-971.

[3] Guan L, Kamel M. Equal-average hyperplane partitioning method for vector quantization of image data. Pattern Recognition Letters 1992;13(10):693-699.

[4] Gersho A, Gray RM. Vector Quantization and Signal Compression. Norwell, MA: Kluwer, 1992.

[5] Ramamurthi B, Gersho A. Classified vector quantization of images. IEEE Trans. Commun. Nov. 1986;34:1105-1115.

[6] Hu YC, Chang CC. Low complexity index-compressed vector quantization for image compression. IEEE Trans. Comsumer Electronics Feb. 1999;45:219-224.

[7] Kim T. Side match and overlap match vector quantizers for images. IEEE Trans. Image Processing Apr. 1992;1:170-185.

[8] Chang RF, Chen WM. Adaptive edge-based side-match finite-state classified vector quantization with quadtree map. IEEE Trans. Image Processing Feb. 1996;5:378-383.

[9] Chen TS, Chang CC. A new image coding algorithm using variable-rate side-match finite-state vector quantization. IEEE Trans. Image Processing Aug. 1997;6:1185-1187.

[10] Wei HC, Tsai PC, Wang JS. Three-Sided side-match finite-state vector quantization. IEEE Trans. Circuits and Systems for Video Technology Feb. 2000;10:51-58.

[11] Ra SW, Kim JK, Fast mean-distance-ordered partial codebook search algorithm for image vector quantization. IEEE Trans. Circuits Syst. II Sept. 1993;40:576-579.

[12] Tai SC, Lai CC, Lin YC. Two fast nearest neighbor searching algorithms for image vector quantization. IEEE Trans. Commun. 1996;40:1623-1628.

[13] Chen TS, Chang CC. Diagonal axes method (DAM): a fast search algorithm for vector quantization. IEEE Trans. Circuits and Systems for Video Technology Jun. 1997;7:555-559.

[14] Shen G, Liou ML. Window-based fast search algorithm for image vector quantization. In: Proc. Picture Coding Symposium, Apr. 1999. p. 147-151.

[15] Pan JS, Lu ZM, Sun SH. An efficient encoding algorithm for vector quantization based on subvector technique. IEEE Trans. Image Processing Mar.
2003;12:265-270.

[16] Lai ZC, Liaw YC. Fast searching algorithm for vector quantization using projection and triangular inequality. IEEE Trans. Image Processing Dec. 2004;13:1554-1558.

[17] Shannon CE, Weaver W. The Mathematical Theory of Communication, Urbana IL: Univ. of Illinois Press, 1963.

[18] Linde Y, Buzo A, Gray RM. An algorithm for vector quantizer design. IEEE Trans. Commun. Jan. 1980;28:84-95.

[19] Rose K, Gurewitz E, Fox GC. Vector quantization by deterministic annealing. IEEE Transactions on Information Theory 1992;38:1249-1257.

[20] Zeger K, Buzo A, Gray RM. Globally optimal vector quantizer design by stochastic relaxation. IEEE Transactions on Signal Processing 1992;40:310-322.

[21] Equitz WH. A new vector quantization clustering algorithm. IEEE Transactions on Acoustics, Speech, and Signal Processing 1989;37:1568-1575

[22] Franti P, Kaukoranta T, Shen DF, Chang KS. Fast and memory efficient implementation of the exact PNN. IEEE Transactions on Image Processing 2000;9:773-777.

[23] Paul DB. A 500--800 bps adaptive vector quantization vocoder using a perceptually motivated distance measure. In: Conf. Rec. IEEE Globecom, 1982. p. 1079-1082.

[24] Gersho A, Yano M. Adaptive vector quantization by progressive codevector replacement. In: Int. Conf. Acoustics, Speech, and Signal Processing, May 1985. p. 133-136.

[25] Bentley JL, Sleator DD, Tarjan RE, Wei VK. A locally adaptive data compression scheme. Commun. ACM Apr. 1986;29:320-346.

[26] Wang X, Shende S, Sayood K. Online compression of video sequences using adaptive VQ codebook. In: IEEE Data Compression Conf., J. A. Storer and M. Cohn, Eds. Snowbird, UT, Mar. 1994. p. 185-194.

[27] Lightstone M, Mitra SK. Adaptive vector quantization for image coding in an entropy-constrained framework. In: Int. Conf. Image Processing, Austin, TX, Nov. 1994, vol. 1. p. 618-622.

[28] Lightstone M, Mitra SK. Image--adaptive vector quantization in an entropy-constrained framework. IEEE Trans. Image Processing Mar. 1997;6:441-450.

[29] Fowler JE, Ahalt SC. Adaptive vector quantization using generalized threshold replenishment. In: IEEE Data Compression Conf., J. A. Storer and M. Cohn, Eds. Snowbird, UT, Mar. 1997. p. 317-326.

[30] Fowler JE. Generalized threshold replenishment: An adaptive vector quantization algorithm for the coding of nonstationary sources. IEEE Trans. Image Processing Oct.
1998;7:1410-1424.

[31] Fowler JE. Adaptive vector quantization for efficient zerotree-based coding of video with nonstationary statistics. IEEE Trans. Circuits and Systems for Video Technology Dec. 2000;10:1478-1488.

[32] Shen G, Zeng B, Liou ML. Adaptive vector quantization with codebook updating based on locality and history. IEEE Trans. Image Processing Mar. 2003;12:283-295.

[33] Huffman DA. A method for the construction of minimum redundancy codes.
In: Proc IRE, 1951, vol. 40. p. 1098-1101.

[34] Witten IH, Neal RM, Cleary JG. Arithmetic coding for data compression. Commun. ACM June 1987;30:520-540.

[35] Wen J, Villasenor JD. A class of reversible variable length codes for robust image and video coding, In: Proc. IEEE Int. Conf. Image Processing, 1997, vol. 2, p.65-68.

[36] Wen J, Villasenor JD. Reversible variable length codes for efficient and robust image and video coding. In: IEEE data compression conference, 1998, p.471-480.

[37] Takishima Y, Wada M, Murakami H. Reversible variable length codes. IEEE Trans. Commun. 1995;43: 158-162.

[38] Tsai CW, Wu JL. Modified symmetrical reversible variable length codes and its theoretical bounds. IEEE Trans. Inform. Theory 2001;47:2543-2548.

[39] Tsai CW, Wu JL. On constructing the Huffman-code-based reversible variable-length codes. IEEE Trans. Commun. 2001;49:1506-1509.

[40] Lin CW, Wu JL. On Error Detection and Error Synchronization of Reversible Variable-Length Codes. IEEE Trans. Commun. 2005;53:826-832.

[41] Kukorelly Z, Zeger K. Sufficient Conditions for Existence of Binary Fix-Free Codes. IEEE Trans. Inform. Theory 2005;51:3433-3444.

[42] ITU-T. Video coding for low bit rate communication. Recommendation H.263, 1997.

[43] ISO/IEC. Coding of audio-visual objects: Visual. Final Draft International Standard 14496-2, Oct. 1998.

[44] Chen HN, Chung KL. Improved adaptive vector quantization using hybrid codebook data structure. Real-Time Imaging 2005;11:270-81.

[45] Chung KL, Chen HN. On symmetrical reversible variable length codes. Signal Processing: Image Communication, submitted.

[46] Webb JLH. Efficient table access for reversible variable-length decoding. IEEE Trans. Circuits and Systems for Video Technology 2001;11:981-985.

[47] Chung KL, Chen HN. On decoding MPEG--4 reversible variable length codes. Signal Processing: Image Communication 2005;20:187-192.

[48] Lee D, Baek S, Sung K. Modified K-means algorithms for vector quantizer design. IEEE Signal Processing Letters 1997;4:2-4.

[49] Chen CQ. An enhanced Generalized Lloyd algorithm. IEEE Signal Processing Letters 2004;11:167-170.

[50] Yang SB. Variable-branch tree-structured vector quantization. IEEE Transactions on Image Processing 2004;13:1275-1285.

[51] Knuth DE. Dynamic Huffman coding. Journal of Algorithms 1985;6:163-180.

[52] Howard PG, Vitter JS. Arithmetic coding for data compression. In: Proceedings of the IEEE, June 1994. p. 857-865.

[53] Bei CD, Gray RM. An improvement of the minimum distortion encoding algorithm for vector quantization IEEE Trans. Commun. 1985;COM-33:1132-1133.

[54] Lai JZC, Lue CC. Fast search algorithms for VQ codebook generation J. Vis. Commun. Image Representation 1996;7:163-168.