《[毕业设计 论文 精品]基于信源模型图像编码的数据压缩算法的研究与实现.doc》由会员分享，可在线阅读，更多相关《[毕业设计 论文 精品]基于信源模型图像编码的数据压缩算法的研究与实现.doc（54页珍藏版）》请在三一文库上搜索。
1、目 录 摘要I ABSTRACT.II 第一章 绪论.1 1.1 课题研究的意义.1 1.2 课题研究的现状.2 1.3 课题研究的内容和目的 .3 1.4 图像压缩的相关概念 .4 第二章 基于信源模型图像压缩的综述.7 2.1 基于信源模型的图像压缩技术分类.7 2.2 分形图像编码 .8 2.2.1 分形图像编码的基本原理8 2.2.2 分形图像压缩的基本算法.9 2.2.3 分形图像压缩的特点.12 2.3 模型基图像编码 .13 2.3.1 模型基图像压缩的基本思想.14 2.3.2 人脸模型化.15 2.3.3 模型基编码的特点17 第三章 矢量量化图像编码的研究.18 3.1 矢
2、量量化的定义 .18 3.2 量化的关键技术 .19 3.2.1 码书设计.19 3.2.2 码字搜索.21 3.2.3 索引分配.22 3.3 相关改进算法 .23 3.3.1 改进的覆盖聚类算法.23 3.3.2 改进的 SA-LBG 算法 24 第四章 软件系统的整体设计与实现.29 4.1 软件系统的整体设计及模块实现说明.29 4.2 算法的 VC+实现的简单说明36 4.3 矢量量化编码的性能和复杂度 .37 4.4 算法的结果 .38 第五章 结束语.39 参考文献.40 致谢.42 附 录.43 I 摘要摘要 伴随着科技的发展，社会的进步，在多媒体压缩范畴里，人们认识到对信源的
3、 建模表达能使压缩技术取得更大的进展。于是产生了一系列的基于信源模型的图像 压缩技术。 本文在概要论述基于信源模型图像压缩技术的基础上，重点研究了矢量量化图 像压缩。矢量量化一直是图像编码领域最常用的有损压缩技术之一，具有信息理论 概念上的最优性和实际应用的简易性。在编码过程中，矢量量化编码器在码书中为 每个输入图像块矢量寻找最匹配码字，并将其索引号而非码字本身传送到解码端， 因而此编码算法能提供较高的压缩比，解码过程也只需进行简单的查表操作。论文 主要的研究工作体现在以下几个方面： 系统地综述了矢量量化的三大关键技术，即码书设计、码字搜索和码字索引分 配。在此基础上提出了改进的LBG算法。
4、同时还介绍了分形图像压缩和模型基图像压缩的基本原理及算法，旨在深入了 解信源模型图像压缩的技术。 关键词：信源模型，矢量量化，分形图像压缩，模型基图像压缩 II ABSTRACT With the development of technology, and the progress of our society, in the multimedia compression category, people realized that the expression on source model can make the compression technology have greater
5、progress. As follows, a series of image compression technology based on the source model have been created. The conceptions and algorithms for image coding based on source model, and focuses the research on vector quantization image compression algorithms is been summarily introduced in this thesis.
6、 Vector Quantization(VQ) has long been established as an efficient lossy compression technique popular in image coding field due to its optimality in information theory and simplicity in practical applications. By finding the nearest codeword in a codebook for each input image block vector and trans
7、mitting the codewords corresponding index to the decoder, VQ coding algorithm can usually provide high compression ratio and a simple table-look-up decoding operation. The main research work and contributions of this thesis are as follows: Firstly, this thesis systematically summarizes three key tec
8、hniques of basic VQ, i.e. codebook design, codeword search and codeword index assignment, and some advances of LBG algorithms are presented. At the same time, the conceptions and algorithms for Fractal image coding and Model Based image coding is also been introduced. The purpose is to deep understa
9、nd the technique of source model image compression. KEY WORDS: source model，vector quantization，fractal image coding，model based image coding 基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论 1 第一章第一章 绪论绪论 1.11.1 课题研究的意义课题研究的意义 每天我们都是在报纸、杂志、书籍、电视、各种小册子等大量的图像信息包围 中度过的。这些图像包括文字、照片、图表、插图等，它使我们感到安适和生活情 趣。 据统计，人们通过感觉器官收集到的
10、各种信息中，视觉约占 65%，听觉约占 20%， 触觉约占 10%，味觉约占 2%1。随着信息处理技术的发展，出现了文本、声音、图 像、视频等大量不同类型的听觉和视觉媒体数据。进入信息时代以后，人们越来越 多地依靠计算机来获取和利用各类媒体数据。然而这些数据由于数据量庞大，在存 储空间和传输带宽有限的情况下，这些数据的存储和传输存在瓶颈。为此，人们通 常要对这些媒体数据作压缩处理，以提高存储和传输效率，降低设备成本。在保证 听觉和视觉质量的前提下，人们往往希望能够以尽量少的空间和尽量小的比特率来 存储和传输各种声音、图像数据。然而在相同的压缩编码技术下，信息理论概念下 的编码质量和压缩比往往是
11、一对矛盾。因此如何建立新的语音、图像和视频的分析 模型，从而改进压缩编码算法长久以来一直是信号处理领域的研究热点。 图像视频通信的发展长期以来落后于语音通信。而在多媒体数据通信的发展趋 势下，图像压缩编码技术的研究和应用越来越引人瞩目。人们对图像压缩的研究兴 趣可以追溯到 62 年前。最初在这一领域研究的焦点集中在如何建立一种模拟的方 法以便减少视频传输所需的带宽。这一过程称为带宽压缩。数字计算机的出现和后 来先进的集成电路的发展，导致了这方面研究的重点从模拟方式转移到数字压缩方 法上来。随着几种关键性的国际图像压缩标准的正式采用，这一领域在实际应用方 面有了重大的发展。当前，图像压缩被认为是
12、一种“开放技术”，已经被广泛用于 现代通信业务、工程应用、媒体传播、医疗服务和商务应用等诸多领域中。 对声音、图像、视频等多媒体信息的压缩有两条思路，要么采用成熟的通用数 据压缩技术进行压缩，要么根据媒体信息的特性设计新的压缩方法。然而在通用数 据压缩领域技术已经相当的成熟，很难有大的突破，与此同时，多媒体信息日益成 为主流信息形态，数据压缩技术特别是专用于图像、音频、视频的数据压缩技术还 基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论 2 有相当大的发展空间毕竟，人们对信息数量和信息质量的追求是永无止境。随 着电子信息产业的发展的牵引和相关科学技术进步的推动，科技界特别是许多跨
13、国 公司对于研究更高效图像压缩技术的热情越来越高涨，观念也在不断更新，新一轮 的技术竞争也愈演愈烈。 今天，从事基于信源模型的图像编码的数据压缩课题的研究也正是在此思潮的 引领之下开展的，希望通过笔者的努力能为这一技术的发展做出应有的贡献。 1.21.2 课题研究的现状课题研究的现状 严格意义上的数据压缩起源于人们对概率的认识。当我们对文字信息进行编码 时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长 的编码，总的编码长度就能缩短不少。信息论之父 C. E. Shannon 第一次用数学 语言阐明了概率与信息冗余度的关系。在 1948 年发表的论文“通信的数学理论（ A
14、 Mathematical Theory of Communication ）2中， Shannon 指出，任何信息都 存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不 确定性有关。 Shannon 借鉴了热力学的概念，把信息中排除了冗余后的平均信息 量称为“信息熵”，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉 为信息论的开山之作，信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲， 数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段 精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限， 即在一定的概率模型下，无
15、损压缩的编码长度不可能小于信息熵公式给出的结果。 1948 年，Shannon 在提出信息熵理论的同时也给出了一种简单的编码方法 Shannon 编码。随着科学技术的不断进步，出现了 Huffman 编码3。编码效率高， 运算速度快，实现方式灵活，从 20 世纪 60 年代至今，在数据压缩领域得到了广 泛的应用。不过，Huffman 编码所得的编码长度只是对信息熵计算结果的一种近似， 还无法真正逼近信息熵的极限。正因为如此，现代压缩技术通常只将 Huffman 视 作最终的编码手段，而非数据压缩算法的全部。1976 年， J. Rissanen 提出了一 种可以成功地逼近信息熵极限的编码方法算
16、术编码3。之后，人们又将算术编 码与 J. G. Cleary 和 I. H. Witten 于 1984 年提出的部分匹配预测模型（ PPM ）相结合，开发出了压缩效果近乎完美的算法。对于无损压缩而言， PPM 模型与 算术编码相结合，已经可以最大程度地逼近信息熵的极限。看起来，压缩技术的发 展可以到此为止了。不幸的是，事情往往不像想象中的那样简单：算术编码虽然可 以获得最短的编码长度，但其本身的复杂性也使得算术编码的任何具体实现在运行 时都慢如蜗牛。即使在摩尔定律大行其道，CPU 速度日新月异的今天，算术编码程 序的运行速度也很难满足日常应用的需求。后来又相继出现了 LZ77、 LZ78
17、及 基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论 3 LZW。使得压缩技术又上了一个大的台阶。 伴随着科技的发展，社会的进步，人们逐渐认识到多媒体的数据压缩成为一项 亟待解决的技术。70 年代末 80 年代初，人们逐渐意识到，对于多数灰度或是彩 色图像乃至声音文件，没有必要忠实地保留其所有信息，在允许一定的精度损失的 情况下，可以实现更为有效的压缩方法。到 80 年代末，许多人已经在这一领域取 得了不小的收获，设计出了一批在压缩效果上让人惊讶不已的声音和图像压缩算法。 在此基础上，国际标准化组织( ISO )和 CCITT 联合组成了两个委员会。委员会的 名字我们大概都已经非常
18、熟悉了：静态图像联合专家小组( JPEG )和动态图像联合 专家小组( MPEG )。JPEG 的压缩目标是静止图像（灰度的和彩色的） ，MPEG 的目 标则是声音和视频。但他们的基本思路是完全一样的，即保留媒体信息中最有规律、 最能体现信息主要特征的数据，而略去其他不重要的数据。他们都取得了令人赞叹 的成就。 就在多媒体压缩范畴里，人们认识到对信源的建模表达能使压缩技术取得更大 的进展。事实上，压缩音频、视频信号的许多很有潜力的方法，实质上都是通过对 信源的分析，将其分解成一系列更宜于表示的“基元”或从中提取若干具有更重要 意义的参数，编码仅对这些基本单元或特征参数进行。而接受端则借助于一定
19、的规 则或模型，按一定的算法将这些基元或参数再综合成原信源的一个逼近。这也就是 基于信源模型图像编码的数据压缩。原则上，压缩编码的极限结果是通过那些能够 反映信号产生过程最早阶段的模型而得到的，比较鲜明的例子就是人类发音的“清 晰声带-声道模型” ，它把注意焦点从 LPC 分析扩展到了声道区分析，原则上为甚 低码率矢量化提供了强得多的定义域，并允许更好的处理声带-声道相互作用，而 简化的激励后滤波模型忽略了这一现象。另一个例子就是人脸的线框模型，它为压 缩可视电话这类以人脸为主要景物的序列图像提供了一个强有力的手段。仅就图像 编码而言，对信源模型的描述正从波形参数向几何特征发展。为了便于研究和
20、加深 理解，学者们对其进行了分类，大致分为如下两类：第一代图像编码压缩（又称波 形基编码） 、第二代图像编码技术。 1.31.3 课题研究的内容和目的课题研究的内容和目的 本课题要求完成如下工作： 1. 对数据压缩的基本理论、技术标准、评价方法进行研究和分析； 2. 对基于信源模型图像编码的数据压缩算法及其衍生算法进行逻辑上的分析 和比较； 3. 对这些算法进行编程实现，并在实践中进行分析比较 4. 从这些算法中选择一个较优算法，并以此算法实现一个完整的压缩软件。 基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论 4 1.41.4 图像压缩的相关概念图像压缩的相关概念 1.4.11
21、.4.1 图像压缩的对象与及方式图像压缩的对象与及方式 保存图像信息的数字文件通常包含着数量可观的冗余信息和大量的不相干信息 4。其中冗余信息是指在图像文件中多余或重复的信息；不相干信息是指图像信息 中不重要，无关紧要的部分。把这部分信息去除后不影响人们可以感知的部分。图 像压缩的对象就是这两种信息。图像压缩技术利用数据固有的冗余性和不相干性， 采用合适的压缩策略将一个大的数据文件转换成较小的文件，这个压缩后的文件可 以在以后需要的时候通过解压缩以精确的或近似的方式将原文件恢复出来。两个文 件的大小之比(压缩比)确定了压缩的程度。 图像压缩的方式可分为无损压缩和有损压缩两种。无损压缩算法去除的
22、仅仅是 冗余信息，因而可以在解压缩时精确地恢复原图像。无损压缩通常应用于对图像数 据有特殊要求的环境中，例如有些图像，以及所有的可执行文件，不允许进行任何 修改，在这种情况下，只能对它们进行无损压缩。对于多数图像来说，为达到较高 的压缩比，保真度的轻微损失是可以接受的，这时就需要采用有损压缩算法。有损 压缩算法把不相干的信息也删除了，因此只能对原图像进行近似地重构，而不能精 确地复原。人们在选择或设计算法时，往往是在算法的复杂度(易实现性，计算量 等)和解压缩图像的保真度之间进行折衷，从而在保持较小的存储空间和传输负担 的同时保持可接受的图像质量。 1.4.21.4.2 速率速率失真理论失真理
23、论 速率失真理论5旨在寻求一种联系失真度和码速率的编码策略，它是有损 压缩编码的理论基础。香农的信息论告诉人们，只要码速率不超过信道容量，符号 就能以任意小的差错概率在该信道中传输。在数学上，速率失真函数 R（D)定义为 在给定失真 D 的条件下，系统所能够达到的最小码速率。对于幅值离散的信源， R(D)5定义如下： （1-1）() ( /) (, ) XY P X P YX d X YD 其中 （1-2）( )() ( /) X Q YP X P YX 平均失真满足条件: （1-3）() ( /) (, ) XY P X P YX d X YD 其中 d(X,Y)是失真测度，它表示输出采样值
24、 Y 再现原始信源采样值 X 所引入的失真， P(Y/X)表示在己经发送 X 的情况下接收到 Y 的概率。R(D)的单位为比特/采样。相 基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论 5 应地，速率失真函数的逆函数 D(R)表示在给定速率不超过 R 的条件下，系统所 能够达到的最小失真。D(R)和 R(D)所给出的编码性能极限，适用于所有信源编码方 法。在实际应用中，速率失真函数常常作为一个理论下界与实际编码速率相比较， 分析系统还有多大的改进余地。对于图像编码而言，在客观评价标准下，编码性能 (峰值信噪比/比特率)曲线同 D(R)曲线的接近程度成为判断编码算法好坏的一个标 准
25、。 1.4.31.4.3 图像质量的测度图像质量的测度 对人类而言，图像信息的接收和预处理都要通过人眼来完成，图像质量好坏的 判断自然和人眼的视觉特性密切相关。在图像的有损压缩过程中，部分视觉信息会 在编码过程中损失而引起人眼视觉上的差异。这种感官上的差异的大小可以反映图 像质量退化的多少。然而，视觉特性的复杂性决定了人眼对不同形式的视觉信息损 失的敏感程度也不同，使得视觉差异很难用量化的形式展示出来。人们把这种纯粹 主观感觉上的图像质量称作图像的主观视觉质量，并提出了一些衡量图像质量的主 观评价标准。 但由于人类视觉敏感方式的复杂性，人们对图像质量的主观评价方法的认识和 研究仍然欠缺，这使得
26、一些图像客观评价标准得到了广泛使用一般来说，客观评价 标准考虑的是原始图像和重构图像之间像素值上的差异，不同的客观评价标准同主 观感受的相关性也不同。虽然客观评价不如主观评价更符合人眼感受特性，但它形 式简单、计算方便，同时也能较好的反映图像信息的损失量。最常用的测度函数3 有均方误差(Mean Squared Error，MSE)、信噪比(Signal Noise Ratio, SNR)和峰 值信噪比(Peak Signal Noise Ratio，PSNR)，分别定义如下： MSE= （1-4） 11 2 00( ) * PQ ijij ij xy P Q SNR=10* （1-5） 11
27、 2 00 1011 2 00 log () PQ ij ij PQ ijij ij x xy PSNR=10* （1-6） 2 10 log L MSE 其中 P 和 Q 分别为表示图像的高度和宽度(即在垂直方向和水平方向上的像素数目)， L 为图像灰度的总阶数，和分别表示在坐标（i,j）处的原始图像像素值和重 ij x ij y 构图像像素值。0iP-1 0jQ-1。 基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论 6 1.4.31.4.3 图像编码性能评价标准图像编码性能评价标准 各类压缩编码算法因各自特点而适用于不同的图像编码场合。在实际应用当中， 通常考虑如下几个评价标
28、准： (1) 图像压缩比。通常用比特率(Bit-rate)来衡量压缩比的大小，它定义为每 个像素占有的比特数(单位是 bits per pixel, bpp)，显然压缩后图像的比特率越 小，压缩比越大。 (2) 图像质量。在客观评价标准下常用信噪比(SNR)和峰值信噪比(PSNR)的高 低表示重构图像质量的高低(单位均为 dB)。 (3) 编码复杂度。包括时间复杂度和空间复杂度，在算法实现时往往表现为乘 法、加法的操作次数和算法占用存储空间的大小。 一般来说，以上三个评价参数是互相矛盾的，不同的算法因不同的应用要求会 在这三个参数上有不同的偏重。具体应用中，编码速率经常受到限制，设计压缩系 统
29、目的是在可承受的复杂度条件下取得较好的编码质量。对给定信源来说，用时间 和存储量来描述的复杂度通常会随比特率的降低而增高。因此，好的编码算法应该 能在最大程度上取得这三方面的改进和折衷。在对编码算法的选取上，人们必须在 系统复杂度和性能，成本和保真度之间寻求折衷。 基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述 7 第二章第二章 基于信源模型图像压缩的综述基于信源模型图像压缩的综述 2.12.1 基于信源模型的图像压缩技术分类基于信源模型的图像压缩技术分类 NJayant 指出：原则上，压缩编码的极限结果是通过那些能够反映信号产生 过程最早阶段的模型而得到的
30、，比较鲜明的例子就是人类发音的“清晰声带-声 道模型” ，它把注意焦点从 LPC 分析扩展到了声道区分析，原则上为甚低码率矢量 化提供了强的多得定义域，并允许更好的处理声带-声道相互作用，而简化的激励 后滤波模型忽略了这一现象。另一个例子就是人脸的线框模型，它为压缩可视电话 这类以人脸为主要景物的序列图像提供了一个强有力的手段。仅就图像编码而言， 对信源模型的描述正从波形参数向几何特征发展。为便于研究和加深理解，学者们 尝试按表 2.1 进行分类3。 表 2.1 基于信源模型的图像编码技术分类 类别信源模型编码信息典型编码技术 1单个像素像素的色彩PCM 2统计相关的像素块像素或像素块的色彩预
31、测、变换、 子带、小波分 析、VQ 等 3平移运动的像素块像素块的色彩和运动矢量运动补偿的混 合 DPCM/DCT 编 码 4结构的自相似IFS 代码运动分形编码 5运动的区域每个区域的轮廓、纹理及 运动参数 区域基编码、 分割基编码 6未知的运动物体每个物体的形状、运动和 色彩 物体基编码 7已知的运动物体物体形状、运动、色彩及 行为表情单元 知识基编码、 语义基编码 从这个表中我们对信源模型图像编码的简史有个大致的了解，学者们又把它们 基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述 8 做了更具体的分类，认为表 2.1 中的 1-3 类技术属于波形基编码
32、，称之为第一代图 像编码技术；而第 4-7 类则称之为第二代图像编码技术。其中第 3 类是第一代图像 编码技术的典型代表，编码效率较高，时延短、技术成熟，被现有的多种视频编码 标准所采纳。第 5-7 类技术统称模型基编码，核心是对模型本身或模型参数进行编 码传输，如果模型足够好，对模型的描述又足够成熟，那么模型基编码就有很强的 利用性。 2.22.2 分形图像编码分形图像编码 1987 年，美国乔治亚工学院的数学家 M.F.Barnsley 在题为“Chaotic Compression” 6的论文中提出了分形图像编码的概念之后，在 1988 年 M.F.Barnsley 和 A.D.S lo
33、an 发表了一篇题为 “A Better Way to Compress Images”7的文章，在此文中，他们首次将 M.F.Barnsley 提出的 IFS 理论应用到 图像压缩编码中，并获得了较好的压缩效果，压缩比高达 10000: 1。但是这个方法 存在的最大不足就是在压缩过程中需要专业技术人员的人机交互操作。尽管如此， 它的极有希望的压缩效果和压缩比使人们看到了用分形理论解决图像压缩问题的前 景和希望。 1990 年，M.F.Barnsley 的博士生 A.E.Jacquin 首次提出了一种全自动的分形 图像压缩方法，完成了分形图像压缩从需人工参与编码到自动编码的飞跃，从此分 形图像
34、编码作为一种很有希望的编码方法列入计算机图像自动编码的行列，得到了 人们的普遍关注。各国学者纷纷效仿 A.E.Jacquin 的压缩方案提出各种各样的改进 方案，从而掀起了分形图像编码的高潮。 2.2.12.2.1 分形图像编码的基本原理分形图像编码的基本原理 分形图像压缩，利用了分形理论中的迭代函数系统理论。编码的过程是依据拼 贴定理，通过给定的图像，寻找一组压缩仿射变换，使其构成的迭代函数系统逼近 给定的吸引子，然后记录下相应参数，并且用这些参数作为图像的编码进行存储和 传输。解码过程首先是由存储或传输的参数确定一组压缩仿射变换，进而构造一个 迭代函数系统，并求出这个迭代函数系统的吸引子，
35、根据吸引子定理，该迭代函数 系统的吸引子就是原始图像的近似解码图。这就是分形图像压缩的基本原理和 方法。其编解码原理框图如图 2.1 所示。 基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述 9 图像分块 对每一块寻找 近似不变集 保留 IFS 码 编码 恢复 IFS 码 IFS 代码迭代 生成不变集 图像合并恢复图像 解码 原始图像 图 2.1 分形编解码原理框图 2.2.22.2.2 分形图像压缩的基本算法分形图像压缩的基本算法 1990 年，A.E.Jacquin 发表了一种基于方块划分的分形图像压缩方案8。这是 一种基于 IFS 的压缩编码方案，准确地
36、说是基于 Local IFS 的压缩方案。该方案突 破了 M.F.Barnsley 设计的方案，将图像分割成两种大小固定的方块，然后去找这 两种方块之间的相似性，由于不再与整幅图像比较，而放宽为原始图像的一部分， 从而使该方案能够自动对任意图像进行编码。首次实现了自动分形图像编码方法。 以后其他学者提出的方案都是基于此方案的改进，因此 A.E.Jacquin 的方案被公认 为最基本的分形图像编码方案3。 在 A.E.Jacquin 提出的编码方案中，分形图像编码分为三个步骤: (1)对待编码图像 I 进行分块。 把大小的待编码图像 I 分割成若干个不重叠的、大小为的子块，称NN BB 之为值域
37、块，记为。这些值域块的并集能够完全的覆盖整个图像，即 N RRR, 21 当，且。然后再把待编码图像分割成若干ji ji RR N RRRI 21 个可以重叠的、大小为的子块，称之为定义域块，记为。要求KK M DDD, 21 ，一般来说。对原始图像的划分如图 2.2 所示： BK BK2 (a)值域块 (b)定义域块 i R j D 图 2.2 分形编码分块表示图 基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述 10 (2)找到合适的迭代函数系统。 跟据 LIFS 理论，寻找一个 IFS，, 2 , 1, 2 , 1|:,MjNiRDwH iji 使得即和
38、 I 在 Hausdorff 测度下尽可能的接近，因为 )(,( 1 ji N i DwIh )( 1 ji N i Dw ，所以实现时，只需要与在 Hausdorff 测度下尽可能 N RRRI 21 )( ji Dw i R 的接近。因此，分形图像编码的关键是如何找到最佳的仿射变换以和定义域块。 j D 在实际应用中，仿射变换难以找到、存储，而是把仿射变换等价分解为几何变 i w i w 换、同构变换和灰度变换，即 i i i G （2- iiii Gw 1） 几何变换:我们用来表示起始位置为，大小为的定 i ),(KjiD ddj ),( dd jiKK 义域块。用来表示经过抽样后，起始
39、位置为），大小为 j D),(LjiD ddj dd ji , ( 的定义域块。通过下式:LL j D （2- 4/ )( 1)(, 1)(1)(),()(, 1)()(),( , jJiIjJiIjJiIjJiIji ddddd jdid 2） 要求： 1, 1 , 0,LjiiiiI d 2)(jjjJ d 2)( 几何变换把大小为定义域块几变换大小为的定义域块，即KK LL j D 。这里的。)( jij DDLK 2 同构变换：同构变换就是 4 种对折、4 种旋转变换。经过同构变) 7 , , 2 , 1(i i 换后，产生。即。 j D )()( jiijij DDD 灰度变换:灰度
40、变化包括比例因子 和补偿因子，对做灰度变换 i Gso j D ，产生。oDsDG jji ) ( j D 对每一个定义域块经过以上三种变换，就得到一个数量很大的定义域池。对值 域块的分形编码就是寻找最佳，以及在定义域池里找到最佳的定义域 i R i i i G 块，我们选择 MSE 来度量块之间的距离，使得下式最小: j D （2-3） 2 , , 2 )(),(odsrDRE jiji N ji 和分别为值域块 R 和经过前两种变换后的定义域块 ji r, ji d , 的像素值。)()( jiijij DDD (3)保存分形变换参数。 当最佳仿射变换，及定义域块找到以后，经过量化，然后存
41、储其 i i i G j D 参数。对每一个值域块 R 都找到一组分形代码，就得到整个图像的分形代码。分形 图像编码三个步骤如图 2.3 所示。 基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述 11 图 2.3 分形编码过程示意图 由以上步骤可以看出，假设我们处理一个 256256 象素的图像 D，每个象素的 灰度分为 256 级，因此我们可把这许多象素分成个 88 象素的 1024 个互不交迭的 小方块。再做 1616 的小方块，它们是可以互为交迭的，这 102421 ,RRRDDi 样的总共达个。对于每一个，要在 D 中寻找一个，使它 i D58081)
42、15256( 2 i R i D 们之间的距离极小化，即找到图像的一个小部分使其看起来很像上述的上的图像。 i R 。又有 8 种方法映射到，这意味着对 1024 个中的任意一个要有 858081 i D i R i R 个比较。这样必然导致计算量很大且复杂，编码过程需要很长的编码时间。 为了缩短编码时间，提高压缩比，1992 年，A.E.Jacquin 发表一篇文章，提出 改进。这种方案根据图像子块(值域块和定义域块)的复杂性，把它们分成了三类: 平滑子块:即灰度变化平缓的子块，由于这类子块的灰度十分接近，对这类子 块的编码就只需要存储平均灰度。 中等复杂子块:即灰度有一定的变化，但是不含有
43、边缘，对这类子块，旋转和 对折的意义不大，因此，为了提高压缩比，省略旋转和对折。 边缘子块:即块内灰度变化大，且含有边缘，需要上面介绍的所有步骤。 对于给定的值域块，首先确定它的类别。如果此值域块为平滑子块，就只需要 计算出它的平均值，不需要在定义域集里进行搜索;如果此值域块为中等复杂子块， 由于 8 种变换的意义不大，因此减少了要搜索的定义域块数目;如果此值域块为边 缘子块，则需要做所有的编码过程。由以上分析可知，这种分类方案可以加快编码 速度，而图像的质量基本不变。 分形图像的解码重建较为简单： （1）译码形成 IFS 代码 （2）由 IFS 代码重构子图像 （3）由子图像重建原图像 由分
44、形编码方法的数学原理可知，在编码过程中所得到的迭代函数系统 IFS 是 紧缩的，它的吸引子可以通过对任意初始图像的不断迭代变换而得到。从严格的数 基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述 12 学角度来说，需要迭代无数多次才能得到吸引子。但是在实际应用过程中，只需要 迭代有限次 N 后即可收敛，在进行 N+1 迭代，图像的质量只是轻微的变化。一般情 况下，N=8。图 2.4 显示了初始迭代图像为“Lena”时，分形图像解码的 8 次迭代 结果: 迭代初始图像 N=1 N=2 N=3 N=4 N=5 N=6 N=7 N=8 图 2.4 初始迭代图像为一幅
45、全黑图像时，分形图像解码的 8 次迭代结果 各次迭代的结果对应的 PSNR 如表 2.2 所示: 表 2.2 初始图像为全黑图像时，8 次迭代结果对应的 PSNR 值 迭代次数12345678 PSNR(dB)10461477190023902777298430613080 由此表可知，解码图像迭代 8 次以后，图像的质量几乎不改变了。 2.2.32.2.3 分形图像压缩的特点分形图像压缩的特点 自从 1990 年 A.E.Jacquin 应用局部迭代函数系统实现了分形图像的自动压缩 以来，人们对分形编码进行了不懈地研究，提出了许多改进方法，这些方法主要针 对 Jacquin 方法中的两大缺点
46、，一是编码计算量大和编码时间较长；二是压缩比不 够理想进行改进。改进后的方法同 JPEG 相比，无论是压缩比，还是解码图像质量 方面都具有一定的优势，而且随着分形图像编码研究的不断发展，这种优势还会愈 加明显。 现将分形图像压缩的优点归纳如下: 压缩原理新颖：在分形图像编码中，利用原始图像局部和局部的自相似性构造 一个迭代函数系统，并使该系统的吸引子尽可能逼近原图像；在解码过程中，只需 要该迭代函数系统对任意初始图像不断迭代就可以重建图像。分形图像编码是一种 基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述 13 特殊的矢量量化，不需要码表 。 压缩比高：由于
47、自然界的景物图像中都存在着确定的或统计的自相似性，而分 形图像编码算法恰恰利用了原始图像的自相似性，因此分形图像编码通常都能获得 较高的压缩比和信噪比。 解码效果好：在解码时能去除锯齿效应，而且图像可以被放大到任意尺寸，能 保持图像的细微结构即与分辨率无关。 发展速度快：分形图像编码技术从提出到现在才仅仅十几年的时间，但其发展 速度之快令人惊讶国际上发表的文献逐年增加，商业化的软件、硬件己在市场 上出售。 “金无足赤” ，分形图像编码也存在着编码时间长，压缩比在无人工干预的情 况下不够高等不足。但是，随着计算机各方面技术特别是人工智能技术的不断发展 并取得突破后，分形图像编码克服时间长的不足，
48、达到极高倍的压缩比并不是不可 能的事。 2.32.3 模型基图像编码模型基图像编码 上个世纪八十年代开始，结构模型被引入到图像编码中，它利用了场景的三维 结构信息。主要有两种模型基方法：一种为将待建模对象的表面采用一些表面几何 模型来建模，如平面或光滑曲面；另外一种就是采用对象参数模型的方法建模。前 一种方法通过图像序列估计表面结构和运动信息。而后一种方法则先给定参数模型， 然后估计模型的运动参数。 顾名思义 ，参数模型基视频编码采用了详细的参数对象模型。当然对一个普 通场景欲获得其详细的模型是很困难的。但是，若待编码对象非常明确，可以将对 象的 3D 模型信息应用到编码系统中。比如在会议电视、可视电话中，一个 3D 的头 肩模型就足以描述序列中的大多数图像前景。这种情况下。首先需要建立的是 3D 模型，主要通过三种方法得到:三维扫描设备、解剖学的方法和采用多幅立体图像 的方法。早在 1982 年 Digital 公司的 F.Parke 就用计算机图形学的方法为脸部动 画采用了一个称为