[毕业设计 论文 精品]基于信源模型图像编码的数据压缩算法的研究与实现

《[毕业设计 论文 精品]基于信源模型图像编码的数据压缩算法的研究与实现》由会员分享，可在线阅读，更多相关《[毕业设计 论文 精品]基于信源模型图像编码的数据压缩算法的研究与实现（54页珍藏版）》请在装配图网上搜索。

1、目 录摘要.IABSTRACT.II第一章 绪论.11.1 课题研究的意义.11.2 课题研究的现状.21.3 课题研究的内容和目的 .31.4 图像压缩的相关概念 .4第二章 基于信源模型图像压缩的综述.72.1 基于信源模型的图像压缩技术分类.72.2 分形图像编码 .82.2.1 分形图像编码的基本原理.82.2.2 分形图像压缩的基本算法.92.2.3 分形图像压缩的特点.122.3 模型基图像编码 .132.3.1 模型基图像压缩的基本思想.142.3.2 人脸模型化.152.3.3 模型基编码的特点.17第三章 矢量量化图像编码的研究.183.1 矢量量化的定义 .183.2 量化

2、的关键技术 .193.2.1 码书设计.193.2.2 码字搜索.213.2.3 索引分配.223.3 相关改进算法 .233.3.1 改进的覆盖聚类算法.233.3.2 改进的 SA-LBG 算法 .24第四章 软件系统的整体设计与实现.294.1 软件系统的整体设计及模块实现说明.294.2 算法的 VC+实现的简单说明.364.3 矢量量化编码的性能和复杂度 .374.4 算法的结果 .38第五章 结束语.39参考文献.40致谢.42附 录.43I摘要摘要伴随着科技的发展，社会的进步，在多媒体压缩范畴里，人们认识到对信源的建模表达能使压缩技术取得更大的进展。于是产生了一系列的基于信源模型

3、的图像压缩技术。本文在概要论述基于信源模型图像压缩技术的基础上，重点研究了矢量量化图像压缩。矢量量化一直是图像编码领域最常用的有损压缩技术之一，具有信息理论概念上的最优性和实际应用的简易性。在编码过程中，矢量量化编码器在码书中为每个输入图像块矢量寻找最匹配码字，并将其索引号而非码字本身传送到解码端，因而此编码算法能提供较高的压缩比，解码过程也只需进行简单的查表操作。论文主要的研究工作体现在以下几个方面：系统地综述了矢量量化的三大关键技术，即码书设计、码字搜索和码字索引分配。在此基础上提出了改进的LBG算法。 同时还介绍了分形图像压缩和模型基图像压缩的基本原理及算法，旨在深入了解信源模型图像压缩

4、的技术。关键词：信源模型，矢量量化，分形图像压缩，模型基图像压缩IIABSTRACT 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 progress. As follows, a series of image compres

5、sion 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. Vector Quantization(VQ) has long been establish

6、ed 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 transmitting the codewords corresponding index to the

7、 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 techniques of basic VQ, i.e. codebook design, codewo

8、rd 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 understand the technique of source model image compression

9、.KEY WORDS: source model，vector quantization，fractal image coding，model based image coding 基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论1第一章第一章 绪论绪论1.11.1 课题研究的意义课题研究的意义每天我们都是在报纸、杂志、书籍、电视、各种小册子等大量的图像信息包围中度过的。这些图像包括文字、照片、图表、插图等，它使我们感到安适和生活情趣。 据统计，人们通过感觉器官收集到的各种信息中，视觉约占 65%，听觉约占 20%，触觉约占 10%，味觉约占 2%1。随着信息处理技术的发展，出现了

10、文本、声音、图像、视频等大量不同类型的听觉和视觉媒体数据。进入信息时代以后，人们越来越多地依靠计算机来获取和利用各类媒体数据。然而这些数据由于数据量庞大，在存储空间和传输带宽有限的情况下，这些数据的存储和传输存在瓶颈。为此，人们通常要对这些媒体数据作压缩处理，以提高存储和传输效率，降低设备成本。在保证听觉和视觉质量的前提下，人们往往希望能够以尽量少的空间和尽量小的比特率来存储和传输各种声音、图像数据。然而在相同的压缩编码技术下，信息理论概念下的编码质量和压缩比往往是一对矛盾。因此如何建立新的语音、图像和视频的分析模型，从而改进压缩编码算法长久以来一直是信号处理领域的研究热点。图像视频通信的发展

11、长期以来落后于语音通信。而在多媒体数据通信的发展趋势下，图像压缩编码技术的研究和应用越来越引人瞩目。人们对图像压缩的研究兴趣可以追溯到 62 年前。最初在这一领域研究的焦点集中在如何建立一种模拟的方法以便减少视频传输所需的带宽。这一过程称为带宽压缩。数字计算机的出现和后来先进的集成电路的发展，导致了这方面研究的重点从模拟方式转移到数字压缩方法上来。随着几种关键性的国际图像压缩标准的正式采用，这一领域在实际应用方面有了重大的发展。当前，图像压缩被认为是一种“开放技术”，已经被广泛用于现代通信业务、工程应用、媒体传播、医疗服务和商务应用等诸多领域中。对声音、图像、视频等多媒体信息的压缩有两条思路，

12、要么采用成熟的通用数据压缩技术进行压缩，要么根据媒体信息的特性设计新的压缩方法。然而在通用数据压缩领域技术已经相当的成熟，很难有大的突破，与此同时，多媒体信息日益成为主流信息形态，数据压缩技术特别是专用于图像、音频、视频的数据压缩技术还基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论2有相当大的发展空间毕竟，人们对信息数量和信息质量的追求是永无止境。随着电子信息产业的发展的牵引和相关科学技术进步的推动，科技界特别是许多跨国公司对于研究更高效图像压缩技术的热情越来越高涨，观念也在不断更新，新一轮的技术竞争也愈演愈烈。今天，从事基于信源模型的图像编码的数据压缩课题的研究也正是在此思潮的

