數(shù)字圖像處理課程設(shè)計(jì)-- huffman編碼理論及算法實(shí)現(xiàn)

1、<p>　　數(shù)字圖像處理課程設(shè)計(jì)</p><p>　　課程題目 Huffman編碼原理及算法實(shí)現(xiàn)</p><p>　　Huffman編碼理論及算法實(shí)現(xiàn)</p><p><b>　　基本介紹</b></p><p>　　霍夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)（如文件中的一個(gè)字母）進(jìn)行編碼，其中變長(zhǎng)編碼表是通過(guò)一種評(píng)估來(lái)

2、源符號(hào)出現(xiàn)機(jī)率的方法得到的，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均長(zhǎng)度、期望值降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的。</p><p>　　霍夫曼樹(shù)又稱(chēng)最優(yōu)二叉樹(shù)，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。所謂樹(shù)的帶權(quán)路徑長(zhǎng)度，就是樹(shù)中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹(shù)的路徑長(zhǎng)度是從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)

3、度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln）</p><p>　　N個(gè)權(quán)值Wi（i=1,2,...n）構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i（i=1,2,...n）?？梢宰C明霍夫曼樹(shù)的WPL是最小的。</p><p><b>　　輸入</b></p><p>　　符號(hào)集合S={s1,s2,&

4、#183;··,Sn}，其S集合的大小為n。</p><p>　　權(quán)重集合W={w1,w2,···,Wn}，其W集合不為負(fù)數(shù)且Wi=weight(Si)，</p><p>　　1 ≤ i ≤ n。</p><p><b>　　輸出</b></p><p>　　一組

5、編碼C(S,W)={c1,c2,···Cn}，其C集合是一組二進(jìn)制編碼且Ci為Si相對(duì)應(yīng)的編碼，1 ≤ i ≤ n。</p><p>　　霍夫曼樹(shù)常處理符號(hào)編寫(xiě)工作。根據(jù)整組數(shù)據(jù)中符號(hào)出現(xiàn)的頻率高低，決定如何給符號(hào)編碼。如果符號(hào)出現(xiàn)的頻率太高，則給符號(hào)的碼越短，相反符號(hào)的號(hào)碼越長(zhǎng)。假設(shè)我們要給一個(gè)英文單字"F O R G E T"進(jìn)行霍夫曼編碼，而每個(gè)英文

6、字母出現(xiàn)的頻率。</p><p><b>　　演算過(guò)程</b></p><p>　　（一）進(jìn)行霍夫曼編碼前，我們先創(chuàng)建一個(gè)霍夫曼樹(shù)。</p><p>　?、睂⒚總€(gè)英文霍夫曼樹(shù)字母依照出現(xiàn)頻率由小排到大，最小在左。</p><p>　?、裁總€(gè)字母都代表一個(gè)終端節(jié)點(diǎn)（葉節(jié)點(diǎn)），比較F.O.R.G.E.T五個(gè)字母中每個(gè)字母的出

7、現(xiàn)頻率，將最小的兩個(gè)字母頻率相加合成一個(gè)新的節(jié)點(diǎn)。如Fig.1所示，發(fā)現(xiàn)F與O的頻率最小，故相加2+3=5。</p><p>　?、潮容^5.R.G.E.T，發(fā)現(xiàn)R與G的頻率最小，故相加4+4=8。</p><p>　?、幢容^5.8.E.T，發(fā)現(xiàn)5與E的頻率最小，故相加5+5=10。</p><p>　?、当容^8.10.T，發(fā)現(xiàn)8與T的頻率最小，故相加8+7=15。&

8、lt;/p><p>　　⒍最后剩10.15，沒(méi)有可以比較的對(duì)象，相加10+15=25。</p><p><b>　　（二）進(jìn)行編碼</b></p><p>　　1.給霍夫曼樹(shù)的所有左鏈結(jié)'0'與霍夫曼樹(shù)右鏈結(jié)'1'。</p><p>　　2.從樹(shù)根至樹(shù)葉依序記錄所有字母的編碼，如Fig.2。&

9、lt;/p><p><b>　　三、實(shí)現(xiàn)方法</b></p><p>　　實(shí)現(xiàn)霍夫曼編碼的方式主要是創(chuàng)建一個(gè)二叉樹(shù)和其節(jié)點(diǎn)。這些樹(shù)的節(jié)點(diǎn)可以存儲(chǔ)在數(shù)組里，數(shù)組的大小為符號(hào)（symbols）數(shù)的大小n，而節(jié)點(diǎn)分為是終端節(jié)點(diǎn)（葉節(jié)點(diǎn)）與非終端節(jié)點(diǎn)（內(nèi)部節(jié)點(diǎn)）。</p><p>　　一開(kāi)始，所有的節(jié)點(diǎn)都是終端節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)有三個(gè)字段：</p>

10、<p>　　1.符號(hào)（Symbol）</p><p>　　2.權(quán)重（Weight、Probabilities、Frequency）</p><p>　　3.指向父節(jié)點(diǎn)的鏈結(jié)（Link to its parent node）</p><p>　　而非終端節(jié)點(diǎn)內(nèi)有四個(gè)字段：</p><p>　　1.權(quán)重（Weight、Probabil

