圖像信息處理技術

1、第4章 圖像信息處理技術,4.1 圖像信號概述 4.2 圖像信號數字化 4.3 數字圖像壓縮方法的分類 4.4 典型的熵編碼方法 4.5 預測編碼 4.6 變換編碼 *4.7 新型圖像編碼技術 4.8 靜態(tài)圖像壓縮編碼標準 4.9 動態(tài)圖像壓縮編碼標準練習與思考題,4.1 圖像信號概述,圖像是一種可視化的信息， 圖像信號是圖像信息的理論描述方法， 圖像信號按其內容變化與時間的關系來分， 主要包括靜態(tài)圖像和動態(tài)圖像兩種。

2、 靜態(tài)圖像其信息密度隨空間分布， 且相對時間為常量； 動態(tài)圖像也稱時變圖像， 其空間密度特性是隨時間而變化的。 人們經常用靜態(tài)圖像的一個時間序列來表示一個動態(tài)圖像。,圖像分類還可以按其他方式進行： 如按其亮度等級的不同可分為二值圖像和灰度圖像； 按其色調的不同可分為黑白圖像和彩色圖像； 按其所占空間的維數不同可分為平面的二維圖像和立體的三維圖像等等。  圖像信號的記錄、 存儲和傳輸可以采用模擬方式或數字方式。

3、傳統(tǒng)的方式為模擬方式， 例如， 目前我們在電視上所見到的圖像就是以一種模擬電信號的形式來記錄， 并依靠模擬調幅的手段在空間傳播的。 將模擬圖像信號經A/D變換后就得到數字圖像信號， 數字圖像信號便于進行各種處理， 例如最常見的壓縮編碼處理就是在此基礎上完成的。 本書介紹的圖像信息處理技術就是針對數字圖像信號的。 ,1． 彩色圖像信號的分量表示 對于黑白圖像信號， 每個像素點用灰度級來表示， 若用數字表示一個

4、像素點的灰度， 有8比特就夠了， 因為人眼對灰度的最大分辨力為26。 對于彩色視頻信號（例如常見的彩色電視信號）均基于三基色原理， 每個像素點由紅（R）、 綠（G）、 藍（B）三基色混合而成。 若三個基色均用8比特來表示， 則每個像素點就需要24比特， 由于構成一幅彩色圖像需要大量的像素點， 因此， 圖像信號采樣、 量化后的數據量就相當大， 不便于傳輸和存儲。,為了解決此問題， 人們找到了相應的解決方法： 利用人的視覺特性降低彩色圖像的

5、數據量， 這種方法往往把RGB空間表示的彩色圖像變換到其他彩色空間， 每一種彩色空間都產生一種亮度分量和兩種色度分量信號。 常用的彩色空間表示法有YUV、 YIQ和YCbCr等。 ,（1） YUV彩色空間。 通常我們用彩色攝像機來獲取圖像信息， 攝像機把彩色圖像信號經過分色棱鏡分成R0、 G0、 B0三個分量信號， 分別經過放大和r校正得到RGB， 再經過矩陣變換電路得到亮度信號Y和色差信號U、 V， 其中亮度信號表示了單位面積上反

6、射光線的強度， 而色差信號（所謂色差信號， 就是指基色信號中的三個分量信號R、 G、 B與亮度信號之差）決定了彩色圖像信號的色調。 最后發(fā)送端將Y、 U、 V三個信號進行編碼， 用同一信道發(fā)送出去， 這就是在PAL彩色電視制式中使用的YUV彩色空間。 YUV與RGB彩色空間變換的對應關系如式（4.1-1）所示。,YUV彩色空間的一個優(yōu)點是， 它的亮度信號Y和色差信號U、 V是相互獨立的， 即Y信號分量構成的黑白灰度圖與用U、 V兩個色

7、彩分量信號構成的兩幅單色圖是相互獨立的。 因為YUV是獨立的， 所以可以對這些單色圖分別進行編碼。 此外， 利用YUV之間的獨立性解決了彩色電視機與黑白電視機的兼容問題。,（4.1-1）,YUV表示法的另一個優(yōu)點是， 可以利用人眼的視覺特性來降低數字彩色圖像的數據量。 人眼對彩色圖像細節(jié)的分辨能力比對黑白圖像細節(jié)的分辨能力低得多， 因此就可以降低彩色分量的分辨率而不會明顯影響圖像質量， 即可以把幾個相同像素不同的色彩值當做相同的色彩值來

8、處理（即大面積著色原理）， 從而減少了所需的數據量。 在PAL彩色電視制式中， 亮度信號的帶寬為4.43 MHz， 用以保證足夠的清晰度， 而把色差信號的帶寬壓縮為1.3 MHz， 達到了減少帶寬的目的。 ,在數字圖像處理的實際操作中， 就是對亮度信號Y和色差信號U、 V分別采用不同的采樣頻率。 目前常用的Y、 U、 V采樣頻率的比例有4∶2∶2和4∶1∶1， 當然， 根據要求的不同， 還可以采用其他比例。 例如要存儲R∶G∶B＝8∶

