多媒體通信技術(shù)四-修訂

1、第四章第四章 視頻信息壓縮與處理視頻信息壓縮與處理第四章第四章 視頻信息壓縮與處理視頻信息壓縮與處理本章主要內(nèi)容本章主要內(nèi)容 圖像信號的相關(guān)特點圖像信號的相關(guān)特點 圖像處理方法圖像處理方法 各種實用編碼各種實用編碼 常見的圖像壓縮編碼標(biāo)準(zhǔn)常見的圖像壓縮編碼標(biāo)準(zhǔn) 圖像信號的相關(guān)特點圖像信號的相關(guān)特點 通常一幅圖像中的各像素之間存在一定的通常一幅圖像中的各像素之間存在一定的相關(guān)性。相關(guān)性。 在活動圖像中，由于兩幅相鄰圖像之間的時在活動圖像中，由于兩幅相鄰圖像之間的時間間隔很短，因此這兩幅圖像信息中包含大量間間隔很短，因此這兩幅圖像信息中包含大量相關(guān)信息。相關(guān)信息。 這些就是圖像信息中的冗余。這些就

2、是圖像信息中的冗余。 圖像信號的相關(guān)特點圖像信號的相關(guān)特點 多媒體數(shù)據(jù)壓縮的目的就是要去除圖像信多媒體數(shù)據(jù)壓縮的目的就是要去除圖像信息中的大量冗余，同時又能保證圖像的質(zhì)量。息中的大量冗余，同時又能保證圖像的質(zhì)量。 一般針對不同類型的冗余信息，采取不同的一般針對不同類型的冗余信息，采取不同的壓縮方法。壓縮方法。 1. 1.空間冗余空間冗余空間冗余是在圖像數(shù)據(jù)中經(jīng)常存在的一種冗余?？臻g冗余是在圖像數(shù)據(jù)中經(jīng)常存在的一種冗余。 在任何一幅圖像中在任何一幅圖像中： 均有許多灰度或顏色都均有許多灰度或顏色都相同的鄰近像素相同的鄰近像素組成的組成的局部區(qū)域局部區(qū)域，它們之間具有空間上的，它們之間具有空間上的

3、強相關(guān)性，在圖像中就強相關(guān)性，在圖像中就表現(xiàn)為空間冗余。表現(xiàn)為空間冗余。 1. 1.空間冗余空間冗余 顏色相同的區(qū)域顏色相同的區(qū)域 對空間冗余的壓縮方法就是把這種對空間冗余的壓縮方法就是把這種顏色都顏色都相相同的鄰近像素組成的同的鄰近像素組成的局部區(qū)域局部區(qū)域當(dāng)作一個整體，當(dāng)作一個整體，用極少的數(shù)據(jù)量來表示它，從而節(jié)省了存儲空用極少的數(shù)據(jù)量來表示它，從而節(jié)省了存儲空間。間。 這種壓縮方法叫這種壓縮方法叫空間壓縮空間壓縮或或幀內(nèi)壓縮幀內(nèi)壓縮。：視頻信號和動畫：視頻信號和動畫是基是基于時間軸的一組于時間軸的一組連續(xù)畫面連續(xù)畫面。 由于活動圖像序列中的任意兩幅相由于活動圖像序列中的任意兩幅相鄰的圖像

4、之間的時間間隔很短，因此兩幅圖像中鄰的圖像之間的時間間隔很短，因此兩幅圖像中存在大量的相關(guān)信息存在大量的相關(guān)信息 時間冗余時間冗余 相鄰幀包含相同的背景和移動物體，只不過移相鄰幀包含相同的背景和移動物體，只不過移動物體所在的空間位置略有不同動物體所在的空間位置略有不同 活動圖像中的兩幅相鄰的圖像有較大的相關(guān)活動圖像中的兩幅相鄰的圖像有較大的相關(guān)性，這反映為性，這反映為時間冗余時間冗余。 在前一幅圖像的基礎(chǔ)上，只需改變少量的數(shù)在前一幅圖像的基礎(chǔ)上，只需改變少量的數(shù)據(jù)，便可以表示出后一幅圖像，達(dá)到數(shù)據(jù)壓縮據(jù)，便可以表示出后一幅圖像，達(dá)到數(shù)據(jù)壓縮的目的。的目的。 這種壓縮對活動圖像往往能得到很高的壓

5、縮比，這種壓縮對活動圖像往往能得到很高的壓縮比，這也稱為這也稱為時間壓縮時間壓縮或或幀間壓縮幀間壓縮。3. 3.統(tǒng)計冗余統(tǒng)計冗余 空間冗余和時間冗余是將圖像信號看作為隨空間冗余和時間冗余是將圖像信號看作為隨機信號時所反映出的統(tǒng)計特征，因此有時把這機信號時所反映出的統(tǒng)計特征，因此有時把這兩種冗余稱為兩種冗余稱為統(tǒng)計冗余統(tǒng)計冗余。 4. 4.信息熵冗余信息熵冗余信息熵是針對數(shù)據(jù)的信息量而言的，它代表信息熵是針對數(shù)據(jù)的信息量而言的，它代表從圖像信息源中發(fā)出的一個符號的平均信息量從圖像信息源中發(fā)出的一個符號的平均信息量設(shè)某種編碼的平均碼長單位（符號）的設(shè)某種編碼的平均碼長單位（符號）的數(shù)據(jù)量數(shù)據(jù)量為為

