計(jì)算機(jī)圖像處理-第六章課件

計(jì)算機(jī)圖像處理

郭永芳36160251@第六章圖像編碼與壓縮6.1概述6.1.1圖像數(shù)據(jù)壓縮的必要性與可能性數(shù)據(jù)壓縮主要研究數(shù)據(jù)的表示、傳輸、變換和編碼方法，目的是減少存儲(chǔ)數(shù)據(jù)所需的空間和傳輸所用的時(shí)間。圖像編碼與壓縮就是對(duì)圖像數(shù)據(jù)按一定的規(guī)則進(jìn)行變換和組合，達(dá)到以盡可能少的代碼（符號(hào)）來(lái)表示盡可能多的信息。圖像數(shù)據(jù)的特點(diǎn)之一是信息量大。海量數(shù)據(jù)需要巨大的存儲(chǔ)空間。如多媒體中的海量圖像數(shù)據(jù)，不進(jìn)行編碼壓縮處理，一張600M字節(jié)的光盤(pán)，只能存放20秒左右的640×480像素的圖像，可見(jiàn)沒(méi)有編碼壓縮，多媒體信息的保存有多么困難。在現(xiàn)代通信中，圖像傳輸已成為重要內(nèi)容。采用編碼壓縮技術(shù)，減少傳輸數(shù)據(jù)量，是提高通信速度、實(shí)現(xiàn)實(shí)時(shí)性的重要手段?？梢哉f(shuō)，沒(méi)有圖像編碼與壓縮技術(shù)的發(fā)展，大容量圖像信息的存儲(chǔ)與傳輸是難以實(shí)現(xiàn)的，多媒體、信息高速公路等新技術(shù)在實(shí)際中的應(yīng)用會(huì)碰到很大困難。從信息論觀點(diǎn)看，描述圖像信源的數(shù)據(jù)由有用數(shù)據(jù)和冗余數(shù)據(jù)兩部分組成。冗余數(shù)據(jù)主要表現(xiàn)為：編碼冗余（信息熵冗余）象素間冗余（空間冗余、時(shí)間冗余、結(jié)構(gòu)冗余）心理視覺(jué)冗余如果能減少或消除其中的1種或多種冗余，就能取得數(shù)據(jù)壓縮的效果。因此圖像信息的壓縮是可能的。但到底能壓縮多少，除了和圖像本身存在的冗余度大小有關(guān)外，很大程度取決于對(duì)圖像質(zhì)量的要求。

廣播電視壓縮比3∶1可視電話壓縮比1500∶1目前高效圖像壓縮編碼技術(shù)已能用硬件實(shí)現(xiàn)實(shí)時(shí)處理，在廣播電視、工業(yè)電視、電視會(huì)議、可視電話、傳真和互連網(wǎng)、遙感等多方面得到應(yīng)用。6.1.2圖像編碼壓縮的分類根據(jù)解壓重建后的圖像和原始圖像之間是否具有誤差，圖像編碼壓縮分為無(wú)誤差（亦稱無(wú)失真、無(wú)損、信息保持）編碼和有誤差（有失真或有損）編碼兩大類。根據(jù)編碼作用域劃分，圖像編碼為空間域編碼和變換域編碼兩大類。圖像壓縮無(wú)損編碼有損編碼霍夫曼編碼行程編碼算術(shù)編碼預(yù)測(cè)編碼變換編碼其它編碼6.2圖像保真度準(zhǔn)則描述解碼圖像相對(duì)原始圖像偏離程度的測(cè)度稱為保真度?？煞忠韵聝深悾?.2.1客觀保真度準(zhǔn)則

最常用的客觀保真度準(zhǔn)則是原圖像和解碼圖像之間的均方根誤差和均方根信噪比兩種。6.2.2主觀保真度準(zhǔn)則

很多解壓圖最終是供人觀看的，一種常用的方法是對(duì)一組（不少于20人）觀察者顯示圖像，并將他們對(duì)該圖像的評(píng)分取平均，用來(lái)評(píng)價(jià)一幅圖像的主觀質(zhì)量。原圖100:1400:1600:1圖像的熵為圖像的平均碼長(zhǎng)為冗余度為編碼效率為

