劉雄恩，黃曉陽(yáng)

（1.福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院，福建 福州350028；2.廈門大學(xué)信息科學(xué)與技術(shù)學(xué)院，福建 廈門361005）

現(xiàn)有的圖像壓縮方法大多是針對(duì)連續(xù)色調(diào)圖像而設(shè)計(jì)的，連續(xù)色調(diào)圖像的相鄰像素通常具有相似的亮度和顏色，在二維平面的不同方向上亮度和顏色在視覺(jué)上的變化基本是連續(xù)的.采用離散余弦變換（DCT）和小波變換等編碼方法，在有損模式下通過(guò)選擇性地丟掉視覺(jué)不敏感的信號(hào)分量，可以達(dá)到很好的壓縮效果［1］.由于離散色調(diào)圖像具有相鄰像素值相同或差異很大以及亮度或顏色變化常常是不連續(xù)的特點(diǎn)，若仍采用基于DCT變換的JPEG［2］或基于小波變換的JPEG2000［3］對(duì)此類圖像進(jìn)行壓縮編碼，無(wú)論是無(wú)損還是有損模式，圖像壓縮效果都不好.此外，由于離散色調(diào)圖像的任何信號(hào)分量都是敏感的，有損壓縮會(huì)明顯地改變此類圖像的質(zhì)量，因此往往采用無(wú)損壓縮方式對(duì)其進(jìn)行壓縮.

目前流行的圖像無(wú)損壓縮標(biāo)準(zhǔn)包括聯(lián)合圖像專家組提出的JPEG－LS和JPEG2000－LS；CompuServe公司開(kāi)發(fā)的GIF格式；W3C組織提出的PNG格式和聯(lián)合二值圖像專家組提出的JBIG和JBIG2等.針對(duì)離散色調(diào)圖像的無(wú)損壓縮方法的研究依然較少.采用算術(shù)編碼的JBIG和JBIG2是專門用于二值圖像的漸進(jìn)式無(wú)損壓縮方法［4－5］，它們是以相鄰像素來(lái)估算當(dāng)前像素的概率分布，當(dāng)這個(gè)概率分布極不均勻時(shí)可以獲得緊致的壓縮編碼，對(duì)于如傳真之類的圖像其壓縮效果較好，而當(dāng)多個(gè)位平面上存在相似結(jié)構(gòu)時(shí)將導(dǎo)致編碼冗余.基于變形的LZW算法［6］實(shí)現(xiàn)的GIF圖像壓縮格式是針對(duì)離散色調(diào)圖像而設(shè)計(jì)的，但它只能處理不超過(guò)256色的圖像［7］，否則顏色失真，且其一維編碼僅消減了行內(nèi)的數(shù)據(jù)冗余，盡管它對(duì)于尺寸較小和256色以內(nèi)的離散色調(diào)圖像具有較高的壓縮比.基于塊分解和搜索的正逆各向異性擴(kuò)散模型（FABD）能消除圖像的二維全局冗余而具有很高的壓縮比，其表現(xiàn)優(yōu)于JBIG［8］，但其壓縮率依賴于算法中對(duì)于3種塊進(jìn)行搜索計(jì)算的時(shí)間，且速度較慢.近年流行于網(wǎng)絡(luò)應(yīng)用的PNG圖像壓縮格式［9］采用LZ77算法與哈夫曼編碼相結(jié)合的DEFLATE壓縮算法，能支持最高48位真彩色圖像和16位灰度圖像，其壓縮率不低于GIF，完全適用于離散色調(diào)彩色圖像的無(wú)損壓縮.針對(duì)離散色調(diào)圖像的冗余特點(diǎn)，繼文獻(xiàn)［10］之后，本文在游程編碼（RLE）與字典編碼的基礎(chǔ)上，再次提出一種新的混合編碼方式，RLE與 LZMA（Lempel－Ziv－Markov chainalgorithm）的混合編碼，其對(duì)離散色調(diào)彩色圖像的無(wú)損壓縮效果明顯較好.

1 RLE與LZMA的混合編碼

1.1 RLE編碼與解碼

