第十五講 圖像的編碼與壓縮

Lecture15

ImageCodingand

CompressionPurpose

圖像壓縮的概念、目的和意義圖像的霍夫曼編碼、香農(nóng)編碼、算術(shù)編碼、行程編碼方法ExplainContents

了解圖像壓縮的目的和意義，熟悉圖像保真度準(zhǔn)則掌握?qǐng)D像霍夫曼編碼、香農(nóng)編碼、算術(shù)編碼、行程編碼方法

圖像壓縮(ImageCompression)的概念

數(shù)據(jù)壓縮的研究?jī)?nèi)容包括數(shù)據(jù)的表示、傳輸、變換和編碼方法，目的是減少存儲(chǔ)數(shù)據(jù)所需的空間和傳輸所用的時(shí)間。

圖像壓縮就是在一個(gè)可以接受的還原狀況的前提下用盡可能少的比特?cái)?shù)來(lái)表示源信號(hào)，即把需要存儲(chǔ)或傳輸?shù)膱D像數(shù)據(jù)的比特?cái)?shù)減少到最少程度。圖像壓縮是通過(guò)編碼實(shí)現(xiàn)的。

概述

圖像數(shù)據(jù)壓縮的必要性

圖像數(shù)據(jù)的特點(diǎn)之一是信息量大。海量數(shù)據(jù)需要巨大的存儲(chǔ)空間。如多媒體中的海量圖像數(shù)據(jù)，不進(jìn)行編碼壓縮處理，一張600M字節(jié)的光盤，只能存放20秒左右的640×480像素的圖像。沒(méi)有編碼壓縮，多媒體信息保存有多么困難是可想而知的。在現(xiàn)代通信中，圖像傳輸已成為重要內(nèi)容之一。采用編碼壓縮技術(shù)，減少傳輸數(shù)據(jù)量，是提高通信速度的重要手段?？梢?jiàn)，沒(méi)有圖像編碼與壓縮技術(shù)的發(fā)展，大容量圖像信息的存儲(chǔ)與傳輸是難以實(shí)現(xiàn)的，多媒體、信息高速公路等新技術(shù)在實(shí)際中的應(yīng)用會(huì)遇到很大困難。概述

圖像數(shù)據(jù)壓縮的可能性概述

從信息論觀點(diǎn)看，描述圖像信源的數(shù)據(jù)由有用數(shù)據(jù)和冗余數(shù)據(jù)兩部分組成。信息量數(shù)據(jù)量冗余量

冗余量是可以壓縮的，在實(shí)際應(yīng)用中應(yīng)盡量保證去除冗余量而不會(huì)減少信息量，即壓縮數(shù)據(jù)在一定條件可以近似恢復(fù)。數(shù)據(jù)冗余(DataRedundancy)

編碼冗余(CodingRedundancy)等長(zhǎng)編碼平均碼長(zhǎng)為3變長(zhǎng)編碼平均碼長(zhǎng)為2.7數(shù)據(jù)冗余

像素間冗余(InterpixelRedundancy)

圖像是由按一定規(guī)則排列起來(lái)的像素組成，圖像中相鄰像素的灰度往往相同或相近，這就稱為像素間冗余或空間冗余。數(shù)據(jù)冗余

心理視覺(jué)冗余(PsychovisualRedundancy)175K1.46M

受生理和心理上的影響，人眼對(duì)黑白和彩色信息的分辨率是有限的。光學(xué)上不一致的圖像在視覺(jué)上可能是一樣。圖像壓縮系統(tǒng)模型信源信源編碼器信道編碼器通信線路或存儲(chǔ)介質(zhì)信源解碼器信道解碼器信宿壓縮的有效性編碼的可靠性圖像保真度準(zhǔn)則描述解碼圖像相對(duì)原始圖像偏離程度的測(cè)度一般稱為保真度。常用的保真度準(zhǔn)則可分為兩大類：客觀保真度準(zhǔn)則和主觀保真度準(zhǔn)則?？陀^保真度準(zhǔn)則最常用的客觀保真度準(zhǔn)則是原圖像和解碼圖像之間的均方根誤差和均方根信噪比兩種。主觀保真度準(zhǔn)則

