RLE图像压缩算法优化研究与应用

郑静 王腾

摘要：该文对比了传统的RLE（游程编码）算法，通过对RLE压缩编码的分析，得出RLE压缩算法存在很大的优化空间，并实现了优化后的RLE图像压缩算法，且着重介绍了这种算法的优缺点和优化方向。

关键词：RLE算法；图像压缩算法；算法优化

中图分类号：TP1 8 文献标识码：A 文章编号：1009-3044（2014）25-5981-04

RLE Image Compression Algorithm Optimization Research and Application

ZHENG Jing ， WANG Teng

（Yangtze University college of arts and sciences， Jingzhou， Hubei 434020， China）

Abstract： Compared to the traditional RLE algorithm， through analysis on compression coding of RLE ， the optimization space RLE compression algorithms exist， follow RLE image compression algorithm to achieve the optimized， and emphatically introduces the advantages and disadvantages of this algorithm and optimization direction.

Key words： RLE ； image compression algorithm； algorithm optimization

大数据量的图像信息会给储存器的储存容量，通信信道的带宽以及计算机的处理速度增加极大的压力，单纯靠增加储存容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，只能从软件方面着手，即压缩。研究结果表明，选用合适的数据压缩技术，有可能将原始数据量压缩为原来的二分之一左右。

1 RLE编码压缩算法概述

RLE（Run-Length Encodeing）编码是windows系统中使用的一种图像文件压缩方法，由于这种压缩格式使用不广泛，一般文献中介绍得很少，且一般的图像处理软件也不支持这种压缩格式。但是，WINDOWS 3.X和WINDOWS 95的启动提示信息的图像文件都是采用这种压缩格式存储的，而且，这种格式存储的图像文件读取速度快，保真程度高，特别适合于信息量大、保真程度高的信息显示系统中。RLE方法主要分为一般的RLE算法、RLE4算法和RLE8算法。

1.1 一般的RLE压缩算法

当图像数据出现连续重复的数值时，在这两个数值的前面，加上一个长度值，表示这个数值重复的次数。用这两字节代表一串连续重复值的数据，第一个字节代表一串相同数据的个数；第二个字节代表这串字节的值。此外，在选定第一个字节时，还必须把最高位的两个Bits当作标志，将这两个Bits都设成1，即11000000（0xC0），其余6个Bits的值，才是代表相同数据的个数，所以其最大值只能到63，也就是说，这两个字节最多能取代63个连续重复出现的字节。

例如，有下面一串图像数据等待压缩处理：

0x19 0x19 0x19 0x19 0x19 0x19 0x19 0x19 0x19 0x54

0x35 0x1C 0x27...（连续重复70个0x27） 0xD7 0xD5 0xE7

经过压缩处理后，图像数据变为：

0xC9 0x19 0x54 0x35 0xlC 0xFF 0x27 0xC7

0x27 0xCl 0xD7 0xCl 0xD5 0xCl 0xE7

0x19连续重复出现9次，以0xC9和0x19取代，而0x54， 0x35，0x1C三个值互不相同，只能保持原状，接着连续重复70个0x27，这已经超出最大值63，所以，必须用两组压缩码来代表。最后三个数并不相同，却用三组压缩码代替，是为了避免解压缩数据时发生错误，误将0xD7和0xD5译为55个0xD5，因此，遇到图像数据大于或等于0xC0 （192）时，即使不是连续重复出现的数据，也必须用一组压缩码来代表一个Byte值。

一般的RLE算法只能压缩处理连续重复同一数值的数据串，若是遇到数值不同的连续数据，就只能将数据原封不动地存入图像文件内，也就是说，一般RLE无法压缩处理不同值的数据串。在特殊情况下，经过一般RLE压缩算法处理的图像数据，有时不但不减少，反而比压缩前更多，所以，有必要对该算法进行改进。

1.2 RLE4压缩算法

RLE4压缩算法是在改进一般的RLE压缩算法的基础上而产生的，它和一般的RLE有相同之处，它仍以两个字节代表一串相同数值的图像数据。但是，RLE4压缩算法的计数方式和识别码与一般的RLE有所不同。在RLE4中，第一个字节表示图像数据的点数，而非字节数；RLE4的识别码也有四种，每种识别码的第一个字节必须为零，其表示方式如下：

1） 0x00 0x00表示一行图像的结束，RLE4压缩算法将一行视为一个压缩单元，每行经过压缩后，都会在压缩数据的末尾加入0x00 0x00两个字节。

2） 0x00 0x01表示所有图像数据的结束。

3） 0x00 0x02 X Y表示向右移动X点，向下移动Y点。这是当背景画面确定之后，想在背景的某块区域加入图像时，就先在这一块图像数据的前面，加上这段控制码。

