武海艷，唐海玲

(黃河科技學(xué)院a.鄭州市智能圖像處理與識(shí)別重點(diǎn)實(shí)驗(yàn)室;b.鄭州市物聯(lián)網(wǎng)傳感技術(shù)及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室;c.信息工程學(xué)院，河南鄭州450063)

圖像數(shù)據(jù)壓縮作為實(shí)現(xiàn)圖像數(shù)據(jù)的存儲(chǔ)和傳輸?shù)暮诵膬?nèi)容受到廣泛的關(guān)注［1］。數(shù)據(jù)壓縮是指利用壓縮算法減少數(shù)據(jù)冗余并保持高保真度，有效地節(jié)約存儲(chǔ)空間、提高數(shù)據(jù)傳輸效率。數(shù)據(jù)壓縮技術(shù)包括有損壓縮和無損壓縮。其中無損壓縮相比有損壓縮具有能100%保留原始信息、無信號(hào)丟失且不受信號(hào)源等優(yōu)點(diǎn)，在諸多領(lǐng)域中得到廣泛應(yīng)用［2-6］。

游程編碼(RLC)是最重要的圖像無損壓縮方法之一，是圖像的編碼標(biāo)準(zhǔn)JPEG和傳真通信國際電信聯(lián)盟ITU-T標(biāo)準(zhǔn)的組成部分［7-9］。其思想為數(shù)據(jù)項(xiàng)a在數(shù)據(jù)流中連續(xù)出現(xiàn)n次，則以單個(gè)字符nd來替換連續(xù)出現(xiàn)n次的數(shù)據(jù)項(xiàng)d，n稱為游程，從而節(jié)省存儲(chǔ)空間?？墒钱?dāng)每兩個(gè)相鄰點(diǎn)的顏色都不同時(shí)，RLC壓縮數(shù)據(jù)量反而會(huì)增加［10］。為此，文獻(xiàn)［10-12］提出相同數(shù)據(jù)項(xiàng)3個(gè)或3個(gè)以上才使用RLC編碼，但需設(shè)立標(biāo)志位;文獻(xiàn)［13］提出的基于長度減半的二進(jìn)制碼流的壓縮算法，按照碼流中的連續(xù)“1”的個(gè)數(shù)(黑長)、連續(xù)“0”的個(gè)數(shù)(白長)的分布特點(diǎn)選取相應(yīng)初始長度進(jìn)行減半壓縮處理，但是仍存在數(shù)據(jù)冗余。鑒于上述原因，本文提出一種漸近式壓縮編碼技術(shù)，按圖像無損壓縮的基本步驟［14］，在長度減半壓縮算法基礎(chǔ)上改進(jìn)編碼思想減少編碼的數(shù)據(jù)冗余，并對(duì)編碼后的碼流進(jìn)行自適應(yīng)轉(zhuǎn)換以提高碼流的相關(guān)性，從而提高壓縮效率。

1 圖像壓縮預(yù)處理

1.1 圖像掃描

圖像掃描簡單來說就是讀取圖像的數(shù)據(jù)以更進(jìn)一步的處理，由于圖像的信源數(shù)據(jù)不是互相獨(dú)立的，是一組有記憶的數(shù)據(jù)，相鄰像素之間具有一定的相關(guān)性。為最大限度地去除像素間的冗余度，提高壓縮效率，對(duì)圖像數(shù)據(jù)進(jìn)行掃描。由于圖像的紋理特性較多，本文使用了3種形式的掃描，橫向掃描、縱向掃描、Zigzag掃描(見圖1)。

1.2 位平面分解

在圖像壓縮之前，為提高二進(jìn)制數(shù)據(jù)的相關(guān)性，根據(jù)式(1)將二進(jìn)制碼轉(zhuǎn)換為格雷碼，并對(duì)圖像進(jìn)行位平面分解。

二進(jìn)制碼轉(zhuǎn)換為格雷碼的公式為

式中:gi為格雷碼的碼字;bi為二進(jìn)制的碼字;⊕為模2加法運(yùn)算。

下面進(jìn)行位平面分解過程的介紹，對(duì)于一幅圖像，每一個(gè)像素點(diǎn)都可以表示為1個(gè)8位二進(jìn)制碼，各像素點(diǎn)的二進(jìn)制碼在相同位置上的值構(gòu)成的平面，稱為位平面。在大多數(shù)的圖像中相鄰的像素值變化很小，所以構(gòu)成的位平面中數(shù)據(jù)間具有很大的相關(guān)性。為進(jìn)一步提高二進(jìn)制數(shù)據(jù)的相關(guān)性，對(duì)圖像進(jìn)行位平面分解，并將圖像位平面的二進(jìn)制碼依次排序。例如灰度圖像的相鄰灰度值為35，36，34，35，37，38，這些灰度值的十進(jìn)制碼是非常接近的，表示為二進(jìn)制碼后為 00100011，00100100，00100010，00100011，00100101，00100110，可以看出二進(jìn)制碼間的相關(guān)性不好，經(jīng)過格雷碼轉(zhuǎn)換和位平面分解后，得到的二進(jìn)制 碼 流 為 00000000，00111111，11110000，00101111，11000111，二進(jìn)制碼間的相關(guān)性顯著提高。

