RLE行程长度编码压缩算法

#RLE行程长度编码压缩算法| 来源: 网络整理| 查看: 265

在看emWIN的时候看到一个图片压缩的算法可以有效的对二值图（简单的2中颜色或者更多）进行压缩，压缩的效果可以节省空间而且不丢失信息！

特点一种压缩过的位图文件格式，RLE压缩方案是一种极其成熟的压缩方案，特点是无损失压缩，既节省了磁盘空间又不损失任何图像数据。游程编码是一种统计编码，该编码属于无损压缩编码。对于二值图有效。其在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字串代替这些连续符号，可大幅度减少数据量。行程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。游程编码所能获得的压缩比有多大，主要取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。缺点在打开这种压缩文件时，要花费更多时间，此外，一些兼容性不太好的应用程序可能会打不开。不过RLE还有一个缺点，那要是内容像ABCABCABC的话使用这种算法文件会增大，就是1A1B1C1A1B1C1A1B1C了，更长，就达不到压缩的效果了。简单来说，游程编码就是用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”。行程编码因此而得名），使符号长度少于原始数据的长度 RLE压缩方式　 ABBBBBBBBA - 1A8B1A 下面都对byte流压缩。如输入数据 LPBTEpByte={1,1,1,1,1,1}; 压缩的数据为6,1 压缩了4个字符。但是在数据流里面不能直接这么替换，而应该使用特殊的控制字符，否则无法解压。比如pByte={6,1,0,1,1,1,1,1,1}; 这样有两个6,1无法判断是原有的6,1还是{1,1,1,1,1,1}压缩后的代码。所以应该有控制字符。 (1) 为了达到最大压缩率，可以先扫描源数据流，使用最少出现的字符做控制字符。如pByte={6,1,0,1,1,1,1,1,1,...}; 扫描后发现0为最少出现的字符。我们使用0作为压缩的控制，其他字符代表他本身。源数据里面的0,用0,0来表示。那么pByte压缩后为 6,1,0,0,0,6,1...... 解压时BYTEa,b,c; a=依次扫描压缩数据，如果输入字符为非控制字符，则直接输出到解压流。如果为控制字符，b=其下一字符是否也为控制字符，如果是，在输出流输出控制字符的代码。如果不是c=读压缩流，然后输出b个c到输出流。注意:该处对于>Ctrlcode的编码需要自己计算偏移. 如ctrl=2.那么n=3时应该修正为2. 刚才介绍的方法是最大压缩率的，但是因为对每个输入字符需要检查，速度不算快。 (2) 为了增加解压速度，可以采用其他的编码方式。主要方法是不对每个输入字符进行检查，只检查较少次就达到几乎相同的压缩率。来看看这个改进的方法。仔细观察，其实对不重复的字符也可以用控制n+数据的方式表示。这里的n带表n个未压缩数据。还是刚才的数据。 pByte={6,1,0,1,1,1,1,1,1} 不用扫描选择0为控制压缩为3,{6,1,0,}0,6,1 nctrlnm 解压就非常方便了扫描数据读一个字符， { n=read; if(n) { 字符拷贝n个 } else { n=read(); m=read; write(n个m); } } (3)优化对(1)的优化。观察得知，1,1,1这样的数据压缩率为0 下面的数组来自于emWIN压缩的图标数组：可以看到控制字符为0 /********************************************************************* * * bm0 */ static GUI_CONST_STORAGE unsigned char _ac0[] = { /* RLE: 011 Pixels @ 000,000 */ 11, 0xFF, /* ABS: 010 Pixels @ 011,000 */ 0, 10, 0xF6, 0xA8, 0x48, 0x1D, 0x11, 0x0E, 0x1E, 0x47, 0x8E, 0xE7, /* RLE: 021 Pixels @ 021,000 */ 21, 0xFF, /* ABS: 002 Pixels @ 010,001 */ 0, 2, 0xBF, 0x30, /* RLE: 008 Pixels @ 012,001 */ 8, 0x00, /* ABS: 003 Pixels @ 020,001 */ 0, 3, 0x17, 0x97, 0xFE, /* RLE: 017 Pixels @ 023,001 */ 17, 0xFF, /* ABS: 003 Pixels @ 008,002 */ 0, 3, 0xFE, 0x91, 0x08, /* RLE: 011 Pixels @ 011,002 */ 11, 0x00, /* ABS: 002 Pixels @ 022,002 */ 0, 2, 0x69, 0xF8, /* RLE: 016 Pixels @ 024,002 */ 16, 0xFF, /* RLE: 001 Pixels @ 008,003 */ 1, 0x7B, /* RLE: 005 Pixels @ 009,003 */ 5, 0x00, /* ABS: 004 Pixels @ 014,003 */ 0, 4, 0x03, 0x0E, 0x0F, 0x06, /* RLE: 005 Pixels @ 018,003 */ 5, 0x00, /* ABS: 002 Pixels @ 023,003 */ 0, 2, 0x49, 0xF6, /* RLE: 014 Pixels @ 025,003 */ 14, 0xFF, /* ABS: 013 Pixels @ 007,004 */ 0, 13, 0xBE, 0x04, 0x00, 0x00, 0x00, 0x03, 0x60, 0xC2, 0xED, 0xF1, 0xD3, 0x7F, 0x13, /* RLE: 004 Pixels @ 020,004 */ 4, 0x00, /* RLE: 001 Pixels @ 024,004 */ 1, 0x85, /* RLE: 014 Pixels @ 025,004 */ 14, 0xFF, /* ABS: 006 Pixels @ 007,005 */ 0, 6, 0x4A, 0x00, 0x00, 0x00, 0x06, 0xA2, /* RLE: 006 Pixels @ 013,005 */ 6, 0xFF, /* ABS: 007 Pixels @ 019,005 */ 0, 7, 0xCE, 0x21, 0x00, 0x00, 0x00, 0x19, 0xE4, /* RLE: 012 Pixels @ 026,005 */ 12, 0xFF, /* ABS: 006 Pixels @ 006,006 */ 0, 6, 0xD4, 0x08, 0x00, 0x00, 0x00, 0x7D, /* RLE: 008 Pixels @ 012,006 */ 8, 0xFF, /* ABS: 006 Pixels @ 020,006 */ 0, 6, 0xB8, 0x01, 0x00, 0x00, 0x00, 0x99, /* RLE: 012 Pixels @ 026,006 */ 12, 0xFF, /* ABS: 006 Pixels @ 006,007 */ 0, 6, 0x9B, 0x00, 0x00, 0x00, 0x15, 0xE5, /* RLE: 009 Pixels @ 012,007 */ 9, 0xFF, /* ABS: 005 Pixels @ 021,007 */ 0, 5, 0x48, 0x00, 0x00, 0x00, 0x5F, /* RLE: 012 Pixels @ 026,007 */ 12, 0xFF, /* ABS: 005 Pixels @ 006,008 */ 0, 5, 0x7A, 0x00, 0x00, 0x00, 0x46, /* RLE: 010 Pixels @ 011,008 */ 10, 0xFF, /* ABS: 006 Pixels @ 021,008 */ 0, 6, 0x82, 0x00, 0x00, 0x00, 0x3E, 0xFE, /* RLE: 011 Pixels @ 027,008 */ 11, 0xFF, /* ABS: 005 Pixels @ 006,009 */ 0, 5, 0x71, 0x00, 0x00, 0x00, 0x56, /* RLE: 010 Pixels @ 011,009 */ 10, 0xFF, /* ABS: 006 Pixels @ 021,009 */ 0, 6, 0x93, 0x00, 0x00, 0x00, 0x34, 0xFA, /* RLE: 011 Pixels @ 027,009 */ 11, 0xFF, /* ABS: 005 Pixels @ 006,010 */ 0, 5, 0x70, 0x00, 0x00, 0x00, 0x57, /* RLE: 010 Pixels @ 011,010 */ 10, 0xFF, /* ABS: 006 Pixels @ 021,010 */ 0, 6, 0x94, 0x00, 0x00, 0x00, 0x33, 0xFA, /* RLE: 011 Pixels @ 027,010 */ 11, 0xFF, /* ABS: 005 Pixels @ 006,011 */ 0, 5, 0x71, 0x00, 0x00, 0x00, 0x57, /* RLE: 010 Pixels @ 011,011 */ 10, 0xFF, /* ABS: 006 Pixels @ 021,011 */ 0, 6, 0x94, 0x00, 0x00, 0x00, 0x34, 0xFA, /* RLE: 011 Pixels @ 027,011 */ 11, 0xFF, /* ABS: 005 Pixels @ 006,012 */ 0, 5, 0x71, 0x00, 0x00, 0x00, 0x57, /* RLE: 010 Pixels @ 011,012 */ 10, 0xFF, /* ABS: 006 Pixels @ 021,012 */ 0, 6, 0x94, 0x00, 0x00, 0x00, 0x35, 0xFB, /* RLE: 008 Pixels @ 027,012 */ 8, 0xFF, /* ABS: 010 Pixels @ 003,013 */ 0, 10, 0xCF, 0x69, 0x59, 0x26, 0x00, 0x00, 0x00, 0x1D, 0x58, 0x57, /* RLE: 007 Pixels @ 013,013 */ 7, 0x56, /* ABS: 009 Pixels @ 020,013 */ 0, 9, 0x5B, 0x32, 0x00, 0x00, 0x00, 0x11, 0x53, 0x5E, 0xAF, /* RLE: 005 Pixels @ 029,013 */ 5, 0xFF, /* ABS: 002 Pixels @ 002,014 */ 0, 2, 0xD6, 0x18, /* RLE: 025 Pixels @ 004,014 */ 25, 0x00, /* RLE: 001 Pixels @ 029,014 */ 1, 0xA4, /* RLE: 004 Pixels @ 030,014 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,015 */ 1, 0x7E, /* RLE: 026 Pixels @ 003,015 */ 26, 0x00, /* RLE: 001 Pixels @ 029,015 */ 1, 0x46, /* RLE: 004 Pixels @ 030,015 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,016 */ 1, 0x63, /* RLE: 026 Pixels @ 003,016 */ 26, 0x00, /* RLE: 001 Pixels @ 029,016 */ 1, 0x34, /* RLE: 004 Pixels @ 030,016 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,017 */ 1, 0x64, /* RLE: 026 Pixels @ 003,017 */ 26, 0x00, /* RLE: 001 Pixels @ 029,017 */ 1, 0x35, /* RLE: 004 Pixels @ 030,017 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,018 */ 1, 0x64, /* RLE: 026 Pixels @ 003,018 */ 26, 0x00, /* RLE: 001 Pixels @ 029,018 */ 1, 0x35, /* RLE: 004 Pixels @ 030,018 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,019 */ 1, 0x64, /* RLE: 026 Pixels @ 003,019 */ 26, 0x00, /* RLE: 001 Pixels @ 029,019 */ 1, 0x35, /* RLE: 004 Pixels @ 030,019 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,020 */ 1, 0x64, /* RLE: 026 Pixels @ 003,020 */ 26, 0x00, /* RLE: 001 Pixels @ 029,020 */ 1, 0x35, /* RLE: 004 Pixels @ 030,020 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,021 */ 1, 0x64, /* RLE: 026 Pixels @ 003,021 */ 26, 0x00, /* RLE: 001 Pixels @ 029,021 */ 1, 0x35, /* RLE: 004 Pixels @ 030,021 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,022 */ 1, 0x64, /* RLE: 026 Pixels @ 003,022 */ 26, 0x00, /* RLE: 001 Pixels @ 029,022 */ 1, 0x35, /* RLE: 004 Pixels @ 030,022 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,023 */ 1, 0x64, /* RLE: 026 Pixels @ 003,023 */ 26, 0x00, /* RLE: 001 Pixels @ 029,023 */ 1, 0x35, /* RLE: 004 Pixels @ 030,023 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,024 */ 1, 0x64, /* RLE: 026 Pixels @ 003,024 */ 26, 0x00, /* RLE: 001 Pixels @ 029,024 */ 1, 0x35, /* RLE: 004 Pixels @ 030,024 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,025 */ 1, 0x64, /* RLE: 026 Pixels @ 003,025 */ 26, 0x00, /* RLE: 001 Pixels @ 029,025 */ 1, 0x35, /* RLE: 004 Pixels @ 030,025 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,026 */ 1, 0x64, /* RLE: 026 Pixels @ 003,026 */ 26, 0x00, /* RLE: 001 Pixels @ 029,026 */ 1, 0x35, /* RLE: 004 Pixels @ 030,026 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,027 */ 1, 0x64, /* RLE: 026 Pixels @ 003,027 */ 26, 0x00, /* RLE: 001 Pixels @ 029,027 */ 1, 0x35, /* RLE: 004 Pixels @ 030,027 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,028 */ 1, 0x62, /* RLE: 026 Pixels @ 003,028 */ 26, 0x00, /* RLE: 001 Pixels @ 029,028 */ 1, 0x34, /* RLE: 004 Pixels @ 030,028 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,029 */ 1, 0x6E, /* RLE: 026 Pixels @ 003,029 */ 26, 0x00, /* RLE: 001 Pixels @ 029,029 */ 1, 0x3B, /* RLE: 004 Pixels @ 030,029 */ 4, 0xFF, /* RLE: 001 Pixels @ 002,030 */ 1, 0xB5, /* RLE: 026 Pixels @ 003,030 */ 26, 0x00, /* RLE: 001 Pixels @ 029,030 */ 1, 0x7B, /* RLE: 005 Pixels @ 030,030 */ 5, 0xFF, /* ABS: 003 Pixels @ 003,031 */ 0, 3, 0x94, 0x1F, 0x0D, /* RLE: 020 Pixels @ 006,031 */ 20, 0x0F, /* ABS: 006 Pixels @ 026,031 */ 0, 6, 0x0D, 0x15, 0x6B, 0xF3, 0xFF, 0xFF, 0 }; // 416 bytes for 1024 pixels GUI_CONST_STORAGE GUI_BITMAP bm0 = { 32, // xSize 32, // ySize 32, // BytesPerLine GUI_COMPRESS_RLE8, // BitsPerPixel (unsigned char *)_ac0, // Pointer to picture data NULL, // Pointer to palette GUI_DRAW_RLEALPHA };

