基于Agast-Adaboost的图像匹配算法

徐铸业, 赵小强,2,3

(1. 兰州理工大学 电气工程与信息工程学院, 甘肃 兰州 730050; 2. 兰州理工大学 甘肃省工业过程先进控制重点实验室, 甘肃 兰州 730050; 3. 兰州理工大学 国家级电气与控制工程实验教学中心, 甘肃 兰州 730050)

图像匹配是图像处理和计算机视觉领域中的重要研究内容之一，目前已被广泛应用于目标识别[1]、三维重建[2]、图像检索[3]、图像融合[4]和医学图像分析[5]等领域.其本质是在变换空间中寻找一种或多种最优变换，使来自不同时间、不同传感器和不同视角的同一场景的两幅或多幅图像在空间上保持一致.为了寻求这种最优变换，研究者们需要在两幅图图像的全局或局部提取特定的描述符.全局特征描述符在提取时过程复杂且速度慢，而局部特征描述符提取则相对简单，同时提取速度快且对尺度、旋转及光照等因素具有良好的鲁棒性.因此，研究局部特征描述符逐渐成为学者们研究的重点和方向.

在研究局部特征描述符的过程中，Lowe等[6]在2004年首先提出了浮点型的SIFT(scale invariant feature transform)算法，通过构建图像组层，将尺度空间中的极值点作为特征点，并用梯度直方图生成128维的特征向量.虽然SIFT算法对旋转、尺度缩放及光照变化具有不变性，但128维的描述向量计算复杂，运行时间过长，很难满足实时性要求.在SIFT算法的基础上，改进的浮点型算法逐渐被提出.Ke等[7]提出的PCA-SIFT(principal component analysis-scale invariant feature transform)算法是用主元分析法代替直方图，在41×41的图像块上计算39×39×2 (x,y方向)个梯度导数，然后用PCA将生成的特征向量降维，算法能够对特征向量进行有效的降维，缩短匹配时间，但构建特征向量所需时间增加，总体的运行时间只是略低于SIFT.Bay等[8]提出的SURF(speeded up robust features)算法是将原图像的积分图像和尺度不等的箱体滤波器作卷积，通过Harr小波构建浮点型描述向量，代替SIFT中的不同尺度图像与高斯函数作卷积的过程，很大程度上减少了特征点检测时间，实时性能约是SIFT算法的2～3倍.Mair等[9]提出的AGAST算法是对FAST[10](features from accelerated segment test)算法的改进，通过判断待检测点的灰度值与周围邻域内设定阈值的大小关系来确定该检测点是否为特征点，AGAST算法虽然对检测效率有一定的提高，但该算法仍然存在对尺度变化及旋转变换敏感的问题.以上改进的浮点型算法与SIFT算法相比在性能上有所提升，但研究表明，这些改进算法在匹配精度和匹配效率上均有明显下降.

随着图像本身包含的信息以指数级的速度增加，浮点型的描述方案逐渐不适合当前高速高精度的工程应用需求.因此，许多研究人员提出利用二进制描述向量代替浮点型描述向量，通过Hamming距离代替欧氏距离，从而快速完成特征点匹配.在二进制描述符的研究过程中，Calonder等[11]提出了二进制鲁棒独立基础特征(binary robust independent elementary features,BRIEF)算法，该算法对随机选取的高斯分布点对进行比较，从而构建二进制描述符向量，且与浮点型的描述算法相比具有明显的实时性能优势.Rublee等[12]提出的ORB(oriented FAST and rotated BRIEF)算法采用改进的BRIEF算法生成二进制特征向量，然后与Hamming距离结合实现特征点的匹配，实验结果表明ORB算法相比BRIEF算法具有更好的区分性和鲁棒性.Leutenegger等[13]提出的BRISK(binary robust invariant scalable keypoints)算法，在同心圆上用AGAST算法提取特征点，然后等间隔采样并计算其距离集合，最后采用Hamming距离完成特征匹配.

以上二进制描述算法虽然在实时性上具有一定的优势，但鲁棒性和区分性与浮点型算法相比明显降低，在实际工程领域很难得到广泛应用.为此，本文提出了一种基于尺度空间金字塔与AGAST融合的局部二进制特征匹配算法(ALBFMA).通过构建高斯尺度金字塔并与AGAST融合，实现特征点的快速提取，同时使AGAST算法具备尺度不变性，然后用改进的Adaboost对特征点进行描述，从而使匹配算法具有较好的匹配效率和较高的匹配精度，同时对尺度及旋转等具有良好的鲁棒性.

