2024/3/261第五章圖像編碼（1）

信息與通信工程學(xué)院張洪剛zhhg@25.1圖像編碼介紹5.1.1圖像編碼技術(shù)的必要性：1.信息傳輸方式發(fā)生了很大的改變通信方式的改變

文字+語(yǔ)音圖像+文字+語(yǔ)音Instagram每天圖片上傳量約為6000萬(wàn)張；今年2月份WhatsApp每天的圖片發(fā)送量為5億張；國(guó)內(nèi)的微信朋友圈也是以圖片分享為驅(qū)動(dòng)。35.1.1圖像編碼技術(shù)的必要性

2.圖像傳輸與存儲(chǔ)需要的信息量空間：

1）彩色視頻信息

對(duì)于電視畫(huà)面的分辨率640*480的彩色圖像，每秒30幀，則一秒鐘的數(shù)據(jù)量為：

640*480*24*30=221.12M

所以播放時(shí)，需要221Mbps的通信回路。

4

2.圖像傳輸與存儲(chǔ)需要的信息量空間：

2）傳真數(shù)據(jù)如果只傳送2值圖像，以200dpi的分辨率傳輸，一張A4稿紙的內(nèi)容的數(shù)據(jù)量為：

1654*2337*1=3888768bit

5.1.1圖像編碼技術(shù)的必要性55.1.2圖像編碼技術(shù)的可能性1.數(shù)字圖像本身的特征帶來(lái)的數(shù)據(jù)壓縮的可能性

1)圖象中象素灰度出現(xiàn)的不均勻性，造成圖象信息熵冗余,即用同樣長(zhǎng)度比特表示每一個(gè)灰度，則必然存在冗余。

2)圖象能量在變換域內(nèi)分布的不均勻性，比如大部分能量集中在低頻部分，而小部分能量集中在高和較高的頻率部分。63)圖象象素灰度在時(shí)間和空間上的相關(guān)性造成信息冗余。例如*空間冗余，鄰近象素灰度分布的相關(guān)性很強(qiáng)；*時(shí)間冗余：序列圖象幀間畫(huà)面對(duì)應(yīng)象素灰度的相關(guān)性很強(qiáng)；*結(jié)構(gòu)冗余：圖像中存在重復(fù)出現(xiàn)或相近的紋理結(jié)構(gòu)，可以通過(guò)特定的過(guò)程來(lái)生成。5.1.2圖像編碼技術(shù)的可能性2024/3/267時(shí)間冗余：序列圖象幀間畫(huà)面對(duì)應(yīng)象素灰度的相關(guān)性很強(qiáng)。結(jié)構(gòu)冗余：重復(fù)出現(xiàn)或相近的紋理結(jié)構(gòu)2024/3/2689描述語(yǔ)言

1）“這是一幅2*2的圖像，圖像的第一個(gè)像素是紅的，第二個(gè)像素是紅的，第三個(gè)像素是紅的，第四個(gè)像素是紅的”。

2）“這是一幅2*2的圖像，整幅圖都是紅色的”。

由此我們知道，整理圖像的描述方法可以達(dá)到壓縮的目的。圖像中的數(shù)據(jù)冗余的概念10圖像冗余無(wú)損壓縮的原理RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGB16RGB從原來(lái)的16*3*8=284bits壓縮為：(1+3)*8=32bits圖像中的數(shù)據(jù)冗余的概念11圖像冗余有損壓縮的原理36353434343434323434333730343434343434343435343431343434343434343434343434343434343434343434343434342534圖像中的數(shù)據(jù)冗余的概念12實(shí)際圖像中冗余信息的表現(xiàn)（灰度圖）圖像中的數(shù)據(jù)冗余的概念13圖象的視覺(jué)冗余（彩色）

R

G

B2488822*2*2=242=16,777,216(248,27,4)(248,27,4)圖像中的數(shù)據(jù)冗余的概念(248,27,4)(251,32,15)143.圖像冗余信息分析結(jié)論

