常用信源编码方法之游程编码课件

常用信源编码方法常用信源编码方法 游程游程编码编码信息理论与编码工程技术学院工程技术学院电气与电子信息系电气与电子信息系郭堃郭堃常用信源编码方法信息理论与编码工程技术学院Page 2课程简介课程简介 寻找信息传输过程中的共同规律，以寻找信息传输过程中的共同规律，以提高信息传输的提高信息传输的有效性有效性、可靠性可靠性和和保密性保密性，使达到信息传输系统最优化。使达到信息传输系统最优化。Page 2课程简介 寻找信息传输过程中的共同规律本次课内容概要本次课内容概要Page 3信源编码信源编码游程编码游程编码1、游程编码在传真文件中的应用2、MH编码游程编码的不足及发展游程编码的不足及发展本次课内容概要Page 3第一节信源编码游程编码1、游程 莫尔斯电码莫尔斯电码Page 4一、信源编码一、信源编码 莫尔斯电码Page 4一、信源编码信源编码简介信源编码简介 信源编码就是把信源符号变换到码符号的一种映射。编码的目的就是将原始数据进行压缩，提高通信效率。信源编码分为：无失真压缩编码和限失真压缩编码。Page 5信源编码简介 Page 5数据压缩原理数据压缩原理 根据信源的统计特性，用短码来代替频繁出现的原始数据，从而达到压缩的目的。常见的信源编码方法常见的信源编码方法“游程编码”、“霍夫曼编码”、“字典编码”、“算术编码”等 Page 6数据压缩原理 Page 6简介简介游程编码又称“游程长度编码”、“运行长度编码”或“行程编码”，该编码属于无失真压缩编码。主要应用在二值文件数据压缩：传真文件、二值图像压缩、音频信号压缩等 Page 7二、游程编码二、游程编码简介Page 7二、游程编码编码原理编码原理原始数据有一定的相关性，往往连续出现同样的消息，将同一个消息连续出现的序列称为游程。该游程可以用一个消息的样本和对于出现的次数来表示，译码时可以根据样本和数量进行数据恢复。基本编码格式：Page 8符号码 标识码 游程长度编码原理Page 8符号码标识码游程长度例如某数据片段：例如某数据片段：BBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUUBBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUU游程编码为：B#10X#9A#6U#13 原始数据共38个字符，编码后共14个字符。由此可见游程编码的符号序列长度远远少于原始信源符号序列长度。Page 9例如某数据片段：BBBBBBBBBBXXXXXXXXXAA1 1、游程编码在传真文件压缩中的应、游程编码在传真文件压缩中的应用用电话网编码器编码器扫描扫描译码器译码器打印打印Page 10原稿原稿打印稿打印稿1、游程编码在传真文件压缩中的应用电话网编码器扫描译码器打印Page 11二值图像 扫描后传真图像属于二值数据，在计算机中是用像素来表示，我们把一副图像细分成很多行，又把每行分为很多像素。像素只有两种取值：0表示背景（白色），1表示前景（黑色）。Page 11二值图像 扫描后传真图像属于 总共有55个白游程以及54个黑游程。如果每个游程用一个字节（8位）进行编码来提高效率。每个字节第一位表示黑白，剩下7个比特表示游程长度（0127）。109个游程总共需要872bit。Page 12例：下图是一幅1050黑白二值图像“Hi Mom”0011 01000011 01001000 00101000 0010Page 12例：下图是一幅1050黑白二值图像“Hi改进方法：改进方法：（1）黑白交替出现，规定第一游程为白，这样可省略符号码，只需对长度编码。（2）不同长度游程概率不同，对长度进行霍夫曼编码，大概率编短码，小概率编长码。（3）白游程长度一般都比黑游程长度大，可考虑分开编码。Page 13改进方法：Page 132 2、MHMH编码编码MH编码又叫修正的霍夫曼编码，是ITU向各国推荐使用的编码方案。先逐行游程编码，再进行霍夫曼编码。该方案是根据多个传真样本为概率统计依据而进行编码的。用途：用途：黑白二值文件传真的数据压缩Page 142、MH编码MH编码又叫修正的霍夫曼编码，是ITU向各国分辨度要求：分辨度要求：A4幅面文件(210mm297mm)有两种分辨度 （1）一页A4幅面有1188条扫描线，每条扫描线有1728个像素的扫描分辨率，约2.05M像素。（2）一页A4幅面有2376条扫描线，每条扫描线有1728个像素的扫描分辨率，约4.1M 像素。Page 15分辨度要求：A4幅面文件(210mm297mm)有两MHMH编码规范如下：编码规范如下：(1)黑白游程分别对应不同的码表；(2)游程长度在0 06363时，直接查表用相应的结尾码作为码字；(3）游程长度在646417281728范围内时，用组合码加上结尾码作为相应的码字；例如：例如：5 5个黑像素个黑像素 129 129个白像素个白像素=128+1 =128+1 Page 16游程长度游程长度白游程码字白游程码字黑游程码字黑游程码字0 00011010100110101000011011100001101111 10001110001110100102 20111011111113 31000100010104 4101110110110115 511001100001100116 61110111000100010游程长度游程长度白游程码字白游程码字黑游程码字黑游程码字6464110111101100000111100000111112812810010100100000110010000000110010002562560110111011011100000101101100000101101132032000110110001101100000001100110000001100113843840011011100110111000000110100000000110100448448011001000110010000000011010100000011010151251201100101011001010000001101100000000110110010010+00011110010+00011100110011结尾码码表结尾码码表063063组合码码表组合码码表641728641728MH编码规范如下：Page 16游程长度白游程码字黑游程(4)为保证收发同色，规定每行的第一个游程为白游程(长度可以为零)，每行用一个结束码(EOL)终止；EOL格式：000000000001，即11个“0”后1个“1”(5)在传输时，每页数据之前加一个结束码，每页尾部连续实用6个结束码。(6)填充码FILL：为了保证每个扫描行数据传输时间达到收发双方约定的最小传输时间，在长度不够的编码的结束码前插入合适的“0”序列。Page 17Page 17MHMH编码传送格式编码传送格式Page 18EOL 数据 EOL 数据 填充 EOL 数据 数据 EOL 数据 6个EOLTTT页首页首页尾页尾第第1行行第第2行行末行末行结尾码结尾码Page 18EOL 数据 EOL 数据 填充 例例 设某页传真文件中某一扫描行的像素点为：设某页传真文件中某一扫描行的像素点为：1717 (白白)5 5（黑）（黑）5555（白）（白）1010（黑）（黑）16411641（白）（白）101011 0011 01011000 0000100 010011010+00101010000000000001Page 191600+41 EOL 原一行为原一行为17281728个像素，用个像素，用“0”0”表示白，用表示白，用“l”l”表表示黑，需示黑，需17281728位二元码元。位二元码元。MHMH码只需用码只需用5454位二元码元，位二元码元，数据压缩比为数据压缩比为1728:541728:543232，压缩效率很高。，压缩效率很高。例 设某页传真文件中某一扫描行的像素点为：17(白)不足之处：不足之处：（1）游程编码属于变长编码，每个码字传送时间长短不一，需要大量的缓冲寄存器。（2）游程编码只能检错不能纠错，一般只适合优质的信道。（3）只适用于二值图像压缩。多元则需对游程码加以改进，配合其他编码算法来实现高效压缩。Page 20三、游程编码的不足及发展三、游程编码的不足及发展不足之处：Page 20三、游程编码的不足及发展基于游程编码的图像压缩技术的发展：基于游程编码的图像压缩技术的发展：1.1.黑白二值图像黑白二值图像MH编码一维压缩MR编码二维压缩JBIG编码带灰度二维压缩2.2.彩色多值图像彩色多值图像JPEG压缩技术通用图像压缩Page 21基于游程编码的图像压缩技术的发展：Page 21谢谢各位！谢谢各位！谢谢各位！