改进HD距离和遗传算法的图像匹配研究

刘晋胜，彭志平，周 靖

（广东石油化工学院 计算机与电子信息学院，广东 茂名 525000）

0 引言

图像匹配是图像理解和计算机视觉中的关键技术之一，在运动目标跟踪和识别、视频运动估计和图像检索等领域有广阔的应用前景。随着图像清晰度的提高，图像的微小细节变得清晰，对图像匹配的要求进一步提高，目前主要采用特征点匹配和模块匹配等方法。在特征点匹配方面，Lowe提出的尺度不变特征变换（SIFT）方法匹配精度高[1]，对角度、尺度变化以及亮度变化都有较强的稳健性[2]，但该方法需对图像进行高斯函数的多尺度变换及获取图像的极值点等复杂运算，无法满足高分辨力图像及复杂场合的匹配精度要求，从而限制了SIFT算子应用[3]。在模板匹配方法中，图像匹配测度Hausdorff（HD）距离，能有效进行图像搜索，因具有计算快捷、不需点对点精确匹配和对局部非相似变形不敏感等优点而得到广泛应用，但经典HD距离采用的最大最小距离对出格噪声和遮挡非常敏感，将导致距离计算的严重错误[4]。许多研究者对其理论形式进行了改进，文献[5-6]提出了部分HD距离、加权HD距离以及稳健统计量LTS-HD等方法处理含有严重遮挡或退化问题的图像，能提高匹配的抗干扰能力，增强其在图像匹配中的应用，本文采用概率加权HD距离（Probability weighted Hausdoff，PWHD）作为算子，能准确找到HD距离的中心，实现图像精确匹配。

改进HD距离实现图像匹配取得了很好的效果，但该方法仍存在匹配计算量大等问题，许多学者提出采用PSO算法[7]及遗传算法等智能算法对其进行优化，以加快图像匹配的速度。冷雪飞等人[8]采用遗传算法的导航实时图像匹配算法，能够提高算法的抗干扰能力等性能，文献[9-10]应用改进的遗传算法提高图像匹配的收敛速度，适用各种不同的图像匹配场合，取得了较好的效果，但算法使用时，必须对不同的图像设置特殊的参数，参数选择对结果影响大，算法稳健性较差。本文提出一种多策略的并行遗传算法（Multi-strategy Parallel Genetic Al⁃gorithm，MSPGA），在并行遗传算法上采用不同的算法策略，以增加群体的多样性及算法的稳健性，对概率加权HD距离进行寻优，实现图像匹配。实验结果表明该算法有效，能满足高分辨力图像匹配要求。

1 改进HD距离

HD距离是描述两组点集之间相似程度的一种量度，它是两个点集之间距离的一种定义形式：假设有两组集合A=｛a1，a2，…，ap｝，B=｛b1，b2，…，bq｝，则这两个点集合之间的HD距离[11]定义为

式中：‖·‖是点集A和点集B间的距离范式。式（1）称为双向HD距离的最基本形式，h（A，B）和h（B，A）分别称为从A集合到B集合和从B集合到A集合的单向HD距离，取两者中的较大者为两集合的双向HD距离H（A，B），度量了两个点集间的最大不匹配程度。

HD距离对变形不敏感，对噪声和图像遮挡退化等比较敏感，文献[8]采用加权平均的方式实现，取得了较好效果，但算法的权值由图像的边沿特征二值化分布情况来决定。本文提出PWHD，是针对两张图片的h（A，B）距离出现的概率来进行加权处理。具体公式为

式中：加权函数w（a）是此距离的权值，由该距离出现的概率决定，概率越大，最后为该值的可能性越大，公式为

式中：na是点集A中特征点的总数，h（a，B）是点集A中的特征点a到点集B的距离，hi（a，b）是点集A中的特征点ai到点集B的特征点b距离，w（a）是此距离的权值，c是归一化分段后进行分段的参数，参数由模版大小确定。h（B，A）的公式同上。

PWHD能够根据HD距离出现的概率来自适应选择加权参数w（a），通过对图像匹配时距离数值的分析发现，此时的数值基本成单峰形式，采用概率加权将更加突出峰值数据，使PWHD距离不仅能改善噪声点、漏检点的影响，也克服了遮挡对图像的影响。PWHD较平均HD距离（MHD）更能够突出距离的相对值并有效去除干扰、突变等情况；较文献[8]加权HD距离的获取不用进行图像边缘的预处理，实现方式简单，因此PWHD距离测度较原HD测度更具优越性。但是不论是传统的HD还是改进的HD，在对高分辨力图像进行处理时计算量仍然较大，匹配速度有待提高，因此采用多策略并行的改进遗传算法进行搜索，以期加快匹配速度。

