第6章 圖像編碼與壓縮

1、第第6章章 圖像編碼與壓縮圖像編碼與壓縮第2頁第6章 圖像編碼與壓縮動機(jī)動機(jī)/原因：表達(dá)數(shù)字圖像所需數(shù)據(jù)量通常很大。原因：表達(dá)數(shù)字圖像所需數(shù)據(jù)量通常很大。圖像編碼壓縮：圖像編碼壓縮：n采用對圖像的新的表達(dá)方法以減小所需的數(shù)據(jù)量。采用對圖像的新的表達(dá)方法以減小所需的數(shù)據(jù)量。n數(shù)據(jù)和信息：數(shù)據(jù)是信息的載體數(shù)據(jù)和信息：數(shù)據(jù)是信息的載體對給定量的信息可用不同的數(shù)據(jù)量來表示對給定量的信息可用不同的數(shù)據(jù)量來表示 對給定量的信息，設(shè)法減少表達(dá)這些信息的數(shù)對給定量的信息，設(shè)法減少表達(dá)這些信息的數(shù)據(jù)量稱為數(shù)據(jù)壓縮。據(jù)量稱為數(shù)據(jù)壓縮。6.1 概述概述第3頁第6章 圖像編碼與壓縮n圖像壓縮方法的分類圖像壓縮方法的分

2、類 ：無損壓縮：無損壓縮：在壓縮和解壓縮過程中沒有信息損失；在壓縮和解壓縮過程中沒有信息損失；有損壓縮：有損壓縮： 圖像壓縮后并不能經(jīng)解壓縮精確復(fù)原。圖像壓縮后并不能經(jīng)解壓縮精確復(fù)原。第4頁第6章 圖像編碼與壓縮圖像壓縮技術(shù)圖像壓縮技術(shù)有損壓縮有損壓縮無損壓縮無損壓縮霍夫曼編碼霍夫曼編碼算術(shù)編碼算術(shù)編碼行程編碼行程編碼其他編碼其他編碼預(yù)測編碼預(yù)測編碼變換編碼變換編碼第5頁第6章 圖像編碼與壓縮6.2 圖像保真度準(zhǔn)則圖像保真度準(zhǔn)則n圖像保真度圖像保真度 描述解碼圖像相對于原始圖像的偏離程度的測度描述解碼圖像相對于原始圖像的偏離程度的測度n主觀保真度準(zhǔn)則主觀保真度準(zhǔn)則 主觀測量圖像的質(zhì)量，因人而異

3、。主觀測量圖像的質(zhì)量，因人而異。n客觀保真度準(zhǔn)則客觀保真度準(zhǔn)則 原圖像與解碼圖像之間的均方根誤差和均方根信噪比。原圖像與解碼圖像之間的均方根誤差和均方根信噪比。第6頁第6章 圖像編碼與壓縮1. 客觀保真度準(zhǔn)則客觀保真度準(zhǔn)則 均方根誤差均方根誤差 均方根信噪比均方根信噪比),(),(),(yxfyxfyxe 21 10102 rms),(),( 1 MxNyyxfyxfMNe 10102 10102),(),( ),( MxNyMxNymsyxfyxfyxfSNR第7頁第6章 圖像編碼與壓縮（歸一化）信噪比（歸一化）信噪比：令令 單位：分貝（單位：分貝（dB） 峰值信噪比峰值信噪比 1010),

