4200.数字图像压缩算法研究与实现本科毕业论文

本科毕业论文（设计）题 目 数字图像压缩算法研究与实现 系 别 信 息 管 理 系 专 业 计算机科学与技术 年 级 学 号 姓 名 指 导 教 师 成 绩 _ 2009 年 5月15日 目 录大学本科毕业论文（设计）任务书I文献综述i大学本科毕业论文（设计）开题报告- 1 -正文1摘要1第1章引言11.1研究背景11.2研究内容21.3研究目标21.4研究意义21.5本文的组织3第2章图像压缩基本知识概述32.1图像压缩32.2图像压缩的必要性32.3图像压缩的可行性42.4图像压缩的意义52.5代表性图像压缩方法5第3章霍夫曼（Huffman）编码73.1霍夫曼算法编码原理及应用73.2对霍夫曼算法问题的讨论113.3小结12第4章算术编码124.1算术编码概念及原理124.2图像信号的统计特性134.3算术编码的优缺点144.4算术编码未来应用前景144.5小结15第5章RLE（Run Length Encoding）压缩算法155.1概念155.2一般的RLE压缩算法155.3RLE4压缩算法165.4RLE8压缩算法175.5小结17第6章LZW压缩算法（字典压缩算法）176.1引言176.2基本原理及流程图176.3实用举例206.4小结21第7章DCT离散余弦变换编码227.1图像压缩基本原理及DCT算法227.2DCT应用于图像压缩的过程237.3小结24第8章图像压缩算法的VB实现248.1VB概述248.2实现具体步骤258.3程序编码与程序调试338.4JPEG压缩软件压缩结果分析338.5小结34第9章结束语34参考文献35附录36致谢39本科毕业论文（设计）指导教师评阅表a本科毕业论文（设计）交叉评阅表b本科毕业论文（设计）答辩记录c大学本科毕业论文（设计）任务书论文题目 数字图像压缩算法研究与实现 系 别 信息管理系 专 业 计算机科学与技术 姓 名 学 号 指导教师 开题日期 2008-11-29 论文的主要内容与要求：首先根据图像压缩的基本原理，研究和剖析现有的经典压缩算法，研究其特点，优点及不足之处，并在算法上做一些可行的研究，为新的标准及应用打下一定的基础；然后从众多压缩算法中，抽出一种使用最广、最优秀的压缩算法加以具体实现。进 度 安 排研究进度安排2008年12月-2009年1月， 根据课题研究的内容，收集资料2009年2月- 2009年3月， 建立研究模型，分类别进行理论研究2009年3月- 2009年4月， 整理研究内容，评价其合理性并进行修改2009年4月- 2009年5月， 归纳总结，形成一份完整的课题论文系部意见：注：1、任务书由指导老师填写。 2、任务书必须在第七学期13周前下达给学生。文献综述数字图像压缩算法研究与实现李 波大学荣昌校区信息管理系，重庆荣昌 402460摘要：随着多媒体技术和通讯技术的不断发展，多媒体娱乐、信息高速公路等不断对信息数据的存储和传输提出了更高的要求，也给现有的有限带宽给予严峻的考验，特别是具有庞大数据量的数字图像通信，更难以传输和存储，极大地制约了图像通信的发展。数字图像及其处理近年来的应用越来越广，但是数据的大量膨胀影响着存储空间，网络数据传输使有限的带宽变得更为拥塞，这些都会影响数字媒体的广泛使用。因此更为有效的数字图像压缩方案已成为信息通讯领域的一个重要研究课题，本文对此研究课题进行了系统的分析和综述。关键字：算法、图像编码、Huffman编码、DCT编码1. 引 言数字图像压缩技术被应用到多媒体通讯、医学等各个领域，在未来的科技领域，它仍然显示出其强大的生命力和发展潜力。在目前，多媒体计算机所涉及的数据包括很广泛，其中图像数据量尤其巨大，怎样处理、组织图像数据，在应用领域里起着至关重要的作用，图像压缩技术一直是多媒体信息处理技术研究中最活跃的领域，如何利用新的技术对图像进行压缩，并且使之符合规范标准以得到各个领域的支持，一直是研究的热点。本课题研究的目标和意义（1）什么是图像压缩及怎样压缩图像压缩是指以较少的比特有损或无损地表示原来的像素矩阵的技术，也称图像编码。图像数据之所以能被压缩，就是因为数据中存在着冗余。图像数据的冗余主要表现为：图像中相邻像素间的相关性引起的空间冗余；图像序列中不同帧之间存在相关性引起的时间冗余；不同彩色平面或频谱带的相关性引起的频谱冗余。数据压缩的目的就是通过去除这些数据冗余来减少表示数据所需的比特数。由于图像数据量的庞大，在存储、传输、处理时非常困难，因此图像数据的压缩就显得非常重要。压缩可分为两类 ：一类压缩是可逆的，即从压缩后的数据可以完全恢复出原来的图像，没有任何信息损失，称为无损压缩；另一类压缩是不可逆的，即从压缩后的数据无法完全恢复原来的图像，信息有一定的损失，称为有损压缩。通常情况下有损压缩的压缩效率比无损压缩的压缩效率要高。本课题研究的出发点就是有损压缩技术。（2）常见图像格式压缩算法1）霍夫曼（Huffman）编码1霍夫曼编码使用于TIFF，JPEG等图像格式中。编码原理：首先统计需要编码的字符的出现概率，然后将短的码赋予出现频率高的字符，而将长的码赋予出现频率低的字符。优点：因为霍夫曼编码较为简单有效，所以得到了广泛的应用。缺点：霍夫曼编码要对原始数据扫描两遍：第一遍扫描要精确地统计出原始数据中每个值出现的频率；第二遍扫描是建立霍夫曼树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都比较慢。另外霍夫曼编码对于位的增减都反映敏感，如果增加或减少位，译码程序将无法正确译出后面的数据。2）算术编码2编码原理：算术编码方法是将被编码的一则消息或符号串表示成0点和1之间的一个间隔，即对一串符号直接编码成 0， 1 区间上的一个浮点小数，符号序列越长，编码表示它的间隔越小，表示这一间隔所需的位数就越多。信源中的符号序列仍然要根据某种模式生成概率的大小来减少问题。可能出现的符号概率要比不可能出现的符号减少范围小。因此，只增加减少的比特位。优点：算术编码不是为每个符号产生一个单独的代码，而是使整条信息公用一个代码。因而可进一步提高压缩比。缺点：它的实现较为复杂，常与其它有损压缩方法结合使用。3）RLE（Run Length Encoding）压缩算法3RLE压缩算法使用于PCX，TIFF，BMP等图像格式编码原理：将一行中颜色值相同的相邻像素用一个记数值和颜色值来代替。例如：aabbbbcdddd经行程压缩处理后表示为2a4b1c4d。优点：当图像中存在很多块颜色相同的大面积区域，则RLE编码产生的压缩率是很高的。缺点：如果图像中很少有两个相邻的像素的灰度值相同时，则RLE编码非但不能压缩，还会造成处理后的图像数据量大于处理前的情况。4）LZW压缩算法（字典压缩算法）4LZW压缩算法使用于GIF，TIFF等图像文件中。编码原理：LZW压缩算法不需要在编码之前构造码表，而是在压缩过程中逐步建立字典的。其基本思想是将每一个字节的值都要与下一个字节的值配成一个字符对，并为每一个字符设置一个代码。当同样的一个字符对再度出现时就用代号代替这一字符对，然后再用这个代号与下一个字符配对。在配对过程中，必须建立三个表格，分别为：字首表、字符表和代号表。所有字符对和代号都分别存入这三个表格中。优点：LZW不仅可以与RLE压缩算法一样对连续出现的相同字符进行压缩，而且可以对经常出现的由不同字符组成的字符串进行压缩，因此在压缩处理不同值数据串方面，LZW压缩算法优于RLE压缩算法。缺点：如果原始图像数据值中带有随机变化的“噪音图像”则很难利用LZW算法来压缩。5）Discrete Cosine Transform (DCT，离散余弦变换)编码5编码原理：DCT属于变换编码，可用于图像处理的二维离散余弦变换。其定义6如下：且，将预先分成小块的原始图像进行DCT变换后，高频部分包含了锐利的边缘信息，而低频部分包含了图像的主要信息，因此低频比高频更重要，可以通过量化步骤有选择性地消除或较粗糙地量化高频部分。需要注意的是，压缩不是在变换步骤取得的，而是在量化时取得的，并且是有损压缩，不可恢复。典型的DCT变换步骤7是：输入图像将图像分块DCT量化熵编码压缩图Fig.1 DCT transform steps图1 DCT变换步骤优点：DCT具有很强的信息集中能力和计算复杂性综合得比较好而得到了较多的应用，如：在JPEG中使用了DCT编码。（3）压缩算法的选择与具体实现本文研究数据压缩的方法是针对图像数据特征，采用较成熟的算法用软件实现压缩目的，在研究过程中遇到如下问题：1) 有效的图像压缩算法 众所周知，现今的图像压缩算法日益众多，流行的图像格式以JPEG居多。JPEG 定义了两种压缩算法: 一种是离散余弦变换(DCT) ， 另一种是空间预测(DPCM) 。DCT 算法偏重于图像的视觉效果， 空间预测偏重于无失真编码而且现在互联网上使用JPEG有损压缩技术的居多，因此本文就对JPEG压缩算法中DCT编码技术进行了实现。2) 图像压缩算法的语言实现根据图像压缩算法理论和自己所学知识，因此我选用Visual Basic 6语言来实现JPEG压缩算法8。实现主要分成四个步骤： 颜色转换及采样； 颜色转换：对BMP图像中的颜色数据进行由RGBYCbCr的转换，Y表示亮度，CbCr分别表示蓝色度和红色度。转换公式：Y=0.2990R+0.5870G+0.1140BCb=-0.1687R-0.3313G+0.5000BCr=0.5000R-0.4187G-0.0813B这样转换以后就得到三个新的基色值，对这三个基色值来讲，都可以当作一个独立的图像平面来进行压缩编码。采样：颜色转换后，保留每一点的亮度值Y而色度值Cb，Cr则是每两点保留一点，在图像的行和列方向上都可执行颜色采样，这里采用的采样比是行列方向都是2:1:1，在行方向，每两点保留一点，列方向也是每两点保留一点，这样如果假设原来的CbCr矩阵大小为M*S，则经过2:1:1抽样之后成了 M/2*s/21/4M*S，只有原来的1/4了，图像大大缩小，如果想减小图像的失真度，则可行方向不抽样或列方向不抽样。 DCT变换（离散余弦变换）； 量化；图像数据转换为频率系数后，还得接受一项量化程序，才能进入编码阶段。量化阶段需要两个8*8矩阵数据，一个是专门处理亮度的频率系数，另一个则是针对色度的频率系数，将频率系数除以量化矩阵的值，取得与商数最近的整数，即完成量化。 编码用VB语言编程实现以上四个步骤，即完成了JPEG压缩过程。3) 实现语言的具体代码编写（4）研究意义多媒体是进入九十年代发展起来的全新的计算机最热门的研究领域之一。多媒体本身是一个先进计算机技术和视频、音频和通信等技术集成的产物。在目前，多媒体计算机所涉及的数据来源包括:文字、语音、音乐、声音、静止图像、电视图像、电影、动画、图形，如何处理、组织这些数据，提高处理、传输和存储的效率，从这些原始数据中去除冗余信息是多媒体计算机技术所要解决的问题之一。在这些数据中，图像数据量尤其巨大，同时由于受到通讯带宽的限制，所以图像压缩在数字电视、网络多媒体通信、会议电视、可视电话、遥感图像传程、图像数据库、自动指纹识别系统的指纹存储等应用中都起着至关重要的作用，其压缩技术一直是多媒体信息处理技术研究中最活跃的领域。数字图像占用的存储空间庞大，同时现在的带宽十分有限，如果数字图像不经过处理就在网络上进行传输，传输速度慢的让人难以忍受。网络带宽成为约束多媒体在网络上发展应用的瓶颈。要取得硬件设施方面的突破，造就宽带网尚需时日，所以目前只能从软件方面着手，对数字图像信息进行压缩。数十年此领域的研究结果表明，选用合适的数据压缩技术，有可能将原始文字数据量压缩到原来的二分之一左右，语音数据量压缩到原来的二分之一到十分之一，图像数据量压缩到原来的二分之一到六十分之一，或者更高。 针对这种情况，如何利用新的技术对图像进行压缩，并且使之符合规范标准以便得到各个领域的支持，于是就这个问题，本论文针对图像压缩算法理论基础进行研究和分析，并在算法上做一些可行的研究，为新的标准及应用打下一定的基础。数字图像压缩技术的研究现状与发展趋势本文对当前分布于众多研究文献中的数字图像压缩算法进行了汇总并进行了可行性研究，图像数据压缩的可行性是因为图像数据是高度相关的，大多数图像内相邻象素之间有较大的相关性，存在很大的冗余度，即空间冗余度。序列图像前后帧之间有较大的相关性，即时间冗余度。若用相同码长表示不同出现概率的符号也会造成比特数的浪费，即符号冗余度。允许图像编码有一定的失真也是图像可压缩的一个重要原因。目前，根据压缩技术的发展可将图像编码划分为以下六代；第一代压缩方法:直接波形变化，代表技术:PCM；第二代压缩方法:冗余去除，代表技术: DPCM、DCT、DWT、VQ；第三代压缩方法:结构编码，代表技术:图像分割；第四代压缩方法:分析与综合，代表技术:基于模型的编码；第五代压缩方法:识别与重构，代表技术:基于知识的编码；第六代压缩方法:智能编码，代表技术:语义编码。现在的编码处于第四代的水平，从国际数据压缩技术的发展看，视频编码会朝着多模式和跨模式的方向发展。随着新理论、新技术的不断发展，必然全有更有效的功能更全面的压缩编码方法出现。2. 本课题研究的内容通过资料收集、实际调查分析，最终形成自己的观点和见解，拟定以下内容进行探析：（1）基本知识1）图像压缩的概念2）图像压缩的起源3）图像压缩的发展4）图像压缩的应用及发展（2）经典压缩算法赏析1）霍夫曼（Huffman）编码2）算术编码3）RLE（Run Length Encoding）压缩算法4）LZW压缩算法（字典压缩算法）5）Discrete Cosine Transform (DCT，离散余弦变换)编码（3）图像压缩算法的具体实现1）图像压缩算法理论研究2）VB编程语言基本知识3）图像压缩算法的具体代码实现4）代码的调试与运行3. 总结在数据处理越来越繁琐的今天，压缩技术的发展同社会的需求息息相关，特别是数据库，因特网数据传输的要求，将随着新理论、新技术的不断发展，必然会有更有效的功能更全面的压缩编码方法出现。本文通过对几种图像压缩方法的分析，对不同的图像采用适合于自身的压缩方法，这样便可以提高压缩效率，来推动图像压缩技术的研究，并对目前图像压缩技术的研究者也具有一定的参考价值。研究本课题有利于人们更加清楚数字图像的压缩技术，认识高效的数字图像压缩技术将会给我们的互连网带来非常巨大的效益。4. 参考文献1 庄红涛，王亮霍夫曼算法在图像压缩中的具体实现及改进J西部广播电视，20032 贾铸算术编码方法在图像压缩编码中的应用J电子工程，19993 苟列红，李学春RLE压缩算法的分析及应用J现代计算机：下半月版，19974 杨小军LZW压缩算法解析及应用设计M火控雷达技术，19985 王云平DCT算法在图像处理中的应用N辽宁工学院学报，20036 冯玉珉，邵玉明，张星数据图像压缩编码M北京：中国铁道出版社，19937 李兰友，万振凯Visual Basic 6图像处理开发与实例M电子工业出版社，20008 李在铭数字图像处理压缩与识别技术M成都：电子科技大学出版社，20009 朱秀昌，刘峰，胡栋数字图像处理与图像通信M北京：北京邮电大学出版社10 吴永辉，俞建新JPEG2000图像压缩算法概述及网络应用前景J计算机工程，200311 张海燕，王东木等图像压缩技术J系统仿真学报，2002，14(7)：831-83512 J M ShaprioEmbedded image coding using zerotree of wavelet coefficientsJ.IEEE Trans.on Signal Processing,1993.13 Rabbani M.Jones P.Digital image compression techniquesJ.SHE,1991,1450:ll6128.14 K R Castleman.Digital Image ProcessingM.PrenticeHallInternational,Inc.vi大学本科毕业论文（设计）开题报告论文题目数字图像压缩算法研究与实现系别专业信息管理系计算机科学与技术年 级2005级开题日期2008.11.29学 号姓 名李 波指导教师汪维清1.本课题研究意义：随着多媒体技术和通讯技术的不断发展，多媒体娱乐、信息高速公路等不断对信息数据的存储和传输提出了更高的要求，也给现有的有限带宽给予严峻的考验，特别是具有庞大数据量的数字图像通信，更难以传输和存储，极大地制约了图像通信的发展。数字图像及其处理近年来的应用越来越广，但是数据的大量膨胀影响着存储空间，网络数据传输使有限的带宽变得更为拥塞，这些都会影响数字媒体的广泛使用。因此更为有效的数字图像压缩方案已成为信息通讯领域的一个重要研究课题。多媒体是进入九十年代发展起来的全新的计算机最热门的研究领域之一。多媒体本身是一个先进计算机技术和视频、音频和通信等技术集成的产物。在目前，多媒体计算机所涉及的数据来源包括:文字、语音、音乐、声音、静止图像、电视图像、电影、动画、图形，如何处理、组织这些数据，提高处理、传输和存储的效率，从这些原始数据中去除冗余信息是多媒体计算机技术所要解决的问题之一。在这些数据中，图像数据量尤其巨大，同时由于受到通讯带宽的限制，所以图像压缩在数字电视、网络多媒体通信、会议电视、可视电话、遥感图像传程、图像数据库、自动指纹识别系统的指纹存储等应用中都起着至关重要的作用，其压缩技术一直是多媒体信息处理技术研究中最活跃的领域。数字图像占用的存储空间庞大，同时现在的带宽十分有限，如果数字图像不经过处理就在网络上进行传输，传输速度慢的让人难以忍受。网络带宽成为约束多媒体在网络上发展应用的瓶颈。要取得硬件设施方面的突破，造就宽带网尚需时日，所以目前只能从软件方面着手，对数字图像信息进行压缩。数十年此领域的研究结果表明，选用合适的数据压缩技术，有可能将原始文字数据量压缩到原来的二分之一左右，语音数据量压缩到原来的二分之一到十分之一，图像数据量压缩到原来的二分之一到六十分之一，或者更高。 针对这种情况，如何利用新的技术对图像进行压缩，并且使之符合规范标准以便得到各个领域的支持，于是就这个问题，本论文针对图像压缩算法理论基础进行研究和分析，并在算法上做一些可行的研究，为新标准的更好的应用打下一定的基础。在这飞速发展的社会里，研究本课题有利于人们更加清楚认识高效的图像压缩技术对现在这个信息社会的重要性，学会利用有效的图像数据压缩方法，从而更加的节约网络带宽，为社会创造更高的效益。2.研究内容：（1）图像压缩的基础知识1）图像压缩的概念2） 图像压缩的起源3） 图像压缩的发展4） 图像压缩的应用及发展（2）图像压缩算法1） 霍夫曼（Huffman）编码2） 算术编码3） RLE（Run Length Encoding）压缩算法4） LZW压缩算法（字典压缩算法5） Discrete Cosine Transform (DCT,离散余弦变换)编码（1）图像压缩算法的具体实现1） 完整的实现方案：颜色转换及采样DCT变换量化编码算法的完整实现2） BMP、GIF、JPG文件格式分析3） 用VB编程实现图像压缩算法：输入一副BMP格式的图片，能压缩到指定的效果 4） 具体代码的编写与程序调试3.技术路线、研究方法和研究进度：（1）技术路线题目分析检测图像是否是BMP格式（如不是BMP格式则要转为BMP格式，用画图工具或者图形处理软件均可）读取文件头根据文件判断是否是真彩色，是则不用调色板，不是则要读取调色板VB编程实现读取BMP图像信息，获取图像行像素和列像素数值产生BMP图像数据矩阵抽样DCT变换量化编码滤除掉图像冗余信息完成，实现图像数据压缩以上内容用流程图表示如下：（2）研究方法第一、 通过查询资料来收集研究所需要的基础知识；资料收集方式：利用网络资源、查找相关书籍、收集有关研究课题内容的报刊杂志等；第二、 在资料收集完成之上，建立课题研究模型，思路清楚地对数字图像压缩技术各方面进行分析、探讨、研究；包括：理清图像压缩的发展、分类应用，根据现有经典的图像压缩算法进行解剖分析，分析各个算法的理论以及它们各自的优缺点。从现实实际出发，从中选择一款使用最广的压缩算法，并以具体软件设计语言实现完成图像压缩，从图像压缩的现状和发展去探索数字图像压缩技术的意义第三、 将所研究各方面按合理的思路组合及实现完成一篇完整的课题论文；（3）研究进度2008年12月2009年1月，根据课题研究的内容，收集资料2009年2月 2009年3月，建研究模型，分类别进行理论研究2009年3月 2009年4月，整理研究内容，评价其合理性并进行修改2009年4月 2009年5月，归纳总结，形成一份完整的课题论文4.导师意见： 指导教师（签名）：年 月 日5.系意见： 系（盖章） 年 月 日- 2 -正文数字图像压缩算法研究与实现李 波大学荣昌校区信息管理系，重庆荣昌 402460摘要：数字图像压缩技术对于数字图像信息在网络上实现快速传输和实时处理具有重要意义。本文首先介绍数字图像及压缩算法基本知识，再重点对现有的经典压缩算法进行介绍、剖析压缩原理及研究其优点与不足之处，展望未来压缩技术的发展方向。最后以压缩算法理论为依据，根据自己所学知识，对使用最广、最适用的压缩算法加以具体实现。关键字：算法、图像编码、Huffman编码、DCT编码Digital image compression algorithm Research and ImplementationLi BoDepartment of Information Management, Southwest University, Rongchang, ChongqingAbstract：Digital image compression technology for digital image information on the network to achieve rapid real-time transmission and processing of great significanceThis article introduced the first digital image compression algorithm and the basic knowledge, re-focus on the existing classical compression algorithm, and analyze the principle of compression analysis of its strengths and weaknesses, looking to the future direction of development of compression technology. Finally, compression algorithm based on the theory, based on their knowledge, the most widely used and most applicable to the specific compression algorithms to achieve. Key words：Algorithm；Image Coding；Huffman coding；DCT coding第1章 引言1.1 研究背景图像是信息传递的一种重要媒体，为了使有限的符号表达更多的信息量，图像压缩就显得非常必要，故此产生了各种各样的图象压缩方法，一般原始图像中存在很大的冗余度(如图像中相邻像素间的相关性引起的空间冗余；图像序列中不同帧之间存在相关性引起的时间冗余；不同彩色平面或频谱带的相关性引起的频谱冗余等)；或者是用户由于种种原因，而对原始图像的信息不全都感兴趣；或者是当信道的分辨率不及原始图像的分辨率时，降低输入原始图像分辨率对输出图像的分辨率影响不大；或者是大量图像信息(如：卫星遥感图像)的短时传输处理。所有这一切都要求在图象处理过程中，必须丢掉大量无用信息，保留有用部分，用尽可能少的字节数来表示原始图像，以提高图像传输的效率和减少图像的存储容量。大数据量的图像信息会给储存器的储存容量，通信干线信道的带宽以及计算机的处理速度增加极大的压力。单纯靠增加储存容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。因此，图像数据在传输和储存中，数据的压缩都是必不可少的。本课题正是从时代的需求出发来进行对数字图像压缩算法的探索。1.2 研究内容本文主要是针对于图像压缩的发展状况和趋势，对图像压缩算法进行分类研究，研究其不同压缩算法的原理、优缺点和应用状况。根据互联网上图像压缩算法的使用，而JPEG有损压缩技术的居多，因此本文就对JPEG压缩算法中DCT编码技术进行了实现。1.3 研究目标通过本课题的研究来探讨图像压缩算法理论基础以及对JPEG压缩技术中的DCT编码进行具体实现，并在算法上做一些可行的研究，为新标准的更好的应用打下一定的基础。1.4 研究意义多媒体是进入九十年代发展起来的全新的计算机最热门的研究领域之一。多媒体本身是一个先进计算机技术和视频、音频和通信等技术集成的产物。在目前，多媒体计算机所涉及的数据来源包括：文字、语音、音乐、声音、静止图像、电视图像、电影、动画、图形。如何处理、组织这些数据，提高处理、传输和存储的效率，从这些原始数据中去除冗余信息是多媒体计算机技术所要解决的问题之一。在这些数据中，图像数据量尤其巨大，同时由于受到通讯带宽的限制，所以图像压缩在数字电视、网络多媒体通信、会议电视、可视电话、遥感图像传程、图像数据库、自动指纹识别系统的指纹存储等应用中都起着至关重要的作用，其压缩技术一直是多媒体信息处理技术研究中最活跃的领域。数字图像占用的存储空间庞大，同时现在的带宽十分有限，如果数字图像不经过处理就在网络上进行传输，传输速度慢的让人难以忍受。网络带宽成为约束多媒体在网络上发展应用的瓶颈。要取得硬件设施方面的突破，造就宽带网尚需时日，所以目前只能从软件方面着手，对数字图像信息进行压缩。数十年此领域的研究结果表明，选用合适的数据压缩技术，有可能将原始文字数据量压缩到原来的二分之一左右，语音数据量压缩到原来的二分之一到十分之一，图像数据量压缩到原来的二分之一到六十分之一，或者更高。针对这种情况，如何利用新的技术对图像进行压缩，并且使之符合规范标准以便得到各个领域的支持，于是就这个问题，本论文针对图像压缩算法理论基础进行研究和分析，并在算法上做一些可行的研究，为新的标准及应用打下一定的基础。1.5 本文的组织本文从如下方面进行组织：先提出图像压缩基本知识，再从图像压缩算法进行分类研究探讨，然后对图像压缩算法中DCT编码进行具体实现，最后进行总结。第2章 图像压缩基本知识概述2.1 图像压缩减少表示数字图像时需要的数据量。基本原理：去除多余数据。以数学的观点来看，这一过程实际上就是将二维像素阵列变换为一个在统计上无关联的数据集合。图像压缩是指以较少的比特有损或无损地表示原来的像素矩阵的技术，也称图像编码。2.2 图像压缩的必要性信息时代带来了“信息爆炸”，使数据量大增。因此，无论传输或存储都需要对数据进行有效的压缩。在遥感技术中，各种航天探测器采用压缩编码技术，将获取的巨大信息送回地面。图像压缩是数据压缩技术在数字图像上的应用，它的目的是减少图像数据中的冗余信息从而用更加高效的格式存储和传输数据。图像压缩可以是有损数据压缩也可以是无损数据压缩。对于如绘制的技术图、图表或者漫画优先使用无损压缩，这是因为有损压缩方法，尤其是在低的位速条件下将会带来压缩失真。如医疗图像或者用于存档的扫描图像等这些有价值的内容的压缩也尽量选择无损压缩方法。有损方法非常适合于自然的图像，例如一些应用中图像的微小损失是可以接受的（有时是无法感知的），这样就可以大幅度地减小位速。图像压缩的主要目标就是在给定位速（bit-rate）或者压缩比下实现最好的图像质量。但是，还有一些其它的图像压缩机制的重要特性：可扩展编码(en:Scalability)通常表示操作位流和文件产生的质量下降（没有解压缩和再压缩）。可扩展编码的其它一些叫法有渐进编码（en:progressive coding）或者嵌入式位流（en:embedded bitstreams）。尽管具有不同的特性，在无损编码中也有可扩展编码，它通常是使用粗糙到精细像素扫描的格式。尤其是在下载时预览图像（如浏览器中）或者提供不同的图像质量访问时（如在数据库中）可扩展编码非常有用，几种不同类型的可扩展性：质量渐进（en:Quality progressive）或者层渐进（en:layer progressive）：位流渐进更新重建的图像。分辨率渐进（en:Resolution progressive）：首先在低分辨率编码图像，然后编码与高分辨率之间的差别。成分渐进（en:Component progressive）：首先编码灰度数据，然后编码彩色数据。感兴趣区域编码，图像某些部分的编码质量要高于其它部分，这种方法可以与可扩展编码组合在一起（首先编码这些部分，然后编码其它部分）。压缩方法的质量经常使用峰值信噪比来衡量，峰值信噪比用来表示图像有损压缩带来的噪声。但是，观察者的主观判断也认为是一个重要的、或许是最重要的衡量标准。由此可见，在这个信息爆炸的时代。数据压缩的作用及其社会效益、经济效益将越来越明显。反之，如果不进行数据压缩，传输或存储都很难实用化。而数据压缩的好处就在于：（1）快地传输各种信源(降低信道占有费用)-时间域压缩；（2）在现有通信干线上开通更多的并行业务(如电视、传真、电话、电报、可视图文等)-频率域的压缩；（3）降低发射机功率-能量域的压缩；（4）紧缩数据存储容量(降低存储费用)-空间域的压缩。2.3 图像压缩的可行性数据之所以能够压缩是基本原始信源的数据存在着很大的冗余度。一般来说，多媒体数据中存在以下种类的数据冗余1：（1）空间冗余：同一幅图像常有的冗余。因为规则物体或规则背景的表面物理特征具有相关性。（2）时间冗余：序列图像或言语数据常有的冗余。（3）信息熵冗余：信息熵：一组数据所携带的信息量。定义为：其中：N：数据类数或码元个数；Pi：码元Yi发生的概率。（码元：数字信号每一位的通称。通常又称为“位”或“Bit”。即可以用二进制表示，也可以用其它进制的数表示。）对于单数据量d：，其中b(Yi)是分配给码元Yi的比特数。为使d接近于或等于H，理论上应取：；但实际中很难估计出P0, P1,P2,., Pn-1,因此一般取：b(Y1)=b(Y2)=b(Y3)=.=b(Yn-1)。这样得到的d必然大于H，由此带来的冗余我们称之为信息熵冗余或编码冗余。（4）结构冗余：有些图像从大的区域上看存在着非常强的纹理结构。（5）认知冗余：对有些图像的理解与某些基础知识有相当大的相关性。如人脸图像有固定的结构。这些规律性的结构可由先验知识和背景知识得到。（6）其他冗余：如由图像的空间非定长特性所带来的冗余。2.4 图像压缩的意义 由于图像具有很大的信息量，在目前的计算机系统的条件下，要想实现实时处理，就必须对图像进行压缩，如果图像信息不经过压缩，则占用信道宽，使传输成本变得昂贵。2.5 代表性图像压缩方法2.5.1 霍夫曼（Huffman）编码霍夫曼编码使用于TIFF，JPEG等图像格式中。编码原理：首先统计需要编码的字符的出现概率，然后将短的码赋予出现频率高的字符，而将长的码赋予出现频率低的字符。优点：因为霍夫曼编码较为简单有效，所以得到了广泛的应用。缺点：霍夫曼编码要对原始数据扫描两遍：第一遍扫描要精确地统计出原始数据中每个值出现的频率；第二遍扫描是建立霍夫曼树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都比较慢。另外霍夫曼编码对于位的增减都反映敏感，如果增加或减少位，译码程序将无法正确译出后面的数据。2.5.2 算术编码编码原理：算术编码方法是将被编码的一则消息或符号串表示成0点和1之间的一个间隔，即对一串符号直接编码成0，1区间上的一个浮点小数，符号序列越长，编码表示它的间隔越小，表示这一间隔所需的位数就越多。信源中的符号序列仍然要根据某种模式生成概率的大小来减少问题。可能出现的符号概率要比不可能出现的符号减少范围小。因此，只增加减少的比特位。优点：算术编码不是为每个符号产生一个单独的代码，而是使整条信息公用一个代码。因而可进一步提高压缩比。缺点：它的实现较为复杂，常与其它有损压缩方法结合使用。2.5.3 RLE（Run Length Encoding）压缩算法RLE压缩算法使用于PCX，TIFF，BMP等图像格式编码原理：将一行中颜色值相同的相邻像素用一个记数值和颜色值来代替。例如：aabbbbcdddd经行程压缩处理后表示为2a4b1c4d。优点：当图像中存在很多块颜色相同的大面积区域，则RLE编码产生的压缩率是很高的。缺点：如果图像中很少有两个相邻的像素的灰度值相同时，则RLE编码非但不能压缩，还会造成处理后的图像数据量大于处理前的情况。2.5.4 LZW压缩算法（字典压缩算法）LZW压缩算法使用于GIF，TIFF等图像文件中。编码原理：LZW压缩算法不需要在编码之前构造码表，而是在压缩过程中逐步建立字典的。其基本思想是将每一个字节的值都要与下一个字节的值配成一个字符对，并为每一个字符设置一个代码。当同样的一个字符对再度出现时就用代号代替这一字符对，然后再用这个代号与下一个字符配对。在配对过程中，必须建立三个表格，分别为：字首表、字符表和代号表。所有字符对和代号都分别存入这三个表格中。优点：LZW不仅可以与RLE压缩算法一样对连续出现的相同字符进行压缩，而且可以对经常出现的由不同字符组成的字符串进行压缩，因此在压缩处理不同值数据串方面，LZW压缩算法优于RLE压缩算法。缺点：如果原始图像数据值中带有随机变化的“噪音图像”则很难利用LZW算法来压缩。2.5.5 Discrete Cosine Transform (DCT，离散余弦变换)编码编码原理：DCT属于变换编码，可用于图像处理的二维离散余弦变换。其定义如下：且，将预先分成小块的原始图像进行DCT变换后，高频部分包含了锐利的边缘信息，而低频部分包含了图像的主要信息，因此低频比高频更重要，可以通过量化步骤有选择性地消除或较粗糙地量化高频部分。需要注意的是，压缩不是在变换步骤取得的，而是在量化时取得的，并且是有损压缩，不可恢复。典型的DCT变换步骤是：输入图像将图像分块DCT量化熵编码压缩图Fig.2.1 DCT transform block diagram图2.1 DCT变换框图优点：DCT具有很强的信息集中能力和计算复杂性综合得比较好而得到了较多的应用，如：在JPEG中使用了DCT编码。第3章 霍夫曼（Huffman）编码3.1 霍夫曼算法编码原理及应用3.1.1 霍夫曼算法编码原理 霍夫曼(Huffman)编码是1952年为文本文件而建立，是一种统计编码，属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。 构造Huffman编码可以先将原始数据构造成一棵带权值的Huffman树。步骤如下： （1）将信号源的符号按照出现概率递减的顺序排列。 （2）将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。 （3）重复进行步骤1和2直到概率相加的结果等于1为止。 （4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。（5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。例如电文“ABACCDAB”，有4种字符。可以用两位二进制代码：00，01，10，11分别表示A，B，C，D。译码为”0001001010110001”。这样的二进制串长度为16位。比原始的字符串长度8*8=64远小。若采用Huffman编码，则得：A：1；B：000；C：01；D：001。译码字符串为：1000101010011。长度为13位，比16又小。对于应用文档来说，一般会有大量词汇重复出现，这样两者之间的差距也随着文件的大小与词汇重复出现的频率而越来越高2。3.1.2 霍夫曼算法的应用例1假设一个文件中出现了8种符号S0，S1，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3bit。假设编码成000，001，010，011，100，101，110，111。那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成000001111000001110010011100101000000001，共用了42bit。我们发现S0，S1，S2这3个符号出现的频率比较大，其他符号出现的频率比较小，我们采用这样的编码方案：S0到S7的码字分别为01，11，101，0000，0001，0010，0011，100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39bit。尽管有些码字如S3，S4，S5，S6变长了（由3位变成4位），但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。对于上述的编码可能导致解码出现非单值性：比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码字。因此，编码必须保证较短的编码决不能是较长编码的前缀。符合这种要求的编码称之为前缀编码。要构造符合这样的二进制编码体系，可以通过二叉树来实现3。（1）首先统计出每个符合出现的频率，上例S0到S7的出现频率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。（2）从左到右把上述频率按从小到大的顺序排列。（3）每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的、根节点，这两个叶子节点不再参与比较，新的根节点参与比较。（4）重复（3），直到最后得到和为1的根节点。Fig.3.1 Method using binary tree coding图3.1 用二叉树法实现压缩编码将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点路径中遇到的0，1序列串起来，得到各个符号的编码。可以看到，符号只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，这样，前缀编码也就构造成功了。这样一棵二叉树在数据结构课程中称之为Huffman树，常用于最佳判定，它是最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为：WPL=（W1*L1+W2*L2+W3*L3+Wn*Ln），N个权值Wi（i=1，2，n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1，2，n）。Huffman树得出的WPL值最小。例2在对一幅大小为100，672bytes8位BMP图像文件进行Huffman编码过程中，用以下步骤实现了压缩和解压缩算法。（1）扫描位图文件的全部数据（对应于调色板的编码），完成数据频度的统计。（2）依据数据出现的频度建立霍夫曼树。（3）将霍夫曼树的信息写入输出文件（压缩后文件），以备解压缩时使用。（4）进行第二遍扫描，将原文件所有编码数据转化为霍夫曼编码，保存到输出文件。解压缩则为逆过程，以下是编码和解码的实现算法。1）定义数据结构Node如下：Struct Nodelong freq;/该节点符号的频率值，初值为0 Int parent,/该节点父节点的序号，初值为-1 Int right;/该节点右子节点的序号，初值为-1 Int left;/该节点左子节点的序号，初值为-1Bmp tree511说明：之所以有511个节点，是因为每个字节可表示的符号个数为256个（对应于256种颜色）二叉树有256个叶节点，根据二叉树的性质总节点数为2*256-1=511个节点。这里用0255个元素来依次对应256种颜色。由第256以后的元素来依次对应形成的各个父节点的信息，即父节点的编号从256开始。2）按照前述的压缩步骤，先对欲压缩文件的各个符号的使用次数进行统计，填充于bmp Tree0255freq项内；在已有的节点中找出频率最低的两个节点，给出它们的父节点，将两个节点号填充于节点的Parent内。重复步骤直到根节点，建树工作完成。建树完成后进行编码，对每个符号从符号的父节点开始。若节点的父节点值不为-1，则一直进行下去，直到树根。回溯过程中遇左出0，遇右出1输出编码。Huffman 编码递归过程如下：Void Bmp Huff Code (int node ,int child)If Bmp tree node.parent!=-1;/父节点为-1的节点是树根Bmp Huff Code (Bmp tree node.parent,node);/若不为-1则递归溯溯 ntian11