游程编码行程编码PPT课件.ppt

游程编码游程编码游程编码内容基本基本RCL方法分析方法分析二值图像的游程编码二值图像的游程编码连续色调图像的二维编码连续色调图像的二维编码 游程编码概念游程编码概念游程编码概念游程编码游程编码RCL: 又称又称“游程长度编码游程长度编码”、、“运行长度编码运行长度编码”或或“行程编码行程编码”，是一种统，是一种统计编码，该编码属于无损计编码，该编码属于无损压缩编码压缩编码 定义：定义：游程编码概念•游程长度游程长度RL ：简称游程，：简称游程，指的是由字符指的是由字符构成的数据流构成的数据流中各个字符重中各个字符重复出现而形成复出现而形成的字符的长度的字符的长度•RCL原理原理：用一个：用一个符号值或串长代替符号值或串长代替具有相同值的连续具有相同值的连续符号，使符号长度符号，使符号长度少于原始数据的长少于原始数据的长度只在各行或者度只在各行或者各列数据的代码发各列数据的代码发生变化时，一次记生变化时，一次记录该代码及相同代录该代码及相同代码重复的个数，从码重复的个数，从而而实现数据的压缩实现数据的压缩 基本RLC方法分析定义定义 就是在数据流中直接用（数据字符就是在数据流中直接用（数据字符X、串的位置、串的位置Sc、串的长度、串的长度RL））3个字符来给出上述个字符来给出上述3种信息。

种信息缺点缺点 用用Sc作为前缀的低效、原字符串中作为前缀的低效、原字符串中RL的长度的长度和出现频度不够显著导致不实用和出现频度不够显著导致不实用解决方法解决方法 在二值图像和连续色调图像中可以省去在二值图像和连续色调图像中可以省去Sc，这样，这样使得改进的使得改进的RCL在图像编码中得到了广泛的应用在图像编码中得到了广泛的应用二值图像的游程编码二值图像二值图像是指仅有黑（用是指仅有黑（用“1”代表）、白（用代表）、白（用“0”代代表）两个亮度值的图像可借助各种图像通信表）两个亮度值的图像可借助各种图像通信方式传输，最经典的通信方式是方式传输，最经典的通信方式是二值图像二值图像对不同的白长（白像素游程）和黑长（黑像素对不同的白长（白像素游程）和黑长（黑像素游程）按其出现概率的不同分别配以不同长度游程）按其出现概率的不同分别配以不同长度的码字实为霍夫曼码的一种具体应用实为霍夫曼码的一种具体应用二值图像二值图像RCL一种只按长度编码，效率低一种只按长度编码，效率低另一种对白长另一种对白长黑长分别编码（改进型霍夫曼编码黑长分别编码（改进型霍夫曼编码MHC）定定义义RCL两两种种方方式式二值图像的游程编码RL=0~63，，用一个相应用一个相应的的结尾码结尾码表表示（示（P59表表4.7）；）；（（1））RL=64~1728，用一个，用一个组合组合基干码基干码加一个加一个补充结尾码补充结尾码；；（（2））规定每行都从白规定每行都从白游程开始，若实游程开始，若实际扫描行由黑开际扫描行由黑开始，则需在行首始，则需在行首加零长度白游程；加零长度白游程；每行结束要加行每行结束要加行同步码同步码EOL。

