漸近式圖像無損壓縮算法

武海艷，唐海玲

(黃河科技學院a.鄭州市智能圖像處理與識別重點實驗室;b.鄭州市物聯網傳感技術及其應用重點實驗室;c.信息工程學院，河南鄭州450063)

圖像數據壓縮作為實現圖像數據的存儲和傳輸的核心內容受到廣泛的關注［1］。數據壓縮是指利用壓縮算法減少數據冗余并保持高保真度，有效地節約存儲空間、提高數據傳輸效率。數據壓縮技術包括有損壓縮和無損壓縮。其中無損壓縮相比有損壓縮具有能100%保留原始信息、無信號丟失且不受信號源等優點，在諸多領域中得到廣泛應用［2-6］。

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

1 圖像壓縮預處理

1.1 圖像掃描

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

1.2 位平面分解

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

二進制碼轉換為格雷碼的公式為

式中:gi為格雷碼的碼字;bi為二進制的碼字;⊕為模2加法運算。

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

2 漸近式壓縮編碼

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

2.1 轉換算法

轉換過程的目的是進一步調整二進制碼流以提高碼字間的相關性從而提高壓縮效率。

1)首先定義一串連續的二進制碼為轉換標記aggregation_idc，如令轉換標記為ω1ω2…ωp，(ωi取0 或1，1≤i≤p，p≥2);

2)然后將二值信源信息按長度p分為各個轉換單元，依據轉換標記值為1的位置，將二值信源各轉換單元中相應位置的值提取到序列的前端，轉換后的碼流長度為L+P。

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

圖2 轉換例子

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

2.2 編碼算法

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

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

編碼過程:

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

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

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

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

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

5)經過K次編碼后，參照圖4中的句法結構保存結果。句法“迭代次數”占用8 bit，取值范圍為0～28-1(0～255)，因此最多可允許進行255次迭代運算。下面舉例說明。

圖4 壓縮算法的句法結構

S21是一段視頻二進制碼流，經過轉換處理，現在的長度為191 bit。

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

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

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

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

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

以下是解碼過程:

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

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

迭代次數自減1，轉到步驟2)對從步驟3)中得到的解碼序列繼續解碼，直到迭代次數為0，解碼完成。

2.3 編碼過程

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

1)根據轉換算法得到轉換后的碼流S1(長度L1)，轉換后的數據按照圖中的句法存儲;

2)根據壓縮算法對S1進行壓縮，得到壓縮后的碼流S2(長度L2)，按照圖中句法存儲;

3)如果滿足L2＜L1則返回步驟1)再一次進行轉換，否則繼續;

4)按圖中的句法結構存儲壓縮完成的最終數據。

3 實驗與結果分析

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

圖6 經典灰度測試圖

設圖像尺寸為M×N，每個像素為Bp比特，壓縮后總比特數為B。壓縮比的計算公式為

對圖中的圖像經測試后得到的數據記入表1，并將結果與長度減半算法進行比較。

表1 經典灰度圖像的壓縮比

從表1中的實驗結果可以看出漸近式編碼方法能達到較好的壓縮效果，比長度減半算法要好。

4 結語

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

:

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

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

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

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

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

［6］孟凡勇.Huffman編碼在環保實時監測系統中的研究與應用［D］.青島:中國海洋大學，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，FL，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］.計算機應用，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.