基于小波变换和改进的粒子群的新型图像匹配算法的研究

解冰　李海娟

摘要：伴随着图像处理技术不断发展，图像匹配是指根据图像的特征在图像数据库中检索相似或相同的图像。传统图像检索算法计算量大、精度小，为了减少计算量提高精度，本文在传统算法基础上将图像匹配问题转化成在图像数据库中根据模板图像数据对目标进行锁定的模型：第一步将模板图像和源图像分区并取灰度直方图信息。第二步将寻找模板图像最相似的问题转化成通过粒子群优化进行分类第三步：通过对相似度大的那类图像进行精确匹配得出最相似的图像。实验结果表明：基于粒子群和新分类思想的图像匹配（PBIM）算法能够在源图像数据库中快速匹配出相似的图像组。

关键词：新分区；图像检索；粒子群优化算法；分类

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）11-0175-04

1 引言

信息飞速发展的今天，各行各业中图像检索已经成为不可或缺关键技术，目前使用者在搜集目标图片的时候使用的大部分是图片的文字标题，而基于内容的图片搜索是十分 少见的，但是基于文字标题的检索效率低，精度差，往往会检索出大量的结果让用户苦不堪言。图形图像检索越来越多的使用在各行各业，特别是大数据和智能计算的今天，生活中越来越多的使用图形图像处理，本文引入对图像通过改进的粒子群（Particle Swarm Optimization， PSO）和小波变换思想加以改进[1]，期望通过实验证明，在降低空间复杂度允许的情况下，同时降低时间复杂度。

通过将图像分块后提取直方图信息计算距离从而将直方图的距离转化为模板图像的位置，同时运用粒子群算法，将模板图像的信息转化为粒子的目标值，粒子群通过迭代学习，将与目标图像接近的图像进行汇总分类，即模板图像在源图像中的位置。实验结果证明此法在不失匹配精度的情况下，在速度方面也有较明显的改善，这种方法是切实可行的，与传统的方法相比更高效[2]。

2 图像检索模型

图像检索的用途支撑者很多学者与专家进行不断的改进。其原理是指通过算法在图像数据库中搜索模板图像的相似或相同图像[3][4]。问题的模型：给定一副大小分别为[K1×G1]的图像，源图像：[Pic1={C1（x，y），1≤x≤K1，1≤y≤G1}] ，模板图像：式中[C1]为图像的灰度值。本文采用灰度值比较方法，在计算机图像处理领域还可以利用其他特征：纹理[5]、形状[6]等。

图像或者图片的整体参数就是采集灰度值并计算总和 ，一组像素的直方图信息用函数[H（h1，h2，L，hi）]表示。本文提出的方法不再是按照挨个像素灰度直接比较的方法，经过反复改造和计算得出下公式：直方图间的距离可使用欧氏距离函数[ME[M（K，G，x，y），R（K，G，x，y）]]衡量：

[ME（M（K，G，x，y），R（K，G，x，y））=i=1L[HM（K，G，x，y）（i）-HR（K，G，x，y）（i）]2]

则可定义：

[M（position（i，j））=][si=1L[HM（K，G，0，0）（si）-HR（K，G，i，j）（si）]2] （3）

公式的含义是以模板图像为基准，在源图像中找相同大小的模块进行直方图信息比较，[Pic2]在[Pic1]中的最优位置[position（i，j）]，为了使得目标位置匹配准确、迅速，必然有

[M（Pic1（i，j），Pic2）]为0或接近0。这是解决问题的核心，找到最优位置意味着完成了图像的匹配。

图像的可用特征有很多，在不失精度的情况下为了简单方便的评价图像，我们采用了灰度值。若为了全方位的评价图像

3 新的分区思想

在计算机图像处理领域很多思想是为了提高处理效果。但是要评价一个图像可以根据很多种属性。比如颜色直方图、灰度直方图、纹理特征还有材质。还可以综合利用各种特征。传统的图像匹配都是将两幅图像的全部像素按着顺序进行比较。这种思想是最基础，也是最容易浪费时间和精确度的。因为两幅图像的内容大多数情况下是不一样的，如果其中有一部分不相似那就没必要将所有的像素特征再进行比较了。

