圖像與數(shù)字圖像通信chapter-3

1、3.1 圖像壓縮編碼的分類圖像壓縮編碼的分類3.2 數(shù)據(jù)壓縮與信息論基礎(chǔ)數(shù)據(jù)壓縮與信息論基礎(chǔ)3.3 霍夫曼編碼霍夫曼編碼3.4 游程長度編碼游程長度編碼3.5 算術(shù)編碼算術(shù)編碼數(shù)字圖象通常要求很大的比特?cái)?shù)，這給圖象的數(shù)字圖象通常要求很大的比特?cái)?shù)，這給圖象的傳輸和存儲(chǔ)帶來相當(dāng)大的困難。要占用很多的傳輸和存儲(chǔ)帶來相當(dāng)大的困難。要占用很多的資源，花很高的費(fèi)用。資源，花很高的費(fèi)用。 如一幅如一幅512x512的黑白圖象的比特?cái)?shù)為的黑白圖象的比特?cái)?shù)為 512x512x8=。 再如一部再如一部90分鐘的彩色電影，每秒放映分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀幀。把它數(shù)字化，每幀512x512象素

2、，象素，每象素的每象素的 、 三分量分別占三分量分別占8 bit，總比，總比特?cái)?shù)為特?cái)?shù)為 90 x60 x24x3x512x512x8bit=。 如一張如一張CD光盤可存光盤可存600兆字節(jié)數(shù)據(jù)，這部兆字節(jié)數(shù)據(jù)，這部電影光圖象（還有聲音）就需要電影光圖象（還有聲音）就需要張張CD光光盤用來存儲(chǔ)。盤用來存儲(chǔ)。 對(duì)圖象數(shù)據(jù)進(jìn)行對(duì)圖象數(shù)據(jù)進(jìn)行壓縮顯得非常必要壓縮顯得非常必要。 本章討論的問題：在滿足一定條件下，能否本章討論的問題：在滿足一定條件下，能否減小圖象減小圖象bitbit數(shù)，以及用什么樣的編碼方法使之?dāng)?shù)，以及用什么樣的編碼方法使之減少。減少。圖像壓縮編碼限失真編碼無失真編碼行程編碼LZW編碼

3、哈夫曼編碼算術(shù)編碼無損預(yù)測編碼位平面編碼有損預(yù)測編碼分形編碼模型編碼子帶編碼神經(jīng)網(wǎng)絡(luò)編碼變換編碼K.L變換Haar變換Walsh.Hadamard變換離散余弦變換離散傅立葉變換斜變換小波變換1. 1.圖象壓縮是可能的圖象壓縮是可能的：n一般原始圖象中存在很大的冗余度。一般原始圖象中存在很大的冗余度。n用戶通常允許圖象失真。用戶通常允許圖象失真。n當(dāng)信道的分辨率不及原始圖象的分辨率當(dāng)信道的分辨率不及原始圖象的分辨率時(shí)，降低輸入的原始圖象的分辨率對(duì)輸出時(shí)，降低輸入的原始圖象的分辨率對(duì)輸出圖象分辨率影響不大。圖象分辨率影響不大。n用戶對(duì)原始圖象的信號(hào)不全都感興趣，用戶對(duì)原始圖象的信號(hào)不全都感興趣，可

4、用特征提取和圖象識(shí)別的方法，丟掉大可用特征提取和圖象識(shí)別的方法，丟掉大量無用的信息。提取有用的信息，使必須量無用的信息。提取有用的信息，使必須傳輸和存儲(chǔ)的圖象數(shù)據(jù)大大減少。傳輸和存儲(chǔ)的圖象數(shù)據(jù)大大減少。 n原始圖象越有規(guī)則，各象素之間的相關(guān)性越原始圖象越有規(guī)則，各象素之間的相關(guān)性越強(qiáng)，它可能壓縮的數(shù)據(jù)就越多。強(qiáng)，它可能壓縮的數(shù)據(jù)就越多。 值得指出的是：當(dāng)前采用的編碼方法得到值得指出的是：當(dāng)前采用的編碼方法得到的結(jié)果，離可能壓縮的極限還相差很遠(yuǎn)，這的結(jié)果，離可能壓縮的極限還相差很遠(yuǎn)，這說明圖象數(shù)據(jù)壓縮的潛力是很大的，直到目說明圖象數(shù)據(jù)壓縮的潛力是很大的，直到目前為止，它還是個(gè)正在繼續(xù)研究的領(lǐng)域。

