一種以鄰近資料機率作為適應性算術編碼之彩色影像壓縮演算法

A Lossless Color Image Compression Algorithm with Adaptive Arithmetic Coding Based on Adjacent Data Probability

林佳婕(Chia-Chieh Lin)

指導教授 ： 莊謙本

國立臺灣師範大學/科技學院/應用電子科技學系/碩士(2011年)

摘要

近年來影像壓縮技術不斷進步，尤其在有損數據壓縮，如JPEG、JPEG 2000都已經發展得相當成熟，且已廣泛的被使用。但壓縮技術在無損數據壓縮方面，礙於無損數據壓縮對於原檔案的資料，不能有任何遺失，頇完整保留，因此壓縮效果較無法明顯的提升。雖有許多無損數據的編碼被發展出來，例如使用熵編碼(Entropy Coding)的算術編碼(Arithmetic Coding)對雜亂資料進行編碼時，能保有良好的壓縮效果，但其無法對不同類型影像有相同的壓縮效果。因此本論文提出一種簡易且能達到泛用的演算法，希望對各類型的影像都有相近的壓縮效果。本演算法分為兩部分，首先以簡單的蛇行掃描(Snake Scan)將資料做相減，以去除像素間的相關性，再開始對資料編碼。接著以適應性算術編碼(Adaptive Arithmetic Coding)中機率模型的建置，不使用整張影像的資料，而是採用待編碼符號鄰近的資料來建立機率模型。以24張Kodak所提供的彩色影像作壓縮的實驗結果，發現本演算法的效率比原適應性算術編碼有效，因此本法具有進步性。

關鍵字

無損數據壓縮 ； 算術編碼 ； 鄰近資料機率 ； 適應性算術編碼

並列摘要

In the last decade, many advances have been made in the area of image compression. Especially on lost data compression, such as JPEG and JPEG 2000 have been developed quite mature and widely used. However, most lossless data compressions have low Compression Rate because it has to reserve all information. Many data codes had been proposed for lossless data compression. Such as Arithmetic Coding is using Entropy Coding to compress the clutter data with good efficiency. But it cannot compress all kinds of images with the same high Compression Rate. In this paper, we propose a simple lossless algorithm which can compress all types of images with the same high Compression Rate. The algorithm consists of two phases. First, it removes the correlation between pixels with Snake Scan to get residual of data. And then encode the residual of data with an Adaptive Arithmetic Coding. This Adaptive Arithmetic Coding only uses adjacent data to build the probability model. 24 color images provided by Kodak Company were used to test compression rate of this proposed algorithm. The results show the efficiency of this proposed algorithm is better than original Adaptive Arithmetic Coding method.

並列關鍵字

lossless data compression ； arithmetic coding ； adjacent data probability ； adaptive arithmetic coding

參考文獻

[1] K. R. Rao and J. J. Hwang, Techniques & Standards for Image and Video & Audio Coding, USA: Prentice Hall PTR, 1996.

[3] A. Neubauer, J Freudenberger and V. Kuhn, Coding theory: Algorithm, Architectures and Applications, New York: Wiley, 2007.

[4] E. Reinhard, G. Ward, S. Pattanaik, and P. Debevec, High Dynamic Range Imaging: Acquisition, Display, and Image-Based Lighting, California: Morgan Kaufmann, 2005.

[12] T. A. Welch, “A technique for high performance data compression,” IEEE Computer Society, vol. 17, no. 6, pp. 8-19, June 1984.

[14] I. H. Witten, R. M. Neal, and J. G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, vol. 30, no. 6, pp. 520-540, June 1987.