13、引领之下开展的，希望通过笔者的努力能为这一技术的发展做出应有的贡献。1.21.2 课题研究的现状课题研究的现状 严格意义上的数据压缩起源于人们对概率的认识。当我们对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，总的编码长度就能缩短不少。信息论之父 C. E. Shannon 第一次用数学语言阐明了概率与信息冗余度的关系。在 1948 年发表的论文“通信的数学理论（ A Mathematical Theory of Communication ）2中， Shannon 指出，任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概

14、率或者说不确定性有关。 Shannon 借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作，信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。1948 年，Shannon 在提出信息熵理论的同时也给出了一种简单的编码方法Shannon 编码。随着科学技术的不断进步，出现了 Huffman

15、 编码3。编码效率高，运算速度快，实现方式灵活，从 20 世纪 60 年代至今，在数据压缩领域得到了广泛的应用。不过，Huffman 编码所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。正因为如此，现代压缩技术通常只将 Huffman 视作最终的编码手段，而非数据压缩算法的全部。1976 年， J. Rissanen 提出了一种可以成功地逼近信息熵极限的编码方法算术编码3。之后，人们又将算术编码与 J. G. Cleary 和 I. H. Witten 于 1984 年提出的部分匹配预测模型（ PPM ）相结合，开发出了压缩效果近乎完美的算法。对于无损压缩而言， PP

16、M 模型与算术编码相结合，已经可以最大程度地逼近信息熵的极限。看起来，压缩技术的发展可以到此为止了。不幸的是，事情往往不像想象中的那样简单：算术编码虽然可以获得最短的编码长度，但其本身的复杂性也使得算术编码的任何具体实现在运行时都慢如蜗牛。即使在摩尔定律大行其道，CPU 速度日新月异的今天，算术编码程序的运行速度也很难满足日常应用的需求。后来又相继出现了 LZ77、 LZ78 及基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论3LZW。使得压缩技术又上了一个大的台阶。伴随着科技的发展，社会的进步，人们逐渐认识到多媒体的数据压缩成为一项亟待解决的技术。70 年代末 80 年代初，人们

17、逐渐意识到，对于多数灰度或是彩色图像乃至声音文件，没有必要忠实地保留其所有信息，在允许一定的精度损失的情况下，可以实现更为有效的压缩方法。到 80 年代末，许多人已经在这一领域取得了不小的收获，设计出了一批在压缩效果上让人惊讶不已的声音和图像压缩算法。在此基础上，国际标准化组织( ISO )和 CCITT 联合组成了两个委员会。委员会的名字我们大概都已经非常熟悉了：静态图像联合专家小组( JPEG )和动态图像联合专家小组( MPEG )。JPEG 的压缩目标是静止图像（灰度的和彩色的） ，MPEG 的目标则是声音和视频。但他们的基本思路是完全一样的，即保留媒体信息中最有规律、最能体现信息主要

18、特征的数据，而略去其他不重要的数据。他们都取得了令人赞叹的成就。就在多媒体压缩范畴里，人们认识到对信源的建模表达能使压缩技术取得更大的进展。事实上，压缩音频、视频信号的许多很有潜力的方法，实质上都是通过对信源的分析，将其分解成一系列更宜于表示的“基元”或从中提取若干具有更重要意义的参数，编码仅对这些基本单元或特征参数进行。而接受端则借助于一定的规则或模型，按一定的算法将这些基元或参数再综合成原信源的一个逼近。这也就是基于信源模型图像编码的数据压缩。原则上，压缩编码的极限结果是通过那些能够反映信号产生过程最早阶段的模型而得到的，比较鲜明的例子就是人类发音的“清晰声带-声道模型” ，它把注意焦点从

19、 LPC 分析扩展到了声道区分析，原则上为甚低码率矢量化提供了强得多的定义域，并允许更好的处理声带-声道相互作用，而简化的激励后滤波模型忽略了这一现象。另一个例子就是人脸的线框模型，它为压缩可视电话这类以人脸为主要景物的序列图像提供了一个强有力的手段。仅就图像编码而言，对信源模型的描述正从波形参数向几何特征发展。为了便于研究和加深理解，学者们对其进行了分类，大致分为如下两类：第一代图像编码压缩（又称波形基编码） 、第二代图像编码技术。1.31.3 课题研究的内容和目的课题研究的内容和目的本课题要求完成如下工作：1. 对数据压缩的基本理论、技术标准、评价方法进行研究和分析；2. 对基于信源模型图

20、像编码的数据压缩算法及其衍生算法进行逻辑上的分析和比较；3. 对这些算法进行编程实现，并在实践中进行分析比较4. 从这些算法中选择一个较优算法，并以此算法实现一个完整的压缩软件。基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论41.41.4 图像压缩的相关概念图像压缩的相关概念1.4.11.4.1 图像压缩的对象与及方式图像压缩的对象与及方式保存图像信息的数字文件通常包含着数量可观的冗余信息和大量的不相干信息4。其中冗余信息是指在图像文件中多余或重复的信息；不相干信息是指图像信息中不重要，无关紧要的部分。把这部分信息去除后不影响人们可以感知的部分。图像压缩的对象就是这两种信息。图像

