數(shù)據(jù)壓縮

摘 要：數(shù)據(jù)壓縮(Data Compression)，是指在一定的數(shù)據(jù)存儲(chǔ)空間要求下，將相對(duì)龐大的原始數(shù)據(jù)，重組為滿足前述空間要求的數(shù)據(jù)集合，使得從該數(shù)據(jù)集合中恢復(fù)出來的信息能夠與原始數(shù)據(jù)相一致，或者能夠獲得與原始數(shù)據(jù)一樣的使用品質(zhì)。

關(guān)鍵詞：無損壓縮 有損壓縮 LZW JPEG JPEG2000

壓縮編碼的理論基礎(chǔ)是信息論。從信息論的角度看，信息定義為“用來消除不確定性的東西”。壓縮是去掉信息中的冗余部分，也就是確定的或可推知的部分，用一種更接近信息本質(zhì)的描述來代替原有冗余的描述。而信息之所以能夠被壓縮，是因?yàn)樾畔⒈旧硗ǔ４嬖诤艽蟮娜哂嗔浚@些冗余量主要是由信息之間的相似性和可推知產(chǎn)生的。另一個(gè)原因是人的感官對(duì)信息之間的某些相似性并不敏感，去掉這部分冗余仍然不影響人們對(duì)信息的感知和理解。按是否壓縮到信息熵，數(shù)據(jù)壓縮方法被分為有損壓縮算法和無損壓縮算法兩類。

無損壓縮算法、無失真壓縮算法，英文為 Lossless compression algorithms。無損壓縮算法是為保留原始數(shù)據(jù)對(duì)象而設(shè)計(jì)的。在無損壓縮中，數(shù)據(jù)在壓縮和解壓縮的過程中都不會(huì)被改變或損失。解壓縮產(chǎn)生的數(shù)據(jù)是對(duì)原始數(shù)據(jù)的完整復(fù)制。

有損壓縮算法，會(huì)造成一些信息熵的損失，只要這種損失被限制在可允許的范圍內(nèi)，有損壓縮就是可接受的。經(jīng)典的壓縮編碼方法通常有三種類型：預(yù)測(cè)編碼、變換編碼、統(tǒng)計(jì)編碼。另外還有一些新的壓縮方法：分形編碼、小波變換圖像壓縮編碼等。

由于計(jì)算機(jī)處理的信息是以二進(jìn)制數(shù)的形式表示的，因此壓縮軟件就是把二進(jìn)制信息中相同的字符串以特殊字符標(biāo)記來達(dá)到壓縮的目的。為了有助于理解文件壓縮，請(qǐng)您在腦海里想象一幅藍(lán)天白云的圖片。對(duì)于成千上萬(wàn)單調(diào)重復(fù)的藍(lán)色像點(diǎn)而言，與其一個(gè)一個(gè)定義“藍(lán)、藍(lán)、藍(lán)……”長(zhǎng)長(zhǎng)的一串顏色，還不如告訴電腦“從這個(gè)位置開始存儲(chǔ)1117個(gè)藍(lán)色像點(diǎn)”來得簡(jiǎn)潔，而且還能大大節(jié)約存儲(chǔ)空間。這是一個(gè)非常簡(jiǎn)單的圖像壓縮的例子。其實(shí)，所有的計(jì)算機(jī)文件歸根結(jié)底都是以“1”和“0”的形式存儲(chǔ)的，和藍(lán)色像點(diǎn)一樣，只要通過合理的數(shù)學(xué)計(jì)算公式，文件的體積都能夠被大大壓縮以達(dá)到“數(shù)據(jù)無損稠密”的效果。如果丟失個(gè)別的數(shù)據(jù)也不會(huì)造成太大的影響，這時(shí)忽略它們是個(gè)好主意，這就是有損壓縮。

最典型的無損壓縮算法就是Lempel-Ziv-Welch (LZW)，該算法主要應(yīng)用有文本壓縮、Gif圖像壓縮等等。LZW壓縮算法是一種新穎的壓縮方法，由Lemple、Ziv、Welch 三人共同創(chuàng)造，用他們的名字命名。它采用了一種先進(jìn)的串表壓縮，將每個(gè)第一次出現(xiàn)的串放在一個(gè)串表中，用一個(gè)數(shù)字來表示串，壓縮文件只存貯數(shù)字，則不存貯串，從而使圖像文件的壓縮效率得到較大的提高。奇妙的是，不管是在壓縮還是在解壓縮的過程中都能正確地建立這個(gè)串表，壓縮或解壓縮完成后，這個(gè)串表又被丟棄。

LZW算法中，首先建立一個(gè)字符串表，把每一個(gè)第一次出現(xiàn)的字符串放入串表中，并用一個(gè)數(shù)字來表示，這個(gè)數(shù)字與此字符串在串表中的位置有關(guān)，并將這個(gè)數(shù)字存入壓縮文件中，如果這個(gè)字符串再次出現(xiàn)時(shí)，即可用表示它的數(shù)字來代替，并將這個(gè)數(shù)字存入文件中。壓縮完成后將串表丟棄。如“print”字符串，如果在壓縮時(shí)用266表示，只要再次出現(xiàn)，均用266表示，并將“print”字符串存入串表中，在圖像解碼時(shí)遇到數(shù)字266，即可從串表中查出266所代表的字符串“print”，在解壓縮時(shí)，串表可以根據(jù)壓縮數(shù)據(jù)重新生成。

