一種優(yōu)化的灰度圖像壓縮算法

王炳月，賈連印，范 瑤，孫劭文

（昆明理工大學(xué) 信息工程與自動化學(xué)院，云南 昆明 650500）

0 引 言

圖像是重要的信息載體[1]，信息圖像的巨大數(shù)據(jù)量會引發(fā)存儲空間大和傳輸速率慢等諸多問題。光電圖像處理是圖像處理中的一個重要分支，主要包括光電成像技術(shù)和數(shù)字圖像處理技術(shù)。隨著激光技術(shù)、光電子技術(shù)及光子學(xué)的發(fā)展和逐步完善，光電成像技術(shù)的優(yōu)勢愈發(fā)明顯，例如生物醫(yī)學(xué)圖像、衛(wèi)星成像等，但光電圖像數(shù)據(jù)之間有較大的相關(guān)性，造成大量時間和空間冗余，不利于存儲和傳輸。圖像壓縮是數(shù)據(jù)壓縮技術(shù)在數(shù)字圖像上的應(yīng)用，是圖像存儲和高效傳輸?shù)幕A(chǔ)。對光電圖像壓縮，可以有效減少圖像數(shù)據(jù)中的冗余信息，從而更高效地存儲和傳輸數(shù)據(jù)[2]。

從信息損失的角度來分，圖像壓縮可分為無損壓縮和有損壓縮兩類[3]。根據(jù)圖像壓縮技術(shù)的不同，圖像壓縮又可分為基于分區(qū)[4]的、基于哈夫曼編碼[5]的、基于LZW （Lempel-Ziv-Welch）編碼[7]的、基于游程編碼[9]的以及基于算術(shù)編碼[10]的圖像壓縮方式?；诜謪^(qū)的圖像壓縮是利用相鄰像素值相近的思想，將原始圖像分割為多個像素值接近的小分區(qū)，并用小分區(qū)的像素均值來代替原始小分區(qū)的壓縮方式。哈夫曼編碼[5]是一種經(jīng)典編碼方式，依據(jù)字符出現(xiàn)頻率來構(gòu)造平均長度最短的碼字。RAJIV[6]利用Hufman 編碼作為熵并基于小波變換對圖像進(jìn)行壓縮，取得了較好的壓縮效果。LZW 編碼通過構(gòu)建編譯表，實(shí)現(xiàn)字符重用及編碼，在圖像壓縮中也得到了廣泛應(yīng)用，如BADSHAH[7]的基于LZW編碼的水印壓縮技術(shù)，謝等人[8]采用Hilbert 掃描將像素進(jìn)行重排并基于LZW 編碼對圖像進(jìn)行壓縮等。游程編碼是統(tǒng)計(jì)編碼的一種，利用符號串代替相同連續(xù)符號實(shí)現(xiàn)數(shù)據(jù)壓縮，例如基于正六邊形柵格的游程編碼壓縮技術(shù)[9]等。算術(shù)編碼是將整個輸入編碼為一個數(shù)的熵的編碼方式，如KUMAR等人[10]提出的基于多項(xiàng)式分布和算術(shù)編碼的壓縮方法。

圖像壓縮[2]的一個重要任務(wù)是最大化像素之間的相關(guān)性，使得復(fù)原的圖像在保持質(zhì)量的同時，盡可能提高壓縮率和壓縮效率。傳統(tǒng)的圖像壓縮算法多采用柵格掃描的策略，逐行掃描圖像然后進(jìn)行壓縮。然而，柵格掃描的圖像并不能最大程度地使相鄰的位置（往往具有相似的像素值）劃分到同一個分段，因此對掃描后的圖像壓縮時將導(dǎo)致大量小分段的產(chǎn)生。

HILBERT 曲線[11]作為Peano 填充曲線的一個重要分支，因具有較好的內(nèi)聚性，可更好地把相鄰的位置劃分到同一分段。相對柵格掃描，它可使得更多像素值接近的位置點(diǎn)壓縮為一個分區(qū)，進(jìn)而可降低分區(qū)數(shù)量，提高壓縮效率，所以Hilbert 曲線在圖像分析、圖像壓縮、圖像加密以及圖像存儲與檢索等領(lǐng)域得到了廣泛應(yīng)用[8，12]。