21、压缩技术利用数据固有的冗余性和不相干性，采用合适的压缩策略将一个大的数据文件转换成较小的文件，这个压缩后的文件可以在以后需要的时候通过解压缩以精确的或近似的方式将原文件恢复出来。两个文件的大小之比(压缩比)确定了压缩的程度。图像压缩的方式可分为无损压缩和有损压缩两种。无损压缩算法去除的仅仅是冗余信息，因而可以在解压缩时精确地恢复原图像。无损压缩通常应用于对图像数据有特殊要求的环境中，例如有些图像，以及所有的可执行文件，不允许进行任何修改，在这种情况下，只能对它们进行无损压缩。对于多数图像来说，为达到较高的压缩比，保真度的轻微损失是可以接受的，这时就需要采用有损压缩算法。有损压缩算法把不相干的信

22、息也删除了，因此只能对原图像进行近似地重构，而不能精确地复原。人们在选择或设计算法时，往往是在算法的复杂度(易实现性，计算量等)和解压缩图像的保真度之间进行折衷，从而在保持较小的存储空间和传输负担的同时保持可接受的图像质量。1.4.21.4.2 速率速率失真理论失真理论速率失真理论5旨在寻求一种联系失真度和码速率的编码策略，它是有损压缩编码的理论基础。香农的信息论告诉人们，只要码速率不超过信道容量，符号就能以任意小的差错概率在该信道中传输。在数学上，速率失真函数 R（D)定义为在给定失真 D 的条件下，系统所能够达到的最小码速率。对于幅值离散的信源，R(D)5定义如下： （1-1）() ( /

23、) (, )XYP X P YX d X YD其中 （1-2）( )() ( /)XQ YP X P YX平均失真满足条件: （1-3）() ( /) (, )XYP X P YX d X YD其中 d(X,Y)是失真测度，它表示输出采样值 Y 再现原始信源采样值 X 所引入的失真，P(Y/X)表示在己经发送 X 的情况下接收到 Y 的概率。R(D)的单位为比特/采样。相基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论5应地，速率失真函数的逆函数 D(R)表示在给定速率不超过 R 的条件下，系统所能够达到的最小失真。D(R)和 R(D)所给出的编码性能极限，适用于所有信源编码方法。

24、在实际应用中，速率失真函数常常作为一个理论下界与实际编码速率相比较，分析系统还有多大的改进余地。对于图像编码而言，在客观评价标准下，编码性能(峰值信噪比/比特率)曲线同 D(R)曲线的接近程度成为判断编码算法好坏的一个标准。1.4.31.4.3 图像质量的测度图像质量的测度 对人类而言，图像信息的接收和预处理都要通过人眼来完成，图像质量好坏的判断自然和人眼的视觉特性密切相关。在图像的有损压缩过程中，部分视觉信息会在编码过程中损失而引起人眼视觉上的差异。这种感官上的差异的大小可以反映图像质量退化的多少。然而，视觉特性的复杂性决定了人眼对不同形式的视觉信息损失的敏感程度也不同，使得视觉差异很难用量

25、化的形式展示出来。人们把这种纯粹主观感觉上的图像质量称作图像的主观视觉质量，并提出了一些衡量图像质量的主观评价标准。但由于人类视觉敏感方式的复杂性，人们对图像质量的主观评价方法的认识和研究仍然欠缺，这使得一些图像客观评价标准得到了广泛使用一般来说，客观评价标准考虑的是原始图像和重构图像之间像素值上的差异，不同的客观评价标准同主观感受的相关性也不同。虽然客观评价不如主观评价更符合人眼感受特性，但它形式简单、计算方便，同时也能较好的反映图像信息的损失量。最常用的测度函数3有均方误差(Mean Squared Error，MSE)、信噪比(Signal Noise Ratio, SNR)和峰值信噪比

26、(Peak Signal Noise Ratio，PSNR)，分别定义如下：MSE= （1-4）11200()*PQijijijxyP Q SNR=10* （1-5）112001011200log()PQijijPQijijijxxy PSNR=10* （1-6）210logLMSE其中 P 和 Q 分别为表示图像的高度和宽度(即在垂直方向和水平方向上的像素数目)，L 为图像灰度的总阶数，和分别表示在坐标（i,j）处的原始图像像素值和重ijxijy构图像像素值。0iP-1 0jQ-1。 基于信源模型图像编码的数据压缩算法的研究与实现 第一章 绪论61.4.31.4.3 图像编码性能评价标准图像

27、编码性能评价标准 各类压缩编码算法因各自特点而适用于不同的图像编码场合。在实际应用当中，通常考虑如下几个评价标准：(1) 图像压缩比。通常用比特率(Bit-rate)来衡量压缩比的大小，它定义为每个像素占有的比特数(单位是 bits per pixel, bpp)，显然压缩后图像的比特率越小，压缩比越大。(2) 图像质量。在客观评价标准下常用信噪比(SNR)和峰值信噪比(PSNR)的高低表示重构图像质量的高低(单位均为 dB)。(3) 编码复杂度。包括时间复杂度和空间复杂度，在算法实现时往往表现为乘法、加法的操作次数和算法占用存储空间的大小。一般来说，以上三个评价参数是互相矛盾的，不同的算法因

28、不同的应用要求会在这三个参数上有不同的偏重。具体应用中，编码速率经常受到限制，设计压缩系统目的是在可承受的复杂度条件下取得较好的编码质量。对给定信源来说，用时间和存储量来描述的复杂度通常会随比特率的降低而增高。因此，好的编码算法应该能在最大程度上取得这三方面的改进和折衷。在对编码算法的选取上，人们必须在系统复杂度和性能，成本和保真度之间寻求折衷。基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述7第二章第二章 基于信源模型图像压缩的综述基于信源模型图像压缩的综述2.12.1 基于信源模型的图像压缩技术分类基于信源模型的图像压缩技术分类NJayant 指出：原则上

