图像压缩文献综述

1、 数字图像处理和模式识别期末大作业题目： 图像压缩文献综述 班级： 数字媒体学院计算机技术 姓名： 徐德荣 学号： 6141603020 图像压缩文献综述1 图像压缩编码概述图像信息的压缩编码，是根据图像信号固有的统计特性和人类的视觉特性进行的。图像信号固有的统计特性表明，其相邻像素之间、相邻行之间或者相邻帧之间，都存在较强的相关特性。利用某种编码方法在一定程度上消除这些相关特性，便可实现图像信息的数据压缩。这个过程也就是尽量去除与图像质量无关的冗余信息，属于信息保持（保持有效信息）的压缩编码。另一种考虑是，图像最终是由人眼或经过观测仪器来观看或判决的。根据视觉的生理学、心理学特性，可以允许图

2、像经过压缩编码后所得的复原图像有一定的图像失真，只要这种失真是一般观众难以察觉的。这种压缩编码属于信息非保持编码，因为它使图像信息有一定程度的丢失。由此可见，图像压缩编码的研究重点是：怎样利用图像固有的统计特性，以及视觉的生理学、心理学特性，或者记录设备和显示设备等的特性，经过压缩编码从原始图像信息中提取有效信息，尽量去除那些无关的冗余信息，并且在保证质量（能从这些数据中恢复出与原图像差不多的图像）的前提下，用最低的数码率或最少的存储容量，实现各类图像的数字存储、数字记录或数字传输。2 图像编码研究现状 图像压缩编码技术可以追溯到1948年提出的电视信号数字化,到今天己经有五十多年的历史。五十

3、年代和六十年代的图像压缩技术由于受到电路技术等的制约,仅仅停留在预测编码、亚采样以及内插复原等技术的研究,还很不成熟。1969年在美国召开的第一届“图像编码会议”标志着图像编码作为一门独立的学科诞生了。到了70年代和80年代,图像压缩技术的主要成果体现在变换编码技术上;矢量量化编码技术也有较大发展,有关于图像编码技术的科技成果和科技论文与日俱增,图像编码技术开始走向繁荣。自80年代后期以后,由于小波变换理论,分形理论,人工神经网络理论,视觉仿真理论的建立,人们开始突破传统的信源编码理论,例如不再假设图像是平稳的随机场。图像压缩编码向着更高的压缩比和更好的压缩质量的道路前进,进入了一个崭新的、欣

4、欣向荣的大发展时期。 数字图像压缩技术可以分为无损压缩技术和有损压缩技术。图像无损压缩技术主要有:位平面编码、无损预测编码(DPCM)以及有损编码与无损编码的组合编码技术。传统的数字图像有损压缩技术主要有预测(PCM、DPCM)、方块化、矢量量化、层次、子频带和变换等等。近年来,人们又提出了神经网络法、几何模型化、分形和小波变换等编码技术。通常认为,JBIG、JPEG、JPEG2000、MEPG一l、MPEG一2、MEPG一4、MPEG一7等图像压缩国际标准是针对不同应用的最佳压缩算法。在这些标准之中成功地采用了以上的一种或多种混合压缩技术。3 图像压缩编码的典型方法3.1统计编码算法 统计编

5、码是一类根据信息熵原理进行的信息保持型、变字长的编码方式，也称熵编码。编码时对出现概率高的被编码符号用短码表示，对出现概率低的被编码符号则用长码表示。在目前图像编码国际标准中，常见的熵编码有霍夫曼（Huffman）编码和算术编码。Huffman 编码可以实现图像的无损压缩，压缩比介于 2:15:1 之间。所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。因此，现代压缩技术通常只将 Huffman 视作最终的编码手段。实际的压缩编码中，码率很难达到熵值（理论上的平均信息量），不过，熵可以作为衡量一种压缩算法的压缩比好坏的标准，码率越接近熵值，压缩比越高。算术编码是到目前为

6、止编码效率最高的统计熵编码方法，它比 Huffman 编码效率提高10%左右。算术编码的一个重要特点就是可以按分数比特逼近信源熵，突破了Huffman编码每个符号只能按整数比特逼近信源熵的限制。另外，比较容易实现动态自适应。自适应算术编码具有实时性好、灵活性高、适应性强等特点，在图像压缩、视频图像编码等领域都得到了广泛的应用。3.2预测编码算法预测编码是利用图像信号在局部空间和时间范围内的高度相关性，依据已经传出的近邻像素的值作为参考，预测当前的像素值，然后量化、编码预测误差。在进行预测编码时，不直接传送图像样值本身，而是对图像的实际样值与它的一个预测值之间的差值进行编码和传送。如果这一差值，

7、即预测误差不被再次量化而直接传送，这就是无损预测编码（信息保持型预测编码）。如果允许压缩过程中存在客观信息损失，则可以进一步利用人的主观视觉特性对预测误差再次量化后再编码传送，从而获得更高的压缩比，这就是差分脉冲编码调制（DPCM, differential pulse code modulation）。如果量化器只有两个输出电平（量化层数为 2），则称为增量调制（M），是 DPCM 的一种特殊形式。由于预测编码的算法较为简单，容易用硬件实现，早年就得到较多的研究和应用。1952 年，Oliver 对图像的线性预测法作了理论研究。1958 年，Graham 首次用计算机模拟法研究 DPCM 编

