第10章圖像編碼

由于通信方式和通信對象的改變帶來的最大問題是：

傳輸帶寬、速度、存儲器容量的限制。給我們帶來的一個難題，也給了我們一個機會：

如何用軟件的手段來解決硬件上的物理極限。10.1概述10.1.1圖像編碼的緣起實例：圖像傳輸與存儲需要的信息量空間

1）彩色視頻信息對于電視畫面的分辨率640*480的彩色圖像，每秒30幀，則一秒鐘的數據量為：640*480*24*30=221.12M

所以播放時，需要221Mbps的通信回路。參考數據：寬帶網為512K,電話線為56K。存儲時，1張CD可存640M，則僅可以存放2.89秒的數據。2）傳真數據如果只傳送2值圖像，以200dpi的分辨率傳輸，一張A4稿紙的內容的數據量為：1654*2337*1=3888768bit

按目前14.4K傳輸速率，需要傳送的時間是：270秒（4.5分）

按每分鐘4元計算：18元10.1概述圖像編碼主要研究壓縮數碼率，即高效編碼問題，用最少的數碼傳遞最大的信息量。利用圖像信號的統計特性及視覺對圖像的生理學和心理學特性對圖像進行信源編碼。圖像編碼屬于信源編碼的范圍。10.1概述描述語言

1）“這是一幅2*2的圖像，圖像的第一個像素是紅的，第二個像素是紅的，第三個像素是紅的，第四個像素是紅的”。

2）“這是一幅2*2的圖像，整幅圖都是紅色的”。整理圖像的描述方法可以達到壓縮的目的。10.1.2圖像中數據冗余的概念10.1概述圖像冗余無損壓縮的原理RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGB16RGB從原來的16*3*8=284bits壓縮為：(1+3)*8=32bits10.1概述10.1.2圖像中數據冗余的概念圖像冗余有損壓縮的原理3635343434343432343433373034343434343434343534343134343434343434343434343434343434343434343434343434253410.1概述10.1.2圖像中數據冗余的概念圖象的視覺冗余（彩色）

R

G

B2488822*2*2=242=16,777,216(248,27,4)(251,32,15)(248,27,4)(248,27,4)10.1概述10.1.2圖像中數據冗余的概念圖像冗余信息分析結論

由于一幅圖像存在數據冗余和主觀視覺冗余，圖像壓縮方式就是從這兩方面著手來開展的。1）因為有數據冗余，將圖像信息的描述方式改變之后，可以壓縮掉這些冗余。2）因為有主觀視覺冗余，如果忽略一些視覺不太明顯的微小差異，可以進行有損壓縮。10.1概述10.1.2圖像中數據冗余的概念10.1.3

壓縮的可能性與圖像保真度

冗余空間冗余時間冗余結構冗余知識冗余視覺冗余信息熵冗余(編碼冗余)其它冗余2.圖像在一些情況下允許一定程度的失真主觀保真度客觀保真度可能不完全統一10.1概述1.圖像中的數據冗余1、客觀保真度：均方誤差和均方信噪比2、主觀保真度：主觀評價10.1概述10.1.3

壓縮的可能性與圖像保真度

10.1.4圖像數據壓縮方法分類保真度編碼：丟失一些無用或作用不大的信息。信息保持編碼：信息沒有丟失。1.從圖像信息角度對編碼分類特征抽取：只對需要的特征信息進行編碼。10.1概述第一代壓縮編碼

主要是根據傳統的信源編碼方法，以去除冗余為基礎對圖像進行編碼。第二代壓縮編碼

較新的編碼方法，結合分形、模型基、神經網絡、小波變換等數學工具，充分利用視覺系統生理心理特性和圖像信源的各種特性對圖像進行數據壓縮。2.從圖像編碼方法對編碼分類10.1概述10.1.4圖像數據壓縮方法分類像素編碼變換編碼預測編碼

輪廓編碼方塊編碼增量調制熵編碼算術編碼Fourier變換Walsh-Hadamard變換DPCM調制第一代壓縮編碼其他編碼行程編碼10.1概述10.1.4圖像數據壓縮方法分類子帶編碼模型編碼分層編碼分型編碼第二代壓縮編碼10.1概述10.1.4圖像數據壓縮方法分類10.1.5

