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

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

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

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

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

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

O 引言

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

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

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

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

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

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

1 預測誤差有效編碼算法

設

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

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

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

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

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

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

與原始數據

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

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

編碼序列為：000 1001 0 21020

這個序列表示為：

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

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

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

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

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

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

其中C1、C2和C3為常數。

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

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

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

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

2 算法實驗結果

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

表1 計算機繪制圖像壓縮對照表

表2 照片圖像壓縮對照表

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

3 結論

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

［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，FIONOV 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］.圖學學報，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］田馳.小波Contour1et變換圖像壓縮算法［J］.長春工業大學學報（自然科學版），2014，40（4）：89-91.

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

肖健（1970 -），通信作者，男，碩士，工程師，主要研究方向：機器視覺、過程控制。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］.微型機與應用，2016，35（9）：44-47.

2016-01-12）