改进转动惯量特征的快速分形图像编码算法

李高平，杨军，陈毅红

西南民族大学计算机科学与技术学院，成都 610041

改进转动惯量特征的快速分形图像编码算法

李高平，杨军，陈毅红

西南民族大学计算机科学与技术学院，成都 610041

1 引言

1990年Jacquin首次提出基于图像中的局部自相似来消除冗余信息的分块迭代函数系统（PIFS）编码算法[1]，用压缩仿射变换的量化参数来表达图像，具有压缩比大、解码快、分辨率无关等特性。但是这种方法因其编码过程需要全搜索而耗费大量时间[2]，限制了它在图像压缩领域的运用。

多年来，研究者们针对编码过程耗时问题已提出最有创新和前途的特征向量法来加快编码过程。但该方法存在高维特征向量需要增加额外存储，且维数越高、性能越差的问题[3-5]。近几年也提出许多降维的替代特征方法[6-10]，这些方法多从图像子块的统计数字特征考虑，没有考虑图像子块上各像素点灰度值的空间分布情况，据此定义的图像子块特征不能全面反映其所含信息。文献[11]借用力学中的“转动惯量”概念来刻画图像子块的特征，定义了综合考虑图像子块上各像素点灰度值大小和空间分布状况的转动惯量，提出一种基于转动惯量的快速算法，该算法的不足之处在于，它依据的假设（即两个等尺寸的子块只有转动惯量值接近时才有可能组成匹配对）仅仅是建立在统计意义而非确定意义上。本文继续研究这个算法，改进了文献[11]中图像子块的转动惯量定义，重新定义了转动惯量特征，并从理论上证明了它与匹配误差间的关系不等式。根据这个不等式，在编码阶段，一个range块的最佳匹配domain块只在与其转动惯量特征值相接近的domain块里面寻找，终止条件由预先设置的误差阈值来控制。在本文提出的快速算法中，也融入了文献[7]中提出的两个措施：一是通过排除码书Ω中的小标准差domain块以缩减码书容量；二是采用非搜索的方式对小方差range块编码。三幅测试图像的仿真实验表明，本文提出的改进转动惯量特征算法是在不降低解码图像质量的情况下，实现加快编码26倍左右，这改进了原转动惯量算法[11]的结果（在PSNR下降约1.7 dB的前提下，加快编码19倍左右）。同时，本文算法也优于全搜索分形编码算法和三均值特征分形编码算法[10]（简称三均值特征算法）。

2 全搜索分形编码算法和三均值特征算法

便于表述，将n×n大小图像子块上各像素点的灰度值向量化为线性空间RN(N=n×n)中的向量。R=(r1,…,rk,…,rN)、D=(d1,…,dk,…,dN)分别表示range块（简称R块）、domain块（简称D块）像素点灰度值向量化的向量，用表示X∈RN的均值，用＜·, ·＞、||·||分别表示向量内积和2-范数，用(RN,E)代表N=n×n灰度图像空间（R是实数集，E为均方根失真度量函数）。

2.1 全搜索分形编码算法

在分形编码中，图像首先被分割成互不重叠大小为n×n的R块和允许重叠大小为2n×2n的D块。然后，将每个D块通过4-邻域像素值平均来收缩为n×n的子块与R块大小匹配，所有收缩后的D块经过8个等距变换的全体D块就构成码书Ω。

编码阶段，对每一个R块，按照全搜索方式在码书Ω中寻找其最佳匹配D块和自仿射变换w，使得w(D)与R的均方误差达到最小。为了寻求R块的最佳匹配块，需要求解下面的极小化问题：

其中，m表示R块的最佳匹配块序号，I∈Rn×n是所有元素均为1的常值块。

显然，直接求解问题式（1）是十分困难的，为了减少计算复杂性，常采用的实用方法是解内层约束极小化时先忽略式（1）中约束|s|＜1，后对不满足约束的对比度因子作截断处理来补偿。因此，问题式（1）的内层约束极小化转化为下述问题来求解：

把问题式（1）的求解转化为式（2）和式（5）这种次优解法后，得到的R块分形码为四元组(m,sˆi,oˆi,t)。其中sˆi,oˆi是si,oi的量化值，t是等距变换序号。原始图像的分形码由全体R块的分形码组成，它描述了一个使图像近似不变的压缩变换。

解码用分形码描述的压缩变换迭代作用于任何初始图像来生成。