3））一维一维MH编码规则：编码规则：二值图像的游程编码例题：设有一页文件其中某一扫描线上的像素点如图例题：设有一页文件其中某一扫描线上的像素点如图 所示求（（1）该扫描行的）该扫描行的MH编码；编码；（（2）编码后的比特总数；）编码后的比特总数；（（3）本编码行的数据压缩比本编码行的数据压缩比1）数据：）数据：75白白 5黑黑 9白白 18黑黑 1621白白 EOL码字码字 1101101000；；0011；；10100；；0000001000；；；； 000000000001（（2）将码字数一下，答案就是）将码字数一下，答案就是57 bit3）压缩前数据总比特：压缩前数据总比特：75+5+9+18+1621=1728 bit 所以数据压缩比：所以数据压缩比：1728:57=30.316:175个白5个黑9个白18个黑1621个白解：解：二值图像的游程编码75个白5个黑9个白18个黑1621个白根据编码的根据编码的3个规则，参考书中个规则，参考书中P59-60页的页的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所以答案为：所以答案为：●EOL：规则：规则(3)同步码同步码，查表可得为，查表可得为000000000001即为答案即为答案连续色调图像的二维编码前面介绍了二值图像的一维前面介绍了二值图像的一维MH编码，但对于多值或编码，但对于多值或连续色调图像，黑白游程已不适用，而基本连续色调图像，黑白游程已不适用，而基本RCL的的3元组也不能直接用。

元组也不能直接用引出前提引出前提JPEG标准的基本系统利用标准的基本系统利用Z型扫描，将二维量化系型扫描，将二维量化系统矩阵转换成了一维数组统矩阵转换成了一维数组ZZ（（k），数组的第一个元），数组的第一个元素素ZZ（（0）为）为直流系数直流系数DC（（在在4.2.3节截断霍夫曼编节截断霍夫曼编码中已经讨论过）码中已经讨论过）；；ZZ（（1））~ZZ（（63）元素为）元素为交流交流系数（系数（AC））编码原理编码原理JPEG将其联合编码表示为将其联合编码表示为“NNNNSSSS+尾码尾码”，，“NNNN”为当前非零值相对于前一个非零为当前非零值相对于前一个非零AC系数的系数的零游程计数，表示零游程计数，表示ZRL；这将；这将“NNNN/SSSS”组合为组合为一个新的前缀码，用二维霍夫曼编码即为一个新的前缀码，用二维霍夫曼编码即为AC系数系数编码表示形式编码表示形式AC编码表示形式编码表示形式连续色调图像的二维编码求求出差分值出差分值DIFFDIFF，查书中，查书中P52P52表表4.24.2即可得即可得前缀码前缀码（用（用标准的霍夫曼编码标准的霍夫曼编码）1)DC系数编码系数编码①①若若ZZZZ（（k k）为待编码的非零）为待编码的非零ACAC系数，系数，根据根据ZZZZ（（k k）的幅度范）的幅度范围由围由P60P60表表4.84.8查出查出尾码的位数尾码的位数B=SSSSB=SSSS，按以下可求得，按以下可求得尾码尾码：： (2)AC系数编码系数编码原码，若原码，若ZZZZ（（k k））≥0≥0反码，若反码，若ZZZZ（（k k））<0<0（（1 1））DCDC系数编码，得系数编码，得前缀码前缀码；；（（2 2））ACAC系数编码，得系数编码，得“NNNN/SSSS+“NNNN/SSSS+尾码尾码””；；（（3 3）综合（）综合（1 1）和（）和（2 2），可得二维编码结果。

可得二维编码结果二维编码规则二维编码规则②②由由ZZZZ（（k k）之间的零游程计数值得）之间的零游程计数值得ZRL=NNNNZRL=NNNN，，SSSSSSSS在在①①中已知，查表可得中已知，查表可得NNNN/SSSSNNNN/SSSS码字码字；；尾码尾码=ZZ=ZZ（（k k）的）的B B位位③③综合综合①①和和②②可得可得ACAC系数编码系数编码“NNNN/SSSS+“NNNN/SSSS+尾码尾码””若若ZZ=5，，B=3，得原码，得原码101若若ZZ=-2，，B=2，得反码，得反码01连续色调图像的二维编码二维编码注意事项二维编码注意事项▲▲若最后一个若最后一个““零零游程游程/ /非零值非零值””中只中只有零游程，则直接有零游程，则直接发送发送块结束码字块结束码字“EOB”“EOB”结束本块，结束本块，否则无需加否则无需加EOBEOB码▲▲一般情况一般情况NNNN=ZRL=0~15NNNN=ZRL=0~15若ZRL>15ZRL>15，则先用，则先用ZRL=16ZRL=16即即NNNN/SSSS=F/0NNNN/SSSS=F/0得到码得到码字字，再对，再对ZRL=ZRL-16ZRL=ZRL-16继继续编码，得到续编码，得到NNNN/SSSSNNNN/SSSS码字，结合尾码就可得码字，结合尾码就可得ACAC系数编码。