4） 0x00 N…表示有N点不同数值的图像数据。如果不同数值的图像数据为奇数个字节，必须在数据末端加入0x00，以维持压缩数据的长度为偶数个字节。

如有以下原始数据：

第一列 0x36 0x36 0x36 0x32 0x83 0x51 0x27 0x27…0x27 0x27 0x27

第二列 0x96 0x98 0x42 0x17 0x77 0x77 0x77 0x77…0x62 0x62 0x81

经过RLE4压缩后变为：

第一列 0x03 0x36 0x00 0x06 0x32 0x83 0x51 0x00 0x04 0x27… 0x06 0x27 0x00 0x00

第二列 0x00 0x0c 0x96 0x98 0x42 0x17 0x08 0x77…

0x04 0x77 0x02 0x81 0x00 0x00 0x00 0x0l

1.3 RLE8压缩算法

RLE8压缩算法与RLE4非常类似，只是计数方式不同。在RLE8中，压缩码的第一个字节代表重复数据个数，RLE8 压缩算法只用于256色的图像压缩，而256色图像正好是一个字节存储一点。从下面的数据可以清楚的看到RLE4和RLE8的区别：

原始数据 0x82 0x82 0x82 0x82 0x96 0x46 0x33

RLE4压缩数据 0x08 0x82 0x00 0x06 0x96 0x46 0x33 0x00

RLE8压缩数据 0x04 0x82 0x00 0x03 0x96 0x46 0x33 0x00

1.4 RLE编码的优缺点

当图像中存在很多块颜色相同的大面積区域时，RLE编码产生的压缩率很高。但如果图像中很少有两个相邻的像素的灰度值相同时，RLE非但不能压缩，还会造成图像数据量增大的情况。

2 RLE优化算法的总体设计

2.1颜色表

图像每一个像素都可用RGB值来表示，该文在量化环节取B通道颜色，解压时将B通道的颜色赋到三个通道中，就形成了一张灰度图像。由于仅取B通道颜色，量化后颜色种类较少，为了用最少的存储空间来表示颜色，就必须有一个颜色对照表。例如：现在有两种颜色0和255，用颜色存储，需要8个bit，用索引存储，只需要一个bit（0代表0色，1代表255色）。

2.2索引表

索引表和颜色表配合使用，索引表中储存的是相应颜色在颜色表中的位置。索引表的长度为图片的长乘以宽，所以压缩图片即是压缩索引表，由于索引表中存储的是颜色位置，所以储存的数值较小，经量化后，还远远小于一个字节能表示的最大长度，存储时只需要用少量的bit位即可表示相应的颜色。

2.3 RLE算法的优化

1） RLE算法的思想

将一行中颜色值相同的相邻像素用一个计数值和颜色值来代替。一组数据需要两个字节存储，其中计数值用一个字节，颜色值用一个字节。

2） RLE优化的过程

主要分两步优化RLE图像压缩编码，第一步从图像的冗余方面，第二步从存储的方式方面。

图像冗余方面，整张图片转换成一个连续的字符串，相对于以前逐行寻找规律，连续的字符串更容易寻找规律。存储方式方面，优化后的RLE，去掉开始标志和结束标志，扩展了一个颜色表和一个检索表。例如：图片颜色矩阵

243 243 243 252 252 255 255 255 255 255 200

243 243 243 252 252 255 255 255 200 200 200

241 241 243 250 250 255 255 200 200 200 200

颜色表：

如直接存储图片矩阵需要33个字节，转化成检索表存储（共6种颜色，每一种用3个bit存储即可）只需要13个字节。所以使用颜色表和检索表可提高压缩效率，节约大量的存储空间。

接下来，针对检索表进行压缩，检索表的压缩，用到了RLE的思想，即相邻连续位置（检索表中存储的是该颜色在颜色表中的位置），使用颜色数目和位置表示，上面例子用RLE编码方式得到结果：3，0 2，1 5，2 1，3 3，0 2，1 3，2 3，3 2，4 1，0 2，6 2，2 4，3，如果直接用RLE编码，需要26个字节存储，反而扩大了存储空间。该文处理方式是根据编码后得到的结果，分配存储空间。从上面的结果，能得出最大数值为5，用3个bit即可表示，每个位置也只需要用3bit，一组数据6bit即可表示，该文的算法压缩后占用存储空间为：6bit×13=69bit=9byte。该文算法的总体压缩率为9byte/33byte=27.27%。

综上所述，该文算法最核心的地方就是根据颜色种类和表示连续颜色的数值自动选择合理的存储位数，其中如果连续数值过大，会对数值进行分割，一组数据最大的存储单位为8bit，超过8bit就分割成多组。算法最大的优点和难点即是颜色和数值的存储位数也不是固定的，而是根据图片本身的情况，得到最优的存储方式，节约大量的存储空间。

2.3 优化后RLE算法优势