29、，压缩编码的极限结果是通过那些能够反映信号产生过程最早阶段的模型而得到的，比较鲜明的例子就是人类发音的“清晰声带-声道模型” ，它把注意焦点从 LPC 分析扩展到了声道区分析，原则上为甚低码率矢量化提供了强的多得定义域，并允许更好的处理声带-声道相互作用，而简化的激励后滤波模型忽略了这一现象。另一个例子就是人脸的线框模型，它为压缩可视电话这类以人脸为主要景物的序列图像提供了一个强有力的手段。仅就图像编码而言，对信源模型的描述正从波形参数向几何特征发展。为便于研究和加深理解，学者们尝试按表 2.1 进行分类3。表 2.1 基于信源模型的图像编码技术分类类别信源模型编码信息典型编码技术1单个像素像

30、素的色彩PCM2统计相关的像素块像素或像素块的色彩预测、变换、子带、小波分析、VQ 等3平移运动的像素块像素块的色彩和运动矢量运动补偿的混合 DPCM/DCT 编码4结构的自相似IFS 代码运动分形编码5运动的区域每个区域的轮廓、纹理及运动参数区域基编码、分割基编码6未知的运动物体每个物体的形状、运动和色彩物体基编码7已知的运动物体物体形状、运动、色彩及行为表情单元知识基编码、语义基编码从这个表中我们对信源模型图像编码的简史有个大致的了解，学者们又把它们基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述8做了更具体的分类，认为表 2.1 中的 1-3 类技术属于

31、波形基编码，称之为第一代图像编码技术；而第 4-7 类则称之为第二代图像编码技术。其中第 3 类是第一代图像编码技术的典型代表，编码效率较高，时延短、技术成熟，被现有的多种视频编码标准所采纳。第 5-7 类技术统称模型基编码，核心是对模型本身或模型参数进行编码传输，如果模型足够好，对模型的描述又足够成熟，那么模型基编码就有很强的利用性。2.22.2 分形图像编码分形图像编码1987 年，美国乔治亚工学院的数学家 M.F.Barnsley 在题为“Chaotic Compression” 6的论文中提出了分形图像编码的概念之后，在 1988 年M.F.Barnsley 和 A.D.S loan

32、发表了一篇题为 “A Better Way to Compress Images”7的文章，在此文中，他们首次将 M.F.Barnsley 提出的 IFS 理论应用到图像压缩编码中，并获得了较好的压缩效果，压缩比高达 10000: 1。但是这个方法存在的最大不足就是在压缩过程中需要专业技术人员的人机交互操作。尽管如此，它的极有希望的压缩效果和压缩比使人们看到了用分形理论解决图像压缩问题的前景和希望。1990 年，M.F.Barnsley 的博士生 A.E.Jacquin 首次提出了一种全自动的分形图像压缩方法，完成了分形图像压缩从需人工参与编码到自动编码的飞跃，从此分形图像编码作为一种很有希望

33、的编码方法列入计算机图像自动编码的行列，得到了人们的普遍关注。各国学者纷纷效仿 A.E.Jacquin 的压缩方案提出各种各样的改进方案，从而掀起了分形图像编码的高潮。2.2.12.2.1 分形图像编码的基本原理分形图像编码的基本原理 分形图像压缩，利用了分形理论中的迭代函数系统理论。编码的过程是依据拼贴定理，通过给定的图像，寻找一组压缩仿射变换，使其构成的迭代函数系统逼近给定的吸引子，然后记录下相应参数，并且用这些参数作为图像的编码进行存储和传输。解码过程首先是由存储或传输的参数确定一组压缩仿射变换，进而构造一个迭代函数系统，并求出这个迭代函数系统的吸引子，根据吸引子定理，该迭代函数系统的吸

34、引子就是原始图像的近似解码图。这就是分形图像压缩的基本原理和方法。其编解码原理框图如图 2.1 所示。基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述9图像分块对每一块寻找近似不变集保留 IFS 码编码恢复 IFS 码IFS 代码迭代生成不变集图像合并恢复图像解码原始图像 图 2.1 分形编解码原理框图2.2.22.2.2 分形图像压缩的基本算法分形图像压缩的基本算法1990 年，A.E.Jacquin 发表了一种基于方块划分的分形图像压缩方案8。这是一种基于 IFS 的压缩编码方案，准确地说是基于 Local IFS 的压缩方案。该方案突破了 M.F.Bar

35、nsley 设计的方案，将图像分割成两种大小固定的方块，然后去找这两种方块之间的相似性，由于不再与整幅图像比较，而放宽为原始图像的一部分，从而使该方案能够自动对任意图像进行编码。首次实现了自动分形图像编码方法。以后其他学者提出的方案都是基于此方案的改进，因此 A.E.Jacquin 的方案被公认为最基本的分形图像编码方案3。在 A.E.Jacquin 提出的编码方案中，分形图像编码分为三个步骤:(1)对待编码图像 I 进行分块。把大小的待编码图像 I 分割成若干个不重叠的、大小为的子块，称NN BB之为值域块，记为。这些值域块的并集能够完全的覆盖整个图像，即NRRR,21当，且。然后再把待编码

