游程编码行程编码RLE

行程编码说在前面行程编码（RLE），又称游程编码，是一种利用空间冗余度压缩图像的方法。该压缩编码技术算法简单，解压速度快，是一种无失真编码，可以完整地还原数据，故在网络传输和大型数据备份等领域有着广泛的应用。浙教版《信息技术选择性必修1数据与数据结构》3.1字符串实践与体验“行程编码”来源于真实问题情境，综合了图像处理、文件操作和字符串操作等知识，算法简单、实用，是需要重点掌握的经典案例。教材文本教材处理教材介绍了“行程编码”的算法原理和实践步骤，并提供了参考代码和图片素材。教师可采用进一步细化问题的方式，帮助学生深刻理解算法原理；通过提供半成品程序的方式，让学生掌握核心代码的编写方法，实现程序功能。对学有余力的同学，可鼓励他们编写程序对“行程编码”进行解压缩，并还原成图片文件。学生任务单阅读教材P68实践与体验“行程编码”，思考如下问题：（1）如下程序能读取图片文件并转换成黑白图像，再将各像素点的颜色编号为0或1，拼接成字符串后存入“图像编码.txt”文件中。请仔细阅读代码，并回答注释中的问题。fromPILimportImageimg=Image.open('原图.bmp')#从文件加载图像，生成Image对象img=img.convert('1')#转换成黑白图像img.show()#显示图片pix=img.load()#获取各像素点的颜色值img_list=[]#请问下列程序在扫描图片时采用何种顺序：逐行扫描还是逐列扫描？forxinrange(img.width):foryinrange(img.height):img_list.append(str(pix[x,y]//255))#将像素点RGB值整除255的目的是什么？#保存数据到文本文件中fp=open('图像编码.txt','w')fp.write(''.join(img_list))fp.close()（2）若某黑白图像的图像编码为：0000001111111101000，则其对应行程编码为多少？（3）如下程序能读取图像编码文件并将其转换成行程编码，请将缺失的代码补充完整。#读取图像编码文件数据fp=open("图像编码.txt","r")img_coding=fp.read()fp.close()#对图像编码进行压缩处理RLE=[]cnt=1pre=img_coding[0]foriinrange(1,len(img_coding)):ifimg_coding[i]==pre:#统计连续相同字符填空1else:RLE.append(str(cnt)+""+pre)cnt=填空2pre=填空3填空4#处理最后一个字符所在子串#保存行程编码到文本文件中fp=open("行程编码.txt","w")fp.write("".join(RLE))fp.close()（4）压缩和解压缩是一个互逆过程，行程编码是一种无失真编码，可以完整地还原数据。如下程序能读取行程编码文件并将其转换成图像编码，请将缺失的代码补充完整。#读取行程编码文件数据fp=open("行程编码.txt","r")RLE=填空1fp.close()#对行程编码进行解压缩处理img_list=[]foriinrange(0,len(RLE),2):填空2#保存图像编码到文本文件中fp=open("还原图像编码.txt","w")fp.write(填空3)fp.close()问题解析（1）因为二重循环的外、内层循环分别遍历图像的横坐标和纵坐标，故程序采用逐列扫描图像方式。将像素点RGB值整除255的目的是将黑白像素值转换成0和1。（2）图像编码：0000001111111101000，对应的行程编码为：6081101130。（3）填空1：cnt+=1；填空2：1；填空3：img_coding[i]；填空4：RLE.append(str(cnt)+""+pre)。（4）填空1：fp.read().split()；填空2：img_list.append(RLE[i+1]*int(RLE[i]))；填空3：''.join(img_list)。课后作业既然可以把黑白图片的颜色编码，存储为“图像编码.txt”，那么能否读取“图像编码.txt”，将其还原成一张黑白图片呢？除了提供“图像编码.txt”文件，还需要哪些信息才能完成还原功能？请开动脑筋，编程实现该功能。

嵌入式算法10---行程编码1、行程编码嵌入式设备采集的数据，变化比较平缓，长时间趋于稳定的状态，其采样结果会有大量连续且相同的数值，对应这些数据，常规的压缩算法在硬件资源有限的嵌入式设备无法运行，代码空间和RAM要求不能满足的情况下，简单有效的行程编码不失为一种最佳选择。行程编码（RunLengthEncoding，RLE),又称游程编码，主要思路是将一个相同值的连续串用一个代表值和串长来代替。例如字符串“AAABBBBCCCCCJJJJJJ”，可以用“3A4B5C6J”来记录，原本长度18字节的字符串使用8个字节即可无损表达。为便于直观显示，举例的编码是进行了特殊描述，“3A4B5C6J”实际应该是3‘A’4‘B’5‘C’

