渐近式图像无损压缩算法

武海艳，唐海玲

(黄河科技学院a.郑州市智能图像处理与识别重点实验室;b.郑州市物联网传感技术及其应用重点实验室;c.信息工程学院，河南郑州450063)

图像数据压缩作为实现图像数据的存储和传输的核心内容受到广泛的关注［1］。数据压缩是指利用压缩算法减少数据冗余并保持高保真度，有效地节约存储空间、提高数据传输效率。数据压缩技术包括有损压缩和无损压缩。其中无损压缩相比有损压缩具有能100%保留原始信息、无信号丢失且不受信号源等优点，在诸多领域中得到广泛应用［2-6］。

游程编码(RLC)是最重要的图像无损压缩方法之一，是图像的编码标准JPEG和传真通信国际电信联盟ITU-T标准的组成部分［7-9］。其思想为数据项a在数据流中连续出现n次，则以单个字符nd来替换连续出现n次的数据项d，n称为游程，从而节省存储空间。可是当每两个相邻点的颜色都不同时，RLC压缩数据量反而会增加［10］。为此，文献［10-12］提出相同数据项3个或3个以上才使用RLC编码，但需设立标志位;文献［13］提出的基于长度减半的二进制码流的压缩算法，按照码流中的连续“1”的个数(黑长)、连续“0”的个数(白长)的分布特点选取相应初始长度进行减半压缩处理，但是仍存在数据冗余。鉴于上述原因，本文提出一种渐近式压缩编码技术，按图像无损压缩的基本步骤［14］，在长度减半压缩算法基础上改进编码思想减少编码的数据冗余，并对编码后的码流进行自适应转换以提高码流的相关性，从而提高压缩效率。

1 图像压缩预处理

1.1 图像扫描

图像扫描简单来说就是读取图像的数据以更进一步的处理，由于图像的信源数据不是互相独立的，是一组有记忆的数据，相邻像素之间具有一定的相关性。为最大限度地去除像素间的冗余度，提高压缩效率，对图像数据进行扫描。由于图像的纹理特性较多，本文使用了3种形式的扫描，横向扫描、纵向扫描、Zigzag扫描(见图1)。

1.2 位平面分解

在图像压缩之前，为提高二进制数据的相关性，根据式(1)将二进制码转换为格雷码，并对图像进行位平面分解。

二进制码转换为格雷码的公式为

式中:gi为格雷码的码字;bi为二进制的码字;⊕为模2加法运算。

下面进行位平面分解过程的介绍，对于一幅图像，每一个像素点都可以表示为1个8位二进制码，各像素点的二进制码在相同位置上的值构成的平面，称为位平面。在大多数的图像中相邻的像素值变化很小，所以构成的位平面中数据间具有很大的相关性。为进一步提高二进制数据的相关性，对图像进行位平面分解，并将图像位平面的二进制码依次排序。例如灰度图像的相邻灰度值为35，36，34，35，37，38，这些灰度值的十进制码是非常接近的，表示为二进制码后为 00100011，00100100，00100010，00100011，00100101，00100110，可以看出二进制码间的相关性不好，经过格雷码转换和位平面分解后，得到的二进制 码 流 为 00000000，00111111，11110000，00101111，11000111，二进制码间的相关性显著提高。

2 渐近式压缩编码

对预处理后的二进制码流S(长度L)进行压缩编码，根据转换算法得到转换后的码流S1(长度L1)，转换后的数据按照所给句法存储;根据压缩算法对S1进行压缩，得到压缩后的码流S2(长度L2)，按照所给句法存储;如果满足L2＜L1，则返回再一次进行转换，否则按图中的句法结构存储压缩完成的最终数据。渐近式压缩算法包括转换、编码两个核心算法。

2.1 转换算法

转换过程的目的是进一步调整二进制码流以提高码字间的相关性从而提高压缩效率。

1)首先定义一串连续的二进制码为转换标记aggregation_idc，如令转换标记为ω1ω2…ωp，(ωi取0 或1，1≤i≤p，p≥2);

2)然后将二值信源信息按长度p分为各个转换单元，依据转换标记值为1的位置，将二值信源各转换单元中相应位置的值提取到序列的前端，转换后的码流长度为L+P。