RLE的基本原理是用一個(gè)符號(hào)值或串長(zhǎng)代替具有相同值的連續(xù)符號(hào)，使符號(hào)長(zhǎng)度少于原始數(shù)據(jù)的長(zhǎng)度.只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時(shí)，一次記錄該代碼及相同代碼重復(fù)的個(gè)數(shù)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮.RLE是一種簡(jiǎn)單的無(wú)損壓縮算法，運(yùn)算簡(jiǎn)單且壓縮和解壓縮都較為快速，適用于圖像中存在連續(xù)大量相同像素的情況.RLE編碼輸出流是由如下所示的二元組組成的序列.

（像素值1，重復(fù)數(shù)1），（像素值2，重復(fù)數(shù)2），（像素值3，重復(fù)數(shù)3），…

像素值的位數(shù)取決于原始圖像顏色的編碼位數(shù)，如24位彩色圖像該值以3字節(jié)表示，而對(duì)于黑白二值圖像可以直接輸出黑白交替的像素點(diǎn)重復(fù)數(shù)序列.

離散色調(diào)圖像在水平或垂直方向上具有大量相同顏色像素線段，采用逐行或逐列掃描像素的RLE編碼方式，以達(dá)到消減水平或垂直方向的冗余.本文采用逐行且上下行不間斷的掃描方式進(jìn)行游程編碼.傳統(tǒng)RLE算法中重復(fù)數(shù)參數(shù)的取值范圍是固定的，由于重復(fù)數(shù)的取值范圍變化較大，采用固定范圍表示時(shí)可能存在空間浪費(fèi)或溢出的問(wèn)題.本文在傳統(tǒng)RLE算法中對(duì)重復(fù)數(shù)參數(shù)采用變長(zhǎng)編碼的方式，以某一字節(jié)的最高位是否為1表示該字節(jié)是否為重復(fù)數(shù)變量的最后一個(gè)字節(jié).算法如下.

1.1.1 RLE編碼算法

1）讀取圖像首行的第1個(gè)像素值，賦予d1；令count為0；

2）讀取下1個(gè)像素值，賦予d2；count加1；

3）若d1與d2相等且未至圖像末尾，重復(fù)步驟2）；否則，繼續(xù)步驟4）；

4）若d1與d2相等，count加1；

5）d1入隊(duì)列；

6）令val為count的低8位與7FH的值，count右移7位；若count不為0，再令val為val位或80H的值；val入隊(duì)列；

7）若count不為0，重復(fù)步驟6）；否則，繼續(xù)步驟8）；

8）令d1為d2，令count為0；

9）若已掃描至圖像末尾，則結(jié)束；否則，轉(zhuǎn)向步驟2），重復(fù)執(zhí)行.

1.1.2 RLE解碼算法

1）出隊(duì)列獲取1個(gè)像素值，賦予d；令count為0，num為0；

2）出隊(duì)列1個(gè)字節(jié)，賦予val；count加上val位與007FH且左移num個(gè)7位的值；num加1；

3）若val位與80H的值不為0，重復(fù)步驟2）；否則，繼續(xù)步驟4）；

4）連續(xù)輸出count個(gè)像素值d；

5）若隊(duì)列已空且至LZMA解碼末尾，則結(jié)束；否則，轉(zhuǎn)向步驟1），重復(fù)執(zhí)行.

1.2 LZMA

LZMA是DEFLATE和LZ77算法改良和優(yōu)化后的壓縮算法，開(kāi)發(fā)者是Igor Pavlov，它使用類似于LZ77的字典編碼機(jī)制，在一般的情況下壓縮率比bzip2為高［11］.LZMA 的編碼流程和 DEFLATE 算法類似［12－13］，首先運(yùn)用改進(jìn)的LZ77字典編碼算法生成字典索引和下一字節(jié)的二元組序列，然后對(duì)這個(gè)序列進(jìn)一步采用統(tǒng)計(jì)編碼進(jìn)行二次壓縮，基本流程參見(jiàn)圖1.與采用哈夫曼編碼的DEFLATE算法不同，LZMA采用算術(shù)編碼并以動(dòng)態(tài)馬爾可夫過(guò)程來(lái)預(yù)測(cè)下一字節(jié)出現(xiàn)的概率，其壓縮性能顯著提升.LZMA中的算術(shù)編碼是以二進(jìn)制的方式實(shí)現(xiàn)的，編碼過(guò)程中頻繁的整數(shù)除法以移位的方式進(jìn)行，由此形成快速的編碼過(guò)程.

