王炳月,賈連印,范 瑤,孫劭文
(昆明理工大學(xué) 信息工程與自動化學(xué)院,云南 昆明 650500)
圖像是重要的信息載體[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 編碼作為熵并基于小波變換對圖像進行壓縮,取得了較好的壓縮效果。LZW 編碼通過構(gòu)建編譯表,實現(xiàn)字符重用及編碼,在圖像壓縮中也得到了廣泛應(yīng)用,如BADSHAH[7]的基于LZW編碼的水印壓縮技術(shù),謝等人[8]采用Hilbert 掃描將像素進行重排并基于LZW 編碼對圖像進行壓縮等。游程編碼是統(tǒng)計編碼的一種,利用符號串代替相同連續(xù)符號實現(xiàn)數(shù)據(jù)壓縮,例如基于正六邊形柵格的游程編碼壓縮技術(shù)[9]等。算術(shù)編碼是將整個輸入編碼為一個數(shù)的熵的編碼方式,如KUMAR等人[10]提出的基于多項式分布和算術(shù)編碼的壓縮方法。
圖像壓縮[2]的一個重要任務(wù)是最大化像素之間的相關(guān)性,使得復(fù)原的圖像在保持質(zhì)量的同時,盡可能提高壓縮率和壓縮效率。傳統(tǒng)的圖像壓縮算法多采用柵格掃描的策略,逐行掃描圖像然后進行壓縮。然而,柵格掃描的圖像并不能最大程度地使相鄰的位置(往往具有相似的像素值)劃分到同一個分段,因此對掃描后的圖像壓縮時將導(dǎo)致大量小分段的產(chǎn)生。
HILBERT 曲線[11]作為Peano 填充曲線的一個重要分支,因具有較好的內(nèi)聚性,可更好地把相鄰的位置劃分到同一分段。相對柵格掃描,它可使得更多像素值接近的位置點壓縮為一個分區(qū),進而可降低分區(qū)數(shù)量,提高壓縮效率,所以Hilbert 曲線在圖像分析、圖像壓縮、圖像加密以及圖像存儲與檢索等領(lǐng)域得到了廣泛應(yīng)用[8,12]。
KAMATA 提出的Hilbert 掃描灰度圖像壓縮算法[4]是基于Hilbert曲線對圖像進行壓縮的經(jīng)典代表。其在基于Hilbert 掃描的一維數(shù)組上進行壓縮,比在基于柵格掃描的數(shù)組上有更高的壓縮率,實驗結(jié)果表明,該算法有著相較JPEG更好的壓縮效果。然而,其采用早期的Hilbert 解碼算法,解碼時間占壓縮總時間的約50%,壓縮效率較低。此外,其采用分區(qū)后合并(MAP)的策略將小分區(qū)進行合并,導(dǎo)致較高的時間和空間開銷。
為解決上述問題,本文在對現(xiàn)有Hilbert 解碼算 法( 如Moore-HD、Burkardt-HD[13]、Li-HD[14]、Unistate-HD、FZF-HD[16])進行深入研究對比的基礎(chǔ)上,引入高效的FZF-HD Hilbert 解碼算法(FZF)及分區(qū)中合并(MIP)的圖像壓縮算法FZF-MIP。通過FZF-HD 算法,可避免對輸入編碼值前部為0的階迭代解碼,可大幅降低圖像壓縮時間。此外,通過設(shè)計高效的MIP 策略,將分區(qū)和合并的步驟融合,從而避免分區(qū)后合并的開銷,進一步提高了圖像壓縮的效率。擴展實驗結(jié)果表明了FZF-MIP 算法的有效性。
1階Hilbert曲線將整個空間分割成4個子區(qū)域,將左下、左上、右上、右下這4 個子區(qū)域依次連接起來,即可構(gòu)成開口向下的1 階Hilbert 曲線。通過在1 階曲線的每個網(wǎng)格嵌入一個1 階曲線,并進行相應(yīng)的旋轉(zhuǎn)和翻轉(zhuǎn),即可得到2 階Hilbert 曲線。重復(fù)這個過程,即可得到n階Hilbert 曲線。不同分辨率對應(yīng)Hilbert 曲線如圖1 所示。
圖1 Hilbert 不同分辨率對照圖
KAMATA 提出基于Hilbert 掃描的灰度圖像壓縮算法[4],首先基于Hilbert 掃描,將圖像映射為一維數(shù)組,然后基于線性插值中的零階插值對數(shù)據(jù)進行遞歸分割。最終將圖像壓縮為一個像素數(shù)組A和長度數(shù)組L。其算法框架如圖2 所示,算法執(zhí)行流程如下。
圖2 Kamata 算法框架圖
(1)基于Hilbert 解碼算法掃描圖像,將初始圖像掃描為一個數(shù)組D。通過Hilbert 掃描可使空間上相鄰的點,在曲線上編碼值盡可能地接近。
(2)將數(shù)組D分割成具有長度為M的多個初始分區(qū)P。
(3)對每個初始分區(qū)P按照方差和最小的原則依次劃分為2 個分區(qū),即找到一個分割點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 進一步合并為一個分區(qū)。
式中:L2max表示待合并的小分區(qū)的長度閾值,Gmax表示P1 和P2 的像素均值之差。
(5)最終合并小分區(qū)后的位數(shù)組A和L即為圖像壓縮后的結(jié)果。
盡管有較好的壓縮效果,但Kamata 算法仍存在如下2 個問題,影響其壓縮效率。
(1)采用傳統(tǒng)的Hilbert 解碼算法,解碼效率低。原文實驗結(jié)果表明,Hilbert 掃描時間占整個壓縮過程的近50%。因此,若能提高Hilbert 掃描效率,必將大幅提高算法的壓縮效率。
(2)該算法采用分區(qū)后合并(MAP)的方式來合并小分段。直觀來看,合并有2 個主要思路:一是直接在位數(shù)組A和L中合并,然而這需要大量元素的移動和刪除的開銷,時間和空間開銷大;二是創(chuàng)建2 個新的位數(shù)組A′和L′,線性掃描位數(shù)組A和L,并將合并后的分區(qū)插入A′和L′。這同樣需要較大的時間和空間開銷。
針對上述問題,本文設(shè)計高效的FZF-MIP 壓縮算法,引入一種高效Hilbert 解碼算法FZF-HD,此外設(shè)計高效的分區(qū)中合并(MIP)策略,從而大幅提高圖像壓縮效率。
針對Kamata 算法中Hilbert 掃描時間占比大問題,本文引入免計前零階的高效Hilbert 解碼算法FZF-HD[15]。FZF-HD 依托2 個簡單、高效的狀態(tài)視圖InvKey和InvType實現(xiàn)。其中,InvKey表示某階編碼值到該階坐標值的映射,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)視圖進行編碼。
表2 狀態(tài)視圖InvType
最終,F(xiàn)ZF-HD 算法(代碼截圖)如圖3 所示。
圖3 FZF-HD 算法代碼截圖
針對Kamata 算法MAP 策略導(dǎo)致大量需合并的小分段的不足,本文設(shè)計高效的分區(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=的像素均值和長度為計算式為式(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>。當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ù)合并的開銷,無需額外的存儲空間,因此可有效提高圖像壓縮效率。基于上述介紹,實現(xiàn)的FZF-MIP 算法(代碼截圖)如圖5 所示。
圖5 FZF-MIP 算法
算法中,ComputeHOrder 對給定圖像的大小,計算其對應(yīng)的Hilbert 階數(shù),如對XSIZE=512,YSIZE=512 的圖像,其對應(yīng)的Hilbert 空間的階數(shù)為9。
解壓過程為壓縮過程的逆過程,即將壓縮后的圖像復(fù)原。本文中,分別從位數(shù)組L讀取log2(Lmax)位分區(qū)p的長度信息LP,從A中讀取分段p的8位灰度信息AP,通過Hilbert 解碼獲得物理坐標,將相應(yīng)坐標對應(yīng)的像素值設(shè)置為AP。循環(huán)上述過程,直到處理完數(shù)組L和A內(nèi)的所有分段,完成圖像解壓。
實驗環(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)。
為詳細考察壓縮算法的性能,采用以下數(shù)據(jù)集。
(1)為驗證Hilbert 掃描算法FZF-HD 的效率,分別將k=4,8,12,16 階Hilbert 空間內(nèi)的所有點作為點數(shù)據(jù)集,每個空間共包含2k×2k個k階數(shù)據(jù)點。
(2)為驗證MIP 策略對壓縮和解壓效率的影響,采用Granada 大學(xué)計算機視覺組提供的灰度圖像數(shù)據(jù)集GrayImages 進行壓縮和解壓。該數(shù)據(jù)集包含49 張大小為512×512 的灰度圖像,每張圖像對應(yīng)Hilbert 階數(shù)為9 階。
實驗中,初始參數(shù)設(shè)置為:Lmax=64,Emax=2 000,L2max=10,Gmax=10,初始分區(qū)長度P=256。
3.2.1 Hilbert 掃描時間對比
為驗證Hilbert 掃描算法FZF-HD 的效率,在點數(shù)據(jù)集上,將FZF-HD 與Moore、Burkardt[13]、Li[14]、Unistate 算法對比。為方便描述,為各解碼算法標注后綴“-HD”。實驗結(jié)果如圖6 所示,圖6 中y軸坐標為對數(shù)坐標。
由圖6 可知,在解碼2k×2k個數(shù)據(jù)點時,隨著階數(shù)k的增加,所有算法的解碼時間均隨階數(shù)的增加而指數(shù)增加。相對而言,當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 中的圖像進行壓縮和解壓(其中壓縮時采用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 算法壓縮性能
為驗證小分區(qū)合并的必要性,對GrayImages 中所有圖像進行壓縮,統(tǒng)計平均每張圖片合并和未合并的信息對比,如表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ū)合并策略的對比
為進一步考察不同分區(qū)合并策略的時間開銷,在采用FZF-HD 進行Hilbert 掃描的基礎(chǔ)上,將FZF-MAP(FZF-HD 和MAP 結(jié)合)和FZF-MIP 進行對比,其時間開銷如圖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%。
針對Kamata 圖像壓縮算法中Hilbert 掃描過程在壓縮中占的比重較大,分區(qū)后合并策略導(dǎo)致壓縮過程空間開銷大、復(fù)雜度較高的不足,本文引入高效的Hilbert 解碼算法FZF-HD 和分區(qū)中合并策略MIP 對其進行優(yōu)化,從而有效提升了壓縮效率。下一步擬對高維圖像壓縮領(lǐng)域進一步深入研究。