6.3統(tǒng)計(jì)編碼方法6.3.1圖像冗余度和編碼效率根據(jù)Shannon無(wú)干擾信息保持編碼定理，若對(duì)原始圖像數(shù)據(jù)的信息進(jìn)行信源的無(wú)失真圖像編碼，壓縮后平均碼率存在一個(gè)下限，這個(gè)下限是信源信息熵H。理論上最佳信息保持編碼的平均碼長(zhǎng)可以無(wú)限接近信源信息熵H。但總是大于或等于圖像的信息量H（熵）。6.3.2霍夫曼編碼Huffman編碼是1952年由Huffman提出的一種編碼方法。這種編碼方法根據(jù)源數(shù)據(jù)符號(hào)發(fā)生的概率進(jìn)行編碼。在源數(shù)據(jù)中出現(xiàn)概率越大的符號(hào)，編碼以后相應(yīng)的碼長(zhǎng)越短；出現(xiàn)概率越小的符號(hào)，其碼長(zhǎng)越長(zhǎng)，從而達(dá)到用盡可能少的碼符表示源數(shù)據(jù)。它在無(wú)損變長(zhǎng)編碼方法中是最佳的。下面通過(guò)實(shí)例來(lái)說(shuō)明此方法。設(shè)輸入數(shù)據(jù)為，其頻率分布分別為P(x1)=0.4，P(x2)=0.3，P(x3)=0.1，P(x4)=0.1，P(x5)=0.06，P(x6)=0.04。求其最佳霍夫曼編碼編碼方法是：①把輸入元素按概率從小到大排列起來(lái)，然后把概率最小的兩個(gè)元素概率加起來(lái);②把它同其余元素概率由小到大排序，然后把兩個(gè)最小概率加起來(lái)，再重新排隊(duì);③重復(fù)②，直到最后只剩下一個(gè)和為1的概率為止。④在上述工作完畢之后，從最后兩個(gè)概率開(kāi)始逐步向前進(jìn)行編碼。對(duì)于概率大的消息賦予0，小的賦予1。一般用二叉樹(shù)方法實(shí)現(xiàn)Huffman編碼較為便利。問(wèn)題：計(jì)算該信源的熵、編碼后的平均碼長(zhǎng)，編碼效率及冗余度，并思考對(duì)于同一圖像采用Huffman編碼，編碼是否唯一？元素xi概率P(xi)編碼wix1x2x3x4x5x60.40.30.10.10.06100011010001010元素xi概率P(xi)編碼wix1x2x3x4x5x60.40.30.10.10.060.04100011010001010010110.61x100

x20.3011

x30.20100

x401011

x601010

x50.10.040.060.10.10.30.40000011111Huffman編碼樹(shù)及編碼過(guò)程：6.3.5行程編碼（RunLengthEncoding）

基本原理：通過(guò)改變圖像的描述方式，來(lái)實(shí)現(xiàn)壓縮。將一行中顏色值相同的相鄰像素用一個(gè)計(jì)數(shù)值和該顏色值來(lái)代替。

舉例說(shuō)明：aaaa

bbb

cc

d

eeeee

fffffff(共22*8=176bits)

4a3b2c1d5e7f(共12*8=96bits)

若計(jì)數(shù)值用3bit來(lái)表示

(共6*3+6*8=66bits)黑白二值圖像：

默認(rèn)起始為白，碼流為：4，5，7，5，9，3，3默認(rèn)起始為黑，碼流為：0，4，5，7，5，9，3，3一維行程編碼和二維行程編碼：圖像的一般特點(diǎn)：像素之間距離越近，其相關(guān)性越強(qiáng)。要提高行程編碼的效率，就希望能夠通過(guò)一定的掃描順序，使相鄰像素值相等的情況盡可能多。一維行程編碼只考慮了消除行內(nèi)像素之間的相關(guān)性，卻沒(méi)有考慮到某種方向間的相關(guān)性。二維行程編碼可先將圖像分塊，再對(duì)各子塊的像素按一定的掃描路線進(jìn)行掃描。例如：混合編碼混合編碼實(shí)現(xiàn)的可能性及有效性：回顧一下講過(guò)的幾個(gè)內(nèi)容的特點(diǎn)1.行程編碼：擅長(zhǎng)于重復(fù)數(shù)字的壓縮。2.Huffman編碼：擅長(zhǎng)于像素個(gè)數(shù)的出現(xiàn)頻度不同的編碼。例：aaaa

bbb

cc

d

eeeee

fffffff（共22*8=176bits）

432157

行程編碼：4a3b2c1d5e7f（共6*(8+3)=66bits）17666Huffman編碼：f=01e=11a=10b=001c=0001d=00001010101010001001001000100010000111111111101010101010101（共7*2+5*2+4*2+3*3+2*4+1*4=53bits）17653Huffman與行程編碼混合：41030012000110000511701