为了节省图像评价的时间，本文中提出了新的分区思想，图像匹配的思想是找到相同或者最大接近的内容的图像，所以新的分区思想在判断内容上做了大胆的改进。 首先将原始圖像和模板图像取中间宽度为边长五分之一的中间带状相交区域，然后在图中A、B、C、D空白处取边长为图像边长五分之一的图像块，如图中 A、B、C、D区，在进行直方图，如图所示：

信息评价时，先让两幅图像的中间横竖相交的黑色区域进行对比，然后A区进行比对，如果结果在设定的阈值之内则继续进行B区，以此类推，这样将很多不一样的图像在比对A区的时候就淘汰了，所以节省了四分之三以上的计算量。通过实验验证该思想能够在不失精度的前提下很大程度的缩短了匹配时间降低了计算复杂度。

4 改进的粒子群优化算法

计算机领域中有很多优化算法。粒子群优化算法（Particle Swarm Optimization PSO）是一种用无质量、无体积的粒子作为个体，并为每个粒子制定了简单的行为规则，从而使整个粒子群表现出复杂的特性，可用来对复杂问题进行优化求解。

粒子群优化算法（PSO）是一种进化计算技术（evolutionary computation），1995 年由Eberhart 博士和kennedy 博士提出，源于对鸟群捕食的行为研究 。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群算法在对动物集群活动行为观察基础上，利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。

在优化过程中粒子追随群体中当前位置和速度最优的粒子而移动，并经逐代迭代搜索后得到最优解。在每一代中，粒子将跟踪本身迄今找到的最优解pbest和迄今找到的最优解gbest进行搜索。公式（1）（2）是粒子群更新的依据，

