图像特征点匹配^[1]是计算机视觉邻域中基础而又重要的课题，广泛应用于模式识别、目标跟踪、图像拼接领域。图像特征点匹配就是在两幅图像中找出有效的匹配点对，它可以分为3个步骤：首先是从图像中检测出特征点，然后根据特征点的邻域信息描述特征点，最后在原图像和待匹配图像中计算特征点之间的对应关系。

传统的特征点检测方法有：Moravec^[2]角点检测，该方法简单但是它所检测出来的特征点不具备旋转不变性，并且对边缘点的反应比较强烈。Harris^[3]角点检测实际上是对Moravec角点检测的改进，它所检测出来的特征点具有旋转不变性，但对尺度敏感。SUSAN^[4](small univalue segment assimilating nucleus)角点检测容易受噪声的影响。

SIFT^[5](scale invariant feature transform)算子自从提出以来一直作为主流的特征点匹配算法，其所提取的特征点鲁棒性强，具有抗光照和抗几何变形的能力，非常适用于局部目标匹配，但其运算量比较大，不能很好地满足实时性。Ke等人^[6]对SIFT算法的描述子进行主成分分析，提出了PCA-SIFT算法，该算法匹配速度较快，但区分性下降。Bay等人^[7]基于简化的思想提出SURF (speeded up robust features)算法, 利用积分图以盒状滤波来近似高斯滤波缩短了计算时间。SURF算法能较好地平衡算法速度和精度，应用较为广泛，但仍无法满足实时处理的要求。

针对上述问题，提出一种实时鲁棒的图像特征点匹配算法(RRM)。首先，引入锚点，利用图像的梯度信息确定图像的边缘区域和边缘方向，然后结合边缘区域和边缘方向，找出图像中的锚点，即梯度局部最大的点。由于边缘点响应大的缘故，利用主曲率予以滤掉，剩下图像的特征点。最后，对所检测出的特征点进行二进制字符描述，利用Hamming距离结合对称匹配检验对特征点进行匹配。由于RRM能很快速的检测出图像的特征点，并充分利用其局部的特征信息进行描述，有效地解决了传统图像匹配方法的问题。

为了使检测出来的特征点具有尺度不变的特性，需要对原图像进行尺度空间操作。即在图像信息处理模型中引入一个尺度参数，通过连续变化尺度参数获得多尺度下的尺度空间序列，然后对这些序列进行尺度空间主轮廓的提取，并以所提取的主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。通过对原图像建立金字塔的方式，生成图像的尺度空间，并在每一层中执行相同的操作来提取特征点。

确定边缘区域和边缘方向^[8-9]的主要目的是找出图像潜在的边缘，而这些区域的确定可以使用微分算子如Sobel^[10]算子、Prewitt^[11]算子、Scharr^[12]算子等实现。首先，通过微分操作可以得到水平方向梯度G_x和垂直方向梯度G_y。然后，根据所得G_x和G_y确定图像的边缘区域和边缘方向。

如图 1所示，如果图像在某点处的梯度G=|G_x|+|G_y|大于阈值T，那么该点就属于边缘区域，同时，如果|G_x|>|G_y|，那么表示该点有一条垂直边缘，反之有一条水平边缘。其中，边缘方向仅是对边缘区域的像素点而言，对边缘区域外的点没有边缘方向可言。

为充分利用上面求出的边缘区域和边缘方向，定义锚点为梯度局部最大的点。根据锚点的这一性质，可以通过比较某一像素点与邻域像素点的梯度值大小来提取出图像中的锚点。例如，对边缘方向为水平的像素点，可通过比较其正上方和正下方像素点的梯度值来判断该像素点是否为锚点。具体判断锚点的流程如下：

判断(x, y)处像素点是否为锚点。

符号表示：

 (x, y)：像素点坐标；

 G:边缘区域；

 D:边缘方向；

 T_A：锚点阈值。

IsAnchor(x, y, G, D, T_A)

G[x, y]⇐Not Anchor

If D[x, y]=HORIZONTAL then

  If G[x, y]-G[x, y-1]≥T_Aand

    G[x, y]-G[x, y+1]≥T_Athen

    G[x, y]⇐Anchor

  End if

Else

// Vertical Edge

