《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 顯示光電 > 設(shè)計應(yīng)用 > 基于低熵源編碼有效圖像壓縮算法
基于低熵源編碼有效圖像壓縮算法
2016年微型機(jī)與應(yīng)用第09期
肖健,邵翠蘭
(廣東科技學(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)行對比實驗,實驗結(jié)果證明該算法提高了壓縮效率。
Abstract:
Key words :

  肖健,邵翠蘭

  (廣東科技學(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)行對比實驗,實驗結(jié)果證明該算法提高了壓縮效率。

  關(guān)鍵詞: 圖像壓縮;低熵源;預(yù)測誤差;圖像編碼;冗余度

0引言

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

 ?。?)計算當(dāng)前點的上下文,引用上一強度值(x);

 ?。?)當(dāng)前點強度值()的預(yù)測源于上的值;

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

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

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

  2.png

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

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

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

  預(yù)測誤差構(gòu)造一個高效編碼算法,由一個低熵源貝努利源Sε與預(yù)測誤差值的字母表生成字符序列Aε={ε|ε∈[-n,n]},概率分布P(ε)由式(3)給出:

  P(ε)=(1-θ)θε2θ,ε≠0;P(0)=1-θ(3)

  式(3)是由式(1)和式(2)概率分布產(chǎn)生,令d=12(當(dāng)d=0和d=12時,式(1)概率分布中心點為0[7])。考慮以上情況,實際上ε+dd,即令|ε+d|≈|ε|。

  設(shè)

  45.png

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

  由式(4)得出=1/7,l=3的結(jié)果,編碼序列形式 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內(nèi)字符編碼,令z1…zi-1=0…0i-1(i=1,2,…,l),判斷字符zi的概率,位于第i個位置后i-1字符0的表觀,則有:

  1111.png

  因此,塊z1…zl中,在第i位置字符zi之后出現(xiàn)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概率編碼,當(dāng)z1=k時,則所有的字符接字符k以編碼器k^用初始概率p(|k|)和分別以k和0編碼。否則,計算Γk2,字符z2用Γk2和1-2∑nk=1τk2概率分別以k與0編碼[13]。因此,塊z1…zl中的字符編碼分為兩步執(zhí)行。

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

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

  用遞推公式Γki計算:

  6.jpg

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

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

  p(0)==6/7

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

  編碼序列為:

  $7C)D}L@UT5AVXBGR`(2O{O.png

  這個序列表示為:

  特殊字符使用編碼器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)可得:

  UO9(Z`BN%0IPZJ]E24JH8CC.jpg

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

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

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

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

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

  l.png

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

 o.png

  因此,計算量的時間Γki用在第(2)步不超過

 c.png

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

  t.png

2算法實驗結(jié)果

  定理1給出了該方法有效性總體思想,然而更加實際意義是如何使所提出的方法對真實數(shù)據(jù)影響的問題。用Waterloo Repertoire GreySet1標(biāo)準(zhǔn)圖像集對算法的性能進(jìn)行測試實驗,所有圖像尺寸為256×256像素,測試使用聯(lián)想PC的配置如下:CPU為IntelPentium(R) Dual-core,主頻為2 GHz,內(nèi)存2 GB,操作系統(tǒng)Windows 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中列出。

001.jpg

002.jpg

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

3結(jié)論

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

參考文獻(xiàn)

 ?。?] TROFIMOV V K. Efficiency of outputuniform coding of bernoulli sources for unknown message statistics[J]. Avtometriya, 2010,46(6):3239.

 ?。?] 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.

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

 ?。?] 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.

 ?。?] NETRAVALI A, LIMB J O. Picture coding: a review[J]. Proceedings of the IEEE 1980,68(3): 366406.

 ?。?] 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.

 ?。?] RYABKO B J, SHAROVA M P. Fast coding of lowentropy sources[J]. Probl. Peredachi Information, 2010,35(1): 4961.

 ?。?] 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.

 ?。?1]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]. 圖學(xué)學(xué)報, 2013,34(6): 8086.

 ?。?3] 褚靜, 徐安成, 張美鳳. 基于DWTLSSVM的圖像壓縮算法[J]. 計算機(jī)工程與應(yīng)用, 2013,40(14):156159.

 ?。?4] 楊曉,劉俊杰, 楊學(xué)友.基于ROI編碼的任意尺寸測量圖像的壓縮方法[J]. 計算機(jī)工程與應(yīng)用,2013,40(4): 1417.

 ?。?5] 陽婷,官洪運,章文康,等. 基于小波變換的圖像壓縮算法的改進(jìn)[J]. 計算機(jī)與現(xiàn)代化, 2014,40(10):123126.

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

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


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。