常用編碼類型與舉例1.等長碼與不等長碼等長碼的碼位長度都相等，即每一個碼字均有相同的比特數，而不等長碼則相反。2.瞬時可譯碼與非瞬時可譯碼瞬時可譯碼：接收到一個碼位即可譯碼非瞬時可譯碼：接收到下一碼位才能譯碼10.1概述3.唯一可譯碼非唯一可譯碼例如：某種代碼，c1=0,c2=1,c3=01,c4=10,則序列0011具有多意性：0011c1c3c2c1c1c2c210.1.5

常用編碼類型與舉例10.1概述10.2.1熵編碼基本概念一、圖像的熵與平均碼字長度1.圖像的熵(Entropy)設數字圖像像素的灰度集合為｛w1,w2,……,wM｝，其對應的概率分別為p1,p2,……,pM,按信息論中信源熵的定義，可以定義圖像的熵

H

為：(bit)由上述定義可以看到：圖像的熵H

是表示其各個灰度級比特數的統計平均值10.2熵編碼例如：①設隨機序列M由8個變量組成，等概率出現，即p1=p2=……,=p8，則：(bit)②設隨機序列M由8個變量組成，p1=1,p2=……,=p8=0，

則：(bit)因此，當M

等于8時，H

的范圍從0到3，即H＝0～log2M，其中H＝3說明信號的隨機程度最大。10.2.1熵編碼基本概念10.2熵編碼2.圖像的平均碼字長度設bk為數字圖像第k

個碼字ck的長度(二進制數的位數)，其對應出現的概率為pk,則該數字圖像的碼字平均長度

R定義為：(bit)10.2.1熵編碼基本概念10.2熵編碼3.圖像的編碼效率：在

R≧H

情況下總可以設計出某種無失真編碼方法，若R接近于H，則說明碼編的較好，稱為最佳編碼。若要求編碼結果R<H,則必然要丟失信息而引起圖像失真。定義數字圖像編碼的效率為：同時定義圖像編碼的冗余度為：4.圖像壓縮比：圖像壓縮前后所需的信息存儲量之比。5.香農信息論：10.2.1熵編碼基本概念10.2熵編碼二、圖像的變長最佳編碼定理在變長編碼中，若對出現概率大的信息賦予短碼字，而對于出現概率小的信息賦予長碼字，如果碼字長度嚴格按照所對應符號出現的概率大小而逆序排列，則此種編碼結果的平均碼字長度一定小于其它任何排列形式得到的編碼。10.2.1熵編碼基本概念10.2熵編碼例如：圖像的熵：(bit)采用等長編碼：平均碼長R＝2(bit)，編碼效率h＝87.5％，Rd=12.5%輸入數據W1W2W3W4概率1/21/41/81/8W1W2W3W400011011W1W2W3W4010110111采用不等長編碼：平均碼長R＝7/4(bit)，編碼效率h＝

100％，Rd=0%10.2.1熵編碼基本概念10.2熵編碼10.2.2哈夫曼（Huffman）編碼

Huffman編碼是根據可變長度最佳編碼定理，應用Huffman編碼算法而產生的一種編碼方法。它的平均碼字長度在系統的輸入概率集合下，比其它唯一可譯碼都小。因此也稱為緊湊碼。Huffman編碼的原則是概率大的信息用短碼，而概率小的信息用長碼，即：若：p1(w1)>p2(w2)>……>pM(wM)則取：b1(c1)<b2(c2)<……<bM(cM)10.2熵編碼Huffman編碼的編碼步驟：①將信源符號（圖像的灰度等級）按概率由大到小排列，概率相同的可以任意放置。②將兩個最小概率相加，形成新的概率集合，并按①的原則重新排隊③重復②的過程，直到僅剩下兩個概率為止④分配碼字進行編碼，原則是從后到前，上0下1(或上1下0)例：設一幅圖像的六個灰度等級w1,w2,w3,w4,w5,w6出現的概率分別為0.4,0.3,0.1,0.1,0.06,0.04，對此圖像進行Huffman編碼10.2.2哈夫曼（Huffman）編碼10.2熵編碼第一次重排編碼結果輸入數據對應概率W10.4W20.3W30.1W40.1W50.06W60.040.40.30.10.10.10.40.30.20.10.40.30.30.60.4第二次重排第三次重排第四次重排111110001000000000100110110100010101000101001011010110101001101101001010.2.2哈夫曼（Huffman）編碼10.2熵編碼熵計算編碼效率：編碼效率：h=2.14/2.2=97.3%平均碼長：R＝0.4＋0.3×2＋0.1×3＋0.1×4＋0.06×5＋0.04×5＝2.2bit10.2.2哈夫曼（Huffman）編碼10.2熵編碼

