行程编码

计算机图形图像名词

行程编码（Run Length Encoding，RLE)，又称游程编码、行程长度编码、变动长度编码等，是一种统计编码。主要技术是检测重复的比特或字符序列，并用它们的出现次数取而代之。比较适合于二值图像的编码，但是不适用于连续色调图像的压缩，例如日常生活中的照片。为了达到较好的压缩效果，有时行程编码和其他一些编码方法混合使用。

基本介绍

行程编码（Run-length Coding）是相对简单的编码技术，主要思路是将一个相同值的连续串用一个代表值和串长来代替。例如，有一个字符串“aaabccddddd”，经过行程编码后可以用“3a1b2c5d”来表示。对图像编码来说，可以定义沿特定方向上具有相同灰度值的相邻像素为一轮，其延续长度称为延续的行程，简称为行程或游程。例如，若沿水平方向有一串M个像素具有相同的灰度N，则行程编码后，只传递2个值（N,M)就可以代替M个像素的M个灰度值N。

在此方式下每两个字节组成一个信息单元。第一个字节给出其后面相连的象素的个数。第二个字节给出这些象素使用的颜色索引表中的索引。例如：信息单元03 04，03表示其后的象素个数是3个，04表示这些象素使用的是颜色索引表中的第五项的值。压缩数据展开后就是04 04 04 。同理04 05 可以展开为05 05 05 05。信息单元的第一个字节也可以是00，这种情况下信息单元并不表示数据单元，而是表示一些特殊的含义。这些含义通常由信息单元的第二个字节的值来描述。

行程编码对传输差错很敏感，如果其中一位符号发生错误，就会影响整个编码序列的正确性，使行程编码无法还原回原始数据，因此一般要用行同步、列同步的方法把差错控制在一行一列之内。

基本原理

行程编码也叫作RLE压缩编码，其中RLE是Run-Length-Encoding的缩写，这种压缩方法是最简单的图像压缩方法。

行程编码的基本原理是在给定的数据图像中寻找连续的重复数值，然后用两个字符取代这些连续值。例如，一串字母表示的数据为“aaabbbbccccdddeeddaa”，经过游程编码处理可表示为“3a4b4c3d2e2d2a”。

对于数字图像而言，同一幅图像某些连续的区域颜色相同，即在这些图像中，许多连续的扫描都具有同一种颜色，或者同一扫描行中许多连续的像素都具有同样的颜色值。在这种情况下，只要存储一个像素的颜色值、相同颜色像素的位置以及相同颜色的像素数目即可，对数字图像的这种编码称为行程编码，把具有相同灰度值（颜色值）的相连像素序列称为一个行程。

对于简单的灰度图像，行程编码的数据结构如表6.2-1所列。

行程长度隐藏在起始坐标中，不必单独列出。

分类

行程编码分为定长行程编码和变长行程编码两种。定长行程编码是指编码的行程所使用的二进制位数固定。如果灰度连续相等的个数超过了固定二进制位数所能表示的最大值，则进行下一轮行程编码。变长行程编码是指对不同范围的行程使用不同位数的二进制位数进行编码，需要增加标志位来表明所使用的二进制位数。

行程编码一般不直接应用于多灰度图像，但比较适合于二值图像的编码。为了达到较好的压缩效果，有时行程编码与其他一些编码方法混合使用。例如，在JPEG中，行程编码和DCT及哈夫曼编码一起使用，先对图像分块处理，然后对分块进行DCT，量化后的频域图像数据做Z形扫描，再做行程编码，对行程编码的结果再进行哈夫曼编码。

技术特点

RLE是一种压缩技术，而且这种编码技术相当直观，也非常经济。RLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。

译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE是无损压缩技术。

RLE压缩编码尤其适用于计算机生成的图像。对减少图像文件的存储空间非常有效，然而RLE对颜色丰富的自然图像显得力不从心，在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大，注意，这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还少不了RLE,只不过是不能单独使用RLE—种编码方法，需要和其他的压缩编码技术联合应用。

