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

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

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

3、度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln）</p><p>　　N個權(quán)值Wi（i=1,2,...n）構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為Li（i=1,2,...n）?？梢宰C明霍夫曼樹的WPL是最小的。</p><p><b>　　輸入</b></p><p>　　符號集合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集合是一組二進制編碼且Ci為Si相對應(yīng)的編碼，1 ≤ i ≤ n。</p><p>　　霍夫曼樹常處理符號編寫工作。根據(jù)整組數(shù)據(jù)中符號出現(xiàn)的頻率高低，決定如何給符號編碼。如果符號出現(xiàn)的頻率太高，則給符號的碼越短，相反符號的號碼越長。假設(shè)我們要給一個英文單字"F O R G E T"進行霍夫曼編碼，而每個英文

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

7、現(xiàn)頻率，將最小的兩個字母頻率相加合成一個新的節(jié)點。如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>　?、蹲詈笫?0.15，沒有可以比較的對象，相加10+15=25。</p><p><b>　?。ǘ┻M行編碼</b></p><p>　　1.給霍夫曼樹的所有左鏈結(jié)'0'與霍夫曼樹右鏈結(jié)'1'。</p><p>　　2.從樹根至樹葉依序記錄所有字母的編碼，如Fig.2。&

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

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

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

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

13、ty Queue）簡單達成這個過程，給與權(quán)重較低的符號較高的優(yōu)先級（Priority），算法如下：</p><p>　?、卑裯個終端節(jié)點加入優(yōu)先隊列，則n個節(jié)點都有一個優(yōu)先權(quán)Pi，1 ≤ i ≤ n</p><p>　　⒉如果隊列內(nèi)的節(jié)點數(shù)>1，則：</p><p>　?、艔年犃兄幸瞥齼蓚€最大的Pi節(jié)點，即連續(xù)做兩次remove(max(Pi), Priori

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

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

16、下:</p><p>　?、卑裯個終端節(jié)點加入第一個隊列（依照權(quán)重大小排列，最小在前端）</p><p>　?、踩绻犃袃?nèi)的節(jié)點數(shù)>1，則:</p><p>　?、艔年犃星岸艘瞥齼蓚€最低權(quán)重的節(jié)點</p><p>　?、茖ⅲ?）中移除的兩個節(jié)點權(quán)重相加合成一個新節(jié)點</p><p><b>　?、羌尤氲?/p>

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

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

19、><p>　　設(shè)L(Sj) : Sj編碼的長度</p><p><b>　　熵：</b></p><p><b>　　霍夫曼碼平均長度</b></p><p>　　霍夫曼碼的長度 </p><p><b>　　五、實驗代碼及結(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('碼長總和是:\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>　　實驗結(jié)果1</b></p><p><b>　　碼長總和是:</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>　　實驗結(jié)果2</b></p><p><b>　　碼長總和是:</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