基于动态拓展的特征匹配方法

左威健，胡立华，刘爱琴，张素兰，马 瑞

(太原科技大学 计算机科学与技术学院，山西 太原 030024)

0 引 言

基于图像的特征匹配方法[1,2]主要包括基于灰度的匹配、基于梯度的匹配、融合多种理论的匹配。然而，针对结构复杂、纹理重复的对象，上述特征匹配方法存在以下问题：①图像区域内各对象提取出的特征点，数量较少；②图像中颜色、结构相近的对象，特征点邻域像素信息趋于相同，采用特征局部描述子生成的描述信息辨识度不高；③采用传统几何度量方法，相近的特征描述信息将产生大量错误匹配结果。

针对上述问题，结合最近邻(K nearest neighbors，KNN)与具有噪声的基于密度的聚类(density-based spatial clustering of applications with noise，DBSCAN)思想，本文提出了一种基于动态拓展的特征匹配方法。给定待匹配的两幅图像，该方法首先采用尺度不变特征变换(scale-invariant feature transform，SIFT)算子提取图像特征点，并构建匹配基础数据集；其次，基于基础数据集，结合KNN与DBSCAN思想，设计了一种逐层约束的动态拓展聚类方法，生成待匹配图像聚类簇；然后，依据两幅待匹配图像聚类簇的簇内距离与簇内区域密度，依据匹配度量因子，获得待匹配图像间的对应聚类簇；最后，依据对应簇内特征描述子的最近邻与次近邻比值，得到最终匹配结果。

1 相关研究

目前，基于图像的特征匹配算法主要分为3类：基于灰度的匹配算法、基于梯度的匹配算法、融合多种理论的匹配算法。

基于灰度的匹配算法也称相关匹配算法，典型方法有：绝对误差和算法(sum of absolute differences，SAD)[3]、误差平方和算法(sum of squared differences，SSD)[4]、归一化积相关算法(normalized cross correlation，NCC)[5]等。该方法的优点为计算过程简单，容易理解，匹配精度高；缺点为运算量大，对噪音、光照、色彩差异与旋转等适应性较低，匹配效果稳定性不高。基于梯度的匹配算法，该方法首先提取图像特征，生成特征描述子，然后依据一定的度量信息匹配特征。典型方法有：GMS[6]+R、SIFT[7]+R、SURF[8]+R与ORB[9]+R(R=RANSAC)等。融合多种理论的匹配算法，通过引入模型、图论、交叉变异等理论，构建空间约束，实现特征匹配。典型的有：基于语义网络匹配算法[10]、基于深度学习匹配算法[11]、基于遗传理论匹配算法等。典型方法有：基于空间聚类的异常值剔除匹配算法[12]，该方法基于初始匹配集构建聚类观测集，将匹配集中误匹配剔除问题转换为观测集中寻找离群点的问题。但该方法依赖于初始匹配集，数据分布不同，最终离群点的查找效果也会有很大差异，匹配结果鲁棒性不高；基于语义模板的匹配算法[13]，该方法基于核距离的简单线性迭代聚类，从模板图像中提取稳定的超像素区域，并构建二进制描述符，以构造多级语义融合特征向量，但该算法在构建区域描述符时，需比较每个超像素区域与其相邻像素之间的平均强度差，来获得每个超像素的优势梯度取向。因此，时间复杂度较高，有待进一步的优化与改进； 基于特征点平面相似性聚类的图像拼接算法[14]，该方法依据相同平面特征点符合同一变换的特性，通过度量初始匹配集中对应特征点的相似性，利用凝聚层次聚类把特征点划分为不同平面，筛选误匹配点。然后结合平面信息，通过带权重的线性变换，计算网格的局部单应性变换矩阵，最后基于此矩阵，利用多频率融合方法拼接配准图像。但该方法对于运动场景下变化较大的图像配准与拼接，仍存在部分适用性问题；基于几何离群值去除的匹配算法[15]，该方法首先依据包含相同场景的两幅图像间特征点的全局相似几何关系，建立数学模型，其次优化模型，找到模型的最优解，最终基于模型剔除误匹配，但该方法在求解模型结果时，对于纹理重复对象，时间复杂度较高，不适用于大规模、实时性的视觉任务； 基于DBSCAN与互信息的图像拼接算法[16]，该方法为保证实时性，提取ORB特征点，并利用DBSCAN聚类算法快速构建邻接图，然后通过邻接图来估算图像的重叠区域。该方法通过估算两幅图像间的重叠区域，进而在重叠区域内进行特征匹配来提高特征点的匹配效率。但该方法基于原始DBSCAN聚类算法进行对应查找，需手动确定重叠区域，且区域范围变化较大，难以保证匹配效果。因此，融合多种理论的特征匹配方法能够结合对象局部结构的相似性，对特征点集进行结构划分并配对；但此类方法计算复杂度较高，不适用于实时场景。