2MSPGA实现

目前，多核处理器的广泛适用使得算法的并行性研究不断增多，并行遗传算法的研究及实现越来越多，为提高遗传算法在图像匹配中不用根据每一幅图片进行修改算法参数，本文提出了一种稳健性强、收敛性速度快的多策略并行遗传算法（MSPGA）。

MSPGA采用并行算法的结构，采用8个并行分支，并构建8个不同的选择、交叉、变异的遗传操作为并行策略，采用是遗传算法中较常见及经典的操作方法，进行图像匹配，对应如表1所示。

表1 算法策略配置

通过改变遗传算子共可产生8个遗传策略，算法结构框图如图1所示。

在图1中数据的迁移产生下一代群体，数据交换采用自适应迁移。自适应迁移策略中，各分支需要转出的数据跟该分支中第t代个体的适应度及前面未迁移代的个体适应度之和成比例关系

式中：fi为个体的适应度；fj为分支的适应度；M为分支群体规模；Kj为第j个策略分支转出数据数量；T为第j分支未迁移代数值，若当代进行了数据迁移设置T值为1，若未产生迁移T=T+1，k为迁移系数。k为针对转移数据量、交换时间、群体多样性等方面综合考虑，再由数据迁移加速度比关系及系统采用的串行传输速率关系，取k值为4将得到较好的加速比。

由自适应迁移策略计算可知，在算法策略针对该函数寻优的过程中，分支适应度大的群体转出的最优个体数量较多，实现不同分支、不同策略最优个体的共享。在移民操作中完成自适应迁移的移出操作后，在数据转移空间将其他分支转出的数据移入到各个分支，重新构成新一代的子群体，作为下代父代群体，各子群体再次分别进行算法选择的操作。

3 实验步骤及结果分析

3.1 图像匹配步骤

在进行多策略并行遗传算法的PWHD实现时，由于PWHD不需对图像进行预处理，只需把H（A，B）放入适应度函数计算过程，实现步骤：

1）对图像进行编码，采用二进制编码形式，对匹配点的坐标（x，y）进行编码，染色体的长度可随模板长度的变化而变化，如一幅2592×1944像素的图像，x用12位，y用11位二进制码表示，产生一个23位长度的染色体。

2）随机产生初始种群，每个分支各50个，共随机产生400个位置（x，y）并把其转化为基因串，作为初始种群。

3）对个体进行适应度函数值计算，适应度是遗传算法中个体进化的驱动力，是进行自然选择的唯一依据。因此设计如下适应度函数

式中：Hx,y(A,B)是在坐标（x，y）处模板和待匹配图像两点集的PWHD距离，加权分段参数c设为10。由该式可见，当两点集越匹配时，PWHD越小，适应度值越大，表明个体越优越。由于在完全匹配的理想情况下，PWHD的H（A，B）有可能等于0，为了避免分母为零，给数值进行加1处理。

4）遗传算法策略进化。每一分支采用该分支中的选择、交叉及变异，产生下一代群体。算法策略如表1所示，其中交叉算子中由于一点交叉对算子的改变影响比两点交叉小，因此算法在交叉概率pc的设置采用一点交叉分支取为0.9，两点交叉分支选取为0.8，来平衡两种交叉方式对算子的影响。变异算子变异概率的大小对算法的收敛性有较大影响，针对图像特征算法的不固定性，取普通变异概率为0.01，大变异概率为0.1。

5）最优个体迁移。最优个体自适应迁移根据自适应迁移公式（式（5））计算分支群体需当代迁出的个体数量，在数据转移空间将其他分支转出的数据移入到各个分支，重新构成新一代的子群体，作为下代群体。

6）算法终止。对该算法的终止条件跟简单遗传算法相同，一是采用最大循环次数本文设为100次，当次数到达最大循环次数时停止；二是采用阈值判断，在算法中的适应度超过阈值时停止，算法采用了多种遗传策略，因此对满足条件的判断上采用了对单一种群判断的策略，当其中某一分支种群的群体适应度达到设定阈值或遗传代数达到上限时退出算法操作，得到算法最优解。若两个终止条件都未满足，则转回3）继续执行。

