數(shù)字圖像處理(探索霍夫曼編碼)_第1頁(yè)
數(shù)字圖像處理(探索霍夫曼編碼)_第2頁(yè)
數(shù)字圖像處理(探索霍夫曼編碼)_第3頁(yè)
數(shù)字圖像處理(探索霍夫曼編碼)_第4頁(yè)
數(shù)字圖像處理(探索霍夫曼編碼)_第5頁(yè)
已閱讀5頁(yè),還剩6頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、探索霍夫曼編碼一、緒論在學(xué)習(xí)完了本學(xué)期的數(shù)字圖像處理課程后,我對(duì)圖像壓縮這部分內(nèi)容產(chǎn)生了興趣,通過深入學(xué)習(xí),我用matlab實(shí)現(xiàn)了霍夫曼編碼,成功地壓縮了圖像。隨著信息時(shí)代的來(lái)臨,多媒體已經(jīng)被人們廣泛的應(yīng)用于生活的各個(gè)領(lǐng)域。我們每天接受的信息開始以Gb計(jì),眾所周知Gb是一個(gè)很大的單位,多媒體是指文字、聲音、圖形和圖像等各種媒體,它能比單純文字傳輸更多、更生動(dòng)的信息,與此同時(shí)它的數(shù)據(jù)量也比文字要大得多,例如一幅分辨率為1024768、顏色24位的圖像將占到2.3MB的存儲(chǔ)空間,1秒鐘沒有任何壓縮的數(shù)字視頻圖像需要上百兆字節(jié)的存儲(chǔ)空間,這是目前的存儲(chǔ)空間和傳輸寬帶不能承受的。采用數(shù)據(jù)壓縮技術(shù)去除不

2、必要的冗余數(shù)據(jù)以減少所需傳輸?shù)臄?shù)據(jù)量是必然的選擇。而我正是對(duì)如何編碼使圖像壓縮而不至于影響人的體驗(yàn)產(chǎn)生興趣的。上課時(shí)我了解到圖像數(shù)據(jù)存在3種冗余:結(jié)構(gòu)冗余、統(tǒng)計(jì)冗余、以及心里視覺冗余。通過上網(wǎng)搜尋資料我也了解到編碼也是分3種的:統(tǒng)計(jì)編碼、預(yù)測(cè)編碼,以及變換編碼。我主要深入學(xué)習(xí)了用統(tǒng)計(jì)編碼的方法來(lái)去除統(tǒng)計(jì)冗余。二、霍夫曼編碼概述赫夫曼(Huffman)編碼是1952年提出的,是一種比較經(jīng)典的信息無(wú)損熵編碼,該編碼依據(jù)變長(zhǎng)最佳編碼定理,應(yīng)用Huffman算法而產(chǎn)生。Huffman編碼是一種基于統(tǒng)計(jì)的無(wú)損編碼。根據(jù)變長(zhǎng)最佳編碼定理,Huffman編碼步驟如下:(1)將信源符號(hào)xi按其出現(xiàn)的概率,由大

3、到小順序排列。(2)將兩個(gè)最小的概率的信源符號(hào)進(jìn)行組合相加,并重復(fù)這一步驟,始終將較大的概率分支放在上部,直到只剩下一個(gè)信源符號(hào)且概率達(dá)到1.0為止;(3)對(duì)每對(duì)組合的上邊一個(gè)指定為1,下邊一個(gè)指定為0(或相反:對(duì)上邊一個(gè)指定為0,下邊一個(gè)指定為1);(4)畫出由每個(gè)信源符號(hào)到概率1.0處的路徑,記下沿路徑的1和0;(5)對(duì)于每個(gè)信源符號(hào)都寫出1、0序列,則從右到左就得到非等長(zhǎng)的Huffman碼。Huffman編碼的特點(diǎn)是:(1)Huffman編碼構(gòu)造程序是明確的,但編出的碼不是唯一的,其原因之一是兩個(gè)概率分配碼字“0”和“1”是任意選擇的(大概率為“0”,小概率為“1”,或者反之)。第二原因