　　方法：

***************************************************************************************************************************************************

1.RLE概述

RLE（Run LengthEncoding行程编码）算法是一个简单高效的无损数据压缩算法，其基本思路是把数据看成一个线性序列，而这些数据序列组织方式分成两种情况：一种是连续的重复数据块，另一种是连续的不重复数据块。对于连续的重复数据快采用的压缩策略是用一个字节（我们称之为数据重数属性）表示数据块重复的次数，然后在这个数据重数属性字节后面存储对应的数据字节本身，例如某一个文件有如下的数据序列AAAAA，在未压缩之前占用5个字节，而如果使用了压缩之后就变成了5A，只占用两个字节，对于连续不重复的数据序列，表示方法和连续的重复数据块序列的表示方法一样，只不过前面的数据重数属性字节的内容为1。一般的这里的数据块取一个字节，这篇文章中数据块都默认为一个字节。为了更形象的说明RLE算法的原理我们给出最原始的RLE算法：

2. 原始RLE方法

给出的数据序列为：A-A-A-A-A-B-B-C-D

未压缩前：A-A-A-A-A-B-B-C-D

（0x41-0x41-0x41-0x41-0x41-0x42-0x42-0x43-0x44）

压缩后：5-A-2-B-1-C-1-D

（0x05-0x41-0x02-0x42-0x01-0x43-0x01-0x44）

