董哲，王翾

(中国传媒大学广播电视数字化教育部工程研究中心，北京 100024)

1 简介

无人机的导航和机器人的自我定位是当今研究的热点。当无人机在低空海拔飞行的时候，因为地理原因，还有一些直接或者间接的干扰，导致使用GPS来定位受到了很大的限制。因此，当没有GPS信号的时候，UAV需要时不时的使用惯性导航来确定自己的位置，而惯性导航则经常使用陀螺仪和加速器。在一定的场合内，UAV的可以通过视觉搜索算法来完成自我定位。有很多方法可以用来解决自我定位的问题。方法主要分成两类:基于标志物的定位［7－8］和基于图像的定位［9］。在特定的场合，人工的标志物和自然的标志物可以用来估算拍摄的位置，因为这些标志物很容易被识别。然而，在其他非特定的场合［1］，标志物很难被确定。这时，就需要利用拍摄图像的特征［3］来估算自我的位置。

提取图像特征以后就需要匹配。通过将输入图像与实时捕获的图像进行匹配，可以利用匹配得到两幅图像的仿射变换矩阵，进而从矩阵中来恢复UAV的位置。到目前为止，有着诸如Harries角点检测［5］，Canny 边缘检测［2］，SIFT 算法［10］，SURF 算法［6］，等检测图像特征的方法.但是Harries角点检测，Canny 边缘检测在对旋转的图像时效果并不算很好。所以，SIFT和SURF算法比较适合用来检测图像特征点和构建描述子。而SURF算法又由于高鲁棒性和利用积分图能减少计算的复杂度成为了本文所使用的图像特征检测方法。由于图像不理想等原因，不可避免的会有一些匹配不理想的特征点，这些不理想的特征点会导致仿射矩阵的估计存在比较大的误差。为了减少这些误差，就需要使用RANSAC［4］来有效的减少估算仿射矩阵时的误差，事实证明，此方法的确有效。

流程步骤如图1所示。

图1

2 SURF

2.1 SURF 算法

在各个局部特征检测算法中，SURF算法可以使用积分图来减少运算的复杂度。积分图可以用I(i，j)来表示，是从左上角到右下角所组成矩形之内的像素的总和，积分图表达式如等式1，其中p(i'，j')代表矩形内部的像素值。

SURF算法的目的是为了寻找那些有局部特征的兴趣点，SURF使用海森矩阵在构建的多尺度空间内去寻找特征点，SURF在构建尺度空间的时候，保持原始图像不变，通过改变滤波器的大小，得到尺度空间。

SURF算法使用非极大值抑制来最终确定兴趣点。兴趣点的描述子采用64维的向量来描述，比SIFT的128维少了一半，因此会大大的加速匹配的速度。

2.2 匹配模块

图像之间的匹配对估计仿射矩阵启着关键性的作用，特征匹配就是对于输入图像的每一个兴趣点的描述子，都能在匹配图像的描述子向量空间中寻找最相似的描述子向量。在这里可以使用Laplacian标示符(海森矩阵的迹)完成一次快速的匹配，SURF在为兴趣点构建的描述子的时候，会为每一个特征点添加Laplacian标示符，只有相同Laplacian标示符的符号的特征点会被保留，符号不相同的会被抛弃，这样可以大大的减少运算量。对于剩下的特征点，使用欧氏距离来计算，欧氏距离如公式2所示，计算待匹配图像的所有兴趣点的描述子与输入图像某一兴趣点的描述子的的欧氏距离，如果最小距离与次小距离的比值小于某一阈值，则认为这两个点是准匹配的，阈值太大会导致有效匹配点减少，阈值太小会导致错误的匹配增多，在这里将阈值设置为0.7较为合适。最后，如果输入图像的兴趣点与带匹配图像的兴趣点匹配相互对应，那么就将这两个点视为一对匹配点。

3 估算仿射矩阵

输入图像和带匹配图像通过匹配点计算出来的仿射矩阵包含着丰富的位置信息。仿射矩阵反映了输入图像通过平移，旋转，缩放变成待匹配图像的一种过程。输入图像与仿射矩阵的乘积就是待匹配图像，所以，如何由输入图像和带匹配图像得到仿射矩阵就是我们要解决的问题。

3.1 仿射矩阵模型

假设(X，Y)是输入图像的兴趣点的坐标，(x，y)与对应兴趣点的匹配点的坐标，对于每一个点，则仿射矩阵模型可以描述为

对于图像的所有兴趣点，仿射矩阵应满足下列等式

只需要三对点我们就可以求出一个仿射矩阵，因为匹配点有若干对，所以我们可以求出很多的仿射矩阵，而仿射矩阵彼此之间可能存在较为大的误差，如何求出误差最小的仿射矩阵就是以下要解决的问题。

3.2 估算仿射矩阵

