游程编码课程设计说明书

******************实践教学*******************兰州理工大学计算机与通信学院2014年春季学期通信系统仿真训练题目：基于游程编码的信源编/解码系统设计及仿真专业班级：通信2011级3班姓名：黄亮学号：11250309指导教师：晏燕成绩：目录TOC\o"1-2"\h\u4253摘要 摘要本课题主要是针对于游程编码信源编解码的数据压缩算法的设计与实现，游程编码非常简单，编码、解码速度快，应用广泛。游程编码是针对于二元序列的一种编码方法，对于二值图像而言是一种具有高压缩比的无损数据压缩技术，它是应用游程编码的原理对二值图像进行数据压缩的编码技术，对连续的黑、白像素数(游程)以不同的码字进行编码。游程编码是一种简单的非破坏性资料压缩法，其好处是加压缩和解压缩都非常快，其方法是计算连续出现的资料长度压缩之，其缺点是对于不重复的资料反而加大容量且需大量的缓冲和优质信道来实现。游程编码在MATLAB中的实现主要体现在对二值图像的压缩上，一张二值图像其实就是两个灰度值所组成的一个图像矩阵，而设计程序首先就要考虑到遍历图像所有的灰度值，并按照游程的原理，即（灰度值，游程宽度）的形式依次记录。由于纯粹的二值图较少的原因，可以先将灰度图转换为二值图进行压缩，在设计的过程中，压缩矩阵的初始化与终止位置是尤为重要的，即游程宽度在编码之前是置为1的（其中也有MATLAB的下标不同于其他高级语言是从0开始的原因），并且在游程宽度初始化时，也要将此矩阵中第一个灰度值给相应的数组向量。在压缩过程中，只需要不断将游程宽度与灰度值所在的数组向量累加就行，而到了将截止时，应该将最后一个灰度值手动赋给灰度值的数组向量中，这是因为在循环体中不能出现超出下标值的值，所以循环次数一般定为图像矩阵的像素数-1，这样循环截止时还剩下最后一个灰度值没有被循环体被遍历上，因而需要手动将之添加进去。为了反映游程编码后的成效，可以绘制一个以游程序列为横轴，游程宽度为竖轴的函数图像，从此图像中也可以看出一幅二值图中哪些地方的灰度值较为集中。而解压缩，其实就是一个压缩的逆过程，同样地也要注意遗漏的问题。本文首先简要介绍了信源编码的原理，然后重点介绍游程编码的原理和实现技术，对游程编码技术做了较为全面的研究。包括游程压缩过程、数据压缩、解压缩过程，并给出了相应的二值图像游程编码MATLAB仿真程序，一般字符进行游程压缩的MATLAB仿真程序以及附录了一段压缩灰度图像的仿真程序以用来对比验证。关键字：信源编码压缩游程编码MATLAB