If G[x, y]-G[x-1, y]≥T_A and

  G[x, y]-G[x, y+1]≥T_A then

   G[x, y]⇐Anchor

  End if

End if

以上方法检测到的关键点含有大量的不稳定边缘响应点，为了增强匹配稳定性和提高抗噪声能力，可以通过利用主曲率与特征值的关系来进一步去除这些不稳定的响应点。获取特征点处的Hessian矩阵，即

$ \boldsymbol{H} = \left[ {\begin{array}{*{20}{c}} {{D_{xx}}}&{{D_{xy}}}\\ {{D_{xy}}}&{{D_{yy}}} \end{array}} \right] $

(1)

H的特征值α和β分别代表x和y方向的梯度，则矩阵H对角线元素之和为

$ {\rm{tr}}\left( \boldsymbol{H} \right) = {D_{xx}} + {D_{yy}} = \alpha + \beta $

矩阵H的行列式为

$ {\rm{Det}}\left( \boldsymbol{H} \right) = {D_{xx}}{D_{yy}} - {\left( {{D_{xy}}} \right)^2} = \alpha \beta $

(2)

假设α是较大的特征值，而β是较小的特征值，令α=rβ，则

$ \begin{array}{*{20}{c}} {\frac{{{\rm{tr}}\left( \boldsymbol{H} \right)}}{{{\rm{Det}}\left( \boldsymbol{H} \right)}} = \frac{{{{\left( {\alpha + \beta } \right)}^2}}}{{\alpha \beta }} = }\\ {\frac{{{{\left( {r\beta + \beta } \right)}^2}}}{{r{\beta ^2}}} = \frac{{{{\left( {r + 1} \right)}^2}}}{r}} \end{array} $

(3)

由式(3)不难看出^[1]，r值越大，说明两个特征值的比值越大，即在某一个方向的梯度值越大，而在另一个方向的梯度值越小，而边缘恰恰就是这种情况。所以为了剔除边缘响应点，需要让该比值小于一定的阈值，因此，为了检测主曲率是否在某阈值r下，只需检测

$ \frac{{{\rm{tr}}\left( \boldsymbol{H} \right)}}{{{\rm{Det}}\left( \boldsymbol{H} \right)}} < \frac{{{{\left( {r + 1} \right)}^2}}}{r} $

(4)

只需将式(4)成立的点保留即可。

为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配一个基准方向。本文特征点的方向运用Intensity Centroid^[14]来运算。以特征点为中心，在其邻域S内计算质心位置，然后以特征点为起点，质心为终点构造向量，该向量的方向即为特征点的方向。定义邻域S的矩为

$ {M_{p,q}} = \sum\limits_{\left( {x,y} \right) \in S} {{x^p}{y^q}f\left( {x,y} \right)} $

(5)

式中，f(x, y)表示图像的灰度值，则此区域质心位置为

$ C = \left( {\frac{{{M_{1,0}}}}{{{M_{0,0}}}},\frac{{{M_{0,1}}}}{{{M_{0,0}}}}} \right)\; $

(6)

因此，特征点的方向为

$ \theta = \arctan \left( {{M_{0,1}}/{M_{1,0}}} \right)\; $

(7)

SIFT和SURF方法性能优异，但它们在实时应用中就力不从心，一个主要的原因就是特征点的描述符结构较复杂，表现为：描述符的维数较多和采用浮点型的数据格式。维数多固然可以提高特征点的可区分性，但亦使匹配效率降低，另一方面采用浮点型的数据格式也必然增加了更大的内存开销。因此改进描述符的形式就成为提高特征点匹配的一个重要手段。

使用ORB^[15](an efficient alternative to SIFT or SURF)算法中的rBrief描述子来对关键点进行特征描述。rBrief(rotation-aware brief)是Brief^[16](binary robust independent elementary features)在旋转不变性能方面的改进。Brief的主要思想是：在特征点的附近随机选取若干点对，将这些点对的灰度值进行比较，组成一个二进制字符串，并将这个二进制字符串作为该特征点的特征描述子。定义S×S大小的图像邻域P的测试准则为