KAMATA 提出的Hilbert 掃描灰度圖像壓縮算法[4]是基于Hilbert曲線對圖像進(jìn)行壓縮的經(jīng)典代表。其在基于Hilbert 掃描的一維數(shù)組上進(jìn)行壓縮，比在基于柵格掃描的數(shù)組上有更高的壓縮率，實(shí)驗(yàn)結(jié)果表明，該算法有著相較JPEG更好的壓縮效果。然而，其采用早期的Hilbert 解碼算法，解碼時間占壓縮總時間的約50%，壓縮效率較低。此外，其采用分區(qū)后合并（MAP）的策略將小分區(qū)進(jìn)行合并，導(dǎo)致較高的時間和空間開銷。

為解決上述問題，本文在對現(xiàn)有Hilbert 解碼算 法（ 如Moore-HD、Burkardt-HD[13]、Li-HD[14]、Unistate-HD、FZF-HD[16]）進(jìn)行深入研究對比的基礎(chǔ)上，引入高效的FZF-HD Hilbert 解碼算法（FZF）及分區(qū)中合并（MIP）的圖像壓縮算法FZF-MIP。通過FZF-HD 算法，可避免對輸入編碼值前部為0的階迭代解碼，可大幅降低圖像壓縮時間。此外，通過設(shè)計(jì)高效的MIP 策略，將分區(qū)和合并的步驟融合，從而避免分區(qū)后合并的開銷，進(jìn)一步提高了圖像壓縮的效率。擴(kuò)展實(shí)驗(yàn)結(jié)果表明了FZF-MIP 算法的有效性。

1 基本定義和前提

1.1 Hilbert 曲線

1階Hilbert曲線將整個空間分割成4個子區(qū)域，將左下、左上、右上、右下這4 個子區(qū)域依次連接起來，即可構(gòu)成開口向下的1 階Hilbert 曲線。通過在1 階曲線的每個網(wǎng)格嵌入一個1 階曲線，并進(jìn)行相應(yīng)的旋轉(zhuǎn)和翻轉(zhuǎn)，即可得到2 階Hilbert 曲線。重復(fù)這個過程，即可得到n階Hilbert 曲線。不同分辨率對應(yīng)Hilbert 曲線如圖1 所示。

圖1 Hilbert 不同分辨率對照圖

1.2 Kamata 算法

KAMATA 提出基于Hilbert 掃描的灰度圖像壓縮算法[4]，首先基于Hilbert 掃描，將圖像映射為一維數(shù)組，然后基于線性插值中的零階插值對數(shù)據(jù)進(jìn)行遞歸分割。最終將圖像壓縮為一個像素數(shù)組A和長度數(shù)組L。其算法框架如圖2 所示，算法執(zhí)行流程如下。

圖2 Kamata 算法框架圖

（1）基于Hilbert 解碼算法掃描圖像，將初始圖像掃描為一個數(shù)組D。通過Hilbert 掃描可使空間上相鄰的點(diǎn)，在曲線上編碼值盡可能地接近。

（2）將數(shù)組D分割成具有長度為M的多個初始分區(qū)P。

（3）對每個初始分區(qū)P按照方差和最小的原則依次劃分為2 個分區(qū)，即找到一個分割點(diǎn)C，將P劃分為P1 和P2 兩個分區(qū)，使得劃分后的兩個分區(qū)的方差EP1和EP2之和最小，如公式（1）所示。若劃分后的分區(qū)P1 的長度小于分區(qū)長度閾值Lmax且方差小于分區(qū)方差閾值Emax，則P1即為一個結(jié)果分區(qū)。將該分區(qū)的像素均值A(chǔ)P1（長度為8 位）和長度LP1（長度為log2(Lmax)位）分別存入位數(shù)組A和L，否則，遞歸對該分區(qū)繼續(xù)劃分，直至所有分區(qū)的長度小于Lmax且方差小于Emax為止。對P2 也執(zhí)行同樣的操作。