8、码方法。1966 年，ONeal 依据最小均方差准则，用计算机模拟5法对图像 DPCM 中的线性预测器和量化器作了系统讨论。1969 年，Mounts 等首次提出帧间预测编码的方法，帧间预测编码应用广泛，在视频编码标准（如 H.261，H.263，H.264，MPEG1-4）中得到采用。预测编码在图像与视频编码中占有重要地位，但是它也有弱点，突出表现为对信道误码的敏感性方面。3.3变换编码算法变换编码是将一组像素值，经过某种形式的正交变换，转换成一组变换系数，然后根据人的主观视觉特性，对各变换系数进行不同精度的量化后再编码。正交变换的作用是解除像素值之间的空间相关性，降低冗余度。用于图像编码的

9、正交变换有：离散傅立叶变换（DFT）、沃什（Walsh-Hadamard）变换（WHT）、哈尔变换（HRT）、离散余弦变换（DCT）、K-L 变换（KLT）、斜变换（SLT）等。除了 K-L 变换外，上述变换都有快速算法。K-L 变换是在最小均方误差准则下进行图像压缩的最佳变换，但由于它的变换矩阵随图像内容而异，所以没有快速算法，也就不适宜用于实时编码。相比之下，DCT 是性能最接近 KLT 的次最优算法，也是目前应用最为广泛的变换编码方法，而且是 JPEG 标准的核心算法。变换编码能充分利用图像所具有的二维或三维相关性，来得到高于预测编码的编码效率。正交变换比较容易实现，已成为图像编码算法的

10、主流。DCT 算法突出的问题是：在低比特率编码时块状编码失真明显。这是因为将图像信号从空间域向频率域变换后，进行有效压缩所采用是的离散余弦变换，它将图像划分成方块域，而后各块内产生的编码失真在块边缘形成了不连续的状况。3.3.1 基于DCT变换的图像编码算法（1）DCT编码最小均方误差条件下得出的最佳正交变换是K一L变换,而离散余弦变换(DCT)是仅次于K一L变换的次最佳变换l0,且已获得广泛应用,并成为许多图像编码国际标准的核心。离散余弦变换的变换核为余弦函数,计算速度较快,有利于图像压缩和其他处理。在大多数情况下,离散余弦变换DCT用于图像的压缩操作中的基本思路是,将图像分解为8X8的子块

11、或16x16的子块,并对每一个子块进行单独的DCT变换,然后对变换结果进行量化、编码。DCT压缩编码是一种正交变换编码,将二维图像变换成它的空间频谱,将其按由低频到高频的顺序重排。由于图像频谱从低到高逐渐衰减,故可在一定量化等级下进行舍弃,从而达到压缩的目的。DCT广泛应用于众多压缩方案的原因在于其理论、算法和硬件相对成熟,去相关性好,适应人眼的视觉特性,计算量不大(没有复数计算),易于实现。基于DCT的混合编码技术对于彩色图像的压缩倍数可以达到几十倍乃至上百倍,而且重建的图像又具有较高的质量,因此得到广泛的应用。近年来,基于DCT变换域的分析、处理操作的研究十分活跃,其主要原因在于JPEG和

12、MPEG等国际压缩标准都是以DCT变换为基础的,而大量的图像数据都采用国际标准进行压缩。（2）一维DCT算法长度为N的一维序列x(n):n=O,1,，,N一1的DCT定义为:其中，为正交化因子,它是为了保证变换基的规范正交性而引入的。一维DCT反变换(IDCT)为:若以N维矢量x表示原始数据,N维矢量X表示DCT变换系数,则有如下矩阵形式: 其中变换矩阵u为:可见u是一个正交矩阵,但不是对称矩阵,反变换(IDCT)矩阵除了行、列序号互换外,形式上与u完全相同。(3)二维DCT算法二维数据 的20一DCT定义为:其中定义与一维DCT变换中定义相同,写成矩阵形式: 其中,u为NxN变换系数阵列,v

13、J为MxM的变换系数阵列。也可表示为下列矩阵形式:其中:x输入数据矩阵(NxM)XDCT系数矩阵（NxM）C(N)N点DCT变换矩阵（NxN）；为其转置。二维DCT的变换核实可分离的，即二维DCT可以分解成行方向的一维DCT和列方向的一维DCT，可用两次一维DCT实现二维DCT，此法称为”行列法”。（4）层次DCT变换方法一直以来,对DCT系数的量化只是局限于每个图像子块中,没有利用到子块图像的相关性,如果我们用频带的观点来看待DCT系数,组成类似子波变换后的结构,就可以把整个图像作整体考虑,克服了图像子块独立处理的缺点,为获得更高的压缩率打下基础。首先将输入图像进行第一层的DCT变换,变换后

14、的图像可以看成是类似于小波变换的子带结构。上图（a）一幅图像首先被分解为四个子图像和,分别分别称为低频子图像,垂直方向子图像,水平方向子图像和高频子图像。利用DCT变换的能量集中性好的特性,只对域的频域系数做DCT反变换,这样恢复到空间域的图像数据再做第二层的DCT变换;同样变换后的空间域图像数据成为频域的系数集,再次利用DCT变换的能量集中性的特性,也只对域的频域系数做第二次DCT反变换,这样恢复到空间域的图像数据再做第三层的DCT变换.如图（b）这样一幅MxN的原始图像经过第一次DCT变换后,分解成4个(M/2)x(N/2)的子带,每个子带经DCT反变换后都是一幅完整的图像,只是各自反映了

