游程编码课程设计说明书Word文档下载推荐.docx
- 文档编号:615273
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:32
- 大小:480.54KB
游程编码课程设计说明书Word文档下载推荐.docx
《游程编码课程设计说明书Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《游程编码课程设计说明书Word文档下载推荐.docx(32页珍藏版)》请在冰点文库上搜索。
3.1压缩前的准备10
3.2进行游程编码11
3.3算法流程13
3.4游程编码的简单实现18
设计总结20
附录21
参考文献23
摘要
本课题主要是针对于游程编码信源编解码的数据压缩算法的设计与实现,游程编码非常简单,编码、解码速度快,应用广泛。
游程编码是针对于二元序列的一种编码方法,对于二值图像而言是一种具有高压缩比的无损数据压缩技术,它是应用游程编码的原理对二值图像进行数据压缩的编码技术,对连续的黑、白像素数(游程)以不同的码字进行编码。
游程编码是一种简单的非破坏性资料压缩法,其好处是加压缩和解压缩都非常快,其方法是计算连续出现的资料长度压缩之,其缺点是对于不重复的资料反而加大容量且需大量的缓冲和优质信道来实现。
游程编码在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)
码表
码1
码2
X1
P(X1)
00
X3
P(X3)
10
001
X2
P(X2)
01
X4
P(X4)
11
111
一般情况下,码可分为两类:
一类是固定长度的码,码中所有码字长度都相同,如表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简单来说,游程长度编码的主要任务是统计连续相同字符的个数,解码时要根据字符及连续相同字符的个数,恢复原来的数据。
游程编码记录方式有两种:
①逐行记录每个游程的终点列号:
②逐行记录每个游程的长度(像元数)。
如有栅格图形如下:
A
B
C
第一种方式记为:
A,3,B,5
A,1,C,4,A,5
第二种就记作:
A,3,B,2
A,1,C,3,A,1
2.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);
灰度图'
path1=input('
请输入要存储的图像路径\n'
imwrite(image2,path1);
%存为灰度图像
效果如下:
图3.1彩色图转换为灰度图
本程序运行之后,要在MATLAB命令窗口中输入将要转换的图像路径,这里我的彩色图像在“D:
\tu3.jpg”,读取图像后可得出当前图像的矩阵行列大小为154*615,利用rgb2gray函数可以将当前彩色图像转换为灰度图像,为了方便之后的压缩,此处将转换后的图像用imwrite命令将之存储在“D:
\tu31.jpg”,并能显示转换后的图像行列大小为154*205,可以知道,转换后的图像比之原图像缩小了3倍,这正是因为彩色图像一个像素点由RGB三个灰度值描述,而灰度图像一个像素点只由一个灰度值表示,因而彩色图像经转换后会变为只有黑白程度不同的图像,这就达到了为下一步转换为二值图像的前提条件,即图像矩阵中一个元素表示一个像素的灰度值。
3.2进行游程编码
读取灰度图像路径,先转换为二值图然后进行游程编码,得出压缩率。
(也可将转换二值图的程序单列出来)
请输入要读取的灰度图像路径\n'
[M,N]=size(image1);
%计算图像行列大小
figure,subplot(211);
imshow(image1);
%显示原图像
IM1=image1(:
%将图像转换为一维数组
IM1length=length(IM1);
%计算转换为一维数组的长度
fori=1:
1:
IM1length%for循环,目的在于转换为二值图像
ifIM1(i)>
=127%灰度值大于127转换为255,反之为0
IM1(i)=255;
else
IM1(i)=0;
end
end
image2=reshape(IM1,M,N);
%重组图像
subplot(212),imshow(i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 游程 编码 课程设计 说明书