為在接收端對上述編碼進行解碼，可以采用樹形解碼方法唯一地解碼，每輸入一位即可確定分支情況，并自動確定碼字的起止位。為此需要建立右圖的解碼樹。wi1011110000w1w3w6w2w4w5

在解碼時將輸入的數碼按樹去分配，得到碼字的切分和代碼符號，例如，輸入序列1011100010101

從上述解碼過程可以看到，雖然Huffman碼不是等長碼，但解碼中能自動確定起止位。解碼結果是唯一的。10.2.2哈夫曼（Huffman）編碼10.2熵編碼10.2.3Shannon-Fano編碼編碼步驟：將信源符號按概率由大到小排列，概率相同的可以任意放置；②將概率分為近似相等的兩部分；③進行編碼，上半部分賦予0，下半部分賦予1；④重復②

③直至編碼完成。Huffman編碼需要多次排序，當信源取值很多時計算不方便，Fano和Shannon分別提出了類似方法，使編碼更簡單：10.2熵編碼編碼結果輸入數據對應概率W10.4W20.3W30.1W40.1W50.06W60.0401010111001101111011111111111011011100100S－F編碼舉例：編碼效率：h＝

97.3%平均碼長：R＝2.2bit001101010.2.3Shannon-Fano編碼10.2熵編碼Huffman編碼使用二進制符號進行編碼，該方法在許多情況下無法得到最佳的壓縮效果。

假設某個信源符號出現的概率為80%，其自信息量為：

即用0.322位編碼就可以了，而Huffman編碼只能分配一位0或一位1進行編碼。若采用Huffman編碼，80%的信源數據所需的碼字長度要比理想編碼后的碼字長度多5倍。算術編碼能有效解決Huffman編碼面臨的壓縮效果不理想的問題！10.2.4算術編碼10.2熵編碼

算術編碼不是將單個信源符號映射成一個碼字，而是把整個信源表示為實數線上的0到1之間的一個區間（Interval），其長度等于該序列的概率，再在該區間內選擇一個代表性的小數，轉化為二進制作為實際的編碼輸出。消息序列中的每個元素都要縮短為一個區間。消息序列中元素越多，所得到的區間就越小，當區間變小時，就需要更多的數位來表示這個區間。采用算術編碼每個符號的平均編碼長度可以為小數。10.2.4算術編碼算術編碼基本原理10.2熵編碼例：假設信源符號為X={a1,a2,a3,a4},其中各符號的概率為P(X)={1/8,1/4,1/2,1/8},若對符號序列a3a3a2a4進行算術編碼，其編碼過程為：首先根據信源符號的概率，確定初始區間；即：符號a1a2a3a4概率1/8(0.001)1/4(0.01)1/2(0.1)1/8(0.001)區間[0,0.001)[0.001,0.011)[0.011,0.111)[0.111,1.0)10.2.4算術編碼10.2熵編碼然后按如下步驟進行編碼：初始化編碼點C0=0，區間間隔A0=1；依次對符號序列進行編碼，并更新編碼點Ci和區間間隔Ai；其中Ci=Ci-1+Ai-1*Pi

Ai=Ai-1*piPi

為待編碼符號的區間間隔最小值（累積概率）；pi為待編碼符號對應的概率。③編碼結束，輸出新的編碼點Ci對a3a3a2a4的編碼過程如下：10.2.4算術編碼10.2熵編碼步驟輸入1a3

符號編碼間隔[0.011,0.111)

2a3

符號編碼間隔[0.1001,0.1101)3a2

符號編碼間隔[0.10011,0.10101)

4a4

符號編碼間隔[0.1010011,0.10101)

Ci=Ci-1+Ai-1*Pi

