編碼技巧於變長碼之應用與改進

Application and improvement of coding techniques for variable length code

張維中(Wei-Chung Chang)

指導教授 ： 顧孟愷

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.02023

摘要

隨著網路世界的蓬勃發展，人們擷取資訊的方式已經從傳統的報章雜誌以及書籍轉變為利用多媒體以影像、視訊或者聲音方式進行。但是多媒體訊息的資料量往往遠大於傳統的文字。為了增加傳輸多媒體訊息的能力，對其進行壓縮乃是必要之途徑。
“壓縮”是指一個有效降低檔案大小的方法。被壓縮檔案的來源可以是各式各樣的形式，如文字、聲音、影像等等。在現今生活中，能給予人們最大感官刺激與效果最佳的傳輸媒介莫過於影像。所以在過去數十年中，各種研究不斷致力於改善並找出最佳的影像壓縮演算法，讓我們可以在有限的頻寬下傳遞更多的訊息。
變長碼是各種壓縮技巧中很重要的一環。與固定長度的編碼方式相比較(如ASCII code)，變長碼可以用更少的位元數來表示一段訊息。
在這篇論文中，我們研究變長碼在現今壓縮標準中扮演的角色。然後在第一個部分，我們提出一個對於霍夫曼碼可以在一個回合中解碼多個符號的資料結構。實驗的結果顯示提出的方法可以有效提昇解碼的速度。
在這篇論文的第二部分，我們研究zigzag scan對於變長碼效能之影響。在影像壓縮標準中，我們先對離散餘弦變換後的係數做zigzag scan，所得的結果再經過量化(quantization)與run-length coding後最終被編成變長碼的形式。Zigzag scan的方式決定了run-length pair的entropy bound，然後決定了變長碼所能得到的最佳效能。因此，我們研究並提出數個改善zigzag 模式的方式。將這些演算法與模式應用在影像上可以進一步改良壓縮的效果。實驗顯示最多可以有1%在壓縮率上之提升。

關鍵字

Huffman code ； Video compression ； zigzag scanning ； variable length code

並列摘要

Multimedia is the computer information that combines several communication media such as audio, video, text, etc. With the growing up of Internet, people are used to acquire information in electronic formats instead of traditional forms. To increase the capacity for current communication channel, data compression is a necessary tool.
Compression is a method to reduce the file size of source data. The source data could be in various kinds of formats. Since we are living in a world full of multimedia information now, the most popular forms of multimedia message are images or videos. In the past few years, many image (video) compression standards had been developed to reduce the size of source data. Hence we could carry more information on a transmission channel with fixed bandwidth.
One of the most important techniques in image (video) compression is variable length coding. Compared with fix length code, the variable length coding scheme requires smaller number of bits to represent a given message.
In this thesis, we survey the role of variable length code in modern codec. Then in the first part, we propose a new data structure which facilitates to decode multiple symbols in a lookup step. The experimental result shows it could speed up the decoding process efficiently.
In the second part, we study the relationship between zigzag scan and variable length coding. Since the result of zigzag scan decides the lowest entropy of the run-length pairs so as to the efficiency of the variable length coding hereafter, we could further improve the compression ratio by choosing customized zigzag patterns for specific images (videos). As the result, we develop a new zigzag scanning scheme for this purpose. Experimental results show we could reduce at most 1% with only little computational cost.

並列關鍵字

霍夫曼碼 ； 影像壓縮 ； 鋸齒狀掃描法 ； 變長碼

參考文獻

[1] D.A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., September 1952, pp 1098–1102.

[2] K.L Chung, ”Efficient Huffman decoding,” Information Processing Letters 61, pp 97-99, 1997.

[3] H.C. Chen, Y.L. Wang and Y.F. Lan, ”A memory-efficient and fast Huffman decoding algorithm,” Information Processing Letters, vol. 69, no. 3, pp. 119-122, 1999.

[4] R. Hashemian, “Memory efficient and high-speed search Huffman coding,” IEEE Trans. Commun., vol. 43, no. 10, pp. 2576–2581, Oct, 1995.

[5] H.C. Chen, Y.L. Wang and Y.F. Lan, ”A memory-efficient and fast Huffman decoding algorithm,” Information Processing Letters, vol. 69, no. 3, pp. 119-122, 1999.