6、式中，式中， 為分配給第為分配給第 符號的比特數(shù)，即符號的比特數(shù)，即二進(jìn)制位數(shù)二進(jìn)制位數(shù)niniiiiiSpSpSISpXH112)(log)()()()(niiiSlSpL1)()()(iSliS 由于實際中很難估算各符號出現(xiàn)的概率，我由于實際中很難估算各符號出現(xiàn)的概率，我們一般認(rèn)為它們是等概率的，所以每個符號比們一般認(rèn)為它們是等概率的，所以每個符號比特數(shù)相同。特數(shù)相同。 這種編碼的符號的數(shù)據(jù)量這種編碼的符號的數(shù)據(jù)量L L為最大。為最大。 但實際各符號出現(xiàn)的概率并不相同。但實際各符號出現(xiàn)的概率并不相同。 這樣所得的這樣所得的L L必然大于實際的信源熵必然大于實際的信源熵H H，由此，由此帶來

7、的冗余我們稱為帶來的冗余我們稱為信息熵冗余信息熵冗余或或編碼冗余編碼冗余。 )()()(21nSlSlSlniiiSlSpL1)()(總結(jié)總結(jié)： 數(shù)據(jù)中通常包含很大的冗余，數(shù)據(jù)的大小與所數(shù)據(jù)中通常包含很大的冗余，數(shù)據(jù)的大小與所攜帶的信息量的關(guān)系由下式給出：攜帶的信息量的關(guān)系由下式給出： L=H+R L=H+R H H：信源熵（信息量：信源熵（信息量/ /符號，代表最小比特數(shù)）、符號，代表最小比特數(shù)）、 L L：數(shù)據(jù)量（平均碼長單位，即符號實際的比特：數(shù)據(jù)量（平均碼長單位，即符號實際的比特數(shù)）數(shù)） R R：冗余量（即信息冗余量）：冗余量（即信息冗余量） R=L-HR=L-H5. 5.結(jié)構(gòu)冗余結(jié)構(gòu)

8、冗余 有些圖像從整體上看存在著非常強的紋理結(jié)構(gòu)。有些圖像從整體上看存在著非常強的紋理結(jié)構(gòu)。 下圖為草席圖像。下圖為草席圖像。是一種是一種規(guī)則有序排列的圖形規(guī)則有序排列的圖形，我們稱它在結(jié)構(gòu)上存在冗余我們稱它在結(jié)構(gòu)上存在冗余 。是一種結(jié)構(gòu)冗余。是一種結(jié)構(gòu)冗余。規(guī)則有序排列的圖形規(guī)則有序排列的圖形6. 6.知識冗余知識冗余 有些圖像的理解與某些知識有相當(dāng)大的相關(guān)有些圖像的理解與某些知識有相當(dāng)大的相關(guān)性。性。 比如人臉的圖像有固定的結(jié)構(gòu)：比如人臉的圖像有固定的結(jié)構(gòu)： 嘴的上方有鼻子、鼻子的上方有雙眼睛，鼻嘴的上方有鼻子、鼻子的上方有雙眼睛，鼻子位于正臉圖像的中線上等等子位于正臉圖像的中線上等等 這類

9、規(guī)律的結(jié)構(gòu)可由先驗知識和背景知識得這類規(guī)律的結(jié)構(gòu)可由先驗知識和背景知識得到，因此這類信息對一般人來說就是冗余信息。到，因此這類信息對一般人來說就是冗余信息。這就是知識冗余。這就是知識冗余。7. 7.視覺冗余視覺冗余 由于人眼的視覺特性有所限制，人類的視由于人眼的視覺特性有所限制，人類的視覺系統(tǒng)不能對圖像畫面的任何變化都能感覺到。覺系統(tǒng)不能對圖像畫面的任何變化都能感覺到。 舉例：舉例： 人眼視覺系統(tǒng)的一般分辨率為人眼視覺系統(tǒng)的一般分辨率為6464灰度等級灰度等級, ,而而一般圖像的量化采用的是一般圖像的量化采用的是256256的灰度等級。的灰度等級。 這種差別就是視覺冗余。這種差別就是視覺冗余。

10、 視頻壓縮編碼方法及其分類視頻壓縮編碼方法及其分類 圖像壓縮的基本目標(biāo)就是減小數(shù)據(jù)量。圖像壓縮的基本目標(biāo)就是減小數(shù)據(jù)量。 至于圖像壓縮到什么程度而又沒有明顯的失真至于圖像壓縮到什么程度而又沒有明顯的失真, ,則取決于圖像數(shù)據(jù)的冗余度。則取決于圖像數(shù)據(jù)的冗余度。所有的這些冗余所有的這些冗余度都可以被除去而不會引起顯著的信息損失。度都可以被除去而不會引起顯著的信息損失。空間冗余空間冗余和和時間冗余時間冗余是圖像信號最常見的冗余是圖像信號最常見的冗余。壓縮編碼分類壓縮編碼分類1. 1.按恢復(fù)的圖像性質(zhì)劃分按恢復(fù)的圖像性質(zhì)劃分 按恢復(fù)的圖像性質(zhì)按恢復(fù)的圖像性質(zhì), ,數(shù)字圖像壓縮方法可以分為兩數(shù)字圖像壓

11、縮方法可以分為兩種種： 無損壓縮編碼無損壓縮編碼 有損壓縮編碼有損壓縮編碼 壓縮編碼分類壓縮編碼分類 無損壓縮編碼無損壓縮編碼： 也稱為熵編碼、可逆編碼或無失真編碼。也稱為熵編碼、可逆編碼或無失真編碼。 當(dāng)系統(tǒng)采用此方法進(jìn)行數(shù)據(jù)壓縮時當(dāng)系統(tǒng)采用此方法進(jìn)行數(shù)據(jù)壓縮時, ,在接收端所在接收端所獲得的解碼與原圖像完全相同獲得的解碼與原圖像完全相同。 無損壓縮不能提供較高的壓縮比。無損壓縮不能提供較高的壓縮比。 一般在一般在2:12:15:15:1。 壓縮編碼分類壓縮編碼分類 有損編碼有損編碼： 也稱為不可逆編碼、熵壓縮編碼或失真編碼。也稱為不可逆編碼、熵壓縮編碼或失真編碼。 由于壓縮了熵，會減少信息

12、而不能再恢復(fù)。由于壓縮了熵，會減少信息而不能再恢復(fù)。 這種壓縮編碼具有較高的壓縮比。這種壓縮編碼具有較高的壓縮比。 最大可達(dá)幾百比一。最大可達(dá)幾百比一。壓縮編碼分類壓縮編碼分類2. 2.按壓縮方法的原理劃分按壓縮方法的原理劃分 按壓縮原理劃分按壓縮原理劃分, ,數(shù)字圖像壓縮方法可以分為以數(shù)字圖像壓縮方法可以分為以下幾種編碼下幾種編碼: : 預(yù)測編碼預(yù)測編碼 變換編碼變換編碼 標(biāo)量量化和矢量量化編碼標(biāo)量量化和矢量量化編碼 信息熵編碼信息熵編碼 子帶編碼子帶編碼 結(jié)構(gòu)編碼結(jié)構(gòu)編碼 模型編碼模型編碼圖像壓縮編碼圖像壓縮編碼無損壓縮無損壓縮有損壓縮有損壓縮霍夫曼編碼霍夫曼編碼行程編碼行程編碼算術(shù)編碼算

13、術(shù)編碼L-Z編碼編碼預(yù)測編碼預(yù)測編碼:量化量化編碼編碼:模型編碼模型編碼:混合編碼混合編碼:變換編碼變換編碼:DPCM；運動補償；運動補償DCT；子帶編碼；子帶編碼分形編碼；分形編碼；知識知識基編碼基編碼JPEG；MPEG；H.26X編碼編碼采樣編碼；矢量量化編碼采樣編碼；矢量量化編碼圖像壓縮算法分類圖像壓縮算法分類壓縮編碼分類壓縮編碼分類（1 1）預(yù)測編碼：）預(yù)測編碼： 其典型的壓縮方法有其典型的壓縮方法有DPCMDPCM和和ADPCM.ADPCM.它們比它們比較適合于圖像數(shù)據(jù)的壓縮。較適合于圖像數(shù)據(jù)的壓縮。 它主要是減少圖像數(shù)據(jù)在它主要是減少圖像數(shù)據(jù)在空間上空間上和和時間上時間上的相的相關(guān)

14、性，從而達(dá)到數(shù)據(jù)壓縮的目的，但這是一種關(guān)性，從而達(dá)到數(shù)據(jù)壓縮的目的，但這是一種有失真的壓縮方法。有失真的壓縮方法。 壓縮編碼分類壓縮編碼分類（2 2）變換編碼：）變換編碼： 它是將圖像它是將圖像時域信號時域信號轉(zhuǎn)換到轉(zhuǎn)換到變換域變換域（系數(shù)空（系數(shù)空間、頻域）上進(jìn)行處理。間、頻域）上進(jìn)行處理。 在實際編碼中，常常利用圖像的統(tǒng)計特性和在實際編碼中，常常利用圖像的統(tǒng)計特性和人眼的視覺特性，只是選擇部分變換系數(shù)來進(jìn)人眼的視覺特性，只是選擇部分變換系數(shù)來進(jìn)行信息傳輸，因此恢復(fù)的圖像中將存在一定的行信息傳輸，因此恢復(fù)的圖像中將存在一定的失真。失真。 常用的正交變換有：離散傅氏變換常用的正交變換有：離散傅

15、氏變換DFTDFT、離、離散余弦變換散余弦變換DCTDCT、離散正弦變換、離散正弦變換DSTDST和和K-LK-L變換。變換。壓縮編碼分類壓縮編碼分類（3 3）標(biāo)量量化和矢量量化編碼：）標(biāo)量量化和矢量量化編碼： 標(biāo)量量化指傳統(tǒng)的量化，是將具有無限電平標(biāo)量量化指傳統(tǒng)的量化，是將具有無限電平的點樣值，用有限電平數(shù)表示的方法，是一個的點樣值，用有限電平數(shù)表示的方法，是一個樣點、一個樣點地進(jìn)行量化編碼樣點、一個樣點地進(jìn)行量化編碼。 這里量化器的設(shè)計是一個很關(guān)鍵的步驟。這里量化器的設(shè)計是一個很關(guān)鍵的步驟。 壓縮編碼分類壓縮編碼分類（3 3）標(biāo)量量化和矢量量化編碼：）標(biāo)量量化和矢量量化編碼： 矢量編碼是相

16、對標(biāo)量量化而提出的矢量編碼是相對標(biāo)量量化而提出的。 矢量編碼中一次可以量化多個樣點矢量編碼中一次可以量化多個樣點。 矢量量化也是一種有損壓縮編碼。矢量量化也是一種有損壓縮編碼。壓縮編碼分類壓縮編碼分類（4 4）信息熵編碼：）信息熵編碼： 信息熵編碼是一種基于圖像統(tǒng)計特性的編碼信息熵編碼是一種基于圖像統(tǒng)計特性的編碼方法。方法。 是一種無損壓縮編碼方法。是一種無損壓縮編碼方法。 壓縮編碼分類壓縮編碼分類（4 4）信息熵編碼：）信息熵編碼： 它是根據(jù)信息熵的原理它是根據(jù)信息熵的原理： 用最短的位數(shù)表示出現(xiàn)概率大的信息，而出現(xiàn)用最短的位數(shù)表示出現(xiàn)概率大的信息，而出現(xiàn)概率較小的信息則用較長的位數(shù)來表示，

17、以此概率較小的信息則用較長的位數(shù)來表示，以此達(dá)到壓縮數(shù)據(jù)的目的。達(dá)到壓縮數(shù)據(jù)的目的。 常見的熵編碼有常見的熵編碼有哈夫曼編碼哈夫曼編碼、游程編碼游程編碼和和算術(shù)算術(shù)編碼編碼。壓縮編碼分類壓縮編碼分類（5 5）子帶編碼：）子帶編碼： 在子帶編碼中，首先將圖像數(shù)據(jù)轉(zhuǎn)換到頻在子帶編碼中，首先將圖像數(shù)據(jù)轉(zhuǎn)換到頻域，然后按頻率分成若干子帶，對每個子帶用域，然后按頻率分成若干子帶，對每個子帶用不同的編碼器進(jìn)行抽樣、量化和編碼，并將各不同的編碼器進(jìn)行抽樣、量化和編碼，并將各子帶輸出數(shù)據(jù)合成為數(shù)據(jù)碼流，從而獲得壓縮子帶輸出數(shù)據(jù)合成為數(shù)據(jù)碼流，從而獲得壓縮數(shù)據(jù)。數(shù)據(jù)。 壓縮編碼分類壓縮編碼分類（6 6）結(jié)構(gòu)編碼

18、：）結(jié)構(gòu)編碼： 結(jié)構(gòu)編碼也稱為第二代編碼。結(jié)構(gòu)編碼也稱為第二代編碼。 編碼時首先求出圖像中的邊界、輪廓、紋理編碼時首先求出圖像中的邊界、輪廓、紋理等結(jié)構(gòu)特征參數(shù)，然后保存這些參數(shù)信息，進(jìn)等結(jié)構(gòu)特征參數(shù)，然后保存這些參數(shù)信息，進(jìn)行編碼。行編碼。 在解碼時則根據(jù)這些結(jié)構(gòu)和參數(shù)信息進(jìn)行圖在解碼時則根據(jù)這些結(jié)構(gòu)和參數(shù)信息進(jìn)行圖像合成，從而恢復(fù)出原圖像。像合成，從而恢復(fù)出原圖像。壓縮編碼分類壓縮編碼分類（7 7）模型編碼：）模型編碼： 這是一種基于知識的編碼。這是一種基于知識的編碼。 利用人們對自然知識的了解而形成一個規(guī)則利用人們對自然知識的了解而形成一個規(guī)則庫，將人臉變化等特征用一系列參數(shù)來進(jìn)行描庫，

19、將人臉變化等特征用一系列參數(shù)來進(jìn)行描述。述。 利用參數(shù)再加上模型就可以實現(xiàn)人臉的圖像利用參數(shù)再加上模型就可以實現(xiàn)人臉的圖像編碼和解碼，達(dá)到壓縮圖像數(shù)據(jù)的目的。編碼和解碼，達(dá)到壓縮圖像數(shù)據(jù)的目的。數(shù)據(jù)壓縮技術(shù)的性能指標(biāo)數(shù)據(jù)壓縮技術(shù)的性能指標(biāo) 1 1、壓縮比、壓縮比用來定義壓縮性能。指壓縮過程中輸入數(shù)據(jù)用來定義壓縮性能。指壓縮過程中輸入數(shù)據(jù)量與輸出數(shù)據(jù)量之比。量與輸出數(shù)據(jù)量之比。 設(shè)原圖像的平均碼長為設(shè)原圖像的平均碼長為Lc,Lc, 壓縮后圖像的平均碼壓縮后圖像的平均碼長為長為L L，則壓縮比，則壓縮比C C為為壓縮比越大，說明數(shù)據(jù)壓縮的程度越高。壓縮比越大，說明數(shù)據(jù)壓縮的程度越高。LLCC 冗余

20、度冗余度和和編碼效率編碼效率也是衡量信源特性以及編解碼也是衡量信源特性以及編解碼設(shè)備性能的重要指標(biāo)，定義如下：設(shè)備性能的重要指標(biāo)，定義如下：冗余度冗余度: :指冗余量在信息量中占的比例指冗余量在信息量中占的比例 L L為平均碼字長度為平均碼字長度 H(X)H(X)為信源熵。為信源熵。編碼效率編碼效率：指信息量在數(shù)據(jù)量中占的比例：指信息量在數(shù)據(jù)量中占的比例 1)(XHLRRLXH11)(數(shù)據(jù)壓縮技術(shù)的性能指標(biāo)數(shù)據(jù)壓縮技術(shù)的性能指標(biāo)2 2、重現(xiàn)質(zhì)量：、重現(xiàn)質(zhì)量： 恢復(fù)效果要好，要盡可能地恢復(fù)原始數(shù)據(jù)?；謴?fù)效果要好，要盡可能地恢復(fù)原始數(shù)據(jù)。 3 3、壓縮和解壓縮速度、壓縮和解壓縮速度無損圖像壓縮編碼