优化后的RLE压缩编码相对于传统的RLE压缩编码，对图片适应性更强，适用图片范围更大。优化后的RLE，继承了传统RLE的优势，又在一定程度上避免了RLE编码的缺陷，不会出现压缩后比压缩前文件还要大的情况。

2.4 与优化后RLE压缩率相关的因素

1） 颜色表的长度（图片本身和量化情况决定）；2） 相邻颜色连续的个数；3） 颜色个数储存使用的bit位数。

3 RLE优化算法与图像压缩的设计

3.1优化的RLE编码

3.1.1获取颜色表、检索表

首先对图片矩阵进行扫描，扫描第一个元素时，将第一个颜色写到颜色表（temclr），并在检索表（search）中写入0（颜色表的1号位置即下标为0的位置），后面扫描，每扫描一个元素，就到颜色表（temclr）中寻找是否有此元素颜色，如果没有，则将新颜色写到颜色表（temclr），并将此时写到颜色表（temclr）中的位置保存到检索表（search），如果有，将该颜色所在颜色表（temclr）的位置写到检索表（search）。扫描完成则检索表（search）和颜色表（temclr）生成完成。

3.1.2 检索表的优化RLE编码

此步骤主要实现对检索表进行RLE编码，color_cishu变量即为计算后得到的表示位置数值的最大bit位数，代码中用一个字节来表示颜色重复数目和颜色，其中位数按照颜色的种类分配。例如：二值图像，颜色只需要一位来表示（0、1分别表示一种颜色），剩下的7位表示数目，那么一次能表示的最大个数为127。

3.2获取图片矩阵

加载BMP图片，获取图片的长（iw）、宽（ih）和图片矩阵灰度值的长串（mData）这些基本信息。这些信息会写到配置文件中，还原图片时需要用到这些信息。

3.3 量化

可分为两步，第一步是计算颜色个数，第二步是量化。计算颜色个数，主要目的是根据颜色个数和选择的压缩级别进行量化，例如：统计颜色种类为16，选择一级压缩，则此时不进行任何量化，直接取该16种颜色；选择选择二级压缩，那么必须根据这16种颜色量化成为8种。

3.4写配置文件

分三个步骤，对应配置文件主要存储的三个信息，分别为图片长宽、颜色个数和位数、颜色表。

第一步，将图片长和宽写到配置文件中，长和宽分别用两个字节表示，所以能压缩图片最大的长宽都为65536（16bit能表示的最大值），“长”在配置文件中储存的位置为第一个和第二个字节，第一个字节表示长的高8位，第二个字节表示长的低8位。“宽”在配置文件中储存的位置为第三个和第四个字节，第三个字节表示宽的高8位，第四个字节表示宽的低8位。

第二步，将颜色个数和体现这些颜色所需要的最少位数写到配置文件中，在配置文件中的位置为第五个和第六个字节，用for循环计算颜色表所需要的最少位数。

第三步，将获取到的颜色表写到配置文件中。

3.5解压检索表

解压检索表相当于压缩过程的反向执行，读出一个字节，还原其颜色，保存到pix中，读取完成，则pix的大小为iw×ih，pix中保存的是颜色，不再是颜色表中的位置。

3.6解压配置文件

读取配置文件的信息时，读出颜色表、颜色个数、存储颜色的位数配合检索表对图像矩阵进行还原，读出的长和宽配合pix对图像进行还原。

3.7 还原图像

还原图像时，将b通道的颜色，赋予到其他通道中，三个通道颜色相同的是灰度图像，所以本算法只适合灰度图片的压缩。

4 压缩率对比

4.1经典压缩算法压缩率表

4.2压缩率对比小结

图片颜色越简单，各种压缩编码压缩率越大。颜色复杂的图片，LZW压缩效果最好，经过优化的RLE排第二位，RLE编码压缩后比压缩前文件更大；颜色分布较为简单的图片，优化的RLE压缩编码压缩效果最好，LZW压缩效果其次，传统的RLE编码压缩效果依然很差；二值图像，哈夫曼压缩效果最好，其次是优化的RLE，效果最差的依然是传统的RLE编码。所以，优化后的RLE编码，适应性最好，压缩比率也较为可观，较传统的RLE，具有很大优势。

5 结束语

优化后的RLE编码较传统RLE优势明显，但不足之处也非常明显，处理图片有局限性，只适合处理灰度图片，其他图片会自动转换成灰度图片处理。量化算法还需要优化，压缩率大的时候，图片失真较多，且难以还原。量化的优化方向，主要是量化后颜色还可以尽可能多的还原，让图片尽可能少的失真。优化后的RLE算法，虽说较为灵活，但存储空间利用率并非达到了极致。优化方向是将霍夫曼编码整合进去，实现存储空间的最大利用率。该文算法压缩的时候，对图片进行了三次扫描，对压缩速度也有一定的影响。