2 漸近式壓縮編碼

對(duì)預(yù)處理后的二進(jìn)制碼流S(長度L)進(jìn)行壓縮編碼，根據(jù)轉(zhuǎn)換算法得到轉(zhuǎn)換后的碼流S1(長度L1)，轉(zhuǎn)換后的數(shù)據(jù)按照所給句法存儲(chǔ);根據(jù)壓縮算法對(duì)S1進(jìn)行壓縮，得到壓縮后的碼流S2(長度L2)，按照所給句法存儲(chǔ);如果滿足L2＜L1，則返回再一次進(jìn)行轉(zhuǎn)換，否則按圖中的句法結(jié)構(gòu)存儲(chǔ)壓縮完成的最終數(shù)據(jù)。漸近式壓縮算法包括轉(zhuǎn)換、編碼兩個(gè)核心算法。

2.1 轉(zhuǎn)換算法

轉(zhuǎn)換過程的目的是進(jìn)一步調(diào)整二進(jìn)制碼流以提高碼字間的相關(guān)性從而提高壓縮效率。

1)首先定義一串連續(xù)的二進(jìn)制碼為轉(zhuǎn)換標(biāo)記aggregation_idc，如令轉(zhuǎn)換標(biāo)記為ω1ω2…ωp，(ωi取0 或1，1≤i≤p，p≥2);

2)然后將二值信源信息按長度p分為各個(gè)轉(zhuǎn)換單元，依據(jù)轉(zhuǎn)換標(biāo)記值為1的位置，將二值信源各轉(zhuǎn)換單元中相應(yīng)位置的值提取到序列的前端，轉(zhuǎn)換后的碼流長度為L+P。

例如取P=8，則轉(zhuǎn)換標(biāo)記aggregation_idc的取值種類為0～28-1(0～255)，令aggregation_idc=01000010，即分別將二值信源D各個(gè)轉(zhuǎn)換單元S1的第2位和第7位的二值數(shù)移到序列的前面得到S2，其他不變(見圖2)。

圖2 轉(zhuǎn)換例子

轉(zhuǎn)換后的結(jié)果S3由轉(zhuǎn)換標(biāo)志位和轉(zhuǎn)換后的序列兩部分組成，比較S1與S3可以看出，轉(zhuǎn)換后的序列相關(guān)性提高有利于更進(jìn)一步的壓縮。按圖3的句法結(jié)構(gòu)保存轉(zhuǎn)換后的數(shù)據(jù)。句法中的“轉(zhuǎn)換標(biāo)記”占1 bit，若值為“1”表示經(jīng)過了轉(zhuǎn)換處理，后面的p比特則為相應(yīng)的轉(zhuǎn)換標(biāo)志位，值為“0”則表示沒有經(jīng)過轉(zhuǎn)換處理，轉(zhuǎn)換標(biāo)志位不存在，可見增加1 bit的轉(zhuǎn)換標(biāo)記是非常有必要的，可以很大程度地防止沒有轉(zhuǎn)換處理時(shí)轉(zhuǎn)換標(biāo)志位的浪費(fèi)，節(jié)省了碼字開銷。

2.2 編碼算法

現(xiàn)有的RLC方法大多基于編碼表或字典，很明顯這些方法不適合碼字間相關(guān)性低的碼流壓縮。編碼算法是本文漸近式無損壓縮算法的核心部分，而上文中的轉(zhuǎn)換過程都是為能得到更好的壓縮效率。本文的編碼算法不需要任何編碼表或字典，可以對(duì)局部碼流多次壓縮。

在RLC算法中，將具有相同灰度值的相鄰像素組成的序列稱為游程，游程中像素的個(gè)數(shù)稱為游長。在二值圖像中，其中:連續(xù)“1”的個(gè)數(shù)稱為黑長，連續(xù)“0”的個(gè)數(shù)稱為白長。

編碼過程:

1)令白長為L0m(m≥1，L0m≥1)，黑長為L1n(n≥1，L1n≥1)，根據(jù)實(shí)驗(yàn)結(jié)果，選擇合適的白長特征長度l0p(p≥1，1≤l0p＜16)和黑長的特征長度l1q(q≥1，1≤l1q＜16)，迭代次數(shù)為N，初始值設(shè)為0。