21、方法無損圖像壓縮編碼方法 無失真（無損）圖像壓縮編碼就是指圖像經(jīng)無失真（無損）圖像壓縮編碼就是指圖像經(jīng)過壓縮、編碼后恢復(fù)出的圖像與原圖像完全一過壓縮、編碼后恢復(fù)出的圖像與原圖像完全一樣樣, ,沒有任何失真。沒有任何失真。 無失真壓縮編碼無失真壓縮編碼-熵熵編碼編碼。 廣泛應(yīng)用于文本數(shù)據(jù)和特殊應(yīng)用場合的圖廣泛應(yīng)用于文本數(shù)據(jù)和特殊應(yīng)用場合的圖像數(shù)據(jù)（指紋圖像、醫(yī)學(xué)圖像、衛(wèi)星圖像等）像數(shù)據(jù)（指紋圖像、醫(yī)學(xué)圖像、衛(wèi)星圖像等）的壓縮。的壓縮。無損圖像壓縮編碼方法無損圖像壓縮編碼方法 香農(nóng)信息論認(rèn)為香農(nóng)信息論認(rèn)為, ,信源中或多或少地含有自信源中或多或少地含有自然冗余度。然冗余度。 這些冗余度既來自于信源

22、本身的相關(guān)性這些冗余度既來自于信源本身的相關(guān)性, ,又來又來自于信源概率分布的不均勻性中。自于信源概率分布的不均勻性中。 只要找到去除相關(guān)性或改變概率分布不均勻只要找到去除相關(guān)性或改變概率分布不均勻性的方法和手段性的方法和手段, ,也就找到了信息熵編碼的方法。也就找到了信息熵編碼的方法。 無損圖像壓縮編碼方法無損圖像壓縮編碼方法 例如例如： 在圖像中存在著空間上的相關(guān)性在圖像中存在著空間上的相關(guān)性 對運動圖像而言存在著幀與幀之間在時間上的相對運動圖像而言存在著幀與幀之間在時間上的相關(guān)性。關(guān)性。 這些都說明這些都說明存在著存在著顏色顏色的概率分布的不均勻性的概率分布的不均勻性。 無損圖像壓縮編碼