5、前為止，它還是個(gè)正在繼續(xù)研究的領(lǐng)域。33K15K 圖象數(shù)據(jù)壓縮的圖象數(shù)據(jù)壓縮的目的目的是在滿足一定圖象質(zhì)量是在滿足一定圖象質(zhì)量條件下，用盡可能少的比特?cái)?shù)來表示原始圖條件下，用盡可能少的比特?cái)?shù)來表示原始圖象，以提高圖象傳輸?shù)男屎蜏p少圖象存儲(chǔ)象，以提高圖象傳輸?shù)男屎蜏p少圖象存儲(chǔ)的容量，在信息論中稱為的容量，在信息論中稱為信源編碼信源編碼。 信源編碼可分為兩大類，一類是信源編碼可分為兩大類，一類是無失真編無失真編碼碼，另一類是，另一類是有失真編碼有失真編碼或稱或稱限失真編碼限失真編碼。從從N個(gè)數(shù)選定一個(gè)數(shù)個(gè)數(shù)選定一個(gè)數(shù)s的概率為的概率為p(s)，且等概率，且等概率，p(s)=1/N。設(shè)信源符號(hào)表

6、為設(shè)信源符號(hào)表為 s=s1, s2, , sq ，其概率分布為其概率分布為P(s)=p(s1), p(s2), , p(sq) ，則信源的，則信源的為為)()(log1loglog)(222spIspNNsIqiiiqiiispIspspspH112)()()(log)()(ss作為灰度，共作為灰度，共q級(jí)級(jí)，出現(xiàn)概率均等時(shí)，出現(xiàn)概率均等時(shí)，p(si)=1/q， 當(dāng)灰度只有兩級(jí)時(shí)，即當(dāng)灰度只有兩級(jí)時(shí)，即si = = 0, 1，且，且0出現(xiàn)出現(xiàn)概率為概率為p1，1出現(xiàn)概率為出現(xiàn)概率為p2=1- p1 ，其熵，其熵qqqHqi212log1log1)(s12112111log)1 (1log)(p

7、pppHs當(dāng)當(dāng)p1=1/2， p2=1- p1 =1/2時(shí)，時(shí)， H(s)=1為最大值。如圖所示。為最大值。如圖所示。（1 1）熵是一個(gè)非負(fù)數(shù)，即總有）熵是一個(gè)非負(fù)數(shù)，即總有H(s)0。（2 2）當(dāng)其中一個(gè)符號(hào)）當(dāng)其中一個(gè)符號(hào)sj的出現(xiàn)概率的出現(xiàn)概率p(sj)=1時(shí)，時(shí)，其余符號(hào)其余符號(hào)si(ij)的出現(xiàn)概率的出現(xiàn)概率p(si) =0，H(s)=0。（3 3）當(dāng)各個(gè)）當(dāng)各個(gè)si出現(xiàn)的概率相同出現(xiàn)的概率相同時(shí)時(shí)，則最大平，則最大平均信息量為均信息量為log2 q。（4 4）熵值總有）熵值總有H(s) log2 q。無失真編碼定理無失真編碼定理 可以證明，在無干擾的條件下，存在一種無可以證明，在無

8、干擾的條件下，存在一種無失真的編碼方法，使編碼的平均長度失真的編碼方法，使編碼的平均長度 與與信源信源的熵的熵H(s)任意地接近，即任意地接近，即L=H(s)+，其中，其中為任意小的正數(shù)，但以為任意小的正數(shù)，但以H(s)為其下限，即為其下限，即LH(s)，這就是，這就是香農(nóng)香農(nóng)(Shannon)無干擾編無干擾編碼定理碼定理。L)(sHL)(sHL 熵與相關(guān)性、冗余度的關(guān)系熵與相關(guān)性、冗余度的關(guān)系 對(duì)于無失真圖象的編碼，原始圖象數(shù)據(jù)的壓對(duì)于無失真圖象的編碼，原始圖象數(shù)據(jù)的壓縮存在一個(gè)下限，即平均碼組長度不能小于原縮存在一個(gè)下限，即平均碼組長度不能小于原始圖象的熵，而理論上的最佳編碼的平均碼長始圖

9、象的熵，而理論上的最佳編碼的平均碼長無限接近原始圖象的熵。無限接近原始圖象的熵。 原始圖象原始圖象定義為：定義為：1)(1sHLr原始圖象的熵原始圖象平均碼長將將定義為：定義為：rLsH11)( 冗余度接近于冗余度接近于0，或編碼效率接近于，或編碼效率接近于1的編的編碼稱為碼稱為。 數(shù)字圖像通信系統(tǒng)的組成數(shù)字圖像通信系統(tǒng)的組成：其中，其中，信源編碼器：完成原數(shù)據(jù)的壓縮。信源編碼器：完成原數(shù)據(jù)的壓縮。信道信道 編編 碼：為了抗干擾，增加一些容錯(cuò)、校驗(yàn)碼：為了抗干擾，增加一些容錯(cuò)、校驗(yàn)位、版權(quán)保護(hù)，實(shí)際上是增加冗余。位、版權(quán)保護(hù)，實(shí)際上是增加冗余。信信 道：如道：如Internet、廣播、通訊、可

10、移動(dòng)介質(zhì)、廣播、通訊、可移動(dòng)介質(zhì)符號(hào)符號(hào)解碼器解碼器反向反向映射器映射器映射器映射器量化器量化器符號(hào)符號(hào)編碼器編碼器等字長編碼等字長編碼 每個(gè)抽樣值都以相同長度的二進(jìn)制碼表示。每個(gè)抽樣值都以相同長度的二進(jìn)制碼表示。 編碼簡單，但編碼效率低編碼簡單，但編碼效率低 PCM變字長編碼變字長編碼n每個(gè)抽樣值用不同長度的二進(jìn)制碼表示。每個(gè)抽樣值用不同長度的二進(jìn)制碼表示。n每個(gè)符號(hào)的平均碼長：每個(gè)符號(hào)的平均碼長：設(shè)圖像信源有設(shè)圖像信源有K種符號(hào)（例如種符號(hào)（例如K種灰度等種灰度等級(jí)），級(jí)）， ,且它們出現(xiàn)的概率為且它們出現(xiàn)的概率為 ,那么，不考那么，不考慮信源符號(hào)的相關(guān)性，對(duì)每個(gè)符號(hào)編碼時(shí)，慮信源符號(hào)的相

11、關(guān)性，對(duì)每個(gè)符號(hào)編碼時(shí)，其平均碼長為：其平均碼長為：其中其中l(wèi)i為為ai的碼字長度，的碼字長度，L為平均碼長為平均碼長若編碼時(shí)，對(duì)概率大的符號(hào)用短碼，概率小若編碼時(shí)，對(duì)概率大的符號(hào)用短碼，概率小的符號(hào)用長碼，則的符號(hào)用長碼，則L L會(huì)比等長編碼所需的碼會(huì)比等長編碼所需的碼字短。字短。 較等長編碼效率高。較等長編碼效率高。i1(a )kiiLpl構(gòu)成不等長編碼的方法有許多，構(gòu)成不等長編碼的方法有許多，Huffman于于1952年提出一種最佳不等長編碼，是圖像編年提出一種最佳不等長編碼，是圖像編碼中常用的無損壓縮編碼。碼中常用的無損壓縮編碼。 1、定理、定理 如果碼字長度嚴(yán)格按照符號(hào)出現(xiàn)概率大小如

12、果碼字長度嚴(yán)格按照符號(hào)出現(xiàn)概率大小逆序排列，則平均碼字長度最小。逆序排列，則平均碼字長度最小。概率大概率大的用短碼，概率小的用長碼。的用短碼，概率小的用長碼。2、編碼方法、編碼方法 （1）對(duì)信源符號(hào)按其出現(xiàn)的概率進(jìn)行遞減排）對(duì)信源符號(hào)按其出現(xiàn)的概率進(jìn)行遞減排序。序。 （2）將兩個(gè)最小的概率相加，其和作為新符）將兩個(gè)最小的概率相加，其和作為新符號(hào)的概率，并按（號(hào)的概率，并按（1）重新排序。）重新排序。 （3）重復(fù)（）重復(fù)（1）（）（2），直到概率之和達(dá)到），直到概率之和達(dá)到1為止。為止。 （4）每次合并符號(hào)時(shí)，將被合并的符號(hào)賦予）每次合并符號(hào)時(shí)，將被合并的符號(hào)賦予1和和0或或0和和1。 （5）尋

13、找從概率）尋找從概率1處到每個(gè)信源符號(hào)的路徑，處到每個(gè)信源符號(hào)的路徑，記錄下路徑上的記錄下路徑上的0，1序列，該序列即為信源符序列，該序列即為信源符號(hào)的碼字（編碼）。號(hào)的碼字（編碼）。 舉例：舉例：信號(hào)源信號(hào)源 s=ss=s1 1, s, s2 2, s, s3 3, s, s4 4, s, s5 5, s, s6 6 ，其概率，其概率分布為分布為p p1 1=0.4 p=0.4 p2 2=0.3 p=0.3 p3 3=0.1 p=0.1 p4 4=0.1 =0.1 p p5 5=0.06 p=0.06 p6 6=0.04=0.04，求最佳，求最佳HuffmanHuffman碼。碼。i. i.

14、 將信源符號(hào)按出現(xiàn)概率從大到小排成一列將信源符號(hào)按出現(xiàn)概率從大到小排成一列，然后把最末兩個(gè)符號(hào)的概率相加，合成，然后把最末兩個(gè)符號(hào)的概率相加，合成一個(gè)概率。一個(gè)概率。ii. ii. 把這個(gè)符號(hào)的概率與其余符號(hào)的概率按從把這個(gè)符號(hào)的概率與其余符號(hào)的概率按從大到小排列，然后再把最末兩個(gè)符號(hào)的概大到小排列，然后再把最末兩個(gè)符號(hào)的概率加起來，合成一個(gè)概率。率加起來，合成一個(gè)概率。 ii. ii. 重復(fù)上述做法，直到最后剩下兩個(gè)概率為重復(fù)上述做法，直到最后剩下兩個(gè)概率為止。止。iii.iii.從最后一步剩下的兩個(gè)概率開始逐步向前從最后一步剩下的兩個(gè)概率開始逐步向前進(jìn)行編碼。每步只需對(duì)兩個(gè)分支各賦予一進(jìn)行

15、編碼。每步只需對(duì)兩個(gè)分支各賦予一個(gè)二進(jìn)制碼，如對(duì)概率大的賦予碼元個(gè)二進(jìn)制碼，如對(duì)概率大的賦予碼元0，對(duì)概率小的賦予碼元對(duì)概率小的賦予碼元1。輸入輸入S1S2S3S4S5S6輸入概率輸入概率0.40.30.10.10.060.04第一步第一步0.40.30.10.10.1第二步第二步0.40.30.20.1第三步第三步0.40.30.3第四步第四步0.60.40101010101S1=1S2=00S3=011S4=0100S5=01010S6=01011壓縮前，等長編碼：每個(gè)符號(hào)壓縮前，等長編碼：每個(gè)符號(hào)3bit壓縮后，壓縮后， =1*0.4+2*0.3+3*0.1+4*0.1+5*0.06+5

16、*0.04=2.2bit壓縮比：壓縮比：3/2.21.36靜態(tài)編碼靜態(tài)編碼：在壓縮之前就建立好一個(gè)概率統(tǒng)計(jì)：在壓縮之前就建立好一個(gè)概率統(tǒng)計(jì)表和編碼樹。算法速度快，但壓縮效果不是最表和編碼樹。算法速度快，但壓縮效果不是最好；好；動(dòng)態(tài)編碼動(dòng)態(tài)編碼：對(duì)每一個(gè)圖像，臨時(shí)建立概率統(tǒng)計(jì)：對(duì)每一個(gè)圖像，臨時(shí)建立概率統(tǒng)計(jì)表和編碼樹。算法速度慢，但壓縮效果最好。表和編碼樹。算法速度慢，但壓縮效果最好。霍夫曼解碼霍夫曼解碼設(shè)接收端收到的碼流是設(shè)接收端收到的碼流是101001000，如何，如何判斷應(yīng)判斷應(yīng)“斷斷”在何處，即哪幾個(gè)比特應(yīng)對(duì)應(yīng)在何處，即哪幾個(gè)比特應(yīng)對(duì)應(yīng)一個(gè)碼字？也就是說如何解碼？下面介紹兩一個(gè)碼字？也就

17、是說如何解碼？下面介紹兩種方法。種方法。1）樹形解碼。樹形解碼。解碼器先進(jìn)高位，并根據(jù)該位是解碼器先進(jìn)高位，并根據(jù)該位是1還是還是0判斷判斷由根向下走向，若走到樹葉，說明至此為止由根向下走向，若走到樹葉，說明至此為止的碼串部分對(duì)應(yīng)一個(gè)碼字，從而解出對(duì)應(yīng)的的碼串部分對(duì)應(yīng)一個(gè)碼字，從而解出對(duì)應(yīng)的符號(hào)；符號(hào)；重新從樹根開始解碼，若未走到樹葉，則繼重新從樹根開始解碼，若未走到樹葉，則繼續(xù)進(jìn)一位，至到走到樹葉。續(xù)進(jìn)一位，至到走到樹葉。 2）并行解碼。）并行解碼。 用樹形解碼時(shí)需一位一位讀入和判斷，當(dāng)碼用樹形解碼時(shí)需一位一位讀入和判斷，當(dāng)碼表較長時(shí)，速度太慢。特別是對(duì)活動(dòng)圖像解表較長時(shí)，速度太慢。特別是對(duì)

18、活動(dòng)圖像解碼時(shí)，難以用硬件實(shí)現(xiàn)。而并行解碼，可一碼時(shí)，難以用硬件實(shí)現(xiàn)。而并行解碼，可一次解出一個(gè)碼字，易于硬件實(shí)現(xiàn)，解碼速度次解出一個(gè)碼字，易于硬件實(shí)現(xiàn)，解碼速度快?？臁Ｓ纬叹幋a游程編碼是一種簡單的無損壓縮的方法。是一種簡單的無損壓縮的方法。概念：概念：行程行程：具有相同灰度值的像素序列。：具有相同灰度值的像素序列。編碼思想：編碼思想：去除像素冗余。去除像素冗余。用行程的灰度和行程的長度代替行程本身。用行程的灰度和行程的長度代替行程本身。例：設(shè)重復(fù)次數(shù)為例：設(shè)重復(fù)次數(shù)為 iC, 重復(fù)像素值為重復(fù)像素值為 iP編碼為：編碼為：iCiP iCiP iCiP 編碼前：編碼前：aaaaaaabbbbb

19、bcccccccc 編碼后：編碼后：7a6b8c基本方法：基本方法： 使用一新字符序列代取原始數(shù)據(jù)中相同的字使用一新字符序列代取原始數(shù)據(jù)中相同的字 符序列，來實(shí)現(xiàn)數(shù)據(jù)壓縮。（壓縮原始符序列，來實(shí)現(xiàn)數(shù)據(jù)壓縮。（壓縮原始數(shù)據(jù)數(shù)據(jù)中相同的字符序列）中相同的字符序列）把沿著掃描行的象素序列把沿著掃描行的象素序列x1, x2, xN映射映射為行程序列為行程序列(g1, l1), (g2, l2), (gk, lk) gi灰度級(jí)灰度級(jí) ligi的行程長度的行程長度因?yàn)橄笏匦蛄锌梢愿鶕?jù)行程序列來重建，故行因?yàn)橄笏匦蛄锌梢愿鶕?jù)行程序列來重建，故行程映射變換是可逆的。因它包含灰度鑒別和行程映射變換是可逆的。因它