系数编码连续色调图像的二维编码例题：设某亮度图像块的量化系数矩阵按例题：设某亮度图像块的量化系数矩阵按Z形扫描得到：形扫描得到： K 0 1 2 3 4 5 6 7 8 9~30 31 32~63ZZ（（k）） 12 5 -2 0 2 0 0 0 1 0 -1 0 而其前一亮度块的量化而其前一亮度块的量化DC系数也为系数也为12，写出编码过程写出编码过程解解(1)DC系数编码系数编码—因为因为DIFF=0，查，查P52表得其码字即为表得其码字即为前缀码前缀码“00” (2)AC系数编码系数编码—①①第一个非零值第一个非零值ZZ(1)=5，查表得，查表得SSSS=3，根据规则得尾码为原码，根据规则得尾码为原码101；与；与ZZ(0)间无零系数，故间无零系数，故NNNN=0，，NNNN/SSSS=0/3查表码字查表码字100；；从而从而ZZ(1)=5的编码为的编码为“NNNN/SSSS+尾码尾码”即即100+101得得100101②②第二个非零值第二个非零值ZZ(2)=-2，，SSSS=2，尾码为反码，尾码为反码01；又与；又与ZZ(1)无零系无零系数，所以数，所以NNNN/SSSS=0/2查表得码字为查表得码字为01；从而；从而ZZ(1)~ZZ(2)编码为编码为0101。

③③ZZ(3)~ZZ(4)编码为编码为1101110 ④④ZZ(5)~ZZ(8)编码为编码为1110101连续色调图像的二维编码例题：设某亮度图像块的量化系数矩阵按例题：设某亮度图像块的量化系数矩阵按Z形扫描得到：形扫描得到： K 0 1 2 3 4 5 6 7 8 9~30 31 32~63ZZ（（k）） 12 5 -2 0 2 0 0 0 1 0 -1 0 而其前一亮度块的量化而其前一亮度块的量化DC系数也为系数也为12，写出编码过程写出编码过程⑤⑤ZZ(31)=-1，查表得，查表得SSSS=1，尾码为反码，尾码为反码0；由于；由于NNNN=30-9+1=22>15，故先编，故先编ZRL=16，，NNNN/SSSS=F/0查表得码字；此后查表得码字；此后NNNN=22-16=6<15再编码，再编码，NNNN/SSSS=6/1查表得码字为查表得码字为1111011；所以；所以ZZ(9)~ZZ(31)编码为⑥⑥此后无非零值，最直接用一个此后无非零值，最直接用一个EOB结束本块结束本块，查表得码字为，查表得码字为1010。

3)综合前面综合前面(1)和和(2)，可知该图像块的编码为，可知该图像块的编码为 00 100101 0101 1101110 1110101 1010(4)原始图像块要用原始图像块要用8*8*8=512位，压缩后为位，压缩后为49位，压缩比为位，压缩比为10.45:1游程编码总结游程编码游程编码RCL是一种熵编码是一种熵编码1）RCL仍需与其他前缀码结合才有望达到更仍需与其他前缀码结合才有望达到更好的效果这种方法对于二值图最有效好的效果这种方法对于二值图最有效2）RCL仍是变长码，有其固有的缺点，即需仍是变长码，有其固有的缺点，即需要较大容量的缓冲和较低误码的优质信道要较大容量的缓冲和较低误码的优质信道3）　　谢　　谢！谢　　谢！。