一种离散色调图像无损压缩方法

刘雄恩，黄晓阳

（1.福建农林大学计算机与信息学院，福建 福州350028；2.厦门大学信息科学与技术学院，福建 厦门361005）

现有的图像压缩方法大多是针对连续色调图像而设计的，连续色调图像的相邻像素通常具有相似的亮度和颜色，在二维平面的不同方向上亮度和颜色在视觉上的变化基本是连续的.采用离散余弦变换（DCT）和小波变换等编码方法，在有损模式下通过选择性地丢掉视觉不敏感的信号分量，可以达到很好的压缩效果［1］.由于离散色调图像具有相邻像素值相同或差异很大以及亮度或颜色变化常常是不连续的特点，若仍采用基于DCT变换的JPEG［2］或基于小波变换的JPEG2000［3］对此类图像进行压缩编码，无论是无损还是有损模式，图像压缩效果都不好.此外，由于离散色调图像的任何信号分量都是敏感的，有损压缩会明显地改变此类图像的质量，因此往往采用无损压缩方式对其进行压缩.

目前流行的图像无损压缩标准包括联合图像专家组提出的JPEG－LS和JPEG2000－LS；CompuServe公司开发的GIF格式；W3C组织提出的PNG格式和联合二值图像专家组提出的JBIG和JBIG2等.针对离散色调图像的无损压缩方法的研究依然较少.采用算术编码的JBIG和JBIG2是专门用于二值图像的渐进式无损压缩方法［4－5］，它们是以相邻像素来估算当前像素的概率分布，当这个概率分布极不均匀时可以获得紧致的压缩编码，对于如传真之类的图像其压缩效果较好，而当多个位平面上存在相似结构时将导致编码冗余.基于变形的LZW算法［6］实现的GIF图像压缩格式是针对离散色调图像而设计的，但它只能处理不超过256色的图像［7］，否则颜色失真，且其一维编码仅消减了行内的数据冗余，尽管它对于尺寸较小和256色以内的离散色调图像具有较高的压缩比.基于块分解和搜索的正逆各向异性扩散模型（FABD）能消除图像的二维全局冗余而具有很高的压缩比，其表现优于JBIG［8］，但其压缩率依赖于算法中对于3种块进行搜索计算的时间，且速度较慢.近年流行于网络应用的PNG图像压缩格式［9］采用LZ77算法与哈夫曼编码相结合的DEFLATE压缩算法，能支持最高48位真彩色图像和16位灰度图像，其压缩率不低于GIF，完全适用于离散色调彩色图像的无损压缩.针对离散色调图像的冗余特点，继文献［10］之后，本文在游程编码（RLE）与字典编码的基础上，再次提出一种新的混合编码方式，RLE与 LZMA（Lempel－Ziv－Markov chainalgorithm）的混合编码，其对离散色调彩色图像的无损压缩效果明显较好.

1 RLE与LZMA的混合编码

1.1 RLE编码与解码

RLE的基本原理是用一个符号值或串长代替具有相同值的连续符号，使符号长度少于原始数据的长度.只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩.RLE是一种简单的无损压缩算法，运算简单且压缩和解压缩都较为快速，适用于图像中存在连续大量相同像素的情况.RLE编码输出流是由如下所示的二元组组成的序列.

（像素值1，重复数1），（像素值2，重复数2），（像素值3，重复数3），…

像素值的位数取决于原始图像颜色的编码位数，如24位彩色图像该值以3字节表示，而对于黑白二值图像可以直接输出黑白交替的像素点重复数序列.

离散色调图像在水平或垂直方向上具有大量相同颜色像素线段，采用逐行或逐列扫描像素的RLE编码方式，以达到消减水平或垂直方向的冗余.本文采用逐行且上下行不间断的扫描方式进行游程编码.传统RLE算法中重复数参数的取值范围是固定的，由于重复数的取值范围变化较大，采用固定范围表示时可能存在空间浪费或溢出的问题.本文在传统RLE算法中对重复数参数采用变长编码的方式，以某一字节的最高位是否为1表示该字节是否为重复数变量的最后一个字节.算法如下.

1.1.1 RLE编码算法