4、是在排序過程中兩個(gè)概率相等,誰(shuí)前誰(shuí)后也是隨機(jī)的。這樣編出的碼字就不是唯一的。(2)Huffman編碼結(jié)果,碼字不等長(zhǎng),平均碼字最短,效率最高,但碼字長(zhǎng)短不一,實(shí)時(shí)硬件實(shí)現(xiàn)很復(fù)雜(特別是譯碼),而且在抗誤碼能力方面也比較差。(3)Huffman編碼的信源概率是2的負(fù)冪時(shí),效率達(dá)100%,但是對(duì)等概率分布的信源,產(chǎn)生定長(zhǎng)碼,效率最低,因此編碼效率與信源符號(hào)概率分布相關(guān),故Huffman編碼依賴于信源統(tǒng)計(jì)特性,編碼前必須有信源這方面的先驗(yàn)知識(shí),這往往限制了霍夫曼編碼的應(yīng)用。(4)Huffman編碼只能用近似的整數(shù)位來(lái)表示單個(gè)符號(hào),而不是理想的小數(shù),這也是Huffman編碼無(wú)法達(dá)到最理想的壓縮效果的原

5、因假設(shè)一個(gè)文件中出現(xiàn)了8種符號(hào)S0,S1,S2,S3,S4,S5,S6,S7,那么每種符號(hào)要編碼,至少需要3比特。假設(shè)編碼成000,001,010,011,100,101,110,111那么符號(hào)序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成000001111000001110010010011100101000000001,共用了42比特。我們發(fā)現(xiàn)S0,S1,S2這三個(gè)符號(hào)出現(xiàn)的頻率比較大,其它符號(hào)出現(xiàn)的頻率比較小,如果我們采用一種編碼方案使得S0,S1,S2的碼字短,其它符號(hào)的碼字長(zhǎng),這樣就能夠減少占用的比特?cái)?shù)。例如,我們采用這樣的編碼方案:S0到S7的碼字分別01,

6、11,101,0000,0001,0010,0011,100,那么上述符號(hào)序列變成011110001110011101101000000010010010111,共用了39比特,盡管有些碼字如S3,S4,S5,S6變長(zhǎng)了(由3位變成4位),但使用頻繁的幾個(gè)碼字如S0,S1變短了,所以實(shí)現(xiàn)了壓縮??捎上旅娴牟襟E得到霍夫曼碼的碼表首先把信源中的消息出現(xiàn)的頻率從小到大排列。每一次選出頻率最小的兩個(gè)值,作為二叉樹的兩個(gè)葉子節(jié)點(diǎn),將和作為它們的根節(jié)點(diǎn),這兩個(gè)葉子節(jié)點(diǎn)不再參與比較,新的根節(jié)點(diǎn)參與比較。重復(fù)(2),直到最后得到和為1的根節(jié)點(diǎn)。將形成的二叉樹的左節(jié)點(diǎn)標(biāo)0,右節(jié)點(diǎn)標(biāo)1。把從最上面的根節(jié)點(diǎn)到最下面

7、的葉子節(jié)點(diǎn)途中遇到的0,1序列串起來(lái),就得到了各個(gè)符號(hào)的編碼。上面的例子用Huffman編碼的過程如圖下圖所示,其中圓圈中的數(shù)字是新節(jié)點(diǎn)產(chǎn)生的順序。Huffman編碼的二叉樹示意圖信源的各個(gè)消息從S0到S7的出現(xiàn)概率分別為4/14,3/14,2/14,1/14,1/14,1/14,1/14,1/14。計(jì)算編碼效率為98.5%,編碼的冗余只有1.5%,可見霍夫曼編碼效率很高。產(chǎn)生Huffman編碼需要對(duì)原始數(shù)據(jù)掃描兩遍。第一遍掃描要精確地統(tǒng)計(jì)出原始數(shù)據(jù)中,每個(gè)值出現(xiàn)的頻率,第二遍是建立Huffman樹并進(jìn)行編碼。由于需要建立二叉樹并遍歷二叉樹生成編碼,因此數(shù)據(jù)壓縮和還原速度都較慢,但簡(jiǎn)單有效,因

