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

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

fc=2w，w為信號帶寬取樣點(diǎn)的比特?cái)?shù)決定編解碼后的信號質(zhì)量：

SNR＝6

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

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

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

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

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

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

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

(run-length)

編碼和哈夫曼(Huffman)

編碼；

2到5倍壓縮比

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

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

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

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

bits→→壓縮后12

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

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

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

I(x)=

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

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

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

，但常用28

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

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

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

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

D=0率失真理論旨在尋求一種聯(lián)系定長編碼的失真度與編碼數(shù)據(jù)率的方法。率失真理論并不針對特定的編碼方法27率失真理論：失真度量1/5符號{xn}原始信源輸出{yn}重構(gòu)輸出平方誤差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)在實(shí)際應(yīng)用中常用峰值信噪比PSNR，通常PSNR比SNR大12～15dB。一般認(rèn)為：峰值信噪比與圖像質(zhì)量近似成正比關(guān)系。但PSNR有其局限性：由于均方誤差σd2

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

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

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

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

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

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

而編碼輸出為bk

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

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

表示在知道bk

后aj

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

為aj

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

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

bj

提供了aj

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

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

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

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

代替aj

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

由條件概率Q(bk|aj)

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

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

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