圖片處理技術(shù)4

1、本章重點(diǎn)：本章重點(diǎn)：圖像編碼與壓縮的基本概念、理論及其編碼分圖像編碼與壓縮的基本概念、理論及其編碼分類(lèi)。類(lèi)。常用的無(wú)損壓縮方法。常用的無(wú)損壓縮方法。常用的有損壓縮方法。常用的有損壓縮方法。第第4章章 圖像編碼與壓縮圖像編碼與壓縮4.1 圖像編碼的必要性與可能性圖像編碼的必要性與可能性 4.2 圖像編碼分類(lèi)圖像編碼分類(lèi) 4.3 圖像編碼評(píng)價(jià)準(zhǔn)則圖像編碼評(píng)價(jià)準(zhǔn)則 4.4 圖像編碼模型圖像編碼模型 4.5 無(wú)損壓縮無(wú)損壓縮 4.6 有損壓縮有損壓縮 4.7 JPEG圖像編碼壓縮標(biāo)準(zhǔn)圖像編碼壓縮標(biāo)準(zhǔn) 4.8 MPEG視頻編碼壓縮標(biāo)準(zhǔn)視頻編碼壓縮標(biāo)準(zhǔn) 4.9 小結(jié)小結(jié)第第4章章 圖像編碼與壓縮圖像編碼與

2、壓縮4.1 圖像編碼的必要性與可能性圖像編碼的必要性與可能性4.1.1圖像編碼的必要性圖像編碼的必要性 數(shù)字圖像的龐大數(shù)據(jù)對(duì)計(jì)算機(jī)的處理速度、存儲(chǔ)容量都提數(shù)字圖像的龐大數(shù)據(jù)對(duì)計(jì)算機(jī)的處理速度、存儲(chǔ)容量都提出過(guò)高的要求。因此必須把數(shù)據(jù)量壓縮。出過(guò)高的要求。因此必須把數(shù)據(jù)量壓縮。 各種媒體信息(特別是動(dòng)態(tài)視頻)數(shù)據(jù)量非常之大。 以一幅10241024分辨率的24位真彩色圖像為例，數(shù)據(jù)量為： 1024 1024 8 3/8=3MB； 若以30幀/秒播放，每秒數(shù)據(jù)量為： 3 30=90MB 陸地衛(wèi)星LandSat-3分辨率為2340 3240，四波段，采樣精度7位，則一幅圖像的數(shù)據(jù)量為： 2340 3

3、240 7 4=212Mb 按每天傳輸30幅計(jì),每天數(shù)據(jù)量為: 21230=6.36Gb=795MB 可見(jiàn)，沒(méi)有圖像編碼與壓縮技術(shù)的發(fā)展，大容量圖像信息的存儲(chǔ)與傳輸是難以實(shí)現(xiàn)的。 從傳送圖像的角度來(lái)看，則更要求數(shù)據(jù)量壓縮。在信從傳送圖像的角度來(lái)看，則更要求數(shù)據(jù)量壓縮。在信道帶寬、通信鏈路容量一定的前提下，采用編碼壓縮道帶寬、通信鏈路容量一定的前提下，采用編碼壓縮技術(shù)，減少傳輸數(shù)據(jù)量，是提高通信速度的重要手段技術(shù)，減少傳輸數(shù)據(jù)量，是提高通信速度的重要手段 。4.1.2圖像編碼的可能性圖像編碼的可能性 圖像、聲音這些媒體確實(shí)又具有很大的圖像、聲音這些媒體確實(shí)又具有很大的壓縮潛力。壓縮潛力。 以目前

4、常用的位圖格式的圖像存儲(chǔ)方以目前常用的位圖格式的圖像存儲(chǔ)方式為例，像素與像素之間無(wú)論是在行方式為例，像素與像素之間無(wú)論是在行方向還是在列方向都具有很大的相關(guān)性，向還是在列方向都具有很大的相關(guān)性，因而整體上數(shù)據(jù)的冗余度很大，在允許因而整體上數(shù)據(jù)的冗余度很大，在允許一定限度失真的前提下，能夠?qū)D像數(shù)一定限度失真的前提下，能夠?qū)D像數(shù)據(jù)進(jìn)行很大程度的壓縮。據(jù)進(jìn)行很大程度的壓縮。 這里所說(shuō)的失真一般都是在人眼允許的誤差范圍之內(nèi)，壓縮前后的圖像如果不做非常細(xì)致的對(duì)比是很難覺(jué)察出兩者的差別的。因此，數(shù)據(jù)壓縮技術(shù)是多媒體系統(tǒng)中一項(xiàng)十分關(guān)鍵的技術(shù)。 數(shù)據(jù)之所以能夠壓縮是基于原始信源的數(shù)據(jù)存在著很大的冗余度。

5、圖像數(shù)據(jù)冗余圖像數(shù)據(jù)冗余q 空間冗余q 時(shí)間冗余q 結(jié)構(gòu)冗余q 知識(shí)冗余q 視覺(jué)冗余q 圖像區(qū)域的相同性冗余q 紋理的統(tǒng)計(jì)冗余空間冗余空間冗余 同一景物表面上各采樣點(diǎn)之間的顏色（亮度）之間往往存在著空間相關(guān)性。 基于離散象素的表示方式通常沒(méi)有利用景物表面顏色（亮度）的這種空間相關(guān)性，從而產(chǎn)生了空間冗余。 大部分區(qū)域所有像大部分區(qū)域所有像素值相同。素值相同。時(shí)間冗余時(shí)間冗余 主要指視頻相鄰幀之間的冗余。 結(jié)構(gòu)冗余結(jié)構(gòu)冗余 有些圖像的紋理區(qū)，圖象像素值之間存在著明顯的分布模式，稱(chēng)之為結(jié)構(gòu)冗余。知識(shí)冗余知識(shí)冗余 某些圖像的理解與某些知識(shí)有相當(dāng)大的相關(guān)性。如人臉有固定的結(jié)構(gòu)。視覺(jué)冗余視覺(jué)冗余 人的視覺(jué)

6、系統(tǒng)對(duì)圖像場(chǎng)的敏感性是非均勻和非線(xiàn)性的，然而，在記錄原始圖像數(shù)據(jù)時(shí)，通常假定視覺(jué)系統(tǒng)是線(xiàn)性的和均勻的，對(duì)視覺(jué)敏感和不敏感部分同等對(duì)待，從而產(chǎn)生視覺(jué)冗余。 如對(duì)亮度和色彩的敏感度不同。圖像區(qū)域的相同性冗余圖像區(qū)域的相同性冗余 指在圖像中的兩個(gè)或?qū)?yīng)的所有像素相同或相近，從而產(chǎn)生的數(shù)據(jù)重復(fù)性存儲(chǔ)，即圖像區(qū)域的相似性冗余。 紋理的統(tǒng)計(jì)冗余紋理的統(tǒng)計(jì)冗余 圖像紋理在統(tǒng)計(jì)意義上服從某一分布規(guī)律。利用這種性質(zhì)可以減少表示圖像的數(shù)據(jù)量。4.2圖像編碼分類(lèi)圖像編碼分類(lèi) 根據(jù)解壓重建后的圖像和原始圖像之間是否具有誤差，根據(jù)解壓重建后的圖像和原始圖像之間是否具有誤差，可以將圖像編碼與壓縮方法分為無(wú)誤差可以將圖像編

7、碼與壓縮方法分為無(wú)誤差(亦稱(chēng)無(wú)失真、亦稱(chēng)無(wú)失真、無(wú)損、信息保持無(wú)損、信息保持)編碼和有誤差編碼和有誤差(有失真或有損有失真或有損)編碼兩編碼兩大類(lèi)。大類(lèi)。 根據(jù)編碼作用域劃分，圖像編碼分為空間域編碼和變根據(jù)編碼作用域劃分，圖像編碼分為空間域編碼和變換域編碼兩大類(lèi)。換域編碼兩大類(lèi)。 若從具體編碼技術(shù)來(lái)考慮，又可分為預(yù)測(cè)編碼、變換若從具體編碼技術(shù)來(lái)考慮，又可分為預(yù)測(cè)編碼、變換編碼、統(tǒng)計(jì)編碼、輪廓編碼、模型編碼等。編碼、統(tǒng)計(jì)編碼、輪廓編碼、模型編碼等。多媒體數(shù)據(jù)編碼多媒體數(shù)據(jù)編碼 脈沖編碼調(diào)制(PCM) 預(yù)測(cè)編碼 變換編碼 統(tǒng)計(jì)編碼（熵編碼） 混合編碼 靜態(tài)圖像編碼 動(dòng)態(tài)圖像編碼 其他編碼4.3 圖

