游程编码的概念

游程编码的基本原理

将具有相同值的连续串用其串长和一个代表值来代替，该连续串就称为游程，串长称为游程长度。

编码思想

去除像素冗余：用游程的灰度和游程的长度代替游程本身。

二元信源的游程编码

二元信源即只有 0 和 1 符号的信源

二元信源中 0 游程和 1 游程总是交替出现； 如规定某二元序列是从 0 开始, 第一个游程是 0 第二个是 1，第三个是 0 等等。

• 0 游程：连续出现 0 符号的段 --> 0 游程长度记作 L(0)
• 1 游程：连续出现 1 符号的段 --> 0 游程长度记作 L(1)
• 游程序列：用自然数标记的游程长度，映射成交替出现的游程长度序列

多元信源的游程编码

• 定长游程编码：编码的游程长度所用的二进制位数固定。
• 变长游程编码：不同范围的游程长度用不同编码位，需要增加标志位来表明所使用的二进制位数。

变长游程编码举例：

但是增加的标志位可能抵消压缩编码带来的好处，所以多元序列进行游程编码的意义不大。

游程编码优缺点分析

缺点

• 游程编码仍然是变长编码，有其固定的缺点，需大量的缓冲和优质的信道。
• 编程长度可以从 1 一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改进。
• 只适用于二元序列，对于多元信源，一般不能直接利用游程编码。
• 游程越长，出现的概率越小；游程长度趋于无穷时，其出现的概率也趋向于零。
• 按照霍夫曼编码的规则，概率越小，码长越长，但小概率的码字对平均码长的影响较小。
• 所以在实际应用时，对长游程一般采用截断处理的方法，将大于一定长度的长游程统一用等长码编码。

图像的游程编码

• 对某些相同灰度级成片连续出现的图像，游程编码也是一种高效的编码方法。特别是对二值图像，效果尤为显著。
• 游程编码所能获得的压缩比主要取决于图像本身的特点。
• 若图像中具有相同颜色的图像块越大，图像块数目越少，则压缩比就越高，反之，压缩比就越小。

图像游程编码举例：

从上例可看出，游程编码适合于对二值图像的编码，如果图像是由很多块颜色或灰度相同的大面积区域组成的，采用游程编码可以达到很大的压缩比。

通常，为了达到比较好的压缩效果，一般不单独使用游程编码，而是和其他编码方法结合使用。如：在 JPEG 中，就综合使用了游程编码以及哈夫曼编码。