1.信源编码1.1信源编码简介编码实质上就是对信源的原始符号按一定规则进行的一种变换。编码可分为信源编码和信道编码。由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体的说就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的基本途径有两个：使序列中的各个符号尽可能地相互独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。既然信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。当然，这些都是广义的信源编码。一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个： ①使序列中的各个符号尽可能地互相独立；②使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性，后者称为概率均匀化。信源编码的一般问题可以表述如下：若某信源的输出为长度等于M的符号序列集合式中符号A为信源符号表，它包含着K个不同的符号，A={ɑk|k=1,…,K}，这个信源至多可以输出KM个不同的符号序列。记‖U‖=KM。所谓对这个信源的输出进行编码，就是用一个新的符号表B的符号序列集合V来表示信源输出的符号序列集合U。若V的各个序列的长度等于N，即式中新的符号表B共含L个符号，B={bl|l=1,…,L}。它总共可以编出LN个不同的码字。类似地,记‖V‖=LN。为了使信源的每个输出符号序列都能分配到一个独特的码字与之对应，至少应满足关系‖V‖=LN≥‖U‖=KM或者N/M≥logK/logL。假若编码符号表B的符号数L与信源符号表A的符号数K相等，则编码后的码字序列的长度N必须大于或等于信源输出符号序列的长度M；反之，若有N=M，则必须有L≥K。只有满足这些条件，才能保证无差错地还原出原来的信源输出符号序列(称为码字的唯一可译性)。可是，在这些条件下，码字序列的每个码元所载荷的平均信息量不但不能高于，反而会低于信源输出序列的每个符号所载荷的平均信息量。这与编码的基本目标是直接相矛盾的。下面的几个编码定理，提供了解决这个矛盾的方法。它们既能改善信息载荷效率，又能保证码字唯一可译。1.2信源编码的理论基础信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；将信源消息分成若干组，即符号序列Xi,Xi=(X1,X2…Xl…XL),序列的每个符号取自符号集A，Xl∈{a1,a2,„,ai,„an}。而每个符号序列Xi依照固定的码表映射成一个码字Yi，这样的码称为分组码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。如图2-1所示的信源编码器，如果信源输出的符号序列长度为1，即信源符号集源概率空间为一元信道是常用的一种信道，他的信道基本符号集为{0，1}。若将信源X通过一个二元信道传输，就必须把信源符号xi变成符号组成的码字序列，即编码。可用不同的码字符号序列，如表1.2.1所示。表1.2.1信源符号Xi信源符号出现概率p(xi)码表信源符号Xi信源符号出现概率p(xi)码表码1码2码1码2X1P(X1)000X3P(X3)10001X2P(X2)0101X4P(X4)11111一般情况下，码可分为两类：一类是固定长度的码，码中所有码字长度都相同，如表1.2.1中的码就是定长码。另一类是可变码，码中的码字长短不一，如表中码2就变长码。限失真信源编码定理：是连续信源/模拟信号编码的基础。信息率失真函数R(D)是满足保真度准则R(D)时所必须具有的最小信息率，在进行信源压缩之类的处理时，R(D)就成为一个界限，不能让实际的信息率低于R(D)。把相关的结论用定理的形式给出，即限失真信源编码定理，也就是通常所说的香农第三编码定理。定义：设离散无记忆平稳信源的信息率失真函数为R(D)，只要满足R<R(D)，当信源系列长度L足够长时，一定存在一种编码方法，其译码失真小于或等于D+ε，其中ε是任意小的正数；反过来，若R<R(D)，则无论采用什么样的编码方法，其译码失真必大于D。该定理包含两部分：R>R(D)的情形称为正定理，R<R(D)的情形称为逆定理。该定理是对离散无记忆信源给出的，对于连续无记忆平稳信源有类似结论。另外，该定理与香农第二编码定理（即信道编码定理）一样，只是码的存在性定理。正定理告诉我们，R>R(D)时，译码失真小于或等于D+ε的码肯定存在，但定理本身并未告知码的具体构造方法。一般来说，要找到满足条件的码，只能用优化的思路去寻求，迄今为止，尚无合适的系统编码方法来接近香农给出的界R(D)。反定理告诉我们，R<R(D)时，译码失真必大于D，肯定找不到满足条件的码，因此用不着浪费时间和精力。在实际应用中，该定理主要存在以下两大类问题：第一，符合实际信源的R(D)函数计算相当困难。首先：对信源的统计特性要有确切的数学描述。其次：失真测度要符合主关实际，例如可以采用方差来表示平均失真度，但是对于图像编码来说，均方差小的方法，人们视觉感到失真较大。所以，人们采用主观观察来评价编码方法的好坏。所以，这点是比较困难。第二，即便求得了符合实际的信息率失真函数，还需要研究采用何种实用的最佳编码才能达到R(D)。第三：即便前两条得到满足，但是R(D)函数计算还是相当困难（数学）。总结起来，香农信息论的三个基本概念——信源熵、信道容量和信息率失真函数，都是临界值，是从理论上衡量通信能否满足要求的重要界限。对应这三个基本概念的是香农的三个基本编码定理——无失真信源编码定理、信道编码定理和限失真信源编码定理，分别又称为香农第一、第二和第三编码定理，或第一、第二、第三极限定理。这是三个理想编码的存在性定理。信源编码的基础是信息论中的两个编码定理：无失真编码定理和限失真编码定理。前者是可逆编码的基础。可逆是指当信源转换成代码后，可以从代码无失真地恢复原信源符号。无失真编码或可逆编码只适用于离散信源。信源编码定理出现后，编码方法就趋于合理化。本章讨论离散信源无失真编码，从无失真编码定理出发，重点讨论以香农码，费诺码，哈夫曼码和算术码为代表的最佳码。