8、像編碼評(píng)價(jià)準(zhǔn)則圖像編碼評(píng)價(jià)準(zhǔn)則 在圖像壓縮編碼中，解碼圖像與原始圖像可能會(huì)有差在圖像壓縮編碼中，解碼圖像與原始圖像可能會(huì)有差異，因此，需要評(píng)價(jià)壓縮后圖像的質(zhì)量。異，因此，需要評(píng)價(jià)壓縮后圖像的質(zhì)量。 描述解碼圖像相對(duì)原始圖像偏離程度的測(cè)度一般稱(chēng)為描述解碼圖像相對(duì)原始圖像偏離程度的測(cè)度一般稱(chēng)為保真度保真度(逼真度逼真度)準(zhǔn)則。準(zhǔn)則。 常用的準(zhǔn)則可分為兩大類(lèi)：客觀保真度準(zhǔn)則和主觀保常用的準(zhǔn)則可分為兩大類(lèi)：客觀保真度準(zhǔn)則和主觀保真度準(zhǔn)則。真度準(zhǔn)則。4.3.1 客觀保真度準(zhǔn)則客觀保真度準(zhǔn)則 最常用的客觀保真度準(zhǔn)則是原圖像和解碼圖像之間的最常用的客觀保真度準(zhǔn)則是原圖像和解碼圖像之間的均方根誤差和均方根信噪

9、比兩種。均方根誤差和均方根信噪比兩種。 均方根誤差均方根誤差 : :1 2211001( , )( , )MNrmsxyef x yf x yMN均方信噪比均方信噪比: : 2111120000( , )( , )( , )MNMNmsxyxySNRf x yf x yf x y對(duì)上式求平方根，就得到均方根信噪比。對(duì)上式求平方根，就得到均方根信噪比。 （4-2） （4-3） 4.3.2主觀保真度準(zhǔn)則主觀保真度準(zhǔn)則 具有相同客觀保真度的不同圖像，人的視覺(jué)可能產(chǎn)生具有相同客觀保真度的不同圖像，人的視覺(jué)可能產(chǎn)生不同的視覺(jué)效果。這是因?yàn)榭陀^保真度是一種統(tǒng)計(jì)平不同的視覺(jué)效果。這是因?yàn)榭陀^保真度是一種統(tǒng)計(jì)

10、平均意義下的度量準(zhǔn)則，對(duì)于圖像中的細(xì)節(jié)無(wú)法反映出均意義下的度量準(zhǔn)則，對(duì)于圖像中的細(xì)節(jié)無(wú)法反映出來(lái)。來(lái)。 一種常用的方法是對(duì)一組一種常用的方法是對(duì)一組(不少于不少于20人人)觀察者顯示圖像，觀察者顯示圖像，并將他們對(duì)該圖像的評(píng)分取平均，用來(lái)評(píng)價(jià)一幅圖像并將他們對(duì)該圖像的評(píng)分取平均，用來(lái)評(píng)價(jià)一幅圖像的主觀質(zhì)量。的主觀質(zhì)量。 例如可用例如可用-3-3，-2-2，-1-1，0 0 ，1 1，2 2，33來(lái)代表主觀評(píng)價(jià)來(lái)代表主觀評(píng)價(jià) 很差，很差，較差，稍差，相同，稍好，較好，很好較差，稍差，相同，稍好，較好，很好 。評(píng)分評(píng)價(jià)說(shuō)明1優(yōu)秀圖像質(zhì)量非常好，如同人能想象出的最好質(zhì)量2良好圖像質(zhì)量高，觀看舒服，有

11、干擾但不影響觀看3可用圖像質(zhì)量可以接受，有干擾但不太影響觀看4剛可看圖像質(zhì)量差，干擾有些妨礙觀看，觀察者希望改進(jìn)5差圖像質(zhì)量很差，幾乎無(wú)法觀看6不能用圖像質(zhì)量極差，不能使用表表4.1 4.1 電視圖像質(zhì)量評(píng)價(jià)尺度電視圖像質(zhì)量評(píng)價(jià)尺度4.4 圖像編碼模型圖像編碼模型 一個(gè)圖像壓縮系統(tǒng)包括兩個(gè)不同的結(jié)構(gòu)塊：一個(gè)圖像壓縮系統(tǒng)包括兩個(gè)不同的結(jié)構(gòu)塊： 編碼器和解碼器。編碼器和解碼器。 圖像圖像f（x，y）輸入到編碼器中，編碼器可以根據(jù)輸入）輸入到編碼器中，編碼器可以根據(jù)輸入數(shù)據(jù)生成一組符號(hào)。在通過(guò)信道進(jìn)行傳輸之后，將經(jīng)數(shù)據(jù)生成一組符號(hào)。在通過(guò)信道進(jìn)行傳輸之后，將經(jīng)過(guò)編碼的表達(dá)符號(hào)送入解碼器，經(jīng)過(guò)重構(gòu)后，

12、生成輸過(guò)編碼的表達(dá)符號(hào)送入解碼器，經(jīng)過(guò)重構(gòu)后，生成輸出圖像。出圖像。 f(x,y)信源編碼信道編碼信道信道解碼信源解碼f(x,y)一個(gè)常用于圖像壓縮系統(tǒng)模型一個(gè)常用于圖像壓縮系統(tǒng)模型4.4.1信源編碼器和信源解碼器信源編碼器和信源解碼器 信源編碼器的任務(wù)是減少或消除輸入圖像中的編碼冗信源編碼器的任務(wù)是減少或消除輸入圖像中的編碼冗余、像素間冗余或心理視覺(jué)冗余。余、像素間冗余或心理視覺(jué)冗余。 從原理來(lái)看主要分為三個(gè)階段從原理來(lái)看主要分為三個(gè)階段:v 第一階段將輸入數(shù)據(jù)轉(zhuǎn)換為可以減少輸入圖像中像素第一階段將輸入數(shù)據(jù)轉(zhuǎn)換為可以減少輸入圖像中像素間冗余的數(shù)據(jù)的集合。間冗余的數(shù)據(jù)的集合。v 第二階段設(shè)法去

13、除原圖像信號(hào)的相關(guān)性第二階段設(shè)法去除原圖像信號(hào)的相關(guān)性 。v 第三階段是找一種更近于熵，又利于計(jì)算機(jī)處理的編第三階段是找一種更近于熵，又利于計(jì)算機(jī)處理的編碼方式碼方式 。 信源解碼器包含兩部分：符號(hào)解碼器和反向轉(zhuǎn)換器。信源解碼器包含兩部分：符號(hào)解碼器和反向轉(zhuǎn)換器。編碼器模型編碼器模型 f(x,y)轉(zhuǎn)換器量化器 符號(hào)編碼器信道信道符 號(hào) 解 碼器反 向 轉(zhuǎn) 換器f(x,y)（a）信源編碼器）信源編碼器（b）信源解碼器）信源解碼器4.4.2信道編碼器和解碼器信道編碼器和解碼器 當(dāng)信道帶有噪聲或易于出現(xiàn)錯(cuò)誤時(shí)，信道編碼器和解當(dāng)信道帶有噪聲或易于出現(xiàn)錯(cuò)誤時(shí)，信道編碼器和解碼器就在整個(gè)譯碼解碼處理中扮演

14、了重要的角色。信碼器就在整個(gè)譯碼解碼處理中扮演了重要的角色。信道編碼器和解碼器通過(guò)向信源編碼數(shù)據(jù)中插入預(yù)制的道編碼器和解碼器通過(guò)向信源編碼數(shù)據(jù)中插入預(yù)制的冗余數(shù)據(jù)來(lái)減少信道噪聲的影響。冗余數(shù)據(jù)來(lái)減少信道噪聲的影響。 最有用的一種信道編碼技術(shù)是由最有用的一種信道編碼技術(shù)是由RwHamming提提出的。這種技術(shù)是基于這樣的思想，即向被編碼數(shù)據(jù)出的。這種技術(shù)是基于這樣的思想，即向被編碼數(shù)據(jù)中加入足夠的位數(shù)以確保可用的碼字間變化的位數(shù)最中加入足夠的位數(shù)以確?？捎玫拇a字間變化的位數(shù)最小。小。 信源編碼器與信源解碼器信源編碼器與信源解碼器信源編碼器的任務(wù)是減少或消除圖象中的編碼冗余、像素間冗余或心理視覺(jué)冗