11、ities、Frequency）</p><p>　　2.指向兩個(gè)子節(jié)點(diǎn)的 鏈結(jié)（Links to two child node）</p><p>　　3.指向父節(jié)點(diǎn)的鏈結(jié)（Link to its parent node）</p><p>　　基本上，我們用'0'與'1'分別代表指向左子節(jié)點(diǎn)與右子節(jié)點(diǎn)，最后為完成的二叉樹(shù)共有n個(gè)終端節(jié)

12、點(diǎn)與n-1個(gè)非終端節(jié)點(diǎn)，去除了不必要的符號(hào)并產(chǎn)生最佳的編碼長(zhǎng)度。</p><p>　　過(guò)程中，每個(gè)終端節(jié)點(diǎn)都包含著一個(gè)權(quán)重（Weight、Probabilities、Frequency），兩兩終端節(jié)點(diǎn)結(jié)合會(huì)產(chǎn)生一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)的權(quán)重是由兩個(gè)權(quán)重最小的終端節(jié)點(diǎn)權(quán)重之總和，并持續(xù)進(jìn)行此過(guò)程直到只剩下一個(gè)節(jié)點(diǎn)為止。</p><p>　　實(shí)現(xiàn)霍夫曼樹(shù)的方式有很多種，可以使用優(yōu)先隊(duì)列（Priori

13、ty Queue）簡(jiǎn)單達(dá)成這個(gè)過(guò)程，給與權(quán)重較低的符號(hào)較高的優(yōu)先級(jí)（Priority），算法如下：</p><p>　?、卑裯個(gè)終端節(jié)點(diǎn)加入優(yōu)先隊(duì)列，則n個(gè)節(jié)點(diǎn)都有一個(gè)優(yōu)先權(quán)Pi，1 ≤ i ≤ n</p><p>　?、踩绻?duì)列內(nèi)的節(jié)點(diǎn)數(shù)>1，則：</p><p>　　⑴從隊(duì)列中移除兩個(gè)最大的Pi節(jié)點(diǎn)，即連續(xù)做兩次remove(max(Pi), Priori

14、ty_Queue)</p><p>　?、飘a(chǎn)生一個(gè)新節(jié)點(diǎn)，此節(jié)點(diǎn)為（1）之移除節(jié)點(diǎn)之父節(jié)點(diǎn)，而此節(jié)點(diǎn)的權(quán)重值為（1）兩節(jié)點(diǎn)之權(quán)重和</p><p>　　⑶把（2）產(chǎn)生之節(jié)點(diǎn)加入優(yōu)先隊(duì)列中</p><p>　?、匙詈笤趦?yōu)先隊(duì)列里的點(diǎn)為樹(shù)的根節(jié)點(diǎn)（root）</p><p>　　而此算法的時(shí)間復(fù)雜度（ Time Complexity）為O（n l

15、og n）；因?yàn)橛衝個(gè)終端節(jié)點(diǎn)，所以樹(shù)總共有2n-1個(gè)節(jié)點(diǎn)，使用優(yōu)先隊(duì)列每個(gè)循環(huán)須O（log n）。</p><p>　　此外，有一個(gè)更快的方式使時(shí)間復(fù)雜度降至線(xiàn)性時(shí)間（Linear Time）O(n)，就是使用兩個(gè)隊(duì)列（Queue）創(chuàng)件霍夫曼樹(shù)。第一個(gè)隊(duì)列用來(lái)存儲(chǔ)n個(gè)符號(hào)（即n個(gè)終端節(jié)點(diǎn)）的權(quán)重，第二個(gè)隊(duì)列用來(lái)存儲(chǔ)兩兩權(quán)重的合（即非終端節(jié)點(diǎn)）。此法可保證第二個(gè)隊(duì)列的前端（Front）權(quán)重永遠(yuǎn)都是最小值，且方法如

16、下:</p><p>　　⒈把n個(gè)終端節(jié)點(diǎn)加入第一個(gè)隊(duì)列（依照權(quán)重大小排列，最小在前端）</p><p>　?、踩绻?duì)列內(nèi)的節(jié)點(diǎn)數(shù)>1，則:</p><p>　?、艔年?duì)列前端移除兩個(gè)最低權(quán)重的節(jié)點(diǎn)</p><p>　　⑵將（1）中移除的兩個(gè)節(jié)點(diǎn)權(quán)重相加合成一個(gè)新節(jié)點(diǎn)</p><p><b>　?、羌尤氲?/p>

17、二個(gè)隊(duì)列</b></p><p>　　⒊最后在第一個(gè)隊(duì)列的節(jié)點(diǎn)為根節(jié)點(diǎn)</p><p>　　雖然使用此方法比使用優(yōu)先隊(duì)列的時(shí)間復(fù)雜度還低，但是注意此法的第1項(xiàng)，節(jié)點(diǎn)必須依照權(quán)重大小加入隊(duì)列中，如果節(jié)點(diǎn)加入順序不按大小，則需要經(jīng)過(guò)排序，則至少花了O（n logn）的時(shí)間復(fù)雜度計(jì)算。</p><p>　　但是在不同的狀況考量下，時(shí)間復(fù)雜度并非是最重要的，如果