[v[]=w*v[]+c1*random（）*（pbest[]-present[]）+c2*random（）*（gbest[]-present[]）（1）//速度更新公式][present[]=present[]+v[]] [（2）]

c1，c2一般取2，[rand（）]取（0，1）之间的随机数，这样是算法更有随机性。公式（1）中第一项v[]是动量项，第二项是认知项，通常认为粒子认识到自身经验，从而增强学习，第三项是社会项，代表了粒子之间相互影响，相互合作。认知项代表粒子之间的竞争，社会项代表粒子之间的合作，从而实现群体智能搜索[8][9]。

在粒子群优化算法中，我们添加了随机的粒子和随机速度与随机位置，在仿真程度上使得算法更接近于现实，比如公式1和公式2中最后一项，经过实验数据的验证，添加了随机值的学习效果更佳，不同的参数对应不同的粒子群优化模型，对于粒子群来说算法参数选取和收敛性是影响算法性能和效率的关键因素，并且有紧密的联系，直接影响着粒子群的搜索过程和收敛特性[10]。

5 改进的算法及其分析

5.1算法解决问题的具体原理

根据之前提出的问题模型，我们将一个在海量图像中进行图像匹配的问题或者在一副图像中进行内容匹配的问题转换为一个样本空间在全局的范围内模拟粒子群算法优化问题，基于灰度的图像匹配的基本思想是将图像的不同归结为其直方图信息的差距[11]，从而将图像的检索转化为直方图的距离计算。

原图像参数为[K1×G1]，模板图像尺寸为[K2×G2]，具体在PSO算法编程时候，我们采用粒子数为[s]，迭代[n]代。每个粒子用一分辨率为[l×l]像素的小方格模拟，用随机函数[Vi（Vi1，Vi2）=（rand（m1-m2+1，m1），rand（n1-n2+1，n1））]均匀初始化粒子的坐标位置。

5.2 小波变换处理原理

小波变换在图形图像处理领域经常采用，图像的低频部分保存的是图像的轮廓信息，而高频保存的是图像的边缘和细节信息，大量的研究表明，幅值低的高频信息对于图像共享较小，所以丢弃对图像质量的影响不大，所以小波变换的特性给了图像压缩一个很好的工具，将原图进行小波分解以后，为高频信息设置一个阈值a，假如该点的值小于a则置零这样就抛弃掉了图像中影响不大的低幅值高频信息，还原出来的图像没有明显的质量下降，但是占用空间却变小了。

本文是为了降低计算量，提高图像匹配的速度和效率，小波变换之后的低频部分仍然可以进行进一步处理。而后继续采用优化算法，是本文提出的核心思想。

5.3算法步骤

PSO中的粒子信息对应于本问题中要求解的模板在源图中的位置信息[position（i，j）]。具体算法步骤：

Step1：输入一幅源图像和一幅模板图像。

Step2：对两幅图像进行一次小波变换，分别取原图像的高频部分。

Step3：分别将小波变换后的源图像和模板图像进行整体新分区（按图1）

Step4：对图像相同坐标位置的高频部分按照新分区计算直方图信息并将结果记录在[c1]中；对模板图像低频部分算直方图信息并将结果记录在[c1]中。

Step5：粒子群算法参数设置：设置权值参数[c1]和[c2]，将当前迭代代数置为t=1，在源图像（新分区后的低频部分）随机产生[s]个粒子，如圖6所示，形成初始样本值，并随机产生各粒子的初始速度。

Step6：粒子群运动过程中进行评测，粒子学习不出现早收敛现象视为正常。

Step7：取单个粒子当前的适应值与整个样本空间最优值比较。

Step8：按公式[（1）（2）]更新粒子的速度和位置，产生新的种群。

Step9：检查是否满足算法结束条件（或停机条件），若满足，计算结束，输出[gbest]，否则[t=t+1]，转到第6步，直到满足结束条件。

经过多次采集样本和反复实验，我们讨论的范围与实际是比较接近的。

5.3算法的评价

适应度评价函数是PSO算法的一个重要因素，在图像匹配问题中适应度评价函数就是上述提到的度量

[ME（M（w，h，x，y），R（w，h，x，y））=]，我们采用的原理是：

[ME（M（w，h，x，y），R（w，h，x，y））=] （3） [ME（M（w，h，x，y），R（w，h，x，y））=]

[i=1L[HM（K，G，x，y）（i）-HR（K，G，x，y）（i）]2] （4）

评价函数公式：

[f（position（row，col））=1（m1-m2）*（n1-n2）]*

[row=1K1-K2col=1G1-G2si=1L[HM（m1，n1，0，0）（si）-HR（m2，n2，row，col）（si）]2] （5）

其中公式（5）是改进的公式，[f（position（row.col））]是粒子群算法评价函数，[HM（m2，n2，0，0）（Si）]是模板图像低频部分M的宽为[m2]，高为[n2]，左上角坐标为（0，0）的图像的直方图信息 ，同理[HR（m1，n1，0，0）（Si）]是源图像低频部分上宽为[m1]高为[n1]，左上角坐标为[（row，col）]的直方图信息，[row]，[col] 分别表示模板中某像素的位置。粒子群速度位置更新公式如上文所述公式[（1）（2）]。

该公式经过修改和实验，在参数优化和实验学习效果上比传统的算法都有较先进的改进。

6 实验结果和分析

6.1实验数据

本实验主要用C++语言实现，编译环境：VS2008 和matlab7.0，所使用的图像是384*384，模板图像是128×128，64×64，32×32。粒子个数是70，如图7所示，匹配时间复杂度及同传统算法比较数据如图8所示。模板部分处理后处的效果如图6。其中图6是将源图像新分区后低频部分通过PSO算法将最优解时的粒子的按着坐标位置在matlab 7.0中画出。

從而使得粒子在整个源图像空间内搜索，图6为本算法停止运算后放大的效果图（模糊是因为新分区后低频部分放大产生的失真现象的结果）。

6.2 实验数据比较分析及结论

进行多次实验采集是验证问题的基本步骤，本试验中针对粒子群算法设置了一个最大迭代次数如图6中， PSO算法进行匹配我们得出的精确匹配率结论如图7：

图7中将本文提出的算法和未改进的算法经过改进的比较，纵轴是匹配准确度。从图易知经改进的算法能做到精确匹配，比其两种传统的更算法高效理论上讲：按上述实验对灰度图像进行传统匹配，由于传统图像是逐像素进行匹配，在执行传统算法时要对两幅图像进行完全匹配处理，从而我们可以得出传统方法计算量公式[（K1-K2）×（G1-G2）]，传统算法计算次数应该为[（384-128）×（384-128）= 65536]次，根据笔者实验实际设定的粒子数，基于新分区后用PSO算法则只需要计算[80×200=16000]次；实验过程中笔者根据实际情况和查阅文献材料发现，粒子个数的选取对结果有重要的影响，群体粒子数目的选择不能过大或者过小，粒子数过大，计算量增加难以体现PSO的精确性，数量过小不能保证解的精确度，同理迭代次数也是有要求的，经过多次实验群体数在[50?80]之间，迭代次数在[140?360]之间时，都能得到同图7相近的结果，由此可见粒子数量和迭代次数在上述数据之间取值较为理想。

图8中纵轴表示时间（单位秒），从图中我们可以看到，改进的算法的时间复杂度和传统的算法相比有了明显的降低。综上实验表明，该算法有效地减少了运算量，提高了图像匹配的精度。实验中，为了方便实现，采用的是图像的直方图的信息距离作为评价图像匹配的标准，在实际应用中还可能有其他的评价方法，如采用ML法中的ML距离作为适应度来进行评价当前搜解，还可以用文献[12][13]中提到的图像特征匹配方法，减少计算量，提高算法的效率。

7 结束语

本文的创新点在进行小波变换的基础上引入智能学习算法和对图像进行新分区，将图像进行新分区后提取图像主要信息，这样在计算时降低了计算复杂度，提高了算法效率，实验证明经PSO算法优化后算法在满足精确要求的情况下时间复杂度大大降低。这是在传统的算法基础上进行的改进，通过实验证实是可行的不足之处，实验中得出改进的算法的匹配精确率随着模板的增大而减小。如何避免这一现象将是笔者下一步的研究对象。

参考文献：

[1] 何清法，李国杰.综合分块主色和相关反馈技术的图像检索方法[J].计算机辅助设计与图形学报，2001，13（10）：912-917.

[2] Qiu G P， Lam K M. Frequency layered color indexing for content-based image retrieval [J]. IEEE Transactions on Image Processing， 2003， 12（1）：102-113.

[3] 汪祖媛，梁栋，李斌.基于树状小波分解的纹理图像检索[J].中国图象图形学报，2001，6（11）：1065-1069.

[4] Mallat， S. G， A Theory for Multiresolution Signal Decomposition： The Wavelet Representation， IEEE Trans. PAMI， 1989，11（ 7）： 674-693.

[5] 廖云涛，任仙怡，张桂林，等.一种新的基于对应像素距离度量的图像相关匹配方法[J].红外与激光工程，2001， 30（6）： 418-421.

[6] 刘哲，任金昌，李言俊.面向遥感应用的图像融合的原理和方法[J].航空计算技术，2001（4）： 9-12

[7] 孙劲光.基于颜色特征的图像数据管理模式研究[D].辽宁：辽宁工程技术大学，2006.

[8] 史燕. 基于新分区的图像检索技术研究[D]. 西安： 西北大学， 2006.

[9] R C Eberhart， J Kennedy. Particles Swarm Optimization[C]， In：IEEE International Conference on Neural Network， Perth， Australia， 1995

[10] 曾建潮，介婧，崔志华.微粒群算法[M].北京：科学出版社，2004.

[11]Zhang，A.KanKanhalli，andS.W.Smoliar，“Automatic Partitioning of Full-Motion Video”，ACM Multimedia System， Apr.1993.

[12] Flickner， M.， etc. Query by image and video content： The QBIC System [J]. IEEE Computer， 1995， 28（9）：23-32.

[13] Rui Y， Huang T S. Optimizing learning in image retrieval[C]. IEEE Conf. on CVPR， South Carolina， USA， 2000.