20、包含灰度鑒別和行程計(jì)數(shù)，故它是非線性的。程計(jì)數(shù)，故它是非線性的。分析：分析：對(duì)于有大面積色塊的圖像，壓縮效果很對(duì)于有大面積色塊的圖像，壓縮效果很好好對(duì)于紛雜的圖像，壓縮效果不好，最壞對(duì)于紛雜的圖像，壓縮效果不好，最壞情況下，會(huì)加倍圖像情況下，會(huì)加倍圖像例如一個(gè)數(shù)據(jù)字符串為例如一個(gè)數(shù)據(jù)字符串為RTTTTTTTTABBC KGHJK用一新的字符串：用一新的字符串：#8T，代替，代替8個(gè)個(gè)T。#為特殊標(biāo)識(shí)符，表示行程編碼。為特殊標(biāo)識(shí)符，表示行程編碼。8代表其后字符重復(fù)的次數(shù)代表其后字符重復(fù)的次數(shù)；T為重復(fù)的字符。為重復(fù)的字符。則行程編碼后的字符串為：則行程編碼后的字符串為：R8TABBC K GHJ

21、K壓縮前總字符數(shù)壓縮前總字符數(shù) 18壓縮后總字符數(shù)壓縮后總字符數(shù) 13其壓縮比：其壓縮比：= 18/13 = 1.38幾點(diǎn)說明幾點(diǎn)說明： 1、如果原始數(shù)據(jù)字符串包含了、如果原始數(shù)據(jù)字符串包含了“#”符符號(hào)，則用兩個(gè)號(hào)，則用兩個(gè)“#”符號(hào)替換原始數(shù)據(jù)字符串符號(hào)替換原始數(shù)據(jù)字符串中的中的“#”符號(hào)。符號(hào)。2、原始數(shù)據(jù)字符串中重復(fù)字符數(shù)少于、原始數(shù)據(jù)字符串中重復(fù)字符數(shù)少于4個(gè)，個(gè)，則行程編碼無效。則行程編碼無效。3、壓縮對(duì)象可以是重復(fù)的單個(gè)字符序列，也、壓縮對(duì)象可以是重復(fù)的單個(gè)字符序列，也可以是重復(fù)的多個(gè)字符序列。對(duì)于后者，必可以是重復(fù)的多個(gè)字符序列。對(duì)于后者，必須標(biāo)識(shí)一個(gè)字符序列的長度或者結(jié)束標(biāo)志