9、8∶8的彩色圖像， 即R、 G、 B分量都用8比特表示， 圖像的大小為640×480像素， 那么所需要的存儲容量為640×480×3×8/8＝921 600字節(jié)； 如果用Y∶U∶V＝4∶1∶1來表示同一幅彩色圖像， 對于亮度信號Y， 每個像素仍用8比特表示， 而對于色差信號U、 V， 每4個像素用8比特表示， 則存儲量變?yōu)?40×480×(8+4)/8＝460 800字節(jié)。

10、盡管數據量減少了一半， 但人眼察覺不出有明顯變化。,（2） YIQ彩色空間。 在NTSC彩色電視制式中選用YIQ彩色空間， 其中Y表示亮度， I、 Q是兩個彩色分量。 I、 Q與U、 V是不相同的。 人眼的彩色視覺特性表明， 人眼對紅、 黃之間顏色變化的分辨能力最強； 而對藍、 紫之間顏色變化的分辨能力最弱。 在YIQ彩色空間中， 色彩信號I表示人眼最敏感的色軸， Q表示人眼最不敏感的色軸。 在NTSC制式中， 傳送人眼分辨能力較強的I

11、信號時， 用較寬的頻帶（1.3～1.5 MHz）； 而傳送人眼分辨能力較弱的Q信號時， 用較窄的頻帶（0.5 MHz）。 YIQ與RGB彩色空間變換的對應關系如式(4.1-2)所示。 ,（4.1-2）,（3） YCbCr彩色空間。 YCbCr彩色空間是由ITU-R（國際電聯(lián)無線標準部， 原國際無線電咨詢委員會CCIR）制定的彩色空間。 按照CCIR601-2標準， 將非線性的RGB信號編碼成YCbCr， 編碼過程開始是先采用符合S

12、MPTE-CRGB（它定義了三種熒光粉， 即一種參考白光， 應用于演播室監(jiān)視器及電視接收機標準的RGB）的基色作為r校正信號。,非線性RGB信號很容易與一個常量矩陣相乘而得到亮度信號Y和兩個色差信號Cb、 Cr。 YCbCr通常在圖像壓縮時作為彩色空間， 而在通信中是一種非正式標準。 YCbCr與RGB彩色空間變換的對應關系如式（4.1-3）所示， 可以看到： 數字域中的彩色空間變換與模擬域中的彩色空間變換是不同的。 ,（4.1-3

13、）,2 ． 彩色圖像信號的分量編碼 通過圖像信號的表示方法的討論可以看到： 對于彩色圖像信號數字壓縮編碼， 可以采用兩種不同的編解碼方案。 一種是復合編碼， 它直接對復合圖像信號進行采樣、 編碼和傳輸； 另一種是分量編碼， 它首先把復合圖像中的亮度和色度信號分離出來， 然后分別進行取樣、 編碼和傳輸。 目前分量編碼已經成為圖像信號壓縮的主流， 在20世紀90年代以來頒布的一系列圖像壓縮國際標準中均采用分量編碼方

14、案。 以YUV彩色空間為例， 分量編碼系統(tǒng)的基本框圖如圖4.1-1所示， 其中對亮度信號Y使用較高的采樣頻率， 對色差信號U、 V則使用較低的采樣頻率。 ,圖4.1-1 彩色圖像信號分量編碼系統(tǒng)的基本框圖,4.2 圖像信號數字化,圖像信號數字化與音頻數字化一樣主要包括兩方面的內容： 取樣和量化。  圖像在空間上的離散化稱為取樣， 即使空間上連續(xù)變化的圖像離散化， 也就是用空間上部分點的灰度值來表示圖像， 這些

15、點稱為樣點（或像素， 像元， 樣本）。 一幅圖像應取多少樣點呢？其約束條件是： 由這些樣點采用某種方法能夠正確重建原圖像。,取樣的方法有兩類： 一類是直接對表示圖像的二維函數值進行取樣， 即讀取各離散點上的信號值， 所得結果就是一個樣點值陣列， 所以也稱為點陣取樣； 另一類是先將圖像函數進行正交變換， 用其變換系數作為取樣值， 故稱為正交系數取樣。  對樣點灰度級值的離散化過程稱為量化， 也就是對每個樣點值數

16、字化， 使其和有限個可能電平數中的一個對應， 即使圖像的灰度級值離散化。 量化也可分為兩種： 一種是將樣點灰度級值等間隔分檔取整， 稱為均勻量化； 另一種是將樣點灰度級值不等間隔分檔取整， 稱為非均勻量化。,4.2.1 取樣點數和量化級數的選取 假定一幅圖像取M×N個樣點， 對樣點值進行Q級分檔取整。 那么對M， N和Q如何取值呢？ 首先， M， N， Q一般總是取2的整數次冪