例如取P=8，则转换标记aggregation_idc的取值种类为0～28-1(0～255)，令aggregation_idc=01000010，即分别将二值信源D各个转换单元S1的第2位和第7位的二值数移到序列的前面得到S2，其他不变(见图2)。

图2 转换例子

转换后的结果S3由转换标志位和转换后的序列两部分组成，比较S1与S3可以看出，转换后的序列相关性提高有利于更进一步的压缩。按图3的句法结构保存转换后的数据。句法中的“转换标记”占1 bit，若值为“1”表示经过了转换处理，后面的p比特则为相应的转换标志位，值为“0”则表示没有经过转换处理，转换标志位不存在，可见增加1 bit的转换标记是非常有必要的，可以很大程度地防止没有转换处理时转换标志位的浪费，节省了码字开销。

2.2 编码算法

现有的RLC方法大多基于编码表或字典，很明显这些方法不适合码字间相关性低的码流压缩。编码算法是本文渐近式无损压缩算法的核心部分，而上文中的转换过程都是为能得到更好的压缩效率。本文的编码算法不需要任何编码表或字典，可以对局部码流多次压缩。

在RLC算法中，将具有相同灰度值的相邻像素组成的序列称为游程，游程中像素的个数称为游长。在二值图像中，其中:连续“1”的个数称为黑长，连续“0”的个数称为白长。

编码过程:

1)令白长为L0m(m≥1，L0m≥1)，黑长为L1n(n≥1，L1n≥1)，根据实验结果，选择合适的白长特征长度l0p(p≥1，1≤l0p＜16)和黑长的特征长度l1q(q≥1，1≤l1q＜16)，迭代次数为N，初始值设为0。

2)将二进制序列中L0m和L1n的分为四类:L0m≥l0p，L0m＜l0p，L1n≥l1q，L1n＜l1q，将分别满足L0m≥l0p与L1n≥l1q的白长和黑长编码为

式中:所得到的商表示Q0mp个连续的“0”和Q1nq个连续的“1”;余数R0mp和R1nq分别为“0”和“1”。所有的商在一起保存为商序列Tk1，所有的余数在一起保存为余数序列Tk2，不满足编码条件的黑长和白长直接按顺序存储在Tk1中。

3)将l0p、l1q、Tk1和反向存储的Tk2按顺序存放在一起作为下一次编码的原序列，迭代次数N加1;

4)转到步骤2)，将步骤3)中得到的二进制序列进行编码，直到不能压缩为止;

5)经过K次编码后，参照图4中的句法结构保存结果。句法“迭代次数”占用8 bit，取值范围为0～28-1(0～255)，因此最多可允许进行255次迭代运算。下面举例说明。

图4 压缩算法的句法结构

S21是一段视频二进制码流，经过转换处理，现在的长度为191 bit。

令l01=4(01002)，l11=2(00102)，根据以上的编码步骤2)可得商序列T11和余数序列T12。

可以看到编码后表示商的码字与游长L0m＜l0p或L1n＜l1q的码字不会有重码出现，因此可以重复步骤2)进行多次编码。将多次编码后的l01、l11、T11和反向的T12放在一起构成序列S22。

令l02=3(00112)，l12=5(01012)，得到商序列T21和余数序列T22，S23为编码后的序列。

假设S23是最后一次编码得到的序列，在序列前加上迭代编码的次数，就是编码后的最终序列S24。

多次实验显示黑长和白长都小于16，因此只需分配黑长和白长各4 bit。对余数序列进行反向存储，这样在解码时不需要知道商序列和余数序列的长度或设置任何标志位，只需从左右两个方向分别取商和余数直到取完为止。经过两次编码后数据由191压缩到138。在编码过程中，压缩步骤与转换过程是捆绑进行的，使用转换算法可以得到进一步的压缩。

以下是解码过程:

1)从码流的首部读取迭代次数(8 bit)的值。2)依次读取l0p(4 bit)和l1q(4 bit)的值。

3)将二进制序列中L0m和L1n的分为4类，L0m≥l0p，L0m＜l0p，L1n≥l1q，L1n＜l1q，将分别满足L0m≥l0p与L1n≥l1q的白长和黑长解码为将不满足此解码条件的序列无需解码直接按顺序存储在解码后的序列中。

迭代次数自减1，转到步骤2)对从步骤3)中得到的解码序列继续解码，直到迭代次数为0，解码完成。