1.3信源编码的分类及作用信源编码的分类：离散信源编码：独立信源编码,可做到无失真编码；连续信源编码：独立信源编码,只能做到限失真信源编码；相关信源编码：非独立信源编码。编码的作用：信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。常见的信源编码方式：霍夫曼编码霍夫曼编码（HuffmanCoding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。也称“哈夫曼编码”，“赫夫曼编码”。1952年，DavidA.Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文。在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。算术编码算术编码是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分区为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足（0.0≤n<1.0）的小数n。在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。例:对一个简单的信号源进行观察，得到的统计模型如下：60%的机会出现符号中性20%的机会出现符号阳性10%的机会出现符号阴性10%的机会出现符号数据结束符.(出现这个符号的意思是该信号源'内部中止'，在进行数据压缩时这样的情况是很常见的。当第一次也是唯一的一次看到这个符号时，解码器就知道整个信号流都被解码完成了。)算术编码可以处理的例子不止是这种只有四种符号的情况，更复杂的情况也可以处理，包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为上下文。比如在英文文档编码的时候，例如，在字母Q或者q出现之后，字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。不管编码器使用怎样的模型，解码器也必须使用同样的模型。一个简单的例子以下用一个符号串行怎样被编码来作一个例子：假如有一个以A、B、C三个出现机会均等的符号组成的串行。若以简单的分组编码会十分浪费地用2bits来表示一个符号：其中一个符号是可以不用传的（下面可以见到符号B正是如此）。为此，这个串行可以三进制的0和2之间的有理数表示，而且每位数表示一个符号。例如，“ABBCAB”这个串行可以变成0.011201（base3，即0为A,1为B,2为C）。用一个定点二进制数字去对这个数编码使之在恢复符号表示时有足够的精度，譬如0.001011001(base2)–只用了9个bit，比起简单的分组编码少（1–9/12）x100%=25%。这对于长串行是可行的因为有高效的、适当的算法去精确地转换任意进制的数字。编码过程的每一步，除了最后一步，都是相同的。编码器通常需要考虑下面三种数据：下一个要编码的符号当前的区间（在编第一个符号之前，这个区间是[0,1）,但是之后每次编码区间都会变化)模型中在这一步可能出现的各个符号的概率分布（像前面提到的一样，高阶或者自适应的模型中，每一步的概率并不必须一样）编码器将当前的区间分成若干子区间，每个子区间的长度与当前上下文下可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为在下一步编码中的初始区间。游程编码游程编码（RLE，run-lengthencoding），又译行程长度编码，又称变动长度编码法（runcoding），在控制论中对于二值图像而言是一种编码方法，对连续的黑、白像素数（游程）以不同的码字进行编码。游程编码是一种简单的非破坏性资料压缩法，其好处是加压缩和解压缩都非常快。其方法是计算连续出现的资料长度压缩之，其缺点是对于不重复的资料反而加大容量。后文有比较详细的介绍，这里不再赘述。1.4信源编码的历史最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。另外，在数字电视领域，信源编码包括通用的MPEG—2编码和H.264（MPEG—Part10AVC）编码等相应地，信道编码是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力。

