數(shù)字圖像處理第十二章

1第十二章圖象壓縮編碼12.1圖象壓縮編碼的基本概念為什么要壓縮？因為圖象信息的數(shù)據(jù)量實在是太驚人了。一張A4(210mm*297mm)幅面的照片，若用中等分辨率（300dpi）的掃描儀按真彩掃描，共有(300*210/25.4)*（300*297/25.4）個像素，每個像素占3個字節(jié),其數(shù)據(jù)量為26M字節(jié)。在Internet上傳送圖象信息時，圖象的巨大數(shù)據(jù)量會增加網(wǎng)絡(luò)帶寬負荷。大數(shù)據(jù)量的圖象信息會給存儲器的存儲容量，通信干線信道的帶寬，以及計算機的處理速度增加極大的壓力。單純靠增加存儲器容量，提高信道帶寬以及計算機的處理速度等方法來解決這個問題是不現(xiàn)實的，這時就要考慮壓縮。12.1圖象壓縮編碼的基本概念圖象壓縮一般是通過改變圖象的表示方式來達到，因此壓縮和編碼是分不開的。圖象壓縮的主要應(yīng)用是圖象信息的傳輸和存儲，可廣泛地應(yīng)用于廣播電視，電視會議，計算機通訊，傳真，多媒體系統(tǒng)，醫(yī)學(xué)圖象，衛(wèi)星圖象等領(lǐng)域。12.1圖象壓縮編碼的基本概念12.1.1圖像冗余壓縮的理論基礎(chǔ)是信息論。從信息論的角度來看，壓縮利用了圖像信號中的冗余度。壓縮就是去除信息中的冗余，用更接近本質(zhì)的描述替代原有冗余的描述。壓縮還可以利用人眼視覺系統(tǒng)的一些特性忽略掉一些不被人眼所察覺的信號成分。12.1圖象壓縮編碼的基本概念圖像冗余包括：編碼冗余：如果一個圖像的灰度級編碼，使用了多于實際需要的編碼符號，就稱該圖像包含了編碼冗余。例如，如只有3bit(8灰度級）灰階，但是仍舊采用標準的8bit存儲一個像素，就有了編碼冗余。通常在存儲圖像時主要考慮的是數(shù)據(jù)文件結(jié)構(gòu)形式統(tǒng)一，而造成編碼冗余。12.1圖象壓縮編碼的基本概念圖像冗余包括：像素冗余：圖像信號像素之間存在非常大的相關(guān)性（相同、接近、按某種規(guī)律變化）。因此任何給定的像素值，原理上都可以通過它的鄰接像素預(yù)測得到。這種像素之間的內(nèi)在相關(guān)性所導(dǎo)致的冗余為像素冗余。視覺心理冗余：最終觀測圖像的對象是人，由于人眼視覺系統(tǒng)的分辨率與非均勻性，無法辨識一些圖像細節(jié)，即一些信息往往被忽視。將這種對視覺感知影響很小的信息稱為視覺心理冗余。因此編碼時忽略一些視覺感知不太明顯的微小差異，即可進行所謂的“有損”壓縮。12.1圖象壓縮編碼的基本概念12.1.2無損壓縮與有損壓縮壓縮可分為兩大類：第一類壓縮過程是可逆的，即從壓縮后的圖象能夠完全恢復(fù)出原來的圖象，信息沒有任何丟失，稱為無損壓縮；第二類壓縮過程是不可逆的，無法完全恢復(fù)出原圖象，信息有一定的丟失，成為有損壓縮。選擇哪一類壓縮，要折中考慮，盡管我們希望能夠無損壓縮，但是通常有損壓縮的壓縮比（即原圖象的字節(jié)數(shù)與壓縮后圖象的字節(jié)數(shù)之比，壓縮比越大，說明壓縮效率越高）比無損壓縮的高。12.1圖象的編碼與壓縮12.1.3壓縮編碼的方法壓縮編碼的方法有很多，主要分成以下4大類：1.像素編碼；2.預(yù)測編碼；3.變換編碼；4.其它方法。12.1圖象的編碼與壓縮12.1.3壓縮編碼的方法像素編碼是指，編碼時對每個像素單獨處理，不考慮像素之間的相關(guān)性。在像素編碼中常用的幾種方法有：1.脈沖編碼調(diào)制（PulseCodeModulation，PCM）;2.熵編碼（EntropyCoding）；3.行程編碼(RunLengthCoding)；4.位平面編碼（BitPlaneCoding）。下面要介紹的是熵編碼中的兩種方法：哈夫曼(Huffman)編碼，行程編碼（以讀取.PCX文件為例）。12.1圖象的編碼與壓縮12.1.3壓縮編碼的方法預(yù)測編碼是指去掉相鄰像素之間的相關(guān)性和冗余性，只對新的信息進行編碼。例如，因為像素的灰度是連續(xù)的，所以在一片區(qū)域中，相鄰像素之間灰度值的差別可能很小。如果我們只記錄第一個像素的灰度，其它像素的灰度都用它與前一個像素灰度之差來表示，就能起到壓縮的目的。如248，2，1，0，1，3，實際上這6個像素的灰度是248，250，251，251，252，255。表示250需要8個比特，而表示2只需要兩個比特，這樣就實現(xiàn)了壓縮。常用的預(yù)測編碼有：Δ調(diào)制（DeltaModulation，簡稱DM）；微分預(yù)測編碼(DifferentialPulseCodeModulation，DPCM)。12.1圖象的編碼與壓縮12.1.3壓縮編碼的方法變換編碼是指將給定的圖象變換到另一個數(shù)據(jù)域（如頻域）上，使得大量的信息能用較少的數(shù)據(jù)來表示，從而達到壓縮的目的。變換編碼有很多，如：1.離散傅立葉變換(DiscreteFourierTransform，DFT)；2.離散余弦變換(DiscreteCosineTransform，DCT)；3.離散哈達瑪變換(DiscreteHadamardTransform，DHT)。12.1圖象的編碼與壓縮12.1.3壓縮編碼的方法其它的編碼方法也有很多，如：混合編碼（HybirdCoding），矢量量化(VectorQuantize，VQ)，LZW算法。后面只介紹LZW算法的大體思想。12.1圖象的編碼與壓縮12.1.3壓縮編碼的方法近年來出現(xiàn)了很多新的壓縮編碼方法，如：使用人工神經(jīng)元網(wǎng)絡(luò)(ArtificialNeuralNetwork，ANN)的壓縮編碼算法；分形（Fractal）；小波(Wavelet)；基于對象（Object–Based）的壓縮編碼算法；基于模型（Model–Based）的壓縮編碼算法(應(yīng)用在MPEG4及未來的視頻壓縮編碼標準中)。最后以JPEG壓縮編碼標準為例，看看上面的幾種編碼方法在實際的壓縮編碼中是怎樣應(yīng)用的。12.2圖象的無損壓縮編碼無損壓縮是指將壓縮后的數(shù)據(jù)進行重構(gòu)（或者稱作還原、解壓縮）后的信息與原來的信息完全相同的壓縮編碼方式。無損壓縮用于要求重構(gòu)的信息與原始信息完全一致的場合。常見的例子有磁盤的文件壓縮（例如常用的Win-RAR,WinZip)。根據(jù)目前的壓縮技術(shù)，無損壓縮的算法一般可以把普通的文件數(shù)據(jù)壓縮到原來的1/2―1/4。常用的無損壓縮算法有行程編碼(RLE)、霍夫曼編碼（HuffmanCode)、LZW等算法。下面就行程編碼和霍夫曼編碼進行介紹12.2圖象的無損壓縮編碼12.2.1行程編碼(RunLengthCoding)行程編碼亦稱步長法、游程編碼。行程編碼的原理也很簡單：將一行中顏色值相同的相鄰像素用一個計數(shù)值和該顏色值來代替。例如：aaabccccccddeee可以表示為3a1b6c2d3e。如果一幅圖象是由很多塊顏色相同的大面積區(qū)域組成，那么采用行程編碼的壓縮效率是驚人的。然而，該算法也導(dǎo)致了一個致命弱點，如果圖象中每兩個相鄰點的顏色都不同，用這種算法不但不能壓縮，反而數(shù)據(jù)量增加一倍。所以現(xiàn)在單純采用行程編碼的壓縮算法用得并不多，PCX文件算是其中的一種。PCX文件最早是PCPaintbrush軟件所采用的一種文件格式，由于壓縮比不高，現(xiàn)在用的并不是很多了。12.2圖象的無損壓縮編碼12.2.1行程編碼(RunLengthCoding)一維行程編碼只考慮了消除行內(nèi)像素之間的相關(guān)性，卻沒有考慮到某種方向之間的相關(guān)性。于是有時候采用二維行程編碼，以達到既可消除行內(nèi)像素之間水平（行）方向的相關(guān)性，又可消除像素垂直（列）方向的相關(guān)性的目的。所以在圖像行程編碼中多采用二維行程編碼方法。從行程編碼的原理可知，要提高行程編碼的效率，就是希望通過排序使得相鄰像素值相等的情況盡可能多。所謂的二維行程編碼是利用圖像的二維信息的強相關(guān)性，按照一定的掃描路線進行掃描，遍歷所有的像素點，獲得點點相鄰的關(guān)系之后進行一維行程編碼的方法。12.2圖象的無損壓縮編碼12.2.1行程編碼(RunLengthCoding)考慮到像素間的相關(guān)性，除了邊界上的點之外，像素之間距離越近，其相關(guān)性越強。故實際中采用的一種非常簡單的，并且是很有效的方法是，首先將圖像分為一定大小的子塊，然后對每個子塊的像素進行二維排序，使像素之間的關(guān)系變成一維的鄰接關(guān)系。如下圖。12.2圖象的無損壓縮編碼12.2.1行程編碼(RunLengthCoding)上圖(b)通常是變換編碼方式中多采用的方法。例如，對圖像進行DCT變換之后，根據(jù)其高、低頻的分布規(guī)律，按照圖示的排序方法可以獲得較大的編碼效率，圖中黑色點表示的是直流分量，該分量的強度集中度為最大，因此在圖像中所有子塊中的第一個位置上的數(shù)合在一起單獨編碼。12.2圖象的無損壓縮編碼12.2.2霍夫曼(Huffman)編碼Huffman編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長的代碼代替，每個數(shù)據(jù)的代碼各不相同。這些代碼都是二進制碼，且碼的長度是可變的。12.2圖象的無損壓縮編碼12.2.2霍夫曼(Huffman)編碼例子：假設(shè)一個文件中出現(xiàn)了8種符號：