$ \tau \left( {p;x,y} \right) = \left\{ {\begin{array}{*{20}{c}} 1&{p\left( x \right) < p\left( y \right)}\\ 0&{p\left( x \right) \ge p\left( y \right)} \end{array}} \right.\; $

(8)

式中，p(x)是图像邻域P在x=[u, v]^T处的灰度值。选择n个(x, y)测试点对时，就唯一定义了二进制准则，这样生成的描述子即为n维的二进制码串

$ {f_n}\left( p \right) = \sum\limits_{1 \le i \le n} {{2^{i - 1}}} \tau \left( {p;{x_i},{y_i}} \right) $

(9)

式中，n可以取128、256等数值，数值不同会影响运行速度、识别率。

然而，Brief描述的特征点并不具备旋转不变性，为增强匹配的稳定性使用1.2节求得的特征点方向对其进行改进。定义一个2×n的矩阵

$ \boldsymbol{Q} = \left[ {\begin{array}{*{20}{c}} {{x_1},{x_2}, \cdots ,{x_n}}\\ {{y_1},{y_2}, \cdots ,{y_n}} \end{array}} \right] $

(10)

其中每一个(x_i, y_i)表示一个测试点对。对每一个特征点，使用其主方向θ构造出的旋转矩阵R_θ，可以得到矫正后的矩阵Q_θ=R_θQ。这样可以得到具备旋转不变性的描述子

$ {g_n}\left( {p,\theta } \right) = {f_n}\left( p \right)\left| {\left( {{x_i},{y_i}} \right) \in {\boldsymbol{Q}_\theta }} \right. $

(11)

由于生成Brief描述子的随机点对不一定具有低相关、高方差的特性，可能致使所生成的特征点描述子独特性和区分性有所下降。为解决该问题，采用贪婪算法来选取低相关性，高方差的测试点对。

由于所生成的描述子为二进制码串形式，因此使用Hamming距离对特征点匹配较为简单，只要设定好阈值便可实现匹配。鉴于对称匹配算法^[17]是一种经典的消除误匹配的方法，具有匹配精度高、可靠性高、鲁棒性强等优点；在上述基础上结合对称匹配来进一步去除误匹配点对。其基本思想^[18]描述如下：

1) 分别对图像I₁和图像I₂进行关键点检测，得到关键点数组P_I1和P_I2。

2) 对P_I1中的每一个点i在P_I2中找出对应的点j。

3) 对P_I2中的每一个点k在P_I1中找出对应的点l。

4) 如果P_I1中的点i在P_I2中的匹配点为j，且P_I2中的点j在P_I1中的匹配点为点i，则匹配成功。

使用Visual Studio 2012进行编程实现，计算机系统是Windows 7, Intel(R) Core(TM) i5-4590 CPU 3.30 GHz，8 GB内存。采用的梯度阈值T_G=36，锚点阈值T_A=8, 扫描间隔S_P=5，特征点的邻域大小为48×48像素。

为检验算法RRM的运行效率，选择图像集leuven中的前两幅图像(900×600像素)做匹配实验，并与SIFT、SURF和ORB算法进行比较。4种算法的具体用时如表 1所示。

从表 1可知，本文算法RRM整个匹配流程下来用时143.45 ms，约是SURF算法耗时的1/4，约是SIFT算法耗时的1/10，而ORB算法耗时最短为85.7 ms。ORB较本文算法快有两方面的原因：一是RRM开始找出的锚点数量多；二是RRM的匹配过程较ORB多了对称匹配检验的环节。因此，RRM较ORB稍耗时。

为了对算法RRM的性能做出准确的评估，分别与算法SIFT、SURF和ORB在尺度、旋转、光照、视角发生变化和噪声等复杂情况下进行对比实验。

尺度性能分析中以Lena图像为实验对象，4种算法的实验效果如图 2所示。算法SIFT的332对匹配点中有2对匹配错误；算法SURF的280对匹配点中有5对匹配错误；算法ORB的226对匹配点中有3对匹配错误；算法RRM的139对匹配点中没出现错误。

从实验结果来看，本文算法(RRM)和SIFT的尺度处理能力相当；算法SURF和ORB出现极少数的错配。总地来说，4种算法在尺度性能方面都表现出较强的鲁棒性。

旋转性能分析中以book图像为实验对象，4种算法的实验效果如图 3所示。算法SIFT的140对匹配点中有3对匹配错误；算法SURF的131对匹配点中有5对匹配错误；算法ORB的116对匹配点中有4对匹配错误；算法RRM的62对匹配点中有1对匹配错误。