由于一幅圖像存在數(shù)據(jù)冗余和主觀(guān)視覺(jué)冗余，我們的壓縮方式就是從這兩方面著手來(lái)開(kāi)展的。1）因?yàn)橛袛?shù)據(jù)冗余，當(dāng)我們將圖像信息的描述方式改變之后，可以壓縮掉這些冗余。2）因?yàn)橛兄饔^(guān)視覺(jué)冗余，當(dāng)我們忽略一些視覺(jué)不太明顯的微小差異，可以進(jìn)行所謂的“有損”壓縮。圖像中的數(shù)據(jù)冗余的概念154.應(yīng)用環(huán)境允許圖象有一定程度失真1)接收端圖象設(shè)備分辨率較低，則可降低圖象分辨率；2)根據(jù)人的視覺(jué)特性對(duì)不敏感區(qū)進(jìn)行降分辨率編碼（視覺(jué)冗余）；3)應(yīng)用方關(guān)心圖象區(qū)域有限，可對(duì)其余部分圖象可采用空間和灰級(jí)上的粗化；4)對(duì)于識(shí)別，圖象特征抽取和描述也是數(shù)據(jù)壓縮。161.等長(zhǎng)碼與不等長(zhǎng)碼映射變換量化器編碼器解碼器反映射原始圖像信源碼字恢復(fù)的圖像等長(zhǎng)碼的碼位長(zhǎng)度都相等，即每一個(gè)碼字均有相同的比特?cái)?shù)，而不等長(zhǎng)碼則相反常用編碼類(lèi)型5.1.3編碼過(guò)程與編碼分類(lèi)173.唯一可譯碼與非唯一可譯碼例如，某種代碼，c1=0,c2=1,c3=01,c4=10,

則序列0011具有多意性：0011c1c3c2c1c1c2c22.瞬時(shí)可譯碼與非瞬時(shí)可譯碼瞬時(shí)可譯碼：接收到一個(gè)碼位即可譯碼非瞬時(shí)可譯碼：接收到下一碼位才能譯碼185.1.4圖像的熵與平均碼字長(zhǎng)度1.圖像的熵

設(shè)數(shù)字圖像像素的灰度集合為｛w1,w2,……,wM｝，其對(duì)應(yīng)的概率分別為p1,p2,……,pM,按信息論中信源熵的定義，可以定義圖像的熵H

為：(bit)由上述定義可以看到，圖像的熵H是表示其各個(gè)灰度級(jí)比特?cái)?shù)的統(tǒng)計(jì)平均值，例如：①設(shè)隨機(jī)序列M由8個(gè)變量組成，等概率出現(xiàn)，即p1=p2=……,=p8，則：(bit)②設(shè)隨機(jī)序列M由8個(gè)變量組成，p1=1,p2=……,=p8=0，則：(bit)

因此，當(dāng)M

等于8時(shí)，H

的范圍從0到3，即H＝0～log2M，其中H＝3說(shuō)明信號(hào)的隨機(jī)程度最大。192.圖像的平均碼字長(zhǎng)度

設(shè)bk為數(shù)字圖像第k

個(gè)碼字ck的長(zhǎng)度(二進(jìn)制數(shù)的位數(shù))，其對(duì)應(yīng)出現(xiàn)的概率為pk,則該數(shù)字圖像的碼字平均長(zhǎng)度R

定義為：(bit)3.圖像的編碼效率：定義數(shù)字圖像編碼的效率為：

在R≧H

情況下總可以設(shè)計(jì)出某種無(wú)失真編碼方法，若R接近于H，則說(shuō)明碼編的較好，稱(chēng)為最佳編碼。若要求編碼結(jié)果R<H,則必然要丟失信息而引起圖像失真。同時(shí)定義圖像編碼的冗余度為：204.圖像的變長(zhǎng)最佳編碼定理定理：在變長(zhǎng)編碼中，若對(duì)出現(xiàn)概率大的信息賦予短碼字，而對(duì)于出現(xiàn)概率小的信息賦予長(zhǎng)碼字，如果碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)符號(hào)出現(xiàn)的概率大小而逆序排列，則此種編碼結(jié)果的平均碼字長(zhǎng)度一定小于其它任何排列形式得到的編碼。21例如：圖像的熵(bit)采用等長(zhǎng)編碼：平均碼長(zhǎng)R＝2(bit)，編碼效率h＝87.5％，Rd=12.5%輸入數(shù)據(jù)W1W2W3W4概率1/21/41/81/8W1W2W3W400011011W1W2W3W4010110111采用不等長(zhǎng)編碼：平均碼長(zhǎng)R＝7/4(bit)，編碼效率h＝

