[科普中国]-游程长度编码

游程长度

信息时代，人们对使用计算机获取信息、处理信息的依赖性越来越高。多媒体计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频和音频信号的数量之大是惊人的，与硬件技术所能提供的计算机存储资源和网络带宽之间有很大差距。这样，对多媒体信息的存储和传输造成了很大困难，成为阻碍人们有效获取和利用信息的一个瓶颈问题。多媒体信息使用的前提是进行有效的压缩。例如一段时间长度为1min，图像尺寸为640×480 pixels，每秒播放30帧的非压缩彩色(24位真彩色)视频的信息量为：640×480×3×30×60=1658880000Bytes，约为1。6GB(未含音频信息的容量)，如果用650MB的CD-R来存放，需要3张。由此可见，在视频信息的处理及应用过程中压缩及解压缩技术是十分必要的[3]。数据压缩技术主要采用两种方法，一种是“保真率”较高的无损压缩法；另一种是以损失信息细节而换取较高压缩比的有损压缩法。无损压缩虽然压缩比不是很高，但还原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常用的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼(Huffman)编码、算术编码(AC)和游程长度编码(RLC)。其中，游程长度编码是一种十分简单的压缩方法，编码/解码的速度也非常快，因此得到了广泛的应用。许多图形和视频文件，如BMPTIF及AVI等，都采用了这种压缩方法，尤其适用于文本(文件)数据压缩，它主要是去除文本中的冗余字符或字节中的冗余位以达到减少数据文件所占的存储空间的目的。

游程长度RL(Run-Length)，简称游程或游长，指的是由字符(或信号取样值)构成的数据流中各个字符重复出现而形成的字符的长度。如果给出了形成串的字符，串的长度及串的位置，就能恢复出原来的数据流，游程长度编码(RLC)就是用二进制码字给出这些信息的一类方法1。

游程长度编码原理游程长度编码的主要思想是将一个相同值的连续串用其值和串长(重复的个数)的数对二元组来替代。例如，在图像编码中，可以定义沿特定方向上具有相同灰度值的相邻像素为一轮，其延续的长度称之为延续的行程，即游程。游程终点位置由前一游程终点的相对距离确定，这样就可以由灰度游程串来表示图像数据。例如，若沿水平方向有一串M个像素具有相同的灰度N，则按游程长度编码后，只传递两个值(N，M)就可以代替这M个像素的M个灰度值N。简单来说，游程长度编码的主要任务是统计连续相同字符的个数，解码时要根据字符及连续相同字符的个数，恢复原来的数据1。

长度编码只用了40个整数就可以表示，而如果用前述的直接编码却需要64个整数表示，可见游程长度编码压缩数据是十分有效又简便的。事实上，压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高。

游程长度编码在栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存贮容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。

[font id="zoom" class="zoom"]游程长度RL (Run—Length)，简称游程或游长，指的是由字符(或信号取样值)构成的数据流中各个字符重复出现而形成的字符的长度．如果给出了形成申的字符，申的长度及申的位置，就能恢复出原来的数据流，游程长度编码(RLC)就是用二进制码字给出这些信息的一类方法。游程长度编码的主要思想是将一个相同值的连续申用其值和申长(重复的个数)的数对二元组来替代．例如，在图像编码中，可以定义沿特定方向上具有相同灰度值的相邻像素为一轮，其延续的长度称之为延续的行程，即游程．游程终点位置由前一游程终点的相对距离确定，这样就可以由灰度游程串来表示图像数据．例如，若沿水平方向有一申M 个像素具有相同的灰度N，则按游程长度编码后，只传递两个值(N，M )就可以代替这M个像素的M个灰度值N。简单来说，游程长度编码的主要任务是统计连续相同字符的个数，解码时要根据字符及连续相同字符的个数，恢复原来的数据．在多媒体信息量激增、网络特性和速度都飞速提高的今天，游程长度编码是一种十分简单的压缩方法，编码/解码的速度也非常快，可广泛应用于多媒体信息的存储，传输。

游程压缩模型在游程长度编码(RLC)中用3个字节表示一个字符串：第一个字节是压缩指示字符Sc，第二个字节记录连续出现的字符，第三个字节记录重复字符出现的次数。可见，只有当RL>3时进行数据压缩才有意义，因此，编码时首先要判断RL值，然后再决定是否进行游程长度编码(RLC)；解码时则需根据每一字符后是否为Sc，再决定其下一字符的含义，如下图所示例如：设一幅二维黑白图像F(i，j)的各像素的灰度值如下所示，规定沿水平方向从左到右扫描，则扫描后得到的游程为右边的13个二元组。由上例可见：

该图像是由8行、8列共64个像素组成；

像素的灰度值变化范围是：0～8；由于是黑白图，颜色过渡只是黑※灰※白，按人眼分辨率，用8bit即可(28=256)。

第一行8个像素灰度值相同，只传(8，8)；第二行只传(8，4)(7，4)；第三行只传(7，8)；第四行只传(6，4)(5，4)；第五行时只传(5，5)(3，3)；第六行只传(3，8)；第七行只传(3，3)(2，5)；第八行只传(1，4)(0，4)。这样，64个像素只需传13个数据对即可，比一个个像素传送要节省很多时间。一般情况下，编码时间=(2～4)解码时间。

例子对图1所示的栅格数据，可沿行方向进行如下游程长度编码：

(9,4),(0,4),(9,3),(0,5),(0,1)(9,2),(0,1),(7,2),(0,2),(0,4),(7,2),(0,2),(0,4),(7,4),(0,4),(7,4) ,(0,4),(7,4) ,(0,4),(7,4)