游程编码的分析与实现.docx
《游程编码的分析与实现.docx》由会员分享，可在线阅读，更多相关《游程编码的分析与实现.docx（10页珍藏版）》请在冰点文库上搜索。
游程编码的分析与实现
课程设计任务书
专业：
通信工程
课程设计名称：
信息论与编码课程设计
设计题目：
游程编码的分析与实现
一．设计目的
1、深刻理解信源编码的基本思想与目的；
2、理解游程编码方法的基本原理与特点；
3、提高综合运用所学理论知识独立分析和解决问题的能力；
4、使用MATLAB或其他语言进行编程。
二．设计内容
读入一个图像，将每一个不同游程（不同颜色的像素块）的起始坐标和灰度值记录下来，以达到压缩图像存储空间的目的。
三．设计要求
通过编码前后数据大小的对比显示压缩效果。
四．设计条件
计算机、MATLAB或其他语言环境
五．参考资料
[1]曹雪虹，张宗橙.信息论与编码.北京：
清华大学出版社，2007.
[2]王慧琴.数字图像处理.北京：
北京邮电大学出版社，2007.
指导教师（签字）：
教研室主任（签字）：
批准日期：
年月日
游程编码的分析与实现
摘要
本文所研究的二值图像游程编码数据压缩，就是一种具有高压缩比的无损数据压缩技术，它是应用游程编码的原理对二值图像进行数据压缩的编码技术，其编码非常简单，编码和解码速度快，因此其应用范围广泛。
文章首先简要介绍了信源编码的原理，然后重点介绍游程编码的原理和实现技术，对游程编码技术做了较为全面的研究。
包括游程压缩模型、数据压缩、解压缩过程，比给出了相应的MATLAB程序。
关键词：
游程编码，解码，信源编码，MATLAB
1信源编码
1.1信源编码简介
编码实质上就是对信源的原始符号按一定规则进行的一种变换。
编码可分为信源编码和信道编码。
由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。
具体的说就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。
信源编码的基本途径有两个：
使序列中的各个符号尽可能地相互独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。
采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。
即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。
1.2信源编码的理论基础
信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。
无失真信源编码定理：
是离散信源/数字信号编码的基础；
限失真信源编码定理：
是连续信源/模拟信号编码的基础。
1.3信源编码的分类及作用
信源编码的分类：
离散信源编码：
独立信源编码,可做到无失真编码；
连续信源编码：
独立信源编码,只能做到限失真信源编码；
相关信源编码：
非独立信源编码。
编码的作用：
信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：
作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。
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简单来说，游程长度编码的主要任务是统计连续相同字符的个数，解码时要根据字符及连续相同字符的个数，恢复原来的数据。
2.3游程编码特点
游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优质的信道。
此外，编程长度可以从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改进。
一般情况下游程长度越长，其概率越小，这在以前的计算中也可以看见，而且将随着长度的增大渐进向零。
对于小概率的码字，其长度为达到概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。
再按哈夫曼编码或其他方法处理以达到压缩码率的目的。
3游程编码的MATLAB实现
3.1程序设计
>>image1=imread（'C:
\ProgramFiles\MATLAB71\work\1\girl.jpg'）;%读入图像
>>imshow（image1）;%显示原图像
>>%以下程序是将原图像转换为二值图像
>>image2=image1（:
）;%将原始图像写成一维的数据并设为image2
>>image2length=length（image2）;%计算image2的长度
>>fori=1:
1:
image2length%for循环，目的在于转换为二值图像
Ifimage2（i）>=127
image2（i）=255;
elseimage2（i）=0;
end
end
>>image3=reshape（image2,146,122）;%重建二维数组图像，并设为image3
>>figure,imshow（image3）;
>>%以下程序为对原图像进行游程编码，压缩
>>X=image3（:
）;%令X为新建的二值图像的一维数据组
>>x=1:
1:
length（X）;%显示游程编码之前的图像数据
>>figure,plot（x,X（x））;
>>j=1;
>>image4
（1）=1;
>>forz=1:
1:
（length（X）-1）%游程编码程序段
ifX（z）==X（z+1）
image4（j）=image4（j）+1;
else
data（j）=X（z）;%data（j）代表相应的像素数据
j=j+1;
image4（j）=1;
end
end
>>data（j）=X（length（X））;%最后一个像素数据赋给data
>>image4length=length（image4）;%计算游程编码后的所占字节数，记为image4length
>>y=1:
1:
image4length;%显示编码后数据信息
>>figure,plot（y,image4（y））;
>>CR=image2length/image4length;%比较压缩前于压缩后的大小
>>%下面程序是游程编码解压
>>l=1;
>>form=1:
image4length
forn=1:
1:
image4（m）;
rec_image（l）=data（m）;
l=l+1;
end
end
>>u=1:
1:
length（rec_image）;%查看解压后的图像数据
>>figure,plot（u,rec_image（u））;
>>rec2_image=reshape（rec_image,146,122）;%重建二维图像数组
>>figure,imshow（rec2_image）;%显示解压恢复后的图像
3.2输出结果
游程长度编码RLC一般不直接应用于多灰度图像，但是比较适合于二值图像的编码，因此首先读入一副图像并对其进行转换，将其转换为二值图像如图1所示：
图1需进行压缩的图像
利用MATLAB显示压缩之前的图像数据图2所示；
图2压缩前的图像数据
利用游程编码思想对图形进行压缩并显示压缩后的图像数据如图3所示：
图3压缩后的图像数据
对图像进行游程编码解压并显示解压缩后的图像数据，如图4所示：
图4解压缩后的图像数据
利用解压缩后的图像数据重建二维图形如图5所示：
图5解压缩后重建的图形
3.2结果分析
通过图2与图3的对比，我们已经能够清楚地看出图像被明显压缩,数据量明显减少。
又通过程序输出的数据CR=12.084，可以看出压缩率为12.084，证明了游程编码的数据压缩能力确实很强。
又由图1与图5，以及图2与图4的对比能够清楚的看出游程编码压缩技术是一种无损的压缩技术，能够实现对图形的无损压缩。
因此游程编码技术在安全、医药等几个对图像数据要求压缩和解压缩过程不能有丝毫损失的特殊领域可以广泛应用。
总结
本设计在历经几天的努力下终于完成了。
通过这次设计使我对编码有一进一步的了解。
游程长度编码RLC一般不直接应用于多灰度图像，但是比较适合于二值图像的编码，例如传真图像的编码等．为了达到较好的压缩效果。
有时游程长度编码和其它一些编码方法混台使用．例如，在JPEG中，游程长度编码和离散余弦变换DCT（DiscreteCosineTransform）及霍夫曼（Huffman）编码一起使用，对分块做完DCT及量化后的频域图像数据做z形扫描，然后做游程长度编码，对游程长度编码的结果再做霍夫曼编码.
游程压缩作为数据压缩技术的一个分支，理论浅显，压缩比之高已经让人刮目相看，这不由令人对数据压缩技术肃然起敬。
走过半个多世纪的离散余弦变换理论在数据压缩领域至今不衰；新兴的神经网络理论将数据压缩推向了一个新的高度；近来，小波变换理论更使数据压缩技术登峰造极，图像压缩的JPEG2000标准使小波理论傲视群雄。
可以预见，新的数学理论将不断为数据压缩技术输入新鲜血液，因此数学理论决不可偏废。
参考文献
[1]夏娜.信息编码与加密实践[M].合肥工业大学出版社，2008，8．
[2]曹雪虹.信息论与编码[M].清华大学出版社，2009，2．
[3]王慧琴.数字图像处理[M].北京：
北京邮电大学出版社，2007.
升级会员 