漸近式圖像無(wú)損壓縮算法

武海艷，唐海玲

(黃河科技學(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ù)包括有損壓縮和無(wú)損壓縮。其中無(wú)損壓縮相比有損壓縮具有能100%保留原始信息、無(wú)信號(hào)丟失且不受信號(hào)源等優(yōu)點(diǎn)，在諸多領(lǐng)域中得到廣泛應(yīng)用［2-6］。

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

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

1.1 圖像掃描

圖像掃描簡(jiǎn)單來(lái)說(shuō)就是讀取圖像的數(shù)據(jù)以更進(jìn)一步的處理，由于圖像的信源數(shù)據(jù)不是互相獨(dú)立的，是一組有記憶的數(shù)據(jù)，相鄰像素之間具有一定的相關(guān)性。為最大限度地去除像素間的冗余度，提高壓縮效率，對(duì)圖像數(shù)據(jù)進(jìn)行掃描。由于圖像的紋理特性較多，本文使用了3種形式的掃描，橫向掃描、縱向掃描、Zigzag掃描(見(jiàn)圖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)行位平面分解過(guò)程的介紹，對(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)過(guò)格雷碼轉(zhuǎn)換和位平面分解后，得到的二進(jìn)制 碼 流 為 00000000，00111111，11110000，00101111，11000111，二進(jìn)制碼間的相關(guān)性顯著提高。

2 漸近式壓縮編碼

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

2.1 轉(zhuǎn)換算法

轉(zhuǎn)換過(guò)程的目的是進(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)然后將二值信源信息按長(zhǎng)度p分為各個(gè)轉(zhuǎn)換單元，依據(jù)轉(zhuǎn)換標(biāo)記值為1的位置，將二值信源各轉(zhuǎn)換單元中相應(yīng)位置的值提取到序列的前端，轉(zhuǎn)換后的碼流長(zhǎng)度為L(zhǎng)+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，其他不變(見(jiàn)圖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)過(guò)了轉(zhuǎn)換處理，后面的p比特則為相應(yīng)的轉(zhuǎn)換標(biāo)志位，值為“0”則表示沒(méi)有經(jīng)過(guò)轉(zhuǎn)換處理，轉(zhuǎn)換標(biāo)志位不存在，可見(jiàn)增加1 bit的轉(zhuǎn)換標(biāo)記是非常有必要的，可以很大程度地防止沒(méi)有轉(zhuǎn)換處理時(shí)轉(zhuǎn)換標(biāo)志位的浪費(fèi)，節(jié)省了碼字開(kāi)銷。

2.2 編碼算法

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

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

編碼過(guò)程:

1)令白長(zhǎng)為L(zhǎng)0m(m≥1，L0m≥1)，黑長(zhǎng)為L(zhǎng)1n(n≥1，L1n≥1)，根據(jù)實(shí)驗(yàn)結(jié)果，選擇合適的白長(zhǎng)特征長(zhǎng)度l0p(p≥1，1≤l0p＜16)和黑長(zhǎng)的特征長(zhǎng)度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的白長(zhǎng)和黑長(zhǎng)編碼為

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

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

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

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

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

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

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

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

以下是解碼過(guò)程:

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的白長(zhǎng)和黑長(zhǎng)解碼為將不滿足此解碼條件的序列無(wú)需解碼直接按順序存儲(chǔ)在解碼后的序列中。

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

2.3 編碼過(guò)程

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

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

2)根據(jù)壓縮算法對(duì)S1進(jìn)行壓縮，得到壓縮后的碼流S2(長(zhǎng)度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)測(cè)試圖中的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)來(lái)衡量，而無(wú)損壓縮不存在PSNR這個(gè)指標(biāo)。本文將對(duì)壓縮比進(jìn)行比較。

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

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

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

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

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

4 結(jié)語(yǔ)

文中提出了一種漸近式無(wú)損圖像壓縮算法，算法在編碼前先對(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)換過(guò)程與編碼過(guò)程的交替，完成數(shù)據(jù)的壓縮。經(jīng)過(guò)多次實(shí)驗(yàn)表明，本文提出的漸近式壓縮算法適用于各種紋理的圖像，通過(guò)與長(zhǎng)度減半算法的實(shí)驗(yàn)對(duì)比，本文的算法具有更高的壓縮比。

:

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

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

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

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

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

［6］孟凡勇.Huffman編碼在環(huán)保實(shí)時(shí)監(jiān)測(cè)系統(tǒng)中的研究與應(yīng)用［D］.青島:中國(guó)海洋大學(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］高健，劉萬(wàn)，宋奧，等.基于長(zhǎng)度減半的二進(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.