17、， 如Q = 2b ， b為正整數， 通常稱為對圖像進行b比特量化， M、 N可以相等， 也可以不相等。 若取相等， 則圖像距陣為方陣， 分析運算方便一些。 其次， 關于M、 N和b(或Q)數值大小的確定。 對b來講， 取值越大， 重建圖像失真越小。 若要完全不失真地重建原圖像， 則b必須取無窮大， 否則一定存在失真， 即所謂的量化誤差。,一般供人眼觀察的圖像， 由于人眼對灰度分辨能力有限， 用5~8比特量化即

18、可。 對M×N的取值主要依據取樣的約束條件。 也就是在M×N大到滿足取樣定理的情況下， 重建圖像就不會產生失真， 否則就會因取樣點數不夠而產生所謂混淆失真。 為了減少表示圖像的比特數， 應取M×N點數剛好滿足取樣定理。 這種狀態(tài)的取樣即為奈奎斯特取樣。 M×N常用的尺寸有512×512， 256×256， 64×64， 32×32等。,再次， 在實際應用

19、中， 如果允許表示圖像的總比特數M×N×b給定， 對M×N和b的分配往往是根據圖像的內容和應用要求以及系統(tǒng)本身的技術指標來選定的。 例如， 若圖像中有大面積灰度變化緩慢的平滑區(qū)域如人圖像的特寫照片等， 則M×N取樣點可以少些， 而量化比特數b多些， 這樣可使重建圖像灰度層次多些。 若b太少， 在圖像平滑區(qū)往往會出現(xiàn)“假輪廓”。,反之， 對于復雜景物圖像， 如群眾場面的照片等， 量化比特數b可以少些

20、， 而取樣點數M×N要多些， 這樣就不會丟失圖像的細節(jié)。 究竟M×N和b如何組合才能獲得滿意的結果很難講出一個統(tǒng)一的方案， 但是有一點是可以肯定的： 不同的取樣點數和量化比特數組合可以獲得相同的主觀質量評價。,*4.2.2 點陣取樣 在分析取樣和重建圖像時， 往往認為取樣系統(tǒng)的輸入圖像是一個確定的圖像場， 即為確知函數， 如一幅照片或膠片。 但是在某些情況下， 如電視圖像由于噪聲影響和取樣方式

21、變化， 把這種取樣看成是二維隨機過程的取樣更為有益， 當然實際取樣還有一些問題要注意。 ,1. 確定圖像場的點陣取樣原理 對理想取樣而言， 其取樣函數為空間抽樣函數 S（x,y）， 離散形式可表示為,（4.2-1）,δ函數的取樣陣列如圖4.2-1所示。,圖4.2-1 δ函數的取樣陣列,令fI(x,y)代表一理想的無限大連續(xù)圖像場， 其點陣取樣方法就是用空間抽樣函數S(x,y)和連續(xù)圖像函數fI(x,

22、y)相乘。 設fS(x,y)表示取樣后的圖像， 理想取樣數學模型如圖4.2-2所示。,圖4.2-2 理想取樣數學模型,由此可以得到,（4.2-2）,式中, 連續(xù)函數fI(x,y)移入求和式內變?yōu)殡x散形式fI(iΔx, jΔy)， 表明只是在取樣點(iΔx, jΔy)上計值。 根據二維傅立葉變換卷積定理， 可以得到頻域關系式為,（4.2-3）,式中,假定理想圖像的頻譜是有限的， 截止頻率為uc和vc， 根據δ函數的篩選性質對式(4.2-3

23、)進一步運算可以得式(4.2-4)和如圖4.2-3所示的取樣圖像頻譜示意圖。,（4.2-4）,圖4.2-3 取樣圖像頻譜示意圖,由式（4.2-4）和圖4.2-3可以看出， 取樣圖像頻譜是原圖像頻譜在頻域中的無窮多個重復。 重復頻譜之間間隔Δu和Δv取決于取樣間隔Δx和Δy的大小， 只要選取合適的Δx、 Δy， 就能保證Δu、 Δv等于或大于原圖像截止頻率2uc、 2vc， 那么各個重復頻譜之間就不會重疊。 在這種情況下， 選用合適的二

24、維重建濾波器， 就可以取出一個完整的原圖像頻譜（即除所有i, j≠0的頻譜成分）， 再由二維傅立葉反變換獲得和原圖像一樣的重建圖像 。,取樣正確與否的原則是能否由取樣圖像不失真地重建原圖像， 而正確取樣的關鍵是取樣間隔Δx、 Δy的選擇， 因此保證正確取樣的條件是,因為,（4.2-5）,所以,則,（4.2-6）,滿足式(4.2-5)和式(4.2-6)中“等于”條件的取樣稱為奈奎斯特取樣。 滿足兩式中大于條