4、( 1MxNyyxfMNf 10102 10102 ),(),( ),( lg10MxNyMxNyyxfyxffyxfSNR),(max),(),(lg10max10102 2maxyxffyxfyxffPSNRMxNy第8頁第6章 圖像編碼與壓縮2. 主觀保真度準(zhǔn)則主觀保真度準(zhǔn)則觀察者對圖像綜合評價的平均觀察者對圖像綜合評價的平均 電視圖像質(zhì)量評價尺度電視圖像質(zhì)量評價尺度評分評價說 明1優(yōu)秀圖象質(zhì)量非常好，如同人能想象出的最好質(zhì)量。2良好圖象質(zhì)量高，觀看舒服，有干擾但不影響觀看。3可用圖象質(zhì)量可接受，有干擾但不太影響觀看。4剛可看圖象質(zhì)量差，干擾有些妨礙觀看，觀察者希望改進(jìn)。5差圖象質(zhì)量很差

5、，妨礙觀看的干擾始終存在，幾乎無法觀看。6不能用圖象質(zhì)量極差，不能使用。第9頁第6章 圖像編碼與壓縮 6.6.3 3 統(tǒng)計編碼方法統(tǒng)計編碼方法 建立在圖像統(tǒng)計特性基礎(chǔ)上的壓縮編碼方法建立在圖像統(tǒng)計特性基礎(chǔ)上的壓縮編碼方法第10頁第6章 圖像編碼與壓縮6.3.1 圖像冗余度和編碼效率圖像冗余度和編碼效率n 數(shù)據(jù)冗余的概念數(shù)據(jù)冗余的概念數(shù)據(jù)是信息的載體數(shù)據(jù)是信息的載體同量的數(shù)據(jù)可表達(dá)不同量的信息同量的數(shù)據(jù)可表達(dá)不同量的信息同量的信息可用不同量的數(shù)據(jù)表達(dá)同量的信息可用不同量的數(shù)據(jù)表達(dá)冗余冗余數(shù)據(jù)表達(dá)了無用的信息數(shù)據(jù)表達(dá)了無用的信息數(shù)據(jù)表達(dá)了已表達(dá)的信息數(shù)據(jù)表達(dá)了已表達(dá)的信息第11頁第6章 圖像編碼與

6、壓縮信源信息熵信源信息熵 102log)(LiiippxH各灰度像素出現(xiàn)的概率與該概率的對數(shù)的乘積再求和。各灰度像素出現(xiàn)的概率與該概率的對數(shù)的乘積再求和。灰度范圍灰度范圍0，L-1第12頁第6章 圖像編碼與壓縮平均碼長平均碼長 為數(shù)字圖像中灰度級為為數(shù)字圖像中灰度級為i i對應(yīng)的碼長。對應(yīng)的碼長。10LiiipBBi理論上，最佳信息保持編碼的平均長度與信源的熵理論上，最佳信息保持編碼的平均長度與信源的熵H無限接近。無限接近。第13頁第6章 圖像編碼與壓縮rBH 11 1 HBr冗余度冗余度定義為：定義為：編碼效率：編碼效率：編碼效率接近于編碼效率接近于1 1的編碼稱為的編碼稱為高效編碼高效編碼

7、。第14頁第6章 圖像編碼與壓縮設(shè)有編碼輸入設(shè)有編碼輸入X=x1,x2,x3,x4,x5,x6，其頻率分布分別為其頻率分布分別為P(x1)=0.4，P(x2)=0.3，P(x3)=0.1，P(x4)=0.1, P(x5)=0.06, P(x6)=0.04求其霍夫曼編碼。求其霍夫曼編碼。第15頁第6章 圖像編碼與壓縮霍夫曼編碼步驟霍夫曼編碼步驟(1) 將輸入元素按出現(xiàn)概率從大到小排列，然后選將輸入元素按出現(xiàn)概率從大到小排列，然后選2個最小的結(jié)個最小的結(jié)合合第16頁第6章 圖像編碼與壓縮霍夫曼編碼步驟霍夫曼編碼步驟 (2)對每個信源符號賦值：概率大的賦對每個信源符號賦值：概率大的賦0，概率小的賦，

8、概率小的賦1.從（消減到）最小的信源開始，逐步回到初始信源從（消減到）最小的信源開始，逐步回到初始信源大值賦給單大值賦給單獨(dú)一個元獨(dú)一個元素素第17頁第6章 圖像編碼與壓縮霍夫曼編碼結(jié)果霍夫曼編碼結(jié)果平均長度平均長度信源熵信源熵 編碼效率編碼效率2 . 251 . 031 . 023 . 014 . 0)()(10 LkkskspsBB142)()log()(1.uJjjjaPaPH973. 02 . 214. 2)u( BH 第18頁第6章 圖像編碼與壓縮n樹的形式：樹的形式：葉子節(jié)點葉子節(jié)點根節(jié)點根節(jié)點第19頁第6章 圖像編碼與壓縮霍夫曼編碼需要多次排列，當(dāng)元素個數(shù)很多時十分不便?；舴蚵?/p>

9、碼需要多次排列，當(dāng)元素個數(shù)很多時十分不便。費(fèi)諾費(fèi)諾-仙農(nóng)編碼仙農(nóng)編碼主要步驟為：主要步驟為：(1) 將元素依其概率從大到小排列；將元素依其概率從大到小排列；(2) 將元素分成概率和接近的兩部分；將元素分成概率和接近的兩部分；(3) 分別給兩部分的元素組合賦值，概率大的賦分別給兩部分的元素組合賦值，概率大的賦0，反之賦，反之賦1；(4) 如果兩部分均只有一個元素，編碼結(jié)束，否則返回如果兩部分均只有一個元素，編碼結(jié)束，否則返回(2)繼繼續(xù)進(jìn)行。續(xù)進(jìn)行。第20頁第6章 圖像編碼與壓縮第21頁第6章 圖像編碼與壓縮n由于計算機(jī)硬件限制使得編碼只能按位進(jìn)行，在一些由于計算機(jī)硬件限制使得編碼只能按位進(jìn)行，

10、在一些情況下，實際編碼效果達(dá)不到理論壓縮比。情況下，實際編碼效果達(dá)不到理論壓縮比。n算術(shù)編碼算術(shù)編碼基本思想基本思想將要壓縮的數(shù)據(jù)映射到將要壓縮的數(shù)據(jù)映射到0,1)0,1)實數(shù)區(qū)間中的某一區(qū)段，構(gòu)造實數(shù)區(qū)間中的某一區(qū)段，構(gòu)造出小于出小于1 1且大于等于且大于等于0 0的數(shù)值。的數(shù)值。第22頁第6章 圖像編碼與壓縮 例：對符號序列例：對符號序列a1a2a3a2a4進(jìn)行算術(shù)編碼進(jìn)行算術(shù)編碼 1）各符號出現(xiàn)的概率）各符號出現(xiàn)的概率)0 . 1 , 8 . 02 . 04)8 . 0 , 4 . 04 . 02)4 . 0 , 2 . 02 . 01)2 . 0 , 0 . 02 . 03aaaa范圍