2.2 三均值特征算法

在定义图像子块特征时，通过对图像子块去均值后，再进行单位化来消除对比度因子的影响[8]。于是，可将图像子块的规范子块定义如下：

编码阶段，一个待编码R块的最佳匹配块搜索范围仅在初始匹配块（与R块的三均值特征值相近的D块）的邻域内，搜索邻域的大小由预先设置的误差阈值来确定，它有效降低了算法的复杂度。

3 改进转动惯量特征的快速编码算法

3.1 理论基础

全搜索分形编码算法的编码过程所耗费时间，主要取决于码书Ω容量的大小。为了减少编码过程时间，必须采取一定的措施来缩减搜索空间。下面通过定义图像子块的特征，将匹配搜索由全局搜索转变为邻域搜索。

借用力学中的“转动惯量”概念，文献[11]在定义图像子块的转动惯量时，选用图像子块的重心作为转动中心，各图像子块的转动中心位置会因其上各像素点灰度值分布不同而变化。此外，将|xˆi,j|视为“质量”，没有考虑图像子块上像素点灰度值规范化出现的正负对转动惯量的不同影响。

这样定义的图像子块的转动惯量特征，其转动中心固定，且考虑了各像素点灰度值规范化出现的正负对转动惯量的不同影响。下面的定理给出了匹配误差与改进转动惯量特征间的关系，它是本文算法的理论基础。

定理若图像子块大小为n×n，其上的像素点灰度值向量化为R,D∈Rn×n，则有下面的不等式：

定理证毕。

3.2 快速编码算法方案

编码过程耗时的多少与待编码的R块数量、码书Ω的容量大小和搜索方式紧密相关。

首先，确定待编码的R块数量。由式（4）可得，E(R,D)≤nσR，它表明σR足够小的R块，任意D∈RN都可以作为其匹配块，这些R块不需要搜索编码，直接赋予分形码。设置分类阈值τ＞0，若R块的σR≤τ，就认为此类R块为非搜索编码块（简称平滑块），否则就认为是搜索编码块（简称非平滑块），因此，待编码R块数量就是非平滑R块的数量。

其次，确定缩减码书Ω的容量。由匹配误差式（4）可推出，，因此，可以预先排除码书Ω中的小标准差D块。设定阈值η＞τ，将原码书Ω缩减为容许码书Ωη，即

最后，确定待编码的R块(σR＞τ)在容许码书Ωη的搜索方式。由本文证明的式（9）可知，与待编码R块匹配D块的匹配误差为：

这说明：如果D和R改进转动惯量特征值相差较大，那么匹配误差E(R,D)也较大，从而D不能匹配R；反之，如果D匹配R，即E(R,D)最小，那么由式（12）可知S(D)应该与S(R)非常接近。它表明R的最佳匹配D在改进转动惯量特征意义下一定是与R最接近Dinit∈Ωη（Dinit称为初始匹配块）的近邻。所以，在设计搜索方式时，首先将容许码书中的D块按其改进转动惯量特征值S(D)的大小进行升序排列，即满足S(Di)≤S(Di+1)，并使用二分法在升序容许码本Ωη中搜索与S(R)相差最小的初始匹配块Dinit={D∈Ωη|min|S(R)-S(D)|}，然后，搜索过程在Dinit的左右方向进行，直至满足预先条件E(R,D)≤δ（δ为误差阈值）为止。储存搜索过程中匹配误差E(R,D)≤δ对应的D块的序号m、量化参数,、等距变换序号t，即得出搜索编码R块的分形码为(m,,,t)。

4 仿真实验结果

仿真实验的测试图像为Lena、Peppers和Boat（512× 512，8 bit量化），计算在运行Windows XP的AMD Athlon（3.01 GHz CPU/2 GB内存）PC上进行，程序用C++编写。

4.1 改进转动惯量特征的有效性验证

本文通过重新定义的图像子块的转动惯量特征，把待编码R块的匹配搜索空间由全局搜索变为局部搜索，在初始匹配块（与R块的改进转动惯量特征值相近的D块）的邻域内搜索。问题是全搜索找到的最佳匹配块（即全局匹配块）在赋序码书中与其初始匹配块的远近是不同的，若邻域半径取得小，那么局部搜索范围内找到的局部匹配块就有可能不是全局匹配块，会导致全局匹配块被局部匹配块取代，使解码图像质量降低。下面通过仿真实验测出全局匹配块落在初始匹配块邻域U(Dinit,k)内的情况。