15、余。映射映射 映射的目的是使原信號(hào)經(jīng)過(guò)映射后更有利于編碼，既映射后的數(shù)據(jù)可用較少的比特來(lái)編碼。 如DPCM中的差分。量化器量化器 把映射后的值進(jìn)行量化。 可以有均勻量化和非均勻量化。數(shù)據(jù)壓縮編碼中的量化處理數(shù)據(jù)壓縮編碼中的量化處理 不是指指 A/D 變換時(shí)的量化，而是指變換時(shí)的量化，而是指在熵編碼之前，對(duì)該值進(jìn)行的量化處理。 量化處理把某個(gè)范圍內(nèi)的一批輸入，量化到一量化處理把某個(gè)范圍內(nèi)的一批輸入，量化到一個(gè)輸出級(jí)上，因此是個(gè)輸出級(jí)上，因此是多對(duì)一的映射，過(guò)程一的映射，過(guò)程不可逆，有信息丟失，會(huì)引起，有信息丟失，會(huì)引起量化誤差(量化噪聲)。 量化方法和量化特性量化方法量化方法標(biāo)量量化矢量量化均勻

16、量化非均勻量化自適應(yīng)量化 標(biāo)量量化：對(duì)PCM數(shù)據(jù)一個(gè)數(shù)一個(gè)數(shù)地進(jìn)行量化。 矢量量化：對(duì)這些數(shù)據(jù)先分組, 每組 K 個(gè)數(shù)構(gòu)成一個(gè) K 維矢量，然后以矢量為單位，逐個(gè)矢量進(jìn)行量化。可有效提高壓縮比。 矢量量化的編碼與解碼矢量量化的編碼與解碼輸入量輸入量：待編碼的K維矢量(如一個(gè)尺寸nn圖象塊中的n2個(gè)象素)碼本碼本C：一個(gè)具有L個(gè)K維矢量的集合(實(shí)際上是一個(gè)長(zhǎng)度為L(zhǎng)的表， 這個(gè)表的每一個(gè)分量是一個(gè)K維矢量y，稱(chēng)其為碼字)。矢量量化編碼過(guò)程：矢量量化編碼過(guò)程： 從碼本 C 中搜索一個(gè)與輸入矢量最接近的碼字 yi(i=1,2,L)的過(guò)程。 傳輸時(shí)并不傳送碼字yi本身，只傳送其下標(biāo)號(hào) i 。 下標(biāo)所需比

17、特?cái)?shù)僅log2L,故該圖象塊一個(gè)象素僅需比特?cái)?shù) * log2L1K矢量量化的關(guān)鍵問(wèn)題矢量量化的關(guān)鍵問(wèn)題 設(shè)計(jì)一個(gè)良好的碼本。設(shè)計(jì)一個(gè)良好的碼本。編碼器編碼器 編碼器的輸入為編碼器的輸入為wi,若若wi可取可取M個(gè)值個(gè)值w1,w2 ,wm 之一，之一， 其輸出碼應(yīng)該是二進(jìn)制碼子其輸出碼應(yīng)該是二進(jìn)制碼子ci。 編碼器不會(huì)引入誤差。編碼器不會(huì)引入誤差。 設(shè)計(jì)編碼器應(yīng)該使設(shè)計(jì)編碼器應(yīng)該使M個(gè)可能輸入都能分配一個(gè)唯一的個(gè)可能輸入都能分配一個(gè)唯一的二進(jìn)制碼字。二進(jìn)制碼字。 例如，用不等長(zhǎng)碼對(duì)例如，用不等長(zhǎng)碼對(duì)w1,w2 ，w3 分別賦予一個(gè)碼字分別賦予一個(gè)碼字c1=0,c2=1,c3=01， 則對(duì)于比特流

18、則對(duì)于比特流0011，既可譯為：，既可譯為：c1c1c2c2，也可譯為也可譯為c1c3c2，不唯一。不唯一。 若賦予一個(gè)碼字若賦予一個(gè)碼字c1=0,c2=10,c3=11， 則對(duì)于比特流則對(duì)于比特流0011，可唯一譯為，可唯一譯為c1,c1,c3。 能實(shí)用的碼都應(yīng)該是唯一的。能實(shí)用的碼都應(yīng)該是唯一的。 信源解碼器包含兩個(gè)部分：符號(hào)解碼器和反向信源解碼器包含兩個(gè)部分：符號(hào)解碼器和反向映射器。映射器。反向映射符號(hào)解碼信道4.5無(wú)損壓縮無(wú)損壓縮 無(wú)損壓縮可以精確無(wú)誤地從壓縮數(shù)據(jù)中恢復(fù)出原始數(shù)無(wú)損壓縮可以精確無(wú)誤地從壓縮數(shù)據(jù)中恢復(fù)出原始數(shù)據(jù)。據(jù)。 常見(jiàn)的無(wú)損壓縮技術(shù)包括：基于統(tǒng)計(jì)概率的方法和基常見(jiàn)的無(wú)

19、損壓縮技術(shù)包括：基于統(tǒng)計(jì)概率的方法和基于字典的技術(shù)。于字典的技術(shù)。 基于統(tǒng)計(jì)概率的方法是依據(jù)信息論中的變長(zhǎng)編碼定理基于統(tǒng)計(jì)概率的方法是依據(jù)信息論中的變長(zhǎng)編碼定理和信息熵有關(guān)知識(shí)，用較短代碼代表出現(xiàn)概率大的符和信息熵有關(guān)知識(shí)，用較短代碼代表出現(xiàn)概率大的符號(hào)，用較長(zhǎng)代碼代表出現(xiàn)概率小的符號(hào)，從而實(shí)現(xiàn)數(shù)號(hào)，用較長(zhǎng)代碼代表出現(xiàn)概率小的符號(hào)，從而實(shí)現(xiàn)數(shù)據(jù)壓縮。據(jù)壓縮。 統(tǒng)計(jì)編碼方法中具有代表性的是利用概率分布特性的統(tǒng)計(jì)編碼方法中具有代表性的是利用概率分布特性的著名的霍夫曼著名的霍夫曼(Huffman)編碼方法編碼方法 ,另一種是算術(shù)編碼。另一種是算術(shù)編碼。 基于字典技術(shù)的數(shù)據(jù)壓縮技術(shù)有兩種：基于字典技術(shù)

20、的數(shù)據(jù)壓縮技術(shù)有兩種： 一種是游程編碼一種是游程編碼(Running Length Coding)，簡(jiǎn)稱(chēng)為，簡(jiǎn)稱(chēng)為RLC ，適用于灰度級(jí)不多、數(shù)據(jù)相關(guān)性很強(qiáng)的圖像數(shù)，適用于灰度級(jí)不多、數(shù)據(jù)相關(guān)性很強(qiáng)的圖像數(shù)據(jù)的壓縮。但最不適用于每個(gè)像素都與它周?chē)南袼負(fù)?jù)的壓縮。但最不適用于每個(gè)像素都與它周?chē)南袼夭煌那闆r。不同的情況。 另一種稱(chēng)之為另一種稱(chēng)之為L(zhǎng)ZW編碼編碼 ， LZW在對(duì)數(shù)據(jù)文件進(jìn)行編在對(duì)數(shù)據(jù)文件進(jìn)行編碼的同時(shí)，生成了特定字符序列的表以及它們對(duì)應(yīng)的碼的同時(shí)，生成了特定字符序列的表以及它們對(duì)應(yīng)的代碼。代碼。 4.5.1霍夫曼編碼霍夫曼編碼 一個(gè)事件集合一個(gè)事件集合x(chóng)1, x2,xn,處于一個(gè)

21、基本概率空間，其處于一個(gè)基本概率空間，其相應(yīng)概率為相應(yīng)概率為p1, p2,pn，且，且p1+ p2+pn=1。每一個(gè)信息。每一個(gè)信息的信息量為的信息量為: 如定義在概率空間中每一事件的概率不相等時(shí)的平均如定義在概率空間中每一事件的概率不相等時(shí)的平均不肯定程度或平均信息量叫作熵不肯定程度或平均信息量叫作熵H，則：，則：)(log)(kakpxInkkaknkkkkppxIpxIEH11log)()(1.理論基礎(chǔ)理論基礎(chǔ) （4-9） （4-10） 圖象熵：圖象熵： 設(shè)數(shù)字圖像像素灰度級(jí)集合為設(shè)數(shù)字圖像像素灰度級(jí)集合為(W1,W2,WM)，其對(duì)其對(duì)應(yīng)的概率分別為應(yīng)的概率分別為P1,P2,PM,則數(shù)字

22、圖像的信息熵則數(shù)字圖像的信息熵H為：為： H=nkkakPP1log a取取2時(shí)，時(shí)，H的單位為比特。的單位為比特。 a取取e時(shí)，時(shí)，H的單位的單位為奈特。圖像編碼中為奈特。圖像編碼中a取取2。 一幅圖像的信息熵就是這幅圖像的平均信息量，一幅圖像的信息熵就是這幅圖像的平均信息量，即表示圖像中各個(gè)灰度級(jí)比特?cái)?shù)的統(tǒng)計(jì)平均值。即表示圖像中各個(gè)灰度級(jí)比特?cái)?shù)的統(tǒng)計(jì)平均值。 等概率事件的熵最大。等概率事件的熵最大。 信息熵是進(jìn)行無(wú)失真編碼理論的極限。低于此極限的無(wú)失真編碼方法是不存在的。例例 :設(shè)設(shè)8個(gè)隨機(jī)變量具有同等概率為個(gè)隨機(jī)變量具有同等概率為18，計(jì)算信，計(jì)算信息熵息熵H。 解解 :根據(jù)公式根據(jù)公式