11、范圍概率概率字符字符2）根據(jù)符號發(fā)生的概率劃分區(qū)間）根據(jù)符號發(fā)生的概率劃分區(qū)間0,1)為為4段段01a3a1a4a2第23頁第6章 圖像編碼與壓縮（3)3)在編碼運(yùn)算過程中，隨著消息符號的出現(xiàn)，子區(qū)按下列規(guī)則縮小：在編碼運(yùn)算過程中，隨著消息符號的出現(xiàn)，子區(qū)按下列規(guī)則縮?。海? 4）初始子區(qū)為）初始子區(qū)為0.2 0.40.2 0.4），編碼），編碼過程過程序號序號子區(qū)左端子區(qū)左端子區(qū)長度子區(qū)長度 范圍范圍a10.20.2 0.2, 0.4)a20.2+0.4*0.2=0.280.08 0.28, 0.36)a30.28+0*0.2=0.280.016 0.28, 0.296)a2a40.28+0

12、.4*0.016=0.28640.2864+0.8*0.0064=0.29150.0064 0.2864, 0.2928)0.00128 0.2915, 0.2928)n規(guī)則規(guī)則A：新子區(qū)左端前子區(qū)左端十當(dāng)前子區(qū)左端：新子區(qū)左端前子區(qū)左端十當(dāng)前子區(qū)左端前子區(qū)長度前子區(qū)長度n規(guī)則規(guī)則B：新子區(qū)長度前子區(qū)長度：新子區(qū)長度前子區(qū)長度當(dāng)前子區(qū)的長度當(dāng)前子區(qū)的長度)4 . 0 , 2 . 02 . 01)2 . 0 , 0 . 02 . 03aa)0 . 1 , 8 . 02 . 04)8 . 0 , 4 . 04 . 02aa第24頁第6章 圖像編碼與壓縮行程編碼簡介行程編碼簡介（Run Length

