游程编码文档.doc

游程编码 翟文婕 张亚群 陈红 古明春 游程编码RCL：又称“游程长度编码”，“运行长度编码”，或“行程编码”，是一种统计编码，该编码啊属于无损编码（指使用压缩后的数据进行重构（或者叫做还原，解压缩），重构后的数据与原来的数据完全相同）。对于二值图有效。在游程编码中，游码长度RL，简称游程，指由字符串构成的数据流中各个字符重复出现而形成的字符长度。 一．其编码的基本原理（RCL原理）如下： 用一个符号值或串长代替具有相同值的连续符号，使符号长度少于原始数据的长度。数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字串代替这些连续符号，可大幅度减少数据量。 需要注意的是：游程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。 二．游程编码算法 一般游程编码有两种算法，一种是使用1的起始位置和1的游程长度，另一种是只使用游程长度，如果第一个编码值为0，则表示游程长度编码是从0像素的长度开始。两种方法各有优缺点：前一种存储比第二种困难，因此编程也比较复杂。而后一种需要知道第一个像素值，故压缩编码算法中需给出所读出的图的第一个像素值。 三．基本RLC方法分析: 基本RLC方法就是在数据流中直接用（数据字符X、串的位置Sc、串的长度RL）3个字符来给出上述3种信息。但是用Sc作为前缀的低效、原字符串中RL的长度和出现频度不够显著。导致不实用。所以我们在实际使用过程中在二值图像和连续色调图像中可以省去Sc，这样使得改进的RCL在图像编码中得到了广泛的应用。 四．具体编码, 以二值图像的游程编码为例 接下来就以二值图像的游程编码为例具体介绍一下游程编码算法 二值图像指是指仅有黑（用“1”代表）、白（用“0”代表）两个亮度值的图像。可借助各种图像通信方式传输，最经典的通信方式是传真。在对他编码时要对不同的白长（白像素游程）和黑长（黑像素游程）按其出现概率的不同分别配以不同长度的码字。实为霍夫曼码的一种具体应用。编码方式有两种，一种只按长度编码，效率低。另一种对白长黑长分别编码（改进型霍夫曼编码MHC）。 一维MH编码规则： 1.RL=0~63，用一个相应的结尾码表示 2. RL=64~1728，用一个组合基干码加一个补充结尾码； 3. 规定每行都从白游程开始，若实际扫描行由黑开始，则需在行首加零长度白游程；每行结束要加行同步码EOL 例题：设有一页传真文件其中某一扫描线上的像素点如图所示。求 （1）该扫描行的MH编码； （2）编码后的比特总数； （3）本编码行的数据压缩比 解： (分析)根据编码的3个规则，参考MH码表： ●75个白：RL=75，用规则(2)。组合基干码为64（白）对应的11011；补充结尾码为75-64=11（白）所对应的01000。所以答案为：1101101000。 ●5个黑：RL=5，用规则(1)。结尾码为5（黑）对应的0011。即为答案。 ●9个白：规则(1)。结尾码为9（白）对应的10100。即为答案。 ●18个黑：规则(1)。结尾码为18（黑）对应的0000001000。即为答案。 ●1621个白：规则(2)。组合基干码为1600（白）对应的010011010；补充结尾码为1621-1600=21（白）所对应的0010111。所以答案为：0100110100010111。 ●EOL：规则(3)。同步码，查表可得为000000000001。 答案 （1）数据：75白 1101101000 ； 5黑 0011； 9白 10100 ； 18黑 0000001000； 1621白 0100110100010111； EOL 000000000001； （2）将码字数一下，答案就是57 bit。 （3）压缩前数据总比特：75+5+9+18+1621=1728 bit。 所以数据压缩比：1728:57=30.316:1