基于遗传算法的匹配跟踪图像分解

基于遗传算法的匹配跟踪图像分解

刘德伟，司菁菁

北京邮电大学，北京 (100876)

E-mail ：bupt_ldw@sohu.com

摘 要：基于遗传算法提出了一种新的匹配跟踪图像分解策略。该算法通过对生成函数进行不同的二维几何变换，构造各向异性的原子，能够有效地捕捉图像中的不同特征。同时，本算法将遗传算法结合到了匹配跟踪的过程中，从构造的冗余原子字典中快速地选择出与图像当前特征最匹配的原子。实验结果表明，本算法明显降低了原子搜索的运算量，并且支持感兴趣区域优先搜索。另外，本文最后还提出了一种在低维空间实现高维空间匹配跟踪分解的思路。

关键词：图像分解 匹配跟踪 遗传算法

中图分类号：TP391

1．引言

Mallat 等提出的匹配跟踪算法(Matching Pursuit ，MP)是一种有效的图像分解方法，它与离散余弦变换和小波变换的区别主要在于其从一个冗余的波形原子字典中选择与图像信号特征最匹配的波形原子，利用这些波形函数的线性组合来逼近原始图像[1]。因此，匹配跟踪包含着一个迭代的过程，在对图像进行分解时，每次迭代均需要在图像中的各个象素位置处计算字典中所有原子与图像的内积，然后选择内积值最大的一个原子作为此次搜索的结果，所需的计算量相当大。同时，原子字典的选择直接关系着能否用尽可能少的原子来表示图像中的关键特征，因此直接影响着匹配跟踪图像分解的效率与效果。

本文通过对生成函数进行不同的二维几何变换，构造各向异性的原子，能够有效地表示图像中的不同特征。同时，本算法将遗传算法结合到了匹配跟踪的过程中，从构造的冗余原子字典中快速地选择出与图像当前特征最匹配的原子。实验结果表明，本算法具有较高的稀疏分解特性，并且由于遗传算法的引入，明显降低了原子搜索的运算量，缩短了运算时间。另外，本文在最后还提出了一种在低维空间实现高维空间匹配跟踪分解的思路。

2．匹配跟踪图像分解

匹配跟踪图像编码将原始图像表示成时频原子字典中若干个最匹配时频原子的线性叠加，可以最佳地显示图像中所包含的各种结构特征。其中时频原子函数g (t )必须满足以下四个条件：

1：g (t )是连续可微实函数；

2：21()O(

)1g t t ∈+ 3：||g (t )||=1;

4：()0g t dt +∞−∞≠∫

还可以对其进行以下尺度变换，平移以及角度旋转等，以产生其他原子[2]。

平移b T r 定义为： ()()b

T g x g x b =−r r r r (1) 角度旋转R θ定义为： ()(())R g x g r x θθ=r r (2)

12cos()sin()()sin()cos()x r x x θθθθθ−⎛⎞⎛⎞=⎜⎟⎜⎟⎝⎠⎝⎠

r (3)

尺度变换a S r 定义为： 1212()(,)a

x x S g x g a a =r r (4) 匹配跟踪算法将信号分解为一系列时频原子的和，能最大限度地反映信号的内在特征。但该算法的计算量十分巨大，每一步都要完成图像或误差图像在冗余字典中的每一个原子上的投影计算。数次迭代后计算量更是惊人，这严重阻碍了匹配跟踪算法的应用。对此问题，本文在以后章节将利用遗传算法对其进行解决。

3．遗传算法

在进行遗传算法时，首先要进行一个基本的数据转换操作，即从表现型到基因型的变换，这个过程称为编码。其中表现型实质上是搜索空间的参数或得到的解。把待寻优的参数表示成用一个二进制码串来表示的染色体，染色体中的二进制码称为基因，而这些具有遗传特性的基因串，称为基因型。相应地在遗传算法的最后还应该把基因型转换成表现型，这个过程称为译码。