（4）步驟（3）可將原始圖像壓縮為兩個位數(shù)組A和L，從而降低圖像的存儲空間。然而，劃分后的分區(qū)可能包含大量小分區(qū)，為此，該算法引入分區(qū)合并步驟。對于待合并的兩個相鄰分區(qū)P1 和P2，如果兩個分區(qū)滿足式（2）、式（3）和式（4），則將P1和P2 進(jìn)一步合并為一個分區(qū)。

式中：L2max表示待合并的小分區(qū)的長度閾值，Gmax表示P1 和P2 的像素均值之差。

（5）最終合并小分區(qū)后的位數(shù)組A和L即為圖像壓縮后的結(jié)果。

2 FZF-MIP 壓縮算法設(shè)計(jì)

2.1 問題分析

盡管有較好的壓縮效果，但Kamata 算法仍存在如下2 個問題，影響其壓縮效率。

（1）采用傳統(tǒng)的Hilbert 解碼算法，解碼效率低。原文實(shí)驗(yàn)結(jié)果表明，Hilbert 掃描時間占整個壓縮過程的近50%。因此，若能提高Hilbert 掃描效率，必將大幅提高算法的壓縮效率。

（2）該算法采用分區(qū)后合并（MAP）的方式來合并小分段。直觀來看，合并有2 個主要思路：一是直接在位數(shù)組A和L中合并，然而這需要大量元素的移動和刪除的開銷，時間和空間開銷大；二是創(chuàng)建2 個新的位數(shù)組A′和L′，線性掃描位數(shù)組A和L，并將合并后的分區(qū)插入A′和L′。這同樣需要較大的時間和空間開銷。

針對上述問題，本文設(shè)計(jì)高效的FZF-MIP 壓縮算法，引入一種高效Hilbert 解碼算法FZF-HD，此外設(shè)計(jì)高效的分區(qū)中合并（MIP）策略，從而大幅提高圖像壓縮效率。

2.2 高效Hilbert 解碼算法

針對Kamata 算法中Hilbert 掃描時間占比大問題，本文引入免計(jì)前零階的高效Hilbert 解碼算法FZF-HD[15]。FZF-HD 依托2 個簡單、高效的狀態(tài)視圖InvKey和InvType實(shí)現(xiàn)。其中，InvKey表示某階編碼值到該階坐標(biāo)值的映射，InvType表示某階狀態(tài)到下一階狀態(tài)的映射，分別如表1 和2 所示。此外，F(xiàn)ZF-HD 可檢測并跳過輸入編碼值前部全0 的階，從而提高編碼效率。算法的基本步驟如下：

表1 狀態(tài)視圖InvKey

（1）利用msb算法[16]檢測輸入編碼值前部全為0 的階的數(shù)量q；

（2）從q+1 階迭代查詢狀態(tài)視圖進(jìn)行編碼。

表2 狀態(tài)視圖InvType

最終，F(xiàn)ZF-HD 算法（代碼截圖）如圖3 所示。

圖3 FZF-HD 算法代碼截圖

2.3 分區(qū)中合并策略MIP

針對Kamata 算法MAP 策略導(dǎo)致大量需合并的小分段的不足，本文設(shè)計(jì)高效的分區(qū)中合并（MIP）的策略來避免這一不足。MIP 的核心思想如下。

（1）設(shè)cur為第一個滿足分區(qū)長度閾值Lmax和分區(qū)方差閾值Emax的小分區(qū)P1。

（2）對第i個（i≥2）待插入位數(shù)組A和L中的小分區(qū)Pi，根據(jù)式（2）、式（3）和式（4）判斷其是否可以與cur合并，如可以合并，則延遲Pi的插入，將其與cur合并后繼續(xù)執(zhí)行步驟（2），合并后的新分區(qū)cur=的像素均值和長度為計(jì)算式為式（5）和式（6）：