23、4-10可得：可得：H=8*-1/8*(log2(1/8)=8*-1/8*(-3)=3 編碼效率編碼效率在一般情況下，編碼效率往往用下列簡(jiǎn)單公式表在一般情況下，編碼效率往往用下列簡(jiǎn)單公式表示：示： =H/R%H為信息熵，為信息熵，R為平均碼字長(zhǎng)度。為平均碼字長(zhǎng)度。 平均碼字長(zhǎng)度平均碼字長(zhǎng)度 設(shè)設(shè) k為數(shù)字圖像第為數(shù)字圖像第k個(gè)碼字個(gè)碼字Ck的長(zhǎng)度（二進(jìn)制的長(zhǎng)度（二進(jìn)制代碼的位數(shù)），其相應(yīng)出現(xiàn)的概率為代碼的位數(shù)），其相應(yīng)出現(xiàn)的概率為Pk，則則該數(shù)字圖像所賦予的碼字平均碼長(zhǎng)該數(shù)字圖像所賦予的碼字平均碼長(zhǎng)R為為: R=nkkkP1 根據(jù)信息熵編碼理論，可以證明在根據(jù)信息熵編碼理論，可以證明在R H條

24、件下，條件下，總可以設(shè)計(jì)出某種無(wú)失真編碼方法?？偪梢栽O(shè)計(jì)出某種無(wú)失真編碼方法。 若編碼結(jié)果遠(yuǎn)大于若編碼結(jié)果遠(yuǎn)大于H，表明這種編碼效率很低，表明這種編碼效率很低，占用的比特?cái)?shù)太多。占用的比特?cái)?shù)太多。 若編碼結(jié)果使若編碼結(jié)果使R等于或接近于等于或接近于H，這種狀態(tài)的這種狀態(tài)的編碼方法稱(chēng)為最佳編碼。編碼方法稱(chēng)為最佳編碼。 若要求編碼結(jié)果使若要求編碼結(jié)果使RH，則必然丟失信息而引則必然丟失信息而引起圖像失真。這就是在允許失真條件下的一些起圖像失真。這就是在允許失真條件下的一些失真編碼方法。失真編碼方法。圖像熵編碼方法圖像熵編碼方法 熵編碼的目的就是要使編碼后的圖像平均比特熵編碼的目的就是要使編碼后的圖

25、像平均比特?cái)?shù)數(shù)R盡可能接近圖象熵盡可能接近圖象熵H。一般根據(jù)圖像灰度。一般根據(jù)圖像灰度級(jí)數(shù)出現(xiàn)的概率賦予不同長(zhǎng)度的碼字，概率大級(jí)數(shù)出現(xiàn)的概率賦予不同長(zhǎng)度的碼字，概率大的灰度級(jí)用短碼字，反之，用長(zhǎng)碼字。的灰度級(jí)用短碼字，反之，用長(zhǎng)碼字。 可以證明：這樣的編碼結(jié)果所獲得的平均碼字可以證明：這樣的編碼結(jié)果所獲得的平均碼字長(zhǎng)度最短。長(zhǎng)度最短。常用的熵編碼方法：常用的熵編碼方法： Huffman編碼編碼 Fano-shannon編碼編碼 游程編碼游程編碼 算術(shù)編碼算術(shù)編碼 Huffman編碼是編碼是1952年由年由Huffman提出的一種編碼方提出的一種編碼方法。法。 這種編碼方法根據(jù)信源數(shù)據(jù)符號(hào)發(fā)生的

26、概率進(jìn)行編碼。這種編碼方法根據(jù)信源數(shù)據(jù)符號(hào)發(fā)生的概率進(jìn)行編碼。在信源數(shù)據(jù)中出現(xiàn)概率越大的符號(hào)，相應(yīng)的碼越短；在信源數(shù)據(jù)中出現(xiàn)概率越大的符號(hào)，相應(yīng)的碼越短；出現(xiàn)概率越小的符號(hào)，其碼長(zhǎng)越長(zhǎng)，從而達(dá)到用盡可出現(xiàn)概率越小的符號(hào)，其碼長(zhǎng)越長(zhǎng)，從而達(dá)到用盡可能少的碼符號(hào)表示源數(shù)據(jù)。能少的碼符號(hào)表示源數(shù)據(jù)。 它在變長(zhǎng)編碼方法中是最佳的。它在變長(zhǎng)編碼方法中是最佳的。2. Huffman編碼編碼 設(shè)信源設(shè)信源A的信源空間為：的信源空間為：其中其中 ，現(xiàn)用，現(xiàn)用r個(gè)碼符號(hào)的碼符號(hào)集個(gè)碼符號(hào)的碼符號(hào)集 對(duì)信源對(duì)信源A中的每個(gè)符號(hào)（中的每個(gè)符號(hào)（i1，2，N)進(jìn)行編碼。進(jìn)行編碼。具體編碼的方法是具體編碼的方法是:(1

27、) 把信源符號(hào)按其出現(xiàn)概率的大小順序排列起來(lái)；把信源符號(hào)按其出現(xiàn)概率的大小順序排列起來(lái)；(2) 把最末兩個(gè)具有最小概率的元素之概率加起來(lái)；把最末兩個(gè)具有最小概率的元素之概率加起來(lái)；(3) 把該概率之和同其余概率由大到小排隊(duì)，然后再把兩個(gè)最小概率把該概率之和同其余概率由大到小排隊(duì)，然后再把兩個(gè)最小概率加起來(lái)，再重新排隊(duì)；加起來(lái)，再重新排隊(duì)；(4) 重復(fù)重復(fù)(2)直到最后只剩下兩個(gè)概率為止。直到最后只剩下兩個(gè)概率為止。1212:( ):()()()NNAaaaA PP AP aP aP a1( )1NiiP a12:,rXxxxHuffman編碼具體方法：編碼具體方法：例例1 :設(shè)有編碼輸入設(shè)有編

28、碼輸入 。其頻率分布分別。其頻率分布分別為為 ，現(xiàn)求其最佳霍夫曼編碼現(xiàn)求其最佳霍夫曼編碼 。 解解 :Huffman編碼過(guò)程下圖所示：編碼過(guò)程下圖所示： 123456,Xx xx xx x12( )0.4, ()0.3P xP x3()0.1,P x456()0.1, ()0.06, ()0.04P xP xP x123456,Ww w w w w w符號(hào) 概率 x1 0.4x2 0.3x3 0.1x4 0.1x5 0.06x6 0.041 0.40.30.10.10.120.40.30.20.130.40.30.340.60.4本例中對(duì)本例中對(duì)0.6賦予賦予0，對(duì)，對(duì)0.4賦予賦予1，0.4

29、傳遞到傳遞到x1，所以，所以x1的的編碼便是編碼便是1。0.6傳遞到前一級(jí)是兩個(gè)傳遞到前一級(jí)是兩個(gè)0.3相加，大值是單獨(dú)相加，大值是單獨(dú)一個(gè)元素一個(gè)元素x2的概率，小值是兩個(gè)元素概率之和，每個(gè)概率的概率，小值是兩個(gè)元素概率之和，每個(gè)概率都小于都小于0.3，所以，所以x2賦予賦予0，0.2和和0.1求和的求和的0.3賦予賦予1。所以。所以x2的編碼是的編碼是00，而剩余元素編碼的前兩個(gè)碼應(yīng)為，而剩余元素編碼的前兩個(gè)碼應(yīng)為01。0.1賦予賦予1，0.2賦予賦予0。以此類(lèi)推，最后得到諸元素的編碼如。以此類(lèi)推，最后得到諸元素的編碼如下：下： 元素元素x1x1x2x3x4x5x6概概 率率P(x1)0.

30、40.30.10.10.060.04編碼編碼w110001101000101001011 經(jīng)霍夫曼編碼后，平均碼長(zhǎng)為：經(jīng)霍夫曼編碼后，平均碼長(zhǎng)為： = =0.41+0.302+0.13+0.14+0.065+0.045=2.20(bit) 該信源的熵為該信源的熵為H=2.14 bit，編碼后計(jì)算的平均碼長(zhǎng)為，編碼后計(jì)算的平均碼長(zhǎng)為2.2 bit,非常接近于熵?？梢?jiàn)非常接近于熵。可見(jiàn)Huffman編碼是一種較好的編碼。編碼是一種較好的編碼。B61()iiPn例2：Huffman編碼舉例Huffman碼字的構(gòu)成3用二叉樹(shù)方法實(shí)現(xiàn)用二叉樹(shù)方法實(shí)現(xiàn)Huffman編碼方法較為便利，因此這種編碼方編碼方法