编码后要根据优化的目标函数来计算每一个基因型的适应度，由适应度来决定该基因型的生存与复制能力。适应度越大的染色体，复制到下一代种群数就越多。然后需要在下一代染色体种群中来进行基因型之间的交换，并随机地在某个基因型的某个位置上进行代码的变异。最后在进行下一代染色体种群适应度的计算，并判断其是否收敛于最优解，若收敛则停止计算并输出。若不收敛则继续进行复制，交换和变异的迭代计算，直到得到最优解为止[3]。

4．基于遗传算法的匹配跟踪图像分解

4.1 原子字典的构造 本文采用的两个原子是：

2212()2

1121(,)2)x x g x x x e −+=− (5) 2212()

212(,)x x g x x −+= (6) 其中第一个原子为AR 原子，用它来捕捉具有高频特性，包含丰富边缘和纹理的图像效果比较好。而第二个原子为高斯原子, 用它来捕捉具有低频特性，平滑的图像效果比较好，图1﹑图2表示了这两个原子的特性[4]。

图1 AR 原子示意图 图2 高斯原子示意图 对这两个原子进行平移，尺度变换以及旋转后，就可以得到不同的原子。相应的给定这些参数的范围，就会得到一个原子字典。

4.2 遗传算法实现匹配跟踪算法

第一步，对遗传算法进行初始化，每组参数都分别含有尺度变换参数a 1﹑a 2,旋转参数angle,以及位移参数b 1﹑b 2。

第二步，将上述参数转换为实际参数，以便求出相应的原子。

第三步，对(5)，(6)两个原子分别根据上面得到的参数进行相应的变换，得到两个归一化后的原子g 1﹑g 2。

第四步，将g 1﹑g 2分别与图像块计算内积值，取这两个中绝对值最大的内积值作为该

个体的适应度f i 。

第五步，选择出该次循环最大的适应度值f max ，将它与上次循环最大的适应度值q max 作比较，如果f max >q max ，则把对应于f max 的那组参数保存为当前最匹配原子。若max max max

0.005,f q f −<则认为已经找到了该块最匹配的原子，并结束这次的搜索。 第六步，对这多组参数进行选择，复制。因为各个适应度值都比较大，它们之间的差相对于本身的值要小的多，所以有必要先对适应度值进行定标。定标后对得到的新的适应度值再用期望值法进行选择复制。

第七步，对复制后得到的新种群进行交换操作，为了避免局部搜索，交换的个体之间应相隔较远。交换的位置选择也比较关键，要使得各个组参数的交换突出不同的参数变化，这样对快速地找到全局最优解比较有利。

第八步，对交换后的新种群进行变异操作。有时搜索会陷入局部搜索状态，这时候对某个体进行变异，使其跳出局部搜索是非常必要的，但变异的概率也不能过高，否则就会使遗传算法的优点得不到发挥。

第九步，将变异后所得到的种群做为下一次搜索的初始种群，并跳到第二步继续搜索，直到搜索三十次为止，三十次后当前最匹配原子中的参数即为匹配原子的参数。

第十步，将上述九步执行完后，就找到了该图像块的匹配原子。然后就可以将该原子还原为图像，将原图像与该还原的图像做差，得到的误差图像作为下一次所要搜索的图像，继续进行上述九步，直到误差图像达到标准为止。

4.3 在低维空间实现高维空间的匹配跟踪算法

用遗传算法虽然大幅减少了搜索匹配原子时需要进行内积运算的次数，但一次内积本身的计算量并没有减少，当搜索的原子比较大时的计算量还是很大。为了进一步提高运算速度，本文给出一种在低维空间实现高维空间的匹配跟踪算法。

以128×128的Barbara 图像为例，如果对图像进行隔点采样，则采样后就会得到一幅×的小图像，这时再对这幅小图像应用遗传算法来搜索大小为×的匹配原子，然后再将这些原子作为高维空间的匹配原子，并用其恢复出128×128的图像。这样做将搜索原子的计算量降低了四倍，但它是以降低图像的恢复质量为代价的。因为从低维空间搜索到的最匹配原子从严格意义上说并不是完全对应于高维空间的最匹配原子，而是对应于以高维空间的最匹配原子为中心的某个领域上的原子。