（共3+2+3+3+3+4+3+4+3+2+3+2=35bits）17635以上三種編碼的數(shù)據(jù)量分別為原始數(shù)據(jù)量的37.5%，30.1%和19.9%。

6.3.3費(fèi)諾-仙儂（Fannon-Shannon）編碼二分法費(fèi)諾-仙儂編碼的步驟如下：

（1）首先統(tǒng)計(jì)出每個(gè)符號(hào)出現(xiàn)的概率；

（2）從上（左）到下（右）對(duì)上述概率從大到小排序；

（3）從這個(gè)概率集合中的某個(gè)位置將其分為兩個(gè)子集合，并盡量使兩個(gè)子集合的概率和近似相等，給前面一個(gè)子集合賦值為0，后面一個(gè)子集合賦值為1；

（4）重復(fù)步驟（3），直到各個(gè)子集合中只有一個(gè)元素為止；

（5）將每個(gè)元素所屬的子集合的值依次串起來(lái)，即可得到各個(gè)元素的費(fèi)諾-仙儂編碼。

6.3.4算術(shù)編碼理論上，用霍夫曼方法對(duì)源數(shù)據(jù)流進(jìn)行編碼可達(dá)最佳編碼效率，但由于計(jì)算機(jī)中存儲(chǔ)、處理數(shù)據(jù)的最小單位是“位”，因此實(shí)際編碼效果不會(huì)達(dá)到理論上的壓縮比。例如，源數(shù)據(jù)流由X和Y兩個(gè)符號(hào)構(gòu)成，它們出現(xiàn)的概率分別為2/3和1/3，理論上，根據(jù)符號(hào)X的熵確定的最優(yōu)碼長(zhǎng)為：H(X)=-log2(2/3)=0.585(bit)若要達(dá)到最佳編碼效果，相應(yīng)于X的碼長(zhǎng)為0.585位。但由于計(jì)算機(jī)中不可能有非整數(shù)位出現(xiàn)，那么受硬件的限制，編碼只能按“位”進(jìn)行。用霍夫曼方法對(duì)這兩個(gè)符號(hào)進(jìn)行編碼，得到X和Y的代碼分別為0和1，顯然出現(xiàn)概率大的符號(hào)不能給予較短的代碼。算術(shù)編碼沒(méi)有沿用編碼技術(shù)中用一個(gè)特定的代碼代替一個(gè)輸入符號(hào)的一般做法，而是把要壓縮處理的整段數(shù)據(jù)映射到一段實(shí)數(shù)半開(kāi)區(qū)間[0，1）內(nèi)的某一區(qū)段，構(gòu)造出小于1且大于或等于0的數(shù)值，這個(gè)數(shù)值是輸入數(shù)據(jù)流的惟一可譯代碼。算術(shù)編碼有兩種模式，均可用硬件實(shí)現(xiàn)。一種是基于信源概率統(tǒng)計(jì)特性的固定編碼模式，另一種是針對(duì)未知信源概率模型的自適應(yīng)模式。算術(shù)編碼的實(shí)現(xiàn)方法要比霍夫曼編碼復(fù)雜一些，但有關(guān)研究表明，算術(shù)編碼一般要優(yōu)于Huffman編碼。例如，在JPEG擴(kuò)展系統(tǒng)中，就用算術(shù)編碼取代了霍夫曼編碼；在MPEG-4標(biāo)準(zhǔn)中，對(duì)形狀編碼采用的也是算術(shù)編碼。自適應(yīng)模式中各個(gè)符號(hào)的概率初始值都相同，它們依據(jù)出現(xiàn)的符號(hào)而相應(yīng)地改變。只要編碼器和解碼器都使用相同的初始值和相同的改變值的方法，那么它們的概率模型將保持一致。下面結(jié)合一個(gè)實(shí)例來(lái)闡述固定模式的算術(shù)編碼的具體方法。

設(shè)有一個(gè)五符號(hào)信源的待編碼數(shù)據(jù)序列“dacab”，信源中各符號(hào)出現(xiàn)的概率依次為：P(a)=0.4，P(b)=0.2，P(c)=0.2，P(d)=0.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,0.8）,d=［0.8,1.0）StartN=StartB+LeftC×L

EndN=StartB+RightC×L

第一個(gè)被壓縮的符號(hào)為“d”，其初始賦值區(qū)間為［0.8,1.0）；第二個(gè)被壓縮的符號(hào)為“a”，由于前面的符號(hào)“d

”的取值區(qū)間被限制在［0.8,1.0）范圍內(nèi)，所以“a

”的取值范圍應(yīng)該在前一符號(hào)區(qū)間［0.8,1.0）的［0,0.4）范圍內(nèi)。為便于討論，再給出一組關(guān)系式：StartN=0.8+0×(1.0-0.8)=0.8EndN=0.8+0.4×(1.0-0.8)=0.88即“a”的實(shí)際編碼區(qū)間在［0.8,0.88)之間。式中，StartN、EndN分別表示新子區(qū)間的起始位置和結(jié)束位置，StartB表示前一子區(qū)間的起始位置，L為前一子區(qū)間的長(zhǎng)度，LeftC、RightC分別表示當(dāng)前編碼符號(hào)的初始區(qū)間的左端和右端。根據(jù)上式可知：第三個(gè)被壓縮的符號(hào)為“c”，其編碼取值范圍應(yīng)在［0.8,0.88）區(qū)間的［0.6,0.8）的子區(qū)間內(nèi)，據(jù)上式可知：StartN=0.8+0.6×(0.88-0.8)=0.848EndN=0.8+0.8×(0.88-0.8)=0.864第四個(gè)被壓縮的符號(hào)為“a”，同理，根據(jù)上式得［0.848，0.8544）第五個(gè)被壓縮的符號(hào)為“b”，同理，根據(jù)上式得［0.84856，0.85144）