31、較為便利，因此這種編碼方法用于計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換中。法用于計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換中。Huffman編碼是最佳的編碼是最佳的 ，其構(gòu)造出來(lái)的碼不唯一，但其平均碼，其構(gòu)造出來(lái)的碼不唯一，但其平均碼長(zhǎng)相同長(zhǎng)相同 ，不影響編碼效率和數(shù)據(jù)壓縮性能。，不影響編碼效率和數(shù)據(jù)壓縮性能。 由于由于Huffman碼的碼長(zhǎng)參差不齊，因此，存在一個(gè)輸入、輸出速碼的碼長(zhǎng)參差不齊，因此，存在一個(gè)輸入、輸出速率匹配問(wèn)題。解決的辦法是設(shè)置一定容量的緩沖存儲(chǔ)器率匹配問(wèn)題。解決的辦法是設(shè)置一定容量的緩沖存儲(chǔ)器 Huffman碼在存儲(chǔ)或傳輸過(guò)程中，如果出現(xiàn)誤碼，可能會(huì)引起誤碼在存儲(chǔ)或傳輸過(guò)程中，如果出現(xiàn)誤碼，可能會(huì)引起誤碼的連續(xù)傳

32、播碼的連續(xù)傳播 Huffman編碼對(duì)不同信源其編碼效率也不盡相同。編碼對(duì)不同信源其編碼效率也不盡相同。 Huffman編碼應(yīng)用時(shí)，均需要與其他編碼結(jié)合起來(lái)使用，才能進(jìn)編碼應(yīng)用時(shí)，均需要與其他編碼結(jié)合起來(lái)使用，才能進(jìn)一步提高數(shù)據(jù)壓縮比。一步提高數(shù)據(jù)壓縮比。 Huffman編碼方法傳輸時(shí)，需要同時(shí)傳輸Huffman編碼表。Huffman編碼需要多次排序。4.5.2 香農(nóng)費(fèi)諾編碼香農(nóng)費(fèi)諾編碼 由于霍夫曼編碼法需要多次排序，當(dāng)很多時(shí)十分不便，由于霍夫曼編碼法需要多次排序，當(dāng)很多時(shí)十分不便，為此費(fèi)諾為此費(fèi)諾(Fano)和香農(nóng)和香農(nóng)(Shannon)分別單獨(dú)提出類(lèi)似的分別單獨(dú)提出類(lèi)似的方法，使編碼更簡(jiǎn)單。

33、具體編碼方法如下：方法，使編碼更簡(jiǎn)單。具體編碼方法如下： 把把 按概率由大到小、從上到下排成一列，然后按概率由大到小、從上到下排成一列，然后把把 分成兩組分成兩組 ， ，并使得，并使得 把兩組分別按把兩組分別按0，1賦值。賦值。 然后分組、賦值，不斷反復(fù)，直到每組只有一種輸入然后分組、賦值，不斷反復(fù)，直到每組只有一種輸入為止。將每個(gè)所賦的值依次排列起來(lái)就是費(fèi)諾為止。將每個(gè)所賦的值依次排列起來(lái)就是費(fèi)諾香農(nóng)香農(nóng)編碼。編碼。 nxx ,.,1nxx ,.,1kxx ,.,1nkxx,.,111()()knijijkPxPx 以前面哈夫曼編碼的例子進(jìn)行香農(nóng)費(fèi)諾編碼以前面哈夫曼編碼的例子進(jìn)行香農(nóng)費(fèi)諾編碼

34、 ：輸入概率 x10.4 o 0 x20.310 10 x30.1100 1100 x40.11 1101x50.0610 1110 x60.041 1111理論上，用Huffman方法對(duì)源數(shù)據(jù)流進(jìn)行編碼可達(dá)到最佳編碼效果。但由于計(jì)算機(jī)中存儲(chǔ)、處理的最小單位是“位”，因此，在一些情況下，實(shí)際壓縮比與理論壓縮比的極限相去甚遠(yuǎn)。例如源數(shù)據(jù)流由X和Y兩個(gè)符號(hào)構(gòu)成，它們出現(xiàn)的概率分別為23和13。根據(jù)字符X的熵確定的最優(yōu)碼長(zhǎng)為：H(X)=0.588bitH(Y)=1.58bit若要達(dá)到最佳編碼效果，相應(yīng)于字符若要達(dá)到最佳編碼效果，相應(yīng)于字符X的碼長(zhǎng)為的碼長(zhǎng)為0.58位；字符位；字符Y的碼長(zhǎng)為的碼長(zhǎng)為1

35、.58位。位。計(jì)算機(jī)中不可能有非整數(shù)位出現(xiàn)。硬件的限制使得計(jì)算機(jī)中不可能有非整數(shù)位出現(xiàn)。硬件的限制使得編碼只能按編碼只能按“位位”進(jìn)行。用進(jìn)行。用Huffman方法對(duì)這兩個(gè)字方法對(duì)這兩個(gè)字符進(jìn)行編碼，得到符進(jìn)行編碼，得到x、y的代碼分別為的代碼分別為0和和1。顯然，對(duì)于概率較大的字符顯然，對(duì)于概率較大的字符x不能給予較短的代碼。不能給予較短的代碼。這就是實(shí)際編碼效果不能達(dá)到理論壓縮比的原因所這就是實(shí)際編碼效果不能達(dá)到理論壓縮比的原因所在。在。4.5.3 算術(shù)編碼算術(shù)編碼 算術(shù)編碼沒(méi)有延用數(shù)據(jù)編碼技術(shù)中用一個(gè)特定的代碼代替一算術(shù)編碼沒(méi)有延用數(shù)據(jù)編碼技術(shù)中用一個(gè)特定的代碼代替一個(gè)輸入符號(hào)的一般做法

36、，它把要壓縮處理的整段數(shù)據(jù)映射到個(gè)輸入符號(hào)的一般做法，它把要壓縮處理的整段數(shù)據(jù)映射到一段實(shí)數(shù)半開(kāi)區(qū)間一段實(shí)數(shù)半開(kāi)區(qū)間0，1內(nèi)的某一區(qū)段，構(gòu)造出小于內(nèi)的某一區(qū)段，構(gòu)造出小于1且大于且大于或等于或等于0的數(shù)值。這個(gè)數(shù)值是輸入數(shù)據(jù)流的唯一可譯代碼。的數(shù)值。這個(gè)數(shù)值是輸入數(shù)據(jù)流的唯一可譯代碼。 算術(shù)編碼把一個(gè)信源集合表示為實(shí)數(shù)軸上的算術(shù)編碼把一個(gè)信源集合表示為實(shí)數(shù)軸上的0到到1之間的一個(gè)區(qū)間。信源集合中的每個(gè)元素都要用來(lái)縮之間的一個(gè)區(qū)間。信源集合中的每個(gè)元素都要用來(lái)縮短這個(gè)區(qū)間。信源集合的元素越多，所得到的區(qū)間就短這個(gè)區(qū)間。信源集合的元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時(shí)，就需要更多的數(shù)位來(lái)表示這

37、個(gè)越小，當(dāng)區(qū)間變小時(shí)，就需要更多的數(shù)位來(lái)表示這個(gè)區(qū)間，這就是區(qū)間作為代碼的原理。算術(shù)編碼首先假區(qū)間，這就是區(qū)間作為代碼的原理。算術(shù)編碼首先假設(shè)一個(gè)信源的概率模型，然后用這些概率來(lái)縮小表示設(shè)一個(gè)信源的概率模型，然后用這些概率來(lái)縮小表示信源集的區(qū)間。信源集的區(qū)間。 算術(shù)編碼的編碼方法算術(shù)編碼的編碼方法初始化子區(qū)間為初始化子區(qū)間為 0,1,預(yù)設(shè)一個(gè)大概率預(yù)設(shè)一個(gè)大概率 Pe 和小概率和小概率 Qe ,信源中的每個(gè)符號(hào)信源中的每個(gè)符號(hào)(0或或1)對(duì)應(yīng)一個(gè)概率對(duì)應(yīng)一個(gè)概率,然后對(duì)被編然后對(duì)被編碼信源比特流符號(hào)碼信源比特流符號(hào)(0或或1)依次進(jìn)行判斷。依次進(jìn)行判斷。QePe01設(shè)置兩個(gè)專(zhuān)用寄存器設(shè)置兩個(gè)專(zhuān)