S0，S1，S2，S3，S4，S5，S6，S7，那么每種符號要編碼，至少需要3比特，假設(shè)編碼成000，001，010，011，100，101，110，111（稱做碼字）。那么符號序列：

S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成

000001111000001110010010011100101000000001共用了42比特。我們發(fā)現(xiàn)S0，S1，S2這三個符號出現(xiàn)的頻率比較大，其它符號出現(xiàn)的頻率比較小，如果我們采用一種編碼方案使得S0，S1，S2的碼字短，其它符號的碼字長，這樣就能夠減少占用的比特數(shù)。12.2圖象的無損壓縮編碼12.2.2霍夫曼(Huffman)編碼我們采用這樣的編碼方案：S0到S7的碼字分別為

01，11，101，0000，0001，0010，0011，100，那么上述符號序列變成：

011110001110011101101000000010010010111，共用了39比特。盡管有些碼字如S3，S4，S5，S6變長了（由3位變成4位），但使用頻繁的幾個碼字如S0，S1變短了，所以實現(xiàn)了壓縮。上述的編碼是如何得到的呢？隨意亂寫是不行的。編碼必須保證不能出現(xiàn)一個碼字和另一個的前幾位相同的情況，比如說，如果S0的碼字為01，S2的碼字為011，那么當序列中出現(xiàn)011時，你不知道是S0的碼字后面跟了個1，還是完整的一個S2的碼字。編碼必須能夠保證這一點。

