圖像編碼

1圖像編碼的基本知識(shí)2圖像壓縮編碼的方法3

哈夫曼編碼4

香農(nóng)－范諾編碼5

行程編碼6算術(shù)編碼7離散小波變換DWT8離散余弦變換DCT1圖像編碼的基本知識(shí)

數(shù)字化后的圖像信息數(shù)據(jù)量非常大，圖像壓縮利用圖像數(shù)據(jù)存在冗余信息，去掉這些冗余信息后可以有效壓縮圖像。

1.空間（像素間、幾何）：在同一幅圖片中，規(guī)則物體和規(guī)則背景（所謂規(guī)則是指表面有序的，而不是完全雜亂無(wú)章的排列）的表面物理特性具有相關(guān)性，這些相關(guān)性的光成像結(jié)果在數(shù)字化圖像中就表現(xiàn)為數(shù)據(jù)冗余。2.時(shí)間冗余。在序列圖像（電視圖像、運(yùn)動(dòng)圖像）中，相鄰兩幀圖像之間有較大的相關(guān)性。3.信息熵冗余。信息熵冗余也稱為編碼冗余，如果圖像中平均每個(gè)像素使用的比特?cái)?shù)大于該圖像的信息熵，則圖像中存在冗余，稱為信息熵冗余。4.結(jié)構(gòu)冗余。有些圖像（例如墻紙、草席等）存在較強(qiáng)的紋理結(jié)構(gòu)，稱為結(jié)構(gòu)冗余。5.知識(shí)冗余。有許多圖像對(duì)其理解與某些基礎(chǔ)知識(shí)有相關(guān)大的相關(guān)性，例如：人臉的圖像有固定的結(jié)構(gòu)，嘴的上方有鼻子，鼻子的上方有眼睛，鼻子位于正臉圖像的中線上等。這些規(guī)則性的結(jié)構(gòu)可由先驗(yàn)知識(shí)和背景知識(shí)得到，稱此類冗余為知識(shí)冗余。6.心理視覺冗余。人類的視覺系統(tǒng)對(duì)于圖像場(chǎng)的注意是非均勻和非線性的，特別是視覺系統(tǒng)并不是對(duì)圖像場(chǎng)的任何變化都能感知，即眼睛并不是對(duì)所有信息都有相同的敏感度。有些信息在通常的視覺感覺過程中與另外一些信息相比來(lái)說(shuō)并不是那么重要，這些信息可認(rèn)為是心理視覺冗余的，去除這些信息并不是明顯地降低所感受到的圖像的質(zhì)量。1圖像編碼的基本知識(shí)

2圖像壓縮編碼的方法

圖像壓縮編碼分為有損壓縮和無(wú)損壓縮。無(wú)損壓縮無(wú)信息損失，解壓縮時(shí)能夠從壓縮數(shù)據(jù)精確地恢復(fù)原始圖像；有損壓縮不能精確重建原始圖像，存在一定程度的失真。根據(jù)編碼原理將圖像編碼分為：（1）熵編碼：無(wú)損編碼，給出現(xiàn)概率較大的符號(hào)賦予一個(gè)短碼字，而給出現(xiàn)概率較小的符號(hào)賦予一個(gè)長(zhǎng)碼字，從而使得最終的平均碼長(zhǎng)很小。2圖像編碼的方法（2）預(yù)測(cè)編碼：基于圖像數(shù)據(jù)的空間或時(shí)間冗余特性，用相鄰的已知像素（或像素塊）來(lái)預(yù)測(cè)當(dāng)前像素（或像素塊）的取值，然后再對(duì)預(yù)測(cè)誤差進(jìn)行量化和編碼。（3）變換編碼：將空間域上的圖像變換到另一變換域上，變換后圖像的大部分能量只集中到少數(shù)幾個(gè)變換系數(shù)上，采用適當(dāng)?shù)牧炕挽鼐幋a就可以有效地壓縮圖像。（4）混合編碼：綜合了熵編碼、變換編碼或預(yù)測(cè)編碼的編碼方法。如JPEG標(biāo)準(zhǔn)和MPEG標(biāo)準(zhǔn)。