25、件的取樣稱為過取樣， 而不滿足上述兩條件的取樣稱為欠取樣。 在欠取樣情況下， 會產生混淆失真。 混淆失真是取樣中應注意的一個重要問題。 防止出現(xiàn)混淆失真的辦法， 從理論上講， 若已知原圖像頻譜的最高頻率成分， 則使用過取樣或奈奎斯特取樣， 而不要使用欠取樣；,但若不知道原圖像頻譜的最高頻率成分， 則應先采用已知截止頻率的低通濾波器預先過濾圖像， 限制其高頻率成分， 再針對低通濾波器截止頻率進行過取樣或奈奎斯特取樣。 在實際取樣系統(tǒng)中，

26、取樣脈沖寬帶效應相當于一個低通濾波器， 另外光學系統(tǒng)的透鏡散焦， 孔闌衍射也都可以等效為低通濾波器的作用， 盡管會引起圖像模糊降質， 但對防止混淆失真卻是有好處的。,2. 隨機圖像場取樣 實際圖像往往有噪聲， 這種附加有噪聲的確定圖像場可以認為是隨機圖像場， 因此這里簡單介紹一下隨機圖像場的取樣。,式中, τx=x1-x2; τy=y1-y2。,用狄拉克取樣函數S（x,y）對這個隨機過程進行取樣所獲得的取樣

27、場為,（4.2-8）,因而取樣場的自相關函數為,（4.2-9）,根據狄拉克函數性質： 兩個狄拉克函數相乘還是一個狄拉克函數， 即 S(x1,y1)S(x2,y2)=S(x1-x2,y1-y2)=S(τx,τy) （4.2-10）將式（4.2-7）和式（4.2-10

28、）代入式（4.2-9）即可得,對上式兩邊取二維傅立葉變換， 根據傅氏變換定理得,（4.2-11）,（4.2-12）,圖4.2-4 有噪聲圖像的取樣（一維示意圖）,4.2.3 圖像信號量化 經過取樣的圖像只是在空間上被離散為像素（樣本）的陣列， 而每一個樣本灰度值還是一個有無窮多個取值的連續(xù)變化量， 必須將其轉化為有限個離散值， 賦予不同碼字才能真正成為數字圖像， 再由計算機或其他數字設備進行處理運算， 這樣

29、的轉化過程稱為量化。 將樣本連續(xù)灰度等間隔分層量化方式稱為均勻量化， 不等間隔分層量化方式稱為非均勻量化。 量化既然以有限個離散值來近似表示無限多個連續(xù)量， 就一定會產生誤差， 這就是所謂的量化誤差。,由此產生的失真叫量化失真或量化噪聲， 對均勻量化來講， 量化分層越多， 量化誤差越小， 但編碼時占用比特數就越多。 在一定比特數下， 為了減少量化誤差， 往往要用非均勻量化， 如按圖像灰度值出現(xiàn)的概率大小不同進行非均勻量化， 即對灰度值經

30、常出現(xiàn)的區(qū)域進行細量化， 反之進行粗量化。 在實際圖像系統(tǒng)中， 由于存在著成像系統(tǒng)引入的噪聲及圖像本身的噪聲， 因此量化等級取得太多（量化間隔太小）是沒有必要的， 因為如果噪聲幅度值大于量化間隔， 量化器輸出的量化值就會產生錯誤， 得到不正確的量化。,在應用屏幕顯示其輸出圖像時， 灰度鄰近區(qū)域邊界會出現(xiàn)“忙動”現(xiàn)象。 假設噪聲是高斯分布， 均值為0， 方差為σ2， 在有噪聲情況下， 最佳量化層選取有兩種方法， 一是令正確量化的概率大于某

31、一個值， 二是使量化誤差的方差等于噪聲方差。 針對輸出圖像是專供人觀察評價的應用， 研究出了一些按人的視覺特性進行非均勻量化方式， 如圖像灰度變化緩慢部分細量化， 而圖像灰度變化快的細節(jié)部分粗量化， 這是由于視覺掩蓋效應被發(fā)現(xiàn)而產生的。 再如按人的視覺靈敏度特征進行對數形式量化分層等。,4.3 數字圖像壓縮方法的分類,圖像壓縮的基本目標就是減小數據量， 但最好不要引起圖像質量的明顯下降， 在大多數實際應用中，

32、 為了取得較低的比特率， 輕微的質量下降是允許的。 至于圖像壓縮到什么程度而沒有明顯的失真， 則取決于圖像數據的冗余度。 較高的冗余度形成較大的壓縮， 而典型的圖像信號都具有很高的冗余度， 正是這些冗余度的存在允許我們對圖像進行壓縮。,例如， 我們在第2章介紹的空間冗余和時間冗余是圖像信號最常見的冗余， 所有的這些冗余度都可以被除去而不會引起顯著的信息損失， 但壓縮編碼無法減少冗余度。 不同的出發(fā)點有不同的分類， 按照信息論的角度， 數