13、 EncodingRun Length Encoding）又稱又稱“運(yùn)行長度編碼運(yùn)行長度編碼”或或“游程編碼游程編碼”，是一種統(tǒng)計編碼，該，是一種統(tǒng)計編碼，該編碼屬于無損壓縮編碼。編碼屬于無損壓縮編碼。行程編碼原理行程編碼原理用一個符號值代替具有相同值的連續(xù)符號，使符號長度少于原用一個符號值代替具有相同值的連續(xù)符號，使符號長度少于原始數(shù)據(jù)的長度。始數(shù)據(jù)的長度。對一個字符串對一個字符串a(chǎn)aabbbbccccdddedddaaaaabbbbccccdddedddaa進(jìn)行行程編進(jìn)行行程編碼。碼。 3a4b4c3d1e3d2a3a4b4c3d1e3d2a編碼舉例編碼舉例第25頁第6章 圖像編碼與壓縮(

14、a) (b) 二維二維二維行程編碼要解決的核心問題是二維行程編碼要解決的核心問題是: : 將二維排列的像素，采用某種方式轉(zhuǎn)化成一維將二維排列的像素，采用某種方式轉(zhuǎn)化成一維排列的方式。之后按照一維行程編碼方式進(jìn)行編碼。排列的方式。之后按照一維行程編碼方式進(jìn)行編碼。第26頁第6章 圖像編碼與壓縮6.4 預(yù)測編碼預(yù)測編碼n預(yù)測就是根據(jù)過去時刻的樣本序列，運(yùn)用一種模型預(yù)測當(dāng)前預(yù)測就是根據(jù)過去時刻的樣本序列，運(yùn)用一種模型預(yù)測當(dāng)前的樣本值。的樣本值。n基本思想基本思想 提取每個像素中的新信息（實際值與預(yù)測值的差）并對它提取每個像素中的新信息（實際值與預(yù)測值的差）并對它們編碼。們編碼。238, 240, 2

15、40, 241, 242, 245 238,2,0,1,1,3第27頁第6章 圖像編碼與壓縮二、線性預(yù)測（二、線性預(yù)測（DPCMDPCM差分脈沖編碼調(diào)制差分脈沖編碼調(diào)制 ）像素點的實際灰度值：像素點的實際灰度值：Nx像素點的預(yù)測灰度值：像素點的預(yù)測灰度值：NxNNNxxe-預(yù)測誤差：預(yù)測誤差：Differential Pulse Code Modulation 第28頁第6章 圖像編碼與壓縮差分預(yù)測編碼原理差分預(yù)測編碼原理輸入序列進(jìn)入系統(tǒng)時，先與預(yù)測值相減，得到預(yù)測誤差值，經(jīng)輸入序列進(jìn)入系統(tǒng)時，先與預(yù)測值相減，得到預(yù)測誤差值，經(jīng)過量化器量化成數(shù)字序列，經(jīng)信道傳送。并且將誤差作為預(yù)測過量化器量化

16、成數(shù)字序列，經(jīng)信道傳送。并且將誤差作為預(yù)測器的下一次輸入。器的下一次輸入。第29頁第6章 圖像編碼與壓縮NNNxxe-NNNxex NNNNNNNNeexxexxx Nx 輸出端恢復(fù)的輸出信號輸出端恢復(fù)的輸出信號量化器對eN進(jìn)行量化得到eN 為根據(jù)為根據(jù)t tN N時刻以前已知的像素亮度取樣值時刻以前已知的像素亮度取樣值X X1 1，X X2 2，X XN-1 N-1 對對X XN N所作的預(yù)測值；所作的預(yù)測值；NxNe為差值信號，也稱誤差信號；為差值信號，也稱誤差信號；第30頁第6章 圖像編碼與壓縮6.5.1 變換編碼（變換編碼（Transform Coding）原理）原理圖像分解：減少變換