2.游程编码2.1游程长度游程长度RL(Run-Length)，简称游程或游长，指的是由字符(或信号取样值)构成的数据流中各个字符重复出现而形成的字符的长度。如果给出了形成串的字符，串的长度以及串的位置，就能恢复出原来的数据流，游程长度编码(RLC)就是用二进制码字给出这些信息的一类方法。2.2游程编码算法游程编码的基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“游程”，游程编码因此而得名），使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L(0)和L(l)。“0”游程和“l”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2，3，„，直到无限。将任何(二元)序列变换成一一对应的游程长度序列，再按哈夫曼编码或其他方法处理以达到压缩码率的目的。游程长度编码的主要思想是将一个相同值的连续申用其值和申长(重复的个数)的数对二元组来替代．例如，在图像编码中，可以定义沿特定方向上具有相同灰度值的相邻像素为一轮，其延续的长度称之为延续的行程，即游程．游程终点位置由前一游程终点的相对距离确定，这样就可以由灰度游程串来表示图像数据．例如，若沿水平方向有一串M个像素具有相同的灰度N，则按游程长度编码后，只传递两个值(N，M)就可以代替这M个像素的M个灰度值NJ简单来说，游程长度编码的主要任务是统计连续相同字符的个数，解码时要根据字符及连续相同字符的个数，恢复原来的数据。游程编码记录方式有两种：①逐行记录每个游程的终点列号：②逐行记录每个游程的长度（像元数）。如有栅格图形如下：AAABBACCCA第一种方式记为：A,3，B,5A,1，C,4，A,5第二种就记作：A,3，B,2A,1，C,3，A,12.3游程编码特点游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优质的信道。此外，编程长度可以从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改进。一般情况下游程长度越长，其概率越小，这在以前的计算中也可以看见，而且将随着长度的增大渐进向零。对于小概率的码字，其长度为达到概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。再按哈夫曼编码或其他方法处理以达到压缩码率的目的。游程长度编码在游程加密时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存贮容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。2.4游程编码算法示例例如：5555557777733322221111111行程编码为：（5，6）（7，5）（3，3）（2，4）（1，7）。可见，行程编码的位数远远少于原始字符串的位数。例如有一张图片，以W表示白色，B表示黑色：WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW使用这个压缩法便可得到12W1B12W3B24W1B14W更先进的算法如DEFLATE都是基于将重复出现的资料“压缩”的想法。常见的游程编码格式包括TGA，Packbits，PCX以及ILBM。游程长度编码是一种无损数据压缩，非常适合基于调色板的图标图像。但是它并不适用于连续色调图像的压缩，例如日常生活中的照片；JPEG格式是一个反例，JPEG在对图像进行转换和离散化后有效地使用了游程长度压缩。游程长度编码还用于传真机（并和其他技巧一起组成了修改过的huffman编码）。相对而言，游程长度编码是比较有效的，因为传真的文档主要是黑白的（二值文档）。

