數據壓縮

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

關鍵詞：無損壓縮 有損壓縮 LZW JPEG JPEG2000

壓縮編碼的理論基礎是信息論。從信息論的角度看，信息定義為“用來消除不確定性的東西”。壓縮是去掉信息中的冗余部分，也就是確定的或可推知的部分，用一種更接近信息本質的描述來代替原有冗余的描述。而信息之所以能夠被壓縮，是因為信息本身通常存在很大的冗余量，這些冗余量主要是由信息之間的相似性和可推知產生的。另一個原因是人的感官對信息之間的某些相似性并不敏感，去掉這部分冗余仍然不影響人們對信息的感知和理解。按是否壓縮到信息熵，數據壓縮方法被分為有損壓縮算法和無損壓縮算法兩類。

無損壓縮算法、無失真壓縮算法，英文為 Lossless compression algorithms。無損壓縮算法是為保留原始數據對象而設計的。在無損壓縮中，數據在壓縮和解壓縮的過程中都不會被改變或損失。解壓縮產生的數據是對原始數據的完整復制。

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

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

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

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

Zip就是對兩種在計算機數據中重復的數據進行壓縮。

第一種是短語形式的重復，即三個字節以上的重復。對于這種重復，Zip用兩個數字：1.重復位置距當前壓縮位置的距離；2.重復的長度，來表示這個重復。假設這兩個數字各占一個字節，于是數據便得到了壓縮，這很容易理解。

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

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

·人類視覺系統可以容忍很大的信息損失而不妨礙對場景內容的感知；

·在大多數情況下，壓縮算法的數字輸入本身是對真實場景的不完全描述；

·無損壓縮通常不能夠達到許多存儲和分布應用的高壓縮要求。

所以，我們產生了對圖像的有損壓縮JPEG圖像。JPEG是聯合圖象專家組(Joint Picture Expert Group)的英文縮寫，是國際標準化組織(ISO)和CCITT聯合制定的靜態圖像的壓縮編碼標準。JPEG是目前壓縮比最高的圖像。

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

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

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

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

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

參考文獻：

［１］［美］薩洛蒙．數據壓縮原理與應用（第二版）.電子工業出版社，2003年9月.

［２］［美］David S.TaubmanMichael W.Marcellin .JPEG2000 圖像壓縮基礎、標準和實踐．電子工業出版社，2004年4月.

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