肖健，邵翠蘭

　　（廣東科技學院，廣東 東莞 523083）

　　摘要： 在信息論中，數據壓縮是數據處理的難題之一，尤其是圖像無損壓縮。JPEG－LS算法是公認的灰度圖像有效的壓縮算法。然而，對于計算機繪制的灰度圖像（如CAD、SOLIDWORK等），其壓縮效率低，限制了JPEG－LS的廣泛應用。提出一種基于兩步編碼法的圖像有效壓縮算法，即建模和編碼,算法與JPEG-LS灰度圖像壓縮標準進行對比實驗，實驗結果證明該算法提高了壓縮效率。

　　關鍵詞： 圖像壓縮；低熵源；預測誤差；圖像編碼；冗余度

0引言

　　數據壓縮是信息論的難題之一，解決方案有若干種［1］，預測誤差編碼是圖像無損壓縮最常見的算法之一，基于這種思想算法總體方案可分為兩步：建模和編碼。使用類圖像的模型，從上一數據預測該點的強度來計算有效圖像數據估計值。編碼步驟包括計算預測誤差，即實現與預測的強度差，壓縮采用二進制表示。圖像壓縮方案首先使用日落算法實現［2］，算法有多種變形，如單通道，其預測誤差和編碼一次完成；雙通道變型，先計算所有誤差，再進行編碼［3］。對于灰度圖像，在算法復雜性和壓縮效率比率最佳方案公認為是JPEGLS無損壓縮標準［4］。基于JPEGS標準算法進行預測當前點的強度，當前點k是連續鄰接點，用k比特數表示（稱為上下文），當前點的強度、編碼的預測和編碼的整個過程可以分為三步［56］：

　　（1）計算當前點的上下文，引用上一強度值（x）；

　　（2）當前點強度值（）的預測源于上的值；

　　（3）ε=－x為計算預測誤差的概率模型參數，使用步驟（1）和（2）及誤差編碼得到的數據。設誤差ε是兩邊幾何分布［56］，關于某個對稱值呈現指數衰減分布，概率模型分別用上下文表示，分布對稱中心可以移動使它接近于0［7］。

　　p(ε)=C(θ,d)θ|ε+d|（1）

　　當ε＝0，±1，±2…是預測誤差時，參數取值范圍0<θ<1，0≤d≤1/2，其特征分布對稱中心C（θ，d）歸一化因子由式（2）給出：

　　灰度圖像JPEG－LS壓縮算法優于其他算法，然而對于計算繪制的灰度圖像，JPEG－LS算法效率低，限制了JPEG－LS的廣泛應用。對于計算繪制的圖像，值為0時預測誤差ε的概率顯著高于照片圖像。ε使用RiceGolomb編碼對字符編碼［8］。在計算繪制圖像的情況下，其中一串零的概率足夠大，低熵源編碼算法是有效解決此類型圖像的方案。

　　編碼低熵源算法已得到證明［8］，它提供任意預定的冗余，同時保留編碼器和解碼器中一般方法相同的存儲器，算法的編碼和解碼率顯著提高［910］。

1預測誤差有效編碼算法

　　預測誤差構造一個高效編碼算法，由一個低熵源貝努利源Sε與預測誤差值的字母表生成字符序列Aε={ε|ε∈［－n,n］}，概率分布P(ε)由式（3）給出：

　　P(ε)=(1－θ)θε2θ,ε≠0;P(0)=1－θ（3）

　　式（3）是由式（1）和式（2）概率分布產生，令d=12（當d=0和d=12時，式（1）概率分布中心點為0［7］）。考慮以上情況，實際上ε+dd，即令|ε+d|≈|ε|。

　　設

　　預測誤差ε序列編碼分為兩步驟：第1步，一個簡單的代碼壓縮源生成消息，且作為結果輸出序列編碼在第2步中使用一個更復雜的代碼編碼。源是一個低熵源，在第1步之后，輸入序列長度明顯減少，提供原始消息字符編碼的總時間減小。第2步，使用目前已知算法中最有效的算術編碼。考慮編碼的第1步，字符輸入序列劃分成長度l=1/塊（子字符串），其中由式（4）給出。如果一個塊的誤差值僅有零值，則這個塊的編碼為0，如果一個塊包含誤差值至少有一個非零值（用k表示，－1≤|k|≤n），則該碼字長度等于l+1：這個塊的開頭碼字為某個特殊字符k，后跟相同塊長度l。在這種情況下，第l+1在開頭的碼字加字符k是有必要的，這表明在位于k后面長度l塊中不可能是字符表觀。

　　例如，設A={0，1，2}，P（0）=6/7，P（1）=2/21，P（2）=1/21，預測誤差序列的編碼為000000000001000 102000。