2)將二進(jìn)制序列中L0m和L1n的分為四類:L0m≥l0p，L0m＜l0p，L1n≥l1q，L1n＜l1q，將分別滿足L0m≥l0p與L1n≥l1q的白長和黑長編碼為

式中:所得到的商表示Q0mp個(gè)連續(xù)的“0”和Q1nq個(gè)連續(xù)的“1”;余數(shù)R0mp和R1nq分別為“0”和“1”。所有的商在一起保存為商序列Tk1，所有的余數(shù)在一起保存為余數(shù)序列Tk2，不滿足編碼條件的黑長和白長直接按順序存儲(chǔ)在Tk1中。

3)將l0p、l1q、Tk1和反向存儲(chǔ)的Tk2按順序存放在一起作為下一次編碼的原序列，迭代次數(shù)N加1;

4)轉(zhuǎn)到步驟2)，將步驟3)中得到的二進(jìn)制序列進(jìn)行編碼，直到不能壓縮為止;

5)經(jīng)過K次編碼后，參照?qǐng)D4中的句法結(jié)構(gòu)保存結(jié)果。句法“迭代次數(shù)”占用8 bit，取值范圍為0～28-1(0～255)，因此最多可允許進(jìn)行255次迭代運(yùn)算。下面舉例說明。

圖4 壓縮算法的句法結(jié)構(gòu)

S21是一段視頻二進(jìn)制碼流，經(jīng)過轉(zhuǎn)換處理，現(xiàn)在的長度為191 bit。

令l01=4(01002)，l11=2(00102)，根據(jù)以上的編碼步驟2)可得商序列T11和余數(shù)序列T12。

可以看到編碼后表示商的碼字與游長L0m＜l0p或L1n＜l1q的碼字不會(huì)有重碼出現(xiàn)，因此可以重復(fù)步驟2)進(jìn)行多次編碼。將多次編碼后的l01、l11、T11和反向的T12放在一起構(gòu)成序列S22。

令l02=3(00112)，l12=5(01012)，得到商序列T21和余數(shù)序列T22，S23為編碼后的序列。

假設(shè)S23是最后一次編碼得到的序列，在序列前加上迭代編碼的次數(shù)，就是編碼后的最終序列S24。

多次實(shí)驗(yàn)顯示黑長和白長都小于16，因此只需分配黑長和白長各4 bit。對(duì)余數(shù)序列進(jìn)行反向存儲(chǔ)，這樣在解碼時(shí)不需要知道商序列和余數(shù)序列的長度或設(shè)置任何標(biāo)志位，只需從左右兩個(gè)方向分別取商和余數(shù)直到取完為止。經(jīng)過兩次編碼后數(shù)據(jù)由191壓縮到138。在編碼過程中，壓縮步驟與轉(zhuǎn)換過程是捆綁進(jìn)行的，使用轉(zhuǎn)換算法可以得到進(jìn)一步的壓縮。

以下是解碼過程:

1)從碼流的首部讀取迭代次數(shù)(8 bit)的值。2)依次讀取l0p(4 bit)和l1q(4 bit)的值。

3)將二進(jìn)制序列中L0m和L1n的分為4類，L0m≥l0p，L0m＜l0p，L1n≥l1q，L1n＜l1q，將分別滿足L0m≥l0p與L1n≥l1q的白長和黑長解碼為將不滿足此解碼條件的序列無需解碼直接按順序存儲(chǔ)在解碼后的序列中。

迭代次數(shù)自減1，轉(zhuǎn)到步驟2)對(duì)從步驟3)中得到的解碼序列繼續(xù)解碼，直到迭代次數(shù)為0，解碼完成。

2.3 編碼過程

按照漸近式無損壓縮流程(圖5)對(duì)預(yù)處理后的二進(jìn)制碼流S(長度L)進(jìn)行壓縮編碼，步驟如下:

1)根據(jù)轉(zhuǎn)換算法得到轉(zhuǎn)換后的碼流S1(長度L1)，轉(zhuǎn)換后的數(shù)據(jù)按照?qǐng)D中的句法存儲(chǔ);

2)根據(jù)壓縮算法對(duì)S1進(jìn)行壓縮，得到壓縮后的碼流S2(長度L2)，按照?qǐng)D中句法存儲(chǔ);

3)如果滿足L2＜L1則返回步驟1)再一次進(jìn)行轉(zhuǎn)換，否則繼續(xù);

4)按圖中的句法結(jié)構(gòu)存儲(chǔ)壓縮完成的最終數(shù)據(jù)。

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