然而，针对结构复杂、纹理重复的对象，上述特征匹配算法仅从图像间局部特征描述信息的角度出发，进行配对，而没有从全局考虑特征匹配的实验结果。实际上，不同视角下的同一对象，检测的图像特征点往往呈现簇状，且特征匹配结果在几何上具有一致性。因此，结合图像特征点的局部描述信息与特征点间的几何约束，可进一步提高特征匹配效率。

2 基础定义

给定图像I(Image)及初始半径δ、近邻参数K，特征提取后生成的特征点集合为P。进而基于特征点集P，基于图像聚类以及特征匹配方法的相关定义如下：

定义1K近邻集KNN(p)：给定图像I内任意特征点p，KNN(p)为特征点p的K近邻集合且KNN(p)满足以下条件

∀q∈KNN(p),o∉KNN(p), dist(p,q)≤dist(p,o)

(1)

式中：函数dist() 计算取值为特征点p，q间坐标的欧式距离。即

(2)

定义2 核心点C(p)：给定初始半径δ与近邻参数K，置特征点p与KNN(p)内所有特征点间欧氏距离最大值为Dmax，若Dmax≤δ，则点p为核心点。

定义3 直接密度可达：特征点q由特征点p直接密度可达所满足的条件为

∃p∈C(p) ∧q∈C(q)∧q∈KNN(p)

(3)

定义4 密度可达：在图像I中，特征点q由特征点p密度可达定义为：存在样本序列p1,p2,…pn， 其中p1=p，pn=q， 且pi+1与pi直接密度可达。

定义5 密度相连：存在特征点o，使得特征点p和q均由o密度可达，则p与q密度相连。

定义6 噪声点：动态迭代聚类延展后，生成n个聚类簇，若某特征点p不属于n个聚类簇中任意一个，则认为p点为数据集中噪音点。

定义7 匹配正确率R定义为

(4)

式中：M为正确匹配对数目，N1，N2分别为图像IL(image left)，IR(image right)中提取出的SIFT关键点数目，R为匹配正确率。

3 本文方法

针对结构复杂、纹理重复的对象，基于图像的特征匹配过程具有以下特点：①不同视角下，同一对象提取的特征点分布密集、间距小、轮廓相似且呈现簇状；②在初始匹配集中，多数正确匹配与错误匹配相比，邻域信息更密，且正确匹配常位于两幅图像间的同一对象；③同一对象间特征点，其特征分布由内及外，满足一定的几何约束。因此，基于上述匹配特性，本文引入基于密度的聚类思想。在局部特征信息基础上，增加全局几何约束信息，即在局部描述子的基础上，通过查找图像间的对应区域(聚类簇)，来提高特征匹配的效率。

DBSCAN[17-19]是一种基于密度的空间聚类算法，该方法无需预先输入聚类数量、抗噪能力强、能查找处理任意形状和大小的簇；但应用于图像数据进行聚类，存在以下问题：①聚类结果受输入的相关参数影响较大，当参数取值不同，聚类结果差异明显。②区域内最小值MinPts只能作为核心点周围圆形区域内的度量标准，而无法动态反映邻域间的映射关系。③图像采集受到光照、设备等因素影响，当采用同一特征提取算法，提取结果会存在部分差异。因此，针对结构复杂、纹理重复的对象，基于DBSCAN的聚类方法所确定的对应区域，精度较低，无法进一步进行特征匹配。而基于邻域信息的KNN方法可将特征点间的欧氏距离映射为特征点间的邻域信息，具有不依赖特定参数、表征邻域信息，且能处理不同规模数据的优点，但抗噪效果不好。