18、我們今天考慮英文字母的出現(xiàn)頻率，變量n就是英文字母的26個(gè)字母，則使用哪一種算法時(shí)間復(fù)雜度都不會(huì)影響很大，因?yàn)閚不是一筆龐大的數(shù)字。</p><p><b>　　數(shù)據(jù)長(zhǎng)度</b></p><p>　　設(shè)符號(hào)集合S = {s1,s2,···,Sn}</p><p>　　設(shè) P(Sj) : Sj 發(fā)生的機(jī)率</p

19、><p>　　設(shè)L(Sj) : Sj編碼的長(zhǎng)度</p><p><b>　　熵：</b></p><p><b>　　霍夫曼碼平均長(zhǎng)度</b></p><p>　　霍夫曼碼的長(zhǎng)度 </p><p><b>　　五、實(shí)驗(yàn)代碼及結(jié)果</b>

20、;</p><p>　　function [h,l,hh,t]=huffman(p) </p><p>　　if (~isempty(find(p<0, 1))) </p><p>　　error('Not a prob,negative component'); </p><p><b>　　end &

21、lt;/b></p><p>　　if (abs(sum(p)-1)>10e-10) </p><p>　　error('Not a prob.vector,component do not add to 1') </p><p><b>　　end </b></p><p>　　n=l

22、ength(p);</p><p>　　q=p; %數(shù)組p附給q</p><p>　　m=zeros(n-1,n); %創(chuàng)建（n-1)*n矩陣 </p><p>　　for i=1:n-1 </p><p>　　[q,l]=sort(q); </p><p>　　m(i,:)=[l(1:n-i+1),zeros(

23、1,i-1)]; </p><p>　　q=[q(1)+q(2),q(3:n),1]; </p><p><b>　　end </b></p><p>　　for i=1:n-1 </p><p>　　c(i,:)=blanks(n*n); </p><p><b>　　end

24、</b></p><p>　　c(n-1,n)='0'; </p><p>　　c(n-1,2*n)='1'; </p><p>　　for i=2:n-1 </p><p>　　c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)==1))... </p>

25、;<p>　　-(n-2):n*(find(m(n-i+1,:)==1))); </p><p>　　c(n-i,n)='0'; </p><p>　　c(n-i,n+1:2*n-1)=c(n-i,1:n-1); </p><p>　　c(n-i,2*n)='1'; </p><p>　　f

26、or j=1:i-1 </p><p>　　c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,... </p><p>　　n*(find(m(n-i+1,:)==j+1)-1)+1:n*find(m(n-i+1,:)==j+1)); </p><p><b>　　end </b></p><p>

27、;<b>　　end </b></p><p>　　for i=1:n </p><p>　　h(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n);</p><p>　　ll(i)=length(find(abs(h(i,:))~=32)); end </p>&

28、lt;p>　　fprintf('碼長(zhǎng)總和是:\n')</p><p>　　l=sum(p.*ll)</p><p>　　fprintf('hufffman code:\n');</p><p><b>　　h</b></p><p>　　fprintf('p信源的熵是:\n&

29、#39;)</p><p>　　hh=sum(p.*(-log2(p)))</p><p>　　fprintf('hufffman effciency:\n');</p><p><b>　　t=hh/l</b></p><p><b>　　主程序1：</b></p>

30、<p>　　p=[0.3 0.1 0.2 0.2 0.2];</p><p>　　huffman(p)</p><p><b>　　實(shí)驗(yàn)結(jié)果1</b></p><p><b>　　碼長(zhǎng)總和是:</b></p><p><b>　　l =</b></p>

31、<p><b>　　2.3000</b></p><p>　　hufffman code:</p><p><b>　　h =</b></p><p><b>　　10</b></p><p><b>　　110</b></p>&

32、lt;p><b>　　111</b></p><p><b>　　00</b></p><p><b>　　01</b></p><p><b>　　p信源的熵是:</b></p><p>　　hh = 2.2464</p><

33、;p>　　hufffman effciency:</p><p><b>　　t =0.9767</b></p><p><b>　　主程序2：</b></p><p>　　p=[0.35 0.15 0.25 0.12 0.08 0.05];</p><p>　　huffman(p)&

34、lt;/p><p><b>　　實(shí)驗(yàn)結(jié)果2</b></p><p><b>　　碼長(zhǎng)總和是:</b></p><p>　　l = 2.3800</p><p>　　hufffman code:</p><p><b>　　h =</b></p>

35、;<p><b>　　11</b></p><p><b>　　00</b></p><p><b>　　10</b></p><p><b>　　010</b></p><p><b>　　0111</b></p

36、><p><b>　　0110</b></p><p><b>　　p信源的熵是:</b></p><p><b>　　hh =</b></p><p><b>　　2.3153</b></p><p>　　hufffman effci