23、方法無損圖像壓縮編碼方法 信息熵編碼所要解決的問題：信息熵編碼所要解決的問題： 如何利用信息熵理論（香農(nóng)信息論）減少數(shù)如何利用信息熵理論（香農(nóng)信息論）減少數(shù)據(jù)在傳輸和存儲時的冗余度據(jù)在傳輸和存儲時的冗余度。香農(nóng)信息論香農(nóng)信息論 香農(nóng)信息論認(rèn)為：香農(nóng)信息論認(rèn)為： 信源所含有的信息熵就是進(jìn)行無失真編碼的信源所含有的信息熵就是進(jìn)行無失真編碼的理論極限。理論極限。 niniiiiiSpSpSISpXH112)(log)()()()(香農(nóng)信息論香農(nóng)信息論 低于此極限的無失真編碼方法是找不到的低于此極限的無失真編碼方法是找不到的, ,而只要不低于此極限而只要不低于此極限, ,那就總能找到某種適宜的那就總能

24、找到某種適宜的編碼方法任意的逼近信息熵。編碼方法任意的逼近信息熵。 熵編碼的目的就是要使編碼后的圖像熵編碼的目的就是要使編碼后的圖像平均碼字平均碼字長度（比特數(shù)）長度（比特數(shù)）L L近可能接近這個近可能接近這個信息熵信息熵H(x)H(x) niniiiiiSpSpSISpXH112)(log)()()()(無損圖像壓縮編碼方法無損圖像壓縮編碼方法根據(jù)：根據(jù)： L=H+R L=H+R H H：信源熵（信息量：信源熵（信息量/ /符號，代表符號的最小比特符號，代表符號的最小比特數(shù)）、數(shù)）、 L L：數(shù)據(jù)量（每個符號實際平均的比特數(shù)，也稱：數(shù)據(jù)量（每個符號實際平均的比特數(shù)，也稱碼字長度碼字長度） R

25、 R：冗余量（即信息冗余量）：冗余量（即信息冗余量） R=L-HR=L-H 無損數(shù)據(jù)壓縮的本質(zhì)：通過減少冗余量無損數(shù)據(jù)壓縮的本質(zhì)：通過減少冗余量R R，減少，減少數(shù)據(jù)量數(shù)據(jù)量L L，使之接近，使之接近H H。無損圖像壓縮編碼方法無損圖像壓縮編碼方法 無損圖像壓縮編碼方法由于其中并沒有考慮人無損圖像壓縮編碼方法由于其中并沒有考慮人眼的視覺特性眼的視覺特性, ,因此其所能達(dá)到的壓縮比非常有因此其所能達(dá)到的壓縮比非常有限。限。 常用的無失真圖像壓縮編碼有：常用的無失真圖像壓縮編碼有： 哈夫曼編碼哈夫曼編碼 游程編碼（行程編碼）游程編碼（行程編碼） 算術(shù)編碼算術(shù)編碼 無損圖像壓縮編碼方法無損圖像壓縮編

26、碼方法 在實際應(yīng)用中在實際應(yīng)用中, ,常將游程編碼與哈夫曼編碼結(jié)常將游程編碼與哈夫曼編碼結(jié)合起來使用合起來使用, ,例如在例如在H.261H.261、JPEGJPEG、MPEGMPEG等國際等國際標(biāo)準(zhǔn)中正是采用此種編碼技術(shù)。標(biāo)準(zhǔn)中正是采用此種編碼技術(shù)。 而在而在H.263H.263等國際標(biāo)準(zhǔn)中則采用算術(shù)編碼技術(shù)。等國際標(biāo)準(zhǔn)中則采用算術(shù)編碼技術(shù)。哈夫曼編碼哈夫曼編碼 哈夫曼哈夫曼(Huffman)(Huffman)編碼方法于編碼方法于19521952年問世年問世, ,迄今為迄今為止仍經(jīng)久不衰止仍經(jīng)久不衰, ,廣泛應(yīng)用于各種數(shù)據(jù)壓縮技術(shù)中廣泛應(yīng)用于各種數(shù)據(jù)壓縮技術(shù)中, ,且仍不失為熵編碼中的最佳編

27、碼方法。且仍不失為熵編碼中的最佳編碼方法。主要編碼思路：主要編碼思路： 對對出現(xiàn)頻率較大出現(xiàn)頻率較大的符號用的符號用較短的碼較短的碼來表示，來表示， 而對于而對于出現(xiàn)頻率較小出現(xiàn)頻率較小的符號則用的符號則用較長的碼較長的碼來表來表示。示。 這樣的編碼結(jié)果所獲得的平均碼字長度最短。這樣的編碼結(jié)果所獲得的平均碼字長度最短。哈夫曼編碼哈夫曼編碼 哈夫曼編碼的碼長是變化的，即可變長編碼哈夫曼編碼的碼長是變化的，即可變長編碼(VLC),(VLC),而且哈夫曼編碼通常被稱為最優(yōu)碼。而且哈夫曼編碼通常被稱為最優(yōu)碼。 最優(yōu)的含義是：最優(yōu)的含義是： 對于給定的符號集和概率模型，找不到任何其對于給定的符號集和概率

28、模型，找不到任何其它整數(shù)碼比哈夫曼編碼有更短的碼長。它整數(shù)碼比哈夫曼編碼有更短的碼長。 整數(shù)碼整數(shù)碼：指每個符號所對應(yīng)的碼字的位數(shù)都是指每個符號所對應(yīng)的碼字的位數(shù)都是整數(shù)。整數(shù)。哈夫曼編碼哈夫曼編碼具體編碼過程：具體編碼過程： 1 1、排序：按符號出現(xiàn)的概率從大到小進(jìn)行排、排序：按符號出現(xiàn)的概率從大到小進(jìn)行排列。列。 2 2、賦值：對排在最后的兩個符號進(jìn)行賦值，、賦值：對排在最后的兩個符號進(jìn)行賦值，概率大的賦概率大的賦“1”1”，概率小的賦，概率小的賦“0”0”?；蛳喾??；蛳喾?。 3 3、合并：將上述最后的兩個符號出現(xiàn)的概率、合并：將上述最后的兩個符號出現(xiàn)的概率相加合成一個概率。相加合成一個概

29、率。哈夫曼編碼哈夫曼編碼 4 4、重新排序：將合成后的概率與其它符號概率、重新排序：將合成后的概率與其它符號概率一起進(jìn)行重新排序（從大到?。?。然后重復(fù)步一起進(jìn)行重新排序（從大到小）。然后重復(fù)步驟驟2 2、3 3的內(nèi)容，直至概率相加為的內(nèi)容，直至概率相加為1 1為止。為止。 5 5、碼字分配：從最后一步開始反向進(jìn)行碼字分、碼字分配：從最后一步開始反向進(jìn)行碼字分配。從而形成一個碼字。配。從而形成一個碼字。哈夫曼編碼的基本原理哈夫曼編碼的基本原理例：例： aaaaaaaa bbbbbb cccc d d eeeeeeeeee ffffffffffffff 4 3 4 3 2 1 5 2 1 5 7

30、7 如果不進(jìn)行特殊的編碼，用字符方式如果不進(jìn)行特殊的編碼，用字符方式（ASCIIASCII碼）傳送，每個字符碼）傳送，每個字符8 8位，需要的位，需要的數(shù)據(jù)量為：數(shù)據(jù)量為： 2222* *8=8=176176 bit bit 哈夫曼編碼的基本原理哈夫曼編碼的基本原理cbafe7/227/225/225/224/224/222/222/2210f=11 e=01 a=00 b=101 c=1001 d=1000d1/221/223/223/226/226/2222/2222/2213/2213/229/229/223/223/2210101010哈夫曼編碼哈夫曼編碼哈夫曼編碼的基本原理哈夫曼編碼

31、的基本原理 aaaaaaaa bbbbbb cccc d d eeeeeeeeee ffffffffffffff 4 3 2 1 5 7 4 3 2 1 5 7按照哈夫曼編碼的原理進(jìn)行編碼：按照哈夫曼編碼的原理進(jìn)行編碼： a=00 b=101 c=1001 d=1000 e=01 f=11a=00 b=101 c=1001 d=1000 e=01 f=11需要的數(shù)據(jù)量為需要的數(shù)據(jù)量為 4 4* *2 2+3+3* *3 3+2+2* *4 4+1+1* *4 4+5+5* *2 2+7+7* *2 2= =5353bitbit比比2222* *8=176bit 8=176bit 少了少了123

32、123bitbit平均編碼長度平均編碼長度L L為為4 . 2)()(1niiiSLSPL哈夫曼編碼的基本原理哈夫曼編碼的基本原理例例 設(shè)信號源為設(shè)信號源為X= X= 、a a、e e、I I、m m、t t、c c、h h、rr。若傳送一個字符串若傳送一個字符串“I am a teacherI am a teacher”，對應(yīng)的概，對應(yīng)的概率為率為p=p=0.220.22、0.220.22、0.140.14、0.070.07、0.070.07、0.070.07、0.070.07、0.070.07、0.070.07, , 試給出該信源的霍夫曼編碼方案。試給出該信源的霍夫曼編碼方案。并計算壓縮比

33、并計算壓縮比C C、冗余度、冗余度R R和編碼效率。和編碼效率。 = =0101 a= a=0000 e= e=111111 I= I=11011101 m= m=11001100 t= t=10111011 c= c=10101010 h= h=10011001 r= r=10001000 出現(xiàn)出現(xiàn)3 3次，次，a a出現(xiàn)出現(xiàn)3 3次，次，e e出現(xiàn)出現(xiàn)2 2次，其它的各出現(xiàn)次，其它的各出現(xiàn)1 1次。次。 共需要共需要3 3* *2 2+3+3* *2 2+2+2* *3 3+6+6* *4 4= =4242bitbit分析分析: : 若傳送一個字符串若傳送一個字符串“I am a teac

34、her”“I am a teacher”，共，共1414個字個字符，其中包括符，其中包括9 9個不同的字符。個不同的字符。（1 1）若使用自然編碼（等長二進(jìn)制編碼），該字）若使用自然編碼（等長二進(jìn)制編碼），該字符串中有符串中有9 9個不同的符號，至少需要個不同的符號，至少需要4 4位二進(jìn)制位二進(jìn)制才能表示，這樣傳送該字符串也要才能表示，這樣傳送該字符串也要5656位。位。（2 2）HuffmanHuffman編碼只需要編碼只需要4242位位，平均編碼長度為，平均編碼長度為2.982.98。平均碼字長度公式為：平均碼字長度公式為：98. 24607. 0314. 02222. 0碼長概率niii

35、SLSPL1)()(求壓縮比、冗余度和編碼效率求壓縮比、冗余度和編碼效率: : 壓縮比壓縮比C C： 14 14個字符，需個字符，需4 4位二進(jìn)制數(shù)位二進(jìn)制數(shù) Lc=4 Lc=4 C=Lc/L=4/2.98= C=Lc/L=4/2.98= 1.34 :11.34 :1 冗余度冗余度R R=(L-H)/H=(2.98-2.97)/2.97=0.34%=(L-H)/H=(2.98-2.97)/2.97=0.34%編碼效率編碼效率符號/97. 207. 007. 0614. 0log14. 022. 0log22. 02)()()(22291bitligSISpXHiii%7 .9998. 297.

36、 2LH哈夫曼編碼哈夫曼編碼例：某信源符號及其對應(yīng)的概率如下：例：某信源符號及其對應(yīng)的概率如下： a1 a2 a3 a4 a5 a6a1 a2 a3 a4 a5 a6 0.4 0.2 0.12 0.15 0.1 0.03 0.4 0.2 0.12 0.15 0.1 0.03請完成哈夫曼編碼，并計算壓縮比、冗余度和編請完成哈夫曼編碼，并計算壓縮比、冗余度和編碼效率。碼效率。哈夫曼編碼哈夫曼編碼例：某信源符號及其對應(yīng)的概率如下：例：某信源符號及其對應(yīng)的概率如下： a1a1 a2a2 a3a3 a4a4 a5a5 a6a6 a7a7 a8a80.40 0.0.40 0.0404 0.1 0.1 0.

37、07 0.06 0. 0.1 0.1 0.07 0.06 0.1818 0.04 0.04請完成哈夫曼編碼，并計算壓縮比、冗余度和編請完成哈夫曼編碼，并計算壓縮比、冗余度和編碼效率。碼效率。a1:a1: 0 0 a2:a2: 1 11101100 0 a3:a3: 100 100 a4:a4: 1111 1111 a5:a5: 1011 1011 a6:a6: 1010 1010 a7:a7: 1 11101101 1 a8:a8: 110 110哈夫曼編碼哈夫曼編碼 特點：特點： （1 1）雖然哈夫曼碼長可變雖然哈夫曼碼長可變, ,但卻不需要另附同步但卻不需要另附同步碼。碼。 （2 2） 通

38、信雙方只要均擁有預(yù)先編寫的解釋各種通信雙方只要均擁有預(yù)先編寫的解釋各種代碼意義的代碼意義的詞典詞典( (即即碼本碼本), ),即可根據(jù)即可根據(jù)碼本碼本逐碼譯出。逐碼譯出。哈夫曼編碼哈夫曼編碼哈夫曼編碼有幾個問題值得注意哈夫曼編碼有幾個問題值得注意: :一、哈夫曼碼沒有錯誤保護(hù)功能。一、哈夫曼碼沒有錯誤保護(hù)功能。 如果碼串中有錯如果碼串中有錯, ,哪怕僅僅是哪怕僅僅是1 1位出錯位出錯, ,不但該碼不但該碼本身將會譯錯本身將會譯錯, ,更糟糕的是對后面的影響更糟糕的是對后面的影響, ,一錯就一錯就是一串是一串, ,一般稱這種現(xiàn)象為錯誤傳播。一般稱這種現(xiàn)象為錯誤傳播。 哈夫曼編碼哈夫曼編碼二、二、

39、不可調(diào)用中間的內(nèi)容不可調(diào)用中間的內(nèi)容 哈夫曼碼是可變長度碼，因此很難隨意查找哈夫曼碼是可變長度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼; ;三、接收端需保存一個與發(fā)送端相同的霍夫曼碼表三、接收端需保存一個與發(fā)送端相同的霍夫曼碼表 哈夫曼碼還是得到廣泛應(yīng)用哈夫曼碼還是得到廣泛應(yīng)用, ,哈夫曼編碼畢竟屬哈夫曼編碼畢竟屬于最佳編碼方法。于最佳編碼方法。游程編碼游程編碼RLCRLC 游程編碼（行程編碼）游程編碼（行程編碼）RLCRLC（RLE)RLE)是一種非是一種非常簡單的數(shù)據(jù)壓縮編碼形式。它在某些場合是常簡單的數(shù)據(jù)壓縮編碼形式。它在某些場合是非常

