多媒體編碼與通信02 熵編碼課件

多媒體編碼與通信111111多媒體編碼與通信1第二章熵編碼技術(shù)熵編碼概述信息熵理論Huffman編碼指數(shù)哥倫布編碼算術(shù)編碼基于上下文的熵編碼自適應(yīng)熵編碼其他無(wú)損編碼方法第二章熵編碼技術(shù)熵編碼概述2熵編碼概述熵編碼是針對(duì)統(tǒng)計(jì)冗余的壓縮編碼方法熵編碼的理論基礎(chǔ)是shannon的信息熵理論，所以被叫做熵編碼熵編碼是無(wú)損編碼熵編碼是壓縮編碼中最重要的一種編碼方法，是各種編解碼方案中都要采用的編碼方法熵編碼概述熵編碼是針對(duì)統(tǒng)計(jì)冗余的壓縮編碼方法3信息熵理論假設(shè)無(wú)記憶信息源

M={mi},mi∈S,i=0..N-1符號(hào)表

S={sk}，k=0..K-1符號(hào)sk出現(xiàn)的概率為pk，k=0..K-1符號(hào)sk的信息量為h(sk)=-log2(pk)信息熵理論假設(shè)無(wú)記憶信息源4信息熵理論符號(hào)出現(xiàn)的概率越小，所包含的信息量越大。經(jīng)過(guò)理論分析和實(shí)踐檢驗(yàn)，證明概率的倒數(shù)的對(duì)數(shù)是最符合概率和信息量之間關(guān)系的（2.26，9.58）信息源的信息量是構(gòu)成它的所有符號(hào)的信息量的和，即?(M)=h(m0)+…+h(mN-1)信息熵理論符號(hào)出現(xiàn)的概率越小，所包含的信息量越大。經(jīng)過(guò)理論分5信息熵理論信息源的熵是構(gòu)成它的所有符號(hào)的平均信息量H(M)=(h(m0)+…+h(mN-1))/N=Σ(-pklog(pk))當(dāng)所有符號(hào)出現(xiàn)的概率相同時(shí)，信息源的熵最大當(dāng)對(duì)數(shù)以2為底時(shí)，?(M)是編碼信息源所需的最小位數(shù)，而H(M)是每個(gè)符號(hào)的平均位數(shù)信息熵理論信息源的熵是構(gòu)成它的所有符號(hào)的平均信息量6信息熵理論M={AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE}信息熵理論M={7huffman編碼Shannon-Fano算法根據(jù)出現(xiàn)概率從大到小將符號(hào)排成一列將符號(hào)列分成上下兩部分，使兩部分的概率之和盡量接近上半部分標(biāo)0，下半部分標(biāo)1對(duì)所分的兩部分重復(fù)上述步驟，直到所有分組都只包含一個(gè)符號(hào)huffman編碼Shannon-Fano算法8huffman編碼huffman算法尋找概率最小的兩個(gè)符號(hào)將概率最小的兩個(gè)符號(hào)連接成一個(gè)新符號(hào)，新符號(hào)的概率為原來(lái)的兩個(gè)符號(hào)的概率之和用新符號(hào)替換原來(lái)的兩個(gè)符號(hào)重復(fù)上述步驟，直到符號(hào)集中只剩下一個(gè)符號(hào)huffman編碼huffman算法9哈夫曼編碼過(guò)程演示A1A2A3A4A5A6A70.230.210.180.150.130.070.03100.10100.23100.33100.44

1

00.56011編碼010011111010110011000哈夫曼編碼過(guò)程演示A10.23100.10100.2310huffman編碼ASCII碼(定長(zhǎng)碼)39x8=312Shannon-Fano算法15x2+7x2+6x2+6x3+5x3=89huffmann算法15x1+7x3+6x3+6x3+5x3=87理論最小值85.25huffman編碼ASCII碼(定長(zhǎng)碼)11指數(shù)哥倫布碼Exponential-Golombcode=Exp-GolombcodeHuffmann碼的局限只適用于有限符號(hào)集需要傳送或保存碼表指數(shù)哥倫布碼的優(yōu)點(diǎn)可以對(duì)無(wú)限符號(hào)集編碼不需要傳送或保存碼表指數(shù)哥倫布碼Exponential-Golombcode12指數(shù)哥倫布碼階數(shù)碼字結(jié)構(gòu)CodeNum取值范圍k=01001x01～2001x1x03～60001x2x1x07～14............k=11x00～101x1x02～5001x2x1x06～130001x3x2x1x014～29............k=21x1x00～301x2x1x04～11001x3x2x1x012～270001x4x3x2x1x028～59............指數(shù)哥倫布碼階數(shù)碼字結(jié)構(gòu)CodeNum取值范圍k=01013指數(shù)哥倫布碼指數(shù)哥倫布碼的局限通常不是最優(yōu)的，只有概率分布合適的時(shí)候是0階指數(shù)哥倫布碼總共用了109位1階指數(shù)哥倫布碼總共用了112位需要根據(jù)符號(hào)的概率分布選擇合適的階數(shù)指數(shù)哥倫布碼指數(shù)哥倫布碼的局限14算數(shù)編碼的由來(lái)Huffman碼和指數(shù)哥倫布碼的碼字必須是整數(shù)個(gè)bit，這就造成了大多數(shù)情況下huffman碼無(wú)法達(dá)到理論極限，甚至距離理論極限很遠(yuǎn)。例如，如果一個(gè)符號(hào)的概率是1/3，則該符號(hào)的編碼位數(shù)最優(yōu)是1.6左右，而huffman碼卻只能為其設(shè)計(jì)1位或2位的碼字。當(dāng)一個(gè)符號(hào)的概率特別高時(shí)，例如大于0.9，則最優(yōu)碼長(zhǎng)是0.15位，而huffman碼只能是1位，比最優(yōu)碼長(zhǎng)長(zhǎng)6倍當(dāng)符號(hào)集中只有兩個(gè)符號(hào)時(shí)（例如二值圖像），huffman碼幾乎失去作用。解決這個(gè)問(wèn)題的方法是將若干個(gè)相連的符號(hào)打包，從而產(chǎn)生一個(gè)較大的符號(hào)集，然后再應(yīng)用huffman編碼。算數(shù)編碼的由來(lái)Huffman碼和指數(shù)哥倫布碼的碼字必須是整數(shù)15算數(shù)編碼的基本思想一個(gè)由服從已知概率分布的符號(hào)集中的符號(hào)組成的符號(hào)串（假設(shè)長(zhǎng)度為N）實(shí)際上是一個(gè)事件，這個(gè)事件發(fā)生的概率可以計(jì)算出來(lái)。假設(shè)所有長(zhǎng)度為N的事件共有K個(gè)，它們的概率之和為1。把這些事件按照某種規(guī)則排成一列，在[0，1）上為每個(gè)事件分配一個(gè)區(qū)間[Lk,Hk），區(qū)間長(zhǎng)度等于第k個(gè)事件的概率，那么得到一個(gè)[0，1）的分割用一個(gè)落入某區(qū)間的值，就可以指示該區(qū)間對(duì)應(yīng)的事件發(fā)生了，這就是算術(shù)編碼的基本思想算數(shù)編碼的基本思想一個(gè)由服從已知概率分布的符號(hào)集中的符號(hào)組成16算數(shù)編碼的編碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..KI(m)是符號(hào)m在符號(hào)集中的索引Low=0;High=1;range=High–Low;for(n=0;n<N;n++)//有N個(gè)符號(hào)需要編碼{High=Low+C[I(mn)+1]*range;Low=Low+C[I(mn)]*range;range=High–Low;}尋找一個(gè)值v，使得Low<=v且v+d<=High且用二進(jìn)制表示時(shí)v的有效位數(shù)最少。其中d是v的最低有效位表示的值。例如v為8位時(shí)d就是1/256算數(shù)編碼的編碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-117算數(shù)編碼的解碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..K{b0,b1,…}是待解碼bit串D[i]=C[i];//動(dòng)態(tài)區(qū)間For(n=0;n<N;n++)//已知有N個(gè)符號(hào)需要解碼{

讀入碼流，直到[v,v+d)落入某個(gè)區(qū)間[D[k],D[k+1])

解碼得到符號(hào)集中索引為k的符號(hào)

range=D[k+1]–D[k];D[0]=D[k];D[i]=D[0]+C[i]*range;}其中d是v的最低有效位表示的值。算數(shù)編碼的解碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-118算數(shù)編碼的終止碼流的終止因?yàn)樗阈g(shù)編碼器輸出的比特串是作為一個(gè)很長(zhǎng)的碼流的一部分，為了不受后續(xù)bit的影響，必須要求low<=vandv+d<=high解碼過(guò)程的終止已知要解碼的符號(hào)的個(gè)數(shù)在符號(hào)集中增加結(jié)束符號(hào)EOB算數(shù)編碼的終止碼流的終止19算數(shù)編碼的區(qū)間放大浮點(diǎn)數(shù)的精度是有限的，當(dāng)待編碼的符號(hào)串很長(zhǎng)時(shí)，會(huì)出現(xiàn)range過(guò)小的情況解決的方法是每編碼一個(gè)符號(hào)都對(duì)區(qū)間進(jìn)行放大解碼過(guò)程也進(jìn)行同樣的放大，以保證編解碼所得的區(qū)間一致算數(shù)編碼的區(qū)間放大浮點(diǎn)數(shù)的精度是有限的，當(dāng)待編碼的符號(hào)串很長(zhǎng)20算數(shù)編碼的整數(shù)實(shí)現(xiàn)浮點(diǎn)數(shù)運(yùn)算復(fù)雜，為了降低復(fù)雜度，發(fā)明了用定點(diǎn)運(yùn)算實(shí)現(xiàn)的算術(shù)編碼器和解碼器定點(diǎn)的算術(shù)編碼器和解碼器一定包含區(qū)間放大算數(shù)編碼的整數(shù)實(shí)現(xiàn)浮點(diǎn)數(shù)運(yùn)算復(fù)雜，為了降低復(fù)雜度，發(fā)明了用定21算數(shù)編碼舉例符號(hào)集{A,B,C}，概率{0.8,0.1,0.1}，分割{0,0.8,0.9,1}符號(hào)串AAAAAAAABC符號(hào)十進(jìn)制low十進(jìn)制high二進(jìn)制low二進(jìn)制high輸出bitA00.8011100A00.64010111A00.512010010A00.4096011011A00.32768000010A00.262144011011A00.2097152001111A00.16777216010011B0.1342177280.1509949941110000111C015099499411001001110010011001算數(shù)編碼舉例符號(hào)集{A,B,C}，概率{0.8,0.122基于上下文的熵編碼考慮了符號(hào)的條件概率，即根據(jù)已經(jīng)出現(xiàn)的符號(hào)調(diào)整下一個(gè)符號(hào)出現(xiàn)的概率基于上下文的熵編碼可以有效的提高編碼效率，具體提高多少和符號(hào)的相關(guān)性有關(guān)基于上下文的熵編碼可以和huffman、指數(shù)哥倫布、算術(shù)編碼等結(jié)合使用基于上下文的熵編碼考慮了符號(hào)的條件概率，即根據(jù)已經(jīng)出現(xiàn)的符號(hào)23自適應(yīng)熵編碼在事先不知道符號(hào)的概率分布的情況下，或者不愿意使用固定的碼表和概率表的時(shí)候，可以使用自適應(yīng)熵編碼技術(shù)自適應(yīng)熵編碼就是一邊編碼一邊統(tǒng)計(jì)，根據(jù)統(tǒng)計(jì)結(jié)果動(dòng)態(tài)生成概率表和變長(zhǎng)碼表自適應(yīng)熵編碼可以和huffmann、指數(shù)哥倫布、算術(shù)編碼等結(jié)合自適應(yīng)熵編碼和基于上下文的熵編碼不同自適應(yīng)熵編碼在事先不知道符號(hào)的概率分布的情況下，或者不愿意使24其他無(wú)損編碼方法游程編碼(run-lengthcoding)字典壓縮靜態(tài)方法與自適應(yīng)方法Jacobziv;AbrahamLempel;TerryWelchLZ77LZ78LZWZIPARJRARMMR一種二值圖像壓縮方法用于傳真機(jī)其他無(wú)損編碼方法游程編碼(run-lengthcodin25學(xué)習(xí)并沒(méi)有結(jié)束，希望繼續(xù)努力Thanksforlistening,thiscourseisexpectedtobringyouvalueandhelp為方便學(xué)習(xí)與使用課件內(nèi)容，課件可以在下載后自由編輯學(xué)習(xí)并沒(méi)有結(jié)束，希望繼續(xù)努力26多媒體編碼與通信111111多媒體編碼與通信27第二章熵編碼技術(shù)熵編碼概述信息熵理論Huffman編碼指數(shù)哥倫布編碼算術(shù)編碼基于上下文的熵編碼自適應(yīng)熵編碼其他無(wú)損編碼方法第二章熵編碼技術(shù)熵編碼概述28熵編碼概述熵編碼是針對(duì)統(tǒng)計(jì)冗余的壓縮編碼方法熵編碼的理論基礎(chǔ)是shannon的信息熵理論，所以被叫做熵編碼熵編碼是無(wú)損編碼熵編碼是壓縮編碼中最重要的一種編碼方法，是各種編解碼方案中都要采用的編碼方法熵編碼概述熵編碼是針對(duì)統(tǒng)計(jì)冗余的壓縮編碼方法29信息熵理論假設(shè)無(wú)記憶信息源

M={mi},mi∈S,i=0..N-1符號(hào)表

S={sk}，k=0..K-1符號(hào)sk出現(xiàn)的概率為pk，k=0..K-1符號(hào)sk的信息量為h(sk)=-log2(pk)信息熵理論假設(shè)無(wú)記憶信息源30信息熵理論符號(hào)出現(xiàn)的概率越小，所包含的信息量越大。經(jīng)過(guò)理論分析和實(shí)踐檢驗(yàn)，證明概率的倒數(shù)的對(duì)數(shù)是最符合概率和信息量之間關(guān)系的（2.26，9.58）信息源的信息量是構(gòu)成它的所有符號(hào)的信息量的和，即?(M)=h(m0)+…+h(mN-1)信息熵理論符號(hào)出現(xiàn)的概率越小，所包含的信息量越大。經(jīng)過(guò)理論分31信息熵理論信息源的熵是構(gòu)成它的所有符號(hào)的平均信息量H(M)=(h(m0)+…+h(mN-1))/N=Σ(-pklog(pk))當(dāng)所有符號(hào)出現(xiàn)的概率相同時(shí)，信息源的熵最大當(dāng)對(duì)數(shù)以2為底時(shí)，?(M)是編碼信息源所需的最小位數(shù)，而H(M)是每個(gè)符號(hào)的平均位數(shù)信息熵理論信息源的熵是構(gòu)成它的所有符號(hào)的平均信息量32信息熵理論M={AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE}信息熵理論M={33huffman編碼Shannon-Fano算法根據(jù)出現(xiàn)概率從大到小將符號(hào)排成一列將符號(hào)列分成上下兩部分，使兩部分的概率之和盡量接近上半部分標(biāo)0，下半部分標(biāo)1對(duì)所分的兩部分重復(fù)上述步驟，直到所有分組都只包含一個(gè)符號(hào)huffman編碼Shannon-Fano算法34huffman編碼huffman算法尋找概率最小的兩個(gè)符號(hào)將概率最小的兩個(gè)符號(hào)連接成一個(gè)新符號(hào)，新符號(hào)的概率為原來(lái)的兩個(gè)符號(hào)的概率之和用新符號(hào)替換原來(lái)的兩個(gè)符號(hào)重復(fù)上述步驟，直到符號(hào)集中只剩下一個(gè)符號(hào)huffman編碼huffman算法35哈夫曼編碼過(guò)程演示A1A2A3A4A5A6A70.230.210.180.150.130.070.03100.10100.23100.33100.44

1

00.56011編碼010011111010110011000哈夫曼編碼過(guò)程演示A10.23100.10100.2336huffman編碼ASCII碼(定長(zhǎng)碼)39x8=312Shannon-Fano算法15x2+7x2+6x2+6x3+5x3=89huffmann算法15x1+7x3+6x3+6x3+5x3=87理論最小值85.25huffman編碼ASCII碼(定長(zhǎng)碼)37指數(shù)哥倫布碼Exponential-Golombcode=Exp-GolombcodeHuffmann碼的局限只適用于有限符號(hào)集需要傳送或保存碼表指數(shù)哥倫布碼的優(yōu)點(diǎn)可以對(duì)無(wú)限符號(hào)集編碼不需要傳送或保存碼表指數(shù)哥倫布碼Exponential-Golombcode38指數(shù)哥倫布碼階數(shù)碼字結(jié)構(gòu)CodeNum取值范圍k=01001x01～2001x1x03～60001x2x1x07～14............k=11x00～101x1x02～5001x2x1x06～130001x3x2x1x014～29............k=21x1x00～301x2x1x04～11001x3x2x1x012～270001x4x3x2x1x028～59............指數(shù)哥倫布碼階數(shù)碼字結(jié)構(gòu)CodeNum取值范圍k=01039指數(shù)哥倫布碼指數(shù)哥倫布碼的局限通常不是最優(yōu)的，只有概率分布合適的時(shí)候是0階指數(shù)哥倫布碼總共用了109位1階指數(shù)哥倫布碼總共用了112位需要根據(jù)符號(hào)的概率分布選擇合適的階數(shù)指數(shù)哥倫布碼指數(shù)哥倫布碼的局限40算數(shù)編碼的由來(lái)Huffman碼和指數(shù)哥倫布碼的碼字必須是整數(shù)個(gè)bit，這就造成了大多數(shù)情況下huffman碼無(wú)法達(dá)到理論極限，甚至距離理論極限很遠(yuǎn)。例如，如果一個(gè)符號(hào)的概率是1/3，則該符號(hào)的編碼位數(shù)最優(yōu)是1.6左右，而huffman碼卻只能為其設(shè)計(jì)1位或2位的碼字。當(dāng)一個(gè)符號(hào)的概率特別高時(shí)，例如大于0.9，則最優(yōu)碼長(zhǎng)是0.15位，而huffman碼只能是1位，比最優(yōu)碼長(zhǎng)長(zhǎng)6倍當(dāng)符號(hào)集中只有兩個(gè)符號(hào)時(shí)（例如二值圖像），huffman碼幾乎失去作用。解決這個(gè)問(wèn)題的方法是將若干個(gè)相連的符號(hào)打包，從而產(chǎn)生一個(gè)較大的符號(hào)集，然后再應(yīng)用huffman編碼。算數(shù)編碼的由來(lái)Huffman碼和指數(shù)哥倫布碼的碼字必須是整數(shù)41算數(shù)編碼的基本思想一個(gè)由服從已知概率分布的符號(hào)集中的符號(hào)組成的符號(hào)串（假設(shè)長(zhǎng)度為N）實(shí)際上是一個(gè)事件，這個(gè)事件發(fā)生的概率可以計(jì)算出來(lái)。假設(shè)所有長(zhǎng)度為N的事件共有K個(gè)，它們的概率之和為1。把這些事件按照某種規(guī)則排成一列，在[0，1）上為每個(gè)事件分配一個(gè)區(qū)間[Lk,Hk），區(qū)間長(zhǎng)度等于第k個(gè)事件的概率，那么得到一個(gè)[0，1）的分割用一個(gè)落入某區(qū)間的值，就可以指示該區(qū)間對(duì)應(yīng)的事件發(fā)生了，這就是算術(shù)編碼的基本思想算數(shù)編碼的基本思想一個(gè)由服從已知概率分布的符號(hào)集中的符號(hào)組成42算數(shù)編碼的編碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..KI(m)是符號(hào)m在符號(hào)集中的索引Low=0;High=1;range=High–Low;for(n=0;n<N;n++)//有N個(gè)符號(hào)需要編碼{High=Low+C[I(mn)+1]*range;Low=Low+C[I(mn)]*range;range=High–Low;}尋找一個(gè)值v，使得Low<=v且v+d<=High且用二進(jìn)制表示時(shí)v的有效位數(shù)最少。其中d是v的最低有效位表示的值。例如v為8位時(shí)d就是1/256算數(shù)編碼的編碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-143算數(shù)編碼的解碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..K{b0,b1,…}是待解碼bit串D[i]=C[i];//動(dòng)態(tài)區(qū)間For(n=0;n<N;n++)//已知有N個(gè)符號(hào)需要解碼{

讀入碼流，直到[v,v+d)落入某個(gè)區(qū)間[D[k],D[k+1])

解碼得到符號(hào)集中索引為k的符號(hào)

range=D[k+1]–D[k];D[0]=D[k];D[i]=D[0]+C[i]*range;}其中d是v的最低有效位表示的值。算數(shù)編碼的解碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-144算數(shù)編碼的終止碼流的終止因?yàn)樗阈g(shù)編碼器輸出的比特串是作為一個(gè)很長(zhǎng)的碼流的一部分，為了不受后續(xù)bit的影響，必須要求low<=vandv+d<=high解碼過(guò)程的終止已知要解碼的符號(hào)的個(gè)數(shù)在符號(hào)集中增加結(jié)束符號(hào)EOB算數(shù)編碼的終止碼流的終止45算數(shù)編碼的區(qū)間放大浮點(diǎn)數(shù)的精度是有限的，當(dāng)待編碼的符號(hào)串很長(zhǎng)時(shí)，會(huì)出現(xiàn)range過(guò)小的情況解決的方法是每編碼一個(gè)符號(hào)都對(duì)區(qū)間進(jìn)行放大解碼過(guò)程也進(jìn)行同樣的放大，以保證編解碼所得的區(qū)間一致算數(shù)編碼的區(qū)間放大浮點(diǎn)數(shù)的精度是有限的，當(dāng)待編碼的符號(hào)串很長(zhǎng)46算數(shù)編碼的整數(shù)實(shí)現(xiàn)浮點(diǎn)數(shù)運(yùn)算復(fù)雜，為了降低復(fù)雜度，發(fā)明了用定點(diǎn)運(yùn)算實(shí)現(xiàn)的算術(shù)編碼器和解碼器定點(diǎn)的算術(shù)編碼器和解碼器一定包含區(qū)間放大算數(shù)編碼的整數(shù)實(shí)現(xiàn)浮點(diǎn)數(shù)運(yùn)算復(fù)雜，為了降低復(fù)雜度，發(fā)明了用定47算數(shù)編碼舉例符號(hào)集{A,B,C}，概率{0.8,0.1,0.1}