因此，结合KNN与DBSCAN思想，本文提出一种动态拓展聚类的特征匹配方法。该方法主要有3个关键步骤：构建特征点数据集、特征聚类区域划分、聚类簇匹配。

3.1 构建特征点数据集

针对结构复杂、纹理重复的对象，为了提高特征提取数量，本文结合SIFT思想，依据式(5)对输入图像I(x,y) 进行图像高斯模糊，依据式(6)构建尺度空间。不同的尺度空间不仅保证了其特征提取结果具有尺度、旋转、亮度不变性，而且还可增加特征点提取数目，具有计算量小，稳定性高等优点

L(x,y,σ)=G(x,y,σ)*I(x,y)

(5)

构建尺度空间时，所需高斯模糊差值为式(6)

D(x,y,σ)=L(x,y,kσ)-L(x,y,σ)L(x,y,kσ)=G(x,y,kσ)*I(x,y)L(x,y,σ)=G(x,y,σ)*I(x,y)

(6)

输入两幅待匹配图像IL(x,y)，IR(x,y)， 并分别采用SIFT算子提取特征，可获得基础数据集SD1，SD2。其中，SD1,2中的每一特征点坐标可描述为p(px，py)， 来表示特征点p的几何坐标信息。

3.2 特征聚类区域划分

构建特征点数据集后，依据特征点间几何信息，确定图像聚类簇。针对任一图像IL，聚类过程为：

(1)输入基础数据集SD1，依据给定参数K与半径参数δ，由定义1和定义2，确定图像IL中的核心点与非核心点，并确定所有核心点的半径Dmax；

(2)针对图像IL内的任一核心点p，依据参数Dmax，在图像IL中，每点所在区域可划分为3种圆形区域(circle region，CR)：核心区域、渐进区域、边界区域。具体定义如下：①核心区域(kernal region，KR)：依据定义2，以任一核心点p为圆心，Dmax为半径确定圆形区域CR(p)，若CR(p)内特征点全为核心点，则该区域为点p核心区域，记为KR(p)；②渐进区域(progressive region，PR)：依据定义2，核心点p确定的圆形区域CR(p)内，部分特征点为核心点，此时，点p所在区域为渐进区域，记为PR(p)；③边界区域(boundary region，BR)：依据定义2，核心点p确定的圆形区域CR(p)内，没有核心点，此时，点p所在区域为边界区域，记为BR(p)。

(3)基于上述区域，对不同区域内特征点，进行分类拓展，拓展条件为：①若核心点p所在区域为核心区域，此区域内核心点不做处理，与点p无约束关系，直接列入核心队列，且标注p点类别，进行下次拓展。(函数2)；②若核心点p所在区域为渐进区域，此区域内核心点q与点p间存在约束关系，即Dmax(q)≤Dmax(p)*1.5。 若满足上述约束，才列入核心队列，并标注p点类别。否则，只标注p点类别。而非核心点直接标注p点类别。(函数3)；③若核心点p所在区域为边界区域，此区域内虽无核心点，但非核心点q与点p间存在约束关系，即Dmax(q)≤Dmax(p)*2.0。 若满足约束，才标注p点类别。当聚类初始时，点p便位于边界区域，则跳过此点，随机选取下一核心点。(函数4)。

依据上述过程，针对图像IL，基于KNN和DBSCAN的聚类算法KD可描述为：

算法1：KD聚类

输入：SD1、 (δ，K) // |SD1|=N

输出： (p，cluster) //每一个特征点的聚类结果

(1)queue= null //初始核心队列置为空

(2)p∈SD1：p= unclassified，p= unvisited

(3)cluster= 0 //初始类别标为0

(4)KNN(p) (p∈SD1)//各点的K近邻集合

(5)Dmax(p) (p∈SD1)//各点的可变半径