Ai=Ai-1*pi對a3a3a2a4的編碼過程如下：輸入符號a3輸入符號a3輸入符號a2輸入符號a4解碼過程碼字0.1010011解碼過程是：[（收到的碼字串)－(已解符號子區間的下端點）]÷

（字符概率)累積概率

收到碼字串0.1010011時，由于這個碼字串指向子區間[0.011,0.111]，因此，解出的第一個符號應為a3;收到碼字串a3累積概率a3字符概率

該字串仍然落在[0.011,0.111]區間內，因此，解出的第二個字符為

a3符號a1a2a3a4概率1/8(0.001)1/4(0.01)1/2(0.1)1/8(0.001)區間[0,0.001)[0.001,0.011)[0.011,0.111)[0.111,1.0)解碼第三個字符：a3的累積概率a3字符的概率收到碼字串

該字符串落在[0.001,0.011]區間，因此，解出的第三個字符為

a2符號a1a2a3a4概率1/8(0.001)1/4(0.01)1/2(0.1)1/8(0.001)區間[0,0.001)[0.001,0.011)[0.011,0.111)[0.111,1.0)a2的累積概率a2字符的概率收到碼字串

該字符串落在[0.111,1]區間，因此，解出的第三個字符為

a4算術編碼的特點:

1.實際的計算機精度有限,會產生溢出問題;2.對整個消息只產生一個編碼,因此譯碼器必須接受到這個實數后才能譯碼;3.對錯誤很敏感.4.在信源符號概率接近時，算術編碼比霍夫曼編碼效率高，但硬件實現比霍夫曼編碼要復雜。10.2熵編碼10.2.4算術編碼10.3預測編碼預測編碼的理論基礎是現代統計學和控制論，它主要減少了數據在時間和空間上的相關性。預測編碼有線性預測和非線性預測。

對于靜止圖像來說，預測編碼將被圖像變換編碼所取代。而預測編碼對于視頻信號來說，它充分利用了連續幀之間的統計冗余性，是當今主流技術。10.3.1預測編碼概述預測編碼是根據圖像數學模型利用以往的樣本值對于新樣本值進行預測，然后將樣本的實際值與其預測值相減得到一個誤差值，對這一誤差值進行編碼。如果模型足夠好且樣本序列在時間上相關性較強，那么誤差信號的幅度將遠遠小于原始信號，從而可以用較少的電平對其差值量化得到較大的數據壓縮效果。

如果能精確地預測數據源輸出，那就不存在關于數據源的不確定性，因而也就不存在要傳輸的信息。

然而沒有一個實際的系統能找到其完整的數學模型，能找到的最好預測器是以某種最小化的誤差對下一個采樣進行預測的預測器。10.3預測編碼10.3.1預測編碼原理

通常預測器的設計不是利用數據源的實際數學模型，因為數據源的實際數學模型是非常復雜，而且是時變的。實驗結果表明以最小均方預測誤差設計的預測器不但能獲得最小均方預測誤差，同時在視覺效果上也是比較好的。

預測法編碼的實踐性成果主要體現在DPCM的應用上。DPCM充分利用了圖像中相鄰象素之間的相關性。差值脈沖編碼調制DPCM(DifferentialPulseCodeModulation)：首先將象素按時間先后排序，若n時刻象素Xn可由其前面的M個象素值來估計，估計值為，則誤差e=Xn-，滿足e最小并對e進行量化編碼。10.3預測編碼10.3.1預測編碼原理10.3.2DPCM的基本原理設輸入信號XN為tN時刻的亮度取樣值；為tN時刻以前已知象素亮度取樣值X1,X2,…,XN-1對XN所作的預測值（估計值）；eN為差值信號，也稱誤差信號。為量化器的量化誤差，為量化器輸出信號接收端輸出為在接收端復原的象素值與發送端的原始輸入象素值XN之間的誤差為：10.3.2DPCM的基本原理結論：DPCM系統的誤差來源于發送端的量化器，與接收無關。①若去掉量化器，那么則這樣就可以完全不失真的恢復輸入信號XN，可實現信息保持編碼。②如果，那么輸入信號和復原信號輸出之間就一定存在誤差，從而產生圖像質量的某種失真。10.3.2DPCM的基本原理圖像樣本在t時刻XN的線性預測10.3預測編碼10.3.3最佳線性預測采用最小均方誤差準則，以獲得最佳線性預測值。定義XN的均方誤差為為使其最小，分別對各個ai求偏微分，即為求極值，令當時簡記為10.3.3最佳線性預測令Xi和Xj的協方差Rij為則當所有的協方差Rij為已知時，即可求出N-1個預測系數ai最佳預測問題就變成求圖像的協方差了，假定圖像為平穩隨機過程且均值為零，則方差在最佳預測的各個ai已知時，其輸出誤差信號的方差為顯然即誤差信號序列{ei}的相關性比原圖像信號輸入序列{Xi}相關性小很多。使達到最小趨近于零，即為最佳預測。10.3.3最佳線性預測量化器的最佳設計有兩類：①量化比特數b（量化等級）確定，根據最小均方誤差原則設計。②量化誤差一定的情況下，減小量化比特數b。10.3.4最佳量化器10.3預測編碼DPCM系統的預測器、量化器的設計以及傳輸信號的影響，會引起圖像的失真。歸納起來有以下幾種：①斜率過載噪聲②散粒噪聲③偽輪廓圖像④邊沿忙亂