15、同一幅图像的不同信息。其中, 是图像的高频系数,反映了图像的细节部分。取做DCT反变换,恢复出一幅完整的图像,进一步对其分解,做第二次DCT变换,同样分解成四个子带,每个子带经DCT变换后也都是一幅完整图像,各自反映了同一幅图像的不同信息。重复上述步骤,再做第三次DCT变换,分解出,具体如下图所示，一幅待编码的图像经过L级变换后得到3L+1幅不同尺度的子带图像。图像经过层次DCT变换后生成的图像的数据总量与原图像的数据量相等,即DCT变换本身并不进行数据压缩,之所以将它用于图像压缩,是因为生成的DCT图像具有与原图像不同的特性,表现在图像的能量主要集中于低频部分,而水平、垂直和对角线部分的能量

16、则较少;水平、垂直和对角线部分表征了原图像在水平、垂直和对角线部分的边缘信息,具有明显的方向特性。低频部分可以称作亮度图像,水平、垂直和对角线部分可以称作细节图像。对所得的四个子图,还应根据人类的视觉心理和心理特点分别作不同策略的量化和编码处理。一直以来,对DCT系数的量化只是局限于每个图像子块中,没有利用到子块图像的相关性,如果我们用频带的观点来看待DCT系数,组成类系子波变换后的机构,这样就可以把整个图像作为整体考虑,克服了图像子块独立处理的缺点,为获得更高的压缩率打下基础。加之人眼对亮度图像部分的信息特别,对这一部分的压缩应尽可能减少失真或者无失真,对细节图像可以采用压缩比较高的编码方案

17、。层次DCT变换的这一特性与小波变换具有相同的特征,但运算的复杂性却大大降低。3.4矢量量化编码算法矢量量化编码的理论基础是香农的率失真理论。Gersho 在 1979 年从理论上证得：当矢量量化中的矢量维数不断增加时，编码性能将无限接近于称之为码率失真界限的信息压缩极限。矢量量化编码的突出优点是解码简单，主要缺点是编码过程计算复杂，矢量量化编码所能达到的图像质量取决于很多因素，包括像素矢量块的大小、像素之间的相关性、码速对编码图像的适应性等。该方法主要适合于低码率图像编码。小波变换压缩算法小波变换弥补了DCT不适合对宽带信号进行压缩的缺陷，是一种不受带宽约束的数据压缩方法。其基本思想是：用一

18、族小波基去逼近一个信号。小波变换的特点是：它具有时频分析的能力，能把图像信号的能量聚集于某些频带中，这一特点有利于压缩编码。对于窄带信号，它可以通过缩小的方法使得对信号的描述较为精细；而对于宽带信号，则可以通过放大的方式使刻画满足精度的需要。小波变换和逆变换具有形式上的完美的对称性，且具有基于卷积和正交镜像滤波器的塔形快速算法。系数编码是小波算法最具特色的部分，常用的有嵌入式小波零树编码（EZW）、层次树分割集（SPIHT）等。这些方法主要是利用了小波分解图像各频带间的继承关系，采用门限过滤算法将系数按其对于重建图像贡献大小依次发送的思想。小波变换（WT）用于图像压缩技术的一系列优点在于：它具

19、有宜与人类视觉系统（Human Visual System，HVS）相结合的潜力，从而可在同样的平均码率下，获得质量更好的重建图像，或在相同的评价条件下，得到更高的图像压缩比。但小波变换也存在一定的问题。如到目前为止，成熟的小波基极其有限，利用多分辨分析构成的一些类型的小波基，大多无解析表达式，多是一些分段函数的傅氏变换形式；常用的紧支正交小波基不能满足实际中对称性的要求；平缓信号的分析不如傅氏变换；正交小波基对于时、频局部性要求都很高的问题显得力不从心。3.4.1 基于小波变换的 EZW 算法。（1）EZW 原理在EZW算法中，待编码的小波系数的重要性一般都是利用阈值来进行预测的。假设给定的

20、阈值为 T，若当前小波系数的绝对值 x 小于阈值 T，则认为 x 是关于阈值 T 的不重要的系数，假如它的所有的子代系数关于 T 也是不重要的，则把 x 称为阈值 T 的零树根. 若 x 的绝对值大于 T 则认为是重要的系数.对于一个给定的阈值，EZW 算法是按照下面的扫描方式。EZW 的量化编码是采用逐次逼近量化的方式进行的，要对图像进行多次的扫描。但每一次的扫描均包含以下的几个步骤： 取阈值对于一个 L 级的小波变换来说，算法所采用的是一个阈值序列：来判断当前小波系数的重要性。其中：i为扫描的次数。其中：i=1,2.L-1。一般初始阈值定义为：其中：f(i,j)为小波变换系数集。- 图：E