3.基于游程编码的信源编/解码的MATLAB仿真设计3.1压缩前的准备在压缩之前，须将图像转换为灰度图，此程序作用即将输入路径的三维彩色RGB图像转换为二维的灰度图像。path=input('请输入要转换的图像路径\n','s');image1=imread(path);%读入图像[M,N]=size(image1)%计算图像行列大小figure,imshow(image1);title('原图像');image2=rgb2gray(image1);%转换为灰度图像[M,N]=size(image2)figure,imshow(image2);title('灰度图');path1=input('请输入要存储的图像路径\n','s');imwrite(image2,path1);%存为灰度图像效果如下：图3.1彩色图转换为灰度图本程序运行之后，要在MATLAB命令窗口中输入将要转换的图像路径，这里我的彩色图像在“D:\tu3.jpg”，读取图像后可得出当前图像的矩阵行列大小为154*615，利用rgb2gray函数可以将当前彩色图像转换为灰度图像，为了方便之后的压缩，此处将转换后的图像用imwrite命令将之存储在“D:\tu31.jpg”，并能显示转换后的图像行列大小为154*205，可以知道，转换后的图像比之原图像缩小了3倍，这正是因为彩色图像一个像素点由RGB三个灰度值描述，而灰度图像一个像素点只由一个灰度值表示，因而彩色图像经转换后会变为只有黑白程度不同的图像，这就达到了为下一步转换为二值图像的前提条件，即图像矩阵中一个元素表示一个像素的灰度值。3.2进行游程编码读取灰度图像路径，先转换为二值图然后进行游程编码，得出压缩率。(也可将转换二值图的程序单列出来)path=input('请输入要读取的灰度图像路径\n','s');image1=imread(path);%读入图像[M,N]=size(image1);%计算图像行列大小figure,subplot(211);imshow(image1);%显示原图像title('原图像');IM1=image1(:);%将图像转换为一维数组IM1length=length(IM1);%计算转换为一维数组的长度fori=1:1:IM1length%for循环，目的在于转换为二值图像ifIM1(i)>=127%灰度值大于127转换为255，反之为0IM1(i)=255;elseIM1(i)=0;endendimage2=reshape(IM1,M,N);%重组图像subplot(212),imshow(image2);%显示重组后的图像title('手动转换后的二值图像');%{level=graythresh(image1);%获取二值图阈值imgbw=im2bw(image1,level);%利用内部函数转换为二值图subplot(222);imshow(imgbw);%显示内部函数转换出的二值图像title('内部函数转换的图像');%}j=1;counter(j)=1;%游程序列码初始化forz=1:1:(length(IM1)-1)ifIM1(z)==IM1(z+1)counter(j)=counter(j)+1;%每遇相等的灰度值，将当前的重合度加1elsedata(j)=IM1(z);%否则，将当前的序列码加1j=j+1;counter(j)=1;endenddata(j)=IM1(length(IM1));%Comp=[data;counter]%查看编码后的矩阵%{counterlength=length(counter);%编码后的序列长度s=1:1:counterlength;figure,plot3(s,counter(s),data(s));%编码后的序列函数关系title('编码后的序列函数关系图（三维图）');xlabel('游程序列码');ylabel('像素重合度');zlabel('灰度值');gridon;%}counterlength=length(counter);%编码后的序列长度s=1:1:counterlength;figure,plot(s,counter(s));title('压缩后的序列函数关系图');xlabel('游程序列码');ylabel('游程宽度');gridon;display('压缩率');CRatio=counterlength*2/IM1length%压缩率%还原数组k=1;form=1:1:counterlengthforn=1:1:counter(m)IM2(k)=data(m);k=k+1;endendimage3=reshape(IM2,M,N);%重组数组为二值图figure,imshow(image3);title('解压后的图像');