为了纠正以上出现的误差，可以并不把低维空间搜索到的匹配原子直接作为高维空间的匹配原子，而是把它作为高维空间中存在匹配原子的一个中心邻域的中心。在这个邻域再进行二次搜索，搜索到的原子再作为匹配原子。这样做将很大程度上提高图像的恢复质量，但由此也将增加额外的计算量。

5．实验及结果分析

实际上如果采用传统的全局搜索算法来实现匹配跟踪图像分解算法，计算量将特别大，所花费的时间将超出人们的忍受程度。本文采用遗传算法来实现匹配跟踪分解算法对这个问题进行了很好的解决，表1给出了匹配跟踪分解算法的每一步中利用全搜索算法和遗传算法所需的乘法计算量。其中遗传算法中种群的个数为20，叠代次数选为30。采用16×16大小的原子时原子字典的大小为8×8×8×8×8×2=65536，采用128×12小的原子时原子字典的大小为32×32×8×××2=671088。每次内积需要的乘法计算量与原子大小相同。 由表可知采用遗传算法为匹配跟踪分解算法的实用化提供了可能，尤其在搜索与图像大小相同的大原子时，计算量的下降程度更是喜人。同时可以看到使用在低维空间实现高维空间的匹配跟踪分解算法可以使计算量又降低四倍，进一步加快了运算速度。

表1 匹配跟踪图像分解算法每一步中不同方法的计算量 算法 需要的乘法运算次数 与原算法计算量的百分比

16×16大小的原子全局搜索算法65536×16×16=16777216100% 遗传算法 1200×16×16=307200 1.8311%

采用在低维空间实现高维空间的

匹配跟踪分解算法的遗传算法

1200×8×8=768000.4578%

128×12小的原子全局搜索算

法671088×128×128=

1099511627776

100%

遗传算法1200×128×128=196608000.0018%

采用在低维空间实现高维空间的

匹配跟踪分解算法的遗传算法

1200××=49152000.0004%

6．总结

本文引入了遗传算法来实现匹配跟踪分解算法，实验结果表明，采用该方法比传统的匹配跟踪图像分解算法在计算量上大大地减少了。同时为了进一步降低计算量，本文还提出了一种在低维空间实现高维空间的匹配跟踪分解算法的方法，该方法通过对原始图像进行隔点采样，然后对采样后得到的小图像进行搜索匹配原子，将所得的原子作为原始图像的匹配原子来恢复图像。采用这种方法可以在图像恢复质量下降的允许范围内，将搜索原子的计算量又降低了四倍。

参考文献

[1] S. Mallat, Z. Zhang. Matching Pursuits with Time-frequency Dictionaries[J]. IEEE Transaction on Signal Processing, 1993, 41(2):3397~3415

[2] 廖斌．基于匹配跟踪的低速率视频编码．(博士学位论文)．北京:中国科学院软件研究所,2003．

[3] A Said, W A Pwarlman. A new fast and efficient image codeC based on set partitioning in hierarchical trees. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(3):243~250

[4] P.Frossard, P. Vandergheynst, R. M. Figueras et al. High flexibility scalable image coding. SPIE, 2003, (5150):

Image Decomposition Method Matching Pursuit Based On

Genetic Algorithm

Liu Dewei，Si Jingjing

School of Telecommunication Engineering, Beijing University of Posts and Telecommunications,

Beijing, PRC, (100876)

Abstract

This paper raises a new method of image separating strategy basing on the genetic algorithm. Through geological transformation of two dimensions, this algorithm constructs atoms of different orientation and thus can capture the different features of the images.Also, this algorithm is applied in the process of the matching,and select the most matching atoms from the redundant atom dictionary. The experiment results suggests that the algorithm reduce the searching calculating process and in favor of searching the fields which is of priority.Apart from this, this dissertation also bring forward a new way of a high space searching in a low space.

Keywords: image decompose, matching pursuit, genetic algorithm