基于MATLAB的图像LZW编码研究

中国矿业大学2015-2016学年第二学期《数字视频技术》课程小设计考核图像的LZW编码研究专业班级：信息14-05班学生姓名：李辉、李港深、李少杰学生学号：04141394、04141393、04141395本人郑重声明：本人认真、独立完成了查找资料、完成作业、编写程序等考核任务，无抄袭行为。签字：日期：2017.05.17成绩评阅人1.引言1.1A.Lempel和J.Ziv在1978年首次发表了介绍字典编码方法的文章将其称之为LZ78。在他们的研究基础上，TerryA.Welch在1984年发表了对这种编码算法进行了改进的文章，并首先在高速硬盘控制器上应用了这种算法。因此后来把这种编码方法称为LZW(Lempel—ZivWalch)压缩编码。近年来越来越多的研究人员注意到图像压缩的重要性，主要原因在于图像文件不仅占据内存空间，而且也占据大量的传输带宽，因此存储和传输前对图像进行压缩就成为必然。信息数字化的高速进行更是给数据压缩带来严峻的挑战，在不同的领域，出现了各种各样的压缩方法，例如基于熵的统计编码(Huffman编码、Shannon编码、算术编码等)，基于字典的ARJ，LZH，PKZIP等压缩方法，分形编码、小波变换等变换编码，分块编码，以及JPEG，MPEG等。LZW压缩算法是一种无损压缩算法，它主要是用一种代码来表示数据流中出现的重复串，以达到压缩的目的，并且LZW算法可以大大缩小对通讯带宽的需求，具有较高的实用价值。LZW算法不仅可以用于文字数据的压缩，而且也可以成功地用于某些图像数据的压缩处理，如GIF和TIFF等图像格式，本文正是基于这种LZW编码的。大量数据的图象信息会给存储器的存储容量，通信干线信道的宽度，以及计算机的处理速度增加极大的压力，会使得WorldWideWeb变成WorldWideWait。单纯靠增加存储器容量，提高信道带宽以及计算机处理速度等方法来解决这个问题是不现实的。很显然，在信道带宽、通信链路一定的前提下，采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。没有图象编码压缩技术的发展，大容量图象信息的存储与传输是难以实现的，多媒体、信息高速公路等新技术在实际中的应用也会碰到很大的困难。LZW压缩算法是一种常用的数据压缩算法，由于它不依赖于任何数据格式，而且具有很高的综合性能指标，因而得到广泛应用。1.2LZW编码LZW算法的词典是根据输入的数据动态创建的。LZW算法先将可能的信源符号创建一个初始词典，然后在编码过程中，遇到词典中没有的短语（信源序列）就加到词典中，动态创建词典。提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.2.设计任务2.1设计任务实现灰度图像的LZW编码和解码恢复图像2.2设计目的(1)了解LZW编码的基本原理及其特点；(2)理解并熟练对图像进行LZW编码的算法；(3)学习和熟悉MATLAB图像处理工具箱；(4)熟悉和掌握MATLAB程序设计方法；2.3设计要求要求实现灰度图像的LZW编码和解码恢复图像；处理结果要求最终图像显示，且计算图像的信息熵，平均码字长度，编码效率，压缩比。扩展要求：读写GIF图片。3.总体设计方案3.1系统运行环境Windows8.1/10系统3.2编程软件平台MATLABR2013a/R2014a3.3LZW编码算法原理LZW算法是一种基于字典的编码——将变长的输入符号串映射成定长的码字——形成一本短语词典索引（串表），利用字符出现的频率冗余度及串模式高使用率冗余度达到压缩的目的。该算法只需要一遍扫描，且具有自适应的特点，不需要保存和传送串表。(1)LZW压缩算法初始化：将所有单个字符的串放入串表ST中(共n2项，实际操作时不必放入，只需空出串表的前n2项，字符对应码字所对应的的串表索引即可）;读首字符入前缀串w；设置码长codeBits=n+1；设置串表中当前表项的索引值next=初始码字=n2；循环：读下一输入字符c；若c=EOF（文件结束符），则输出w的码字，结束循环（输出结束码字）；若wc已在串表中，则w=wc，转到循环开始处；否则，输出w的码字，将wc放入ST中的next中，next++；令w=c，转到循环开始处；若next的位数超过码长（＞codeBits），则codeBits＋＋；若串表已满（next的位数已超过最大码长12），则清空串表，输出清表码字，转到初始化开始处。（2）LZW还原算法初始化：将所有单个字符串放入串表ST中；（共n2项【码字为0-n2-1】），实际操作不必放入，只需空出串表前n2项，字符对应码字对应字符串表索引即可）串表中当前表项索引next=n2+2；设置码长codeBits=n+1；读取首个码字（所对应的单个字符）入老串old，输出该字符；循环：读取下一个码字new；若new=结束码字，结束循环；若new=清表码字，则清空串表，转到初始化开始处；若new大于等于next则输出串newStr=old+old【0】（例外处理）；若new小于next，则输出串newStr；将newStr【0】+old放入串表ST【next】中，next++；若next的位数超过码长（大于codeBits），则codeBits++，但是若加1后的codeBits大于12，则重新让codeBits=12；old=newStr，转到循环处开始，其中：newStr=ST【new】（即串表中索引为new的串）；3.4LZW编码算法的特点(1)LZW压缩技术对于可预测性不大的数据具有较好的处理效果，常用于GIF格式的图像压缩，其平均压缩比在2：1以上，最高压缩比可达到3：1。(2)对于数据流中连续重复出现的字节和字串，LZW压缩技术具有很高的压缩比。(3)除了用于图像数据处理以外，LZW压缩技术还被用于文本程序等数据压缩领域。(4)LZW压缩技术有很多变体，例如常见的ARC、RKARC、PKZIP高效压缩程序。(5)对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。(6)对机器硬件条件要求不高，在Intel80386的计算机上即可进行压缩和解压缩。3.5算法流程图设计3.5.1主流程图开始加载图像，并将其灰度化计算图像大小并转化格式类型调用LZW编码程序进行压缩调用LZW解码程序进行解码显示原始图像、灰度图像和经编码解码后的图像结束显示平均码长、压缩比、信息熵及编码效率3.5.2编码流程图开始初始化读图像序列前缀=新序列加入词典输出前缀码前缀＝序列新序列在词典否是词典已满？是编码完成？否是结束否3.5.3解码流程图3.6组员任务分工李少杰：编写主要程序，编码解码函数程序及相关子程序，修改报告及演示文稿。李港深：编写部分程序及部分函数程序，撰写报告。李辉：编写部分程序，进行程序调试完善，制作演示文稿。4.程序实现4.1主程序clear;clcI=rgb2gray(imread('house1.png'));[m,n]=size(I);x=double(I(:)');%转化格式类型%LZW编码[S,sz]=LZW(x);%LZW解码A=[];fori=1:length(sz)A=[AS{sz(i)}];end开始结束读取压缩序列，并存入行词典中解码后的序列解码A=[Azeros(1,m*n-length(A))];II=uint8(reshape(A,m,n));[M,N]=size(II);b=length(S);sum=M*N;H=0;%初始化信息熵fori=0:255;[r,c]=find(II==i);%统计每个灰度值的像素点总数num(i+1)=length(r);p(i+1)=num(i+1)/sum;%统计每个灰度值的概率ifp(i+1)~=0H=H-p(i+1)*log2(p(i+1));%计算信息熵endend%计算平均码字长度pjmc=b/sum%计算编码效率bmxl=H/pjmc%计算压缩比ysb=sum*8/bdisp('信息熵');disp(H);disp('平均码字长度');disp(pjmc);disp('编码效率');disp(bmxl);disp('压缩比');disp(ysb);imshow(II);4.2编解码程序function[S,sz]=LZW(x)%LZW词典编码%x为输入序列S为词典sz为输出n=length(x);%序列长度S=unique(x);%初始化词典x=num2cell(x);%转化为细胞数组S=num2cell(S);%转化为细胞数组sz=[];%初始化输出序列temp=[];%当前序列%开始编码fori=1:ntemp=[tempx{i}];%取一个元素放入序列中forj=1:length(S)ifisequal(S{j},temp)flag=1;break;elseflag=0;endendifflag==1%如果当前序列在词典中continue;else%如果当前序列不在词典中S=[Stemp];%将当前序列加入词典forj=1:length(S)ifisequal(S{j},temp(1:end-1))T=j;break;endendsz=[szT];temp=temp(end);%重置tempendendforj=1:length(S)ifisequal(S{j},temp(end))T=j;break;endendsz=[szT];%最后一位加入输出5.调试结果原图编解码后信息熵6.4501平均码字长度0.7295编码效率8.8420压缩比10.9665经过多次测试和调整，最终编码结果正确，解码结果正确，程序运行正确。6.总结感谢王利娟老师教授《数字视频技术》课程并为我们安排了这次课程设计。通过这次课设，我们更深地熟悉和掌握了MATLAB程序设计方法和灰度图像LZW的编码解码过程，学会了运用MATLAB平台对图像进行处理和分析。提高我们编程能力的同时，也让我们对编解码算法有了更深入的理解。课程设计是我们专业课程知识综合应用的实践训练，是我们迈向社会，从事职业工作前一个必不少的过程。在这次的课程设计中不仅检验了我们所学习的知识，也引发了我们对如何去把握一件事情，如何去做一件事情，如何完成一件事情等问题的思考。在设计过程中，与同学分工设计，和同学们相互探讨，相互学习，相互监督，提高了团队合作能力，学到了平时在课上学不到的知识，每个人都得到了很大的进步。通过这次数字视频技术课程设计，我们在多方面都有所提高。这次课程设计中，综合运用了本专业所学课程的理论知识。学会了在图像处理过程中，运用编程思维去实现某种功能或效果。在这次设计过程中，体现出自己的能力以及综合运用知识的能力，体会到了学有所用、学以致用的兴奋感和成就感，同时也暴露出了自己平时学习的不足和薄弱环节，进而加以弥补和改正。