(1)Huffman編碼原理:整體的大部分字符是由較短的編碼從而保證文件出現(xiàn)頻率高低的順序分別賦以由短到長(zhǎng)的代碼，先統(tǒng)計(jì)數(shù)據(jù)中各字符出現(xiàn)的概率，再按字符所構(gòu)成。3哈夫曼編碼編碼思想①將信源符號(hào)按概率遞減順序排列；②將兩個(gè)最小的概率加起來(lái)作為新符號(hào)的概率；③重復(fù)步驟①和②，直到概率和等于1；④完成上述步驟后沿路徑返回進(jìn)行編碼。尋找從每一信源符號(hào)到概率為1處的路徑,每層有兩個(gè)分支，分別大的概率賦予0和小的概率為1，從而得到每個(gè)符號(hào)的編碼。3010402020402002020303020402040(1)

統(tǒng)計(jì)出每級(jí)灰度出現(xiàn)的頻率：灰度值：010203040出現(xiàn)頻率：1/161/167/163/164/16霍夫曼編碼舉例3010402020402002020303020402040哈夫曼編碼(2)從左到右把上述頻率按從小到大的順序排列?；叶戎担?10304020出現(xiàn)頻率：1/161/163/164/167/163010402020402002020303020402040哈夫曼編碼(3)

選出頻率最小的兩個(gè)值（1/16，1/16）作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將頻率和2/16作為它們的根節(jié)點(diǎn),新的根節(jié)點(diǎn)再參與其它頻率排序：

2/163/165/167/161/161/162/163010402020402002020303020402040哈夫曼編碼（4）

選出頻率最小的兩個(gè)值（2/16，3/16）作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將頻率和5/16作為它們的根節(jié)點(diǎn),新的根節(jié)點(diǎn)再參與其它頻率排序：

4/165/167/161/161/162/163/165/163010402020402002020303020402040哈夫曼編碼（5）

選出頻率最小的兩個(gè)值（4/16，5/16）作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)將頻率和9/16作為它們的根節(jié)點(diǎn),新的根節(jié)點(diǎn)再參與其它頻率排序：7/169/161/161/162/163/165/164/169/163010402020402002020303020402040哈夫曼編碼（6）最后兩個(gè)頻率值（7/16，9/16）作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將頻率和1作為它們的根節(jié)點(diǎn)。1/161/162/163/165/164/169/167/1613010402020402002020303020402040哈夫曼編碼（7）分配碼字。將形成的二叉樹的左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。把從最上面的根節(jié)點(diǎn)到最下面的葉子節(jié)點(diǎn)途中遇到的0,1序列串起來(lái)，就得到了各級(jí)灰度的編碼.

010030140020011103010402020402002020303020402040哈夫曼編碼各灰度的編碼如下：灰度值：204030100哈夫曼編碼：01011111011100則圖所示的圖像哈夫曼編碼為：1111010100101100000111111010100010030140020011104香農(nóng)-范諾編碼香農(nóng)-范諾編碼的理論基礎(chǔ)是符號(hào)的碼字長(zhǎng)度完全由該符號(hào)出現(xiàn)的概率來(lái)決定。

香農(nóng)－范諾編碼與Huffman編碼相反，采用從上到下的方法。香農(nóng)－范諾（二分法）編碼具體步驟：(1)首先將編碼字符集中的字符按照出現(xiàn)頻度和概率進(jìn)行排序。后面的賦值為1直至不可再分，即每一個(gè)葉子對(duì)應(yīng)一個(gè)字符。(3)編碼(從根結(jié)點(diǎn)開始)。(2)用遞歸的方法分成兩部分，使兩個(gè)部分的概率和接近于相等。給前一個(gè)子集合賦值為0，

如：設(shè)一副灰度級(jí)為8的圖象中，各灰度所對(duì)應(yīng)的概率分別為0.04，0.05，0.06，0.07，0.10，0.10，0.18，0.40，現(xiàn)在對(duì)其進(jìn)行二分法香農(nóng)－范諾編碼？編碼舉例s0,s1,s2,s3,s4,s5,s6,s7s2,s3,s4,s5,s6,s7s0,s10.580.42s2,s3s4,s5,s6,s7s0s1s4,s5s6,s7s2s3s4s5s6s7s00.40s1s2s3s4s5s60.180.100.100.07s70.060.050.040.200.220.130.0901010101010101S0:00S1:01S2:100S3:101S4:1100S5:1101S6:1110S7:11115行程編碼行程編碼基本方法（RLE）