从实验结果可以看出，本文算法在旋转性能方面占有较明显的优势，而其他3种算法在这方面能力相当，出现了极少数的错配。造成这样的原因是，本文算法较另外3种算法多了对称匹配的检验环节，这能有效地剔除不匹配点。从实验效果来看，4种算法在旋转性能方面也是表现出较强的鲁棒性。

视角性能分析以标准图像库中图像集wall的第3幅和第4幅图像为实验对象，4种算法的实验效果如图 4所示。算法SIFT的286对匹配点中没有匹配错误；算法SURF的153对匹配点中也没有匹配错误；算法ORB的168对匹配点中有2对匹配错误；算法RRM的112对匹配点中没有错误匹配。

从实验结果来看，在视角变化幅度不是很大的情况下，4种算法的视角处理能力相当，都能较好地处理视角变化带来的影响。总地来说，4种算法在视角性能方面都表现出较强的鲁棒性。

噪声性能分析以存在高斯噪声的Lena图像为实验对象，各算法的实验效果如图 5所示。算法SIFT的41对匹配点中有4对匹配错误；算法SURF的74对匹配点中有11对匹配错误；算法ORB的98对匹配点中有4对匹配错误；算法RRM的45对匹配点中没有错误匹配。

从实验结果来看，在图像存在噪声的情况下，RRM和ORB算法表现出较强的鲁棒性，接下来依次是SIFT和SURF算法。

为检验算法RRM在光照方面的稳定性，采用标准图像库进行测试。这里选取文献[19]中光照变化的图像集leuven来分析3种算法在光照变化情况下的处理能力。其中，leuven图像集包含6幅图像，以第1幅为基准，其余每幅图像的光照逐渐变暗。使用准确匹配率来衡量各算法的光照处理能力，准确匹配率表达式为

$ k = \frac{R}{N} \times 100\% $

(12)

式中，N为返回的匹配点总数，R为正确匹配点的个数。

4种算法在光照变化情况下的处理能力如图 6所示，光照变化程度越大代表光照的变化程度也越大，即越暗。

由图 6可知，算法RRM在4种算法之中对光照变化的影响表现出明显的优越性和稳定性；其余3种算法在光照变化不太明显的时候，准确匹配率还比较高，但随着光照变化程度的增大，其准确匹配率会逐渐下降。RRM之所以较SIFT、SURF和ORB对光照具有更强的鲁棒性，是因为它通过梯度局部极值检测关键点的方式不受光照变化的影响。

本文提出了一种新的图像特征点匹配算法(RRM)，通过边缘区域和边缘方向求取图像的锚点，然后使用主曲率剔除不稳定的边缘点，提高了算法匹配的稳定性和实时性。在此基础上，利用rBrief对特征点进行描述，并使用Hamming距离和对称匹配结合的方法对特征点进行匹配，提高匹配的精度。

RRM算法之所以较传统SIFT和SURF算法表现出更好的实时性，主要原因有：1) 在特征点检测方面，RRM采用一阶导数求梯度极值点的方式，而传统算法采用先滤波再找极值点的方式；2) RRM算法采用改进BRIEF的二进制字符串来描述特征点，而传统算法SIFT、SURF采用梯度方向直方图的形式来描述特征点；3) RRM采用Hamming距离来匹配特征点的方式较传统SIFT、SURF采用欧氏距离匹配特征点的方式要快，因为后者所使用的是浮点型数据。

RRM算法鲁棒性好，主要原因有：1) 利用金字塔所生成的尺度空间求出的特征点具有尺度不变性；2) 通过Intensity Centroid求出特征点的主方向，根据该方向对所有的采样点对进行旋转，再判别并生成二进制字符串，使特征点具有旋转不变性；3) 由于RRM采用Sobel算子进行梯度计算，使得所找出的特征点对光照不敏感。

与SIFT、SURF和ORB算法进行对比的实验中，本文算法在光照发生变化的情况下表现出明显的优越性和稳定性；在视角、尺度和旋转等情况下也表现出较强的健壮性。下一步的研究方向主要是将运动目标跟踪算法与本文算法结合，从而达到对特定的运动目标进行准确的跟踪。