40、有效的一種無損壓縮編碼方法。非常有效的一種無損壓縮編碼方法。 游程編碼游程編碼RLCRLC 游程編碼編碼原則游程編碼編碼原則: : 連續(xù)重復(fù)的數(shù)據(jù)值序列（或稱為連續(xù)重復(fù)的數(shù)據(jù)值序列（或稱為“流流”）用一）用一個重復(fù)次數(shù)和單個數(shù)據(jù)值來代替。個重復(fù)次數(shù)和單個數(shù)據(jù)值來代替。比如：得到的字符串為比如：得到的字符串為AAAAAAAAABCDDDDDDDDAAABCDDDDDDDDD DBBBBBBBBBBBBBBBB 可壓縮為可壓縮為* *6 6ABCABC* *9 9D D* *8 8B B 顏色相同的區(qū)域顏色相同的區(qū)域游程編碼游程編碼RLCRLC 不需要存儲每一個像素的顏色值，而僅存儲不需要存儲每一

41、個像素的顏色值，而僅存儲一個像素的顏色值以及具有相同顏色的像素數(shù)一個像素的顏色值以及具有相同顏色的像素數(shù)目。目。 或者存儲一個像素的顏色值，以及具有相同顏或者存儲一個像素的顏色值，以及具有相同顏色值的行數(shù)。色值的行數(shù)。 這種壓縮編碼稱為這種壓縮編碼稱為游程編碼游程編碼或或行程編碼行程編碼。游程編碼游程編碼RLCRLC 游程編碼多用于游程編碼多用于黑白黑白圖像圖像或圖形或圖形的壓縮。的壓縮。 具有相同具有相同灰度等級灰度等級的連續(xù)的像素數(shù)目稱為的連續(xù)的像素數(shù)目稱為游游程程長度長度RLRL。 圖像中具有相同灰度的圖像塊越大越多，壓縮圖像中具有相同灰度的圖像塊越大越多，壓縮的效果就越好。的效果就越好