33、字圖像壓縮方法一般可分為： （1） 可逆編碼（Reversible Coding 或Information Preserving Coding）， 也稱為無損壓縮。 這種方法的解碼圖像與原始圖像嚴格相同， 壓縮是完全可恢復的或無偏差的， 無損壓縮不能提供較高的壓縮比。,（2） 不可逆編碼（Non-Reversible Coding）， 也稱為有損壓縮。 用這種方法恢復的圖像較原始圖像存在一定的誤差， 但視覺效果一般

34、是可接受的， 它可提供較高的壓縮比。,按照壓縮方法的原理， 數字圖像壓縮方法可分為： （1） 預測編碼（Predictive Coding）。 預測編碼是一種針對統(tǒng)計冗余進行壓縮的方法， 它主要是減少數據在空間和時間上的相關性， 達到對數據的壓縮， 是一種有失真的壓縮方法。 預測編碼中典型的壓縮方法有DPCM和ADPCM等， 它們比較適合于圖像數據的壓縮。,（2） 變換編碼（Transform Coding）。

35、變換編碼也是一種針對統(tǒng)計冗余進行壓縮的方法。 這種方法將圖像光強矩陣（時域信號）變換到系數空間（頻域）上進行處理。 常用的正交變換有DFT（離散傅氏變換）、 DCT（離散余弦變換）、 DST（離散正弦變換）、 哈達碼變換和Karhunen-Loeve變換。,（3） 量化和矢量量化編碼（Vector Quantization）。 量化和矢量量化編碼本質上也還是一種針對統(tǒng)計冗余進行壓縮的方法。 當我們對模擬量進行數字化時， 必然要經歷一個量

36、化的過程。 在這里量化器的設計是一個很關鍵的步驟， 量化器設計的好壞對于量化誤差的大小有直接的影響。 矢量量化是相對于標量量化而提出的， 如果我們一次量化多個點， 則稱為矢量量化。,（4） 信息熵編碼（Entropy Coding）。 根據信息熵原理， 用短的碼字表示出現(xiàn)概率大的信息， 用長的碼字表示出現(xiàn)概率小的信息。 常見的方法有哈夫曼編碼、 游程編碼以及算術編碼。 （5） 子帶編碼（Sub-band Codi

37、ng）。 子帶編碼將圖像數據變換到頻域后， 按頻率分帶， 然后用不同的量化器進行量化， 從而達到最優(yōu)的組合。 或者是分步漸近編碼， 在初始時對某一頻帶的信號進行解碼， 然后逐漸擴展到所有頻帶， 隨著解碼數據的增加， 解碼圖像也逐漸地清晰起來。 此方法對于遠程圖像模糊查詢與檢索的應用比較有效。,（6） 結構編碼（Structure Coding）， 也稱為第二代編碼（Second Generation Coding）。 編碼時首先求出圖像

38、中的邊界、 輪廓、 紋理等結構特征參數， 然后保存這些參數信息。 解碼時根據結構和參數信息進行合成， 從而恢復出原圖像。 （7） 基于知識的編碼（Knowledge-Based Coding）。 對于人臉等可用規(guī)則描述圖像， 利用人們對其的知識形成一個規(guī)則庫， 據此將人臉的變化等特征用一些參數進行描述， 從而用參數加上模型就可以實現(xiàn)人臉的圖像編碼與解碼。圖像壓縮算法的總體框圖如圖4.3-1所示。,圖4.3-1 圖像

39、壓縮算法的總體框圖,下面幾節(jié)主要介紹幾種常見的壓縮編碼方法： 信息熵編碼方法（如哈夫曼編碼、 游程編碼和算術編碼）、 預測編碼和變換編碼， 并介紹新一代編碼方法（如知識基編碼和分形編碼）等以及相關知識。 由于矢量量化編碼和子帶編碼方法在上一章中結合音頻編碼已經介紹， 它們在應用于圖像時原理基本相同， 這里不再贅述。,4.4 典型的熵編碼方法,4.4.1 基本概念 1． 圖像熵和平均碼字長度

40、 1） 圖像熵（Entropy） 設數字圖像像素灰度級集合為 （W1, W2,…,Wk，…,WM）， 其對應的概率分別為P1， P2， …， Pk， …， PM。 按信息論中信源信息熵定義， 數字圖像的熵H為,由此可見， 一幅圖像的熵就是這幅圖像的平均信息量度， 也是表示圖像中各個灰度級比特數的統(tǒng)計平均值。 式(4.4-1)所表示的熵值是在假定圖像信源無記憶（即圖像的各個灰度級不相關）的前提下獲得

41、的， 這樣的熵值常稱為無記憶信源熵值， 記為H0(·)。 對于有記憶信源， 假如某一像素灰度級與前一像素灰度級相關， 那么公式(4.4-1)中的概率要換成條件概率P(Wi/Wi-1)和聯(lián)合概率P(Wi, Wi-1)， 則圖像信息熵公式變?yōu)?（4.4-1）,式中， P(Wi, Wi-1)=P(Wi)P(Wi/Wi-1), 則稱H(Wi/Wi-1)為條件熵。 因為只與前面一個符號相關， 故稱為一階熵H1(·)。 如果與前