21、ZW算法扫描顺序 扫描按照如上图 中所示的扫描方式，将当前小波系数与阈值进行比较，输出以下四种编码符号： a：若当前系数的绝对值小于阈值，则该系数为次要系数，并且各级子带系数的绝对值均小于阈值，则输出符号 T，并将其用特殊的符号进行标注，在后续的编码中，对其所有的子系数都不再处理；b：若当前系数的绝对值小于阈值，则该系数为次要系数，但它的子带中有重要的系数，在输出符号 Z；c：若当前系数的绝对值大于阈值且为正,则该系数是正的重要系数，输出符号P；d：若当前系数的绝对值大于阈值且为负,则该系数是负重要系数，输出符号 N；在扫描的过程中，这些符号存储到一张表中，在第i次扫描后，将重要系数的位置上的

22、系数值设置为 0，在下次扫描过时则直接跳过这些位置. 辅扫描辅扫描主要是在主扫描中被认为是重要系数的小波系数进行量化编码。在量化要首先构造量化器，量化器具有一个区间，区间的最大值为初始阈值的 2 倍，最小值为当前的阈值，所以输入区间为，将输入区间分为两个区间若系数属于区间则量化为“0”，在重构时，重构值为 1.25，若属于区间则量化为“1”。重构值为 1.75。并用一张辅表存储这些二进制符号流。 新排序在下一次的扫描进行之前，要将辅表中的重要系数进行排序。排序所用的标准是重要系数所在的区间值的大小，即将幅值在中的数据排在幅值位于的数据之前。因此在本级的编码中，被优先编码的是那些排在前面的幅值较

23、大的系数。 出编码符号流EZW 编码算法中，编码器的输出主要包括两个部分的信息：传解码端的信息和编码端用于下次扫描的信息。其中，解码端的信息主要有主、辅扫描表和阈值；编码器端的信息主要是当前所用阈值及重新排序过的重要系数序列。下面2图分别表示的是系数类型编码和图幅值编码的流程图。（2）EZW的算法步骤 综合以上的说明可给出 EZW 算法的主要的步骤如下：1.数字图像进行边界严拓；2.寻找合适的小波基，采用二维离散小波变换对经过边界严拓后的图像进行变换，产生出一系列的子图像；3.据初始阈值的计算公式得出初始阈值；4. 按照上述的主扫描和辅扫描的方法，对图像进行多次扫描，形成主表和辅表；5. 将辅

24、表中存储的重要小波系数量化值的次序进行调整；6. 到达指定的要求停止编码，否则重复和。在解码端，最先得到恢复的是最重要的系数，随后恢复的是在阈值减小一半后控制输出的系数，如此重复的进行，也可以满足要求后即结束解码。在解码的过程中，重要系数的恢复幅值均是所在区间的中间值。3.5分形压缩算法分形压缩的方法是利用图形处理技术把原始图像分割成若干子图像，然后为每个子图像寻找迭代函数（Iterated Function），子图像以迭代函数的形式存储。由于这样的迭代函数一般只需要几个数据表示即可，所以分形压缩可以达到较高的压缩比。解压缩时，只要调出每个子图像对应的迭代函数进行反复迭代，就可以恢复出原来的子

25、图像。分形压缩充分考虑人的视觉特性以及自然景物的特点。其优点是：压缩比取决于图像分割后所产生的子块的大小，子块取得越大，压缩比越高；由于分形变换可把图像划分成大得多、形状复杂得多的分区，故压缩比不受分辨率的影响。缺点有：分形压缩编码是非对称的，压缩时计算量较大，所需时间较长，但是解压缩速度很快；随着被压缩图像尺寸的增大，运算量增长过快。目前的最大障碍在于它的逆问题，即如何寻找任意一幅自然图像的分形迭代码，此方法仍处于不成熟的发展阶段。3.5.1 Jacquin 分形图像压缩算法（1）Jacquin 提出的基于方块划分的分形图像压缩方法是以局部的仿射变换代替全局的仿射变换，此方案为实现了图像的自

26、动分割，为分形压缩编码的研究注入了生机与活力，使其得到快速发展。此后，分形图像编码引起了世界各国研究人员的广泛兴趣和关注，成为目前编码研究的热点。（2）局部迭代函数系统为讨论图像压缩，应首先建立图像数学模型，常用的模型有三种：测度空间、像素数据和函数。1.当以测度作为图像模型时，是把图像表示成平面上的一种测度 ，此时，明暗度就能由平面子集 A上的度量来表示。2.在像素数据模型中，把图像表示为离散像素的集合。3.函数模型就是将图像表示成连续函数 f ( x, y )，( x, y ) 0,1 × 0,1。对于一些实际的图像，不存在整体与局部的自相似性，但经验表明，图像中一些部分存在不同

27、比例的自相似，这些部分不是它们自身在仿射变换下的恒等复制品，而是有误差的。于是产生了局部迭代函数系统，它是 IFS 的推广，只是每个变换 的定义域仅为 X 的一部分。定义 12（局部迭代函数系统LIFS）设( x, d )是完备度量空间， 局部迭代函数系统是下列压缩映射集： 为了能够实现灰度上的匹配，我们对二维的平面映射上再加上灰度的映射作为三维，就构成了带映射的局部迭代函数系统。（3）固定分块算法原理及分析 算法原理本节主要研究灰度图像的 Jacquin 的固定分块分形图像压缩编解码过程。编码过程可分为如下步骤：1）对压缩图像进行分块：Jacquin 不从整幅图像作拼贴来寻找 IFS 码，而