Zip就是對(duì)兩種在計(jì)算機(jī)數(shù)據(jù)中重復(fù)的數(shù)據(jù)進(jìn)行壓縮。

第一種是短語(yǔ)形式的重復(fù)，即三個(gè)字節(jié)以上的重復(fù)。對(duì)于這種重復(fù)，Zip用兩個(gè)數(shù)字：1.重復(fù)位置距當(dāng)前壓縮位置的距離；2.重復(fù)的長(zhǎng)度，來表示這個(gè)重復(fù)。假設(shè)這兩個(gè)數(shù)字各占一個(gè)字節(jié)，于是數(shù)據(jù)便得到了壓縮，這很容易理解。

第二種重復(fù)為單字節(jié)的重復(fù)，一個(gè)字節(jié)只有256種可能的取值，所以這種重復(fù)是必然的。其中，某些字節(jié)出現(xiàn)次數(shù)可能較多，另一些則較少，在統(tǒng)計(jì)上有分布不均勻的傾向，這是容易理解的，比如一個(gè) ASCII 文本文件中，某些符號(hào)可能很少用到，而字母和數(shù)字則使用較多，各字母的使用頻率也是不一樣的，據(jù)說字母 e 的使用概率最高；許多圖片呈現(xiàn)深色調(diào)或淺色調(diào)，深色（或淺色）的像素使用較多（這里順便提一下：Png 圖片格式是一種無損壓縮，其核心算法就是 Zip 算法，它和 Zip 格式的文件的主要區(qū)別在于：作為一種圖片格式，它在文件頭處存放了圖片的大小、使用的顏色數(shù)等信息）；上面提到的短語(yǔ)式壓縮的結(jié)果也有這種傾向：重復(fù)傾向于出現(xiàn)在離當(dāng)前壓縮位置較近的地方，重復(fù)長(zhǎng)度傾向于比較短（20字節(jié)以內(nèi)）。這樣，就有了壓縮的可能：給 256 種字節(jié)取值重新編碼，使出現(xiàn)較多的字節(jié)使用較短的編碼，出現(xiàn)較少的字節(jié)使用較長(zhǎng)的編碼，這樣一來，變短的字節(jié)相對(duì)于變長(zhǎng)的字節(jié)更多，文件的總長(zhǎng)度就會(huì)減少，并且，字節(jié)使用比例越不均勻，壓縮比例就越大。

然而，對(duì)于圖像壓縮來說，一定的信息損失通常是可以接受的，原因主要有以下三點(diǎn)：

·人類視覺系統(tǒng)可以容忍很大的信息損失而不妨礙對(duì)場(chǎng)景內(nèi)容的感知；

·在大多數(shù)情況下，壓縮算法的數(shù)字輸入本身是對(duì)真實(shí)場(chǎng)景的不完全描述；

·無損壓縮通常不能夠達(dá)到許多存儲(chǔ)和分布應(yīng)用的高壓縮要求。

所以，我們產(chǎn)生了對(duì)圖像的有損壓縮JPEG圖像。JPEG是聯(lián)合圖象專家組(Joint Picture Expert Group)的英文縮寫，是國(guó)際標(biāo)準(zhǔn)化組織(ISO)和CCITT聯(lián)合制定的靜態(tài)圖像的壓縮編碼標(biāo)準(zhǔn)。JPEG是目前壓縮比最高的圖像。

JPEG是采用變換編碼進(jìn)行信息壓縮的。所謂變換編碼是指，將給定的圖像變換到另一個(gè)數(shù)據(jù)域(如頻域)上，使得大量的信息能用較少的數(shù)據(jù)來表示，從而達(dá)到壓縮的目的。變換編碼有很多，如(1)離散傅立葉變換(Discrete Fourier Transform，簡(jiǎn)稱DFT)；(2)離散余弦變換(Discrete Cosine Transform，簡(jiǎn)稱DCT)；(3)離散哈達(dá)瑪變換(Discrete Hadamard Transform，簡(jiǎn)稱DHT)。

JPEG的壓縮編碼器的流程為：

解碼器基本上為上述過程的逆過程：

我們將圖像分為很多8×8的圖像，而8×8的圖像經(jīng)過DCT變換后，其低頻分量都集中在左上角，高頻分量分布在右下角(DCT變換實(shí)際上是空間域的低通濾波器)。由于該低頻分量包含了圖像的主要信息(如亮度)，而高頻與之相比，就不那么重要了，所以我們可以忽略高頻分量，從而達(dá)到壓縮的目的。當(dāng)然，將高頻分量進(jìn)行省略，也就是信息損失的根源。

JPEG 2000 與傳統(tǒng) JPEG 最大的不同，在于它放棄了 JPEG 所采用的以離散余弦轉(zhuǎn)換(Discrete Cosine Transform) 為主的區(qū)塊編碼方式，而改采以小波轉(zhuǎn)換(Wavelet transform) 為主的多解析編碼方式。小波轉(zhuǎn)換的主要目的是要將影像的頻率成分抽取出來。

參考文獻(xiàn)：

［１］［美］薩洛蒙．?dāng)?shù)據(jù)壓縮原理與應(yīng)用（第二版）.電子工業(yè)出版社，2003年9月.

［２］［美］David S.TaubmanMichael W.Marcellin .JPEG2000 圖像壓縮基礎(chǔ)、標(biāo)準(zhǔn)和實(shí)踐．電子工業(yè)出版社，2004年4月.

［３］馬平.數(shù)字圖像處理和壓縮．電子工業(yè)出版社，2007年4月.