【毕业学位论文】（Word原稿）基于分形理论的图像压缩方法的研究与实现-软件工程

硕士学位论文 （专业学位） 姓 名：赵磊 学 号： 1021170428 所在院系： 软件学院 职业类型： 工程硕士 专业领域：软件工程 指导教师：张惠娟 王冬青 副指导教师：王莹 二一二年八月 基于分形理论的图像压缩方法的研究与实现 A in 2010 2012 基于分形理论的图像压缩方法的研究与实现 赵磊 同济大学 学位论文版权使用授权书 本人 完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年 月 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 年 月 日同济大学 硕士学位论文 摘要 I 摘要 近几十年来，科学技术取得了飞速的发展。由计算机技术所带来的信息革命使人类由工业化的社会进入到了信息化的社会。在众多信息中，图像信息是人类认识世界及人类自身的重要源泉。然而，数字图像中包含的数据量十分巨大，给图像的传输、存贮以及读出造成了难以克服的困难。因此，对图像进行压缩就成了必要的工作。 早提出了一种新的分形压缩算法，成为图像压缩编码中的一次伟大变革，也是分形理论在图像编码中的创新性应用。后来 展 了 论，提出了局部迭代函数理论 (并在此基础上提出了一种自动的基于方块划分的分形图像压缩方案。此方案较好地利用了人的视觉特性，为分形图像压缩的研究带来了一次质的飞跃，也为该领域的研究工作注入了新的生机和活力。但出的分形编码方法中，数据字典来源于图像自身且是变化的，所得到的字典是一个非常有限的集合。 通过阅读大量文献资料和对前人的成果的研究，本文提出了一种新颖的分形图像压缩算法，即基于固定字典分形图像压缩方法，同时对图像块在匹配过程中使用的圆盘变换来代替基本分形压缩算法的八种仿 射变换。再对压缩字典进行适当的分类，使编码时间大大的缩短。通过计算机模拟实验结果显示，此算法具有较高的图像压缩比和高质量的重建图像，由于采取了固定字典的方式，编码速度提高很明显。在具体程序实现过程中，使用了多线程的编程方式，提高了程序的运行效率。 本文主要工作有以下几个方面： 首先，介绍了数据压缩的思想起源，在当今信息时代图像压缩技术研究的重要性和必要性。同时简单的介绍了图像压缩发展的现状和趋势以及分形图像压缩的基本概念。 第二，对分形理论的起源和发展阶段进行了详细的介绍；并对分形理论的数学基础分形空间、仿 射变换、压缩映射、迭代函数系统、不动点定理、拼贴定理做了简单介绍。 第三，介绍了图像编码的模型，根据模型 用 论进行了图像压缩编码，获得了极高的压缩比。重点介绍了 分形图像压缩方法，对 法的图像分割、码本构成、几何变换、编码实现、解码过程和实验同济大学 硕士学位论文 摘要 果进行详细的说明。 第四，详细的介绍了本文提出方法过程、主要思路和实现步骤。算法的主要过程是，首先是改变传统的编码方式使用动态变化的码本，由于传统的方式是依靠需要压缩的原始图像构成码本，因此码本每次压缩的时候都 需要重新构建，而这个过程需要花费很长的时间。作者使用固定字典作为编码时的压缩字典，只需要一次构建多次使用。其次在图像块匹配过程中，使用圆盘变换来代替八种仿射变换，这样增加了图像块匹配的准确度。最后对量化后的图像块进行适当的分类，加快了编码速度。 最后，对本文的工作进行了总结，并对存在的问题做了认真的分析，提出下一步的工作方向。 关键词： 分形；图像压缩；固定字典；迭代函数系统 n by to to to is of an of in is a of to of of is a of in by on FS to he an on of an of of a in as as to As a By a of of a is on of At of in in of of to of it to a of In of it of of In of on in s V of At of of a FS to a by on s of in a to is it of in on of to in a to to a we as as of By in of to it be It of et to to in to it is to a of 硕士学位论文 目录 V 目录 . 1 章 绪论 . 1 言 . 1 像压缩的可能性 . 1 像压缩编码 . 3 像压缩编码的评价标准 . 5 观标准 . 5 观标准 . 6 论文的主要内容 . 7 第 2 章 分形图像压缩原理与改进策略 . 9 形空间与迭代函数系统 . 9 形空间 . 9 仿射变换 . 11 压缩映射及不动点定理 . 11 形图像压缩的基本原理 . 13 图像模型 . 13 的仿射变换 . 14 带映射的局部迭代函数系统 (. 15 形图像压缩改进策略 . 18 定网格法 . 18 近搜索法 . 19 类搜索法 . 19 第 3 章 基于固定字典的分形图像压缩算法的实现 . 23 言 . 23 分形图像压缩方法 . 23 定字典的构造 . 30 非线性分形压缩模型 . 31 传统仿射变换的不足 . 31 同济大学 硕士学位论文 目录 改进八种仿射变换 . 32 法描述 . 36 编码算法 . 36 压缩算法实现 . 37 解码算法 . 37 解码算法实现 . 38 第 4 章 基于 的非线性分形压缩算法实现 . 40 逃逸时间 (法得到 . 40 分形图像压缩的非线 性模型 . 46 对 进行量化 . 46 实际像素的计算 . 48 图像块的分类 . 49 算法的实现 . 50 第 5 章 实验结果及分析 . 53 基于固定字典分形图像压缩实验结果分析 . 53 验设计 . 53 验数据分析 . 56 定字典压缩的进一步改进研究 . 57 于 的分形图像压缩的实验结果分析 . 57 验设计 . 57 验数据分析 . 59 于 的分形图像压缩进一研究 . 59 第 6 章 总结与展望 . 61 参考文献 . 63 致谢 . 67 个人简历 在读期间发表的学术论文与研究成果 . 68 第 1 章 绪论 1 第 1 章 绪论 言 近年来，随着多媒体计算机技术的发展，数据压缩技术的研究受到了人们越来越多地重视。特别是近年来计算机网络技术的广泛应用，更促进了数据压缩相关技术和理论的研究和发展。在计算机网络中，大量的信息 (特别是图像和语音等多媒体信息 )需要在较窄的信道中传输， 如何提高传输速度就成为一个关键问题，数据压缩是解决这一问题的有效方法。 当今社会是信息 爆炸 的时代，而信息的本质，就是交流和传播。一般来说，信息的传播不外乎以下两种情况：将信息从 此处 传输到 彼处 典型的 通信 概念，或者将信息从 现在 传输到 将来 所谓的 存储 问题。通过对信源进行压缩等处理，力求用少的数据传递最大的信息量，使信号更适合传输。因此，从信息论的角度看，信源编码的一个主要目的就是要解决数据压缩的问题，它构成了数据压缩的理论基础。数据压缩最初是信息论的一个重要研究课题，在信息论中称 为信元编码。数据压缩是以尽可能少的数据表示信源所发出的信号，减少容纳给定消息集合的信号空间 1。 像压缩的可能性 二十世纪后二三十年代，计算机技术和网络技术取得了飞速地发展，人类社会进入了前所未有的信息化时代。随着信息时代的来临，人们对通信业务的要求不断增长，大量的信息数据需要传输、存储和处理。 科学实验表明，人类从外界所获取的信息中 80%以上是通过视觉感知的。图像信息是人类认识世界和自身的重要源泉。相比于语音、文字等信息，图像包含的信息量更大、更确切，因而具有更广泛的适应性。然而图像数据的传输往往需要 占用很大的带宽，需要很大的存储空间，因而如何对图像数据进行有效地传输是一个极具挑战性的课题。图像压缩就是在没有明显失真的情况下。将图像的位图信息转变另一种能缩减数据量的表达形式。图像压缩的目的是以第 1 章 绪论 2 尽量少的比特表征图像，同时保持复原图像的质量，使它符合预定的应用场合的要求，提高有效性是图像压缩的首要目的 2。 图像数据之所以能进行压缩主要有以下几个方面的原因： 首先，原始图像数据是高度相关的，存在很大的冗余度。数据冗余造成比特数浪费，消除这些冗余可以节省码字，达到数据压缩的目的。一幅画中通常包含较多的可见景 物，而同一景物表面上各采样点的灰度值之间往往存在着空间连贯性，即相邻像素之间有较大的相关性，这称为空间冗余；序列图像是由一组连续画面组成，其中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在空间位置略有不同，这就产生了大量的数据冗余，称为时间冗余；多光谱遥感图像各谱间有相关性，这称为频率域冗余；给定图像某一些区域，往往可以在该区域附近找到一个更大的区域，两者在仿射变换下相等或非常接近，这就是图像的局部相似性冗余。图像中的某一个像素的灰度值，总是和其周围其它灰度值有某种关系，它在统计意义上服从某些规律 ，利用这种形式也可以减少表示图像的数据量，因而称之为统计冗余。 其次，若用相同的码长表示出现概率不同的符号也会造成比特数的浪费，这成为符号冗余。如果采用可变长编码技术，对出现概率高的符号用短码字表示，对出现概率低的符号用长码字，就可消除符号冗余节省码字。 再次，允许图像编码有一定的失真也是图像可以压缩的一个重要原因。在许多应用场合，并不要求经过压缩及复原之后的图像和原图像完全相同，而允许有少量失真，只要这些失真并不被人眼所察觉，在许多情况下是完全可以接受的。这就为提高压缩比提供了十分有利的条件。人类的视觉系 统对图像场的敏感性是非均匀和非线性的，在多数应用中，如果能充分利用人眼的视觉特性，就可以在保证所要求的图像主观质量的前提下实现较高的压缩比，这就是利用了视觉冗余。 此外，在某些特定的应用场合，编码对象的某些特性可预先知道。此时，可以利用对编码对象的先验知识对编码对象建立模型，通过摄取模型参数，对参数进行编码而不对图像直接进行编码，可以达到非常高的压缩比。这就是模型编码的基本思想，这里利用了知识冗余 3。 第 1 章 绪论 3 像压缩编码 自从 1948 年 表第一篇图像压缩论文开始，图像压缩工作历经近六 十年，形成了众多图像压缩方法。大体上可以分为两大类：无损编码 (有损编码 (在不同场合下无损编码也称无噪声编码，熵编码，有损编码也称为限失真编码 3。 （ 1） 无损编码 无损编码是理想的压缩编码 (无信息丢失 )，也称位保持压缩或可逆压缩。它的目标是在图像没有任何失真的前提下使数码率最小。在无失真压缩后重建的图像中每个像素的数值都与原图像中的对应像素的数值相等。显然，无失真压缩中无信息丢失，是理想的压缩。但是采用这一类方法，只能作少量的图像压缩。无损压缩广泛应 用在文本数据和对图像失真度 (质量 )要求较高的领域，如医学和卫星图片，压缩比一般为 1:。对于人像、自然景物等一些结构复杂、细节丰富、灰度层次较多的数字化图像，无损压缩技术难以发挥较大作用。 （ 2） 有损编码 又称为不可逆压缩。为进一步提高压缩率，常采用有损压缩方法。其基本原理在于：人类视觉系统 (图像各种信息 (如位置、频率和指向等 )的感知具有不均匀性，对一些信息的损失不甚敏感，通过改变图像的表现方式，损失一部分次要信息，突出图像中的冗余性，再用合适的方法发现并消除这种冗余，便可获得更高的压缩 比。由于变形过程中曾丢掉了一部分图像信息，因而解码结果不能完全恢复原始图像。尽管如此，只要把图像失真度限制在某个容许限度内，就能保证解码图像与原始图像的差异不被人眼所感知或虽然有感知但失真仍在可接受范围内。有损压缩编码的主要方法有：预测编码、变换编码、向量量化、模型编码、子带编码和将上述几种技术结合而成的混合编码等，所有这些方法 。 第 1 章 绪论 4 表 常见的压缩编码算法 都可获得比无损压缩更高的图像压缩比。现代压缩编 码应用中，无损压缩常与有损压缩方法混合使用，将无损压缩作为有损压缩方法的后处理过程。如准就用 算术编码对经 换再量化后的编码符号作进一无 损 编 码 行程长度编码 码 自适应 码 固定 码 算术编码 码 有 损 编 码 预测及内插编码 点线性预测 帧内域预测 帧间编码 正交变换编码 换 换 换 换 矢量变换编码 分离 搜索 层编码 位平面法 四元树 逐次生成法 频带分割编码 分频带法 块分割法 分形编码 小波编码 模型编码 域分割编码 分析合成编码 识别合成编码 基于知识的编码 第 1 章 绪论 5 步处理。表 1出了一些常见的压缩编码算法。 像压缩编码的评价标准 在图像处理领域中，如何评价一幅经过处理的图像的质量好坏，如何评估某个图像处理算法的优劣一直是人们关心的焦点，然而图像质量评价没有统一的测度。对于图像压缩编码算法也不例外，也没有严格评价其算法优劣的标准。对解压缩图像的客观评价是人们非常关心的问题。目前普遍采用基于最小均 方误差准则的峰值信噪比 为衡量解压缩图像质量的指标。虽然 义明确、计算简单 ,但是人眼接触的是解压缩后的图像，而 有考虑人类的视觉感知特性。衡量解压缩图像质量不仅要客观评价，而且要符合人眼的主观评价，用人眼对图像打分而得到 3。 观标准 当所损失的信息量可用编码输入图与解码输出图的函数表示时，就说它是基于客观保真度准则的 (客观标准 )。客观标准是建立在原图与重建图对应的像素的误差上的，可分为多种。最常用的一个准则是输入图与输出图之间的均方误差 ( 设原图像为 ),( 解压 缩后图像为 ),( i 取值范围从 1 到 N， j 取值范围从 1 到 M。于是新旧图像的均方误差 表示为 : 211),(),(1 规范化均方误差为： 中 2f= 211),(1 对数信噪比 ： 0=第 1 章 绪论 6 设 ,i =1,2,L ,N;j =1,2,L ,M，则峰值信噪比： 010(),(),(12112m a x 在一般的实验中，采用下面的峰值信噪比 : 010(),(),(12552112观标准 客观标准提供了一种简单、方便的评估图像质量损失的方法，但很多解压图最终是供 人看的。在这种情况下，用主观的方法来测量图像的质量更为合适。其方法多采用平均判分法 即组织足够多的评判人员，通过观察来评定图像的质量，观察者给评定的图像打上一定的质量等级，比较损伤程度及与原图进行比较等方法。根据不同的质量打上 5 级、 6 级或 7级的评分制，最后用平均的办法得到图像的分数，表 1出两种典型的评分标准。这样的评分虽然很花时间，但比较符合实际。目前，国际的标准都是采用主观评价。主观评价与客观评价之间有一定的联系，但不能完全等同，由于客观评价比较方 便，很有说服力，故在论文中常被采用，但主观评价很直观，符合人的视觉效果，比较实际，在制定国际标准时常采用主观评价。 不过，主观评价有几个显著的不足之处： (1) 观察者一般需要是一个群体，并且经过培训以准确判定主观评测分，人力和物力投入大，为时较长； (2) 图像内容与情节千变万化，观察者个体差异大，容易发生主观上的偏差； (3) 主观评价无法进行实时监测； (4) 仅仅只有平均分，如果评测分数低，无法确切定位问题出在哪里。 第 1 章 绪论 7 表 得分 第一 种评价标准 第二种评价标准 5 非常好 感觉不到失真 4 好 感觉到失真，但没有不舒服感觉 3 一般 稍有感觉到不舒服 2 较差 不舒服 1 差 非常不舒服的感觉 论文的主要内容 论文共分为 6章。 第 1章：简要介绍了论文的研究背景和研究的意义与必要性，回顾了图像压缩的发展概况，还介绍了图像压缩的分类以及一些常用经典的图像压缩编码方法，主要介绍的是分形压缩编码。 第 2章： 对 分形 和分形图像压缩的 基本概念以及分形、不动点定理、吸引子、迭代函数系统以及局部迭代函数系统等 提出改进策略 。 第 3章：提出了基于固定字典的分形图像压缩方法 ，并通过实验验证了算法的有效性 第 4章：提出了基于 形图像压缩方法，并通过实验验证了算法的有效性。 第 5章： 对实验结果进行认真分析。 第 6章：对全文进行总结和对下一步工作的设想 第 1 章 绪论 8 第 2 章 分形图像压缩原理与改进策略 9 第 2章 分形图像压缩原理与改进策略 分形理论是二十世纪七十年代中期由美国科学家 立，其诞生的标志是 1975 年发表的专著： 它是近代非线性科学研究中的一个非常活跃的分支，在地理、物理、地质、材料科学、信息科 学、生命科学、工程技术等各个领域，甚至在经济和社会