為了驗(yàn)證本算法的性能，選擇了標(biāo)準(zhǔn)測試圖中的20張圖像進(jìn)行實(shí)驗(yàn)，圖片規(guī)格分別為256×256和512×512的8位灰度圖(圖6)。首先對(duì)圖像數(shù)據(jù)進(jìn)行預(yù)處理，由于圖像的紋理千變?nèi)f化，對(duì)灰度圖像分別進(jìn)行橫向掃描、縱向掃描、Zigzag掃描并進(jìn)行比較，取其中相關(guān)性較好的掃描方法，這里采用統(tǒng)計(jì)圖像相鄰像素點(diǎn)的平均方差作為判斷圖像像素相關(guān)性的標(biāo)準(zhǔn)，平均方差越小，相關(guān)性越好。然后對(duì)掃描得到的數(shù)據(jù)進(jìn)行二進(jìn)制到格雷碼的轉(zhuǎn)換和位平面分解。最后使用本文提出的編碼方法對(duì)得到的二進(jìn)制碼流進(jìn)行編碼。壓縮質(zhì)量的客觀評(píng)價(jià)通常采用壓縮比C和峰值信噪比(PSNR)兩個(gè)指標(biāo)來衡量，而無損壓縮不存在PSNR這個(gè)指標(biāo)。本文將對(duì)壓縮比進(jìn)行比較。

圖6 經(jīng)典灰度測試圖

設(shè)圖像尺寸為M×N，每個(gè)像素為Bp比特，壓縮后總比特?cái)?shù)為B。壓縮比的計(jì)算公式為

對(duì)圖中的圖像經(jīng)測試后得到的數(shù)據(jù)記入表1，并將結(jié)果與長度減半算法進(jìn)行比較。

表1 經(jīng)典灰度圖像的壓縮比

從表1中的實(shí)驗(yàn)結(jié)果可以看出漸近式編碼方法能達(dá)到較好的壓縮效果，比長度減半算法要好。

4 結(jié)語

文中提出了一種漸近式無損圖像壓縮算法，算法在編碼前先對(duì)二進(jìn)制碼流進(jìn)行預(yù)處理，并對(duì)二進(jìn)制碼流的順序做出調(diào)整，提高了數(shù)據(jù)間的相關(guān)性，采用提出的編碼算法對(duì)數(shù)據(jù)進(jìn)行更深層次的壓縮，反復(fù)進(jìn)行轉(zhuǎn)換過程與編碼過程的交替，完成數(shù)據(jù)的壓縮。經(jīng)過多次實(shí)驗(yàn)表明，本文提出的漸近式壓縮算法適用于各種紋理的圖像，通過與長度減半算法的實(shí)驗(yàn)對(duì)比，本文的算法具有更高的壓縮比。

:

［1］姚慶棟，畢厚杰.圖像編碼基礎(chǔ)［M］.北京:清華大學(xué)出版社，2006.

［2］李雷定，馬鐵華，尤文斌.常用數(shù)據(jù)無損壓縮算法分析［J］.電子設(shè)計(jì)工程，2009(1):49-51.

［3］武曉玥.圖像無損壓縮及去噪技術(shù)研究［D］.西安:西安電子科技大學(xué)，2010.

［4］王春潔.無損圖像編碼技術(shù)研究［D］.湘潭:湘潭大學(xué)，2013.

［5］王大偉，于樂，章圣焰.靜態(tài)圖像無損/近無損壓縮技術(shù)研究［J］.航空電子技術(shù)，2013，44(3):31-35.

［6］孟凡勇.Huffman編碼在環(huán)保實(shí)時(shí)監(jiān)測系統(tǒng)中的研究與應(yīng)用［D］.青島:中國海洋大學(xué)，2010.

［7］ BENTLEY J L，SLEATOR D D，TARJAN R E，et al.A locally adaptive data compression scheme［J］.ACM Communications，1986，29(4):320-330.

［8］ TOGNERI R，DESILVA C J S.Fundamentals of information theory and coding design［M］.Boca Raton，F(xiàn)L，USA:CRC Press，2003.

［9］ SHEN Dingtao，CUI Can，WANG Jiechen.Implementation and application of intersection operation based on run-length encoding［C］//Proc.International Conference on Computer Science and Software Engineering.Wuhan:IEEE Press，2008:602-606.

［10］ LUSE M.Bitmapped graphics programming in C++［M］.Boston，MA，USA:Addison-Wesley Longman Publishing Co.，Inc.，1993.

［11］ ACHARYA T，TSAI P S.JPEG2000 standard for image compression:concepts，algorithms and VLSI architectures［S］.2004.

［12］ SALOMON D.Data compression:the complete reference［EB/OL］.［2013-11-20］.http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20&path=ASIN/0387406972.

［13］高健，劉萬，宋奧，等.基于長度減半的二進(jìn)制碼流的壓縮算法［J］.計(jì)算機(jī)應(yīng)用，2011(7):1856-1858.

［14］ BOVIK A C.The essential guide to image processing［EB/OL］.［2013-11-20］.http://www.doc88.com/p-397145670042.html.