圖1 LZMA壓縮編碼流程Fig.1 Flow chart of LZMA encoding

1.3 基于RLE與LZMA的混合編碼算法

采用RLE壓縮編碼離散色調(diào)圖像，僅能揭示像素在一維水平方向上的相關(guān)性和減小行內(nèi)的冗余度，卻完全沒(méi)有考慮垂直方向上的相關(guān)和冗余，其壓縮效果有限［10］.單獨(dú)使用基于字典編碼方法的LZMA，逐行掃描圖像，同樣對(duì)于垂直方向上像素間的相關(guān)性未予直接考慮，且因離散色調(diào)圖像相同顏色的像素的連續(xù)而重復(fù)出現(xiàn)，字典會(huì)迅速膨脹，而當(dāng)前字典中許多前綴詞條后續(xù)不再利用或者很少利用，使字典索引標(biāo)識(shí)過(guò)早加長(zhǎng)，因此也難于取得好的壓縮效果.典型的離散色調(diào)圖像在水平和垂直2個(gè)方向上同時(shí)存在相關(guān)和冗余，或者存在多個(gè)相同或相似的二維局部區(qū)域，由上述RLE生成的像素值與重復(fù)數(shù)二元組構(gòu)成的序列，不僅在一定程度上消除了原圖像在水平方向上的冗余，而且很好地壓縮并保留了垂直方向的相關(guān)信息，一次壓縮所得到的二元組序列的冗余特性十分適宜采用基于字典編碼的方法，如LZW算法或LZMA，對(duì)其進(jìn)行二次壓縮.LZMA的基本原理是基于字節(jié)序列的字典匹配，通過(guò)RLE編碼后相同的像素值已得到高度聚合并使得二維圖像壓縮成一維的線性序列，這使得LZMA的匹配更加便利，從而使得二次壓縮能夠得到理想的效果.

本文采用RLE與LZMA相結(jié)合的混合編碼壓縮方法的基本流程如圖2所示.壓縮混合編碼的步驟是：1）首先啟動(dòng)一個(gè)線程，逐行且上下行不間斷地掃描原始圖像像素，以前文所述的RLE編碼并輸出至一個(gè)共享隊(duì)列存儲(chǔ)；2）當(dāng)隊(duì)列長(zhǎng)度達(dá)到一定閾值時(shí)啟動(dòng)另一并行的線程，它以隊(duì)列的出隊(duì)數(shù)據(jù)作為L(zhǎng)ZMA的輸入流，以LZMA編碼并輸出最終的壓縮碼流.解壓步驟是一個(gè)大致相反的過(guò)程，首先啟動(dòng)一個(gè)線程，它以LZMA解碼壓縮碼流并輸出到一個(gè)共享隊(duì)列，當(dāng)隊(duì)列長(zhǎng)度達(dá)到一定閾值時(shí)啟動(dòng)另一并行的線程，此線程以出隊(duì)數(shù)據(jù)作為RLE解碼過(guò)程的輸入流，最終輸出和恢復(fù)圖像數(shù)據(jù).

圖2 RLE與LZMA混合編碼的壓縮與解壓流程Fig.2 Flow chart of compression ＆decompression with hybrid encoding by RLE ＆LZMA

2 壓縮與解壓實(shí)驗(yàn)

2.1 測(cè)試圖像

針對(duì)離散色調(diào)彩色圖像無(wú)損壓縮的研究較少，其標(biāo)準(zhǔn)測(cè)試圖像相應(yīng)缺乏.本文用于測(cè)試的圖像除少數(shù)來(lái)自文獻(xiàn)，如圖3和表1所列的具代表性的9幅離散色調(diào)圖像中，G.5摘自文獻(xiàn)［1］，screendump來(lái)自文獻(xiàn)［7］，text、editor、blueprint和 RGB等4幅取自文獻(xiàn)［10］，webpage截自科學(xué)松鼠會(huì)頁(yè)面（http：∥songshuhui.net／archives／76501），其余53幅均由本文收集和制作，尺寸詳見(jiàn)表1.