17、的計算復(fù)雜度圖像分解：減少變換的計算復(fù)雜度圖像變換：解除每個子圖像內(nèi)部像素之間的相關(guān)性，或者說圖像變換：解除每個子圖像內(nèi)部像素之間的相關(guān)性，或者說將盡可能多的信息集中到盡可能少的變換系數(shù)上將盡可能多的信息集中到盡可能少的變換系數(shù)上壓縮不是在變換中而是在量化變換系數(shù)時及編碼取得的壓縮不是在變換中而是在量化變換系數(shù)時及編碼取得的輸入圖象壓縮圖象解壓圖象正變換量化符號編碼符號解碼反變換構(gòu)造子圖象合并子圖象壓縮圖象第31頁第6章 圖像編碼與壓縮n正交變換是線性變換，且變換前后能量不變正交變換是線性變換，且變換前后能量不變(Parseval定理定理)n熵保持熵保持n重新分配能量重新分配能量n去相關(guān)性質(zhì)去

18、相關(guān)性質(zhì)6.5.2 正交變換的特點正交變換的特點第32頁第6章 圖像編碼與壓縮平穩(wěn)隨機(jī)向量平穩(wěn)隨機(jī)向量X，Y 的協(xié)方差矩陣定義為（注意它的的協(xié)方差矩陣定義為（注意它的對稱性和半正定性）對稱性和半正定性）AXY TnxxxX,21 TnyyyY,21 )(TxXXXXE TxTTTTyAAAXXXXAEXAAXXAAXEYYYYE )()()(第33頁第6章 圖像編碼與壓縮設(shè)設(shè) 是一個是一個 維的隨機(jī)向量，則它可以用下式無誤維的隨機(jī)向量，則它可以用下式無誤差的展開：差的展開：xn111121112221211212( ) ( )ni iinnnnnnTnyy yy xyy=ATy12 TTTmA

19、=第34頁第6章 圖像編碼與壓縮 是線性獨(dú)立的，其構(gòu)成了包含是線性獨(dú)立的，其構(gòu)成了包含 的的 維空間，維空間，這些向量就是這個空間的一個基組。進(jìn)一步它還滿足以這些向量就是這個空間的一個基組。進(jìn)一步它還滿足以下性質(zhì)：下性質(zhì)：假定我們只保留假定我們只保留 向量的分量的一個子集向量的分量的一個子集 ， 就用這些分量估計出就用這些分量估計出 。n12, , nx12, , myyyym nx1 1,2,1, 0, ,TTiTiijTyiiijnj xy yxxxI=Ax第35頁第6章 圖像編碼與壓縮 最佳子集的選取最佳子集的選取 若用若用y y的分量來恢復(fù)原始模式的分量來恢復(fù)原始模式x，不應(yīng)使模式產(chǎn)生

20、明顯的，不應(yīng)使模式產(chǎn)生明顯的畸變。實際上我們的任務(wù)就是要選擇一個最佳的變換使畸變。實際上我們的任務(wù)就是要選擇一個最佳的變換使得模式向量的維數(shù)降低后仍能保留模式的最重要的特征。得模式向量的維數(shù)降低后仍能保留模式的最重要的特征。若保留若保留 ，不保留的用預(yù)先選定的常數(shù)來代，不保留的用預(yù)先選定的常數(shù)來代替，這時對替，這時對x的估計值為：的估計值為：12, , myyy1111111()mni ii iii mni iinmnni ii ii iiiiiii mi mybyyybyb xxxx x第36頁第6章 圖像編碼與壓縮2221() ()()nTiii mEEEyb xx xx x 222()(

21、2)20iiii iiiiiiiiTiiTiiiEybEyy bbE ybbbbE yybE yExx注意到注意到x和和 都是隨機(jī)向量，用都是隨機(jī)向量，用 的均方誤差作為選的均方誤差作為選取取m個特征的子集的有效性的判據(jù)，則個特征的子集的有效性的判據(jù)，則 是是 和和 的函數(shù)，要使的函數(shù)，要使 最小，就是求使最小，就是求使 取極小值的最佳的取極小值的最佳的 和和 的值。的值。對對 的選擇的選擇xx2ibi22ibiib第37頁第6章 圖像編碼與壓縮 221211()( )( )niii mTiiiTiinnTTTiiiii mi mEyE ybE yEyEEE xxxxxxxi1Tii 1Tii 2i第38頁第6章 圖像編碼與壓縮2111(1)(1)12nnnTTTiiiiiiii mi mi mLi xi220 ii iii iiL xxixi2111nnnTTiiii iii mi mi m xii 第39頁第6章 圖像編碼與壓縮12mn12 TTTmA=第40頁第6