42、。 寬度：寬度：263 263 寬度：寬度：263263 高度：高度：300 300 高度：高度：300 300 灰度灰度：4 4 灰度灰度：8 8 游程編碼游程編碼RLCRLC RLCRLC特點：特點： 編碼簡單直觀，編碼編碼簡單直觀，編碼/ /解碼速度快解碼速度快，只需要簡只需要簡單地復(fù)制字符若干遍即可以了。單地復(fù)制字符若干遍即可以了。 BMPBMP、TIFFTIFF、AVIAVI等格式文件的壓縮均采用此方等格式文件的壓縮均采用此方法。在法。在PDFPDF文件格式中也得到應(yīng)用文件格式中也得到應(yīng)用。 存在著不同的實現(xiàn)技術(shù)和文件格式。存在著不同的實現(xiàn)技術(shù)和文件格式。游程編碼游程編碼RLCRLC

43、的構(gòu)成的構(gòu)成在在RLCRLC中用中用3 3個字節(jié)表示一個字符串：個字節(jié)表示一個字符串：由一個指示符、一個重復(fù)次數(shù)字節(jié)和一個被重復(fù)的由一個指示符、一個重復(fù)次數(shù)字節(jié)和一個被重復(fù)的字符構(gòu)成的字符構(gòu)成的3 3字節(jié)碼字節(jié)碼 思考：思考：RL RL ? ? 時，數(shù)據(jù)壓縮才用意義時，數(shù)據(jù)壓縮才用意義3游程編碼游程編碼RLCRLC方法方法例如例如: :字符串字符串 RTAAAASDEEEEERTAAAASDEEEEE經(jīng)經(jīng)RLERLE壓縮后為：壓縮后為： RT RT* *4ASD4ASD* *5E 5E “* *4A” 4A” 代替了代替了“AAAA”“AAAA” “ “* *5E” 5E” 代替代替“EEEE

44、E”“EEEEE” 指示符采用特殊字符指示符采用特殊字符* *： 指出一個指出一個RLCRLC編碼的開始，后面的數(shù)字表示重編碼的開始，后面的數(shù)字表示重復(fù)的次數(shù)，數(shù)字后的單個字符是被重復(fù)的字符。復(fù)的次數(shù)，數(shù)字后的單個字符是被重復(fù)的字符。游程編碼游程編碼RLCRLC方法方法例例: : 設(shè)有數(shù)據(jù)設(shè)有數(shù)據(jù)“AAAAAAA ABBBBCCCCCBBBBCCCCCCCCCDAAAAAADAAAAAA”試計算該數(shù)據(jù)的行程編碼。試計算該數(shù)據(jù)的行程編碼。解：解：A A重復(fù)重復(fù)4 4次，次，B B重復(fù)重復(fù)4 4次，次，C C重復(fù)重復(fù)7 7次，次，D D不重復(fù)，不重復(fù)，A A重復(fù)重復(fù)6 6次，次， RLC RLC數(shù)