42、面兩個符號相關， 求得的熵值就稱為二階熵H2(·)。 依此類推可以得到三階和四階等高階熵， 并且可以證明 H0（·）＞H1（·）＞H2（·）＞H3（·）＞…,(4.4-2),香農信息論已證明： 信源熵是進行無失真編碼的理論極限。 低于此極限的無失真編碼方法是不存在的， 這是熵編碼的理論基礎。 而且可以證明， 如果考慮像素間的相關性， 使用高階熵一定可以獲得更高的

43、壓縮比。,2） 平均碼字長度 設βk為數字圖像第k個碼字Ck的長度(二進制代數的位數)， 其相應出現(xiàn)的概率為Pk， 則該數字圖像所賦予的碼字平均長度R為,（4.4-3）,3） 編碼效率在一般情況下， 編碼效率往往用下列簡單公式表示,（4.4-4）,式中， H為信源熵， R為平均碼字長度。,根據信息論中信源編碼理論， 可以證明在R≥H條件下總可以設計出某種無失真編碼方法。 若編碼結果使R遠大于H， 表明這種編碼方

44、法效率很低， 占用比特數太多。 例如對圖像樣本量化值直接采用PCM編碼， 其結果平均碼字長度R就遠比圖像熵H大。 若編碼結果使R等于或很接近于H， 這種狀態(tài)的編碼方法稱為最佳編碼。 它既不丟失信息而引起圖像失真， 又占用最少的比特數， 例如下面要介紹的哈夫曼編碼即屬于最佳編碼方法。,若要求編碼結果R<H， 則必然丟失信息而引起圖像失真。 這就是在允許失真條件下的一些失真編碼方法。 熵編碼的目的就是要使編

45、碼后的圖像平均比特數R盡可能接近圖像熵H。 一般是根據圖像灰度級數出現(xiàn)的概率大小賦予不同長度的碼字， 概率大的灰度級用短碼字， 反之， 用長碼字。 可以證明， 這樣的編碼結果所獲得的平均碼字長度最短。 這就是下面要介紹的變長最佳編碼定理。,2. 變長最佳編碼定理 【定理】 在變長編碼中， 對出現(xiàn)概率大的信息符號賦予短碼字， 而對于出現(xiàn)概率小的信息符號賦予長碼字。 如果碼字長度嚴格按照所對應符號出現(xiàn)概率大小逆序排列

46、， 則編碼結果平均碼字長度一定小于任何其他排列方式。 這個定理就是下面要介紹的哈夫曼編碼方法的理論基礎。 設圖像灰度級為W1, W2, …, Wi…, WN； 各灰度級出現(xiàn)的概率分別為P1， P2， …， Pi， …， PN；,編碼所賦予的碼字長度分別為t1， t2， …， ti， …， tN； 則編碼后圖像平均碼字長度R應為,再令嚴格按照定理規(guī)則進行編碼， 其結果平均碼字長度為R1； R2為將其中任兩個灰度

47、級不按定理規(guī)則編碼（即概率大的灰度級賦予長碼字。 反之， 用短碼字）， 而其他所有灰度級仍按定理規(guī)則編碼所得的圖像平均碼字長度， 那么R2應等于R1加上“不按定理規(guī)則編碼所增加的平均碼字長度”ΔR。 只要證明ΔR大于0， 即可以證明上述定理。,3. 可變長最佳編碼的平均碼字長度 設可變長編碼所用碼元進制為D， 被編碼的信息符號總數為N， 第i個符號出現(xiàn)的概率為Pi， 與其對應的碼字長度為ti， 則可以證明這種編碼

48、結果平均碼字長度R落在下列區(qū)間內,式中,  , 由此可以引導出對某一信息符號存在下式,（4.4-5）,對二進制碼進一步簡化為 -lbPi≤ti＜-lbPi+1 （4.4-6）,4. 惟一可譯編碼 有些情況下， 為了減少表示圖像的平均碼字長度， 往往對碼

49、字之間不加同步碼。 但是， 這樣就要求所編碼字序列能被惟一地譯出來。 滿足這個條件的編碼稱為惟一可譯編碼， 也常稱為單義可譯碼。 單義可譯碼往往是采用非續(xù)長代碼。,1） 續(xù)長代碼和非續(xù)長代碼 若代碼中任何一個碼字都不是另一個碼字的續(xù)長， 也就是不能在某一碼字后面添加一些碼元而構成另一個碼字， 稱其為非續(xù)長代碼。 反之， 稱其為續(xù)長代碼。 如二進制代碼［0， 10， 11］即為非續(xù)長代碼， 而［0， 01， 11］