2.3 编码过程

按照渐近式无损压缩流程(图5)对预处理后的二进制码流S(长度L)进行压缩编码，步骤如下:

1)根据转换算法得到转换后的码流S1(长度L1)，转换后的数据按照图中的句法存储;

2)根据压缩算法对S1进行压缩，得到压缩后的码流S2(长度L2)，按照图中句法存储;

3)如果满足L2＜L1则返回步骤1)再一次进行转换，否则继续;

4)按图中的句法结构存储压缩完成的最终数据。

3 实验与结果分析

为了验证本算法的性能，选择了标准测试图中的20张图像进行实验，图片规格分别为256×256和512×512的8位灰度图(图6)。首先对图像数据进行预处理，由于图像的纹理千变万化，对灰度图像分别进行横向扫描、纵向扫描、Zigzag扫描并进行比较，取其中相关性较好的扫描方法，这里采用统计图像相邻像素点的平均方差作为判断图像像素相关性的标准，平均方差越小，相关性越好。然后对扫描得到的数据进行二进制到格雷码的转换和位平面分解。最后使用本文提出的编码方法对得到的二进制码流进行编码。压缩质量的客观评价通常采用压缩比C和峰值信噪比(PSNR)两个指标来衡量，而无损压缩不存在PSNR这个指标。本文将对压缩比进行比较。

图6 经典灰度测试图

设图像尺寸为M×N，每个像素为Bp比特，压缩后总比特数为B。压缩比的计算公式为

对图中的图像经测试后得到的数据记入表1，并将结果与长度减半算法进行比较。

表1 经典灰度图像的压缩比

从表1中的实验结果可以看出渐近式编码方法能达到较好的压缩效果，比长度减半算法要好。

4 结语

文中提出了一种渐近式无损图像压缩算法，算法在编码前先对二进制码流进行预处理，并对二进制码流的顺序做出调整，提高了数据间的相关性，采用提出的编码算法对数据进行更深层次的压缩，反复进行转换过程与编码过程的交替，完成数据的压缩。经过多次实验表明，本文提出的渐近式压缩算法适用于各种纹理的图像，通过与长度减半算法的实验对比，本文的算法具有更高的压缩比。

:

［1］姚庆栋，毕厚杰.图像编码基础［M］.北京:清华大学出版社，2006.

［2］李雷定，马铁华，尤文斌.常用数据无损压缩算法分析［J］.电子设计工程，2009(1):49-51.

［3］武晓玥.图像无损压缩及去噪技术研究［D］.西安:西安电子科技大学，2010.

［4］王春洁.无损图像编码技术研究［D］.湘潭:湘潭大学，2013.

［5］王大伟，于乐，章圣焰.静态图像无损/近无损压缩技术研究［J］.航空电子技术，2013，44(3):31-35.

［6］孟凡勇.Huffman编码在环保实时监测系统中的研究与应用［D］.青岛:中国海洋大学，2010.

［7］ BENTLEY J L，SLEATOR D D，TARJAN R E，et al.A locally adaptive data compression scheme［J］.ACM Communications，1986，29(4):320-330.

［8］ TOGNERI R，DESILVA C J S.Fundamentals of information theory and coding design［M］.Boca Raton，FL，USA:CRC Press，2003.

［9］ SHEN Dingtao，CUI Can，WANG Jiechen.Implementation and application of intersection operation based on run-length encoding［C］//Proc.International Conference on Computer Science and Software Engineering.Wuhan:IEEE Press，2008:602-606.

［10］ LUSE M.Bitmapped graphics programming in C++［M］.Boston，MA，USA:Addison-Wesley Longman Publishing Co.，Inc.，1993.

［11］ ACHARYA T，TSAI P S.JPEG2000 standard for image compression:concepts，algorithms and VLSI architectures［S］.2004.

［12］ SALOMON D.Data compression:the complete reference［EB/OL］.［2013-11-20］.http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20&path=ASIN/0387406972.

［13］高健，刘万，宋奥，等.基于长度减半的二进制码流的压缩算法［J］.计算机应用，2011(7):1856-1858.

［14］ BOVIK A C.The essential guide to image processing［EB/OL］.［2013-11-20］.http://www.doc88.com/p-397145670042.html.