(6)CR(p) (p∈SD1)//各点所标定的圆形区域

(7)for(p∈SD1)do

(8) ifp== unclassified then

(9) ifDmax(p) ≤δthen

(10)cluster=cluster+1 //类别加1

(11) classify(p,cluster,Dmax(p))//函数1

(12) end if

(13) end if

(14)end for

函数1： Function classify(p,cluster,Dmax(p))

说明： 基于核心点p的分类处理

输入：p、cluster、Dmax(p)

输出：clusters//基于点p生成的聚类簇

(1)ifCR(p)∈KR(p) then

(2)p= visited

(3)cluster(p) =cluster//当前类别赋予点p

(4) assignKR(cluster,p,Dmax(p))//函数2

(5)else ifCR(p)∈PR(p) then

(6)p= visited

(7)cluster(p) =cluster

(8) assignPR(cluster,p,Dmax(p))//函数3

(9)else ifCR(p)∈BR(p) then

(10) ifp== unvisited then //若聚类初始，核心点位于BR内，跳过此点

(11)cluster=cluster-1

(12) continue

(13) else //聚类延展，遇到BR内核心点

(14) assignBR(cluster,p,Dmax(p))//函数4

(15) end if

(16)end if

函数2： Function assignKR(cluster,p,Dmax(p))

说明： 遍历点p核心区域内数据， 聚类延展

输入：cluster,p,Dmax(p)

输出：clusters

(1)forq∈KR(p) do

(2) ifq== unclassified then

(3)cluster(q) =cluster

(4)queue=queue∪q

(5) end if

(6)end for

(7)fore∈queuedo

(8) ife== unvisited then

(9)e= visited

(10) classify(e,cluster,Dmax(e))

(11) end if

(12)end for

函数3： Function assignPR(cluster,p,Dmax(p))

说明： 遍历点p渐进区域内数据， 聚类延展

输入：cluster,p,Dmax(p)

输出：clusters

(1)forq∈PR(p) do

(2) ifq== unclassified then

(3)cluster(q) =cluster

(4) ifDmax(q)≤δthen //q为核心点

(5) ifDmax(q)≤Dmax(p) * 1.5 then

(6)queue=queue∪q

(7) end if

(8) end if

(9) end if

(10)end for

(11)fore∈queuedo

(12) ife== unvisited then

(13)e= visited

(14) classify(e,cluster,Dmax(e))

(15) end if

(16)end for

函数4： Function assignBR(cluster,p,Dmax(p))

说明： 遍历点p边界区域内数据， 聚类不延展

输入：cluster,p,Dmax(p)

输出：clusters

(1)forq∈BR(p) do //此处不导入数据到queue

(2) ifDmax(q) ≤Dmax(p) * 2.0 then

(3) ifq== unclassified then

(4)cluster(q) =cluster

(5) end if

(6) end if

(7)end for

3.3 聚类簇匹配

输入两幅图像IL，IR，分别采用KD聚类算法生成相应聚类簇后，下一步需要确定两幅图像间的对应相似簇，即同一对象。两簇间的相似性度量依据如下两个参数：

(1)簇内距离D：任给图像的某一簇A，则A的簇内距离定义为：簇A中所有核心点间欧氏距离最大值，记为AD，簇B则为BD。

(2)簇密度N：任给图像的某一簇A，则簇A密度定义为：簇内特征点个数，记为AN，簇B则为BN。

从上述两个参数出发，两幅图像间相似因子SE可定义为：

设图像IL的簇A，簇内距离为ADIL，簇密度为ANIL，任取图像IR的簇B，簇内距离为BDIR，簇密度为BNIR，下标为图像标号，则簇A、簇B间相似因子SEA,B定义为式(7)

SEA,B=ADIL/BDIR+ANIL/BNIR

(7)

理想状态下，两簇间相似因子SE取值为2。因此，任意两簇间的比值SE越接近于2，则越相似。

取图像IL中任意簇A，计算图像IR中与簇A最相似的簇B、次相似的簇C。若簇A、B满足式(8)，则认为两簇为同一对象

