图像压缩编码系统.docx
- 文档编号:10577500
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:33
- 大小:337.71KB
图像压缩编码系统.docx
《图像压缩编码系统.docx》由会员分享,可在线阅读,更多相关《图像压缩编码系统.docx(33页珍藏版)》请在冰点文库上搜索。
图像压缩编码系统
新疆大学毕业论文(设计)
题目:
图像压缩编码系统(MATLAB)版
学生姓名:
王丽梅
学生学号:
20060803207
所属院系:
数学与系统科学学院
专业:
信息与计算科学
班级:
2006--1班
指导教师:
艾斯卡尔﹒肉孜
完成日期:
2010年5月28日
声明
本人郑重声明该毕业论文(设计)是本人在艾斯卡尔老师指导下独立完成的,本人拥有自主知识产权,没有抄袭、剽窃他人成果,由此造成的知识产权纠纷由本人负责。
声明人(签名):
年月日
王丽梅同学在本人的指导下,按照任务书的要求,独立完成了该毕业论文(设计),本人已经详细审阅了该毕业论文(设计)。
指导教师(签名):
年月日
新疆大学
毕业论文(设计)任务书
班级:
信息与计算科学06-1姓名:
王丽梅
设计(论文)题目:
图像压缩编码系统(MATLAB版)
专题:
理论研究
设计(论文)来源:
指导教师指定
要求完成的内容:
学习图像压缩的知识,运用matlab编程实现图像的压缩,并且将压缩编码解码,对比压缩效果,并能在已有的知识上进行创新
发题日期:
2010年3月10日完成日期:
2010年5月28日
实习单位:
数学学院地点:
数学学院
论文页数:
23页;图纸张数:
28页
指导教师:
教研室主任:
院长(系主任):
摘要
图像压缩技术在现在并不是一个全新的技术,而是发展得比较完善了,并且它有很强的实用性,运用在很多领域上。
本文介绍了图像压缩的目的和压缩的本质。
由于压缩的方法很多,本文仅介绍了两种常用的算法,即哈夫曼算法和行程编码算法。
这两种算法都是利用统计的方法,将原图像中的灰度级用新的编码替代,从而达到压缩的目的。
当然,仅仅是编码是没有意义的,因此,本文也简单的介绍了解码的过程,并将解码后的结果与原图作了对比。
需要说明的是,这里的解码仅仅是粗糙的过程,在实际运用中,还要进行更多的处理。
关键词:
图像压缩,哈夫曼编码算法,行程编码,统计,解码
ABSTRACT
Imagecompresstechnologyisnotanewtechnologynow,butitisdevelopedcompletelybetter.Anditisveryavailableandappliedinmanyfields.Thisarticleintroducesthepurposeofimagecompressandtheessenceofcompress.Becausetherearemanycompressionmethods,thisarticleonlydescribestwocommonlyusedalgorithms,thatHuffmancodingalgorithmandrunlengthencoding.Boththetwoalgorithmsareusingstatisticalmethodstomaketheoriginalgray-levelimagecodingbeinsteadofthenewcodingtoachievethepurposeofcompression.Ofcourse,it’snotmeaningfultocompressonly.Thus,wesimplyintroducetheprocessofthedecoding,andcomparetheoldpicturewiththeresultofdecoding.Beexplainedthat,wheretheprocessofdecodingisonlyrough,inpracticaluse,butalsoformoreprocessing.
Keywords:
picturecompress,Huffmancodingalgorithm,runlengthencoding,statistic,decoding
目录
1前言1
1.1图像压缩的原因1
1.2压缩的本质1
1.3图像压缩的应用1
2图像压缩的基本原理2
2.1图像压缩的根据2
2.2数据冗余的类型2
2.3图像压缩的分类2
2.4图像压缩后的处理4
3哈夫曼编码5
3.1哈弗曼编码具体算法5
3.2哈弗曼编码过程简述7
3.3哈夫曼算法的MATLAB实现7
3.3.1彩色图像的相关说明7
3.3.2算法流程8
3.3.3程序及详细注解8
3.3.4最终的结果13
3.3.5哈夫曼编码解码13
3.3.6哈夫曼算法的分析说明14
3.3.7哈夫曼算法的改进15
4行程编码16
4.1图像编码必要性16
4.2行程编码介绍16
4.3行程编码的实现16
4.3.1算法流程16
4.3.2行程编码算法的MATLAB实现17
4.3.3行程编码最终结果18
4.3.4行程编码解码19
4.3.5行程编码分析说明20
5总结21
参考文献22
致谢23
1前言
1.1图像压缩的原因
在介绍图象的压缩编码之前,先考虑一个问题:
为什么要压缩?
因为图像信息的数据量实在是很大。
如今在Internet上,浏览图像信息的方式是WWW(WorldWideWeb),WWW尽管漂亮,但是也带来了一个问题:
图像信息的数据量太大了,本来就已经非常紧张的网络带宽变得更加不堪重负,使得WorldWideWeb变成了WorldWideWait。
大数据量的图像信息会给存储器的存储容量,通信干线信道的带宽,以及计算机的处理速度增加极大的压力。
单纯靠增加存储器容量,提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的,这时就要考虑压缩。
因此,压缩的最终目的就是便于存储和传输。
1.2压缩的本质
压缩的理论基础是信息论。
从信息论的角度来看,压缩就是去掉信息中的冗余,即保留不确定的信息,去掉确定的信息(可推知的),也就是用一种更接近本
质的描述来代替原有冗余的描述。
这个本质的东西就是信息量(即不确定因素)。
1.3图像压缩的应用
图像压缩一般通过改变图像的表示方式来达到,因此压缩和编码是分不开的。
图像压缩的主要应用是图像信息的传输和存储,可广泛地应用于广播电视、电视会议、计算机通讯、传真、多媒体系统、医学图象、卫星图像等领域。
2图像压缩的基本原理
2.1图像压缩的根据
图像能够被压缩,是因为原始图像的数据量远远大于它所提供的有效信息量。
也就是说原始的图像数据文件包含大量的冗余信息和不相干的信息。
冗余信息是重复出现在的信息,它的删除对原始信息并没有损失。
不相干的信息的删除对原始信息有一定的影响,但在限制条件下不会影响信息内容的理解。
但通常不必准确区别这两个概念。
只删除冗余信息的算法被称为“无损压缩”,它可以完全恢复原文件,但其压缩比率会降低;不干信息的算法被称为“有损压缩”,它只能近似的恢复原文件,它的压缩比率比较高。
如果用n1表示一副原图的数据量,n2表示压缩后的数据量,压缩率Cr定义为:
Cr=n1/n2,冗余量Rd=1-1/Cr。
2.2数据冗余的类型
1)编码冗余
对图像编码时须建立数据与编码的对应关系。
图像的每个灰度值对应一个码字。
下面我们讲的哈夫曼算法和行程编码算法都是利用编码冗余做的。
2)像素间冗余
它指的是像素灰度级间具有的相关性。
它包括以下三种形式:
(1)空间冗余:
是指在一副图像内,物体和背景的表面物理特性各自具有很强的相关性。
(2)时间冗余:
序列图像间存在明显的相关性。
(3)结构冗余:
有的图像构成非常规则,如纹理结构在人造图像中经常出现,如果能找到纹理基元,就可以通过仿射变换生成图像的其他部分。
(4)知识冗余:
人类拥有的知识也可以用于图像编码系统的设计,如人脸具有固定结构,只是不同的人在局部的表达不同而已。
3)心理视觉冗余
我们的视觉系统具有非线性、非均匀性特点,对图像上呈现的信息具有不同的分辨率。
也就是说很多图像间的微小变化人眼察觉不到,这部分可以认为是心理视觉冗余的,删除此类信息不会明显降低图像的视觉质量。
2.3图像压缩的分类
压缩可分为两大类:
第一类压缩过程是可逆的,也就是说,从压缩后的图象能够完全恢复出原来的图象,信息没有任何丢失,称为无损压缩;第二类压缩过程是不可逆的,无法完全恢复出原图象,信息有一定的丢失,称为有损压缩选择哪一类压缩,要折衷考虑,尽管我们希望能够无损压缩,但是通常有损压缩的压缩比(即原图象占的字节数与压缩后图象占的字节数之比,压缩比越大,说明压缩效率越高)比无损压缩的高。
图像数据压缩的目的是节省图像存储空间、减少传输信道的容量和缩短图像加工处理时间。
针对不同应用目的可以使用不同的压缩办法。
1.在数字处理领域如下几种压缩方法:
1)信息保持编码:
该编码技术主要针对图像数字存储方面。
该类编码技术要求能够最大限度的压缩图像大小,而且解码后能够无失真的恢复图像信息,通常也称该类编码为无误差编码。
2)保真度编码:
该类编码主要用于数字电视技术和静止图像通信方面。
这些图像受传输信道容量的限制,接受图像信息的信宿又往往是人眼,过高的空间分辨率和过多的灰度层次不仅仅增加了数据量,而且人眼无法接受。
因此可以在编码过程中丢失一些对信宿无用或用处不大的信息,也就是允许失真的条件下和在一定保真准确度准则下进行图像的压缩编码。
3)特征提取:
在图像识别和分析、分类技术中,往往不需要全部的图像值。
例如在文字识别过程中,不需要知道文字的具体灰度值,只要将文字和背景区分开就可以了。
因此,只要对需要的特征信息进行编码,就可以压缩图像数据量。
显然,特征提取编码也是一种非信息保持编码。
2.另一种分类可以将图像编码分成四大类:
平均信息法、预测编码法及其他编码法。
1)平均信息法(象素编码):
平均信息法是对每个像素进行单独处理,不考虑像素之间的相关性。
在象素编码中常用的几种方法有:
(1)脉冲编码调制(PulseCodeModulation,简称PCM);
(2)熵编码(EntropyCoding);常用的哈弗曼编码属于熵编码。
(3)行程编码(RunLengthCoding);
(4)位平面编码(BitPlaneCoding)。
2)预测编码法:
预测编码法是利用相邻像素之间的相关性,去掉图像中冗余的信息,只对有用信息进行编码。
例如由于像素灰度是连续的,所以在一片区域中,相邻像素之间灰度值的差别可能很小。
如果只记录一个像素的灰度,其他像素的灰度都用其与其前一个灰度之差来表示,就能起到压缩的目的。
举个简单的例子,因为象素的灰度是连续的,所以在一片区域中,相邻象素之间灰度值的差别可能很小。
如果我们只记录第一个象素的灰度,其它象素的灰度都用它与前一个象素灰度之差来表示,就能起到压缩的目的。
如248,2,1,0,1,3,实际上这6个象素的灰度是248,250,251,251,252,255。
表示250需要8个比特,而表示只需要两个比特,这样就实现了压缩。
常用的预测编码方法有增量调制(简称DM)和微分预测编码(简称DPCM)。
3)变换编码法:
变换编码法是指给定的图像变换到另一个数据域上,使得大量的信息能用较少的数据来表示,从而达到压缩的目的的方法。
常用的有正交变换编码、离散余弦变换和离散沃尔什-哈达玛变换等。
4)其他编码法:
其他编码法方法还很多,如内插法中的低取样和来取样法、方块编码、混合编码、矢量化和LZW算法等。
这些年又出现了新的压缩方法:
如使用人工神经元网络的压缩编码方法、分形、小波、基于对象的压缩编码算法和基于模型的压缩编码算法等。
2.4图像压缩后的处理
由于图像压缩的目的仅是便于存储和传输,而我们存储传输后,需要原图像,因此,我们需要对压缩后的东西解压,这个解压过程实际上就是压缩的逆过程。
接下来,介绍图像压缩方法。
由于有关图像压缩的方法很多,因此在此仅介绍哈弗曼编码和行程编码。
3哈夫曼编码
3.1哈弗曼编码具体算法
哈夫曼(Huffman)编码是一种常用的压缩编码方法,是Huffman于1952年为压缩文本文件建立的。
它的基本原理是频繁使用的数据用较短的代码代替,较少使用的数据用较长的代码代替,每个数据的代码各不相同。
这些代码都是二进制码,且码的长度是可变的。
举个例子:
假设一个文件中出现了8种符号S0,S1,S2,S3,
S4,S5,S6,S7,那么每种符号要编码,至少需要3比特。
假设编码000,001,010,011,
100,101,110,111(称做码字)。
那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成000001111000001110010010011100101000000001,共用了42比特。
我们发现S0,S1,S2这三个符号出现的频率比较大,其它符号出现的频率比较小,如果我们采用一种编码方案使得S0,S1,S2的码字短,其它符号的码字长,这样就能够减少占用的比特数。
例如,我们采用这样的编码方案:
S0到S7的码字分01,11,101,0000,0001,0010,0011,100,那么上述符号序列变成01111000111001110
1101000000010010010111,共用了39比特,尽管有些码字如S3,S4,S5,S6变长了(由3位变成4位),但使用频繁的几个码字如S0,S1变短了,所以实现了压缩。
上述的编码是如何得到的呢?
随意乱写是不行的。
编码必须保证不能出现一个码字和另一个的前几位相同的情况,比如说,如果S0的码字为01,S2的码字为011,那么当序列中出现011时,你不知道是S0的码字后面跟了个1,还是完整的一个S2的码字。
我们给出的编码能够保证这一点。
下面给出具体的Huffman编码算法。
(1)首先统计出每个符号出现的频率,例如S0到S7的出现频率分别为:
0.25,0.19,0.08,0.06,0.21,0.02,0.03,0.16
(2)从左到右把上述频率按从大到小的顺序排列。
(3)将最小的两个数相加的值表上*号,其余的数据不变,然后将得到的数据排序
(4)重复(3),直到只有两个数据。
(5)从最后一列概率编码,从而得到最终编码。
具体过程如下图所示:
概率压缩过程:
初始信源
信源的消减步骤
符号
概率
123456
S0
0.25
0.250.250.250.35*0.4*0.6*
0.210.210.210.250.350.4
0.190.190.190.210.25
0.160.160.19*0.19
0.080.11*0.16
0.060.08
0.05*
S4
0.21
S1
0.19
S7
0.16
S2
0.08
S3
0.06
S6
0.03
S5
0.02
表3-1哈夫曼概率压缩过程
编码过程:
初始信源
对消减信源的赋值
符号
概率编码
123456
S0
0.2501
0.25010.25010.25010.35*000.4*10.6*0
0.21100.21100.21100.25010.35000.41
0.19110.19110.19110.21100.2501
0.160010.160010.19*0000.1911
0.0800010.11*00000.160001
0.06000000.080001
0.05*00001
S4
0.2110
S1
0.1911
S7
0.16001
S2
0.080001
S3
0.0600000
S6
0.03000010
S5
0.02000011
表3-2哈夫曼算法编码过程
哈夫曼编码与二进制编码的比较:
符号
概率
二进制编码
huffman编码
S0
0.25
000
01
S4
0.21
100
10
S1
0.19
001
11
S7
0.16
111
001
S2
0.08
010
0001
S3
0.06
011
00000
S6
0.03
110
000010
S5
0.02
101
000010
平均码长
3
2.7
表3-3二进制编码与哈夫曼编码比较表
平均码长是各代码长度的加权平均。
很明显,哈夫曼编码总体码长比原来的存储码长短。
因此,我们达到了压缩的目的。
3.2哈弗曼编码过程简述
产生Huffman编码需要对原始数据扫描两遍。
第一遍扫描要精确地统计出原始数据中,每个符号出现的频率,第二遍是按照上述过程进行Huffman编码。
这样,每种符号都被哈夫曼编码代替,最后按照符号的排序,将相应的哈夫曼编码写出来就完成了。
若要还原原图像,对其进行解码就可以了。
3.3哈夫曼算法的MATLAB实现
3.3.1彩色图像的相关说明
在彩色图像中,每一种彩色是由红、绿、蓝三色形成的,每种色调都有256种灰度,即0—255级。
因此,在MATLAB中,通过imread读出的图像信息是三页多维矩阵,每一页对应一个颜色层。
并且imread读图时是按逐个像素读的,每个像素的色彩由上述三种灰度形成。
例如,一个206×217像素的彩色图像,imread读出的矩阵是206行,217列,3页的。
可以看出该图不大,但是由它读出的矩阵不小,相应的计算量也是不容忽视的。
3.3.2
算法流程
此处并没有采用概率排序,
而是采用对灰度像素个数
排序,这是因为计算概率无
疑增大了计算量,因此用灰
度级的像素个数替代
图3-1哈夫曼算法程序流程图
3.3.3程序及详细注解
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%读入图像,定义结构体,便于存储
I=imread('zbz.jpg');
pix(256)=struct('huidu',0.0,...%灰度值
'number',0.0,...%对应像素的个数
'bianma','');%对应灰度的编码
[mnl]=size(I);
fid=fopen('huffman.txt','w');%huffman.txt是灰度级及相应的编码表
fid1=fopen('huff_compara.txt','w');%huff_compara.txt是编码表
huf_bac=cell(1,l);
fort=1:
l
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化结构数组
fori=1:
256
pix(i).number=1;
pix(i).huidu=i-1;%灰度级是0—255,因此是i-1
pix(i).bianma='';
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%统计每种灰度像素的个数记录在pix数组中
fori=1:
m
forj=1:
n
k=I(i,j,t)+1;%当前的灰度级
pix(k).number=1+pix(k).number;
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%按灰度像素个数从大到小排序
fori=1:
255
forj=i+1:
256
ifpix(i).number temp=pix(j); pix(j)=pix(i); pix(i)=temp; end end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %因为有的灰度值在图像中可能没有对应的像素值,所以要 %找出在图像中存在像素的灰度级的个数,并保存在num中 fori=256: -1: 1 ifpix(i).number~=0 break; end end num=i; count(t)=i;%记录每层灰度级%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %定义用于求解的矩阵 clearhuffman huffman(num,num)=struct('huidu',0.0,... 'number',0.0,... 'bianma',''); huffman(num,: )=pix(1: num); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %矩阵赋值 fori=num-1: -1: 1 p=1; %算出队列中数量最少的两种灰度的像素个数的和 sum=huffman(i+1,i+1).number+huffman(i+1,i).number; forj=1: i %如果当前要复制的结构体的像素个数大于sum就直接复制 ifhuffman(i+1,p).number>sum huffman(i,j)=huffman(i+1,p); p=p+1; else %如果当前要复制的结构体的像素个数小于或等于sum就插入和的结构体 %灰度值为-1标志这个结构体的number是两种灰度像素的和 huffman(i,j).huidu=-1; huffman(i,j).number=sum; sum=0; huffman(i,j+1: i)=huffman(i+1,j: i-1); break; end end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %开始给每个灰度值编码 fori=1: num-1 obj=0; forj=1: i ifhuffman(i,j).huidu==-1 obj=j; break; else huffman(i+1,j).bianma=huffman(i,j).bianma; end end ifhuffman(i+1,i+1).number>huffman(i+1,i).number %说明: 大概率的编0,小概率的编1,概率相等的,标号大的为1,标号小的为0 huffman(i+1,i+1).bianma=[huffman(i,obj).bianma'0']; huffman(i+1,i).bianma=[huffman(i,obj).bianma'1']
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图像 压缩 编码 系统