　　由式（4）得出=1/7,l=3的結果，編碼序列形式 000 1001 0 21020第1步編碼后得到序列，在編碼第1步之后，令z1z2…zs。(zi∈A,A={k|－n≤k≤n})。

　　第2步編碼是編碼算法，在序列z1z2…zs選擇長度為l的塊后跟隨任意特殊字符k，特殊字符0和k不包含在塊中，序列z1z2…zs表示成：

　　0…0kz1…zll0…0kz′1…z′ll編碼方案描述如下：

　　特殊字符0和k（－n≤k≤n）由編碼器k0分別用l和1－l概率編碼，在式（4）中定義。

　　考慮長度為l的塊z1z2…zs內字符編碼，令z1…zi－1=0…0i－1(i=1,2,…,l),判斷字符zi的概率，位于第i個位置后i-1字符0的表觀，則有:

　　因此，塊z1…zl中，在第i位置字符zi之后出現i-1個零表觀，由編碼器Ki用概率Γki編碼，因為字符K和1－2∑nk=1Γki為零。最后，塊中z1…zl字符位于任意字符k之后，由編碼器k^以初始概率和p(|k|)分別為0和k編碼［12］，其中p(|k|)由式（3）給出。概率Γki不存儲在編碼器和解碼器之中，而是采用遞歸計算［1112］。首先，z1分別用字符0與k以Γk1和1－2∑nk=1τk1概率編碼，當z1=k時,則所有的字符接字符k以編碼器k^用初始概率p(|k|)和分別以k和0編碼。否則，計算Γk2，字符z2用Γk2和1－2∑nk=1τk2概率分別以k與0編碼［13］。因此，塊z1…zl中的字符編碼分為兩步執行。

　　(1)計算Γki，字符zi用Γki和1－2∑nk=1τki概率編碼。

　　(2)如果zi=k，則所有的字符接zi以概率和p(|k|)編碼;否則，算法前移下一字符并返回到步驟（1）［1416］。

　　用遞推公式Γki計算：

　　下一塊的字符用相同方式編碼，編碼每一新塊之前用初始數據進行更新。

　　使用之前步驟序列，考慮下面的編碼結構。令：

　　p(0)==6/7

　　p(1)=2/21,p(2)=1/21,=1/7,l=3

　　編碼序列為：

　　這個序列表示為：

　　特殊字符使用編碼器k0用以下概率編碼

　　p(z1)=p(z2)=p(z3)=p(z8)=p(z13)=(6/7)3=216/343

　　p(z4)=p(z9)=1－(6/7)3=127/343

　　第1塊z5z6z7的字符串編碼如下。由式（6）可得：

　　所以，z7=1，由編碼器k3以τ13=2/3概率編碼。第2塊z10z11z12的字符串以相同的方式編碼。因為(τ11)－1=38198，z10=1也遵循編碼器k1以τ11=98/381概率編碼，余下的字符串z11和z12由編碼器k^以概率p(z11)=p(0)=6/7和p(z12)=p(2)=1/21編碼。編碼器與解碼器存儲大小以及所提出方法的編碼與解碼比率的特點在定理1中來描述［17］。

　　定理1設有一低熵源貝努利Sε，用字母表Aε={ε|ε［－n,n］}生成預測誤差序列，以概率分布p(ε)由式（3）和一些r(0<r<1)給出。第(1)步，令這個源用上述l=1/(<1/2)進行編碼，其由式（4）給出。第(2)步，冗余r=r/2，總的冗余不超過r,并且編碼器與解碼器V(Sε)總的存儲器大小和一個符號T(Sε)編碼與解碼平均時間滿足不等式:

　　V<C1log1,T<C2·log(1r）·loglog(1r）·logloglog(1r）+C3

　　其中C1、C2和C3為常數。

　　證明：總編碼冗余量R=l′T。

　　l′=l1/l編碼是第1步之后獲得的代碼平均長度（每個字符），當僅有字符0組成的塊出現，概率可表示為l=(1－）l，因此有:

　　即總冗余量不超過r。對該方法的平均編碼和解碼時間進行評估，第（1）步序列字符壓縮編碼花費時間等于

　　因此，計算量的時間Γki用在第（2）步不超過

　　乘以平均代碼長度l′得第（2）步編碼的總時間，考慮第（1）步的時間等于0(1)，發現對于所提出的方法，一個字符編碼和解碼平均時間滿足下式：

2算法實驗結果

　　定理1給出了該方法有效性總體思想，然而更加實際意義是如何使所提出的方法對真實數據影響的問題。用Waterloo Repertoire GreySet1標準圖像集對算法的性能進行測試實驗,所有圖像尺寸為256×256像素，測試使用聯想PC的配置如下：CPU為IntelPentium(R) Dual-core,主頻為2 GHz，內存2 GB，操作系統Windows 7。用JPEGLS標準對兩種算法進行比較。表1和表2是兩種算法比較結果，圖像壓縮k（bit）和時間t（s）的程度要求編碼器來壓縮圖像，在這種情況下壓縮程度是指對應于原圖像（未壓縮）中的一個字節（8 bit）的壓縮文件中的比特數。換言之，如果L是原始文件的大小，L1是壓縮文件的大小，那么壓縮程度為8（L1/L）。一組計算機繪制圖像壓縮結果在表1中列出，另一組照片圖像壓縮數據在表2中列出。

　　表1表明，計算機繪制圖像壓縮程度平均大于JPEGLS算法27%，編碼率提高約37%。對于照片圖像（如表2所示），新算法平均提高約2%，與JPEGLS算法相比，編碼率仍然較高，提高約21%。實驗結果表明，算法提供了良好的壓縮比，證明所提出的算法是高效的。

3結論

　　本文所提出的基于兩步編碼有效算法經實驗證明，計算機繪制圖像編碼的壓縮比和編碼率明顯增加，分別提高27%和37%，超過JPEG算法。可應用于地圖、地球表面的衛星圖像和網頁圖形等實際領域。對于固定位置和固定數目的像素進行預測公式較簡單，預測的像素點能充分利用。

參考文獻

　　［1］ TROFIMOV V K. Efficiency of outputuniform coding of bernoulli sources for unknown message statistics［J］. Avtometriya， 2010,46(6)：3239.

　　［2］ TODD S, LANGDON G. G, RISSANEN J. Parameter reduction and context selection for compression of the grayscale images［J］. IBM J. Res. Develop， 2013,29(2):188193.

　　［3］ HOWARD P G, VITTER J S. Fast and efficient lossless image compression［C］. In Proc. IEEE Data Compression Conference, Snowbird, Utah, 2012: 351360.

　　［4］ WEINBERGER M J, SEROUSSI G, SAPIRO G. The LOCOI lossless image compression algorithm: principles and standardization into JPEGLS［J］. IEEE Transacation on Image Process, 2013,9(8):13101324.

　　［5］ NETRAVALI A, LIMB J O. Picture coding: a review［J］. Proceedings of the IEEE 1980,68(3): 366406.

　　［6］ REININGER R C, GIBSON J D. Distributions of the twodimentional DCT coefficients for images［J］. IEEE Transacations on Communicatons, 2013,31(6):835839.

　　［7］ MERHAV N, SEROUSSI G, WEINBERGER M J. Optimal prefix codes for sources with twosided geometric distributions［J］. IEEE Transacations on Information Theory, 2013,46(1):121135.

　　［8］ RYABKO B J, SHAROVA M P. Fast coding of lowentropy sources［J］. Probl. Peredachi Information, 2010,35(1): 4961.

　　［9］ RYABKO YA B, FIONOV A N. Homophonic coding with logarithmic memory size［M］. In Algorithms and Computation, Springer, Berlin, 2009:253262.

　　［10］ WITTEN I H, NEAL R M, CLEARY J G. Arithmetic coding for data compression communication［J］. ACM, 1987,30(6):520540.

　　［11］Library of images for testing and demonstration of data compression algorithms［EB/OL］.［20120112］（20160105）. http://cdb.paradiceinsight.us/corpora/Corpus% 20Waterloo/GreySet1/?C= N;O=A.

　　［12］ 王鳳, 萬智萍. 基于閾值與人眼特性的小波圖像壓縮算法［J］. 圖學學報, 2013,34(6): 8086.

　　［13］ 褚靜, 徐安成, 張美鳳. 基于DWTLSSVM的圖像壓縮算法［J］. 計算機工程與應用, 2013,40(14):156159.

　　［14］ 楊曉,劉俊杰, 楊學友.基于ROI編碼的任意尺寸測量圖像的壓縮方法［J］. 計算機工程與應用,2013,40(4): 1417.

　　［15］ 陽婷,官洪運,章文康,等. 基于小波變換的圖像壓縮算法的改進［J］. 計算機與現代化, 2014,40(10):123126.

　　［16］ 田馳.小波Contourlet變換圖像壓縮算法［J］. 長春工業大學學報(自然科學版) , 2014,40(4):8991.

　　［17］ 陳鴻,柏森,劉博文.混沌和小波變換的圖像加密壓縮算法［J］. 重慶大學學報, 2014,40(6):6570.