第2章 人脸图像分形编码压缩算法
2.1 数字图像压缩技术
数字图像压缩是解决数字图像传输和存储的主要途径之一。所谓数据压缩，就是以较少的数码表示信源所发出的信息，减少容纳给定消息集合或数据采样集合的信号空间。信号空间是指数据存储介质的物理空间、传输信息的时间区间以及电磁频谱区域带宽，也就是指某信号集合所占的空域、时域和频域空间。信号空间的这几种形式是相互关联的，存储空间的减少也意味着传输效率的提高与占用带宽的节省。只要采用某种方法来减少某一种信号空间，都能压缩数据。
压缩数据量的重要方法是消除冗余数据。从数学角度来说，是要将原始图像转化为从统计角度看尽可能不相关的数据集。这个转换要在对图像进行存储、处理和传输之前进行，而在这之后需要将压缩了的图像解压缩以重建原始图像或其近视图像。图像压缩和图像解压缩都是图像编码要研究的问题，分别称为图像编码和图像解码。根据解码结果对原图像的保真程度，图像压缩分为限失真压缩和无失真压缩。无失真压缩常用于图像存档，如医学图像和遥感图像，在压缩和解压缩过程中没有信息损失。目前技术所能提供的压缩比一般在2～10之间。限失真压缩常能取得较高的压缩比，但图像经过压缩后并不能无失真恢复，所以只能用于允许存在一定信息损失的应用场合。
第二代图像编码技术是Kunt[2.1]等人于1985年提出的，他们认为，第一代图像编码技术以信息论和数字信号处理技术为理论基础，旨在去除图像数据中的线性相关性。这类技术去除客观和视觉的冗余信息的能力已接近极限，其压缩比不高，大约为10∶1。第二代图像编码技术是不局限于信息论框架的，要求充分利用人的视觉、生理、心理和图像信源的各种特征，能获得高压缩比的一类编码技术，其压缩比多在30∶1～70∶1之间，有的甚至高达100∶1。
20世纪80年代中后期，人们相继提出了在多个分辨率下表示图像的方案，主要方法有子带压缩编码、金字塔压缩编码等。它们首先利用不同类型的线性滤波器，将图像分解到不同频带中，然后对不同频带的系数采用不同的压缩编码方法。这些方法均在不同程度上有如下优点：多分辨率的信号表示有利于信号的渐进式传输；不同分辨率的信号占用不同的频带，便于引入视觉特性。1988年，Barnsley和Sloan[2.2]共同提出了分形图像压缩编码方案，该方案利用图像中固有的自相似性来构造一个紧缩变换，并使原图像成为该紧缩变换的吸引子。编码时只需存储变化的参数，解码时需要利用该变化对任一幅图像不断地进行迭代变换。此方案具有思路新颖、压缩潜力大、解码与分辨率无关性等特点，是一种很有潜力的编码方法。
1987年，Mallat首次巧妙地将计算机视觉领域内的多尺度分析思想引入到了小波变换中，统一了在此之前的各种小波的构造方法。之后，他又研究了小波变换的离散形式，并将相应的算法应用于图像的分解与重构中，为随后的小波图像压缩编码奠定了基础。
进入20世纪90年代，又取得了一系列图像压缩编码研究的阶段性新成果，其中，EZW编码算法、SPIHT编码算法被认为是目前世界上比较先进的图像压缩编码算法，这两种算法均具有结构简单、无需任何训练、支持多码率、图像复原质量较理想等优点，但同时又都不同程度地存在算法时间复杂度和空间复杂度过高的弱点。而小波变换的图像压缩编码算法和分形压缩编码算法已成为目前图像压缩研究领域的重要方向之一。
2.1.1 目前主要的图像压缩编码标准
图像编码的研究内容是图像数据压缩，其主要应用领域是图像通信和图像存储。当需要对所传输或存储的图像信息进行高比率压缩时，必须采取复杂的图像编码技术。但是，如果没有一个共同的标准做基础，不同系统间不能兼容，除非每一编码方法的各个细节完全相同，否则系统间的连接十分困难，鉴于这一状况，国际电信联盟（International Telecom-munication Union, ITU）、国际标准化组织（International Organization for Standardization, ISO）和国际电工委员会（International Electrotechnical Commission, IEC）近年来在全世界范围内积极工作，已经制定并在继续制定一系列静止和活动图像编码的国际标准，这些标准和建议是在相应领域工作的各国专家合作研究的成果和经验的总结，由于这些国际标准的出现，图像编码尤其是视频图像压缩编码技术得到了飞速发展。目前，按照这些标准做的硬件、软件产品和专用集成电路已经在市场上大量涌现，对现代图像通信的迅速发展及开拓图像编码新的应用领域（如多媒体通信、数字高清晰度电视传输等）发挥了重要作用，这些标准主要包括以下几种。
1.JPEG（Joint Photographic Expert Group）标准
“联合图像专家组”（JPEG）经过5年的细致工作后，于1991年3月提出ISO CD 10918号建议草案：“多灰度静止图像的数字压缩编码”。主要技术为：基本系统（Baseline System）提供顺序扫描重建的图像，实现信息有丢失的图像压缩，而重建图像要达到难以观察出图像损伤的要求。它采用8×8像素自适应DCT算法、量化以及霍夫曼型的熵编码器；扩展系统（Extended System）选用累进工作方式，编码过程采用具有自适应能力的算术编码。无失真预测编码，采用帧内预测编码及霍夫曼编码（或算术编码），可保证重建图像数据与原始图像数据完全相同（即均方误差等于零）。采用JPEG基本系统压缩方案，图像平均压缩比可达16∶1。由于JPEG优良的品质，使它在短短几年内获得了极大的成功，被广泛应用于互联网和数码相机领域，传统的JPEG压缩技术已经无法满足人们对多媒体影像资料的要求，于是，一种功能更强大、效率更卓越的静止图像压缩标准被提到制定日程上，这就是JPEG2000。
2.JPEG2000标准
JPEG2000的制定始于1973年3月，但因为无法很快确定算法，耽误了不少时间，直到2000年3月，规定基本编码系统的最终协议草案才出台。目前JPEG2000已由ISO和IEC（国际电工协会）JTC1 SC29标准化小组正式命名为“ISO15444”。JPEG2000的基本部分（Part1）已经作为ISO标准公布于世，JPEG2000的Part2和Motion JPEG2000的标准化进程也相当顺利。这两部分内容目前已经分别处于Final Committee Draft阶段和Committee Draft 1.0阶段。有关专利许可方面的问题也有了相当的进展。
JPEG2000拥有5种层次的编码形式：彩色静态画面采用JPEG编码、二值图像采用JPEG、低压缩率图像采用JPEGLS等，成为应对各种图像的通用编码方式。在编码算法上， JPEG2000采用离散小波变换（DWT）和bit plain算术编码（MQ coder）。此外，JPEG2000还能根据用户的线路速度以及使用方式（在个人计算机上或在PDA上），以不同的分辨率及压缩率传送图像。
JPEG2000作为JPEG的升级版，具有以下特点。
① 高压缩率。JPEG2000压缩性能比JPEG提高了30%～50%。也就是说，在同样的图像质量下，JPEG2000比JPEG的系统稳定性好，运行平稳，抗干扰性好，易于操作。
② 同时支持有损和无损压缩。JPEG只支持有损压缩，而JPEG2000能支持无损压缩。在实际应用中，诸如卫星遥感图像、医学图像、文物照片等重要的图像都非常适合于采用JPEG2000压缩。目前，对图像进行无损编码的经典方法——预测法已经发展成熟，并作为一个标准写入了JPEG2000。
③ 实现了渐进传输。这是JPEG2000一个极其重要的特征，它可以先传输图像的轮廓，然后逐步传输数据，不断提高图像质量，让图像由朦胧到清晰显示，而不必像现在的JPEG那样，由上到下慢慢显示，这在网络传输中有重大意义。
④ 支持“感兴趣区域”（Region of Interest, RoI）。用户可以任意指定图像上感兴趣区域的压缩质量，还可以选择指定的部分先解压缩，重点突出。这种方法的优点在于它结合了接收方对压缩的主观需求，实现了交互式压缩。
⑤ JPEG2000允许在压缩的图像文件中含有对图像内容的说明和描述。
⑥ JPEG2000允许通过水印、冲压、标签、指纹、加密等方式对图像进行保护。
JPEG2000与传统JPEG最大的不同在于它放弃了JPEG所采用的以离散余弦变换为主的区块编码方式，转而采用以小波变换为主的多分辨率解析编码方式。余弦变换是经典的谱分析工具，它考察的是整个时域过程的频域特征或整个频域过程的时域特征，因此对于平稳过程，它有很好的效果，但对于非平稳过程，它却有诸多不足。在JPEG中，离散余弦变换把图像压缩划分为8×8的小块，然后依次放入文件中，这种算法靠丢弃频率信息实现压缩，因而图像的压缩率越高，频率信息被丢弃的越多。在极端情况下，JPEG图像只保留了反映图像外貌的基本信息，精细的图像细节都损失了。小波变换是现代谱分析工具，它既能考察局部时域过程的频域特征，又能考察局部频域过程的时域特征，因此即使对于非平稳过程，处理起来也得心应手，它能将图像变换为一系列小波系数，这些系数可以被高效压缩和存储。此外，小波的粗略边缘可以更好地表现图像，消除了DCT压缩普遍具有的方块效应。
2.1.2 分形图像压缩方法及发展现状
分形图像压缩一词是美国数学家M. F. Barnsley于1987年提出的。次年，他和合作者A. D. Sloan发表了一篇题为A Better Way to Compress Images的文章[2.2]。在此文章中，他们将Hutchinson于1981年提出的迭代函数系统（IFS）应用到图像压缩编码中，获得了极好的压缩性能。这种压缩方法达到了以往熵压缩编码的理论界限，新颖、有效。但这种方法的缺点是在图像分割时需要人机交互，对操作者有较高的要求。此方案在当时并未引起太多的注意。1990年，M. F. Barnsley的博士生A. E. Jacquin发表了一种基于方块的分形图像压缩方案[2.3][2.18]。在其方案中首先将图像划分为固定大小的互不重叠的小块Ri（排列块），同时也将图像划分为较大的、可相互重叠的区域块Dj。然后对每个排列块Ri寻找可以匹配的区域块Dj，使Dj通过收缩变换Wi可以近似于Ri，这样找出的一组变换组合W1,W2, …,Wn，就是该图像的IFS代码。解码时采用拼贴定理，将IFS代码反复迭代作用于任意一初始图像，即可获得分形图像。这些操作都可由计算机自动完成，它为分形图像编码的研究带来了一次质的飞跃。
分形图像编码是目前较有发展前途的图像编码方法之一，也是目前研究较为广泛的编码方法之一。对其研究已有近十年的历史，其间人们发现了它所具有的许多优点。比如，它突破以往熵压缩编码的界限，在编码过程中，采用了类似描述的方法。解码是通过迭代完成的，且具有分辨率无关的解码特性等。随着国内外研究的广泛深入，人们在赞叹其新颖的编码思路的同时，也发现了一些缺点，因此许多改进的编码方案不断出现。目前分形编码方案大致有三个发展方向：加快分形的编解码速度、提高分形编码质量、基于分形的低码率视频编码。
经典分形算法的复杂性导致编码速度慢，一直是分形编码实用化的最大障碍。Fisher和Jacob提出了根据灰度均值和方差进行分类的方法将图像分为四个子块（左上、右上、左下、右下）并计算每个子块的灰度均值和方差。根据四个子块的灰度均值，将图像块做不同的旋转和对称变换，将图像块分为三类。然后，在每一大类中，根据四个子块的方差的排列顺序，可以定义出24个子类。这样可把图像块共分成72类，在为每一个排列块寻找匹配区域块时，只在同类的区域块内进行搜索，即减少区域块池中区域块的数目，从而缩短编码时间。Masaki Harada等人提出了一种快速计算分形图像编码的IFS参数的算法[2.4]。在这种算法中提出了两种减少计算时间的方法。第一种方法为使用最大幅度比率（排列块范围最大幅度和区域块范围最大幅度的比值）来减少仿射变换、均方误差的计算时间，在计算仿射变换参数前，将不满足条件的区域块排除。每二种方法为使用方差比率法（排列块方差和区域块的比率）来减少比例参数的计算时间。如果将这两种方法相结合，则可以将编码速度提高50%左右。T. K. Truong等人[2.5]提出了一种分形图像压缩的快速分类方法。对每一个图像块进行离散余弦变换，在频域中，根据最低频率的系数在水平方向和垂直方向上值的大小将它分为三类：非边缘块、水平/垂直块、对角线块，在匹配时只在相应的类内进行搜索。这种方法分类简单并且DCT变换容易实现，可以起到很好的加速作用。Ismail Salih等人提出了一种通过逼迫拼贴误差来进行分形图像编码的方法[2.6]，这种方法的性能优于四叉树分割的方法。
以上这些方法都是寻求如何进行快速搜索的解决方案。另一种途径是通过排除许多区域来减少搜索量，进而达到加速的目的。通过对经典分形编码算法的研究，人们发现对某一排列块进行匹配时，许多区域块就没有用到。Saupe的倾斜区域池方法[2.7]，其原理是丢弃一部分方差较小的区域块。因为这种方法不是自适应的，所以其编码速度提高的同时，图像质量有所下降。Dekking提出了一种一维函数的方法[2.8]，其原理是通过使用一个不等式来排除那些和给定排列块不相匹配的区域块，这种方法可以在不损伤编码图像质量的条件下获得较好的加速效果。Chong Sze Tong提出了一种基于自适应搜索的快速分形图像编码方法[2.9]。在这种方法中，使用排列块的均值来代替亮度偏移因子作为一个参数，这个参数较经典的亮度因子参数有较多的优点，并由此对新的仿射参数给出了优化的量化编码和位分配方案。同时还引入了一种自适应的搜索编码方法，它可以在保持较高解码图像质量时起到很好的加速作用。Jean Cardinal[2.10]将排列块和区域块用它们所对应的特征向量空间进行分割，如果区域块和排列块所对应的特征向量落在同一个集合内，则达到了最佳匹配。其实质是基于图像块特征空间的一个几何分割。
人们对分形解码图像的研究发现，与其他经典的压缩方法相比，分形解码图像的质量较低。因此提高编码质量也是目前分形编码的重要方向之一。目前，提高分形编码质量的方法有三种：采用混合编码方案、改进分割方案及改进灰度逼迫能力等。Jacquin方案[2.3]在采用较大排列块时，图像细节部分匹配效果不佳，往往引起恢复图像质量不好；而经典的一些编码方法在较低压缩比时效果较好，因此许多研究者就将分形与这些编码方法混合使用，扬长避短。Trieu-Truong等人将DCT与分形结合[2.11]，在频域中计算排列块的均方误差和区域块的8种对等变换，来消除冗余计算。这种方法可有效提高恢复图像的细节质量。分形与小波联合编码是目前分形研究的一个发展方向。G. M. Davis在其论文中[2.12]对分形和小波的关系进行了细致分析，发现Jacquin提出的方案是一种Haar小波子树量化方案，并将其方案推广到其他平滑子波，收到了较好的压缩效果。Jin Litk C. C. Jay Kuo[2.13]使用分形收缩变换来从低分辨率的小波系数中预测高分辨率的小波系数，然后用位平面小波编码器对预测误差进行编码。Charavi-Alkhasari等人[2.14]将方块变换、VQ和分形结合起来，在寻找相似定义域子块时，既可以像分形编码那样在较大子块中寻找，又可以像VQ那样在相同大小的子块中寻找，因此该方案既利用了不同分辨率下的自相似性又利用了相同分辨率下的自相似性，提高了编码质量。Raouf等人[2.15]用聚类算法从一系列训练图像中设计一些固定向量，当用它作为辅助向量量化码书时，不但可以加快区域块的搜索，而且可以提高比特率失真性能。
另一类提高编码质量的方法是对经典分割方法的改进。在Jacquin最初提出的方案中，采用固定大小的方块分割，由于受灰度线性逼近的限制，在采用较大的方块时，虽可以获得较高的压缩比，但图像质量较差，而采用较小的方块时，灰度的逼近较好，编码质量较高，但压缩比较低。因此，一些研究人员通过改进分割方案来改进图像质量。
Y. Fisher[2.3]等人提出了四象限的划分方式，分割按多层进行，使分形压缩的质量和压缩速度有了较大的提高，是目前较为实用的压缩方法。Frank Davoine等人[2.16]提出了一种Delaunay三角形分割方案，它除了具有Fisher三角形分割方案的优点外，其三角形的方向和大小是任意性的。Riccardo[2.17]提出了一种B树三角形编码方案，将区域块循环分割成直角三角形，并以二进制树的形式排列。
在实际应用中，序列图像较静止图像有着更广阔的应用场合。由于时间维的引入，编码方法也有新的变化。因此序列图像编码是图像编码的热点之一。由于分形图像编码在低码率压缩方面的独到之处，因此分形编码又被广泛地应用到序列图像之中。1994年，加拿大学者Lazar等人发表了一篇论文，将Jacquin[2.18]的分形编码从二维变换直接推广到三维。Bernd Hurtgen等人将分形编码用于低码率视频编码中，他们首先将当前帧和前一帧相减，根据差值的大小将当前帧划分为背景和前景，仅对前景采用多层分割进行分形编码。Chang-Su Kim[2.19]等人提出了一种基于循环预测变换编码和非收缩帧间变换的视频序列分形编码技术，通过用邻近帧中和排列块同样大小的区域块来近似该块，有效地利用了图像序列中的时间相关性，在低比特率时具有很好的性能。