3.2 试验结果及分析

为了验证本文算法的有效性，利用Sony相机拍摄的500万像素图像在计算机上进行匹配仿真实验，算法采用Matlab语言编写，在主频为Intel Core4 2.8 GHz、内存2 Gbyte的PC机上进行算法测试。首先从不同场景下对本文算法进行定量性能评估，并给出匹配结果；然后用本文算法与文献[8]的算法进行分析比较。

由于遗传算法具有随机性，为验证算法稳健性，采用100组图像进行试验。对图像在噪声、旋转以及抗遮挡方面进行算法收敛速度、正确匹配次数和平均收敛时间进行分析，验证算法中PWHD的抗干扰能力及MSPGA的稳健性。选取其中一幅图像加以说明，原图（图2a）为2592×1944，匹配图（图2b）为256×256，图像进行原始匹配结果为图2c。分别进行加入随机噪声、匹配图像旋转10°及加入1/4图像匹配区域遮挡等实验，各组实验100次，遗传算法的收敛过程如图3所示。

图3为在各种情况下多策略并行遗传算法的收敛分析，结果说明算法对图像中的噪声、旋转以及抗遮挡有效。在MSPGA收敛过程和结果进行数据追踪，8个分支中收敛速度和适应度的值在不同图像的情况下数值各异，在原图匹配中，策略3的收敛速度快，在第60代即满足收敛要求；加入随机噪声匹配中，分支5的收敛速度快，在第80代即满足收敛要求；在匹配图像旋转的匹配中，策略4的收敛速度快，在第90代即满足收敛要求；而区域遮挡匹配中，分支1的收敛速度快，在第90代即满足收敛要求。

为了验证算法的匹配精度及速度，用相近的文献[8]和[10]匹配算法对实验图像进行匹配，图像匹配算法各进行100次实验，匹配误差为（0，0）时认为解正确。匹配结果比较如表2所示。

表2 不同算法的匹配结果

由表2可见，本文算法在各种情况下收敛速度均较文献[8]和[10]的算法快，正确率只在图像旋转时较文献[8]算法低，表明本文算法在图像匹配的速度及精度均较高。

4 结论

在对高分辨力图像进行匹配的过程中，本文提出了采用概率加权HD距离及多策略并行遗传算法的方法，充分考虑了图像匹配中噪声干扰、旋转及遮挡的情况，因此对HD距离进行了研究和改进，并考虑图像匹配中数据容易陷入局部最优，采用多策略并行遗传算法加快匹配速度。实验结果表明提出的算法是有效、可行的。

[1] LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[2] 宋海华，邵志一.基于改进型特征匹配的图像拼接方案设计[J].电视技术，2008，32（2）：19-20.

[3] 杨涛，张艳宁，张秀伟，等.基于场景复杂度与不变特征的航拍视频实时配准算法[J].电子学报，2010，38（5）：1069-1077.

[4] Jordi Inglada，Alain Giros.On the possibility of automatic multisensor image registration[J].IEEE Transactions on Geoscience and Remote Sensing，2004，42（10）：2104-2120.

[5] 王靖，朱梦宇，赵保军，等.基于小波和改进型Hausdorff距离的遥感图像配准方法[J].电子学报，2006，34（12）：2167-2169.

[6] 杨猛，潘泉，张绍武，等.基于定量定性互信息的多层次特征图像匹配算法[J].中国图象图形学报，2010，15（9）：1376-1383.

[7] 陈飒，吴一全.基于Contourlet域Hausdorff距离和粒子群的多源遥感图像匹配[J].测绘学报，2010，39（6）：599-604.

[8] 冷雪飞，刘建业，熊智.基于遗传算法的导航实时图像匹配算法[J].通信学报，2008，29（2）：17-21.

[9] 杨延西，刘丁，辛菁.模糊遗传图像相关匹配算法[J].仪器仪表学报，2005，26（11）：1166-1169.

[10] 龚志辉，张春美，孙雷，等.一种改进Hausdorff距离和自适应遗传搜索的遥感目标匹配方法[J].测绘学报，2009，34（5）：190-193.

[11] 孙晓路，丁晓青.基于边缘特征的异质图像目标配准方法[J].电视技术，2010，34（12）：130-134.