DVIP04-信源編碼和率失真理論

第04章信源編碼和率失真理論SourceCodeandRate-DistortionTheory內容提要Outline信源編碼定理信源壓縮方法圖像冗余率失真理論22/4/20233香農信息論的基本任務1948年shannon發(fā)表了“通信的數學理論”奠定了信息論理論基礎基本任務是設計有效而可靠的通信系統(tǒng)可靠是要使信源發(fā)出的消息經過傳輸后，盡可能準確地、不失真地再現(xiàn)在接收端有效是用盡可能短的時間和盡可能少的設備來傳輸一定量的消息32/4/20234通信系統(tǒng)模型信源、信道、信宿信源是消息的來源，信道是消息傳送媒介，信宿是消息的目的地。信源編碼器信道譯碼器信宿干擾源42/4/20235通信系統(tǒng)模型進一步細分信源信源編碼器糾錯編碼器調制器信道干擾源解調器糾錯譯碼器信源譯碼器信宿等效離散信道等效離散信源等效信宿信道編碼器信道譯碼器52/4/20236各部件功能信源產生消息的源，消息可以是文字，語言，圖像?？梢噪x散，可以連續(xù)。隨機發(fā)生。研究的主要問題是消息的統(tǒng)計特性和產生信息的速率編碼器信源編碼器：對信源輸出進行變換，求得有效性信道編碼器：對信源編碼輸出變換，提高抗干擾性調制器：將信道編碼輸出變成適合信道傳輸的方式62/4/20237各部件功能信道信號從發(fā)端傳到收端的介質干擾源系統(tǒng)各部分引入的干擾，包括衰落，多徑，碼間干擾，非線性失真，加性噪聲，主要是統(tǒng)計特性信道的中心問題是研究信道的統(tǒng)計特性和傳信能力，即信道容量72/4/20238各部件功能譯碼器編碼器的逆變換中心問題是研究各種可實現(xiàn)的解調和譯碼方法信宿信息的接收者82/4/20239信息、消息和信號信息一個抽象的概念，可以定量的描述。信息、物質和能量是構成一切系統(tǒng)的三大要素消息是信息的載體，相對具體的概念，如語言，文字，數字，圖像信號表示消息的物理量，電信號的幅度，頻率，相位等等9信源編碼信源信道編碼調制信道解調噪聲干擾信道解碼信源解碼信宿二進制符號用二進制符號流表示信源適應傳輸信道的特性數字傳輸系統(tǒng)10信源的原始信號絕大多數是模擬信號，因此，信源編碼的第一個任務是模擬和數字的變換，即：A/D、D/A。取樣頻率取決于原始信號的帶寬：

fc=2w，w為信號帶寬取樣點的比特數決定編解碼后的信號質量：

SNR＝6

L(dB)，L為量化位數但是，由于傳輸信道帶寬的限制，又由于原始信源的信號具有很強的相關性，則信源編碼不是簡單的A/D、D/A，而是要進行壓縮。為通信傳輸而進行的信源編碼，主要是壓縮編碼。信源編碼要考慮的因素：

－信源的統(tǒng)計特性。

－傳輸信道引入的損傷，如誤碼。

－信宿的質量要求。數字傳輸系統(tǒng)－概述11信源編碼定理：對于給定的失真率D，總可以找到一種信源編碼方法，只要信源速率R大于率失真

R(D)，就可以在平均失真任意接近D的條件下實現(xiàn)波形重建。說明1：R(D)稱為率失真函數，它是單調非增函數，速率越高，平均失真越小。說明2：為了保證在一定速率下的失真，必需采用信源編碼，因而會引入編碼延時。信道編碼定理：如果信源速率R小于信道容量

C，總可以找到一種信道編碼方法，使得信源信息可以在有噪聲信道上進行無差錯傳輸，即：RC，無差錯傳輸條件。說明1：信道容量C是根據仙儂定理得到的

