1 案例背景
一幅普通的未經壓縮的圖檔可能需要占幾兆的存儲空間，一個時長僅為1秒的未經壓縮的視訊檔案所占的存儲空間甚至能達到上百兆位元組，這給普通PC的存儲空間和常用網絡的傳輸帶寬帶來了巨大的壓力。其中，靜止圖像是不同媒體的建構基礎，對其進行壓縮不僅是各種媒體壓縮和傳輸的基礎，其壓縮效果也是影響媒體壓縮效果好壞的關鍵因素。基于這種考慮，本案例主要研究靜止圖像的壓縮技術。随着人們對圖像壓縮技術的重視，目前已經提出了多種壓縮編碼方法。如果以不同種類的媒體資訊為處理對象，則每種壓縮編碼方法都有其自身的優勢和特點，如編碼複雜度和運作效率的改善、解碼正确性的提高、圖像恢複的品質提升等"。特别是，随着網際網路資訊量的不斷增大，高效能資訊檢索的品質也與壓縮編碼方法存在越來越緊密的聯系。從發展的現狀來看，采用分形和小波混合圖像編碼方法能充分發揮小波和分形編碼的優點，彌補互相的不足，是以成為圖像壓縮的一個重要研究方向，但是依然存在某些不足之處，有待進一步提高。
2 理論基礎
壓縮，根據編碼前後資料損失的角度可分為無損壓縮編碼和有損壓縮編碼；根據已知編碼方法分類的實用性角度可分為統計編碼、預測編碼和變換編碼。所謂無損壓縮，就是利用資料的統計備援資訊進行壓縮，且能夠在不引起任何失真的前提下完全恢複原始資料。無損壓縮法廣泛用于文本、程式和特殊應用場合的圖像資料(如指紋圖像、醫學圖像等) 的壓縮。常用的無損壓縮編碼方法有香農(Shannon-Fano) 編碼、霍夫曼(Huffman)編碼、行程(Run-length) 編碼、LZW(Lempel-Ziv-Welch) 編碼和算術編碼等。霍夫曼編碼完全依據字元出現的機率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼。霍夫曼編碼将使用次數較多的代碼用長度較短的編碼代替，将使用次數較少的代碼用較長的編碼代替，并且確定編碼的唯一可解性。其根本原則是壓縮編碼的長度(即字元的統計數字x字元的編碼長度)最小，也就是權值和最小。
3 霍夫曼編碼的步驟
霍夫曼圖像壓縮重建，過程為：1.符号機率 2.合并機率 3.更新機率 4.配置設定碼字 。
霍夫曼編碼是一種無損壓縮方法，其一般算法如下。
（1）符号機率
統計信源中各符号出現的機率，按符号出現的機率從大到小排序。
（2）合井機率
提取最小的兩個機率并将其相加，合并成新的機率，再将新機率與剩餘的機率組成新的機率集合，
（3）更新機率
将合并後的機率集合重新排序，再次提取其中最小的兩個機率，相加得到新的機率，進而組成新的機率集合。如此重複進行，直到剩餘最後兩個機率之和為1.
（4）配置設定碼字
配置設定碼字從最後一步開始逆向進行，對于每次相加的兩個機率，大機率賦0，小機率賦1，當然也可以反過來指派，即大機率賦1，小機率賦0；特别是，如果兩個機率相等，則從中任選一個賦0，另一個賦1.依次重複該步驟，從第一次指派開始進入循環處理，直到最後的碼字機率和為1時結束。将中間過程中所遇到的0和1按從最低位到最高位的順序排序，就得到了符号的霍夫曼編碼。
4 霍夫曼編碼的特點
霍夫曼編碼是最佳的變長編碼，其特點如下回。
（1）可重複性
霍夫曼編碼不唯一，具有可重複性。
（2）效率差異性
霍夫曼編碼對于不同的信源往往具有不同的編碼效率，具有效率差異性。
（3）不等長性
霍夫曼編碼的輸出内容不等長，是以給硬體實作帶來一定的困難，也在一定程度上造成了誤碼傳播的嚴重性。
（4）信源依賴性
霍夫曼編碼的運作效率往往要比其他編碼算法高，是最佳的變長編碼。但是，霍夫曼編碼以信源的統計特性為基礎，必須先統計信源的機率特性才能編碼，是以具有對信源的依賴性，這也在一定程度上限制了霍夫曼編碼的實際應用。
如圖所示是一個霍夫曼編碼的例子。從圖中二叉樹的形狀分步可以發現，符号隻能出現在樹葉上，且每個字元的路徑都不允許是其他字元路徑的字首路徑，是以能夠成功構造字首編碼。該二叉樹在資料結構中被稱為霍夫曼樹，一般應用于最佳判定的場景，是最優二叉樹的一種，而且帶權路徑長度最短。其中，二叉樹的帶權路徑長度由樹中所有葉節點的權值乘以其到根節點的路徑長度來獲得，假設根節點為0層，則葉節點到根節點的路徑長度就是葉節點的層數值。是以， 二叉樹的帶權路徑長度記作WPL， 其計算公式為：WPL=(WxL+Wx Ly+…+W、xLy) .如果由N個權值W(i=1， 2， …， n) 構成的一棵包含N個節點的二叉樹，則相應樹節點的路徑長度為L(i=1，2，…，n)，選擇霍夫曼編碼得出的
WPL值最小。
圖13-1霍夫曼編碼執行個體
在實際應用中，霍夫曼編碼在預處理之前需要知道葉節點(即信源資料符号)的機率，這往往會對實時性要求較高的應用場景帶來困擾。是以，人們在實時編碼的應用場景中往往會采用所謂的準可變字長碼，如采用雙字長編碼，并且通過從短碼集合中選出一個碼字，作為長碼字頭，進而保證碼字的非續長特性2]。此外，在數字圖像通信中所使用的三類傳真機中包含的MH碼采用了多字長VLC技術， 該技術根據一系列标準圖像進行統計資料分析而得出，通過預先在其IC晶片中加入号碼表，使得實際的編碼解碼過程簡化為一個查表過程，進而確定了高速、實時應用場景的需要。
1 matlab版本
2014a
2 參考文獻
[1] 蔡利梅.MATLAB圖像處理——理論、算法與執行個體分析[M].清華大學出版社，2020.
[2]楊丹,趙海濱,龍哲.MATLAB圖像處理執行個體詳解[M].清華大學出版社，2013.
[3]周品.MATLAB圖像處理與圖形使用者界面設計[M].清華大學出版社，2013.
[4]劉成龍.精通MATLAB圖像處理[M].清華大學出版社，2015.