肖 健，邵翠蘭（廣東科技學(xué)院，廣東東莞523083）

基于低熵源編碼有效圖像壓縮算法

肖 健，邵翠蘭
（廣東科技學(xué)院，廣東東莞523083）

在信息論中，數(shù)據(jù)壓縮是數(shù)據(jù)處理的難題之一，尤其是圖像無損壓縮。JPEG-LS算法是公認(rèn)的灰度圖像有效的壓縮算法。然而，對于計算機(jī)繪制的灰度圖像（如CAD、SOLIDWORK等），其壓縮效率低，限制了JPEG-LS的廣泛應(yīng)用。提出一種基于兩步編碼法的圖像有效壓縮算法，即建模和編碼，算法與JPEG-LS灰度圖像壓縮標(biāo)準(zhǔn)進(jìn)行對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明該算法提高了壓縮效率。

圖像壓縮；低熵源；預(yù)測誤差；圖像編碼；冗余度

O 引言

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

（1）計算當(dāng)前點(diǎn)的上下文，引用上一強(qiáng)度值（x）；

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

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

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

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

1 預(yù)測誤差有效編碼算法

設(shè)

式（3）代入式（4）得：

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

例如，設(shè)A=｛0，1，2｝，P（0）=6 /7，P（1）=2 /21，P （2）=1 /21，預(yù)測誤差序列的編碼為000000000001000 102000。

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

因此，塊z1…zl中，在第i位置字符zi之后出現(xiàn)i-1個零表觀，由編碼器Ki用概率編碼，因?yàn)樽址鸎和為零。最后，塊中z1…zl字符位于任意字符k之后，由編碼器以初始概率和P（｜k｜）分別為0和k編碼［12］，其中P（｜k｜）由式（3）給出。概率不存儲在編碼器和解碼器之中，而是采用遞歸計算［11-12］。首先，z1分別用字符0與k以和概率編碼，當(dāng)z1=k時，則所有的字符接字符k以編碼器用初始概率P（｜k｜）和分別以k和0編碼。否則，計算字符z2用和1 -概率分別以k與0編碼［13］。因此，塊z1…zl中的字符編碼分為兩步執(zhí)行。

（2）如果zi=k，則所有的字符接zi以概率^q和P（｜k｜）編碼；否則，算法前移下一字符并返回到步驟（1）［14-16］。

與原始數(shù)據(jù)

下一塊的字符用相同方式編碼，編碼每一新塊之前用初始數(shù)據(jù)進(jìn)行更新。

使用之前步驟序列，考慮下面的編碼結(jié)構(gòu)。令：

編碼序列為：000 1001 0 21020

這個序列表示為：

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

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

因此，字符z5=0，編碼器k1以概率編碼，接著向前移至字符z6，由式（6）可得：

因此，z6=0，由編碼器k2以概率編碼，由式（6）可得：

所以，z7=1，由編碼器k3以概率編碼。第2塊z10z11z12的字符串以相同的方式編碼。因?yàn)?，z10=1也遵循編碼器k1以概率編碼，余下的字符串z11和z12由編碼器以概率P（z11）=P（0）=6 / 7和P（z12）=P（2）=1 /21編碼。編碼器與解碼器存儲大小以及所提出方法的編碼與解碼比率的特點(diǎn)在定理1中來描述［17］。

定理1 設(shè)有一低熵源貝努利Sε，用字母表Aε=｛ε｜ε［-n，n］｝生成預(yù)測誤差序列，以概率分布P（ε）由式（3）和一些r（0

其中C1、C2和C3為常數(shù)。

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

即總?cè)哂嗔坎怀^r。對該方法的平均編碼和解碼時間進(jìn)行評估，第（1）步序列字符壓縮編碼花費(fèi)時間等于

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

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

2 算法實(shí)驗(yàn)結(jié)果

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

表1 計算機(jī)繪制圖像壓縮對照表

表2 照片圖像壓縮對照表

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

3 結(jié)論

本文所提出的基于兩步編碼有效算法經(jīng)實(shí)驗(yàn)證明，計算機(jī)繪制圖像編碼的壓縮比和編碼率明顯增加，分別提高27%和37%，超過JPEG算法?？蓱?yīng)用于地圖、地球表面的衛(wèi)星圖像和網(wǎng)頁圖形等實(shí)際領(lǐng)域。對于固定位置和固定數(shù)目的像素進(jìn)行預(yù)測公式較簡單，預(yù)測的像素點(diǎn)能充分利用。