100％，Rd=0%2024/3/26225.2統(tǒng)計(jì)編碼5.2.1Huffman編碼（Huffman

，1952）Huffman編碼是根據(jù)可變長(zhǎng)度最佳編碼定理，應(yīng)用Huffman編碼算法而產(chǎn)生的一種編碼方法它的平均碼字長(zhǎng)度在系統(tǒng)的輸入概率集合下，比其它唯一可譯碼都小。因此也稱(chēng)為緊湊碼。Huffman編碼的原則是概率大的信息用短碼，而概率小的信息用長(zhǎng)碼，即：若：p1(w1)>p2(w2)>……>pM(wM)則?。篵1(c1)<b2(c2)<……<bM(cM)2024/3/2623Huffman編碼的編碼步驟：①將信源符號(hào)按概率由大到小排列，概率相同的可以任意放②將兩個(gè)最小概率相加，形成新的概率集合，并按①的原則重新排隊(duì)③重復(fù)②的過(guò)程，直到僅剩下兩個(gè)概率為止④分配碼字進(jìn)行編碼，原則是從后到前，上0下1(或上1下0)2024/3/2624Huffman編碼舉例：第一次重排編碼結(jié)果輸入數(shù)據(jù)對(duì)應(yīng)概率W10.4W20.3W30.1W40.1W50.06W60.040.40.30.10.10.10.40.30.20.10.40.30.30.60.4第二次重排第三次重排第四次重排01111110001000000000100110110100010101000101001011010110101001101101002024/3/2625熵計(jì)算編碼效率：編碼效率：h=2.14/2.2=97.3%為在接收端對(duì)上述編碼進(jìn)行解碼，可以采用樹(shù)形解碼方法唯一地解碼，每輸入一位即可確定分支情況，并自動(dòng)確定碼字的起止位。為此需要建立右圖的解碼樹(shù)。平均碼長(zhǎng)：R＝0.4＋0.3×2＋0.1×3＋0.1×4＋0.06×5＋0.04×5＝2.2bit說(shuō)明：wi1011110000w1w3w6w2w4w5在解碼時(shí)將輸入的數(shù)碼按樹(shù)去分配，得到碼字的切分和代碼符號(hào)，例如，輸入序列1011100010101從上述解碼過(guò)程可以看到，雖然Huffman碼不是等長(zhǎng)碼，但解碼中能自動(dòng)確定起止位。解碼結(jié)果是唯一的。2024/3/2626Huffman編碼特點(diǎn)優(yōu)點(diǎn)平均碼長(zhǎng)>=熵平均碼長(zhǎng)<等長(zhǎng)碼需要的碼字碼長(zhǎng)與概率成反比分布唯一可譯碼瞬時(shí)可譯碼缺點(diǎn)編碼過(guò)程強(qiáng)烈依賴(lài)概率結(jié)構(gòu)，不斷排序，工作量大碼字長(zhǎng)度變化大，碼字結(jié)構(gòu)復(fù)雜，實(shí)現(xiàn)困難。2024/3/2627構(gòu)造結(jié)果不唯一01與10的不同；概率相同的情況碼字字長(zhǎng)參差不齊硬件實(shí)現(xiàn)不方便對(duì)不同的信源的編碼效率不同信源概率是2-n

時(shí)

哈夫曼編碼效率達(dá)到100%信源概率相等時(shí)

哈夫曼編碼效率最低只有在概率分布很不均勻時(shí),哈夫曼編碼才會(huì)收到顯著的效果；信源分布均勻,一般不使用哈夫曼編碼哈夫曼編碼——特點(diǎn)2024/3/2628Huffman編碼在圖像壓縮中的實(shí)現(xiàn)