测试图像采用方块分割方案，R块、D块大小分别取为4×4、8×8，生成码书的步长取为8，此时，待编码R块的数量为16 384。在改进转动惯量特征意义下，三幅测试图像的编码R块的全局匹配块落入邻域U(Dinit,k)内的数量列于表1，表中标识“M-N”表示k的取值区间为(|Ω|×M%,|Ω|×N%]，其中|Ω|为码本容量。

表1 全局匹配块落入邻域U(Dinit,k)内的R块数量（改进转动惯量特征）

从表1可以看出，当邻域半径k≤|Ω|×10%时，三幅测试图像的编码R块的全局匹配块落在邻域内的比例分别为35.6%、33.5%、37.2%；当邻域半径k≤|Ω|×30%时，三幅测试图像的编码R块的全局匹配块落在邻域内的比例分别为73.5%、70.4%、75.7%；当邻域半径k≤|Ω|×50%时，三幅测试图像的编码R块的全局匹配块落在邻域内的比例分别为89.3%、87.8%、91.7%；只有极少数的R块的全局匹配块，几乎需要全搜索才能找到，其比例分别为0.7%、0.8%、0.3%。这些数据充分表明，绝大多数的待编码R块的全局匹配块就在其初始匹配块附近，不需要进行全搜索就能找到，验证了邻域搜索是可行的。

在原转动惯量特征[11]、三均值特征[10]意义下，用同样方法得到三幅测试图像编码R块的全局匹配块落入邻域U(Dinit,k)内的数量列于表2。

将表2与表1中的数据进行对比不难发现，在邻域半径k相同的情况下，三幅测试图像的编码R块的全局匹配块落在邻域内的数量比较结果为：改进转动惯量特征最多，其次是三均值特征，最后才是原转动惯量特征。表明改进转动惯量特征比三均值特征和原转动惯量特征更能准确全面刻画图像子块的信息。

4.2 改进转动惯量特征快速算法的有效性验证

在上面设计的改进转动惯量特征快速编码方案中，首先应选取R块的分类阈值τ和容许码书阈值η，根据文献[7]的研究结果，可取τ=4，η=20。其次，通过实验确定误差阈值δ，显然，编码过程时间会随着δ增大而减少，其解码图像质量也会相应地降低。

表2 全局匹配块落入邻域U(Dinit,k)内的R块数量（转动惯量特征[11]、三均值特征[10]）1）

图1显示的是三幅图像的解码图像质量（以PSNR度量）在不同误差阈值δ下的变化情况。当δ≤10时，解码图像质量下降比较缓慢，当δ＞10时，解码图像质量下降比较快，综合考虑编码时间和解码图像质量两个因素，取δ=10比较合适。

图1 解码图像质量随误差阈值变化情况

为了验证本文提出的快速算法的有效性，选编码时间（s）和峰值信噪比PSNR（dB）为测试性能参数。本文算法(τ=4,η=20,δ=10)与全搜索算法的对比实验结果列于表3。为比较结果公正，原转动惯量算法[11]也融入了文献[7]中提出的两个措施，它和本文的对比结果见图2。

表3 本文算法与全搜索分形算法对比结果

从表3可知，对选用的三幅标准测试图像，本文提出的算法与全搜索算法相比，从平均意义角度看，在基本保持解码图像质量不降低的情况下，编码速度加快达26倍左右。

图2 本文算法与转动惯量算法的编码性能对比

5 结论

从综合考虑图像子块上各像素点灰度值及其空间分布的角度，本文借用力学中的“转动惯量”概念，重新定义了图像子块的转动惯量特征，并从理论上证明了它与均方根误差间的关系不等式，以此为基础，把耗时的R块与码书D块的匹配搜索问题转化为转动惯量特征意义下初始匹配块Dinit的邻域搜索问题，有效降低了算法的复杂度。通过对三幅测试图像进行仿真实验，验证了绝大多数的待编码R块，在其初始匹配块邻域内搜索得到的局部匹配块就是全局匹配块，表明了邻域搜索是可行的。与转动惯量特征和三均值特征相比，改进转动惯量特征更能准确全面刻画图像子块的信息。本文基于图像子块的改进转动惯量特征提出的快速分形编码算法，在解码图像质量基本相同的情况下，平均加快编码过程的速度26倍左右。该快速算法不仅有理论基础，而且也得到了仿真实验的验证，为加快分形图像编码过程提供了一个有效的方法。