［1］TROFIMOV V K.Efficiency of outPut-uniform coding of bernou11i sources for unknown message statistics［J］.Avtometriya，2010，46（6）：32-39.

［2］TODD S，LANGDON G.G，RISSANEN J.Parameter reduction and context se1ection for comPression of the gray-sca1e images［J］.IBM J.Res.Deve1oP，2013，29（2）：188-193.

［3］HOWARD P G，VITTER JS.Fast and efficient 1oss1ess image comPression［C］.In Proc.IEEE Data ComPression Conference，Snowbird，Utah，2012：351-360.

［4］WEINBERGER M J，SEROUSSIG，SAPIRO G.The LOCO-I 1oss1ess image comPression a1gorithm：PrinciP1es and standardization into JPEG-LS［J］.IEEE Transacation on Image Process，2013，9（8）：1310-1324.

［5］NETRAVALIA，LIMB JO.Picture coding：a review［J］.Pro

ceedings of the IEEE 1980，68（3）：366-406.

［6］REININGER R C，GIBSON JD.Distributions of the two-dimentiona1DCT coefficients for images［J］.IEEE Transacations on Communicatons，2013，31（6）：835-839.

［7］MERHAV N，SEROUSSIG，WEINBERGER M J.OPtima1Prefix codes for sourceswith 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 1ow-entroPy sources［J］.Prob1.Peredachi Information，2010，35（1）：49-61.

［9］RYABKO YA B，F(xiàn)IONOV A N.HomoPhonic coding with 1ogarithmic memory size［M］.In A1gorithms and ComPutation，SPringer，Ber1in，2009：253-262.

［10］WITTEN IH，NEAL R M，CLEARY JG.Arithmetic coding for data comPression communication［J］.ACM，1987，30 （6）：520-540.

［11］Library of images for testing and demonstration of data com-Pression a1gorithms［EB/OL］.［2012-01-12］（2016-01-05）. httP：//cdb. Paradiceinsight. us/corPora/CorPus% 20Water1oo/GreySet1 /？C=N；O=A.

［12］王鳳，萬智萍.基于閾值與人眼特性的小波圖像壓縮算法［J］.圖學(xué)學(xué)報，2013，34（6）：80-86.

［13］褚靜，徐安成，張美鳳.基于DWT-LSSVM的圖像壓縮算法［J］.計算機(jī)工程與應(yīng)用，2013，40（14）：156-159.

［14］楊曉，劉俊杰，楊學(xué)友.基于ROI編碼的任意尺寸測量圖像的壓縮方法［J］.計算機(jī)工程與應(yīng)用，2013，40（4）：14-17.

［15］陽婷，官洪運(yùn)，章文康，等.基于小波變換的圖像壓縮算法的改進(jìn)［J］.計算機(jī)與現(xiàn)代化，2014，40（10）：123-126.

［16］田馳.小波Contour1et變換圖像壓縮算法［J］.長春工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2014，40（4）：89-91.

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

肖健（1970 -），通信作者，男，碩士，工程師，主要研究方向：機(jī)器視覺、過程控制。E-mai1：1018647306@qq.com。

邵翠蘭（1972 -），女，碩士，講師，主要研究方向：軟件工程。

The effective image comPression a1gorithm based on 1ow entroPy source coding

Xiao Jian，Shao Cui1an
（Guangdong University of Science and Techno1ogy of China，Dongguan 523083，China）

In information theory，the data comPression is one of the imPortant Prob1ems in data Processing，Particu1ar1y the image 1oss1ess com-Pression.The JPEG-LS comPression a1gorithm is recognized as the effective image comPression a1gorithm for the ha1ftone image Picture，but it is inefficient for artificia1gray sca1e，which 1imits its aPP1ication.The PaPer ProPoses an image comPression a1gorithm based on two-steP，which are mode1ing and coding，and the contrast exPerimentwith JPEG-LS a1gorithm ha1ftone comPression standard shows that the ProPosed method is effective.

image comPression；1ow-entroPy source；Prediction error；coding of image；redundancy

TP391

A

10.19358 /j.issn.1674-7720.2016.09.014

肖健，邵翠蘭.基于低熵源編碼有效圖像壓縮算法［J］.微型機(jī)與應(yīng)用，2016，35（9）：44-47.

2016-01-12）