45、據(jù)流為：數(shù)據(jù)流為：“# #4 4A#4B#A#4B#7 7CD#6ACD#6A”，其中，其中# #為指示符?？偣舱加脼橹甘痉?。總共占用1313個字節(jié)，而源數(shù)據(jù)占用個字節(jié)，而源數(shù)據(jù)占用2222個字節(jié)。個字節(jié)。游程編碼游程編碼也可以也可以不用指示符不用指示符: : 重復(fù)與否相同對待，相應(yīng)的重復(fù)與否相同對待，相應(yīng)的RLCRLC為為“3A4B5C1D6A3A4B5C1D6A”占用占用1010個字節(jié)。個字節(jié)。游程編碼游程編碼RLCRLC方法方法 例：例： aaaaaaaa bbbbbb cccc d d eeeeeeeeee ffffffffffffff ( (共共2222* *8=176 bit)8=

46、176 bit) 4a3b2c1d5e7f 4a3b2c1d5e7f ( (共共1212* *8=96 bit)8=96 bit) 壓縮率為：壓縮率為：176/96=1.83:1176/96=1.83:1游程編碼游程編碼 游程編碼的壓縮率不高，但編碼、解碼的速度游程編碼的壓縮率不高，但編碼、解碼的速度快，仍被得到廣泛的應(yīng)用。快，仍被得到廣泛的應(yīng)用。 特別是在特別是在變換編碼變換編碼后再進(jìn)行后再進(jìn)行游程編碼游程編碼，有很好的，有很好的效果。在效果。在圖像圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)數(shù)據(jù)壓縮標(biāo)準(zhǔn)( (JPEGJPEG) )中扮演重要中扮演重要角色。角色。 算術(shù)編碼算術(shù)編碼 算術(shù)編碼產(chǎn)生于算術(shù)編碼產(chǎn)生于2020

47、世紀(jì)世紀(jì)6060年代初年代初, ,在圖像數(shù)據(jù)在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)中算術(shù)編碼扮演了重要的角色。能有壓縮標(biāo)準(zhǔn)中算術(shù)編碼扮演了重要的角色。能有效地壓縮信源冗余度，屬于熵編碼的一種。效地壓縮信源冗余度，屬于熵編碼的一種。 該方法實現(xiàn)較為復(fù)雜，常與其它有損壓縮編該方法實現(xiàn)較為復(fù)雜，常與其它有損壓縮編碼結(jié)合使用，在碼結(jié)合使用，在視頻視頻數(shù)據(jù)壓縮標(biāo)準(zhǔn)數(shù)據(jù)壓縮標(biāo)準(zhǔn)( (如如H.263H.263) )中中扮演重要角色。扮演重要角色。 算術(shù)編碼算術(shù)編碼 算術(shù)編碼與哈夫曼編碼一樣，也是對概率較大算術(shù)編碼與哈夫曼編碼一樣，也是對概率較大的符號采用短碼，對概率較小的符號采用長碼。的符號采用短碼，對概率較小的符號采用長碼。

48、 它突破了哈夫曼編碼每個符號只能按整數(shù)比特它突破了哈夫曼編碼每個符號只能按整數(shù)比特來逼近信源熵的限制來逼近信源熵的限制: : 每個符號的平均編碼長度可以按每個符號的平均編碼長度可以按小數(shù)比特小數(shù)比特來逼來逼近信源熵。近信源熵。算術(shù)編碼基本思想算術(shù)編碼基本思想 算術(shù)編碼不是將單個信源符號映射成一個碼算術(shù)編碼不是將單個信源符號映射成一個碼字。字。 而是把而是把整個信源整個信源表示為實數(shù)線上的表示為實數(shù)線上的0 0到到1 1之間的之間的一個區(qū)間，其長度等于該一個區(qū)間，其長度等于該信源信源的概率。的概率。 再在該區(qū)間內(nèi)選擇一個代表性的小數(shù)，轉(zhuǎn)化再在該區(qū)間內(nèi)選擇一個代表性的小數(shù)，轉(zhuǎn)化為二進(jìn)制作為實際的編

49、碼輸出。為二進(jìn)制作為實際的編碼輸出。算術(shù)編碼基本步驟算術(shù)編碼基本步驟 將編碼的消息表示成實數(shù)將編碼的消息表示成實數(shù)0 0和和1 1之間的一之間的一個區(qū)間。個區(qū)間。 消息序列中的每個元素都要用來縮短這個消息序列中的每個元素都要用來縮短這個區(qū)間。區(qū)間。 消息序列中元素越多，所得到的區(qū)間就越小，消息序列中元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時，表示這一區(qū)間所需的二進(jìn)制位當(dāng)區(qū)間變小時，表示這一區(qū)間所需的二進(jìn)制位就越多。就越多。 消息結(jié)束時就最后所得到區(qū)間的下邊界值表消息結(jié)束時就最后所得到區(qū)間的下邊界值表示該消息。示該消息。 給定符號序列的算術(shù)編碼步驟如下：給定符號序列的算術(shù)編碼步驟如下： （1 1

50、）初始化：初始化： 編碼器開始時將編碼器開始時將“當(dāng)前區(qū)間當(dāng)前區(qū)間” ” 設(shè)置為一。設(shè)置為一。 為為0 0，1) 1) （2 2）按消息（按消息（符號序列符號序列）中符號的順序：）中符號的順序： 對每一符號，編碼器按步驟對每一符號，編碼器按步驟（a a）和和（b b）重復(fù)進(jìn)重復(fù)進(jìn)行處理行處理 給定符號序列的算術(shù)編碼步驟如下：給定符號序列的算術(shù)編碼步驟如下： （a a）編碼器將編碼器將“當(dāng)前區(qū)間當(dāng)前區(qū)間”分為分為子區(qū)間子區(qū)間，每一，每一個符號分配一個子區(qū)間。一個子區(qū)間的大小與個符號分配一個子區(qū)間。一個子區(qū)間的大小與符號的概率成比例。符號的概率成比例。 （b b）對應(yīng)于一個確切發(fā)生的符號，編碼器選

51、擇對應(yīng)于一個確切發(fā)生的符號，編碼器選擇其子區(qū)間，并使它成為其子區(qū)間，并使它成為新的新的“當(dāng)前區(qū)間當(dāng)前區(qū)間”。 這也稱為重新歸一化。這也稱為重新歸一化。給定符號序列的算術(shù)編碼步驟如下：給定符號序列的算術(shù)編碼步驟如下： （3 3）最后一個符號對應(yīng)有最后輸出的）最后一個符號對應(yīng)有最后輸出的“當(dāng)前區(qū)當(dāng)前區(qū)間間” ” 。 最后輸出的最后輸出的“當(dāng)前區(qū)間當(dāng)前區(qū)間”的下邊界就是該給定的的下邊界就是該給定的整個符號序列的算術(shù)編碼。整個符號序列的算術(shù)編碼。算術(shù)編碼方法算術(shù)編碼方法算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它的累積概率。的累積概率。累積概率（累積概率（下下邊