C＝Wlog2(1+S/N)說明2：為了保證無差錯傳輸，必需采用信道編碼，因而會引入編碼延時。數字傳輸系統(tǒng)－信源和信道編碼12信息傳輸定理： 將信源編碼定理和信道編碼定理綜合，就得到信息傳輸定理。即：為保證無差錯傳輸及失真度，必需滿足：R(D)≤R≤C，即CR(D)。說明1：在一般數字通信系統(tǒng)中，信源編碼和信道編碼可以分開考慮。信道編碼定理給出無差錯的速率上限R<C，否則產生誤碼；信源編碼定理給出無失真的速率下限R(D)<R，否則產生的失真大于所要求的失真D。說明2：為了實現(xiàn)理想性能，都要付出延時的代價。數字傳輸系統(tǒng)－信息傳輸定理13內容提要Outline信源編碼定理信源壓縮方法圖像冗余率失真理論14壓縮方法信源壓縮方法可以主要分為三大類：利用人眼的視覺特性模擬壓縮技術統(tǒng)計編碼人眼視覺特性：因為最終評價圖像的質量是通過人眼來完成，所以可利用人眼的一些視覺特性對圖像進行有損壓縮，而產生的誤差又不易被人眼所察覺。模擬壓縮技術：常用的有亞取樣、隔行隔點取樣以及減少刷新速率。它們的使用都有一定的限制條件。亞取樣可能導致混迭現(xiàn)象。隔行隔點取樣將降低空間分辨率，可能導致爬行現(xiàn)象，當然也可在收端再插入行和點。減少刷新速率，將出現(xiàn)閃爍，且運動的連續(xù)性不好。15壓縮方法統(tǒng)計編碼：兩種有效的壓縮方法無失真壓縮Loss-lesscompression：即熵編碼，如游程長

(run-length)

編碼和哈夫曼(Huffman)

編碼；

2到5倍壓縮比

有失真壓縮Lossycompression：即允許有部分失真，遵循率失真函數，如預測編碼、變換編碼、運動補償技術等

5到250倍壓縮比－信源的統(tǒng)計特性。

－傳輸信道引入的損傷，如誤碼。

－信宿的質量要求。16壓縮-無失真方法游程數據編碼101000100010001001101=1+4x0100+1101源21

bits→→壓縮后12

bits變字長編碼（Variable-lengthCode,VLC)哈夫曼編碼(HuffmanCode)概率大的塊（事件）賦予短碼概率小的塊賦予長碼算術編碼(ArithmeticCode)概率大的塊（事件）賦予短碼，概率小的塊賦予長碼但它的編碼過程與Huffman編碼卻不相同17壓縮-有失真方法量化Quantisation-截短或舍入DPCM編碼運動估計和補償變換編碼(TransformCoding)KLT變換離散余弦變換Discretecosinetransform(DCT)小波變換WaveletTransform分形編碼FractalCoding18內容提要Outline信源編碼定理信源壓縮方法圖像冗余率失真理論19圖象的相關性（冗余度）

空間冗余例:圖象中包含許多規(guī)則物體，它們的亮度、飽和度及顏色可能都一樣，因此，圖象在空間上具有很大的相關性。例如Lenna

圖象的臉部和肩部。例:序列圖象時間冗余20信息熵冗余信息量：從N個可能事件中選出一個事件所需要的信息度量。設事件X的概率為P(x)，則信息量定義為：

I(x)=

-log2P(x)信息熵：如果將信源所有可能事件的信息量進行平均，就得到了信息熵(entropy)。熵就是平均信息量。信息源的符號集為Xj(j=1,2,3……..N)，設X出現(xiàn)的概率為P(xj),則信息源X的熵為圖象的相關性（冗余度）當Xj

等概時，H(X)最大。當Xj

非等概時，H(X)不是最大，就存在冗余。21結構冗余圖象有非常強的紋理結構如草席圖結構上存在冗余圖象的相關性（冗余度）知識冗余圖像的理解與某些基礎知識有關例:人臉的圖像有同樣的結構：嘴的上方有鼻子，鼻子上方有眼睛，鼻子在中線上……22視覺冗余視覺冗余是非均勻、非線性的。例:人類視覺分辨率為26

，但常用28

就是數據冗余。其它冗余圖象空白的非定長性。圖象的相關性（冗余度）23內容提要Outline信源編碼定理信源壓縮方法圖像冗余率失真理論24率失真理論：有損壓縮前面我們已經討論了離散信源的無失真編碼/熵編碼理論但無失真編碼并非總是必需的和可能的無失真壓縮存在固有的限制：熵人的認知器官人的視覺/聽覺系統(tǒng)只能感知有限范圍的信號如果我們不能看見/聽見，為什么還編碼呢？從部分損失恢復的能力如低幀率會使得運動跳躍，但仍然可被感知由于受到信息存儲、處理或傳輸設備的限制，而不得不對信源輸出的信號作某種近似以降低熵率，如對連續(xù)信號的數字化、音視頻。25率失真理論：有損壓縮無損編碼：