（3）如Pi不能和cur合并，則將cur插入到位數(shù)組A和L后，令cur=Pi，繼續(xù)執(zhí)行步驟（2）。

示例1：假設(shè)L2max=10，Gmax=10，Lmax=64，給定依次劃分出的小分區(qū)P1=<167,6>，P2=<160,8>，P3=<175,6>，P4=<167,27>。

初始時cur=P1，對于分區(qū)P2，因其滿足LP2≤L2max，|AP1-AP2|=7 ≤Gmax，LP1+LP2=6+8=14 ≤Lmax，故 將P2 并 入 到cur后 如 圖4 的 過 程①，得cur=<163,14>。當(dāng)i=3 時，LP3≤L2max，|A′cur-AP3|=|175-163|=12>Gmax且L′cur+LP3=14+6=20 ≤Lmax因P3 不滿足式（3），如圖4 中的過程②，故此時將cur插入到位數(shù)組得A=(163)2=10 100 011 和L=(14)2=001 110。令cur=P3 后，繼續(xù)從i=4 重復(fù)執(zhí)行該過程。

圖4 MIP 示意圖

由上可見，與MAP 不同的是，MIP 采用延遲插入的策略將分區(qū)過程和合并過程融為一體，從而減少后續(xù)合并的開銷，無需額外的存儲空間，因此可有效提高圖像壓縮效率?；谏鲜鼋榻B，實(shí)現(xiàn)的FZF-MIP 算法（代碼截圖）如圖5 所示。

圖5 FZF-MIP 算法

算法中，ComputeHOrder 對給定圖像的大小，計(jì)算其對應(yīng)的Hilbert 階數(shù)，如對XSIZE=512，YSIZE=512 的圖像，其對應(yīng)的Hilbert 空間的階數(shù)為9。

2.4 解壓算法設(shè)計(jì)

解壓過程為壓縮過程的逆過程，即將壓縮后的圖像復(fù)原。本文中，分別從位數(shù)組L讀取log2(Lmax)位分區(qū)p的長度信息LP，從A中讀取分段p的8位灰度信息AP，通過Hilbert 解碼獲得物理坐標(biāo)，將相應(yīng)坐標(biāo)對應(yīng)的像素值設(shè)置為AP。循環(huán)上述過程，直到處理完數(shù)組L和A內(nèi)的所有分段，完成圖像解壓。

3 實(shí)驗(yàn)結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境：CPU 為Intel（R）Core（TM）i7-7500U CPU @2.7 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows 10，編譯環(huán)境為Microsoft Visual Studio 2015且禁用了優(yōu)化（/Od）。

為詳細(xì)考察壓縮算法的性能，采用以下數(shù)據(jù)集。

（1）為驗(yàn)證Hilbert 掃描算法FZF-HD 的效率，分別將k=4，8，12，16 階Hilbert 空間內(nèi)的所有點(diǎn)作為點(diǎn)數(shù)據(jù)集，每個空間共包含2k×2k個k階數(shù)據(jù)點(diǎn)。

（2）為驗(yàn)證MIP 策略對壓縮和解壓效率的影響，采用Granada 大學(xué)計(jì)算機(jī)視覺組提供的灰度圖像數(shù)據(jù)集GrayImages 進(jìn)行壓縮和解壓。該數(shù)據(jù)集包含49 張大小為512×512 的灰度圖像，每張圖像對應(yīng)Hilbert 階數(shù)為9 階。

實(shí)驗(yàn)中，初始參數(shù)設(shè)置為：Lmax=64，Emax=2 000，L2max=10，Gmax=10，初始分區(qū)長度P=256。

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 Hilbert 掃描時間對比

為驗(yàn)證Hilbert 掃描算法FZF-HD 的效率，在點(diǎn)數(shù)據(jù)集上，將FZF-HD 與Moore、Burkardt[13]、Li[14]、Unistate 算法對比。為方便描述，為各解碼算法標(biāo)注后綴“-HD”。實(shí)驗(yàn)結(jié)果如圖6 所示，圖6 中y軸坐標(biāo)為對數(shù)坐標(biāo)。

