2同济大学电气工程系,上海200331)摘要:在对基本的DCT域分形图像压缩方法进行分析基础上，提出了一种改进方案，即基于自适应分类加权最小二乘法的DCT域分形图像压缩方法，并使用基本方法和改进方法对标准灰度图像分别进行了测试。测试结果表明，本文提出的方法可以在PSNR下降很小的情况下大大提高编码速度。
关键词:自适应;加权最小二乘法;二维离散余弦变换;分形图像压缩1引言
分形图像压缩［1］［2］是一种新的图像压缩方法，它的基本思想是利用图像的相似性，把整个或局部图像映射到图像的一部分，并使用拼接定理完成整个图像的压缩。
一般的分形图像压缩方法［2］是在图像进行分形压缩时，首先在空间域内把图像分为不同大小的图像块：R块（称为子块）和D块（称为父块），其中R块较小，且各个R块之间不重叠，而D块比R块大，各个D块之间可以有重叠；然后对每一个R块，找到一个D块，使得这个D块经过平均压缩，反射旋转变换后与当前的R块相匹配，匹配表达式为
FR≈CK，L·LP(K，L)·Av·FD hK，L·I(1)
式中：CK,L为伸缩因子；LP(K,L)为反射旋转因子；Av为平均抽样因子；hK,L为平移因子；I是与R块规模相同的全1矩阵，下标中的K和L为子块的左上角位置。上述的分形压缩方法具有明显的优点：每个R块只需要CK,L、LP(K,L)、hK,L和D块的位置等4个数据，所以可以达到较大的压缩比，非常适合有限带宽的应用场合。但是，分形图像压缩的时间非常长，原因有两个：对每个R块，需要和所有的D块进行匹配检测；对每一个D块，还要进行8种反射旋转变换，这大大限制了分形图像压缩方法的应用。许多文献提出了改进方案以减少压缩时间，如与其它方法结合的分形编码方法［3］、D块预搜索进行分类的技术［4］、减少反射旋转变换的数目［5］、不需要搜索的BFT变换［6］［7］［8］、可变块形状和大小技术［9］等。
另一方面，一幅自然图像的能量主要分布在低频部分。由数字信号处理的有关理论可知，2-D离散余弦变换（DCT）能有效地去除像素之间的空间相关性，经2-DDCT变换后低频数据大，高频数据小，即矩阵的左上角数据（低频数据）较大，右下角的数据（高频数据）较小。从分形的观点看，每个自然图像经过2-DDCT后，都具有明显的相似性，这正好符合分形图像压缩的基本思想，从而出现了DCT域分形图像压缩方法。它是在DCT域进行的，压缩的对象是经过DCT变换的图像数据。本文首先介绍一般的DCT域分形图像压缩，然后对它的优、缺点进行分析，给出一种改进方法，并通过标准图像进行测试。测试结果证明，本文提出的改进方法可以在恢复图像质量下降很小的情况下，大大加快压缩速度。
2基本的DCT域分形图像压缩方法
基本的DCT域分形图像压缩方法和空间域分形图像压缩方法类似。设原始图像G为m×n，且m、n都是16的整数倍。把G分为两种类型的块，一种为8×8的子块R，另一种是16×16的父块D，它们分别进行2-DDCT变换，用FR和FD表示。而FR根据其交流数据可以分为两类即简单子块和复杂子块。假设Tω为给定的阈值，则有
FR(0,0)为直流成分，FR(0,1)、FR(1,0)、FR(1,1)是频率比较低的交流成分。前面已经提及，一般的DCT变换块中，低频成分的幅度较大，高频成分的幅度较小，因此，低频交流成分幅度小的子块几乎是一个平坦块，此时只要保留FR(0,0)，就保留了其主要信息量。对于复杂子块，可采用分形变换
式(3)中CK,L、LP(K,L)、h(K,L)、I、K和L的意义与式（1）中相同，A为抽样因子，表示取FD的左上角的8×8子块（即较低频率的8×8系数阵）。设τ(FD(k,l))表示式（3）中右边的变换，则仿射变换的误差为
如果误差E(k,l)仍比较大，则可继续对误差块E(k,l)进行编码得到补偿项，得到其误差值的无失真编码，以保证在分形解码时，恢复DCT系数的误差在设定范围内；如果E(k,l)比较小，则当前子块的分形编码已达到恢复DCT系数的目的。
在解码时，用得到的分形系数进行任意初始图像的分形迭代。由于父块和子块都是在DCT变换后的数据中进行，所以每迭代一次都要用2D反离散余弦变换（IDCT）回到原始图像。
上述DCT域分形压缩方法具有以下优点：DCT域中的R块和D块较空间域中的R块和D块更容易找到相似性，因此，也可以不用对父块进行反射旋转；DCT有快速算法，运算速度比较快；加入了对过大的E(k,l)编码得到的补偿项，对恢复图像的质量有改善作用。但同时也存在以下问题：在R块和D块的匹配中，虽然省掉了部分R块的匹配检测，但对每一个要进行匹配检测的R块，仍需对所有D块进行检测，这仍然限制了压缩速度。对此，本文提出以下能明显提高压缩速度的改进方案。
3基于自适应分类加权最小二乘的DCT域分形图像压缩方法
在叙述改进方法之前，先对进行2-DDCT前后的图像数据的关系进行分析。
假设有一图像块F，不妨设F为N×N的正方形块，对于一般矩形块结论是一样的。设F的灰度函数为f(i,j)，i,j=0,1,…,N-1。对F做2-DDCT，得到G块，其值为g(i,j)，i,j=0,1,…,N-1。由于DCT只是对图像能量分布进行了改变，而不改变总的能量，因此，可以证明下列关系：对G进行从左上角到右下角的“之”字形扫描，形成一个长度为N2的从低频数据到高频数据的序列，将G中与序列的后N2-m个高频数据对应的数据置0得到矩阵G′，则对G′做2-DIDCT后得到的恢复图像与原始图像的MSE（meansquareerror）与被置0的高频数据有关，即若被置0的高频数据为h(n)，其中n=0,1,…,(N2-m-1)，G′做2-DDCT之后得到恢复图像的灰度函数为f′(i,j)，则恢复图像的MSE为
式（6）表明恢复图像的MSE值就是被置0的DCT数据的平方累加和。这也从另一个角度说明，如果给定一个MSE，我们可以有选择地忽略某些DCT数据，而使恢复图像满足一定的要求。从人的视觉特性看，常用的误差指标是PSNR。PSNR和MSE的关系如
一般来说，当恢复图像的PSNR超过30db时，主观感觉不易找到其差异。设PSNR=30db时对应的MSE值为LMSE，则当被置0的高频数据的平方和小于LMSE时，可以达到主观的满意。
在图像的匹配检测中，一般采用最小二乘法搜索和R块匹配度最高的D块，即对某一个R块，找到一个D块，使得式（4）的值最小。由于DCT域数据对恢复图像的主观视觉和PSNR的影响不均衡，所以为了获得更好的恢复质量，应该对各个数据误差引起的总体误差进行不同的处理。根据加权最小二乘法的定义，可以将低频成分的数据误差乘上较大的权值，而将对恢复质量影响不大的高频成分的数据误差乘上较小的权值，从而达到分别处理的目的。但不同图像各个数据的重要性是不同的，这就产生了一个问题，如何确定各个数据对恢复图像的影响程度?为了解决这个问题，把加权最小二乘法和前面论述的2-DDCT前后图像数据的关系相结合，同时考虑编码速度因素，对R块和D块进行分类，得到自适应分类加权最小二乘法的DCT域分形图像压缩法。下面是该方法的基本实现过程。
1)将原始图像分为8×8的不重叠R块和16×16的半重叠的D块，分别进行2-DDCT，得到R块库和D块库；
2)分别对R块库和D块库进行分类，分为9类，分别对应去掉左上角k（k=1，3，6，10，15，21，28，36）个低频数据后剩下的高频数据的平方和小于LMSE的情形。这9类分别表示只保留左上角k个数据就可以较好地恢复图像。分类时依次进行，即只有当一个块不属于第一类时，才检查是否属于第二类，依此类推；
3)对属于同一类的R块和D块使用加权最小二乘法进行匹配检测。由于左上角的低频数据对恢复图像的重要性要大于其余的高频数据，所以对9个不同的类，使左上角k个数据对应的权系数较大，k的取值与2相同。每一个R块，找到匹配度最好的D块，记下各个仿射变换系数，如果仍不能达到要求，可以对误差函数进行编码以在解码时进行补偿。
在上述方法中，2)和3)中之所以采用1，3，6，10，15，21，28，36这9个数字，是因为在2-DDCT域数据中，每个数据都同时反映了原始行[1][2]下一页