38、用寄存器 C, A，存貯符號(hào)到來(lái)之前子存貯符號(hào)到來(lái)之前子區(qū)間的狀態(tài)參數(shù)，令：區(qū)間的狀態(tài)參數(shù)，令： C = 子區(qū)間的起始位置，子區(qū)間的起始位置， A = 子區(qū)間的寬度，子區(qū)間的寬度，初始化時(shí)，初始化時(shí)，C=0, A=1.隨著被編碼信源數(shù)據(jù)比特流符號(hào)隨著被編碼信源數(shù)據(jù)比特流符號(hào)0,1的輸入，的輸入，C和和A按以下方法進(jìn)行修正：按以下方法進(jìn)行修正：當(dāng)?shù)透怕史?hào)到來(lái)時(shí)，當(dāng)?shù)透怕史?hào)到來(lái)時(shí)， C C A A Qe 當(dāng)高概率符號(hào)到來(lái)時(shí)，當(dāng)高概率符號(hào)到來(lái)時(shí)， C C + A Qe A A Pe 新的子區(qū)間為新的子區(qū)間為C, C+A, , 以此類(lèi)推，直到一以此類(lèi)推，直到一組信源符號(hào)結(jié)束為止。算術(shù)編碼的結(jié)果落在

39、最組信源符號(hào)結(jié)束為止。算術(shù)編碼的結(jié)果落在最后的子區(qū)間之內(nèi)，為子區(qū)間頭、尾之間的取值。后的子區(qū)間之內(nèi)，為子區(qū)間頭、尾之間的取值。 題題 己知信源己知信源 X = 試對(duì)試對(duì) 1011 進(jìn)行算術(shù)編碼。進(jìn)行算術(shù)編碼。0 11/4 3/4 解 (1) 對(duì)二進(jìn)制信源只有兩個(gè)符號(hào)“0” 和“1”，設(shè)置小概率Qe =1/4，大概率 Pe = 1 Qe = 3/4. (2) 設(shè) C 為子區(qū)間的左端起始位置，A 為子區(qū)間的寬度，符號(hào)“0”的子區(qū)間為0,1/4), 符號(hào)“1”的子區(qū)間為1/4, 1)(3) 初始子區(qū)間為初始子區(qū)間為0, 1), C=0, A=1,子區(qū)間按以子區(qū)間按以下各步依次縮?。合赂鞑揭来慰s?。翰?/p>

40、序步序 符號(hào)符號(hào) C A1 1 0+1*1/4=1/4 1*3/4=3/4 2 0 1/4 3/4*1/4=3/163 1 1/4+3/16*1/4=19/64 3/16*3/4=9/644 1 19/64+9/64*1/4=85/256 9/64*3/4=27/25601/4119/6485/25610117/16112/256最后的子區(qū)間左端最后的子區(qū)間左端(起始位置起始位置) C = ( 85/256)d = (0.01010101)b最后的子區(qū)間右端最后的子區(qū)間右端(終止位置終止位置) C+A = (112/256) d = (0.01110000) b 編碼結(jié)果為子區(qū)間頭、尾之間取值

41、，其值為編碼結(jié)果為子區(qū)間頭、尾之間取值，其值為0.011, 可編碼為可編碼為011，原來(lái)，原來(lái)4個(gè)符號(hào)個(gè)符號(hào)1011現(xiàn)被壓縮現(xiàn)被壓縮為三個(gè)符號(hào)為三個(gè)符號(hào)011。 解碼 解碼時(shí)，是編碼的逆過(guò)程。解碼時(shí)，是編碼的逆過(guò)程。 首先將區(qū)間首先將區(qū)間 0 , 1) 按按 Qe 靠近靠近 0 側(cè)、側(cè)、 Pe 靠近靠近 1 側(cè)分割成兩個(gè)子區(qū)間，判斷被解碼的碼字落側(cè)分割成兩個(gè)子區(qū)間，判斷被解碼的碼字落在哪個(gè)子區(qū)間，賦以對(duì)應(yīng)符號(hào)，然后調(diào)整子區(qū)在哪個(gè)子區(qū)間，賦以對(duì)應(yīng)符號(hào)，然后調(diào)整子區(qū)間間 C, A 的值。的值。 按此法多次重復(fù)，便可依次得到串中各符號(hào)。按此法多次重復(fù)，便可依次得到串中各符號(hào)。4.5.4游程編碼游程編

42、碼 游程編碼游程編碼(RLC)是一種利用空間冗余度壓縮圖像的方是一種利用空間冗余度壓縮圖像的方法法 ，屬于統(tǒng)計(jì)編碼類(lèi)，屬于統(tǒng)計(jì)編碼類(lèi) 。 設(shè)圖像中的某一行或某一塊像素經(jīng)采樣或經(jīng)某種變換設(shè)圖像中的某一行或某一塊像素經(jīng)采樣或經(jīng)某種變換后的系數(shù)為后的系數(shù)為 ： 某一行或某一塊內(nèi)像素值某一行或某一塊內(nèi)像素值可分為可分為k段，長(zhǎng)度為段，長(zhǎng)度為 的連續(xù)串，每個(gè)串具有相同的值，的連續(xù)串，每個(gè)串具有相同的值，那么，該圖像的某一行或某一塊可由下面偶對(duì)那么，該圖像的某一行或某一塊可由下面偶對(duì) 來(lái)表示來(lái)表示： 其中其中 為每個(gè)串內(nèi)的代表值，為每個(gè)串內(nèi)的代表值， 為串的長(zhǎng)度。串長(zhǎng)就是為串的長(zhǎng)度。串長(zhǎng)就是游程長(zhǎng)度游程長(zhǎng)

43、度(Runlength)，簡(jiǎn)寫(xiě)為，簡(jiǎn)寫(xiě)為RL，即由灰度值構(gòu)成，即由灰度值構(gòu)成的數(shù)據(jù)流中各灰度值重復(fù)出現(xiàn)而形成的長(zhǎng)度。如果給的數(shù)據(jù)流中各灰度值重復(fù)出現(xiàn)而形成的長(zhǎng)度。如果給出了灰度值、對(duì)應(yīng)長(zhǎng)度及位置，就能很容易地恢復(fù)出出了灰度值、對(duì)應(yīng)長(zhǎng)度及位置，就能很容易地恢復(fù)出原來(lái)的數(shù)據(jù)流。原來(lái)的數(shù)據(jù)流。 12( ,)Mxxx121122( ,)(,),(,),(,)Mkkxxxglglgligil(,),1iiglik ilRL的基本結(jié)構(gòu)的基本結(jié)構(gòu) 游程編碼分為定長(zhǎng)游程編碼和變長(zhǎng)游程編碼兩類(lèi)。游程編碼分為定長(zhǎng)游程編碼和變長(zhǎng)游程編碼兩類(lèi)。v定長(zhǎng)游程編碼是指編碼的游程所使用位數(shù)是固定的，即定長(zhǎng)游程編碼是指編碼的游

44、程所使用位數(shù)是固定的，即RL位數(shù)是固定的。如果灰度連續(xù)相同的個(gè)數(shù)超過(guò)了固定位數(shù)所位數(shù)是固定的。如果灰度連續(xù)相同的個(gè)數(shù)超過(guò)了固定位數(shù)所能表示的最大值，則進(jìn)入下一輪游程編碼。能表示的最大值，則進(jìn)入下一輪游程編碼。變長(zhǎng)游程編碼是指對(duì)不同范圍的游程使用不同位數(shù)的編碼，變長(zhǎng)游程編碼是指對(duì)不同范圍的游程使用不同位數(shù)的編碼，即表示即表示RL位數(shù)是不固定的。位數(shù)是不固定的。X SC RL串字符串位置串長(zhǎng)游程編碼一般不直接應(yīng)用于多灰度圖像，但比較適合游程編碼一般不直接應(yīng)用于多灰度圖像，但比較適合 于二于二值圖像的編碼。值圖像的編碼。 為了達(dá)到較好的壓縮效果，有時(shí)游程編碼和其他一些編碼方為了達(dá)到較好的壓縮效果，有

45、時(shí)游程編碼和其他一些編碼方法混合使用。法混合使用。RLC比較適合二值圖像數(shù)據(jù)序列，其原因是在比較適合二值圖像數(shù)據(jù)序列，其原因是在二值序列中，只有二值序列中，只有“0”和和“1”兩種符號(hào)；這些符號(hào)的連續(xù)出兩種符號(hào)；這些符號(hào)的連續(xù)出現(xiàn)，就形成了現(xiàn)，就形成了“0”游程：游程：L(0)，“1”游程：游程：L(1)。 定義了游程和游程長(zhǎng)度之后，就可以把任何二元序列變換成定義了游程和游程長(zhǎng)度之后，就可以把任何二元序列變換成游程長(zhǎng)度的序列，簡(jiǎn)稱(chēng)游程序列。這一變換是可逆的，一一游程長(zhǎng)度的序列，簡(jiǎn)稱(chēng)游程序列。這一變換是可逆的，一一對(duì)應(yīng)的。對(duì)應(yīng)的。 4.5.5 無(wú)損預(yù)測(cè)編碼無(wú)損預(yù)測(cè)編碼 一幅二維靜止圖像，設(shè)空間坐