28、是根据局部迭代函数系统，把图像 I 分成为不重叠的N × N个图像块，如8 × 8和4 × 4的方块 ，称为尺寸 R × R的值域块（range）或子块。，且，当 i j时。是分形压缩中的一个编码单元。2）建立搜索空间：用 D × D截取窗口沿待编码图像的水平和垂直方向(即 X Y轴)分别以步长和 移动，每一次移动后的截取方块称为匹配块 (domain block，也称定义域块)，所有 构成搜索空间 。搜索空间的大小即匹配块个数n（）， 由下式计算： 实际算法中通常取 D = 2N = 3）搜索最优匹配块：在搜索空间内，对每一个值域块 ，通过

29、MSE 原则寻找误差最小的匹配块 ，使得 经适当的仿射变换 来逼近 即使之满足：。 如图所示：其中，仿射变换 必须是压缩映射，对灰度图像进行实际操作时，仿射变换一般采用以下三种具体变换的合成： a. 几何缩小变换 G：主要完成从定义域块到值域块的空间收缩映射，通常采用四邻域平均法，相邻四个象素压缩成一个象素，其灰度值为四象素灰度值的平均。 压缩成 ，大小为8 × 8，且 相邻差一个像素，从而形成了新的D 库，使得与 具有相同的空间尺度，通常用下式表示此过程： b. 仿射变换 A：通过适当的对称变换和旋转变换，使得尽可能具有相近的灰度分布。为了减少变换参数所需的存储空间并降低变换的复杂

30、性，对一个方块象素块，A 通常采用第二章的 8 种对称变换方式之一，使得c. 灰度变换 M：取为线性变换，其形式为：，其中 和 分别是灰度变换的尺度因子和偏移因子。将得到的新子块与值域块 的灰度平方误差记为，则平方误差可表示为：要求得最佳匹配，即要使变换后得到的新子块与值域块最相似，就需要使它们对应像素之间的灰度差值最小，灰度平方误差也就最小。利用最小方差准则，可以求得使值最小的s和o。灰度变换尺度因子: 灰度变换偏移因子: 其中 为的平均灰度值，为的平均灰度值；此时，平均误差的最小值为：将与预先定义的灰度平方误差门限L比较，若 < L，则己求得最佳匹配，进行步骤 4）。否则，回到步骤

31、2）的对称旋转变换 A，从下表 中重新选取另外一种变换，并计算相应的和 。若下表所示的所有变换都进行过，未找到最佳匹配，在搜索空间中选择另外一个块，计算其与 是否匹配。重复以上过程，若搜索空间中的所有都计算匹配过，而未能与匹配，即未能找到满足 < L的，则取前述搜索过程中最小的对应的定义域块作为最佳匹配块。4）存储分形编码信息：通常需要存储值域块与其最佳匹配块之间的相对位置，灰度变换尺度因子 s ，灰度偏移因子 o ，对称旋转变换序号 n。以 256 ×256大小的灰度图像为例：分割成8 × 8大小的值域块，以步长 1 分成16 × 16大小的定义域块，采用

32、全局搜索。则个需要 8bits 表示；s 的范围基本为 0 1，可用 3bits进行保存； o 范围为 0 255，需要 8bits 表示；n 为 0 7，采用 3bits。8+8+3+8+3=30bits，而8 × 8大小图像块原来的灰度信息需要 8 × 8 × 8=512bits 表示，因此，压缩比。解码过程如下：分形编码方法的解码就是用我们求得的局部迭代函数系统(LIFS)的吸引子来近似原始图像。编码过程中所得到的 LIFS 是紧缩、收敛的，它的吸引子可以通过对任意的初始图像的不断迭代变换得到。恢复图像与原始图有一定误差，拼贴定理限定了其误差上限。从严格的数

33、学角度上讲，这种迭代是无穷次的，但在实际的数字图像的解码中，迭代 610 次就可以满足要求。 算法分析 Jacquin 分形图像算法虽然实现了全自动编码，整个过程不需要人工交互，但最大的缺陷就是计算量太大，不能达到实用的阶段。这里简单分析一下 Jacquin 编码方案的计算复杂度。对于一个C × C大小的图像，假设值域块的大小为K × K，定义域块的大小为2 K × 2K，则该图像共有个值域块，个定义域块。在 Jacquin 方案中，一个值域块和一个定义域块之间相似性的计算量与 成正比，而对于每一个值域块，要与所有的定义域块进行相似性比较，因此每一个值域块的编码计

34、算量与成线性关系，所以对一幅图像来说，其编码复杂度与成正比，考虑到K 为常数，因此分形图像编码的计算复杂度为O ( )。若考虑到 8 种将 映射到的仿射变换，这意味着对每个值域块中的任一个都要有8 × O ( )次比较。另外定义域块中的像素数目为值域块中的像素数目的 4 倍，所以我们还需要进行下采样或者将定义域块中2 × 2的小块取平均值后对应于值域块中的像素。因此，降低分形图像编码的复杂度，提高编码速度，成为人们研究热点。从20 世纪 90 年代起，很多学者都提出了改进算法。3.5.2 改进的Fisher 分形图像压缩算法 （1）自适应四叉树分割Fisher在Jacqui

