劉雄恩，黃曉陽

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

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

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

1 RLE與LZMA的混合編碼

1.1 RLE編碼與解碼

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

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

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

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

1.1.1 RLE編碼算法

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

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

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

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

5）d1入隊列；

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

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

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

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

1.1.2 RLE解碼算法

1）出隊列獲取1個像素值，賦予d；令count為0，num為0；

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

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

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

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

1.2 LZMA

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

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

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

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

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

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

2 壓縮與解壓實驗

2.1 測試圖像

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

2.2 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

3 結(jié) 論

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

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

［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)彩色圖像的無損壓縮方法［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的無損編碼方法［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.