行程編碼又稱行程長(zhǎng)度編碼（RunLengthEncoding，RLE），是一種熵編碼，其編碼原理是將具有相同值的連續(xù)串用其串長(zhǎng)和一個(gè)代表值來(lái)代替，該連續(xù)串就稱為行程，串長(zhǎng)稱為行程長(zhǎng)度。RLE編碼簡(jiǎn)單直觀，編碼/解碼速度快，因此許多圖形、均采用此方法。圖像和視頻文件，如.BMP、.TIFF及AVI等格式文件的壓縮定長(zhǎng)行程編碼:編碼的行程長(zhǎng)度所用的二進(jìn)制位數(shù)固定。變長(zhǎng)行程編碼:不同范圍的行程長(zhǎng)度用不同編碼位，需要增加標(biāo)志位來(lái)表明所使用的二進(jìn)制位數(shù)。3，，12，4，，9，，1，行程編碼基本方法例如：aabbbcddddd的行程長(zhǎng)度編碼為2a3b1c5d。二值圖變長(zhǎng)行程編碼的一種方法

3124911111001001001111110010010011

（不知道各行程應(yīng)在何處分?jǐn)啵┛梢远x：可表示行程長(zhǎng)度值編碼編碼長(zhǎng)度1-40??35-810???59-16110????717-321110?????933-6411110??????1165-128111110???????13

如：1100的編碼為：1100-1=1011（十進(jìn)制11）？？行程編碼為：1101011

01011010110111101000000

31249111110010010011

10101111100000101101011

0111101000000還原方法：從符號(hào)串左端開始往右搜索，遇到第一個(gè)0時(shí)停下來(lái)，計(jì)算這個(gè)0的前面有幾個(gè)1。設(shè)1的個(gè)數(shù)為K，則在0后面讀K+2個(gè)符號(hào)，這K+2個(gè)符號(hào)所表示的二進(jìn)制數(shù)加上1的值就是第1個(gè)行程的長(zhǎng)度。開始搜索第一個(gè)0該0前1的個(gè)數(shù)為0讀0+2個(gè)字符10+01=11第二個(gè)0該0前1的個(gè)數(shù)為2讀2+2個(gè)字符1011+0001=1100第三個(gè)0該0前1的個(gè)數(shù)為0讀0+2個(gè)字符11+01=100第四個(gè)0該0前1的個(gè)數(shù)為2讀2+2個(gè)字符1000+0001=1001第五個(gè)0該0前1的個(gè)數(shù)為0讀0+2個(gè)字符00+01=01(1)0101110110111110000000000000開始搜索第一個(gè)0該0前1的個(gè)數(shù)為0讀0+2個(gè)字符10+01=11第二個(gè)0該0前1的個(gè)數(shù)為2讀2+2個(gè)字符1011+0001=1100第三個(gè)0該0前1的個(gè)數(shù)為0讀0+2個(gè)字符11+01=100第四個(gè)0該0前1的個(gè)數(shù)為2讀2+2個(gè)字符1000+0001=1001第五個(gè)0該0前1的個(gè)數(shù)為0讀0+2個(gè)字符00+01=01(1)0101110110111110000000000000RLE所能獲得的壓縮比主要取決于圖像反之，壓縮比就越小。塊越大，本身的特點(diǎn)。若圖像中具有相同顏色的圖像圖像塊數(shù)目越少，則壓縮比就越高，行程編碼適合于對(duì)二值圖像的編碼，如果圖像是由很多塊顏色或灰度相同的大面積區(qū)域組成的，采用行程編碼可以達(dá)到很大的壓縮比。通常，為了達(dá)到比較好的壓縮效果，一般不單獨(dú)使用行程編碼，而是和其他編碼方法結(jié)合使用。如：在JPEG中，就綜合使用了行程編碼以及哈夫曼編碼。