52、界值）：邊界值）： 設(shè)信源符號集為設(shè)信源符號集為 A=A=a a0 0, , a a1 1, , a a2 2, , , a am-1m-1 相應(yīng)的概率為相應(yīng)的概率為Pi Pi， i=0 i=0， 1 1， 2 2， ， m-1 m-1。 各符號的累積概率各符號的累積概率P Pr r為為: :a a0 0的累積概率為的累積概率為0 0， a a1 1的累積概率為的累積概率為P P0 0 ， a a2 2的累積的累積概率為概率為 P P0 0 + P + P1 1irirpP10算術(shù)編碼示例：算術(shù)編碼示例： 符號符號 S1 S1、 S2 S2、 S3 S3、 S4 S4 十進(jìn)制概率十進(jìn)制概率 1

53、/8 1/4 1/2 1/8 1/8 1/4 1/2 1/8 二進(jìn)制概率二進(jìn)制概率P Pi i 0.001 0.01 0.1 0.001 0.001 0.01 0.1 0.001 累積概率累積概率P Pr r 0 0.001 0.011 0.1110 0.001 0.011 0.111 0 1/8 3/8 0 1/8 3/8 7/8 7/8 1 1 0 0.001 0.011 0.111 0 0.001 0.011 0.111 1 1 現(xiàn)在以符號序列：現(xiàn)在以符號序列：s3s3 s3s3 s2s2 s4 s4 為例來解釋編碼過程為例來解釋編碼過程算術(shù)編碼的基本法則歸納如下算術(shù)編碼的基本法則歸納如

54、下: : (1) (1) 初始狀態(tài)初始狀態(tài) 區(qū)間起始點區(qū)間起始點C=0C=0, , 區(qū)間寬度區(qū)間寬度A=1.0A=1.0。 (2)(2)新區(qū)間起點新區(qū)間起點C C= =原起點原起點C+C+原區(qū)間寬度原區(qū)間寬度A AP Pr r, , 新區(qū)間寬度新區(qū)間寬度A A= =原區(qū)間寬度原區(qū)間寬度A APi Pi 其中其中P Pr r為所編符號為所編符號si si對應(yīng)的對應(yīng)的累積概率累積概率 Pi Pi為所編符號為所編符號si si對應(yīng)的對應(yīng)的概率概率。對序列對序列s3s3 s3s3 s2s2 s4s4 進(jìn)行編碼的過程如下進(jìn)行編碼的過程如下: :初始起點初始起點C=0 C=0 初始區(qū)間寬度初始區(qū)間寬度A=

55、1A=1第第1 1個符號個符號s3s3: :新區(qū)間起點：新區(qū)間起點： C C=0+1=0+10.0110.011=0.011=0.011新區(qū)間寬度新區(qū)間寬度： A A=1=10.10.1=0.1 =0.1 區(qū)間終點為區(qū)間終點為0.1110.111新的新的當(dāng)前區(qū)間當(dāng)前區(qū)間范圍為：范圍為：0.011-0.011-0.1110.111第第2 2個符號個符號s3s3: : 新區(qū)間起點：新區(qū)間起點： C C =0.011+0.1 =0.011+0.10.011=0.10010.011=0.1001新區(qū)間寬度新區(qū)間寬度： A A=0.1=0.10.10.1=0.01 =0.01 區(qū)間終點區(qū)間終點0.110

56、10.1101新的新的當(dāng)前區(qū)間當(dāng)前區(qū)間為：為：0.1001-0.1001- -0.11010.1101 第第3 3個符號個符號s2s2: : 新區(qū)間起點：新區(qū)間起點：C C=0.1001+0.01=0.1001+0.010.0010.001=0.10011=0.10011新區(qū)間寬度：新區(qū)間寬度： A A=0.01=0.010.010.01=0.0001 =0.0001 新的新的當(dāng)前區(qū)間當(dāng)前區(qū)間為：為：0.10011-0.10011- -0.101010.10101 第第4 4個符號個符號s4:s4: 新區(qū)間起點：新區(qū)間起點：C C = 0.10011+0.0001= 0.10011+0.000

57、10.1110.111= = 0.10100110.1010011新區(qū)間寬度：新區(qū)間寬度：A A = 0.0001 = 0.00010.0010.001 = 0.0000001= 0.0000001取最后符號的當(dāng)前區(qū)間的下邊界作為序列的算術(shù)編取最后符號的當(dāng)前區(qū)間的下邊界作為序列的算術(shù)編碼碼所以最終編完的碼字是所以最終編完的碼字是 0.1010011 0.1010011算數(shù)編碼的代碼長度算數(shù)編碼的代碼長度L L為多少？為多少？根據(jù)信源熵：根據(jù)信源熵：得出，算數(shù)編碼的代碼長度得出，算數(shù)編碼的代碼長度L L： N N 代表出現(xiàn)的符號數(shù)量代表出現(xiàn)的符號數(shù)量 代表代表大于大于X X的的最小最小整數(shù)。整數(shù)

58、。 代碼取其值小數(shù)點后的代碼取其值小數(shù)點后的L L位。若有尾數(shù)，就進(jìn)位位。若有尾數(shù)，就進(jìn)位到第到第L L位。位。niniiiiiSpSpSISpXH112)(log)()()()( X)(XHNL如：如： 則取則取 L= L=3 3 如果最后符號的下邊界為如果最后符號的下邊界為0.101100010.10110001 ?。喝。篶=0.11c=0.110 0 傳輸?shù)亩M(jìn)制代碼序列是傳輸?shù)亩M(jìn)制代碼序列是11110 08 . 2L剛才例題最終編完的碼字剛才例題最終編完的碼字0.10100110.1010011傳輸傳輸s3s3 s3s3 s2s2 s4s4共共4 4個符號，得個符號，得取取7 7位位

59、所以傳輸?shù)拇a流為所以傳輸?shù)拇a流為10100111010011壓縮率為：壓縮率為：4 42/7=8/7=1.14:12/7=8/7=1.14:1符號/75. 12log5 . 04log25. 08log125. 02)()()(22241bitSISpXHiii 775. 14)(XHNL算術(shù)編碼解碼過程算術(shù)編碼解碼過程 在解碼器中在解碼器中, ,當(dāng)收到碼字串當(dāng)收到碼字串0.1010.10100001111時時, , 這個碼字串指向子區(qū)間這個碼字串指向子區(qū)間0.011,0.011, 0.111)0.111), , 解出的第一個符號應(yīng)為解出的第一個符號應(yīng)為s3s3 0 0.001 0.011 0

60、 0.001 0.011 0.111 0.111 1.01.0 算術(shù)編碼解碼過程算術(shù)編碼解碼過程 之后之后采取與編碼過程相反的步驟：采取與編碼過程相反的步驟： 即即：從碼字串中減去從碼字串中減去已解符號已解符號的的累積概率累積概率, ,并將并將差差值值除以除以概率值概率值, ,則得到新碼字串。則得到新碼字串。 (0.10100111(0.10100111- -0.011)0.011)(0.1)=(0.1)=0.1000110.100011。 新碼字串仍落在新碼字串仍落在0.011,0.111)0.011,0.111)區(qū)間之內(nèi)區(qū)間之內(nèi), , 解出的第解出的第2 2個符號仍為個符號仍為s3s3。