第五章圖像編碼(1)

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

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

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

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

1）彩色視頻信息

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

640*480*24*30=221.12M

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

4

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

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

1654*2337*1=3888768bit

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

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

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

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

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

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

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

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

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

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

因此，當(dāng)M

等于8時，H

的范圍從0到3，即H＝0～log2M，其中H＝3說明信號的隨機程度最大。192.圖像的平均碼字長度

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

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

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

在R≧H

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

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

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

時

哈夫曼編碼效率達到100%信源概率相等時

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

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

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

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

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