哈夫曼編碼和分形編碼圖像壓縮技術(shù)初探

1、第13卷第2期2010年6月成都電子機(jī)械高等?？茖W(xué)校學(xué)報(bào)Journal of Chengdu Electrom echanical C ollege V ol . 13, N o . 2June. , 2010收稿日期:2010-03-24作者簡介:冉曉娟(1982- , 女(漢族 , 四川成都人。碩士, 主要研究方向:計(jì)算機(jī)應(yīng)用技術(shù)、圖形圖像處理、多媒體技術(shù)及應(yīng)用等。哈夫曼編碼和分形編碼圖像壓縮技術(shù)初探冉曉娟1, 梁靜2(1. 四川烹飪高等?？茖W(xué)校信息技術(shù)系, 成都610000; 2. 成都電子機(jī)械高等專科學(xué)校網(wǎng)管中心, 成都610031摘要:隨著信息技術(shù)的發(fā)展, 各種影像、語音、文字、數(shù)據(jù)

2、等信息都以數(shù)字化的方式存儲起來, 給信息的存儲帶來極大的壓力。“資料壓縮”成為解決信息儲存不可缺少的工具。本文通過介紹常見的圖像壓縮技術(shù)哈夫曼編碼和分形編碼, 提出了一些改進(jìn)的方法。關(guān)鍵詞:圖像壓縮; 哈夫曼編碼; 分形編碼中圖分類號:TP311. 13文獻(xiàn)標(biāo)志碼:A 文章編號:1008-5440(2010 02-0017-04A Study of Huff man Codi n g n g on1G J ing 2(logy en t, Sichuan H igher Institu te of C u isine, C hengdu 610000, C h ina ;2. en ter o

3、f N et w o rk M anage m en t, C hengdu Electrom echan ical C o llege, C hengdu 610031, C h ina Abstract:W ith the developm en t of info r m ation techno logy, all kinds of videos, vo ices, texts, data ando ther info r m ation are d igitally sto red, w h ich bring us great p ressu re on how to sto re

4、 the tens of thousandsof info r m ation. A s a resu lt, “data com p ression ”becom es an indis pensable too l fo r info r m ation sto rage .T h is p aper first in troduces the comm on i m age com p ression techno logy 2H uff m an coding and fractalcoding, and then p roposes som e i m p rovem en ts .

5、Key words:I m age com p ression; H uff m an coding; Fractal coding圖像壓縮技術(shù)的提出最早可追溯到1948年的電視信號數(shù)字化, 至今已有近70年的歷史。20世紀(jì)五、六十年代, 由于受到電路技術(shù)的制約, 圖像壓縮僅僅停留在預(yù)測編碼、亞采樣以及內(nèi)插復(fù)原等技術(shù)的研究。直到第一屆“圖像編碼會議”的召開, 圖像編碼才作為一門獨(dú)立的學(xué)科誕生。20世紀(jì)七、八十年代, 隨著科學(xué)研究的深入, 圖像壓縮技術(shù)的研究得到了很大的發(fā)展, 其成果主要體現(xiàn)在變換編碼技術(shù)和矢量量化編碼技術(shù)上, 同時(shí)關(guān)于圖像編碼技術(shù)的科技成果和科技論文與日俱增, 圖像編碼技術(shù)開始

6、走向繁榮。從80年代后期開始, 隨著小波變換理論、分形理論、人工神經(jīng)網(wǎng)絡(luò)理論、視覺仿真理論的建立, 人們開始突破傳統(tǒng)的信源編碼理論, 向著追求更好的壓縮質(zhì)量以及更高的壓縮比的道路前進(jìn)。1哈夫曼編碼哈夫曼算法是眾多圖像壓縮算法中一種很重要的基礎(chǔ)算法。它能有效地減少數(shù)據(jù)的存儲空間, 提高存儲媒體的訪問速度。同時(shí)由于它易于實(shí)現(xiàn), 因此常常與其他算法合并使用。成都電子機(jī)械高等?？茖W(xué)校學(xué)報(bào)第13卷1. 1哈夫曼編碼原理哈夫曼編碼1又稱統(tǒng)計(jì)編碼, 是哈夫曼在1952年提出的一種無失真壓縮技術(shù), 它是通過用更有效的代碼代替數(shù)據(jù)來實(shí)現(xiàn)的。哈夫曼編碼最初是為了對文本文件進(jìn)行壓縮而建立的, 迄今已經(jīng)有很多變體。它

7、的基本思想是出現(xiàn)頻率越高的值, 其對應(yīng)的編碼長度越短, 反之出現(xiàn)頻率越低的值, 其對應(yīng)的編碼長度越長。其原理是將欲壓縮的字串, 先讀一遍, 將字串中的每一個(gè)相異單字元的出現(xiàn)頻率作統(tǒng)計(jì), 依此構(gòu)建哈夫曼樹。每一相異單字元, 用0與1予以編碼, 出現(xiàn)次數(shù)越多者, 給予較少的位元編碼, 最后將這些位元串組合起來, 并加入哈夫曼樹, 成為壓縮檔案。1. 2哈夫曼編碼特性由于經(jīng)過哈夫曼編碼法所編碼出來的檔案是具有唯一碼性質(zhì)的即時(shí)碼, 即各個(gè)相異字元所編碼出的所有位元串并不相同, 解碼時(shí)能立即解出。因此, 哈夫曼編碼法的解碼過程是即時(shí)且唯一的解碼。由此可見, 哈夫曼編碼具有以下明顯的特點(diǎn):1 編出來的碼都

8、是異字頭碼, 保證了碼的唯一可譯性。2 由于編碼長度可變。因此譯碼時(shí)間較長, 使得哈夫曼編碼的壓縮與還原相當(dāng)費(fèi)時(shí)3 編碼長度不統(tǒng)一, 硬件實(shí)現(xiàn)有難度。4 由于“0”與“1”的指定是任意的, , , 故不影響編碼效率與數(shù)據(jù)壓縮性能。由此可見, , , ; 而對于出現(xiàn)頻率低的信息, 1. 3哈夫曼編碼可以采用以下步驟進(jìn)行:1 將信號源的符號按照出現(xiàn)概率遞減的順序進(jìn)行排列。2 將兩個(gè)最小出現(xiàn)概率進(jìn)行合并相加, 得到的結(jié)果作為新符號的出現(xiàn)概率。3 重復(fù)進(jìn)行步驟1和2直到概率相加的結(jié)果等于1為止。4 在合并運(yùn)算時(shí), 概率大的符號用編碼0表示, 概率小的符號用編碼1表示。5 記錄下概率為1處到當(dāng)前信號源符

9、號之間的0, l 序列, 從而得到每個(gè)符號的編碼。1. 4哈夫曼編碼存在的問題及其改進(jìn)由1. 3哈夫曼編碼步驟可知, 哈夫曼算法要求掃描兩遍原始數(shù)據(jù):第一遍掃描是為了精確統(tǒng)計(jì)原始數(shù)據(jù)中各數(shù)據(jù)出現(xiàn)的頻率, 利用得到的頻率值創(chuàng)建哈夫曼樹, 并必須保存統(tǒng)計(jì)結(jié)果; 第二遍則根據(jù)第一遍掃描過程中生成的哈夫曼樹進(jìn)行編碼, 并必須存儲編碼后得到的碼字。可見, 當(dāng)某信息的數(shù)據(jù)量較大時(shí), 直接采用哈夫曼模型進(jìn)行靜態(tài)統(tǒng)計(jì)將消耗大量的時(shí)間, 若將其用于通訊網(wǎng)絡(luò), 勢必引起較大的延時(shí)。其次, 由于哈夫曼編碼必須保存統(tǒng)計(jì)出的結(jié)果以便解壓縮時(shí)構(gòu)造相同的編碼樹, 因此也將消耗大量的存儲空間, 從而得到較低的壓縮比。另一方面

10、, 對于含有0255或更多種顏色的視頻圖像來說, 哈夫曼編碼這種靜態(tài)統(tǒng)計(jì)模型統(tǒng)計(jì)出的頻率是某一種顏色在整個(gè)文件中的出現(xiàn)頻率, 不能有效反映出該顏色在圖像文件中不同局部出現(xiàn)頻率的變化情況, 直接使用這一頻率進(jìn)行壓縮, 大多數(shù)情況下得不到太好壓縮效果。壓縮編碼的宗旨是要獲得最小的帶權(quán)路徑長度值, 針對哈夫曼編碼的低壓縮比及占用存儲空間大的缺點(diǎn), 可對某個(gè)數(shù)據(jù)使用多值的編碼, 確保編碼的單值性(前綴編碼 , 并使相同長度的一組編碼按順序排列, 從而實(shí)現(xiàn)壓縮。其具體實(shí)現(xiàn)壓縮的步驟如下:1 統(tǒng)計(jì)每個(gè)需要編碼符號出現(xiàn)的頻率。2 根據(jù)步驟(1 中統(tǒng)計(jì)所得的頻率信息求出該編碼符號在哈夫曼編碼樹中的深度(即表示

11、該符號所需要的編碼長度 。由于我們僅僅關(guān)心該符號在樹中的深度, 因此不用構(gòu)造二叉樹, 而是用一個(gè)數(shù)組模擬二叉樹的創(chuàng)建過程并得到符號的深度。2010年第2期冉曉娟, 梁靜:哈夫曼編碼和分形編碼圖像壓縮技術(shù)初探3 分別統(tǒng)計(jì)每個(gè)編碼長度N i (二叉樹上的N i 層 上對應(yīng)數(shù)據(jù)的數(shù)目, 然后分別對N i 層上的符號以遞增順序分配編碼。最底層編碼從0開始, 第N i 層第一個(gè)編碼取下一層最后一個(gè)編碼的左邊N i 位數(shù)+1, 這樣可以確保編碼為前綴編碼。4 編碼輸出壓縮信息, 并保存按照層的順序排列的符號表, 然后只需保存每層同樣長度編碼的個(gè)數(shù)即可。通過以上方法就可在不依賴任何樹結(jié)構(gòu)的情形下進(jìn)行高速解壓

12、縮了, 并在整個(gè)壓縮與解壓縮過程中占用比傳統(tǒng)哈夫曼編碼少得多的存儲空間, 從而得到較高的壓縮比。表1為分別采用傳統(tǒng)哈夫曼算法與改進(jìn)哈夫曼算法得到的實(shí)驗(yàn)對比數(shù)據(jù)。表1傳統(tǒng)哈夫曼算法與改進(jìn)哈夫曼算法的實(shí)驗(yàn)數(shù)據(jù)對比源文件名文件大小傳統(tǒng)哈夫曼算法壓縮后的文件大小改進(jìn)哈夫曼算法壓縮后的文件大小Huff man . cpp5. 34K B 2. 96K B 2. 16K B Huff man . doc54. 5K B 29. 03K B 19. 62K B Huff man . exe 127K B 92K B 66. 81K 2分形編碼, 然而自然界景象是由非常不規(guī)則的曲線構(gòu)成的, , 因此經(jīng)典幾何學(xué)

13、就無能為力, 從而醞釀了分形幾何學(xué)的產(chǎn)生。2. 1分形編碼原理分形圖像壓縮是一種新的圖像壓縮方法, 它的基本思想是利用圖像的相似性, 把整個(gè)或局部圖像映射到圖像的一部分, 并使用拼接定理完成整個(gè)圖像的壓縮。其步驟如下2:1 把圖像劃分為互不重疊、任意大小形狀的domain 分區(qū), 所有domain 分區(qū)拼起來應(yīng)恰為原圖。2 再劃定一些可以相互重疊的range 分區(qū), 每個(gè)range 分區(qū)都大于相應(yīng)的do main 分區(qū), 而所有range 分區(qū)之“并”無須覆蓋全圖。為每一個(gè)domain 劃定的range 分區(qū)必須在三維放射變換后盡可能與domain 分區(qū)圖像接近, 而每個(gè)三維仿射變換由其系數(shù)來

14、描述定義, 從而形成分形圖像格式文件F I F 。Domain 分區(qū)大小的劃分要作一些權(quán)衡, 劃得越大, 分區(qū)總數(shù)越少, 所作仿射變換也越少, 但由此構(gòu)成的range 分區(qū)變換所得圖像與原domain 分區(qū)圖像差別就大, 解碼圖像質(zhì)量下降。劃得太小, 運(yùn)行時(shí)間加長。因此分形方法在圖像編碼應(yīng)用中有兩個(gè)難點(diǎn)要進(jìn)一步研究:其一, 如何恰到好處地分割圖像, 對于一些有明顯分形特點(diǎn)的圖像很容易在迭代數(shù)系統(tǒng)中找到與這些子圖像對應(yīng)的迭代函數(shù), 反復(fù)迭代后即可產(chǎn)生與原子圖像很逼近的圖像, 而對不具備明顯分形特點(diǎn)的圖像, 分割是一個(gè)難以解決的問題; 其二, 如何構(gòu)造迭代函數(shù)系統(tǒng)。仿射變換AT 3是分形圖像壓縮編

15、碼的重要問題, 它是n 維空間函數(shù)圖像經(jīng)過旋轉(zhuǎn)、伸縮、偏斜、平移等形成的?？梢宰C明:變換了的圖形的“并”越精確地接近目標(biāo)圖像, 這些變換“集合”提供的目標(biāo)圖形的編碼就越精確, 這也是一個(gè)需要仔細(xì)研究的問題。分形編碼的解碼過程非常簡單, 從F I F 文件中讀取domain 分區(qū)劃分方式的信息和仿射變換系數(shù)等數(shù)據(jù), 再劃定兩個(gè)緩沖區(qū), 即domain 圖像區(qū)(稱為D 緩沖區(qū) 和range 圖像區(qū)(稱為R 緩沖區(qū) , 然后按F I F 文件的規(guī)定把D 劃分為domain 分區(qū), R 劃分為range 分區(qū)。把指針指向第一個(gè)domain 分區(qū), 根據(jù)它的變換系數(shù)把其相應(yīng)的range 分區(qū)一一進(jìn)行上述

16、操作, 全都完成后形成一幅新的domain 圖像, 再把D 的內(nèi)容拷貝到R 中。再把新的R 當(dāng)作D, D 當(dāng)作R 重復(fù)操作, 即迭代, 直到兩個(gè)緩沖區(qū)圖像無多大差別, 即為解碼復(fù)原圖像。一般幾次到幾十次迭代即可完成。2. 2分形編碼特點(diǎn)1 分形編碼壓縮比高(比經(jīng)典編碼高12個(gè)數(shù)量級 。成都電子機(jī)械高等?？茖W(xué)校學(xué)報(bào)第13卷2 運(yùn)算速率隨圖像分辨率增加影響不大, 因?yàn)镕 I F 文件大小與分辨率大小無關(guān)。3 可以保留圖像中如邊緣之類的細(xì)節(jié)。4 分形編碼具有非對稱性, 即壓縮編碼計(jì)算量大, 時(shí)間長, 但解壓縮簡單, 速度快。分形編碼的非對稱性和不受圖像分辨率影響這兩個(gè)特點(diǎn), 使其在需要迅速訪問高質(zhì)量

17、圖像的多媒體場合非常合適, 是多媒體圖像編碼一種期望的編碼方式。2. 3分形編碼的應(yīng)用及發(fā)展趨勢圖像壓縮已研究了幾十年, 提出了諸如DPC M 、DCT 、VQ 等壓縮方法, 并已出臺了基于DCT 等技術(shù)的國際壓縮標(biāo)準(zhǔn), 如JPEG 、MPEG 等。人們也逐漸發(fā)現(xiàn)了這些方法的許多缺點(diǎn):比如高壓縮比時(shí)圖像出現(xiàn)嚴(yán)重的方塊效應(yīng)、人眼視覺系統(tǒng)的特性不易被引入到壓縮算法中等等。人們認(rèn)為目前有三種方法屬于第二代圖像編碼方法:基于分割的壓縮方案、基于模型的壓縮方案及基于分形的壓縮方案。分形編碼是目前較有發(fā)展前途的圖像編碼方法之一, 也是目前研究較為廣泛的編碼方法之一。對其研究已有近十年的歷史, 其間, 人們

18、發(fā)現(xiàn)了它所具有的許多優(yōu)點(diǎn):比如, 它突破以往熵壓縮編碼的界限, 在編碼過程中, 采用了類似描述的方法, 而解碼是通過迭代完成的, 。分形編碼的思想最早由Barnsley 和Sl oan 引入, 。在此基礎(chǔ)上, Jacquin , 子塊, 對于每一個(gè)值域子塊, , 使隨后, 采用有效的分類技術(shù), 極, 分形圖像編碼目前已形成了三個(gè)主要發(fā)展方向:、提高分形編碼質(zhì)量、分形序列圖像編碼。3結(jié)束語當(dāng)今社會, 任何信息都是以數(shù)據(jù)的形式進(jìn)行存儲, 因此信息壓縮技術(shù)的突破對于通信以及多媒體事業(yè)的發(fā)展具有深遠(yuǎn)的影響, 而圖像壓縮技術(shù)作為其中的一個(gè)分支, 也將是一個(gè)很有發(fā)展前途的研究領(lǐng)域。隨著互聯(lián)網(wǎng)的普及, I nternet 上圖像數(shù)據(jù)的傳出速度與質(zhì)量, 直接影響著人們的日常生活, 因此, 很多圖像壓縮算法的研究和應(yīng)用都應(yīng)用于I nternet 環(huán)境中(如基于小波變換的分形圖像編碼壓縮算法 , 它有利緩解了網(wǎng)絡(luò)帶寬不足, 并有效加快了圖像信息的傳播速度。圖文資料數(shù)字化必然會產(chǎn)生大量的圖像數(shù)據(jù), 對于高比率圖像壓縮算法的需求尤為迫切。今天, 研究并掌握各種圖像壓縮編碼技術(shù)并在實(shí)際中加以應(yīng)用具有極其廣泛重要的意義。參考文獻(xiàn):1夏良正. 數(shù)字圖像處理M.南京:東南大學(xué)出版社, 2002.2陳守吉