46、標(biāo)一幅二維靜止圖像，設(shè)空間坐標(biāo)(i，j)像素點(diǎn)的實(shí)際灰度為像素點(diǎn)的實(shí)際灰度為f(i,j)， 是根據(jù)以前已出現(xiàn)的像素點(diǎn)的灰度對(duì)該點(diǎn)的預(yù)測(cè)灰是根據(jù)以前已出現(xiàn)的像素點(diǎn)的灰度對(duì)該點(diǎn)的預(yù)測(cè)灰度，也稱(chēng)預(yù)測(cè)值或估計(jì)值，計(jì)算預(yù)測(cè)值的像素，可以是同一度，也稱(chēng)預(yù)測(cè)值或估計(jì)值，計(jì)算預(yù)測(cè)值的像素，可以是同一掃描行的前幾個(gè)像素，或者是前幾行上的像素，甚至是前幾掃描行的前幾個(gè)像素，或者是前幾行上的像素，甚至是前幾幀的鄰近像素。實(shí)際值和預(yù)測(cè)值之間的差值，以下式表示：幀的鄰近像素。實(shí)際值和預(yù)測(cè)值之間的差值，以下式表示： ),(jif),(),(),(jifjifjie（4-13） 由圖像的統(tǒng)計(jì)特性可知，相鄰像素之間有著較強(qiáng)的

47、相由圖像的統(tǒng)計(jì)特性可知，相鄰像素之間有著較強(qiáng)的相關(guān)性。因此，其像素的值可根據(jù)以前已知的幾個(gè)像素關(guān)性。因此，其像素的值可根據(jù)以前已知的幾個(gè)像素來(lái)估計(jì)，即預(yù)測(cè)。來(lái)估計(jì)，即預(yù)測(cè)。 預(yù)測(cè)編碼是根據(jù)某一模型，利用以往的樣本值對(duì)于新預(yù)測(cè)編碼是根據(jù)某一模型，利用以往的樣本值對(duì)于新樣本值進(jìn)行預(yù)測(cè)，然后將樣本的實(shí)際值與其預(yù)測(cè)值相樣本值進(jìn)行預(yù)測(cè)，然后將樣本的實(shí)際值與其預(yù)測(cè)值相減得到一個(gè)誤差值，對(duì)于這一誤差值進(jìn)行編碼。減得到一個(gè)誤差值，對(duì)于這一誤差值進(jìn)行編碼。 如果模型足夠好且樣本序列在時(shí)間上相關(guān)性較強(qiáng)，那如果模型足夠好且樣本序列在時(shí)間上相關(guān)性較強(qiáng)，那么誤差信號(hào)的幅度將遠(yuǎn)遠(yuǎn)小于原始信號(hào)。么誤差信號(hào)的幅度將遠(yuǎn)遠(yuǎn)小于原

48、始信號(hào)。 對(duì)差值信號(hào)不進(jìn)行量化而直接編碼就稱(chēng)之為無(wú)損預(yù)測(cè)對(duì)差值信號(hào)不進(jìn)行量化而直接編碼就稱(chēng)之為無(wú)損預(yù)測(cè)編碼。編碼。 無(wú)損預(yù)測(cè)編碼器的工作原理圖無(wú)損預(yù)測(cè)編碼器的工作原理圖 如下：如下：預(yù)測(cè)器源圖像熵編碼器編碼表壓縮源圖像 由先前三點(diǎn)預(yù)測(cè)可以定義為：由先前三點(diǎn)預(yù)測(cè)可以定義為： 其中其中a1，a2, a3稱(chēng)預(yù)測(cè)系數(shù)，都是待定參數(shù)。如果預(yù)測(cè)稱(chēng)預(yù)測(cè)系數(shù)，都是待定參數(shù)。如果預(yù)測(cè)器中預(yù)測(cè)系數(shù)是固定不變的常數(shù)，稱(chēng)之為線(xiàn)性預(yù)測(cè)。器中預(yù)測(cè)系數(shù)是固定不變的常數(shù)，稱(chēng)之為線(xiàn)性預(yù)測(cè)。 預(yù)測(cè)誤差：預(yù)測(cè)誤差： ),(jif), 1() 1, 1() 1,(),(321jifajifajifajif),(),(),(jifji

49、fjie), 1() 1, 1() 1,(),(321jifajifajifajif（4-14） （4-15） 設(shè)設(shè)a=f(i,j-1)，b=f(i-1,j), c=f(i-1,j-1)， 的預(yù)測(cè)方法如的預(yù)測(cè)方法如右圖所示，可有右圖所示，可有8種選擇方法：種選擇方法： ),(jif選擇方法預(yù)測(cè)值0非預(yù)測(cè)1acb 2b ax3c4a+b-c5a+(b-c)/26B+(a-c)/27 (a+b)/2),(yxf例：設(shè)有一幅圖像，例：設(shè)有一幅圖像，f(i-1,j-1),f(i-1,j), f(i,j-1), f(i,j)的灰度值的灰度值分別為分別為253,252,253,255，用圖，用圖4-8第四

50、種選擇方法預(yù)測(cè)第四種選擇方法預(yù)測(cè)f(i,j)的灰度值，并計(jì)算預(yù)測(cè)誤差。的灰度值，并計(jì)算預(yù)測(cè)誤差。 解：解： =a+b-c= f(i,j-1)+ f(i-1,j)- f(i-1,j-1)=252+253-253=252 預(yù)測(cè)誤差預(yù)測(cè)誤差 =255-252=3顯然，預(yù)測(cè)誤差顯然，預(yù)測(cè)誤差e(i,j)=3比像素的實(shí)際值比像素的實(shí)際值f(i,j)=255小的小的多，對(duì)多，對(duì)2進(jìn)行編碼比對(duì)進(jìn)行編碼比對(duì)255直接編碼將占用更少的比特直接編碼將占用更少的比特位。位。 ),(jif),(),(),(jifjifjie4.6有損壓縮有損壓縮 有損編碼是以丟失部分信息為代價(jià)來(lái)?yè)Q取高壓縮比。有損編碼是以丟失部分信息

51、為代價(jià)來(lái)?yè)Q取高壓縮比。 有損壓縮方法主要有有損預(yù)測(cè)編碼方法、變換編碼方有損壓縮方法主要有有損預(yù)測(cè)編碼方法、變換編碼方法等。法等。4.6.1有損預(yù)測(cè)編碼有損預(yù)測(cè)編碼 在預(yù)測(cè)編碼中，對(duì)差值信號(hào)進(jìn)行量化后再進(jìn)行編碼就在預(yù)測(cè)編碼中，對(duì)差值信號(hào)進(jìn)行量化后再進(jìn)行編碼就稱(chēng)之為有損預(yù)測(cè)編碼。稱(chēng)之為有損預(yù)測(cè)編碼。 有 損 預(yù) 測(cè) 方 法 有 多 種 ， 其 中 差 分 脈 沖 編 碼 調(diào) 制有 損 預(yù) 測(cè) 方 法 有 多 種 ， 其 中 差 分 脈 沖 編 碼 調(diào) 制(Differential Pulse Code Modulation，簡(jiǎn)稱(chēng)，簡(jiǎn)稱(chēng)DPCM)，是，是一種具有代表性的編碼方法。一種具有代表性的編碼

52、方法。 DPCM系統(tǒng)由編碼器和解碼器組成，它們各有一個(gè)相系統(tǒng)由編碼器和解碼器組成，它們各有一個(gè)相同的預(yù)測(cè)器。同的預(yù)測(cè)器。DPCM系統(tǒng)的工作原理如下圖所示系統(tǒng)的工作原理如下圖所示:量化器編碼器預(yù)測(cè)器信道傳輸解碼器輸入輸出預(yù)測(cè)器( , )f i j( , )e i j( , )e i j( , )fi j( , )fi j( , )fi j( , )e i j( , )fi j 系統(tǒng)包括發(fā)送、接收和信道傳輸三個(gè)部分。發(fā)送端由系統(tǒng)包括發(fā)送、接收和信道傳輸三個(gè)部分。發(fā)送端由編碼器、量化器、預(yù)測(cè)器和加減法器組成；接收端包編碼器、量化器、預(yù)測(cè)器和加減法器組成；接收端包括解碼器和預(yù)測(cè)器等；信道傳送以虛線(xiàn)表示