1 AGAST 检测算法

AGAST算法是在FAST算法的基础上改进而来，为了进一步提高检测效率与检测速度，该算法提取足够多的像素点，并且以待检测点为圆心，半径为3个像素的Bresenham圆作为模板，将灰度值大于或小于周围邻域内阈值的待检测点视为特征点.虽然AGAST算法与FAST算法具有相似的特征点检测标准，但其对复杂图像有更好的性能，并且采用下式所示的”非较亮”与”非较暗”模式对原配置空间进行扩展:

(1)

2 ALBFMA算法

2.1 ALBFMA特征点提取

在特征点提取阶段，本文采用将AGAST算法与尺度空间理论进行融合.首先用高斯差分滤波器把图像构建成N组S层的高斯差分金字塔，然后分别在尺度空间金字塔的每层都使用AGAST特征点检测算法，如图1所示.

由于AGAST算法不具备尺度不变性，且高斯核是实现尺度变换的唯一线性核，因此本文将高斯函数与原始图像进行卷积从而得到尺度空间，图像I对应的尺度空间函数L(x,y,σ)为

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

(2)

(3)

式中:k为常数，表示相邻的尺度空间倍数.

特征点检测过程如图2所示.它由n个octave层ci和n个中间层di组成(i=0,1,…，i-1)，其中，ci是由原始图像c0降采样生成，中间层di位于ci和ci+1之间，将1.5倍的原始图像c0进行降采样得到d0，然后再对d0降采样即可得到其他内层.差分结果表明：若标记点为极值点，则记录该点的尺度空间和位置；若该点为非极值点，则将相邻两层与当前层作二次函数拟合，然后对特征空间作插值运算，并将与插值点对应的像素点的尺度空间和位置记录，则此像素点即为新的特征点.

2.2 ALBFMA特征描述符

利用改进的AGAST算法提取特征点时具有尺度及旋转不变性，且具有较高的准确率，但描述向量存在维数高且计算时间长的问题，因此本文采用改进的Adaboost算法对生成的特征向量降维.Adaboost算法[14]是由刘冲等在Boosting算法[15]的基础上提出的一种机器学习方法，它在分类时计算弱分类的权重，并没有考虑测试集中各样本的特征从而导致达不到预期的效果.因此，本文通过对测试样本集聚类，找到每个测试样本最近的样本组，并计算它们之间的相似度，然后根据各弱分类器对各样本组分类的错误率赋予其相应的权重，最后结合测试样本与各样本组的相似度并加权各弱分类器的权重来构成最终的决策分类器，从而达到降维的目的.

以下是本文提出的改进的Adaboost算法的弱分类器和决策分类器的实现过程.

输入：训练数据集

S={(x1,y1),(x2,y2),…,(xn,yn)}

初始化：S1(i)=1/N，其中i=1,2，…，n

fori=1,2,…,k其中k为迭代次数

1) 从S中有放回抽样，得到Sk；

2) 在Sk中训练出弱分类器hk；

3) 计算hk的错误率εk：

4) 对每个样本的权重归一化.

输出：弱分类器H=(h1,h2,…,hk)

在得到弱分类器后将S分为b组，各组为(b1,b2,…,bm),并用错误率计算每个弱分类器对各组的权重，如下式：

(4)

式中:abk为第i个弱分类器对第b个组分类的错误率.再通过下面两式计算第b个样本组对第i个弱分类器的权重vbi以及整体权重Vbk：

(5)

(6)

计算第j个样本到第c个样本组的距离djc和相似度ljc：

式中：xjθ为第j个样本的第θ个属性值；bcθ为第c个样本组的第θ个属性值.然后通过下式可得第j个样本相应的第i个弱分类器的权重：

(9)

最后对多个弱分类器加权，得到决策分类器H(X)：

(10)

2.3 ALBFMA算法收敛性分析