6算術(shù)編碼是一種從整個(gè)符號(hào)序列出發(fā)，采用遞推形式連續(xù)編碼的方法，與建立在符號(hào)和碼字對(duì)應(yīng)基礎(chǔ)上的塊碼不同，在算術(shù)編碼中，源符號(hào)和碼字間的一一對(duì)應(yīng)關(guān)系并不存在。1個(gè)算術(shù)碼字要賦給整個(gè)信源符號(hào)碼字，而每個(gè)碼字本身確定了0和1之間的1個(gè)實(shí)數(shù)區(qū)間。 算術(shù)編碼具體方法是將被編碼的信源消息表示成實(shí)數(shù)軸0-1之間的一個(gè)間隔，消息越長(zhǎng)，編碼表示的間隔就越小，即這一間隔所采用算術(shù)編碼每個(gè)符號(hào)的平均編碼長(zhǎng)度可以為小數(shù)。需的二進(jìn)制位數(shù)就越多。算術(shù)編碼算術(shù)編碼對(duì)信源“baacc”進(jìn)行算術(shù)編碼（1）計(jì)算信源中各符號(hào)出現(xiàn)的概率P(a)=0.4，P(b)=0.2，

P(c)=0.4。（2）將數(shù)據(jù)序列中的各數(shù)據(jù)符號(hào)在區(qū)間［0,1］內(nèi)的間隔（賦值范圍）設(shè)定為a=［0,0.4）,

b=［0.4,0.6）,c=［0.6,1.0］。算術(shù)編碼(3)第一個(gè)被壓縮的符號(hào)為“b”，其初始間隔為［0.4,0.6)；(4)第二個(gè)被壓縮的符號(hào)為“a”，由于前面的符號(hào)“b”的取值區(qū)間被限制在［0.4,0.6)范圍內(nèi)，所以“a”的取值范圍應(yīng)在前一符號(hào)間隔［0.4,0.6)的［0,0.4)子區(qū)間內(nèi):

起始位為0.4+0×(0.6-0.4)=0.4終止位為0.4+0.4×(0.6-0.4)=0.48即“a”的實(shí)際編碼區(qū)間在［0.4,0.48)之間。算術(shù)編碼(5)第三個(gè)被壓縮的符號(hào)為“a”，由于前面的符號(hào)“a”的取值區(qū)間被限制在［0.4,0.48)范圍內(nèi)，所以“a”的取值范圍應(yīng)在前一符號(hào)間隔［0.4,0.48)的［0,0.4)子區(qū)間內(nèi):

起始位為0.4+0×(0.48-0.4)=0.4終止位為0.4+0.4×(0.48-0.4)=0.432即“a”的實(shí)際編碼區(qū)間在［0.4,0.432)之間。算術(shù)編碼(6)第四個(gè)被壓縮的符號(hào)為“c”，其取值范圍應(yīng)在前一符號(hào)間隔［0.4,0.432)的［0.6,1］子區(qū)間內(nèi):起始位為0.4+0.6×(0.432-0.4)=0.4192終止位為0.4+1×(0.432-0.4)=0.432

即“c”的實(shí)際編碼區(qū)間在［0.4192,0.432］之間。算術(shù)編碼(6)第五個(gè)被壓縮的符號(hào)為“c”，其取值范圍應(yīng)在前一符號(hào)間隔［0.4192,0.432)的［0.6,1］子區(qū)間內(nèi):

起始位為0.4192+0.6×(0.432-0.4192)=0.42688終止位為0.4192+1×(0.432-0.4192)=0.432即“c”的實(shí)際編碼區(qū)間在［0.42688,0.432］之間。算術(shù)編碼(7)把區(qū)間［0.42688,0.432］用二進(jìn)制形式表示為［0.0110110101001,0.011011101000011］。(8)在這個(gè)區(qū)間中找出其編碼最短的二進(jìn)制作為算術(shù)編碼?？梢钥闯?，0.0110111是此區(qū)間最短的編碼，且算術(shù)編碼中任一數(shù)據(jù)序列的編碼都含有“0.”，在編碼時(shí)，可以不考慮“0.”，故把0110111其作為數(shù)據(jù)序列“baacc”的算術(shù)編碼。解碼如下：（0.42688-0）/1=0.42688b（0.42688-0.4）/0.2=0.1344a（0.1344-0）/0.4=0.336a（0.336-0）/0.4=0.84c（0.84-0.6）/0.4=0.