利用图像的匹配点来进行矩阵估算可以有以下选择，线性方法和鲁棒算法，图像之间的匹配较为理想的时候，也就是对应点的特征一致性比较强，那么线性算法［11］，比如最小二乘法是一个不错的选择，因为线性算法足够快，计算效率也比较高，但是由于图像的成像质量不理想，拍摄的角度问题，以及光线的影响，以及匹配算法的不确定性，导致图像之间的匹配准确率下降，造成了一定数量的错误的匹配点，使用这些错误的匹配点计算出来的仿射矩阵会与真实的仿射矩阵有比较大的误差，由于线性算法对于噪声和错误匹配非常敏感，导致估计出来的矩阵十分不理想，使用这样的矩阵得到的位置信息也就会有比较大的偏差。要想在有着较多误差的匹配点中来计算出相对准确的仿射矩阵，就要想法找到符合大多数匹配点的仿射矩阵，如果存在这样一个矩阵，如果一定的兴趣点能通过这个矩阵计算出来匹配点都与真正的匹配点在可控的误差范围内，可以使用欧氏距离来评估，这样每一个特征匹配可以求出一个归一化的估计误差，最终得到一个估计误差向量［11］，根据估计误差向量确定一个误差阈值，估计误差向量中低于这个阈值的对应的特征匹配为合理的匹配。并且符合矩阵的兴趣点多于不符合矩阵的兴趣点的话，就可以认为这样的仿射矩阵是合理的。不断地寻找可以匹配更多兴趣点的仿射矩阵，最后就可以确定下来一个相对准确的仿射矩阵了。这样的算法叫做鲁棒性算法，最常见的鲁棒性算法是RANSAC算法。

此流程如图2所示。

图2

RANSAC算法的步骤如下所示。

步骤一:对输入图像和待匹配图像完成配准，记录下来匹配点的坐标

步骤二:估算仿射模型，选取三对兴趣点来计算出来一个仿射矩阵

步骤三:对于输入图像的所有兴趣点，使用仿射矩阵完成仿射变换，计算出对应的坐标，计算这些坐标和已知兴趣点匹配点的坐标的欧氏距离，得到归一化后的误差向量。

步骤四:判断误差向量和阈值之间的关系，由此确定是否保留这个仿射模型

步骤五:统计符合条件的兴趣点的个数，如果足够多，即认为仿射矩阵时合理的

最后，不断地重复步骤二到步骤五，总是保留符合条件兴趣点最多的一个，最终得到我们想要的仿射矩阵。

4 实验结果与分析

输入的参考图像

待匹配的图像

两幅图像之间真实的仿射变换矩阵是:

测试几种阈值下的匹配结果

海森阈值 欧氏距离阈值 RANSAC阈值288 0.18 8.7

图5

海森阈值 欧氏距离阈值 RANSAC阈值632 0.28 8.7

图6

海森阈值 欧氏距离阈值 RANSAC阈值460 0.45 8.7

图7

经过多次实验，得到了较为丰富的特征点和仿射矩阵

设真实的仿射矩阵为

计算出来的仿射矩阵

计算两者之间的误差距离

可见误差距离相当小，当误差距离比较大的时候，就需要使用不同的阈值多次计算，直到找到符合条件的误差距离。

最后可以根据仿射矩阵恢复位置参数，根据仿射矩阵模型

得到了旋转，缩放，和平移的位置参数，cosθ=0.8，λx=λy=0.5，x0=59，y0=18。

5 结论

在本文中，我们首先回顾了SURF匹配算法，我们使用SURF来计算两幅图像之间的位置关系，在计算仿射变换的时候主要会遇到两个问题，提高匹配的准确度以及如何减少估算仿射矩阵的误差，在这里使用了拉普拉斯算子预匹配以及相互确认匹配的验证的方法来提高匹配的准确度，使用RANSAC算法来减少仿射矩阵的误差，剔除匹配不准确的点，还要调整匹配过程中的各种阈值达到满意的效果，如何较为精准的确定阈值是我们以后要解决的问题。实验结果证明，我们计算出来的仿射矩阵误差较小，能够较为精准的恢复出两幅图像的位置关系。

［1］Robertson D，Cipolla R.An image－ based system forurban navigation［C］.BMVC，2004.

［2］Canny J.A computational approach to edge detection［J］.IEEE PAMI，1986，8(6).

［3］Murillo A C，Guerrero J J，Sagues C.SURF features for efficient robot localization with omnidirectional images［C］.IEEE International Conference on Robotics and Automation，2007:3901 －3907.

［4］Fischler M，Bolles R.Random sample consensus:a paradigm for model fitting with application to image analysis and automated cartography［J］.Commun ACM，1981，24(6):381 －395.

［5］Olague Gustavo，Hernandez，Benjamin.A new accurate and flexible model based multi－corner detector for measurement and recognition［J］.Pattern Recognition Letters，2005，26(1)，27 －41.

［6］Bay H，Ess A，Tuytelaars T，et al.Speeded －up robust features(SURF)［J］.Computer Vision and Image Understanding，2008，7(3):346 －359.

［7］Caballero F，Merino L，Ferruz J，Ollero A.Vision －Based Odometry and SLAM for Medium and High Altitude Flying UAVs［J］.J of Intelligent and Robotic Systems，2009，54(1 －3):137 －161.

［8］Bryson M，Sukkarieh S.Building a Robust Implementation of Bearing－only Inertial SLAM for a UAV［J］.J of Field Robotics，2007，24(1 － 2):113－143.

［9］Tola E，Lepetit V，Fua P.DAISY:An efficient dense descriptor applied to wide baseline stereo［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(5):815 －830.

［10］Lowe D G.Object recognition from local scale －invariant features［C］.Proceedings of the Seventh IEEE International Conference on Computer Vision，Los Alamitos，CA，USA，1999:1150 －7.

［11］甄艳，刘学军，王美珍 .一种改进 RANSAC的基础矩阵估计方法［J］.测绘通报，2014，(4):39－43.