1）读取图像首行的第1个像素值，赋予d1；令count为0；

2）读取下1个像素值，赋予d2；count加1；

3）若d1与d2相等且未至图像末尾，重复步骤2）；否则，继续步骤4）；

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

5）d1入队列；

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

7）若count不为0，重复步骤6）；否则，继续步骤8）；

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

9）若已扫描至图像末尾，则结束；否则，转向步骤2），重复执行.

1.1.2 RLE解码算法

1）出队列获取1个像素值，赋予d；令count为0，num为0；

2）出队列1个字节，赋予val；count加上val位与007FH且左移num个7位的值；num加1；

3）若val位与80H的值不为0，重复步骤2）；否则，继续步骤4）；

4）连续输出count个像素值d；

5）若队列已空且至LZMA解码末尾，则结束；否则，转向步骤1），重复执行.

1.2 LZMA

LZMA是DEFLATE和LZ77算法改良和优化后的压缩算法，开发者是Igor Pavlov，它使用类似于LZ77的字典编码机制，在一般的情况下压缩率比bzip2为高［11］.LZMA 的编码流程和 DEFLATE 算法类似［12－13］，首先运用改进的LZ77字典编码算法生成字典索引和下一字节的二元组序列，然后对这个序列进一步采用统计编码进行二次压缩，基本流程参见图1.与采用哈夫曼编码的DEFLATE算法不同，LZMA采用算术编码并以动态马尔可夫过程来预测下一字节出现的概率，其压缩性能显著提升.LZMA中的算术编码是以二进制的方式实现的，编码过程中频繁的整数除法以移位的方式进行，由此形成快速的编码过程.

图1 LZMA压缩编码流程Fig.1 Flow chart of LZMA encoding

1.3 基于RLE与LZMA的混合编码算法

采用RLE压缩编码离散色调图像，仅能揭示像素在一维水平方向上的相关性和减小行内的冗余度，却完全没有考虑垂直方向上的相关和冗余，其压缩效果有限［10］.单独使用基于字典编码方法的LZMA，逐行扫描图像，同样对于垂直方向上像素间的相关性未予直接考虑，且因离散色调图像相同颜色的像素的连续而重复出现，字典会迅速膨胀，而当前字典中许多前缀词条后续不再利用或者很少利用，使字典索引标识过早加长，因此也难于取得好的压缩效果.典型的离散色调图像在水平和垂直2个方向上同时存在相关和冗余，或者存在多个相同或相似的二维局部区域，由上述RLE生成的像素值与重复数二元组构成的序列，不仅在一定程度上消除了原图像在水平方向上的冗余，而且很好地压缩并保留了垂直方向的相关信息，一次压缩所得到的二元组序列的冗余特性十分适宜采用基于字典编码的方法，如LZW算法或LZMA，对其进行二次压缩.LZMA的基本原理是基于字节序列的字典匹配，通过RLE编码后相同的像素值已得到高度聚合并使得二维图像压缩成一维的线性序列，这使得LZMA的匹配更加便利，从而使得二次压缩能够得到理想的效果.

本文采用RLE与LZMA相结合的混合编码压缩方法的基本流程如图2所示.压缩混合编码的步骤是：1）首先启动一个线程，逐行且上下行不间断地扫描原始图像像素，以前文所述的RLE编码并输出至一个共享队列存储；2）当队列长度达到一定阈值时启动另一并行的线程，它以队列的出队数据作为LZMA的输入流，以LZMA编码并输出最终的压缩码流.解压步骤是一个大致相反的过程，首先启动一个线程，它以LZMA解码压缩码流并输出到一个共享队列，当队列长度达到一定阈值时启动另一并行的线程，此线程以出队数据作为RLE解码过程的输入流，最终输出和恢复图像数据.

图2 RLE与LZMA混合编码的压缩与解压流程Fig.2 Flow chart of compression ＆decompression with hybrid encoding by RLE ＆LZMA

2 压缩与解压实验

2.1 测试图像