很多解壓圖最終是供人觀看的，一種常用的方法是讓一組（不少于20人）觀察者觀察圖像并給該圖像評(píng)分，將他們對(duì)該圖像的評(píng)分取平均，作為這幅圖像的質(zhì)量。信息論要素(ElementsofInformationTheory)

熵(Entropy)根據(jù)Shannon無(wú)干擾信息保持編碼定理，若對(duì)原始圖像數(shù)據(jù)的信息進(jìn)行無(wú)失真圖像編碼，壓縮后平均碼長(zhǎng)存在一個(gè)下限，這個(gè)下限是圖像信息熵H。理論上最佳信息保持編碼的平均碼長(zhǎng)可以無(wú)限接近圖像信息熵H。但總是大于或等于圖像的熵H。

平均碼長(zhǎng)(AverageCodeLength)平均信息量度，圖像中各灰度級(jí)比特?cái)?shù)的統(tǒng)計(jì)平均值。M:灰度級(jí)數(shù)Pk:灰度級(jí)Wk出現(xiàn)的概率

編碼效率CodingEfficiency

冗余度Redundancy熵編碼目的：使R盡量減少至H

信息論要素(ElementsofInformationTheory)例題設(shè)一離散信源如下：

信源概率編碼求信源X的熵、平均碼長(zhǎng)和編碼效率。解：

比特平均碼長(zhǎng)：編碼效率：比特

變長(zhǎng)最佳編碼定理

對(duì)概率大的消息符號(hào)賦予短碼字，而對(duì)概率小的信息符號(hào)賦予長(zhǎng)碼字，則編碼的平均碼長(zhǎng)一定最短。

如：WmWnPm<PnPm：概率低Pn：概率高

tm>tntm：長(zhǎng)碼tn：短碼符合定理的平均碼長(zhǎng)不符合定理的平均碼長(zhǎng)

唯一可譯編碼

所編碼字序列能唯一地譯出來(lái)。單義性、非續(xù)長(zhǎng)碼是唯一可譯編碼。單義性代碼：任意一個(gè)有限長(zhǎng)的碼字序列只能被唯一地分割成一個(gè)個(gè)碼字。非續(xù)長(zhǎng)代碼：集合中的碼字不能由其他碼字在后面添加碼元構(gòu)成。如：信源概率碼I碼II碼III碼IVW11/20000W21/4011001W31/8100110011W41/810111110111碼I：非單義性、續(xù)長(zhǎng)碼如：00110W1W2W3W4W1W1W3W3W1W1W1W3W3W2碼II：非單義性、續(xù)長(zhǎng)碼如：

010011W1W2W3W4W1W2W1W1W4

W1W2W1W3W2W2W1W2W1W1W2W2碼III：?jiǎn)瘟x性、非續(xù)長(zhǎng)碼如：010110111W1W2W3W4碼IV：?jiǎn)瘟x性、續(xù)長(zhǎng)碼如：0010110111W1W2W3W4單義非續(xù)長(zhǎng)代碼平均碼長(zhǎng)最短單義代碼的充要條件：

D：代碼中的碼元種類；n：代碼中的碼字個(gè)數(shù)；ti：第i個(gè)碼字的碼長(zhǎng)；如上例：圖像編碼壓縮的分類圖像壓縮無(wú)損編碼有損編碼霍夫曼編碼行程編碼算術(shù)編碼預(yù)測(cè)編碼變換編碼其它編碼根據(jù)解壓重建后的圖像和原始圖像之間是否具有誤差，圖像編碼壓縮分為無(wú)損（亦稱無(wú)失真、無(wú)誤差、信息保持）編碼和有損（有失真或有誤差）編碼兩大類。Huffman編碼是1952年由Huffman提出的一種編碼方法。這種編碼方法是根據(jù)信源數(shù)據(jù)符號(hào)發(fā)生的概率進(jìn)行編碼的?；舴蚵幋a(HuffmanCoding)思想：在信源數(shù)據(jù)中出現(xiàn)概率越大的符號(hào)，編碼以后相應(yīng)的碼長(zhǎng)越短；出現(xiàn)概率越小的符號(hào)，其碼長(zhǎng)越長(zhǎng)，從而達(dá)到用盡可能少的碼符表示信源數(shù)據(jù)。它在無(wú)損變長(zhǎng)編碼方法中是最佳的。把輸入符號(hào)按出現(xiàn)的概率從大到小排列起來(lái),接著把概率最小的兩個(gè)符號(hào)的概率求和;把它（概率之和）同其余符號(hào)概率由大到小排序,然后把兩個(gè)最小概率求和;重復(fù)2,直到最后只剩下兩個(gè)概率為止。在上述工作完畢之后，從最后兩個(gè)概率開(kāi)始逐步向前進(jìn)行編碼。對(duì)于概率大的消息賦予0，小的賦予1。在反向進(jìn)行的過(guò)程中，若概率不變，保留原碼字；若概率分裂為兩個(gè)，前幾位保留原碼字，最后一位一個(gè)賦“0”，另一個(gè)賦“1”碼。