為了糾正以上四種噪聲，應采用自適應量化，即量化步長隨圖像灰度等級變化的陡、緩而自適應調節。DPCM系統存在的問題DPCM在傳輸過程中，一旦遇到信道干擾，就會呈彗星狀向右下方蔓延。

一般來講二維預測要比一維預測的抗干擾能力強，對通信信道的質量要求也較高。一維信道誤碼率應小于10-9，二維信道誤碼率應小于10-8。10.3.5DPCM系統中的噪聲10.3預測編碼

預測編碼和Huffman編碼直接對象素在圖像空間進行操作，稱為空域變換。基于圖像正交變換的編碼方法常稱為頻域方法。熵保持性質：正交變換不會丟失信息；能量保持性質：可以由變換域中的有限個系數來重建信號；能量重新分配和集中：可以對信號能量進行重新分配，可以舍棄一些能量較小的系數，或者根據譜點能量大小的分配不同的存儲位數；去相關特性：可以使相關的空間域變為不相關的變換域，使相關性之中的多余度得以去除。正交變換的性質：正交變換可以使圖像在變換域中變為能量保持、集中且不相關。如果用變換系數來代替空間樣值編碼傳送，只需對變換系數中能量比較記集中的部分進行編碼，就可以達到壓縮的目的。10.4.1變換編碼概述10.4變換編碼基于圖像變換的編碼方法常稱為頻域方法。壓縮比高，視覺效果好，一般為非信息保持編碼。圖像變換編碼的系統框圖：10.4變換編碼10.4.1變換編碼概述

在變換編碼中，首先要將圖像數據分割成子圖像，然后對子圖像數據塊實施某種變換，如DCT變換，那么子圖像尺寸取多少好呢？根據實踐證明子圖像尺寸取4×4、8×8、16×16適合作圖像的壓縮，這是因為：

<1>如果子圖像尺寸取得太小，雖然計算速度快，實現簡單，但壓縮能力有一定的限制。

<2>如果子圖像尺寸取得太大，雖然去相關效果變好，因為象DFT、DCT等正弦型變換均具有漸近最佳性，但也漸趨飽和。若尺寸太大，由于圖像本身的相關性很小，反而使其壓縮效果不顯示，而且增加了計算的復雜性。

10.4.2子圖像尺寸選擇10.4變換編碼FT能量集中于中心（示意圖）移中FT原圖像f（x，y）能量分布于四角（示意圖）10.4.3二維傅立葉變換編碼10.4變換編碼WT移中FTWT將能量集中于頻率平面的左上角移中FT將能量集中于頻率平面的中央10.4.4二維沃爾什－哈達瑪變換編碼WT截取圖像的左上角保存補0經反變換，恢復原圖像10.4.4二維沃爾什－哈達瑪變換編碼跳過白塊編碼游程長度編碼準最佳可變長度編碼預測差值量化編碼識別編碼方塊編碼二值圖像常用的編碼方法二值圖像是指只有兩個灰度級的圖像。例如文字組成的文件掃描圖、氣象圖、工程圖、指紋卡、軍用態勢圖…10.5二值圖像編碼10.5.1二值圖像編碼概述基本原理