我們知道，對(duì)一幅圖像進(jìn)行編碼時(shí)，如果圖像的大小大于256時(shí)，這幅圖像的不同的碼字就有可能是很大，例如極限為256個(gè)不同的碼字。對(duì)整幅圖直接進(jìn)行Huffman編碼時(shí)，小分布的灰度值，就有可能具有很長(zhǎng)的編碼。如：100位以上，這樣不但達(dá)不到壓縮的效果反而會(huì)使數(shù)據(jù)量加大，應(yīng)該如何處理？2024/3/2629常用的且有效的方法是：將圖像分割成若干的小塊，對(duì)每塊進(jìn)行獨(dú)立的Huffman編碼。例如：分成的子塊，就可以大大降低不同灰度值的個(gè)數(shù)（最多是64而不是256）。2024/3/26305.2.2.Shannon－Fano編碼編碼步驟：①將信源符號(hào)按概率由大到小排列，概率相同的可以任意放②將概率分為近似相等的兩部分③進(jìn)行編碼，上半部分賦予0，下半部分賦予1④重復(fù)②③直至編碼完成S－F編碼舉例：編碼結(jié)果輸入數(shù)據(jù)對(duì)應(yīng)概率W10.4W20.3W30.1W40.1W50.06W60.0401101111011111001101111011111111111011011100100編碼效率：h＝

97.3%平均碼長(zhǎng)：R＝2.2bit2024/3/2631適用于少細(xì)節(jié)的圖像，如工程圖紙，文字，指紋等?；舅悸罚簩?duì)圖像中灰度相同的區(qū)域，可以通過(guò)確定以下特征來(lái)表示：5.3等值線(xiàn)編碼(1)包圍這個(gè)區(qū)域的外圍邊界，即輪廓的方向序列(2)輪廓的起始位置(行數(shù)和列數(shù))(3)輪廓所包圍區(qū)域的灰度值若區(qū)域有一定面積，則對(duì)上述三個(gè)特征編碼，可能比對(duì)區(qū)域內(nèi)每個(gè)象素都分配碼字節(jié)約，且圖像細(xì)節(jié)越少，節(jié)省的比特?cái)?shù)越多。2024/3/2632算法：尋找輪廓的算法計(jì)算輪廓方向序列的算法：T算法計(jì)算輪廓起始點(diǎn)的算法：IP算法先找到第一個(gè)起始點(diǎn)，并進(jìn)行第一個(gè)輪廓方向序列的計(jì)算，再找到第二個(gè)起始點(diǎn)，進(jìn)行第二個(gè)輪廓方向序列的計(jì)算，依次交叉進(jìn)行，直到找到所有輪廓。2024/3/26335.3.1輪廓方向序列的計(jì)算－T算法采用LML(LeftMostLooking)規(guī)則，沿輪廓前進(jìn)。例：LML規(guī)則：①先向左看②向前看③向右看④向后看利用LML規(guī)則，判斷所看的點(diǎn)是否灰度相等，若相等則前進(jìn)，若所有方向都不等，則為孤立點(diǎn)。共有四種象素灰度：代碼 灰度值表示為

00 a01 b10c11d選左上角的象素作為第一個(gè)輪廓的起始點(diǎn)！2024/3/2634若等值線(xiàn)上的點(diǎn)走了兩次，則按下列規(guī)則合并指示符：2.等值線(xiàn)上的點(diǎn)賦“指示符”第一次、第二次通過(guò)的方向標(biāo)志DAADRRDRRDDDAR

RAAA合并后RDAIP1ARRRRRRDDDDDDRRRARRRRRAAAAADR或RA或或或輸出輸入指示符號(hào)分為I，A，R，D四種，初始化時(shí)各點(diǎn)賦指示符號(hào)I，然后根據(jù)等值線(xiàn)輸入和輸出的方向按下列規(guī)則更改：2024/3/26353.用IP算法尋找新起始點(diǎn)通過(guò)建立一個(gè)比較表，并順序掃描搜索，利用判別規(guī)則確定掃描過(guò)的點(diǎn)是否為新的起始點(diǎn)。表的建立：(1)每掃描一行制一個(gè)表，掃描前表為空(2)對(duì)每一行掃描，從左到右逐象素進(jìn)行判別，若遇到標(biāo)記為A的點(diǎn)，將該點(diǎn)