至此,數(shù)據(jù)序列“dacab”已被描述為一個(gè)實(shí)數(shù)區(qū)間［0.85056,0.85184），或者說(shuō)在此區(qū)間內(nèi)的任一實(shí)數(shù)值都惟一對(duì)應(yīng)該數(shù)據(jù)序列。這樣，就可以用一個(gè)實(shí)數(shù)表示這一數(shù)據(jù)序列。我們把區(qū)間［0.85056,0.85184）用二進(jìn)制形式表示為［0.110110011011,0.110110100001）。從這個(gè)區(qū)間可以看出，0.1101101位于這個(gè)區(qū)間內(nèi)并且其編碼最短，故把其作為數(shù)據(jù)序列“dacab”的編碼輸出?？紤]到算術(shù)編碼中任一數(shù)據(jù)序列的編碼都含有“0.”，所以在編碼時(shí)，可以不考慮“0.”，于是把1101101作為本例中的數(shù)據(jù)序列的算術(shù)編碼。由此可見(jiàn)，數(shù)據(jù)序列“dacab”用7比特的二進(jìn)制代碼就可以表示，平均碼長(zhǎng)為1.4比特／字符。

解碼是編碼的逆過(guò)程，根據(jù)編碼時(shí)的概率分配表和壓縮后數(shù)據(jù)代碼所在的范圍，確定代碼所對(duì)應(yīng)的每一個(gè)數(shù)據(jù)符號(hào)。在完成對(duì)第一個(gè)符號(hào)的解碼后，設(shè)法去掉第一個(gè)符號(hào)對(duì)區(qū)間的影響，再用相同的方法找到下一個(gè)符號(hào)。重復(fù)此過(guò)程，直到完成解碼。6.6圖像壓縮的標(biāo)準(zhǔn)圖像壓縮的國(guó)際標(biāo)準(zhǔn)主要是由國(guó)際標(biāo)準(zhǔn)化組織（ISO）和國(guó)際電報(bào)電話咨詢委員會(huì)（CCITT）制訂的。6.6.1靜態(tài)圖像壓縮標(biāo)準(zhǔn)JPEG(JointPictureExpertGroup)格式即聯(lián)合圖像專家組,是由ISO和CCITT為靜態(tài)圖像所建立的第一個(gè)國(guó)際數(shù)字圖像壓縮標(biāo)準(zhǔn)，1991年開(kāi)始使用。在相同圖像質(zhì)量條件下，JPEG文件擁有比其他圖像文件格式更高的壓縮比。JPEG目前被廣泛應(yīng)用于多媒體和網(wǎng)絡(luò)程序中，是現(xiàn)今萬(wàn)維網(wǎng)中使用最廣泛的兩種圖像文件格式之一。(JPEG和GIF成為HTML語(yǔ)法選用的圖像格式。)JPEG定義了三種編碼系統(tǒng)：DCT（離散余弦變換）有損編碼系