22、。須標(biāo)識(shí)一個(gè)字符序列的長度或者結(jié)束標(biāo)志。算術(shù)編碼：越來越流行（在很多標(biāo)準(zhǔn)中被算術(shù)編碼：越來越流行（在很多標(biāo)準(zhǔn)中被采用）采用）適合的場合：適合的場合：小字母表：如二進(jìn)制信源小字母表：如二進(jìn)制信源概率分布不均衡概率分布不均衡建模與編碼分開建模與編碼分開算術(shù)編碼算術(shù)編碼：對(duì)整個(gè)序列信源符號(hào)串產(chǎn)生一個(gè)唯一的對(duì)整個(gè)序列信源符號(hào)串產(chǎn)生一個(gè)唯一的標(biāo)識(shí)（標(biāo)識(shí)（ tag ）直接對(duì)序列進(jìn)行編碼（不是碼字的串直接對(duì)序列進(jìn)行編碼（不是碼字的串聯(lián)）：非分組碼聯(lián)）：非分組碼不用對(duì)該長度所有可能的序列編碼不用對(duì)該長度所有可能的序列編碼標(biāo)識(shí)是標(biāo)識(shí)是0,1)之間的一個(gè)數(shù)（二進(jìn)制小之間的一個(gè)數(shù)（二進(jìn)制小數(shù)，可作為序列的二進(jìn)制編碼