[1]Jacquin A E.Image coding based on a fractal theory of iterated contractive image transformations[J].IEEE Transactions on Image Processing，1992，1（1）：18-30.

[2]Fisher Y.Fractal image compression：theory and application[M]. New York：Springer-Verlag，1995.

[3]Saupe D.Accelerating fractal image compression by multi-dimensional nearest neighbour search[C]//Proc Data Compression Conf，1995：222-231.

[4]Wohlberg B，De Jager G.A review of the fractal image coding literature[J].IEEE Trans on Image Process，1999，12：1716-1729.

[5]Selvi S S，Makur A.Variable dimension range and domain block-based fractal image coding[J].IEEE Transactions on Circuits and Systems for Video Technology，2003，4：343-347.

[6]He C，Yang S X，Xu X.Fast fractal image compression based on one-norm of normalised block[J].Electron Lett，2004，40（17）：1052-1053.

[7]何传江，黄席樾.基于图像块叉迹的快速分形图像编码算法[J].计算机学报，2005，28（10）：1753-1759.

[8]何传江，申小娜.改进分形图像编码的叉迹算法[J].计算机学报，2007，30（12）：2156-2163.

[9]李高平，向慧芬，赵正武.四分位数特征的快速分形图像编码算法[J].计算机工程与应用，2011，47（22）：145-148.

[10]李高平.三均值特征的快速分形图像编码算法[J].中国图象图形学报，2011，16（1）：1-7.

[11]孙后山，刘晓东，党晶涛，等.基于转动惯量的快速分形图像编码算法[J].微电子学与计算机，2009，26（5）：92-95.

LI Gaoping,YANG Jun,CHEN Yihong

College of Computer Science&Technology,Southwest University for Nationalities,Chengdu 610041,China

Fractal image encoding with full search typically requires a very long runtime,which is essentially spent on searching for the best-matched block to an input range block in a large domain pool.This paper thus proposes an effective method to improve the drawback,which is mainly based on certified inequality linking the root-mean-square and Improved Moment of Inertia（IMI）feature of normalized block.During the search process,the IMI feature is utilized to confine efficiently the search space to the vicinity of the domain block having the closest IMI feature to the input range block being encoded,aiming at reducing the searching scope of similarity matching to accelerate the encoding process.Besides,a beforehand error threshold is used to determine the size of search neighbourhood.Simulation results of three standard test images show that the proposed scheme not only reduces the searching scope of best-matched to averagely obtain the speedup of 26 times or so by error threshold set 10,but also can obtain the same quality of the decoded images as the baseline algorithm with full search.Moreover,it is better than the moment of inertia algorithm and the three-mean feature algorithm.

image compression;fractal;fractal image coding;improved moment of inertia feature

全搜索分形图像编码过程特别耗时的原因在于，每个range块都需要在一个很大的domain块池里寻找最佳匹配domain块。为了改进这个缺点，重新定义了图像规范块的转动惯量特征，证明了它与匹配均方根误差间的关系不等式，据此提出了一个限制搜索范围来加快编码过程的算法：一个待编码range块的最佳匹配块搜索范围仅在与它的转动惯量特征值相近的domain块的邻域内搜索，邻域半径的大小由预先设置的误差阈值来确定。三幅图像的仿真结果表明，它确实能够在不降低解码图像质量的情况下，通过减少搜索范围达到了平均加快全搜索分形编码算法的编码速度26倍左右（误差阈值为10），且也优于转动惯量算法和三均值特征算法。

图像压缩；分形；分形图像编码；改进转动惯量特征

A

TN919.81

10.3778/j.issn.1002-8331.1306-0259

LI Gaoping,YANG Jun,CHEN Yihong.Fast fractal image encoding algorithm based on improved moment of inertia feature. Computer Engineering and Applications,2013,49（24）：144-148.

国家民族事物委员会科研项目（No.12XN05）；西南民族大学自然科学项目（No.2012NYT001）。

李高平（1966—），男，教授，研究方向为分形理论及其在图像处理中的应用；杨军（1963—），男，博士，教授，研究方向为信息安全、应用密码学和组密钥管理；陈毅红（1972—），男，博士，实验师，研究方向为嵌入式系统研究、物联网、RFID。

2013-06-24

2013-08-09

1002-8331（2013）24-0144-05

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.006.html