三维行程编码

所谓三维行程编码就是将三维表示转换成一维表示，从而实现数据压缩的方法。在压缩过程中对属性值相同的连续编码进行压缩，同时保证空间关系没有任何损失。在三维行程编码中，叶节点采用与线性八叉树相同的地址码，即Morton码。十进制的Morton码是使用最广泛的一种方法，它具有线性八叉树编码的功能，但比常规八叉树和基于八进制的线性八叉树更有优势。由于十进制是一组连续的自然数，其中的顺序是一种空间最近关系。当采用自然数编码时，可以直接用Morton码作为域性值数组的下标。按照地址码的大小进行排序，得到的序列可以看成是一组子序列的集合，其中的每一个子序列对应于一组属性值相同的叶节点。对于每一个子序列只保留其第一个元素，删除其他元素，即可得到八叉树的三维行程编码表示。三维行程编码是线性八叉树的进一步压缩，其压缩的元素可以通过相邻两个三维行程编码的元素进行恢复。

三维行程编码具有以下优点：

①由于采用自然数编码排列，提高了检索和査询速度，对于插入、删除等操作更为简便，而且它与线性八叉树的转换也十分方便。

②由于它和线性八叉树一样不需要记录中间节点，从而省去了大量的中间节点指针的存储空间；合并过程按照这种自然数的顺序节省了排序工作，在存储空间上更节省。

③它以十进制为编码，比八进制更符合人们的使用习惯；在生成速度和使用习惯上，也表现得更快、更方便。

④当检査相邻栅格的属性以判断能否合并时，它不需要排序，从而节省了排序时间。Morton码的建立过程类似于基于八进制的线性八叉树编码。

应用实例

行程编码的M语言实现如例程6.2-1所示。

【例程6.2-1】

clear

读入图像并进行灰度转换

I=imread('pears.png');

imshow(I)

IGRAY=rgb2gray(I)

[m n]=size(IGRAY)

建立数组RLEEcod，其中元素排列形式为[行程起始行坐标、行程列坐标、灰度值]

c=I(1,1);RLEcode(1,1:3)=[1 1 c];

t=2;

进行行程编码

for k=1:m

for j=1:n

if(not(and(k = =1,j= =1)))

if(not(I(k,j)= =c))

RLEcode(t,1:3)=[k j I(k,j)]

c=I(k,j);

t=t+1;

end

对例程6.2-1分析可知，待压缩的灰度图像大小为486×732=355754个字节，而输出行程编码的数组为925719个字节，比原来图像占用的储存空间还要大，可见对该幅图像采用行程编码的效果并不好。

对6.2-1稍作修改，使得待压缩编码的图像为二值图像，如例程6.2-2所示，再来看行程编码的压缩效果。

【例程6.2-2】

clear

读入图像并转换成二值图像

I=imread('pears.png');

imshow(I)

IBW=im2bw(I);

[m n]=size(IBW);

建立数组RLEEcod，其中元素排列形式为[行程起始行坐标、行程列坐标、灰度值]

c=I(1,1);RLEcode(1,1:3)=[1 1 c];

t=2;

进行行程编码

for k=1:m

for j=1:n

if(not(and(k = =1,j= =1)))

if(not(IBW(k,j)= =c))

RLEcode(t,1:3)=[k j IBW(k,j)]

c=IBW(k,j);

t=t+1;

end

对二值化图像进行行程编码。压缩后的输出行程编码的数组为31170，为原来存储图像所需空间的8.8%，取得了良好的压缩效果。

通过对例程6.2-1和例程6.2-2的运行结果进行分析可知，行程编码对于仅包含很少几个灰度级的图像，特别是二值图像，压缩效果好.特别地，该编码方法对单一颜色背景下物体的图像.具有较高的压缩比。对于其他情况下的图像，其压缩比较低，甚至在最坏的情况下，比如图像的每一个像素都与周围的像素不同，行程编码甚至可将文件的大小加倍，达不到压缩编码的目的。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省