23、）數(shù)，可作為序列的二進(jìn)制編碼） 算術(shù)編碼中，信源符號(hào)與碼字之間不存在一一算術(shù)編碼中，信源符號(hào)與碼字之間不存在一一對(duì)應(yīng)的關(guān)系。一個(gè)碼字不是賦給某個(gè)信源符對(duì)應(yīng)的關(guān)系。一個(gè)碼字不是賦給某個(gè)信源符號(hào)，而是賦給整個(gè)消息序列。這個(gè)碼字本身號(hào)，而是賦給整個(gè)消息序列。這個(gè)碼字本身定義一個(gè)介于定義一個(gè)介于0和和1之間的實(shí)數(shù)區(qū)間，該區(qū)間之間的實(shí)數(shù)區(qū)間，該區(qū)間中的任何一個(gè)實(shí)數(shù)就代表要編碼的消息序列中的任何一個(gè)實(shí)數(shù)就代表要編碼的消息序列。當(dāng)消息中的符號(hào)數(shù)目增加時(shí)，用于描述消。當(dāng)消息中的符號(hào)數(shù)目增加時(shí)，用于描述消息的間隔變得更小，而表示間隔所需要的信息的間隔變得更小，而表示間隔所需要的信息單元（如編碼位數(shù)）變得更多了。