2.2 實(shí)驗(yàn)結(jié)果與分析

本文選擇JPEG2000－LS、GIF256 色 （GIF 的 上限）和24位色的PNG等圖像壓縮格式與本文提出的RLE與LZMA的混合編碼壓縮方法，分別對(duì)上述60幅離散色調(diào)彩色圖像進(jìn)行壓縮與解壓測(cè)試.部分測(cè)試結(jié)果如表1和圖4所示，其中壓縮率為壓縮圖像尺寸與未壓縮圖像尺寸的比值，壓縮后圖像平均每個(gè)像素所需位數(shù)用bpp表示.

圖3 部分壓縮測(cè)試圖像Fig.3 Some images for compression test

4種壓縮方法對(duì)60幅離散色調(diào)圖像壓縮測(cè)試的統(tǒng)計(jì)結(jié)果如表2所示.

4種圖像壓縮的ratio和bpp對(duì)比清晰地表明：對(duì)于連續(xù)色調(diào)圖像具有很高的壓縮率的JPEG2000－LS在對(duì)離散色調(diào)圖像的無(wú)損壓縮中表現(xiàn)不佳，其bpp值數(shù)倍至10倍于其他3種壓縮格式；GIF與PNG的壓縮比幾乎不相上下，但GIF對(duì)于24位彩色圖像的壓縮存在顏色失真而非無(wú)損壓縮，從這個(gè)意義上看，PNG對(duì)離散色調(diào)高分辨率彩色圖像的無(wú)損壓縮要優(yōu)于GIF；本文提出的RLE與LZMA混合編碼方法的壓縮率最高，壓縮后圖像每像素所需位數(shù)最低.測(cè)試圖像RGB中相同顏色的區(qū)域較大且集中，壓縮后的bpp僅有0.090.

PNG的解碼特點(diǎn)使得其圖像顯示是漸進(jìn)式，因此PNG圖像數(shù)據(jù)在網(wǎng)絡(luò)傳輸過(guò)程中支持快速預(yù)覽，圖像顯示由粗及細(xì)，這也是PNG圖像格式在網(wǎng)絡(luò)迅速流行的原因.由于RLE與LZMA混合編碼的特點(diǎn)導(dǎo)致解碼過(guò)程是逐行恢復(fù)圖像的，這一點(diǎn)不如PNG，但其更小的圖像像素深度使得存儲(chǔ)離散色調(diào)彩色圖像所需空間更小，且網(wǎng)絡(luò)傳輸所需的時(shí)間更少.

表1 9幅測(cè)試圖像的壓縮率對(duì)比Tab.1 Comparisons of compression ratio and bpp for 9images

圖4 9幅測(cè)試圖像4種壓縮格式的bpp值對(duì)比圖Fig.4 Chart of bpp values of 9images in four formats

表2 60幅測(cè)試圖像的4種壓縮統(tǒng)計(jì)結(jié)果Tab.2 Statistical results of compression rates for 60discrete－tone images in four formats

為實(shí)際檢測(cè)RLE與LZMA混合編碼法壓縮與解壓的速率，本文采用與文獻(xiàn)［10］完全相同的運(yùn)行環(huán)境進(jìn)行壓縮與解壓縮測(cè)試，部分測(cè)試圖像的混合編碼壓縮和解壓所耗費(fèi)的時(shí)間如表3所示.測(cè)試結(jié)果表明，本文所提出的方法具有較高壓縮與解壓速率.

表3 9幅測(cè)試圖像的壓縮與解壓執(zhí)行時(shí)間Tab.3 Time consume of compression ＆decompression for 9images s

3 結(jié) 論