MS(A,B)=SEA,B/SEA,C≤0.8

(8)

最相似函数MS()为两幅图像间，聚类簇度量函数。

3.4 算法设计

基于上述过程，设计了一种基于KNN与DBSCAN聚类的动态拓展匹配算法KN_DB：匹配算法的基本流程如下所示：

输入：图像IL、IR

输出：特征匹配结果匹配对数目M

(1)对图像IL、IR构建尺度空间，生成SIFT特征点数据集SD1,2；

(2)依据KD算法，分别确定图像IL、IR的聚类结果；

(3)依据度量函数MS，确定图像IL、IR间对应聚类簇；

(4)找到图像IL、IR间对应聚类簇后，依据对应簇内特征点坐标，构建其SIFT描述子，并采用最近邻次近邻原则输出特征匹配结果，得到匹配数M；

3.5 复杂度分析

特征匹配算法KN_DB主要包括3个主要步骤：K近邻计算，类DBSCAN的聚类簇生成，查找对应簇并匹配。其中，为方便表述，SD1,2内的数据总数均为N。

对于某次K近邻计算，它需要为SD中的每个样本，通过KD树，查找K个最近邻的邻居，其时间复杂度接近O(NlogN)。

而聚类簇生成，首先需要确定核心点，划分区域，并构造核心队列，然后，遍历核心队列，开始延展聚类，生成聚类簇，它的时间复杂度近似为O(NK)。

在最后查找对应簇并匹配中，其时间复杂度近似为O(N/K)2。因此，本文算法总的时间复杂度约为O(NK)+O(NlogN)+O(N/K)2。

4 实验结果

为了验证算法KN_DB的精确性与鲁棒性，采用Oxford VGG标准数据集(Paris、Wall、Leuven)、中科院三维重建数据集[21]为对象进行验证。实验环境为：Windows 10操作系统，英特尔Core i7-8750H @ 2.20 GHz 六核处理器，8 G内存。采用Matlab编程语言，计算机视觉库Opencv3.4.5。

4.1 聚类效果

以Oxford VGG Paris标准数据集为对象，提取SIFT关键点，分别实现KD、DBSCAN[17]、Kmeans[20]算法，聚类参数分别设置为：①KD：δ=5，K=10；②DBSCAN：δ=5，MinPts=15；③Kmeans：K=9。聚类效果如图1所示。

图1 聚类效果

从图1可以看出：KD聚类算法，基于核心点的KNN邻域信息，划分3种区域，并逐层约束，可以有效且准确的将图像区域内各对象限制在其本身范围，即对象内，数据分布均匀，对象间，边界界限清晰。DBSCAN聚类算法，仅基于固定参数δ与MinPts，标定核心点，进行聚类。此种方式，固化邻域信息，无法动态反映数据间分布，在图1显示效果为，仅能生成部分聚类簇，无法标定对象整体区域。Kmeans聚类算法，预先输入K值，仅依据欧式距离，通过迭代质心，来划分类别。此种方式在图1聚类效果为，不同对象被划分成一类。

4.2 参数设置

KD聚类算法主要有两个参数：半径δ与参数K。而不同的参数取值下，聚类效果见表1。其中，表1中簇内距离表示为当前参数取值下，各簇簇内距离D的均值。

表1 聚类效果分布

从表1可以看出，随着参数K与半径δ取值逐渐增大，邻域信息逐渐拓展，聚类簇数目逐渐减少，而簇内距离逐渐增大。在实际匹配中，因图像内对象数目相对有限，针对不同图像，选择能较好表示图像中各对象数目的K值与δ值就成为影响KD算法性能的一个关键因素。

经多次实验，针对像素大小为500*300的图像，K值确定方式为式(9)，N为SD中特征点的数目，且N*0.05所得数值向下取整

(9)

半径δ确定方式为式(10)，此时，依据定义2，求出各个特征点的最大半径Dmax，然后，从这些最大半径中，找出最大与最小，再进行计算，求出半径δ

δ=0.1*(max{Dmax}-min{Dmax})+min{Dmax}

(10)

4.3 特征匹配结果与分析