35、n的分形图像压缩算法的基础上提出了一种改进的方法自适应四叉树方法分割值域块。和经典的Jacquin分形图像编码相比，四叉树分割法具有分块灵活性高，压缩率高的优点。自适应四叉树方法是一种值域块分块方法，它将图像表示成一棵四叉树，树根就是原图像本身。除叶节点外，树中每个节点均有4个子节点，分别对应于原图像(或图像块)4个象限的子块。原理如图所示：图像自适应分块的目的是将图像合理地划分成不同尺寸的R块，使任意一块都能找到合适的D块与之相应。这样图像中粗糙的部分能以较大的图像块进行变换压缩，提高压缩比；而图像中精细的部分以较小的图像块进行变换压缩，保证较高的图像还原质量。为保证图像质量同时减少分块数，

36、一般在分割图像之前，设定一个误差阈值，先把图像分成尺寸相对较大的固定块，按MSE 准则寻找其最优相似快，如果找不到满足误差阈值要求的相似块，则将它细分为4个尺寸相同的较小块，再重复寻找最优相似块的过程，直到找到所有块的最优相似块或分割的图像块达到设定的最小尺寸为止。在实际操作过程中，常设定块尺寸的最大边长为 ，块尺寸的最小边长为 ，一个边长为 图像块的四叉树编码过程与步骤描述如下：Step 1：设置一空堆栈，置堆栈指针 j = 0，对边长为的块按 MSE 准则寻找其最优相似快，若找到满足误差阈值要求的最佳相似快，转至Step5，否则进入Step2；Step 2：把找不到满足要求的值域块，按图示

37、意分成4个尺寸相同的较小块，记成， i = 1, 2,3, 4，依次压入堆栈，置 j = 4；Step 3：弹出堆栈中的一个块 ， j = j 1，在原图像中搜索4倍规模于 的匹配块 ，对进行伸缩，使得伸缩后的尺寸与值域块 的尺寸相同，对伸缩后的定义域进行仿射变换，进而寻找最优的对比度s和亮度o。按下式计算误差e：其中（ i = 1, 2, , n； j = 1, 2, , m）是定义域块经过旋转反射和伸缩变换后的像素值，（ i = 1, 2, , n； j = 1, 2, , m）是值域块的像素值；Step 4：若 e 小于误差阈值 或图像块 的边长已是预先设定的 ，则保存相似块的像素值，转

38、向Step5；否则把该 块均分成为4，变成4个更小的区域块 ，依次压入堆栈, j = j+ 4,转至Step3；Step 5：若 j = 0，编码结束；否则转至Step3。经过以上方法进行分解后，其最终的值域块的集合可能包含多种不同尺寸的方块。虽然从理论上来说，如果块的大小取1×1或2×2或N × N，是可行的，在分形图像压缩中显然是不合适的。因此，在实际中我们常取最小块为4×4，最大块( N / 2 ) × ( N/ 2)。（2）相似块集合的矩分类为了配合分割法预处理的自适应四叉树图像分块，把经过四叉树分割后的值域块和定义域块都分成四个等大小

39、的子块，然后分别计算出这四个子块的均值 ( i = 1, 2,3, 4)和方差（ i = 1, 2,3, 4），根据子块均值 ( i = 1, 2,3, 4)的排列组合，应该有24种不同的类型。但是考虑到前面介绍的块的8种仿射变换（4种旋转，4种对折），这24种类型可以归并为3种主类。这样就可以先把值域块和定义域块分成三个主类之一（图3.4表示了3个主类对应的亮度层次）：其次，再根据子块方差（ i = 1, 2,3, 4）的排列组合，也得到24种类型（经过仿射变换后，这24种类型不能归并，即没有相同的类型）。这样就又把每个主类又分成24个子类，总共可以分成72类。编码时，先进行预处理，将所有的

40、定义域按上述方法归类，然后在对某一个给定的值域块编码时，也先对它进行归类，搜索时就只在与其同类的定义域块集中寻找匹配的定义域块。这样需要与值域块进行匹配计算的定义域块的数目，即搜索空间就大大减少了，从而可以达到加快编码的目的，同时还能保证解码图像质量几乎不变。解码时，自适应的解码原理同基本分形图像压缩算法解码原理相同。3.6基于神经网络的压缩算法人工神经网络（Artificial Neural Net，ANN）简称神经网络，是对人脑或自然神经网络若干基本特性的抽象和模拟。人工神经网络由大量的神经元模型所组成，实际上是一个超大规模的非线性连续时间动力自适应信息处理系统。目前人工神经网络在人工智能

41、、模式识别、图像处理等领域都有着重要应用。基于神经网络的压缩算法试图在解决好充分利用人的视觉特性这个问题上有所突破。目前直接用于图像压缩的神经网络主要有BP（Back Propagation）网络和自组织映射神经网络。BP 网络是一种按误差逆传播算法训练的多层前馈网络，是目前应用最广泛的神经网络模型之一。该算法的思想为：把一组输入模式通过少量的隐节点映射到一组输出模式，并使输出模式尽可能的等同于输入模式。当中间的隐含层节点数小于输入层节点数时，就意味着中间隐含层能更有效地表现输入模式，并把这种表现传送到输出层。在这个过程中，输入层和中间层的变换可以看成是压缩编码的过程；而中间层和输出层的变换可

