[科普中国]-行程编码

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

行程编码的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

end

end

end

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

对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

end

end

end

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

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