3.3算法流程图3.3解压流程图图3.2压缩流程图开始将原图像矩阵重构为1*IM1length的列向量IM1初始化j=1，z=1IM1(z)==IM1(z+1)counter(j)++data(j)=IM1(z)j++,z++counter(j)=1输入图像路径并读取图像输出压缩后矩阵Comp=[data;counter]结束否是Z=IM1length是否开始读入counter,data初始化k=1,m=1,n=1m<counterlengthn<counter(m)IM2(k)=data(m)k++将列向量IM2重构为原图像结束否是图3.3解压流程图图3.2压缩流程图开始将原图像矩阵重构为1*IM1length的列向量IM1初始化j=1，z=1IM1(z)==IM1(z+1)counter(j)++data(j)=IM1(z)j++,z++counter(j)=1输入图像路径并读取图像输出压缩后矩阵Comp=[data;counter]结束否是Z=IM1length是否开始读入counter,data初始化k=1,m=1,n=1m<counterlengthn<counter(m)IM2(k)=data(m)k++将列向量IM2重构为原图像结束否是是否本程序将选择图像的权利交给用户，用户可以通过输入图像在计算机中的路径去读取将要压缩的图像，程序将用户输入的路径赋给path，并通过imread(path)命令读取图像。图像矩阵会存储在变量image1中，再通过image1(:)命令将图像矩阵转换为长度为IM1length的列向量IM1。初始化j,z两个变量为1，建立一维矩阵counter并初始化counter(j)，此矩阵将接收压缩中所得的灰度值的各个游程宽度，建立一维矩阵data，此矩阵将接收压缩中所得灰度值序列。接着遍历整个IM1的数值，用if语句判断IM1(z)是否与IM1(z+1)相等，即判断相邻灰度值是否相等，若是相等，则初始化data(j)并将此灰度值赋给data(j)，以及将counter(j)累加，如果相邻灰度值并不相等，则使j加1，即进入下一次游程的压缩。当遍历完整个IM1数值后，就可以将data,counter合并为一个二维矩阵Comp，此矩阵即压缩后得到的码字。对比原图像矩阵的长度，就可以得到压缩率CRatio。解压流程：读取data,counter两个一维矩阵，初始化k，m，n为1，求得counter矩阵的长度counterlength，并遍历整个counter矩阵中的数值，可以从压缩流程中知道counter(m)即代表各个灰度值的宽度，data(m)代表相应的灰度值，两相组合就能知道整个图像矩阵的灰度序列，因而初始化一个一维矩阵IM2，并在循环体中赋值IM2(k)=data(m)，即可得到一个包含原图像矩阵所有灰度值的矩阵IM2，将IM2用reshape(IM2,M,N)命令重组此矩阵为一个二维的矩阵，其中M,N是求得的原图像的行列大小，这样得出的矩阵即原图像的二值矩阵，用imshow命令显示出来即可对比。无论压缩还是解压，核心都在于循环体中遍历数值时的赋值，将矩阵的数值打散并按照相应的顺序排列，就能得到相应的压缩效果。此程序也可以直接遍历原图像的二维矩阵，不过计算量会变大，鉴于在MATLAB中转换一维矩阵的简单易行，完全可以将原图像矩阵转换为一维矩阵再进行压缩，这样的效率无疑要高上许多。另外，针对二值图像时，可以考虑只统计其中一个灰度值，这样会减少压缩过程的繁琐，在此实例中为了原理的阐述清楚，将两个灰度值都进行了统计。游程编码本身可以对任何数值序列进行统计，不过只有对数值重复率较高的序列压缩较理想，尤以二值图为最，读者可以通过附录中的灰度图像的游程编码程序进行对比。

3.4程序运行效果及分析图3.4灰度图转换为二值图将灰度图像转换为二值图像是必要的，游程编码在灰度图像中的应用并不广泛（可用附录中的代码进行实验对比），因为灰度值有256个，导致其相邻的重复灰度值并不会太紧密，特别是在一些着色较讲究的灰度图像中，灰度的变化十分细微，如本实例的原图像，在明暗值上有相当丰富的表现，即代表着此图像矩阵相邻数值的重复概率较小，而事实上，如果就原图像这样的灰度图像用游程编码压缩后，得出的压缩率在160%左右，即比原来还大了不少，自然不能称之为压缩了，其他灰度图像虽说并不如本实例中的图像明暗丰富，但也相差不多，压缩后的大小都在原图像之上。本程序的二值转换是将灰度图像矩阵中，大于127的灰度值全部重构为255，而小于或者等于127的灰度值全部重构为0，这样转换后，图像就会变得黑白分明，整张图像中只会存在黑白两种颜色，图像矩阵中也只会存在0,255两种数值，即所谓的“二值图”。为了后面表示函数关系的方便，这里也一并将二维的图像矩阵转换为一维的列向量IM1，即将图像矩阵按列的顺序组成一个新的一维矩阵。 图3.5编码后游程宽度关于序列的函数图这一步骤要点在于实现压缩，此程序中将变量IM1作为一维的列向量，并用for,if等命令将IM1中的值进行统计，得出data与counter两个新的一维矩阵，前者是代表冗余的数值，后者则表示冗余度。例如IM1=[1,1,2,3,3,3,1]，那么data=[1,2,3,1]，counter=[2,1,3,1]，而事实上IM1中只有0与255两种数值，这就使统计的难度大大降低。此处可以再进一步简化，只将0或者255其中一个值的冗余度求得，另一个值的冗余度自然就可得出，不过出于两种数值都表现出来较为全面明了的考虑，这里是将两者做了统计，最后的压缩率高达5.19%，这种高压缩率正好说明了游程编码在二值图中强大的优势。压缩的原理较为简单，即先为data,counter两个矩阵初始化，然后遍历整个IM1即图像矩阵的灰度值，相邻灰度值相等，则counter累加1，并由data记录当前灰度值，若相邻灰度值不同，则使counter初始化计数，data初始化其中数值，如此反复，最后就能得出data中的灰度值，与counter的冗余度。不难看出，两上一维矩阵的长度是相等的，于是压缩率便可由此两矩阵中的任何一个矩阵的长度的2倍比上原二值图像的大小得出。由上图也可以看出此二值图像最高的冗余度在140左右，这也是压缩率高的原因。 图3.6解压后的二值图 图3.7程序中的各变量值