24、息單元（如編碼位數(shù)）變得更多了。定義一一映射：定義一一映射：ak FX(k-1), FX(k), k = 1.m, FX(0) = 0FX(k-1), FX(k)區(qū)間內(nèi)的任何數(shù)字表示區(qū)間內(nèi)的任何數(shù)字表示 ak對(duì)對(duì)2字母序列字母序列ak aj編碼編碼對(duì)對(duì)ak ，選擇，選擇FX(k-1), FX(k)然后將該區(qū)間按比例分割并選取第然后將該區(qū)間按比例分割并選取第j個(gè)區(qū)間：個(gè)區(qū)間： 11,111XXXXXXXXFjFjFkFkFkFkFkFk算術(shù)編碼方法：算術(shù)編碼方法：1.產(chǎn)生標(biāo)識(shí)將0, 1)分為m個(gè)區(qū)間： 00,.1,1XXXFmiiFiF考慮對(duì)考慮對(duì)a1a2a3編碼編碼：A = a1, a2, a

25、3, P = 0.7, 0.1, 0.2)映射：映射：a1 1, a2 2, a3 3cdf: FX(1) = 0.7, FX(2) = 0.8, FX(3) = 1.0A = a1, a2, , am對(duì)公平擲骰子的例子：1, 2, 3, 4, 5, 66.161kforkXP iXPiFiXPkXPaTXikiX2112111 25. 022112XPXPTX 75. 0521541XPkXPTkX映射成數(shù)字映射成數(shù)字字符串的詞典順序：字符串的詞典順序：其中其中 表示表示“在字母順序中，在字母順序中，y在在x的前面的前面”n 為序列的長度為序列的長度 ( ):12inXiiTPPy y xx