53、。圖中輸括解碼器和預(yù)測(cè)器等；信道傳送以虛線(xiàn)表示。圖中輸入信號(hào)入信號(hào)f(i,j)是坐標(biāo)是坐標(biāo)(i,j) 處的像素的實(shí)際灰度值，處的像素的實(shí)際灰度值， 是由已出現(xiàn)先前相鄰像素點(diǎn)的灰度值對(duì)該像素的預(yù)測(cè)是由已出現(xiàn)先前相鄰像素點(diǎn)的灰度值對(duì)該像素的預(yù)測(cè)灰度值?；叶戎?。 e(i,j)是預(yù)測(cè)誤差。是預(yù)測(cè)誤差。 DPCM包含量化器，這時(shí)編碼器對(duì)編碼，量化器導(dǎo)致包含量化器，這時(shí)編碼器對(duì)編碼，量化器導(dǎo)致了不可逆的信息損失，這時(shí)接收端經(jīng)解碼恢復(fù)出的灰了不可逆的信息損失，這時(shí)接收端經(jīng)解碼恢復(fù)出的灰度信號(hào)不是真正的度信號(hào)不是真正的f(i,j)，而是重建信號(hào)。可見(jiàn)引入量，而是重建信號(hào)。可見(jiàn)引入量化器會(huì)引起一定程度的信息損失

54、，使圖像質(zhì)量受損?；鲿?huì)引起一定程度的信息損失，使圖像質(zhì)量受損。但是可以利用人眼的視覺(jué)特性，丟失不易覺(jué)察的圖像但是可以利用人眼的視覺(jué)特性，丟失不易覺(jué)察的圖像信息，不會(huì)引起明顯失真信息，不會(huì)引起明顯失真 。),(jif4.6.2變換編碼變換編碼 變換編碼不是直接對(duì)空域圖像信號(hào)編碼，而是首先將圖變換編碼不是直接對(duì)空域圖像信號(hào)編碼，而是首先將圖像數(shù)據(jù)經(jīng)過(guò)某種正交變換（如傅立葉變換（像數(shù)據(jù)經(jīng)過(guò)某種正交變換（如傅立葉變換（DFT），離），離散余弦變換（散余弦變換（DCT），），K-L變換等等）另一個(gè)正交矢量變換等等）另一個(gè)正交矢量空間空間(稱(chēng)之為變換域稱(chēng)之為變換域)，產(chǎn)生一批變換系數(shù)，然后對(duì)這些變，產(chǎn)生

55、一批變換系數(shù)，然后對(duì)這些變換系數(shù)進(jìn)行編碼處理，從而達(dá)到壓縮圖像數(shù)據(jù)的目的。換系數(shù)進(jìn)行編碼處理，從而達(dá)到壓縮圖像數(shù)據(jù)的目的。 變換編碼的原理變換編碼的原理 如下圖：如下圖： 圖像數(shù)據(jù)經(jīng)過(guò)正交變換后，空域中的總能量在變換域圖像數(shù)據(jù)經(jīng)過(guò)正交變換后，空域中的總能量在變換域中得到保持，但像素之間的相關(guān)性下降，能量將會(huì)重中得到保持，但像素之間的相關(guān)性下降，能量將會(huì)重新分布，并集中在變換域中少數(shù)的變換系數(shù)上，因此，新分布，并集中在變換域中少數(shù)的變換系數(shù)上，因此，選擇少數(shù)選擇少數(shù)F(u,v)來(lái)重建圖像就可以達(dá)到壓縮數(shù)據(jù)的目來(lái)重建圖像就可以達(dá)到壓縮數(shù)據(jù)的目的，并且重建圖像僅引入較小誤差。的，并且重建圖像僅引入較

56、小誤差。 變換多采用正交函數(shù)為基礎(chǔ)的變換。變換多采用正交函數(shù)為基礎(chǔ)的變換。 f(x,y)重建f(x,y)圖象正交變換樣本選擇量化編碼F(u,v)( , )F u v( , )F u v( , )F u v 卡胡南卡胡南-列夫變換（列夫變換（K-L）對(duì)于對(duì)于N N的矩陣的矩陣T，有，有N個(gè)標(biāo)量個(gè)標(biāo)量i，i=1,2,N,能使能使|T-iI|=0 則則i叫做矩陣叫做矩陣T的特征值。另外，的特征值。另外，N個(gè)滿(mǎn)足個(gè)滿(mǎn)足 的向量的向量Vi叫做叫做T的特征向量，這些特征向量的特征向量，這些特征向量構(gòu)成一個(gè)正交基集。構(gòu)成一個(gè)正交基集。 設(shè)設(shè)X是一個(gè)是一個(gè)N 1的隨機(jī)向量，也就是說(shuō)，的隨機(jī)向量，也就是說(shuō)，X的

57、每個(gè)的每個(gè)分量都是分量都是xi隨機(jī)變量。隨機(jī)變量。X的均值（平均向量）可以由的均值（平均向量）可以由L個(gè)樣本向量來(lái)估計(jì)向量個(gè)樣本向量來(lái)估計(jì)向量Mx： iiiVTVLllxXLM11（4-32） Mx協(xié)方差矩陣可以由協(xié)方差矩陣可以由來(lái)估計(jì)。協(xié)方差矩陣是實(shí)對(duì)稱(chēng)的。對(duì)角元素是個(gè)隨機(jī)來(lái)估計(jì)。協(xié)方差矩陣是實(shí)對(duì)稱(chēng)的。對(duì)角元素是個(gè)隨機(jī)變量的方差，非對(duì)角元素是它們的協(xié)方差。變量的方差，非對(duì)角元素是它們的協(xié)方差。定義一個(gè)線(xiàn)性變換定義一個(gè)線(xiàn)性變換T，它可由任何，它可由任何X向量產(chǎn)生一個(gè)新向量產(chǎn)生一個(gè)新向量向量Y： 式中式中，T的各行是的各行是Mx的特征向量，即的特征向量，即T的行向量就是的行向量就是Mx的特征向量

58、。的特征向量。LlTllTllTxxMxMMXXLMXMXE11)()(xMXTY（4-33） （4-34） 變換得到的變換得到的Y是期望為零的隨機(jī)向量。是期望為零的隨機(jī)向量。Y的協(xié)方差矩的協(xié)方差矩陣可以由陣可以由X的協(xié)方差矩陣決定：的協(xié)方差矩陣決定： 因?yàn)橐驗(yàn)門(mén)的各行是的各行是x的特征向量，故的特征向量，故y是一個(gè)對(duì)角陣，是一個(gè)對(duì)角陣，對(duì)角元素是的對(duì)角元素是的x特征值。因此特征值。因此 這些也是的這些也是的x特征值。特征值。 隨機(jī)向量隨機(jī)向量Y是由互不相關(guān)的隨機(jī)變量組成的，因此線(xiàn)是由互不相關(guān)的隨機(jī)變量組成的，因此線(xiàn)性變換性變換T起到了消除變量間的相關(guān)性的作用。起到了消除變量間的相關(guān)性的作用。

59、 TXYTTx1 1 0 00 0 N N （4-35） 特征向量變換是可逆的。特征向量變換是可逆的。 要實(shí)現(xiàn)對(duì)信號(hào)進(jìn)行要實(shí)現(xiàn)對(duì)信號(hào)進(jìn)行KL變換，首先要求出矢量變換，首先要求出矢量x的協(xié)的協(xié)方差矩陣方差矩陣x，再求協(xié)方差矩陣，再求協(xié)方差矩陣x的特征值的特征值i，然后，然后求求對(duì)應(yīng)的對(duì)應(yīng)的x的特征向量，再用的特征向量，再用x的特征向量構(gòu)成正的特征向量構(gòu)成正交矩陣交矩陣T。 例例 :若已知隨機(jī)矢量若已知隨機(jī)矢量x的協(xié)方差矩陣為的協(xié)方差矩陣為 求其正交矩陣求其正交矩陣T？ x x6 2 06 2 02 2 2 2 1 10 0 1 11 11) 按按 , 求求x的特征值的特征值i : 得得: 則可解

60、得則可解得: =6.854 =2 =0.146 2) 求求i對(duì)應(yīng)的特征向量。將對(duì)應(yīng)的特征向量。將1，2，3代入代入(4-31)中分中分別求得如下三個(gè)特征向量：別求得如下三個(gè)特征向量： = = =0|xI011012202600000001101220261231V2V3V0.9180.3920.0670.3330.6670.6670.2170.6340.742用用V1，V2，V3的轉(zhuǎn)置向量作為正交矩陣的轉(zhuǎn)置向量作為正交矩陣T的行向量，的行向量，那么，對(duì)于任一向量那么，對(duì)于任一向量X=(2，1，-0.1)的的K-L變換為變換為 :則則Y的協(xié)方差矩陣的協(xié)方差矩陣y為為: Y=TX=0.918 0.