3.4游程编码的简单实现以上是游程编码常用的二值图编码压缩，其原理是将一个数矩阵转换为列向量并对列向量中重复的数值进行统计，最后得出较为精简的数矩阵，重复的数越紧密，压缩率也就越大。下面由手动输入的一组数矩阵实现的MATLAB仿真代码:F=input('请输入行程码\n');j=1;counter(j)=1; %游程序列码初始化forz=1:1:(length(F)-1)ifF(z)==F(z+1)counter(j)=counter(j)+1;%每遇相等的灰度值，将当前的重合度加1elsedata(j)=F(z);%否则，将当前的序列码加1j=j+1;counter(j)=1;endenddata(j)=F(length(F));disp('编码后的码字');Comp=[data;counter]%输出编码后的行程码disp('压缩率')CRatio=length(Comp)*2/length(F)counterlength=length(counter);%编码后的序列长度k=1;form=1:1:counterlengthforn=1:1:counter(m)G(k)=data(m);k=k+1;endenddisp('解压后的码字');G现输入一列向量如:[1,1,1,3,3,3,3,2,1,1,2,2,2,2,2,3,3,3,4,4,4,5,5,5,5]那么经压缩后应得到：1321234534125334压缩率为64%，可见游程编码对重复率较高的码字序列拥有较为优秀的压缩效率。

其效果如下：图3.8简单游程编码实例从图中不难看出，对于一维矩阵[1,1,1,3,3,3,3,2,1,1,2,2,2,2,2,3,3,3,4,4,4,5,5,5,5]的游程编码，统计其各个数值的重复度（即游程宽度），可以得出压缩矩阵Comp为[(1,3),(3,4),(2,1),(1,2),(2,5),(3,3),(4,3),(5,4)]。得出压缩率为64%，可见对于有着不同元素的矩阵压缩并不高（相对于二值图的压缩率）。

设计总结此次课程设计是对于信源编码中较为简单的游程编码进行MATLAB的仿真设计。游程编码的原理是利用压缩资料的重复冗余进行简化，整个压缩过程即一个遍历数矩阵并统计重复数值将重复度与重复的数值分别存入两个行向量中，然后将两个行向量合为一个二维数组，即最后的压缩矩阵的过程，对比原矩阵与压缩矩阵的大小，即可得出压缩率。而解压缩过程即压缩过程的逆运行，即将压缩矩阵中的元素按原图像像素下标值的顺序排列。经过此次课程设计，让我理解了信源编码的基本原理，尤其是游程编码的原理，虽然简单，但在做MATLAB仿真设计却遇到诸多问题，主要在于两个方面，一是许多绘图命令的不熟悉，显示不出相应效果的图像，二是虽然明白原理，却难以用代码准确地表达出来。一番查阅资料与熟悉命令后，才能用MATALB真正实现图片或者数矩阵的压缩。可见理论与实践必须同时进行，否则只会眼高手低，不能真正解决实际问题。此次课程设计总体成功，除必要的要求外，我还另外设计了两段压缩灰度图像与彩色图像的代码，（附录中有压缩灰度图像的代码）在以验证游程编码在二值图像中的优势。附录对于灰度图像的压缩基于游程编码的MATLAB实现：path=input('请输入要读取的灰度图像路径\n','s');image1=imread(path);%读入图像[M,N]=size(image1);