行程长度编码

常用的无损压缩算法，将一扫描行中颜色值相同的相邻像素用两个字节来表示，第一个字节是一个计数值，用于指定像素重复的次数；第二个字节是具体像素的值。能够比较好地保存图像的质量，但是相对有损压缩来说这种方法的压缩率比较低

行程长度编码(RLE)定义

行长度编码是一种与资料性质无关的无损数据压缩技术。

变动长度编码法为一种“使用固定长度的码来取代连续重复出现的原始资料”的压缩技术。

行长度编码，在同一行上出现重复的像素点是记录一个像素及像素的重复数量，而不对每个像素进行记录，该压缩比率和特定的图象内容有关；

RLE行程长度编码概述

目前, 压缩技术已经广泛应用于各种软件、声音、影像格式等领域。总的来说, 有两种截然不同的图像格式压缩类型: 有损压缩和无损压缩[1]。有损压缩利用视觉识别的原理可以大大地压缩文件的数据, 但是会影响图像质量。无损压缩的基本原理是相同的颜色信息只需保存一次, 可以删除一些重复数据, 大大减少要在磁盘上保存的图像的容量。无损压缩方法的优点是能够比较好地保存图像的质量, 但是相对有损压缩来说这种方法的压缩率是比较低的。常用的无损压缩算法有 RLE、LZW等。

RLE 压缩算法的基本原理

RLE(Run- Length Encoding 行程长度编码)压缩算法是Windows 系统中使用的一种图像文件压缩方法, 其基本思想是: 将一扫描行中颜色值相同的相邻像素用两个字节来表示, 第一个字节是一个计数值, 用于指定像素重复的次数; 第二个字节是具体像素的值[2]。主要通过压缩除掉数据中的冗余字节或字节中的冗余位,从而达到减少文件所占空间的目的。例如, 有一表示颜色像素值的字符串RRRRRGGBBBBBB,用 RLE 压缩方法压缩后可用 5R2G6B 来代替,显然后者的串长度比前者的串长度小得多。译码时按照与编码时采用的相同规则进行, 还原后得到的数据与压缩前的数据完全相同。因此, RLE 是无损压缩技术。

RLE 压缩算法的改进

RLE 压缩算法对于数据重复量大的情况是非常高效率的。但是, 当图像像素的颜色值出现每个相邻像素的颜色值均不同的特殊情况时, 如颜色字符串GBR, 则经此方法压缩后变成了 1G1B1R, 反而会使数据串的长度增加一倍, 这是一种“病态”情况。为了尽量避免“病态”情况的出现, 需要对 RLE 的基本方法进行改进。改进的方法是在具体实施时对计数字节和图像像素字节进行了区分, 利用计数字节的高两位作为压缩的标志。对每个相邻像素的颜色值均不同的单个像素数据, 只有当计数字节高 2位全1( 即 C0) 时才加 1 计数, 否则直接输出该像素值, 因此避免了压缩后长度增加一倍的情况。这样就使得计数字节本身的高 2 位也是全 1, 即计数字节为 C0H+n( 像素数据连续相同的字节数)。当单个图像数据的值大于或等于C0 时, 则先输出 C1, 再输出该图像数据值, 否则直接输出该数据。如有以下一系列数据: D2,20,30,30,30,C0,C1,C1,E2,E2,E2,…,E2(132个),E0,E0,D4,经压缩后数据为 : C1,D2,20,C3,30,C1,C0,C2,C1,FF,E2,FF,E2,C6,E2,C2,E0,C1,D4,从这个压缩过程可以看到,单个的图像数据 D2、C0、D4 前面带有计数字节 C1, 而 20 前没有。这样可以有效避免压缩后膨胀的异常情况。在上述改进的基础上, 我们发现, 由于一个字节最大只能为 FFH, 因此 n 最大只能为 FFH- C0H=3FH=(63)10, 故当 n>63 时, 则需要分多次压缩。例如132个数据 E2 用了 6个字节 (FF,E2,FF,E2,C6,E2)来表示。为了减少大批量重复数据所需的字节数, 我们对其进行更进一步的改进: 规定紧跟 FF 后的字节, 依然是计数字节。如上述数据: D2,20,30,30,30,C0,C1,C1,E2,E2,E2,…,E2(132个),E0,E0,D4,经压缩后数据为:C1,D2,20,C3,30,C1,C0,C2,C1,FF,45,E2,C2,E0,C1,D4。比较两组数据, 现在 132个数据 E2 用了 3个字节(FF,45,E2)就可以表示了, 有效地减少了数据量。一种极端的情况是某个数据刚好重复的次数是 FF 次, 对于这种特殊情况, 我们在 FF 字节后增加一个 00 的字节来区别表示。通过这样的改进, 并不会增加压缩和解压缩太多的复杂性, 却改善了压缩的效率。

------------------

压缩策略

压缩

先使用一个暂存函数Q读取第一个资料，接着将下一个资料与Q值比，若资料相同，则计数器加1；若资料不同，则将计数器存的数值以及Q值输出，再初始计数器为，Q值改为下一个资料。以此类推，完成资料压缩。

以下为简易的算法：input： AAABCCBCCCCAA

解压缩

其方法为逐一读取整数(以C表示)与资料(以B表示)，将C与B的二进制码分别转成十进制整数以及原始资料符号，最后输出共C次资料B，即完成一次资料解压缩；接着重复上述步骤，完成所有资料输出。

RLE特点

从前面所给的例子中我们不难看出RLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之， RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。因此，具体实现时，需要和其它的压缩编码技术联合应用。

--------------------

重复次数即行程(Run-Length)

一种可行的方案是,将数据流中各数值分为两类:其中一类数值行程小于

或等于128,按原值输出;另一类数值行程大于128,此类

数值加上128后输出。综上所述,改进后的行程编

码算法如下:

①对行程小于或等于2的数值按原值输出;

②对行程大于2的数值,将其加上128后输

出,并在其后相邻位置输出行程大小。

RLE算法的局限性

在RLE数据压缩中,只有当重复的字节数大于

3时才可以起到压缩作用,并且还需要一个特殊的