8、而得到廣泛的應(yīng)用。三、霍夫曼編碼應(yīng)用本文霍夫曼編碼壓縮圖像的步驟如下:讀入圖像,并把它用矩陣表示。統(tǒng)計(jì)圖像顏色的種數(shù)。統(tǒng)計(jì)各種顏色值出現(xiàn)的概率,并把它們按從大到小的順序排列。進(jìn)行霍夫曼編碼的計(jì)算: 定義一個(gè)矩陣M,M矩陣的第一行,存放的是需要編碼的各個(gè)顏色值出現(xiàn)的概率,并且按照從大到小排列順序,然后再將第一行從后往前兩兩相加(即概率最小的兩個(gè)數(shù)相加),把相加得到的結(jié)果放到第二行,然后再將第二行重新進(jìn)行排序,依此類推,一直到最后一行,這時(shí)最后一行只有兩個(gè)概率,并且相加肯定為1 。 對(duì)M矩陣的數(shù)值進(jìn)行霍夫曼編碼:首先建立N矩陣,用來(lái)存放編碼的碼字。然后將字符0,賦給最后一行的第一小段,再將字符1,

9、賦給最后一行的第二小段,在M矩陣中,由于每一行的最后兩個(gè)數(shù),都是這一行中概率最小的兩個(gè)數(shù),所以將倒數(shù)第二行的最后兩個(gè)數(shù)進(jìn)行相加,然后用相加的結(jié)果到倒數(shù)第一行中去尋找,肯定會(huì)在倒數(shù)第一行中找到一樣的值,然后記錄下來(lái)在倒數(shù)第一行中這個(gè)值的位置,再將這個(gè)在M矩陣中的位置對(duì)應(yīng)到N矩陣中, 將N矩陣中的該位置的字符賦給倒數(shù)第二行的第二小段和第三小段,最后在給第二小段的后面賦字符0,給第三小段后面賦字符1,然后將在最后一行找到的那個(gè)數(shù)的左邊的數(shù),一一對(duì)應(yīng)到上一行去,右邊的數(shù),向左串一位,再對(duì)應(yīng)到上一行去,這樣依此類推,那么在N矩陣的第一行,可以得到最后的編碼。實(shí)驗(yàn)程序見附錄實(shí)驗(yàn)結(jié)果如下:壓縮效果對(duì)比:圖像

10、大小比較: 從圖中我們可以明顯的對(duì)比出來(lái),經(jīng)過了霍夫曼編碼壓縮圖片后,在畫質(zhì)上看不出明顯的區(qū)別,但是實(shí)際上壓縮后的圖片大小是原來(lái)的五分之一,占用空間是原來(lái)的三分之一。四、附錄%霍夫曼編碼實(shí)現(xiàn)圖像壓縮代碼:tic;clearz=imread(原圖.jpg);gray2=rgb2gray(z);f0=gray2;subplot(1,2,1),image(f0);imshow(uint8(f0);title(原始圖像);f=abs(f0/4)-10;M,N=size(f);p=zeros(1,61);for t=1:61 count=0; for i=1:M for j=1:N if f(i,j)=

11、t-1 count=count+1; end end end p(t)=count;p0=p;endcore=cell(61,1);sign=zeros(61);for hh=1:60 re=M*N; for t=1:61 if (p(t)0) re=p(t); end end t=1; while (p(t)=re)&(t61) t=t+1; end if sign(t,1)=0 coret=0; else coret=0,coret; i=1; while (sign(t,i)=0)&(i61) coresign(t,i)=0,coresign(t,i); i=i+1; end end p

12、(t)=0; cou=t; re1=M*N; for t=1:61 if (p(t)0) re1=p(t); end end t=1; while (p(t)=re1)&(t61) t=t+1; end if sign(t,1)=0 coret=1; else coret=1,coret; i=1; while (sign(t,i)=0)&(i61) coresign(t,i)=1,coresign(t,i); i=i+1; end end p(t)=p(t)+re; cou1=t; i=1; while (sign(t,i)=0)&(i61) i=i+1; end sign(t,i)=cou

13、; i=i+1; j=1; while (sign(cou,j)=0)&(j61) sign(t,i)=sign(cou,j); i=i+1; j=j+1; endend %產(chǎn)生huffman碼fc=cell(M,N);for i=1:M for j=1:N if f(i,j)len-1; i=1; j=j+1; else i=i+1; end break; end endendf=uint8(f*4+35);subplot(1,2,2)imshow(f);title(解碼后的壓縮圖像);imwrite(f,壓縮圖像.jpg);imfinfo(壓縮圖像.jpg)toc五.總結(jié)學(xué)習(xí)完本門課程之后,是我的知識(shí)面有

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論