大多數二值圖像中的黑象素只占整個圖像的一小部分，若能跳過白色象素，只對黑色象素編碼，則表示圖像的比特數就能減少，平均比特數就能大大降低。一維WBS將圖像的每條掃描線分成若干段，每一段的象素個數為n對全部是白色的象素用0表示對至少有一個黑象素的線段用n+1個比特表示，第一個比特為1，其余n比特采用直接編碼如：黑白白黑～～11001白白白白～～0設長度為N的象素段出現全白的概率為PN，則一維WBS編碼平均字長bN為：10.5.2跳過白塊編碼（WBS）二維WBS將一維WBS的象素段推廣為象素塊。設象素塊大小為M×N，全白象素塊用“0”表示否則用M×N個比特來直接編碼自適應WBS編碼根據圖像的局部結構或統計特性，改變象素塊的大小，進一步提高壓縮效果，這就是所謂的自適應WBS編碼。改進型的一維WBS編碼：對于一維的WBS編碼，如果一條掃描線全為白象素時，則用1比特“0”表示，否則先賦1碼元，再用正常的一維WBS編碼。自適應的WBS編碼可以使得表示圖像的bit數下降很多，但是為了自適應增加了設備的復雜性。10.5.2跳過白塊編碼（WBS）對二值圖像的每一掃描行來看，總是由若干段連著的黑象素段和連著的白象素段組成，分別稱為“黑長”和“白長”。黑長和白長總是交替發生。對于不同長度按其發生概率分配以不同長度的碼字，這就是游程長度編碼(RLC)。基本原理設二值圖象中有長度為1,2,…，N等不同長度的黑長和白長，N為一個掃描行的象素數。如果不分黑長和白長進行統一編碼，則圖像對游程長度的熵H為：其中Pi為游程長度為i所發生的概率。游程(行程)：連續灰度取值相同的象素個數(長度)。10.5.3游程長度編碼（RLC）游程的平均長度E為：游程的符號熵（即象素的熵）為：根據信號編碼定理，每個游程的平均長度B滿足：即每個象素的熵h為用游程長度編碼所得的最小比特率的估計值10.5.3游程長度編碼（RLC）為了進一步減小比特率，可以將黑長和白長分開分別編碼，因為它們出現的概率不同。對白長進行最優編碼后，應該有：令Ew為表示白長的平均長度于是，10.5.3游程長度編碼（RLC）同樣，對于黑長，有經過黑白統計平均，每個象素的熵值hbw為每個象素的編碼比特數bbw為綜合以上各式：由于hbw<h，因此黑長白長分別編碼比混合編碼效果好。要估算RLC編碼的最小比特率，必須知道圖像游程長度的概率分布。這是十分復雜的測量技術，往往采用某些實用的游程長度概率模型來計算。10.5.3游程長度編碼（RLC）

實際使用的壓縮編碼方法，都是綜合了各種方法而達到最高的效率。在計算機圖像壓縮編碼方面，已經有一批標準，并在不斷發展。MPEG-1標準，1992

MPEG-2標準，1993

H.261標準(CCITT)H.263標準MPEG-4標準，1999第1版，2000第2版MPEG-7標準，1996－1998，2001年底

二值圖像壓縮標準靜止圖像壓縮標準視頻圖像壓縮標準G3G4JBIGCCITTGroup3&Group4JointBilevelImagingGroup,1991JPEGJointPictureExpertGroup,1991標準化組織：ISO(國際標準化組織)ITU(國際電信聯盟)CCITT(國際電報電話咨詢委員會，ITU的前身)JPEG2000H.26L標準10.6圖像壓縮編碼國際標準

JPEG是一個應用廣泛的靜態圖像數據壓縮標準，其中包含兩種壓縮算法(DCT和DPCM)，并考慮了人眼的視覺特性，在量化和無損壓縮編碼方面綜合權衡，達到較大的壓縮比(25:1以上)。JPEG既適用于灰度圖像也適用于彩色圖像。JPEG有三種編碼系統：1、基于DCT變換的有損編碼；2、擴展編碼系統(高壓縮比、高精度等)；3、無損獨立編碼系統。10.6圖像壓縮編碼國際標準10.6