編碼方法：符號(hào)集x1x2x3x4x5x6概率分布0.400.200.120.110.090.08Huffman編碼符號(hào)集經(jīng)排序的概率分布第一次合并后排序第二次合并后排序第三次合并后排序第四次合并后排序第五次合并后排序x10.400.400.400.400.601x20.200.200.230.370.40x30.120.170.200.23x40.110.120.17x50.090.11x60.08符號(hào)集經(jīng)排序的概率分布第一次合并后排序第二次合并后排序第三次合并后排序第四次合并后排序第五次合并后排序x10.400.400.400.400.601x20.200.200.230.370.40x30.120.170.200.23x40.110.120.17x50.090.11x60.0801100010100000111100000000101001101001100100011符號(hào)集x1x2x3x4x5x6概率分布0.400.200.120.110.090.08Huffman編碼100001001100100011

用二叉樹(shù)方法實(shí)現(xiàn)Huffman編碼方法也較為便利。

計(jì)算該信源的熵、編碼后的平均碼長(zhǎng)，并思考對(duì)于同一圖像采用Huffman編碼，編碼是否唯一？？0.230.4

x10.6

0.11

x4

10

100.37

0.20

x2

0.08

x60.09

x50.17

10

10

100.12

x3香農(nóng)編碼(ShannonCoding)編碼方法：1、將輸入灰度級(jí)按出現(xiàn)的概率由大到小排列；2、按計(jì)算各概率對(duì)應(yīng)的碼長(zhǎng)；3、計(jì)算各灰度級(jí)對(duì)應(yīng)的累加概率：

4、把各個(gè)累加概率由十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)：轉(zhuǎn)換規(guī)則：乘2取整，先取的整數(shù)為高位，后取的整數(shù)為低位。5、將二進(jìn)制表示的累加概率去掉多于ti的尾數(shù)，即得Wi對(duì)應(yīng)的碼字。算術(shù)編碼(ArithmeticCoding)思想：

按照符號(hào)序列的出現(xiàn)概率區(qū)間分割，用一個(gè)實(shí)數(shù)代表一個(gè)數(shù)據(jù)流的輸入符號(hào)，再將這個(gè)實(shí)數(shù)轉(zhuǎn)化為一定位數(shù)的二進(jìn)制代碼。對(duì)于較長(zhǎng)的消息，二進(jìn)制代碼的位數(shù)也會(huì)增加。它們是通過(guò)算術(shù)運(yùn)算逐步形成碼字的，因而得名。

設(shè)四階Markov信源符號(hào)集為｛a,b,c,d｝，其概率分布為｛0.2,0.2,0.4,0.2｝。（1）若對(duì)該信源進(jìn)行Huffman編碼，可得其平均碼長(zhǎng)為2.0比特/字符（2）若信源發(fā)出序列為｛b,c,a,c,d｝，算數(shù)編碼過(guò)程如下：各個(gè)數(shù)據(jù)符號(hào)在半封閉實(shí)數(shù)區(qū)間[0，1）內(nèi)按概率進(jìn)行賦值范圍設(shè)定為數(shù)據(jù)流bcacd編碼區(qū)間[0.2,0.4）[0.28,0.36）[0.28,0.296）[0.2864,0.2928）[0.29152,0.2928）區(qū)間長(zhǎng)度0.20.080.0160.00640.00128新子區(qū)間左端＝前一子區(qū)間左端＋新子區(qū)間左邊累加概率×前子區(qū)間長(zhǎng)度新子區(qū)間長(zhǎng)度＝當(dāng)前區(qū)間概率×前子區(qū)間長(zhǎng)度行程編碼(Run-