12.2圖象的無損壓縮編碼12.2.2霍夫曼(Huffman)編碼具體的Huffman編碼算法：1.首先統(tǒng)計出每個符號出現(xiàn)的頻率，上例S0到S7的出現(xiàn)頻率分別為4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。2.從左到右把上述頻率按從小到大的順序排列。3.每一次選出最小的兩個值，作為二叉樹的兩個葉子節(jié)點，將和作為它們的根節(jié)點，這兩個葉子節(jié)點不再參與比較，新的根節(jié)點參與比較。4.重復(fù)3，直到最后得到和為1的根節(jié)點。5.將形成的二叉樹的左節(jié)點標為0，右節(jié)點標為1。把從最上面的根節(jié)點到最下面的葉子節(jié)點途中遇到的0，1序列串起來，就得到了各個符號的編碼。

12.2圖象的無損壓縮編碼12.2.2霍夫曼(Huffman)編碼具體的Huffman編碼算法：上面的例子用Huffman編碼的過程如下圖所示，其中圓圈中的數(shù)字是新節(jié)點產(chǎn)生的順序。可見，我們上面給出的編碼就是這么得到的：12.2圖象的無損壓縮編碼12.2.2霍夫曼(Huffman)編碼產(chǎn)生哈夫曼編碼需要對原始數(shù)據(jù)掃描兩遍：第一遍掃描要精確地統(tǒng)計出原始數(shù)據(jù)中，每個值出現(xiàn)的頻率，第二遍是建立霍夫曼樹并進行編碼。由于需要建立二叉樹并遍歷二叉樹生成編碼，因此數(shù)據(jù)壓縮和還原速度都較慢，但簡單有效，因而得到廣泛的應(yīng)用。12.2圖象的無損壓縮編碼12.2.3LZW算法的大體思想LZW是一種比較復(fù)雜的壓縮算法，其壓縮效率也比較高。LZW壓縮算法的基本原理：LZW把每一個第一次出現(xiàn)的字符串用一個數(shù)值來編碼，在還原程序中再將這個數(shù)值還成原來的字符串。例如：用數(shù)值0x100代替字符串“abccddeee”，每當出現(xiàn)該字符串時，都用0x100代替，這樣就起到了壓縮的作用。至于0x100與字符串的對應(yīng)關(guān)系則是在壓縮過程中動態(tài)生成的，而且這種對應(yīng)關(guān)系隱含在壓縮數(shù)據(jù)中，隨著解壓縮的進行，這張編碼表會從壓縮數(shù)據(jù)中逐步得到恢復(fù)，后面的壓縮數(shù)據(jù)再根據(jù)前面數(shù)據(jù)產(chǎn)生的對應(yīng)關(guān)系產(chǎn)生更多的對應(yīng)關(guān)系，直到壓縮文件結(jié)束為止。LZW是無損的。GIF文件采用了這種壓縮算法。LZW算法由Unisys公司在美國申請了專利，要使用它首先要獲得該公司的認可。12.3JPEG壓縮編碼標準1.概述JPEG是聯(lián)合圖象專家組（JointPictureExpertGroup）的英文縮寫，是國際標準化組織(ISO)和CCITT聯(lián)合制定的靜態(tài)圖象的壓縮編碼標準。和相同圖象質(zhì)量的其它常用文件格式（如GIF，TIFF，PCX）相比，JPEG是目前靜態(tài)圖象中壓縮比最高的。以例圖（Windows目錄下的Clouds.bmp）數(shù)據(jù)比較，原圖大小為640*480，256色。將其分別轉(zhuǎn)成下列格式，其文件大小（以字節(jié)為單位）分別為：24位色BMP921,654；24位色JPEG17,707；GIF（只能轉(zhuǎn)成256色）壓縮格式177,152；24位色TIFF壓縮格式923,044；24位色TGA壓縮格式768,136?？梢奐PEG比其它幾種壓縮比要高得多，而圖象質(zhì)量都差不多（JPEG處理的顏色只有真彩和灰度圖）。由于其高壓縮比，使得JPEG被廣泛地應(yīng)用于多媒體和網(wǎng)絡(luò)程序中，例如HTML語法中選用的圖象格式之一就是JPEG（另一種是GIF），這是因為網(wǎng)絡(luò)的帶寬是非常寶貴的，選用一種高壓縮比的文件格式是十分必要的。12.3JPEG壓縮編碼標準2.JPEG壓縮編碼原理JJPEG有幾種模式，其中最常用的是基于DCT變換（離散余弦變換，是簡化傅立葉變換的一種方法）的順序型模式，又稱為基本系統(tǒng)（Baseline）。JPEG的壓縮原理其實是上面介紹的原理的綜合，博采眾家之長，這正JPEG有高壓縮比的原因。其編碼器的流程為：

12.3JPEG壓縮編碼標準2.JPEG壓縮編碼原理