50、則為續(xù)長代碼。 因為碼字01可由碼字“0”后加上一個碼元“1”構成。,2） 單義代碼 在介紹單義代碼前， 先簡單介紹一下克勞夫特(Kraft)不等式： 若信源符號有m種取值， 其碼字長度分別為li(i=1， 2， …, m)； 又設最長的碼字長度為L， 碼元種類（即多少進制碼）為D， 長度為li的碼字占用了 個長度為L的碼字， 也就是必須有,對于二進制, 則有,。,任意有限長的碼字序列， 只能被

51、惟一地分割成一個個碼字， 則這樣的碼字序列稱為單義代碼。 單義代碼的充要條件是滿足克勞夫特(Kraft)不等式,（4.4-7）,式中, D為代碼中碼元種類， 對于二進制D＝2； n為代碼中碼字個數； ti為代碼中第i個碼字的長度（即碼元個數）。,如代碼C＝［00， 10， 001， 101］， 因為是二進制碼， 則D＝2， 共有4個碼字C1＝00、 C2＝10、 C3＝001、 C4＝101， 其相應的長度為t1=2、 t2=2

52、、 t3=3、 t4=3， 代入式（4.4-7）可得,4.4.2 哈夫曼（Huffman）編碼方法 哈夫曼編碼是根據可變長度最佳編碼定理， 應用哈夫曼算法而產生的一種編碼方法。 在具有相同輸入概率集合的前提下， 它的平均碼字長度比其他任何一種惟一可譯碼都小， 因此， 也常稱其為緊湊碼。 下面以一個具體的例子來說明其編碼方法， 如圖4.4-1所示。,圖4.4-1 哈夫曼（Huffman）編碼的示例,1. 編碼步驟

53、 (1) 先將輸入灰度級按出現(xiàn)的概率由大到小順序排列（對概率相同的灰度級可以任意顛倒排列位置）。 （2） 將最小兩個概率相加， 形成一個新的概率集合。 再按第(1)步方法重排（此時概率集合中概率個數已減少一個）。 如此重復進行， 直到只有兩個概率為止。,（3） 分配碼字。 碼字分配從最后一步開始反向進行， 對最后兩個概率一個賦予“1”碼， 一個賦予“0”碼。 如概率0.60賦予“0”碼，

54、 0.40賦予“1”碼（也可以將0.60賦予“1”碼， 0.40賦予“0”碼）。 如此反向進行到開始的概率排列。 在此過程中， 若概率不變， 則仍用原碼字。 如圖4.4-1中第六步中概率0.40到第五步中仍用“1”碼。 若概率分裂為兩個， 其碼字前幾位碼元仍用原來的。 碼字的最后一位碼元一個賦予“0”碼元， 另一個賦予“1”碼元。 如圖中第六步中概率0.60到第五步中分裂為0.37和0.23， 則所得碼字分別

55、為“00”和“01”。,2. 前例哈夫曼編碼的編碼效率計算 根據式(4.4-1)求出前例信源熵為,根據式(4.4-3)求出平均碼字長度為,根據式（4.4-4）求出編碼效率η為,可見哈夫曼編碼效率很高。,*4.4.3 游程編碼 在圖像中， 尤其是一些不太復雜的圖像和計算機生成的圖像中， 往往存在著灰度或顏色相同的圖像塊， 對這樣的圖像進行掃描時， 對應這些相同灰度和顏色的圖像塊就會有連續(xù)多行掃描行數據

56、具有相同的數值， 而且在同一行上會有許多連續(xù)的像素點具有同樣的數值。 只保留連續(xù)相同像素值中的一個值及具有相同數值的像素點數目， 這種方法就是人們常說的行程編碼或游程編碼（RLC， Run Length Coding）， 而且這種方法可以用少的數據量來表示圖像信息。,在二元序列中， 只有兩種符號， 即“0”和“1”； 這些符號可連續(xù)出現(xiàn)， 連“0”這一段稱為“0”游程， 連“1”這一段稱為“1”游程。 它們的長度分別為L(0)和L(1)

57、。 “0”游程和“1”游程總是交替出現(xiàn)的。 倘若規(guī)定二元序列是以“0”開始， 第一個游程是“0”游程， 第二個必為“1”游程， 第三個又是“0”游程等等。 對于隨機的二元序列， 各游程長度將是隨機變量； 其取值可為1， 2， 3， …， 直到無限。,定義了游程和游程長度， 就可把任何二元序列變換成游程長度的序列， 或簡稱游程序列。 這種變換是一一對應的， 也就是可逆的。 例如有一二元序列

58、 000101110010001… 可變換成下列游程序列 3113213…,*4.4.4 算術編碼 哈夫曼編碼、 游程編碼等無損編碼都是建立在符號和碼字相對應的基礎上的， 這種編碼通常叫做塊碼或分組碼。 此時， 信源符號應是多元的， 而且不考慮符號相關性。 要用于最常見的二元序列， 須