(1)Oxford VGG标准数据集

为评估效果，从Oxford VGG数据集内，选取标准图像作为实验对象，采用KN_DB、GMS[6]、ORB[9]等几类特征匹配算法进行验证。其中，Oxford VGG数据集内示例图像如图2所示。

图2 数据集内图像

标准数据集匹配结果如图3所示。其中，图3(a)～图3(c)为Wall中的图片，用以验证旋转变化；图3(d)～图3(f)为Paris中的图片，用以验证尺度变化；图3(g)～图3(i)所选图片为Leuven中的图片，用以验证光照变化。图3为分别采用KN_DB、GMS、ORB等算法进行特征匹配。标准数据集匹配结果量化描述见表2。

表2 匹配数据分布

图3 匹配效果

由图3可以看出：算法KN_DB在图像发生旋转、光照变化等情况下，能通过逐层约束，稳定找到图像间各对应区域，匹配准确率较高，适用性较强。GMS算法在图像发生旋转、光照变化时，匹配效果较好，但在图像发生尺度变化时，虽能提取较多特征点，但正确匹配率较低。ORB算法在3种图像变化中，通过暴力匹配来处理图像，错误匹配率较高，匹配效果不理想。

由表2可以看出：由于ORB算法采用FAST算子检测关键点，并基于二进制描述子，进行暴力匹配，因此匹配时间最短，但正确率R最低。算法KN_DB采用SIFT算子，构建高斯尺度空间，提取特征点，所用时间较多，但基于同一对象进行匹配，效果稳定，故正确率R最高。GMS算法提取ORB基础特征点，并基于网格，依据运动平滑性，认为正确匹配点相对错误匹配点，其邻域内有较多正确匹配点，进行匹配。提取特征点数目较多，但需通过比较匹配点邻域信息进行特征统计，所以时间最多，但正确率R居中。

为了评估本文算法的有效性，以定义7，匹配正确率R为评价指标，在Oxford VGG标准数据集上进行特征匹配。经过多次实验验证，本文算法的匹配平均正确率R保持在92.85%，说明该方法在图像发生旋转、尺度等变化时，仍具有较好的鲁棒性，且从前面的实验结果可以看出，本文算法相对于近几年提出的GMS、ORB算法来说，匹配准确率较高，鲁棒性较强。

(2)中科院三维重建数据集

为验证本文算法KN_DB的鲁棒性，本节依据中科院三维重建数据集中的青城山、武当山、五台山，并采用KN_DB、SIFT+RANSAC[7]、GMS、SURF+RANSAC[8]、ORB等5种算法进行验证，实验结果如图4、图5所示。其中图4为匹配正确率分布，图5为匹配时间分布。

图4 匹配正确率分布

图5 匹配时间分布

由图4、图5可以看出，SIFT算法基于图像整体区域，提取特征，构建描述子，计算相似性，寻找对应点，所需时间最多，匹配正确率较低。而SURF算法在求主方向阶段时太过依赖局部区域像素的梯度方向，虽相对SIFT算法采用积分图加速计算，所需时间减少，但稳定性不高。本文算法虽基于SIFT描述子，但不用遍历全图，只需在两幅图像间，计算对应区域内特征相似性，减少了匹配时间，提高了匹配效率。

5 结束语

针对纹理重复、结构复杂的对象，为了提高特征匹配的精确性与鲁棒性，本文结合KNN与DBSCAN思想，提出了一种基于动态拓展的特征匹配算法KN_DB。该算法依据图像特征点间几何信息，首先构建特征点的最近邻邻域集合，来描述特征点邻域信息；其次，基于DBSCAN聚类半径，标定核心点，确定特征点拓展条件，形成特征点聚类簇；然后，从聚类簇内，采用相似度量函数进行特征匹配；最后，采用标准数据集与古建筑数据集为对象验证算法KN_DB的效率。实验结果表明，本文方法在图像发生旋转、尺度等变化时，匹配平均正确率保持在92.85%左右。然而，针对像素较大的图像，本文算法存在参数不稳定的情况，因此，下一步将结合聚类区域密度分布差异，研究参数确定模型。