42、以看成是解码的过程。该算法可以直接用来进行数据压缩，实现起来比较简单，但是并不完善，存在学习收敛速度太慢、网络的学习记忆具有不稳定性等缺陷。3.6.1基于BP人工神经网络的图像压缩算法（1）传统的基于BP人工神经网络的图像压缩BP(Back一ProPagation)算法,即为误差反向传播算法,在网络内部有两种信息!流通:输入信号正向传播和误差信号反向传播两个过程,如图4.1所示"网络的拓扑结构包括输入层!隐层和输出层"从外界或者其他神经元来的信息进入输入层,经过输入层的运算输出传给中间隐层神经元;隐层神经元进行信息的处理,包括特征提取等,隐层可以有单层或者多层结构,根据信息

43、表示的需要和变化能力的需求进行设计;输出层接受最后一个隐层的输出作为输出层的输入,通过输出层的运算得到整个神经网络的输出,从而完成一次输入信号的正向传播"如果输出的结果与期望的结果,即与“教师”差别超出了能够容许的范围,或者网络的训练次数还没有达到设定的最大阂值,则进入误差的反向传播,从而逐层地按照误差梯度下降的方式调整各层的权值"权值的改变有两种方式,一种是对所有模式的梯度求和,即计算出权值误差,到训练结束是进行累加,然后调整权值,将变化量加到原有的权值上得到新的权值,这是属于一种批处理的方式;另一种方式是对每一个输入模式,调整一次网络的权值,如果模式结合的可能性比较大,

44、这种处理方式更为有利"在整个网络中,每一层神经元只能够影响其相邻层的神经元状态"通过不断地输入信自!正向传播和误差信息的后向传播,各层权值不断调整,直到输出结果和“教师”之间的误差减少到可以接受的程度"当训练次数超过设定的最大值时,网络的训练也会结束"。传统的基于BP的人工神经网络中,对于一幅MxN的图像,将其划分为大小为mxn的子块,每个子块的数据按照一定的排列规则形成一个向量"训练时,从这些向量中随机选取一个向量作为BP网络输入,并将此向量作为输出的”教师”假设隐层神经元数量为k,则要求k<mxn,隐层神经元的多少不仅影响压缩比,而且

45、影响重构图像的质量,通过实验大致上取为为合理"例如,对于一幅大小512*512像素,每个像素值在O一255的灰度图像,可将其划分为4x4的子模块,则整幅图像包含有128x128个子模块,每个子模块形成一个向量"由于神经网络输入值范围的特点,对所有向量输入进行归一化处理,使向量的每个元素取值都在0,l的范围内"将这些向量输入BP网络进行训练,直到满足要求的误差精度或者达到了最大的训练次数为止,此时形成了固定的网络权值"每个输入向量通过输入层到隐层的映射,形成对应的压缩数据"在解码端,通过隐层到输出层的网络映射,将压缩数据进行恢复"最后进

46、行反归一化处理,得到灰度取值在O到255之间的重构图像" 图：3层的BP神经网络3.7基于方向滤波的图像压缩算法为了解决小波变换方向缺失的问题，多尺度、多方向和各向异性的多尺度几何分析(Muti-scale geometric analysis, MGA)理论得到了快速的发展。MGA 的范畴非常广泛，其中有一类带有方向滤波器组(Directional filter banks, DFB)的图像方向滤波算法，可以较好地捕捉图像的方向信息，达到比小波变换更优的表示效果。Do 和 Vetterli 提出的contourlet 变换就是一种著名的方向滤波算法。Contourlet 变换通过引

47、入拉普拉斯塔式(Laplacian pyramid，LP)分解和方向滤波器组，可以最优地表示二维图像的方向信息。但是，contourlet 变换因为有 4/3 的冗余度而造成编码效率偏低，并不是图像编码的最佳选择。Eslami 和 Radha 在 contourlet 变换的基础上，用二维小波变换取代 LP 分解，提出了小波-contourlet 变换(Wavelet-based contourlet transform, WBCT)。WBCT 是一种无冗余变换，比 contourlet 更适合图像编码。随后，Eslami 和 Radha 又提出了混合小波-方向滤波器组 (Hybrid wav

48、elets and directional filter banks, HWD)变换，从而扩展了WBCT 的概念。HWD 通过定义了多种 DFB 形式，使方向滤波器组和小波变换的结合更加灵活。图像的这一类方向滤波算法提出后，受到了很多学者的关注和深入研究，期间出现了各种基于方向滤波的图像编码方案，而非冗余的 WBCT 和 HWD 无疑是这个分支上最优秀的两种算法。在 WBCT 域做图像编码，影响编码性能的因素有很多，如小波分解级数，方向分解级数等，都是需要讨论的问题。而在 HWD 域中，情况似乎更加复杂，除了上述几个问题，HWD 的分解结构也是至关重要的一个因素。另外，虽然基于 WBCT和 H

49、WD 域的图像编码方案可以较好地捕捉图像的方向信息，但是由于变换域系数的量化，也引入了不可避免的振铃效应。由于方向滤波器组本身的特性，这种振铃效应要比JPEG2000 编码方案中的振铃效应严重得多，在寻求较优的编码方案时，控制好振铃效应也是必须要考虑的重要问题。目前就这些问题讨论并提出解决方案的文献，相对较少。深入研究 WBCT 和 HWD 变换域的特性，寻求一种高效的图像编码方案，具有重要的意义。3.7.1 WBCT 域静止图像压缩算法(1)WBCT 的小波分解级数 NLA 实验可以很好地考察变换域的稀疏表达能力。其主要思想是在变换域保留绝对值最大的一部分系数，其他系数都舍弃(即置零)。用保