从这里我们看到RLE的压缩和解压的算法原理非常简单，实现起来也并不复杂。

在进行压缩时逐个扫描待压缩数据，如果碰到某个字节后有重复的字节则计数器就加1（计数器初始值默认为1，也可设置为0），直到找到一个不重复的字节为止，将当前计数器中的值存入数据重数属性的字节中，将对应的该字节的数据存放在数据字节中，然后计数器置1继续用同样的策略扫描剩下的未压缩文档的数据。这里需要主意的是，数据重数属性的单位是一个字节，故最大值为255，因此对于数据序列的某一个数据重复次数大于255时的数据，当计数器记到255时就必须强制将计数器值和当前数据值写入数据重数属性字节中和数据字节中，然后计数器置1继续扫描，直到到达文件末尾。

由于压缩后的数据格式为：数据重数，数据块值，数据重数，数据块值……，因此解压的算法很简单，就是读出第一个位置上的数据重数字节存放的数据块的个数N，然后将第二个位置上的数据字节存放的数据块向解压缓冲区写N份，然后再读出第三个位置上数据重数字节存放的数据块的个数M，然后将第四个位置上数据字节存放的数据块向解压缓冲区写M份，直到读到压缩数据末尾结束。

代码如下：为了显示更清楚（将数据重数属性字节中的ASCII码值转换成了真实的数值，即本该为0x03的就用0x51表示）

[cpp] view plaincopyprint? #include #include #include #define MAX_SIZE 4096 /** 实现了一个简化版的RLE压缩算法，该算法要求字符重复次数不超过79个（127-48）如果是可打印的，则为78吧~ 因为127的ASCII码对应的字符Del是不可打印的 */ void CompressRLE(char* input ,char* output) { int i,j,k = 0; for(i = 0; i

【本文地址】

RLE行程长度编码压缩算法

RLE行程长度编码压缩算法

今日新闻

推荐新闻