x=x’亦稱為熵編碼（entropycoding）或可逆編碼（reversiblecoding）有損編碼：x

x’亦稱為不可逆編碼（irreversiblecoding）圖象源編碼器解碼器顯示失真d≤D

時的最小碼率R失真d碼流解碼后的表示26率失真理論：有損壓縮如果允許信號存在一定可接受的失真度D，則能得到更低的比特碼率R。DistortionDRateR無失真編碼

D=0率失真理論旨在尋求一種聯(lián)系定長編碼的失真度與編碼數據率的方法。率失真理論并不針對特定的編碼方法27率失真理論：失真度量1/5符號{xn}原始信源輸出{yn}重構輸出平方誤差d(x,y)=(x–y)2絕對誤差d(x,y)=|x–y|絕對最大誤差(Absolutemaximumerror)28率失真理論：失真度量2/5信噪比(Signal-to-noiseratio,SNR)平均絕對誤差(Averageabsolutedifference)均方誤差(Meansquarederror,MSE)29率失真理論：失真度量3/5峰值信噪比(Peak-signal-to-noiseratio,PSNR)在實際應用中常用峰值信噪比PSNR，通常PSNR比SNR大12～15dB。一般認為：峰值信噪比與圖像質量近似成正比關系。但PSNR有其局限性：由于均方誤差σd2

是功率的平均，因此它不能完全地反映主觀感覺。例如，在圖像出現(xiàn)窄的水平亮條干擾時，雖然圖像的PSNR高，但主觀感覺差；又如在圖像傳輸處理過程中出現(xiàn)的小錯誤，雖然它不會對PSNR值產生大的影響，但如果其位置恰好處在圖像理解的關鍵位置，由于人類視覺系統(tǒng)對關鍵信息的改變非常敏感，因此，會大大影像主觀質量的評價。30率失真理論：失真度量4/5峰值信噪比=6.24峰值信噪比=5.98結論：1、峰值信噪比度量與人的視覺感知并不完全一致！但由于均方誤差和信噪比在數學上容易處理，另外也缺少性價比更好的替代方法。因此，上述方法在圖像處理的客觀失真測量方面仍得到了大量的應用。

2、需要尋求更加符合人類視覺感知的客觀度量方法以及相應的編碼理論和方法。31率失真理論：失真度量5/5客觀評價：用數學表達式表示原始信號與重構信號之間的差異如上述準則不一定符合用戶的感知評價，但在數學計算上可以控制用戶主觀評價：最終用戶評價重構信號的質量（可接受程度）工作量大符合用戶感知的真實情況，但數學計算可能不好處理介于二者中間：用數學模型表示人類的感知機制將信源輸出和重構信號都投影到感知空間然后在感知空間中度量二者之間的差異但人類感知過程很難建模，或數學模型太復雜32率失真理論：條件自信息信源編碼：將輸入符號集映射成另一個輸出符號集條件自信息I(aj|bk)

表示在發(fā)現(xiàn)信源編碼器輸出為bk

時，對應的信源發(fā)出符號aj

的不確定程度。而條件自信息I(bk|aj)

表示在信源發(fā)出符號為aj

而編碼輸出為bk

的不確定程度。信源編碼器33率失真理論：互信息互信息：自信息與條件自信息之間的差I(aj)表示aj

所含的信息量（不確定性），I(aj|bk)

表示在知道bk

后aj

還保留的信息量，所以互信息表示符號bk

為aj

提供的信息量。平均互信息：表示信源X的平均不確定性與其在信源Y被確定條件下仍保留的平均不確定性之差，即隨機變量Y對X提供的平均信息量。34率失真理論：互信息-條件熵平均條件熵X、Y的聯(lián)合熵定義為35率失真理論：互信息-條件熵例題請求以下熵值：36率失真理論：互信息-Venn圖互信息量與熵的關系僅當X與Y獨立時，等號成立。37例題：若信源編碼器是一個簡單的一一對應關系，即m=n，且即所以互信息

I(aj;bj)=I(aj)，即

bj

提供了aj