针对离散色调彩色图像无损压缩的研究较少，其标准测试图像相应缺乏.本文用于测试的图像除少数来自文献，如图3和表1所列的具代表性的9幅离散色调图像中，G.5摘自文献［1］，screendump来自文献［7］，text、editor、blueprint和 RGB等4幅取自文献［10］，webpage截自科学松鼠会页面（http：∥songshuhui.net／archives／76501），其余53幅均由本文收集和制作，尺寸详见表1.

2.2 实验结果与分析

本文选择JPEG2000－LS、GIF256 色 （GIF 的 上限）和24位色的PNG等图像压缩格式与本文提出的RLE与LZMA的混合编码压缩方法，分别对上述60幅离散色调彩色图像进行压缩与解压测试.部分测试结果如表1和图4所示，其中压缩率为压缩图像尺寸与未压缩图像尺寸的比值，压缩后图像平均每个像素所需位数用bpp表示.

图3 部分压缩测试图像Fig.3 Some images for compression test

4种压缩方法对60幅离散色调图像压缩测试的统计结果如表2所示.

4种图像压缩的ratio和bpp对比清晰地表明：对于连续色调图像具有很高的压缩率的JPEG2000－LS在对离散色调图像的无损压缩中表现不佳，其bpp值数倍至10倍于其他3种压缩格式；GIF与PNG的压缩比几乎不相上下，但GIF对于24位彩色图像的压缩存在颜色失真而非无损压缩，从这个意义上看，PNG对离散色调高分辨率彩色图像的无损压缩要优于GIF；本文提出的RLE与LZMA混合编码方法的压缩率最高，压缩后图像每像素所需位数最低.测试图像RGB中相同颜色的区域较大且集中，压缩后的bpp仅有0.090.

PNG的解码特点使得其图像显示是渐进式，因此PNG图像数据在网络传输过程中支持快速预览，图像显示由粗及细，这也是PNG图像格式在网络迅速流行的原因.由于RLE与LZMA混合编码的特点导致解码过程是逐行恢复图像的，这一点不如PNG，但其更小的图像像素深度使得存储离散色调彩色图像所需空间更小，且网络传输所需的时间更少.

表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种压缩统计结果Tab.2 Statistical results of compression rates for 60discrete－tone images in four formats

为实际检测RLE与LZMA混合编码法压缩与解压的速率，本文采用与文献［10］完全相同的运行环境进行压缩与解压缩测试，部分测试图像的混合编码压缩和解压所耗费的时间如表3所示.测试结果表明，本文所提出的方法具有较高压缩与解压速率.

表3 9幅测试图像的压缩与解压执行时间Tab.3 Time consume of compression ＆decompression for 9images s

3 结 论

针对离散色调彩色图像数据的冗余特性，本文提出一种RLE与LZMA算法相结合的混合编码方法.该算法能够有效地消除此类图像中的水平相关和垂直相关.与常见无损压缩模式的JPEG2000－LS、GIF和PNG的对比测试结果表明，该方法对于离散色调彩色图像可以取得0.1～0.6bits／pixel的压缩后像素深度，优于其他常见图像无损压缩格式，且图像中相同颜色的区域越大，其压缩性能更加显著.同时，由于LZMA具有极高的解压速率，使得RLE与LZMA混合编码的解压的整体速率表现良好.

此外，本文还对一些背景单一的图像，如常见的CT图像等医学图像进行了测试，结果表明，本文算法的压缩率优于PNG，但不如JPEG2000－LS，分析其原因在于这类医学类图像的背景虽然单一，但其主体是连续色调的.本文提出的混合编码方法仅适用于典型的离散色调图像的无损压缩，即图像背景和主体都由离散色调组成.再者，本文算法的解压过程是逐行复原的模式，在应用的视觉效果上不如PNG的渐进式模式.这些不足都在一定程度上限制了本文算法的应用范围，但鉴于典型的离散色调图像中单一颜色的区域在整幅图像中常占有相当的比重，本文算法正如测试结果所示其压缩比优于现有的无损压缩方法.当离散色调图像垂直方向上的相关性和冗余度高于水平方向时，逐行扫描方法可能不是最有效的RLE编码方式，分块的搜索与逐行扫描相结合的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］刘雄恩.离散色调彩色图像的无损压缩方法［J］.计算机应用研究，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］.上海：复旦大学，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.