50、留的大系数来重构图像，分析重构图像的质量。下表为 barbara 图像在各个 WBCT 分解向量下的 NLA 实验结果，表中数据为重构图像和原图像的 PSNR 值。分析下表的实验结果，可以得出，小波变换的分解级数对 WBCT 的变换性能有着极大的影响。当分解级数 L 小于一定值时，在较低码率下的重构图像质量很差，这是因为 L 较小时，LL 子带系数过多。在低码率下保留的系数较少，那些被置为零的系数有相当一部分来自于 LL 子带，而 LL 子带携带的信息是图像中最重要的信息，此时解码图像质量就会急剧下降。在 L 大到一定的值后，WBCT 变换的性能得到了一定的保证。但是，方向分解级数的不同依然在

51、一定程度上影响着重构图像的质量。寻求较优的分解向量，从而使 WBCT 发挥其最优的变换性能，将是本文一个重要的研究要点。（2）WBCT 域编码的振铃效应1虽然在变换域系数量化后，各个频带都会有相应的频率干扰，但是低频子带量化引入的振铃效应要比高频子带严重得多。所以在 contourlet 变换中，Do 和 Vetterli 先对原图像进行了 LP 分解，实现了高频和低频的分离，再对高频部分作 DFB 分解，从而在一定程度上控制了振铃效应。Contourlet 的过采样方案虽然可以较好地解决频率干扰的问题，却也同时引入了过多的冗余信息。图3-1所示为barbara图像最高频带作L级DFB分解，N

52、LA实验中重构图像的PSNR随着 L 的变化而变化的折线图。其中，L=0 表示小波变换（不做任何方向分解）。图 3-2和图 3-3 分别为次高频带和第三高频带的相应 L 级 DFB 分解的 NLA 实验结果。图 3-1 和图 3-2 折线的升降变化，说明了在最高频和次高频做适当的 DFB 分解，可以提高解码图像质量。频率越低，折线峰值所对应的最佳方向分解级也越低。由图 3-3可见，在第三高频上作 DFB 分解，会导致高码率下的解码图像质量下降，而且分解级数越高，解码图像的 PSNR 越低。因此，在第三高频子带上，保持小波系数不分解是最佳的选择。对于更低的频率子带，更是如此。（3）振铃效应和方向

53、分解级数的关系在一个小波子带内，多级方向滤波等效于滤波器的卷积。方向分解级数 L 越大，等效滤波器就越长，捕捉方向信息的能力越强，所产生的振铃效应也越严重。反之，L 越小，捕捉方向信息的能力越弱，振铃效应也越轻微。从图 3-3(a)中不难发现，随着 DFB分解级数的增大，解码图像质量急剧下降，过于严重的振铃效应是出现这种现象的根本原因。图 3-4 所示的实验结果也可以验证这个论点。图 3-4 所示为 NLA 实验采用五级小波变换，保留 1/8 大系数，对次高频带作方向分解，方向分解级数为 L=1 和 3 时的解码图像(等效于 WBCT0 1 0 0 0和0 3 0 0 0分解)。比较图 3-4

54、(b)和图 3-4(c)可以发现，L=3 时的重构图像平滑区域出现了很多因振铃效应而导致的噪声，比 L=1 时的解码图像严重得多。（4）WBCT 域最优分解条件小波变换的分解级数是影响 WBCT 变换性能的最大因素。达到一定分解级的小波变换才是比较适合图像编码的。JPEG2000 标准程序中采用五级9-7 小波变换，不管是计算量还是编码性能都是较优的。在本文接下来的实验中，全部采用五级 9-7 小波变换。NLA 实验验证了 WBCT 变换性能和分解级数、小波频带之间的关系。在寻求 WBCT 分解向量的问题上，存在着一个最优解，使 DFB 分解既保持在捕捉方向信息上的优势，又能较好地控制解码图像

55、中的振铃效应。方向分解级数，并不是越高越好，也不是越低越好。而且其最佳的分解级数和所处的频率子带有关。一般而言，只适合对小波变换后的最高的两个频带作 DFB 分解，从第三频带开始就保留小波系数不分解。另外，频率越低的小波子带，所对应的最优方向分解级数也越低，比如选取 V=3 2 0 0 0或者2 1 0 0 0。这就是选取 WBCT 变换最优分解向量的限制条件。图 3-5 所示为五级小波变换域和 WBCT3 2 0 0 0变换域的 NLA 对比实验，可以看到，保留相同数目大系数的前提下，WBCT 域的重构图像拥有比小波变换重构图像更高的 PSNR 值。这是因为基于 DFB 的 WBCT 变换更好地编码了图像的方向信息，其对图像内容的表达比小波变换更稀疏。（5）子带方向和子带频率的关系在 WBCT 中，DFB 对小波变换后的 HL，LH 和 HH 子带作方向分解，虽然这三个子带都是图像的高频子带，但是 HL 只是水平方向上的高频，LH 只是垂直方向