針對(duì)離散色調(diào)彩色圖像數(shù)據(jù)的冗余特性，本文提出一種RLE與LZMA算法相結(jié)合的混合編碼方法.該算法能夠有效地消除此類圖像中的水平相關(guān)和垂直相關(guān).與常見(jiàn)無(wú)損壓縮模式的JPEG2000－LS、GIF和PNG的對(duì)比測(cè)試結(jié)果表明，該方法對(duì)于離散色調(diào)彩色圖像可以取得0.1～0.6bits／pixel的壓縮后像素深度，優(yōu)于其他常見(jiàn)圖像無(wú)損壓縮格式，且圖像中相同顏色的區(qū)域越大，其壓縮性能更加顯著.同時(shí)，由于LZMA具有極高的解壓速率，使得RLE與LZMA混合編碼的解壓的整體速率表現(xiàn)良好.

此外，本文還對(duì)一些背景單一的圖像，如常見(jiàn)的CT圖像等醫(yī)學(xué)圖像進(jìn)行了測(cè)試，結(jié)果表明，本文算法的壓縮率優(yōu)于PNG，但不如JPEG2000－LS，分析其原因在于這類醫(yī)學(xué)類圖像的背景雖然單一，但其主體是連續(xù)色調(diào)的.本文提出的混合編碼方法僅適用于典型的離散色調(diào)圖像的無(wú)損壓縮，即圖像背景和主體都由離散色調(diào)組成.再者，本文算法的解壓過(guò)程是逐行復(fù)原的模式，在應(yīng)用的視覺(jué)效果上不如PNG的漸進(jìn)式模式.這些不足都在一定程度上限制了本文算法的應(yīng)用范圍，但鑒于典型的離散色調(diào)圖像中單一顏色的區(qū)域在整幅圖像中常占有相當(dāng)?shù)谋戎?，本文算法正如測(cè)試結(jié)果所示其壓縮比優(yōu)于現(xiàn)有的無(wú)損壓縮方法.當(dāng)離散色調(diào)圖像垂直方向上的相關(guān)性和冗余度高于水平方向時(shí)，逐行掃描方法可能不是最有效的RLE編碼方式，分塊的搜索與逐行掃描相結(jié)合的RLE方法值得進(jìn)一步的探索.

［1］Salomon D.Data compression：the complete reference［M］.London：Springer，2007.

［2］Pennebaker W B，Mitchell J L.JPEG：still image data compression standard［M］.Amsterdam：Kluwer Academic Publishers，1993.

［3］ISO／IEC.Internationalstandard IS 15444－1，information technology－JPEG2000image coding system［S］.Geneva：ISO，2000.

［4］Arps R B，Truong T K.Comparison of international standards for lossless still image compression ［J］.Proceeding of the IEEE，1994，82（6）：889－899.

［5］Pennebaker W B，Mitchell J L，Langdon G G，et al.An overview of the basic principles of the Q－coder adaptive binary arithmetic coder［J］.IBM Journal of Research and Development，1988，32（6）：737－752.

［6］Philips D.LZW data compression［J］.The Computer Application Journal，1992，27：36－48.

［7］Murray J D，William V R.Encyclopedia of graphics file format［M］.Sebastopol：O′Reilly Association，1994.

［8］Gilbert J M，Broderson R W.A lossless 2－D image compression technique for synthetic discrete－tone images［EB／OL］.［1998－05－17］.http：∥infopad.eecs.berkeley.edu／gilbert.

［9］W3C（MIT，ERCIM，Keio）.Portable network graphics（PNG）specification（second edition）［EB／OL］.［2003－11－10］.http：∥www.w3.org／TR／2003／REC－PNG－20031110／.

［10］劉雄恩.離散色調(diào)彩色圖像的無(wú)損壓縮方法［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（增刊）：920－921.

［11］Igor P.LZMA SDK ver 9.22beta （software development kit） ［EB／OL］.［2011－01－19］.http：∥www.7－zip.org／sdk.html.

［12］涂宗劼.一種基于JPEG2000和LZMA的無(wú)損編碼方法［D］.上海：復(fù)旦大學(xué)，2008.

［13］Deutsch P.DEFLATE compressed data format specification version 1.3［EB／OL］.［1996－05－13］.http：∥tools.ietf.org／html／rfc1951＃section－7.