6‘J’，字符个数的数字转为字符显示，例如3变成了‘3’显示更易理解。以下举例也是这个规则，正确方式是应该是以%X查看，如果不明白3和‘3’的区别，请先补习C基础。2、局限性与改进型行程编码的原理简单，但算法需结合实际，统计数据出现概率与次数，有针对性的改进编码，提高压缩比。按前面范例规则，原始数据全部都不连续出现，如源字符串“ABCDE”编码后变成“1A1B1C1D1E”，其长度反而扩大一倍，因此对于随机出现没有连续字符的数据，基本规则不适合。可以改进为编码时查询连续出现的才进行编码，只出现一次的直接使用原始值，不进行处理。如"111233334"编码为“312434”，字符2和4只出现一次，编码时忽略。但缺点是解码无法分辨其中的2是数值出现次数，还是数值本身。因此对编码与未编码的分段，使用标记区分段。例如定义编码段以E开头，则"111233334"编码为“E312E434”，解析时只对出现E的字段才进行解析，单个字段直接原样替换。增加段标记后，每个连续段编码后都是3个字节，如果相同字符值出现2次，如“11335577”则编码后为“E21E23E25E27”,其长度超过原始长度，因此可以改为，只有连续出现的次数大于3的才进行编码。例如"112223333"编码为“11222E43”。因为表示字符连续次数的数字分配了一个字节，某个字符如连续出现255次以上，则拆分为两部分。如“AAA...AAA”连续出现300次，则编码以%X显示为45FF41452D41，其中'E'=0x45,'A'=0x41。45

FF

41

//行程编码255个'A'

45

2D

41

//行程编码

45

个'A'前面描述编码段的头以'E'作为标记，字符连续出现次数大于3的才进行编码处理的，因此'E'后面的数字肯定大于3。如果源数据中存在‘E’，则以‘E’0转义，这样才能解析分辨，是真实的'E'，还是编码标记。如“EEEEE”编码后以16进制显示为4500

4500

4500

4500

45

00，结果是长度增加一倍，因此定义合理的标记很关键。选择字数据串中出现概率最小的为标记。如纯ASCII字符串（0-0x7F），选择0x80则避开该问题。算法规则没有最好的，只有最合适的，如果认可前面的规则，可继续阅读下面的源码，包括编码和解码。3、源码#include

"stdio.h"

#include

"string.h"

//配置为数据源中出现概率最小的数

#define

FLAG_ENCODE_HEAD

0x80

void

log(char

*head,unsigned

char

*data,unsigned

int

len)

{

unsigned

int

i;

printf("%s:",head);

for(i=0;i<len;i++)

{

printf("%02X

",data[i]);

}

printf("\r\n");

}

//行程编码

//输入待编码的数据及长度，提供输出编码数据的缓冲区

//返回编码后的长度

int

compress_encode(unsigned

char

*dect,

unsigned

char

*src,

unsigned

int

len)

{

unsigned

char

last

=

0,

count

=

0;

unsigned

char

*dd

=

dect;

unsigned

char

flag

=

1;

while(len)

{

if(flag)

{

flag

=

0;

}

else

if(last

==

FLAG_ENCODE_HEAD)

{

*dect++

=

FLAG_ENCODE_HEAD;

*dect++

=

0x00;

}

else

if(last

==

*src)

{

if(count

<

0xFF)

{

count++;

}

else

{

*dect++

=

FLAG_ENCODE_HEAD;

*dect++

=

count;

*dect++

=

last;

count

=

1;

}

}

else

{

count++;

if(count

>

3)

{

*dect++

=

FLAG_ENCODE_HEAD;

*dect++

=

count;

*dect++

=

last;

count

=

0;

}

else

{

while(count)

{

*dect++

=

last;

count--;

}

}

}

last

=

*src;

src++;

len--;

if(len

==

0)

{

count++;

if(count

>

3)

{

*dect++

=

FLAG_ENCODE_HEAD;

*dect++

=

count;

*dect++

=

last;

count

=

0;

}

else

{

while(count)

{

if(last

==

FLAG_ENCODE_HEAD)

{

*dect++

=

FLAG_ENCODE_HEAD;

*dect++

=

0x00;

}

else

{

*dect++

=

last;

}

count--;

}

}

}

}

return

(dect

-

dd);

}

//解码

//输入待解码的数据及长度，提供输出解码数据的缓冲区

//返回解码后的长度

int

compress_decode(unsigned

char

*dect,

unsigned

char

*src,

unsigned

int

len)

{

unsigned

char

cc

=

0;

unsigned

char

*dd

=

dect,

*src2

=

src;

while(len)

{

if(*src

==

FLAG_ENCODE_HEAD)

{

if(len

==

1

||

(src[1]

==

0

&&

len

<

2)

||

(src[1]

!=

0

&&

len

<

3))

{

return

-2;

}

cc

=

src[1];

if(!cc)

{

*dect++

=

FLAG_ENCODE_HEAD;

src

+=

1;

len

-=

1;

}

else

{

while(cc)

{

*dect++

=

src[2];

cc--;

}

src

+=

2;

len

-=

2;

}

}

else

{

*dect++

=

*src;

}

src++;

len--;

}

return

(dect

-

dd);

}

int

main(int

argc,

char

*argv[])

{

unsigned

char

input[100]={"AAAAAAAAABBBBBBBBBCCCCCCCCCDDDEFGGGGGGGGGGG#"};

//最差情况下编码后的长度是源数据的2倍，这种情况下应该调整编码规则

unsigned

char

encode_buff[200]={0};

int

encode_len;

unsigned

char

decode_buff[100]={0};

int

decode_len;

encode_len=compress_encode(encode_buff,input,strlen((char

*)input));

log("encode",encode_buff,encode_len);