36、图像分割成若干ji jiRR NRRRI21个可以重叠的、大小为的子块，称之为定义域块，记为。要求KK MDDD,21，一般来说。对原始图像的划分如图 2.2 所示： BK BK2 (a)值域块 (b)定义域块iRjD 图 2.2 分形编码分块表示图基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述10(2)找到合适的迭代函数系统。跟据 LIFS 理论，寻找一个 IFS，, 2 , 1, 2 , 1|:,MjNiRDwHiji使得即和 I 在 Hausdorff 测度下尽可能的接近，因为)(,(1jiNiDwIh)(1jiNiDw，所以实现时，只需要与在 Hau

37、sdorff 测度下尽可能NRRRI21)(jiDwiR的接近。因此，分形图像编码的关键是如何找到最佳的仿射变换以和定义域块。jD在实际应用中，仿射变换难以找到、存储，而是把仿射变换等价分解为几何变iwiw换、同构变换和灰度变换，即iiiG （2-iiiiGw1）几何变换:我们用来表示起始位置为，大小为的定i),(KjiDddj),(ddjiKK 义域块。用来表示经过抽样后，起始位置为），大小为jD),(LjiDddjddji,(的定义域块。通过下式:LLjD （2-4/ )(1)(, 1)(1)(),()(, 1)()(),(,jJiIjJiIjJiIjJiIjidddddjdid2）要求：

38、 1, 1 , 0,LjiiiiId2)(jjjJd2)(几何变换把大小为定义域块几变换大小为的定义域块，即KK LLjD。这里的。)(jijDDLK 2同构变换：同构变换就是 4 种对折、4 种旋转变换。经过同构变)7 , 2 , 1(ii换后，产生。即。jD )()(jiijijDDD 灰度变换:灰度变化包括比例因子 和补偿因子，对做灰度变换iGsojD ，产生。oDsDGjji )(jD 对每一个定义域块经过以上三种变换，就得到一个数量很大的定义域池。对值域块的分形编码就是寻找最佳，以及在定义域池里找到最佳的定义域iRiiiG块，我们选择 MSE 来度量块之间的距离，使得下式最小:jD

39、（2-3）2,2)(),(odsrDREjijiNji和分别为值域块 R 和经过前两种变换后的定义域块jir,jid,的像素值。)()(jiijijDDD (3)保存分形变换参数。当最佳仿射变换，及定义域块找到以后，经过量化，然后存储其iiiGjD参数。对每一个值域块 R 都找到一组分形代码，就得到整个图像的分形代码。分形图像编码三个步骤如图 2.3 所示。基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述11 图 2.3 分形编码过程示意图 由以上步骤可以看出，假设我们处理一个 256256 象素的图像 D，每个象素的灰度分为 256 级，因此我们可把这许多象

40、素分成个 88 象素的 1024 个互不交迭的小方块。再做 1616 的小方块，它们是可以互为交迭的，这102421,RRRDDi样的总共达个。对于每一个，要在 D 中寻找一个，使它iD58081)15256(2iRiD们之间的距离极小化，即找到图像的一个小部分使其看起来很像上述的上的图像。iR。又有 8 种方法映射到，这意味着对 1024 个中的任意一个要有 858081iDiRiR个比较。这样必然导致计算量很大且复杂，编码过程需要很长的编码时间。 为了缩短编码时间，提高压缩比，1992 年，A.E.Jacquin 发表一篇文章，提出改进。这种方案根据图像子块(值域块和定义域块)的复杂性，把

41、它们分成了三类: 平滑子块:即灰度变化平缓的子块，由于这类子块的灰度十分接近，对这类子块的编码就只需要存储平均灰度。 中等复杂子块:即灰度有一定的变化，但是不含有边缘，对这类子块，旋转和对折的意义不大，因此，为了提高压缩比，省略旋转和对折。 边缘子块:即块内灰度变化大，且含有边缘，需要上面介绍的所有步骤。 对于给定的值域块，首先确定它的类别。如果此值域块为平滑子块，就只需要计算出它的平均值，不需要在定义域集里进行搜索;如果此值域块为中等复杂子块，由于 8 种变换的意义不大，因此减少了要搜索的定义域块数目;如果此值域块为边缘子块，则需要做所有的编码过程。由以上分析可知，这种分类方案可以加快编码速

42、度，而图像的质量基本不变。分形图像的解码重建较为简单：（1）译码形成 IFS 代码（2）由 IFS 代码重构子图像（3）由子图像重建原图像由分形编码方法的数学原理可知，在编码过程中所得到的迭代函数系统 IFS 是紧缩的，它的吸引子可以通过对任意初始图像的不断迭代变换而得到。从严格的数基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述12学角度来说，需要迭代无数多次才能得到吸引子。但是在实际应用过程中，只需要迭代有限次 N 后即可收敛，在进行 N+1 迭代，图像的质量只是轻微的变化。一般情况下，N=8。图 2.4 显示了初始迭代图像为“Lena”时，分形图像解码的

43、 8 次迭代结果:迭代初始图像 N=1 N=2 N=3 N=4 N=5 N=6 N=7 N=8图 2.4 初始迭代图像为一幅全黑图像时，分形图像解码的 8 次迭代结果各次迭代的结果对应的 PSNR 如表 2.2 所示:表 2.2 初始图像为全黑图像时，8 次迭代结果对应的 PSNR 值迭代次数12345678PSNR(dB)10461477190023902777298430613080由此表可知，解码图像迭代 8 次以后，图像的质量几乎不改变了。2.2.32.2.3 分形图像压缩的特点分形图像压缩的特点自从 1990 年 A.E.Jacquin 应用局部迭代函数系统实现了分形图像的自动压缩以

44、来，人们对分形编码进行了不懈地研究，提出了许多改进方法，这些方法主要针对 Jacquin 方法中的两大缺点，一是编码计算量大和编码时间较长；二是压缩比不够理想进行改进。改进后的方法同 JPEG 相比，无论是压缩比，还是解码图像质量方面都具有一定的优势，而且随着分形图像编码研究的不断发展，这种优势还会愈加明显。 现将分形图像压缩的优点归纳如下:压缩原理新颖：在分形图像编码中，利用原始图像局部和局部的自相似性构造一个迭代函数系统，并使该系统的吸引子尽可能逼近原图像；在解码过程中，只需要该迭代函数系统对任意初始图像不断迭代就可以重建图像。分形图像编码是一种基于信源模型图像编码的数据压缩算法的研究与实

45、现 第二章 基于信源模型图像压缩的综述13特殊的矢量量化，不需要码表 。压缩比高：由于自然界的景物图像中都存在着确定的或统计的自相似性，而分形图像编码算法恰恰利用了原始图像的自相似性，因此分形图像编码通常都能获得较高的压缩比和信噪比。解码效果好：在解码时能去除锯齿效应，而且图像可以被放大到任意尺寸，能保持图像的细微结构即与分辨率无关。发展速度快：分形图像编码技术从提出到现在才仅仅十几年的时间，但其发展速度之快令人惊讶国际上发表的文献逐年增加，商业化的软件、硬件己在市场上出售。“金无足赤” ，分形图像编码也存在着编码时间长，压缩比在无人工干预的情况下不够高等不足。但是，随着计算机各方面技术特别是

46、人工智能技术的不断发展并取得突破后，分形图像编码克服时间长的不足，达到极高倍的压缩比并不是不可能的事。2.32.3 模型基图像编码模型基图像编码上个世纪八十年代开始，结构模型被引入到图像编码中，它利用了场景的三维结构信息。主要有两种模型基方法：一种为将待建模对象的表面采用一些表面几何模型来建模，如平面或光滑曲面；另外一种就是采用对象参数模型的方法建模。前一种方法通过图像序列估计表面结构和运动信息。而后一种方法则先给定参数模型，然后估计模型的运动参数。顾名思义 ，参数模型基视频编码采用了详细的参数对象模型。当然对一个普通场景欲获得其详细的模型是很困难的。但是，若待编码对象非常明确，可以将对象的

47、3D 模型信息应用到编码系统中。比如在会议电视、可视电话中，一个 3D 的头肩模型就足以描述序列中的大多数图像前景。这种情况下。首先需要建立的是 3D模型，主要通过三种方法得到:三维扫描设备、解剖学的方法和采用多幅立体图像的方法。早在 1982 年 Digital 公司的 F.Parke 就用计算机图形学的方法为脸部动画采用了一个称为 Parke 的脸部网格模型.当时他也曾提出可以将他的脸部模型用于视频数据压缩，但他本人并未实现自己的想法。P.Ekman 等在 1970 年代提出了FACS(Facial Action Coding System)3,是第一个将面部表情量化成数字来表征其强度的系

48、统。现代的模型基图像编码“通过动画编码”的概念是瑞典 Linkoping 大学的 R.Forchcheimer 提出的，著名的 Candide 模型也是他的研究小组的成果。到 1987 年，W.1.Welsh 和 K.Aizawa 将纹理映射的概念引入到此方案中，这对模型基图像编码来讲是一个里程碑，纹理映射(Texture Mapping)3技术为相片现实化模型基编码(photo realistic model-based coding)成为可能，迅速成为一个基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述14研究热点，包括东京大学、UIUC、MIT 媒体实验

49、室等一些著名的研究机构都开展了这项研究，他们各自对人脸作出了自己的 3D 参数模型，用于视频压缩。基于三维模型的方法是一个很特效的方法。必须承认的一点，基于三维模型图像编码的研究还很不成熟。目前研究的热点和难点在编码端，最近大都集中在三维人脸跟踪上，也可以称为姿态估计和三维运动参数估计。2.3.12.3.1 模型基图像压缩的基本思想模型基图像压缩的基本思想模型基编码根据所采用模型的不同类型分为物体基图像编码和语义基图像编码两种。 物体基图像编码通过自动图像分析将输入图像分解为若干个运动物体的区域,并用 3 组参数分别表示每个物体的运动、形状和亮色信息。由于模型中物体的不确实性增大,可利用的先验

50、知识减少,压缩比要小于语义基编码。语义基图像编码9要求收发双方共有一个 3 维人脸线框模型,发送方采用 3 维运动估值和结构估值技术跟踪线框模型的全局和局部运动以及结构变化,并将预测所得的运动和结构(深度) 信息、变化了的纹理信息编码送至接收方,接收方用它们来恢复下一帧图像,该方法的编码框图见图 2.6。图像分析3D 线框模型图象分析3D 线框模型头肩图像输出头肩图像输入图 2.6 语义基图像编码框图建模是合成图像的关键步骤。为了使 3 维模型（见图 2.7）投影为 2 维图像,一般模型都采用线框的形式。根据线框模型的形变不同，现有的模型可分为几何模型和生理模型。根据测定参数所采用的手段，可将

51、运动估值方法分为两类:灰度法和光流法。另外，在对待全局参数和局部参数上,也有两种方案：一种方案是将两者分开来测，另一种方案是将全局参数和局部参数同时测。基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述15 图 2.7 头部的 3D 线框模型对局部运动参数估值是件困难的事情,因为人的表情变化是非刚体运动。但是我们可以采用一组“表情基本活动单元”来表示各种脸部表情。P. Ek-man 和 W. Friesen 提出了“脸部活动编码系统(FACS) ”,指出共有 44 种表情基本活动单元，每个表情基本活动单元是无法再分解的小动作。任何脸部表情都可由不同的表情基本活动

52、单元(AU) 来线性组合。这样就可以在对全局参数进行补偿后, 用 FACS 对面部表情进行描述，编码仅需要对特定的 AU 系数进行。语义基编码和传统的波形编码不同，它利用图像的宏观特点，运用了计算机视觉、计算机图形学、图像处理、模式识别等技术，为图像编码开辟了新途径。由于其压缩比很高，恢复图像质量好，克服了波形编码中出现的方块效应及颗粒化噪声，出现的模型几何失真不易察觉，所以，在现有的编码方案中，语义基编码最适合于极低码率下的图像传输。不过，它面临以下 3 个实际问题：(1) 如何将线框模型自动匹配到具体人脸上；(2) 实时进行运动跟踪,即不断提供全局和局部运动参数；(3) 尽快完成戴眼镜的人

53、脸模型。解决了这 3 个问题,语义基编码的应用前景将很好。2.3.22.3.2 人脸模型化人脸模型化模型基编码的前提是人脸对象的模型化3表示，通常，采用网格化的三维图形来表示。1 1、网格对象通常有两种网格对象平面，用不同的方式编码，对于内部编码的网格平面，只编码单一的 2D 网格几何形状，它既可以是统一型，也可为 Delaunay，统一型网格基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述16的几何形状用小参数集编码；而 Delaunay 类型的网格的几何形状则用节点和边的位置来编码。三角形网格结构用编码信息隐含说明。对预测编码的网格对象平面，根据过去的参考

54、网格对象平面利用时间预测来编码。预测编码网格的三角形结构与参考网格相同，只是接点位置有所变化，接点的位移表明了网格的运动，可以用当前网格对象平面与参考网格对象平面的接点运动向量来描述。2 2、人脸对象 从概念上讲，人脸对象由一个场景图的接点集合组成。人脸的形状、纹理和表示由包含人脸定义参数集（FDP）和人脸动画参数集（FAP）的码流来控制。在解码之前，人脸对象包含一个带自然表示的一般人脸。这个脸一旦被展现，就可以马上从码流中接受 FAP 来生成人脸的活动，例如表情和语言等。如果收到 FDP，就利用FDP 中确定的形状和纹理将一般的人脸变成特定的人脸。一个完整的人脸模型通过FDP 集用类似向场景

55、图中插入人脸结点的方法生成。FAP 是基于最小人脸活动的研究而得出的，和肌肉活动密切相关。他们描述了基本人脸活动的一个完全集，因此可以表示绝大部分自然人脸。所有包含运动信息的参数都在人脸动画参数单元（FAPU：Facial Animation Parameter Units）中表示。这些单元是为了用统一的方式描述人脸模型而定义的，以便对表情语言生成合理的结果。编码开始时，人脸被假设为一个自然的姿势，当 FAP 的值全为 0 时，也显示一个自然人脸。所有 FAP 表示了人脸特征位置的移动。自然人脸有以下定义：1、采用右手坐标系，两眼的连线为水平方向2、凝视方向为 Z 轴3、所有脸部肌肉是松弛的4

56、、眼皮接触虹膜5、瞳孔是 IRISD0 的 1/36、两片嘴唇接触，唇线水平，两嘴角等高7、嘴紧闭，上下齿接触8、舌头平坦，舌尖接触上下齿3 3、人脸定义参数集FDP 集用与用户自定义人脸模型，一般用于让解码器得到连续变化的人脸模型。FDP 参数通常是每一个镜头传输一遍，然后才是压缩的 FAP 参数。因此，如果解码器没有受到 FDP 参数，要保证仍然可以利用 FAPU 中 FAP 参数解释人脸，这样就可以在视频会议中只使用最小的操作。 在对人脸网格化之后，就可以着手建立模型基编码系统了。基于信源模型图像编码的数据压缩算法的研究与实现 第二章 基于信源模型图像压缩的综述172.3.32.3.3

57、模型基编码的特点模型基编码的特点 模型基编码是区域基编码、分割基编码、物体基编码、知识基编码和语义基编码几种技术的统称，它与经典方法中的预测编码类似，在发端既有分析用的编码器，又有综合用的解码器。只有这样，发端才能获得与收端相同的综合后的重构图像，并将后则与原始图像进行补交。这种比较应能判断重建图像与原始图像是否“相似”，也即前者的图像失真是否低于某种阀值。由此可以注意到模型基图像编码与经典的图像编码有两点显著的不同： 一是编码失真。模型基编码所引起的失真已从传统方法的量化误差转为几何失真，并可能进一步转为物理失真或行为失真。这些失真同量化误差相比，将更难以为人眼所察觉。例如，两个相似的三角形

58、左右并列且其尺寸相近时，主观上难以察觉二者的区别；与此类似，人脸的宽度的增加或减少一两个像素，主观上也无法区分其差别。 二是如何评价重建图像质量。由于编码失真的性质有了本质的变化，传统的以像素为单位计算原始图像与重建图像之间“逼真度”（如 MSE、SNR 等）的方法，仅能评价量化误差，不能测量几何失真和物理失真，因此从原理上讲根本不适用于模型基编码。究竟采用什么函数才能定量地计算重建图像的“失真度”，正是模型法需要研究和解决的一个关键问题。 另外，除了压缩比很高外，模型基编码的码率与图像分辨率无关，不会因收端计算机合成的图像大小变了，就要求模型参数及运动参数的数目也相应变化。而在其他视频编码方

59、法如 MPEG-2 标准中，如果提高图像分辨率，则所需传输的码率也会大幅增加。当然，模型基编码也存在不足的地方，主要问题是，计算机根据 3D 模型和信息合成的图像缺乏足够的自然度和真实度。原因在于，摄像机拍摄自然景物的过程是三维景物投影到摄像平面的过程，其间丢失了三维景物的深度信息，而要重建这些深度信息是非常困难的。其进一步的研究方向是把物体基编码和语义基编码结合起来，取长补短；或者在语义基编码器中加入波形编码器，对不能建模的物体进行混合编码，以扩大前者的适用范围。基于信源模型图像编码的数据压缩算法的研究与实现 第三章 矢量量化图像编码的研究18第三章第三章 矢量量化图像编码矢量量化图像编码的

60、研究的研究3.13.1 矢量量化的定义矢量量化的定义 矢量量化3(Vector Quantization，VQ)利用了相邻采样之间的相关性，基本思想是在量化时用输出组集合(码书)中最匹配的一组输出值(码字)代替输入的一组采样值(输入矢量)。矢量量化的历史可追溯到 1956 年由 Steinhaus 第一次系统地阐述了最佳矢量量化问题。1978 年，Buzo 第一个提出实际的矢量量化器。1980 年，Linde,，Buzo 和 Gray 将 Lloyd-Max 算法推广，发表了第一个实用的矢量量化器设计算法LBG 算法，从此矢量量化在有损数据压缩上得到了广泛的应用。 基本的矢量量化器可以定义为从

61、 k 维欧几里德空间到一个有限子集 C 的一KR个映射，即 Q：C，其中 C=称为码书，N 为码书大小。KRK011i,.,|RNyyyy该映射满足：Q(x|x )= ，其中 x=()为中的 k 维矢量，KRpy011,.,kx xxKR为码书 C 中的码字并满足：01(1)(,.,)pppp kyyyy （3-0 j N 1( ,)min( ,)pjd x yd x y 1）其中，为输入矢量 x 与码字之间的失真测度。每一个矢量 x=( ,)jd x yjy)都能在码书 C=中找到最匹配码字=Q(x|x )。011,.,kx xx011i,.,|NyyyypyKR输入矢量空间通过量化器 Q

62、量化后，可以用划分 S=来 描述，其中011 ,.,Ns ss是所有映射成码字的输入矢量集合，即。这 N 个子空间iSiy( |( )iisx Q xy满 足：011,.,Ns ss （3-10()Niiijssssij 且2）矢量量化编码与解码过程如图3.1所示。矢量量化编码器根据一定的失真测度在码书中搜索出与输入矢量之间失真最小的码字。传输时仅传输该码字的索引。矢量量化解码过程很简单，只要根据接收到的码字索引在码书中查找该码字，并将它作为输入矢量的重构矢量。用数学的观点来描述，可以将矢量 S=看作是在 N 维空间中的一个011 ,.,Ns ss点。把 N 维空间划分为 L 个区域，i=1,

63、2,.,L，人们称之为 Voronoi 区域。落iR基于信源模型图像编码的数据压缩算法的研究与实现 第三章 矢量量化图像编码的研究19在区域上的所有矢量都用同一个矢量来表示，这里矢量称为码字iR11,.,iiiiNrr rr(Codeword)，由所有 L 个码字组成的集合称为码书(Codebook)。由上可知，矢量量化的编码首先要将原始的数据划分为一系列矢量，然后在特定码书中搜索误差最小的码字作为量化值。矢量量化的编码结果并不是码字，而是码字在码书中的索引值。如果这个索引值记录所需要的存储空间小于原始矢量的存储空间，就达到了压缩数据的目的。而量化质量则体现为原始矢量同其码字之间的误差。由此可

64、见矢量量化技术包括矢量构成、码书设计、码字搜索等多个方面。索引 P索引 P输出码字py输入矢量 X搜索最匹配码字py信 道查找索引P 对应的码字py 0y 1y N 1y 0y 1y N 1y码书C码书C 图 3.1 矢量量化编码与解码原理图3.23.2 量化的关键技术量化的关键技术 3.2.13.2.1 码书设计码书设计矢量量化的首要问题是设计出性能好的码书。在矢量维数 k 与码书尺寸 N 已经确定的情况下，好的码书训练方法可以使训练得到的码书性能大大提高，使得编码时的总体量化误差(通常采用均方误差)尽可能小。假设采用平方误差测度作为失真测度，训练矢量数目为 M(M N)，则码书设计的过程可

65、看作对这 M 个训练矢量进行N 数目最优分类的过程，并把各类的质心矢量作为码书的码字。可以证明在这种条件下各种可能的码书个数为:基于信源模型图像编码的数据压缩算法的研究与实现 第三章 矢量量化图像编码的研究20 (3-3)01( 1)*NN iiMNiCiN其中心为组合数。然而，在 N 和 M 比较大的情况下，建立这样一个大尺寸的码iNC书会带来存储上的问题，更严重的是由于码书设计和编码时码字搜索的计算复杂度随着码书尺寸 N 的增大呈指数增加，使得大尺寸码书的应用受到实际编码设备的限制而难以实现。从实用角度讲，码书设计算法应保证所得到的码书具有高的性能，同时算法的复杂度也要在可以接受的范围之内

66、。对于灰度、色度和纹理信息丰富的图像信源而言，要在码书设计算法的性能和计算量之间的取得平衡并不容易。1980 年 Linde、Buzo 和 Gray 将劳埃德最佳标量量化算法在多维空间上进行推广提出一种有效的矢量量化码书设计方法经典的 LBG 算法3，也称作GLA(General Lloyd Algorithm)算法。该算法基于最佳矢量量化器设计的最近邻条件和质心条件这两个必要条件，其特点是概念清晰、算法理论严谨且算法实现方便。质心条件是指在量化区间预先知道的情况下，使噪声最小的各量化值应是各量化区间的质心；最佳划分条件是指在给定一组量化值的条件下，相应的最佳量化区间的诸端点值应为相邻两个量化值的中点。推广到矢量量化编码中，最近邻条件和质心条件可以分别定义为：(1) 最近邻条件对已给定的输出电平(码字)集合(码书)C，最优划分单元应满足： (3-4) : ( ,);ijRx d x yij这种划分也被称为 Voronoi 划分。(2) 质心条件对已给定的划分，最优码字应满足：;1,2,.,iR iN (3-5)()iiycent RLBG 采用迭代的方法轮流满足(3-4)和(3-5)以