RLE 行程长度压缩算法的改进.doc

RLE 行程长度压缩算法的改进 分类： VR 2007-05-21 22:54 967人阅读 评论(1) 收藏 举报 计算机所能处理的各种信息都是数字信息。数字化了的各种信息数据量很大，如果直接使用，肯定会给计算机造成很大负担。例如，一张A4幅面的图片，若用中等分辨率的扫描仪按真彩扫描，其数据量大约为26MB，这是一个不小数目。这些大量的数据信息会对存储器的存储容量、通信干线信道的带宽以及计算机的处理速度产生极大的压力，因此必须对这些数据进行压缩。本文仅就行程长度(RLE)无损压缩算法及其改进方法进行研究。1行程长度(RLE)压缩算法的基本原理1对于图像文件中的各个像素数据，由于图像颜色的梯度变化，相邻像素的颜色值相同的可能性极大，RLE(Run Length Encoding)压缩算法的原理就是将一扫描行中颜色值相同的相邻像素，用一个计数值和那些像素的颜色值来代替。主要通过压缩除掉数据中的冗余字节或字节中的冗余位，从而达到减少文件所占空间的目的。例如，有一表示颜色像素值的字符串aaaaaabbccccddddddddeeeeeee，用RLE压缩方法压缩后，可用6a2b3c8d6e来代替，显然后者的串长度比前者的串长度小得多。但是，当图像像素的颜色值出现特殊情况时，如每个相邻像素的颜色值均不同，则经此方法压缩后，反而会使数据串的长度增加一倍，为了尽量避免前述特殊数据的出现，RLE方法在具体实施时对计数字节和图像像素字节进行了区分，对每个相邻像素的颜色值均不同的单个像素数据，只有当高2位全1时才加1计数，否则直接输出该像素值，因此避免了压缩后长度增加一倍的情况。这样就使得计数字节本身的高2位也是全1，即计数字节为C0H+n(像素数据连续相同的字节数)。由于一个字节最大只能为FFH，因此n最大只能为FFH-C0H=3FH=(63)10，故当n63时，则需分多次压缩。当单个图像数据的值大于C0时，先输出C1，再输出该图像数据值，否则直接输出该数据。例如，有以下一系列数据:E2， 20， 30， 30， 30，C0，C1，C1，D3，D3，D3，D3(135个)，E0，E0，E0，E0，D4，经压缩后数据为:C1，E2， 20，C3， 30，C1，C0，C2，C1，FF，D3，FF，D3，C9，D3，C4，E0，C1，D4，从这个压缩过程可以看到，单个的图像数据E2、C0、D4前面带有计数字节C1，而20前没有，135个数据D3用了6个字节来表示。2行程长度(RLE)压缩算法的改进2。1方法1我们知道RLE压缩方法对于拥有大面积相同颜色区域的图像数据，其压缩效果是很高的。但有一些弊端，如遇到前述的特殊情况数据时，其压缩效果明显下降。为了回避此类数据而使其计数字节从C0开始，这又使得对于大批量重复出现的像素数据需要用更多字节来存储，如前述的135个D3需用6个字节来存储，同样降低了压缩效率。为此，我们可用特殊的控制字节，即用控制字节的最高位来指示是否进行压缩。当最高位为1时，则低7位表示字节的重复次数，这样可表示的最大重复次数是127;最高位为0时，则后面的X个数据是不压缩的，其中X是由控制字节的低七位来表示的。采取这种方法，一个字符只有重复两次以上，才能被压缩。即使一个数据只重复3次，也可以获得30%的压缩比。在此基础上，可以对RLE压缩方法进行进一步改进。当你要压缩的数据包括大量的空白时，可用更有效的方法来压缩重复较多的空白字符。具体的方法是只用控制字节来表示重复的空白字符，即用空白字节的第二高位(bit 6)来表示要压缩的是否是空白字符，如果bit 6为1 ，则后6位用来表示空白字符的重复次数，这样仅用一个字节就可表示63个字节的空白字符， 即使空白字符仅重复2次，也可获得50%的压缩比。此改进方法对于有大量空白的数据文件可获得较高的压缩比。如果某文件中重复较多的不是空白字符，而是另外一个字符，如图像的背景，我们也可以事先规定该默认压缩字符，同样用一个字节来表示63个字节的字符，从而获得较高的压缩比。2。2方法22在改进方法1的基础上，可进一步对上面重复字节数大于127而需分多次压缩的数据采用一次压缩，具体方法是调整计数方法，将计数字节FF后的字节作为计数字节。例如，上述图像数据:E2， 20， 30， 30， 30，C0，C1，C1，D3，D3，D3，D3(135个)，E0，E0，E0，E0，D4经压缩后数据为:C1，E2， 20，C3， 30，C1，C0，C2，C!，FF，D3，FF，D3，C9，D3，C4，E0，C1，D4而用改进后的方法压缩则成为:81，E2，20，83，30，81，C0，82，C1，FF，08，D3，84，E0，81，D4通过对这组数据的比较，我们看到原来用(FF，D3，FF，D3，C9，D3)表示的135个数据D3，现在用(FF，08，D3)表示，这里我们对于大于63字节的重复信息所需的计数字节作了调整，使得紧随计数字节FF后的字节仍是计数值的一部分，且不必作减除80的运算，从而减少表示这种大批量重复信息所需的字节数据。很显然，表示数据D3的字节数由原来的6字节减少到现在的3字节。通过分析我们发现这种方法较以前相比，会增加一个多余计数字节的唯一特例是当重复数据刚好等于127字节时，会在计数字节FF后增加一计数字节00，但这种情况出现的概率极小，而且这样改进后并不过多地增加压缩和译码算法的复杂性，同时更好地体现了RLE方法的压缩思想。3改进的RLE压缩算法的实现3。1压缩过程(1)打开原数据文件或打开压缩后的文件;(2)从原数据文件中读取字节，并把它放进一寄存器中，然后再循环读取后面的字节，与寄存器中的字符相比较，如果相等，则计数器加1，否则把寄存器中的字符和计数器中的值写入压缩数据文件，接着把寄存器中字符不相等的字符放进寄存器中，并把计数器置1。压缩算法流程图如图1。 3。2 解压缩过程(1)打开压缩文件。(2)从压缩文件中循环读出字符和该字符连续的个数，在恢复文件中连续写从压缩文件中读取的字符，写的次数等于该字符连续的个数4压缩效果分析比较改进前后的压缩算法，对行程长度小于或等于63字节的数据，其效果是一样的，但对于行程长度大于63字节的数据，改进后的方法其效果却高得多，从理论上讲，当N充分大时，后者所需的存储量仅为前者的百分之十几。经过具体比较，对于一般情况，后者