59、采用游程編碼、 分幀編碼或合并符號等方法， 轉換成多值符號， 而這些符號間的相關性也不予考慮。 這就使信源編碼的匹配原則不能充分滿足， 編碼效率就有所損失。 倘若要較好的解除相關性， 常需在序列中取很長一段， 而這將遇到采用等長碼時的那種困難。,為了克服這種局限性， 就需跳出塊碼的范疇， 研究非塊碼的編碼方法。 這就是從全序列出發(fā)， 采用遞推形式的連續(xù)編碼。 其實香農早就提出信源序列的積累概率的概念， 把這個概率映射到［0，1）區(qū)間上，

60、 使每個序列對應區(qū)間內的一點， 這就是一個二進位的小數。 這些點把［0，1）區(qū)間分成許多小段， 每段的長度等于某一序列的概率。 再在段內取一個二進位小數， 其長度可與該序列的概率匹配， 達到高效編碼的目的。 這也就是算術編碼的基本概念。 在這里將著重討論積累概率的意義以及遞推計算等， 以說明算術編碼的基本原理。 再通過實例介紹獨立二元序列的編碼過程。,1. 積累概率的遞推計算 我們先從信源符號的積累概率開始， 再

61、討論序列的積累概率。 設信源符號集為 A={a0, a1, a2, …, am-1}  相應的概率為Pr， r=0， 1， 2， …， m-1。 定義各符號的積累概率為,（4.4-8）,顯然， 由上式可得 P0=0, P1=p0, P2=p0+p1， …  而且

62、 pr=Pr+1-Pr 由于Pr和Pr+1都是小于1的正數， 可用［0,1)區(qū)間內的兩個點來表示， 則pr就是這兩點間的小區(qū)間的長度。 不同的符號有不同的小區(qū)間， 它們互不重疊， 這種小區(qū)間內任一個點可作為該符號的代碼。,現(xiàn)在來計算序列的積累概率。 為了簡單起見， 先以獨立二元序列為例來計算， 所得的結果很容易推廣到一般情況。 設有一序列S=011， 這種三個二元符號的序

63、列可按自然二進數排列， 000， 001， 010， …， 則S的積累概率為 P(S)=p(000)+p(001)+p(010) （4.4-9） 倘若S后面接一個“0”， 積累概率就成為P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)=p(000)+p(001)+p(010)=P(S),因為兩個四元符號的最后一位是“0”和“1

64、”時， 根據歸一律， 它們的概率和應等于前三位的概率， 即p(0000)+p(0001)=p(000)等。,倘若S后面接一個“1”， 則其積累概率是 P(S1)=p(0000)+p(0001)+p(0010)+p(0011) +p(0100)+p(0101)+p(0110) =P(S)+p(0110)=P(S)+p(S)p0 

65、 由于二元集的積累概率為P0=0， P1=p0， 所以上面兩式可統(tǒng)一寫成 P(Sr)=P(S)+p(S)Pr r=0， 1 (4.4-10),這樣寫的式子很容易推廣到多元序列， 即可得到一般的積累概率遞推公式 P(Sar)=P(S)+p(S)Pr (4.4-11) 以及序列的概率公式

66、 p(Sar)=p(S)pr (4.4-12) 對于有相關性的序列， 上面的兩個遞推公式也是適用的， 只是上式中的單符號概率應換成條件概率。,用遞推公式可逐位計算序列的積累概率， 而不用像式（4.4-9）那樣列舉所有排在前面的那些序列概率。 實際上， 可用兩個存儲器把p(S)和P(S)存下來， 然后根據輸入符號和式(4.4-11)、 式(4

67、.4-12)， 更新兩個存儲器中的值。 在起始時可令 P（φ）=0, p(φ)=1其中φ代表空集， 只有一個符號ar的序列就是φar。,2. 代碼長度 從以上關于積累概率P(S)的計算中可看出， P(S)把區(qū)間［0,1）分割成許多小區(qū)間， 每個小區(qū)間的長度等于各序列的概率p(S)， 而這些小區(qū)間內的任一點可用來代表這些序列， 現(xiàn)在來討論如何選擇這個點。

68、 令,（4.4-13）,其中［X］代表大于或等于X的最小整數， 把積累概率P(S)寫成二進位的小數， 取其前L位， 若有尾數， 就進位到第L位， 這樣得到一個數C。 例如, P(S)=0.10110001， p(S)=1/7, 則L=3, 得C＝0.110。 這個C就可以作為S的碼字。 可以證明這C點必然在長度為p(S)的小區(qū)間內， 因而是可以惟一解碼的。,這樣構成的碼字，

69、 編碼效率是很高的， 因為已經達到概率匹配， 尤其是當序列很長時。 由式（4.4-13）可見， 對于長序列， p(S)必然很小， L與概率倒數的對數已幾乎相等。 也就是取整數所造成的差別很小， 平均代碼長度將接近S的熵值。,實際編碼過程是這樣的。 可先設定兩個存儲器， 起始時一個為“0”， 另一個為“1”， 分別代表空集的積累概率和概率。 每輸入一個信源符號, 更新一次， 得到P(S)值后， 按前述方法得到碼字C， 暫存起來, C值也隨