的全部信息。信息保持編碼屬于這種情況。例如：只要傳輸不出錯，則收到任一碼字，如“110”后，即可判斷出所發(fā)的信源符號是“7”。率失真理論：互信息38同上例，假設實際信源的8個符號，但發(fā)現(xiàn)1,2;3,4;5,6;7,8

兩兩相差不多，可用同一碼字代表，如

n=4個情況，用2bit即可表示，較上面的3bit編碼，節(jié)省了1bit。但引入了一定的誤差，如收到碼“01”后判斷為“3”，若信源實際發(fā)出的是“4”，則有了誤差，這個誤差可能是允許的！！！該誤差的產生是由于對信源的某些符號進行了合并，減少了事件的數目，從而使新信源的熵降低。所以，當集合中事件結構發(fā)生變化時，會引起信源概率結構的變化，從而影響到信源熵的變化。率失真理論：互信息39率失真理論：互信息只要允許誤差存在，就可以減少編碼輸出的字符數，因而也可以降低碼率。可是字符數越少，譯碼誤差或失真就越大。問題：在給定的失真條件下，最小需要多大的碼率，才能保證不超過允許的失真。即要確定每個編碼符號至少應提供的關于信源符號的信息量。用互信息表示，即在一定的失真條件下，得到平均互信息的最小值minI(X;Y)。率失真函數的基本含義40率失真理論：平均互信息互信息由以下概率決定：信源符號概率P(aj)編碼輸出符號概率Q(bk)已知信源符號出現(xiàn)的條件概率Q(bk|aj)在確定信源的條件下，P(aj)已知，選擇編碼方法實際上是通過改變條件概率

Q(bk|aj)的分布來控制平均互信息量。41率失真理論在信源允許一定失真情況下所需的最少碼率：在允許一定失真D的情況下，信源輸出的信息傳輸率可壓縮到R(D)。從分析失真函數、平均失真出發(fā)，求出信息率失真函數R(D)在一些實際問題中，信號有一定的失真是可以容忍的。但是當失真大于某一限度后，信息質量將被嚴重損傷，甚至喪失其實用價值。要規(guī)定失真限度，必須先有一個定量的失真測度。為此引入失真函數?？陀^的失真函數如前所述42率失真理論：失真函數假如某一信源X，輸出樣值為x，x∈{a1,a2,….,am}，經過有失真的信源編碼器，輸出Y，樣值為y，y∈{b1,b2,….,bm}.失真的大小用一個量來表示，即失真函數d(aj,bk)以衡量用bk

代替aj

所引起的失真程度。一般失真函數（失真度）定義為：信源編碼器43率失真理論：平均失真平均失真：失真函數d(aj,bk)的數學期望或統(tǒng)計平均值，記為

由條件概率Q(bk|aj)

控制。44率失真函數R(D)信源編碼器的目的是使編碼后所需的碼率R盡量小。然而R越小，引起的平均失真就越大。給出一個失真的限制值D*，在滿足平均失真D(Q)≤D*的條件下，選擇一種編碼方法使碼率R盡可能小。所以若要求平均失真函數D(Q)≤D*，則必然存在一個條件概率Q(bk|aj)

，使得D(Q)≤D*，記為保證失真在允許范圍D*內的條件概率的集合。45率失真函數R(D)由于互信息I(X;Y)也受Q的控制，可將率失真函數R(D)（亦稱碼率-失真函數）定義為率失真函數是在允許失真為D*的條件下，信源編碼給出的平均互信息的下界，也是數據壓縮的極限碼率。

無記憶離散信源限失真編碼定理：若一離散無記憶平穩(wěn)信源的率失真函數是R(D)，則當碼率R>R(D)，只要信源序列長度足夠長，一定存在一種編碼方式，其編碼失真≤D+ε，為任意小的正數。逆定理：當碼率R<R(D)，則無論采用什么編譯碼方法，其平均失真一定會大于失真限度D。46率失真理論：限失真信源編碼定理限失真信源編碼定理只能說明最佳編碼是存在的，而具體構造編碼方法卻一無所知。因而就不能像無失真編碼那樣從證明過程中引出概率匹配的編碼方法。一般只能從優(yōu)化的思路去求最佳編碼。實際上迄今尚無合適的可實現(xiàn)的編碼方法可接近R(D)這個界。計算一個具體信源的R(D)也很困難條件極小值求解問題，其解的結果一般以參數形式給出，其中起控制作用的變量只有Q(bk)。編碼就是通過對Q(bk)