由圖6 可知，在解碼2k×2k個數(shù)據(jù)點(diǎn)時，隨著階數(shù)k的增加，所有算法的解碼時間均隨階數(shù)的增加而指數(shù)增加。相對而言，當(dāng)k為16 時，F(xiàn)ZF-HD算法解碼效率在Li 的算法基礎(chǔ)上提高了11.3%，相對于Burkardt 算法，F(xiàn)ZF 算法解碼效率提高2.5 倍。由此可見，F(xiàn)ZF-HD 算法具有較高的解碼效率，且隨著階數(shù)的增加，解碼優(yōu)勢不斷增加。

圖6 Hilbert 解碼效率對照圖

基于不同的解碼算法，本文對GrayImages 中的圖像進(jìn)行壓縮和解壓（其中壓縮時采用MAP 的策略），并對比不同Hilbert 掃描時間及其占總的壓縮和解碼時間的比例，結(jié)果分別如圖7 和圖8 所示。

圖7 Hilbert 掃描占壓縮比重對照圖

圖8 Hilbert 掃描占解壓比重對照圖

由圖7、圖8 可知，相對Burkardt-HD 算法，基于FZF-HD 算法壓縮時間和解壓縮時間可以分別減少33.5%和39%。Burkardt 算法和Moore 算法分別占其總壓縮時間的40%和解壓時間的50%以上，而對于FZF-HD，該值僅分別為21.1%和27.1%。因此，高效Hilbert 解碼算法可以顯著提高壓縮和解壓縮效率。

3.2.2 算法壓縮性能

為驗(yàn)證小分區(qū)合并的必要性，對GrayImages 中所有圖像進(jìn)行壓縮，統(tǒng)計(jì)平均每張圖片合并和未合并的信息對比，如表3 所示。

表3 合并和未合并小分區(qū)信息對比

由表3 可知，將小分段合并，能節(jié)約大量存儲空間，合并后的壓縮率由0.210 319%降低至0.175 818%，空間開銷降低16.4%。

值得注意的是，本文的優(yōu)化算法并不會改變原有Kamata 算法的壓縮效果。以蝴蝶圖片為例，壓縮及解壓后的圖像對比如圖9（a）和圖9（b）所示?？梢?，壓縮過程中，圖像基本保持原貌，損失的部分對理解原始圖像的影響很小，卻換來了較大的壓縮比。

圖9 壓縮前后對照圖

3.2.3 不同分區(qū)合并策略的對比

為進(jìn)一步考察不同分區(qū)合并策略的時間開銷，在采用FZF-HD 進(jìn)行Hilbert 掃描的基礎(chǔ)上，將FZF-MAP（FZF-HD 和MAP 結(jié)合）和FZF-MIP 進(jìn)行對比，其時間開銷如圖10 所示。

圖10 不同合并策略下效率對照圖

由圖10 可知，在引入分區(qū)中合并策略MIP 后，相對MAP 策略，壓縮49 張圖片的時間由7.092 s 降低到6.733 s，效率提高5.1%，表明分區(qū)中合并策略可避免合并時數(shù)組內(nèi)的大量元素移動，從而提高圖像的壓縮效率。

總體而言，相對原Kamata 算法，F(xiàn)ZF-MIP 壓縮GrayImages 數(shù)據(jù)集用時6.733 s，相對Kamata 的FZF-MAP，綜合壓縮效率提升近37.8%。

4 結(jié) 語

針對Kamata 圖像壓縮算法中Hilbert 掃描過程在壓縮中占的比重較大，分區(qū)后合并策略導(dǎo)致壓縮過程空間開銷大、復(fù)雜度較高的不足，本文引入高效的Hilbert 解碼算法FZF-HD 和分區(qū)中合并策略MIP 對其進(jìn)行優(yōu)化，從而有效提升了壓縮效率。下一步擬對高維圖像壓縮領(lǐng)域進(jìn)一步深入研究。