ALBFMA算法在弱分类器的实现过程中采用迭代采样的实现方式，在Adaboost算法训练过程中，其收敛性通常是由最终决策分类器的错误率是否有界来进行判断.由Adaboost算法的弱分类器实现过程可知，迭代次数为k，且弱分类器hk的错误率为

则由Freund[16]提出的理论可知,对任意的Adaboost算法，若每次迭代生成的弱分类器的错误率分别为ε1,ε2,…，εk，则最终的决策分类器的训练错误率ε有上界，且终止条件为

(11)

由此可知，本文所提算法是收敛的.

3 实验分析

为了验证本文算法在复杂应用场景中的有效性，将Oxford dataset[17]标准测试图像集中的2幅图像Img1和Img2作为待匹配图像和参考图像，然后对2幅图像分别用SIFT算法、FAST算法、 BRISK算法和本文算法进行匹配实验，匹配结果如图3和表1所示.

由图3和表1可以看出，SIFT算法在两幅图像中都能检测出较多的特征点，但匹配点数要少于BRISK和本文算法；FAST算法的特征点的检测个数和匹配点数都逊色于SIFT算法、BRISK算法和本文算法；BRISK算法检测出的特征点个数少于SIFT和本文算法，但其匹配点数多于SIFT算法；本文算法的特征点检测个数和匹配点数都优于SIFT、FAST、BRISK算法，从而可以体现出本文算法在复杂应用场景下的有效性.

表1 四种算法匹配点数对比

为了进一步验证所提算法的有效性，将本文算法与SIFT算法、FAST算法以及BRISK算法作了一系列实验对比.实验同样采用来自于Oxford dataset的标准测试图像集，本文选择数据包bikes、Leuven、UBC、boat四组图像的第1张和第4张图像作为参考图像和待匹配图像，分别选择模糊变换(bikes)、光照变换(Leuven)、JPEG压缩(UBC)、尺度变换和旋转变换(boat)测试四种算法在不同条件的性能.仿真硬件环境为CPU Intel(R) Core(TM) i5-2430M 2.40 GHz、RAM 8GB、MATLAB R2014a和64位Windows10 SP1.

图4是本文所选四种图像变换的测试图像，为进一步评估上述四种算法在四种图像变换下的匹配性能，采用文献[17]的查准率(recall)和查错率(1-性能优越的匹配算法可以在匹配率高的同时找出更多的匹配点,而且具有更高的正确匹配率，即在查错率相同的情况下，查准率越高算法匹配性能越优越.

precision)作为评估标准：

图5为四种算法在图像发生模糊变换时的匹配结果.从图中可以看出,随着查错率的不断增加，本文算法和BRISK算法表现出良好的匹配性能，而SIFT 算法和FAST算法则对模糊变换相对敏感，这是由于SIFT和FAST算法采用易受环境影响的浮点型描述符，而本文算法和BRISK算法采用更加稳定的二进制描述符，从而对模糊变换体现出更好的鲁棒性.

四种算法在图像发生光照变换时的匹配结果如图6所示.从图中可以看出,当给图像加上不同强度的光源后，本文算法性能最佳，受光照影响最小.这是由于本文算法对生成的描述符作了归一化处理，从而使其对光照变换具有更好的不变性.

四种算法在发生JPEG压缩变换时的匹配结果如图7所示.从图中可以看出,本文算法对JPEG压缩变换性能优于SIFT算法、FAST算法和BRISK算法，且随着查错率的增加，本文算法和BRISK算法查准率逐渐接近，由此可知本文算法和BRISK算法对JPEG压缩变换都具有良好的鲁棒性.

四种算法对尺度和旋转变换的匹配结果如图8所示.从图中可以看出,本文算法对尺度和旋转具有良好的鲁棒性，这是由于本文算法在特征点提取阶段对AGAST算法进行改进，使其与尺度空间理论融合，从而具有较好的尺度和旋转不变性.

4 结语

针对传统浮点型特征描述算法误匹配率高、匹配率低的问题，本文提出一种新的图像匹配算法ALBFMA，将尺度空间理论与AGAST融合，使AGAST具有尺度不变性，然后用改进的Adaboost生成二进制特征向量，从而提高算法的匹配精度和匹配效率.经实验验证，本文算法和SIFT、FAST、 BRISK算法相比具有匹配率高的优势，同时对模糊变换、光照变换和尺度变换具有良好的鲁棒性.