26、yxxy 考慮兩輪連續(xù)的骰子：考慮兩輪連續(xù)的骰子：輸出輸出 = 11, 12, , 16, 21, 22, , 26, , 61, 62, , 66 469. 07251321121113xPxPxPTXv注意：注意：為了產(chǎn)生為了產(chǎn)生13的標(biāo)識(shí)，我們不必對(duì)產(chǎn)生其他標(biāo)識(shí)的標(biāo)識(shí)，我們不必對(duì)產(chǎn)生其他標(biāo)識(shí)=但是，為了產(chǎn)生長度為但是，為了產(chǎn)生長度為n的字符串的標(biāo)識(shí)，我的字符串的標(biāo)識(shí)，我們必須知道比其短的字符串的概率們必須知道比其短的字符串的概率這與產(chǎn)生所有的碼字一樣繁重！這與產(chǎn)生所有的碼字一樣繁重！應(yīng)該想辦法來避免此事應(yīng)該想辦法來避免此事區(qū)間構(gòu)造區(qū)間構(gòu)造包含某個(gè)標(biāo)識(shí)的區(qū)間與所有其他標(biāo)識(shí)的區(qū)間不相交包含某

27、個(gè)標(biāo)識(shí)的區(qū)間與所有其他標(biāo)識(shí)的區(qū)間不相交基本思想基本思想遞歸：將序列的下遞歸：將序列的下/上界視為更短序列的界的上界視為更短序列的界的函數(shù)函數(shù)上述骰子的例子：上述骰子的例子：考慮序列：考慮序列：3 2 2 令令u(n), l(n) 為長度為為長度為n序列的上界和下界，則序列的上界和下界，則 u(1) = FX(3), l(1) = FX(2)u(2) = FX(2)(32), l(2) = FX(2)(31) (2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx6661212112111,iiiPkiP xk xiP xkP xiP xkwherex xxx

28、(2)1132(1)(2)(31)(32)(2)(31)(32)XXFP xP xPPFPPxxxx1221(31)(32)(3)(1)(2)(3)(2)XPPP xP xP xP xFxx)2()3()3(1XXFFxP)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu ) 1 ()2()3()2(31)2(XXXXXFFFFF) 1 ()1()1()1()2(XFlull()()(3)( )(3)( )322 ,32133XXuFlF=()()(3)(2)(2)(2)322(31)(32)(31)(2)XXXXXFFFFF=+-()()(3)(

29、2)(2)(2)321(31)(32)(31)(1)XXXXXFFFFF=+-)2()2()2()2()3(XFlulu) 1 ()2()2()2()3(XFlull)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu產(chǎn)生標(biāo)識(shí)：產(chǎn)生標(biāo)識(shí)：通常，對(duì)任意序列通常，對(duì)任意序列x = x1x2xn ( )( )2nnXulTx( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl只需知道信源的只需知道信源的cdfcdf，即信源的概率模型，即信源的概率模型算術(shù)編碼：編碼和解碼過程都只涉及算術(shù)運(yùn)算（加、算術(shù)編碼

30、：編碼和解碼過程都只涉及算術(shù)運(yùn)算（加、減、乘、除）減、乘、除）考慮隨機(jī)變量考慮隨機(jī)變量X(ai) = i 對(duì)序列對(duì)序列1 3 2 1編碼：編碼：3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX1, 0)0()0(ul8 . 0) 1 (0)0()0()0()0()1()0()0()0()1(XXFluluFlull18 . 0)3(656. 0)2()1()1()1()2()1()1()1()2(XXFluluFlull1377408. 0)2(7712. 0) 1 ()2()2()2()3()2()2()2()3(XXFluluFlull132()()(4)(1)(3)(3)(4)(3)(3)(3)( )0.7712(1)0.7735040XXllulFululF=+-=+-=1321(4)(4)13210.7723522XulT( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl算術(shù)編碼的唯一性和有效性算術(shù)編碼的唯一性和有效性上述產(chǎn)生的標(biāo)識(shí)可以唯一表示一個(gè)序列，上述產(chǎn)生的標(biāo)識(shí)可以唯一表示一個(gè)序列，這意味著該標(biāo)識(shí)的二進(jìn)制表示為序列的唯這意味著該標(biāo)識(shí)的二進(jìn)制