基于实时局部特征描述的自然路标提取与匹配

刘天衡+石朝侠+王一璞

摘 要： 针对户外场景路标匹配中所需的局部特征抽取和匹配技术进行研究，提出了基于曲率的特征抽取和二进制特征描述相结合的方法。算法利用基于曲率算法的特征分布较合理的特性，克服了传统特征分布不均的问题，且通过二进制描述算法解决了特征匹配的实时性问题，最后通过实验对比了不同算法的有效性和实时性。结果表明，该算法能够在保证实时性的同时提取出有效的均匀特征点。

关键词： 特征匹配； 特征抽取； 路标匹配； 曲率算法

中图分类号： TN911.73?34 文献标识码： A 文章编号： 1004?373X（2015）15?0008?04

Extraction and matching of natural road sign

based on real?time local features description

LIU Tianheng1， SHI Chaoxia1， WANG Yipu2

（1. School of Computer Science and Engineering， Nanjing University of Science and Technology， Nanjing 210094， China；

2. School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080， China）

Abstract： Local features extraction and matching techniques required in outdoor scene road sign matching are studied. The method in combination with curvature based feature extraction and binary feature description is proposed. The algorithm takes the advantage of reasonable features distribution in curvature algorithm to overcome the problems of traditional features uneven distribution. The real?time problem of feature matching is resolved by binary description algorithm. The validity and real?time performance of different algorithms are compared by experiments. The experimental results show that the proposed algorithm can extract even features effectively while guaranteeing real?time performance.

Keywords： feature matching； feature extraction； road sign matching； curvature algorithm

0 引 言

定位是移动机器人最基本的功能之一，最早的定位研究成果主要是通过机器人的内部传感器，如码表、惯性仪等设施实现定位，但由于打滑、地面崎岖不平等原因造成的误差累积常常会导致定位结果不精确，不宜长时间单独导航。如果通过GPS定位或者利用我国的北斗导航系统定位，在有遮挡区域等信号不好的地方定位系统将失效，因此，人们开始逐渐采用外部传感器来辅助定位，比如红外和视觉传感器[1?2]。

视觉传感器因其丰富的环境信息如视觉、纹理、形状等备受关注，而且由计算机视觉理论可知，通过视觉系统便可准确识别出目标并判断出自身位姿。目前许多现存的方法中，大多采用人工设置路标，然后在机器人移动过程中对事先设定的人工路标进行匹配实现定位。但是随着研究工作的不断进展，人们逐渐将移动机器人的应用场景从室内转到了室外，此时许多特定情况下，人工设置路标是不现实的，所以自然路标就成为在户外条件下的首选方法。所谓自然特征就是指环境中已有的、非人工设置的、能够用以标识不同环境场景的特征对象。相对于室内大多结构化的环境，室外复杂的非结构化环境对移动机器人的定位和导航带来了相当大的挑战，同时，相对于室内，室外不断变化的光照条件和气候环境也是研究中的一大挑战。

基于视觉的自然路标需要提取其不变点，之后利用特征点匹配的方法判断和识别路标，从而实现移动机器人的定位。与GPS定位方法不同，基于特征的定位方法首先将原始的采样数据转换为相应的局部特征，在只需少量存储空间的情况下保存丰富而精确的环境信息。这类方法通常具有较好的鲁棒性，能满足相对复杂的应用，但在道路两旁有植被分布时，大多数特征点都集中于道路两旁的树木，而且提取的特征较为相似，这对后期的特征匹配和机器人定位带来了较大的影响。因此，如何剔除植被对自然路标提取的影响，将特征点尽可能均匀地分布到场景的建筑物中去，成为自然路标提取中的一大难题 [3]。

目前已有的局部特征匹配算法主要有Harris，SIFT，SURF，ORB等[4?5]，SIFT（Scale?invariant Feature Transform）算法由David Lowe在1999年提出，2004年完善总结。因其具有良好的尺度旋转不变性而受到广泛关注，但由于其运算速度较慢，影响了其在实时应用中的应用。Herbert Bay针对SIFT算法提出了改进的SURF算法[6?7]，在速度上提升了一个量级，但是在一些实时应用中此速度依旧不够。直到2011年Willowgarage提出了ORB算法[8?9]，可以满足大多数实时性应用。但是，ORB算法提取的特征点，在户外应用中，特征点分布都不够均匀，故本文采用基于曲率的算法来实现较均匀的特征点提取[10]。

1 基于曲率的特征点抽取

基于曲率的特征点抽取方法计算简单，提取出来的特征点具有旋转不变性，对噪声和亮度变化也都具有良好的鲁棒性，且特征点分布均匀，更重要的是可以提取定量的特征点。该方法主要通过灰度变化来判断是否是角点，当图像中某一点沿任意方向的微小偏移都会产生灰度的大量变化，则该点被认为是角点。设[Ix]为水平方向灰度的变化，[Iy]为竖直方向的灰度变化，那么角点就是[Ix，][Iy]变化都很大的点，而边缘则是[Ix，][Iy]中只有一个变化较大的点。设[w（x，y）]是以[（x，y）]为中心的一个滑块，当其在任意方向滑动[[u，v]]时，产生灰度变化[E（u，v）]的计算方法如下：

[E（u，v）=x，yw（x，y）I（x+u，y+v）-I（x，y）2] （1）

而后根据泰勒级数计算出一阶到[n]阶的偏导数，最终可以得到一个矩阵公式：

[M=w（x，y）I2xIxIyIxIyI2y] （2）

再根据矩阵的特征值[λ1，λ2]判断是否为角点，但实际操作中一般计算出角点响应值如下：

[R=det M-k（trace M）2] （3）

式中：[k]为系数值，一般取0.04～0.06，通过[R]来判断是否为角点，[R]若为对应的邻域的极大值就是角点所在位置。

邻域设置为[3×3]和[8×8]时基于曲率的特征点提取的效果图，如图1所示。

图1 基于曲率的特征抽取

原本的基于曲率的特征点提取算法，判断一个点是否为特征点的依据是判断计算出的[R]是否在邻域内最大，若最大则为特征点。而这里因为一个点的不确定性主要取决于较小的那个特征值，若采用行列式的特征值来判断是否为特征点的话，只需较小的一个特征值数值大于预先设置的阈值，则该点便可以被认为是一个强角点[11]，即此时：

[R=λ1， λ1<λ2λ2， λ2<λ1] （4）

若[R]大于预先给定阈值即为强角点，由于该算法对发现特征值的要求较低，可以抽取到一些不是特别明显的特征点，若实际应用中需要特征点均匀分布时，适当提高该算法的运算邻域，即可获得相对其他算法而言分布更加均匀的角点分布图，效果如图2所示。

图2 改进的曲率特征提取效果图

图2（a）和图2（b）分别为极大值抑制区域为[3×3]和[8×8]的情况，可以发现当极大值抑制区扩大为[8×8]时，特征分布已相当均匀。

2 具有旋转不变性的二进制特征描述

二进制字符串描述符，相对其他算法减少了描述符的维度，从而减少了描述和匹配的时间。该算法首先对图像进行高斯滤波以降低噪声的影响，后在图像中选择一个局部块[p，]大小为[S×S]像素，定义一个[τ]测试如下：

[τ（p；u，v）=1， p（u）

式中：[u，][v]是形如[（x，y）]的二维坐标对；[p（u），p（v）]是所在点的亮度。

由若干个[τ]测试的结果组成字符串：

[f（p）=1≤i≤n2i-1τ（p；x，y）] （6）

式中：[n]可以取128，256，512等，这里取512，其需要[5128=64 ]B的存储空间。如何有效地选取特征点对接下来的运用影响很大，经实验证明，采用服从[125S2]的高斯分布，特征向量具有较好的分辨率，同时采用Hamming距离代替传统的欧式距离判断是否匹配，匹配时只需按位进行异或操作，大大缩短了特征匹配的时间。

BRIEF运算简单且所占内存较小，比较适用于一些实时应用，但该算法同样也存在一些缺点：易受噪声影响，未考虑特征方向，不具备旋转不变性，不具备尺度不变性。

为了让该算法具有旋转不变性以减少移动机器人在抖动过程中画面旋转对匹配结果造成的影响，通过质心算法计算出各关键点的方向，如下式所示：

[Mij=xyxiyjIx，y] （7）

得到特征点的方向为：

[cx=M10M00，cy=M01M00，θ=tan-1cycx] （8）

式中：[（x，y）]为检测到兴趣点的坐标，之后将获得的[θ]以[2π30]的尺标将其量化。在位置[（xi，yi）]上对任意[n]个二进制特征集，定义一个[2×n]的矩阵：

[S=x1x2xny1y2yn] （9）

用之前得到的[θ]校正[S]得到[Sθ=SRθ，]其中：

[Rθ=cosθsinθ-sinθcosθ] （10）

根据得到的方向再提取描述子[g（p，θ）=f（p）（xiyi）∈Sθ]就具有旋转不变性了。

3 实验和结论

本实验在Win7系统下，利用vs2010和opencv2.4.10实现了基于曲率算法的特征抽取与二进制特征描述方法。实验硬件为AMD四核的A6?3420M APU 1.5 GHz，内存4 GB，显卡HD 7470M 1G。由于实现移动机器人定位所需的特征点对不多，故本文所有算法对每一幅图像检测到的特征点数设置上限为200，所使用图片采用录制视频中相近帧截屏获得，各算法实验效果如图3所示，实验数据见表1。

图3 特征匹配效果

表1 各算法实验数据

[特征提取算法＼&正确匹配率 /%＼&匹配用时 /ms＼&快速角点检测算法＼&86＼&68＼&SIFT＼&60＼&5 237＼&SURF＼&58＼&1 142＼&基于曲率的算法＼&75＼&152＼&改进基于曲率的均匀提取＼&77＼&143＼&]

从实验结果来看，SIFT和SURF所获得的特征点分布比较均匀，但是在速度上和其他算法相比，慢了很多，不适用于实时性应用，速度最快的快速角点检测算法检测出的特征点分布较为集中，无法减少树木等对特征匹配的影响。

基于曲率的算法在算法实时性和特征均匀分布特性方面得到了很好的权衡，改进的基于曲率的特征抽取方法，由于简化了运算过程，在处理时间上更短；在正确匹配率方面，两种方法相差不大，相对于原算法，本文算法分布更加均匀，减少了树木等自然路标对特征匹配造成的影响。故本文提出的算法能满足户外条件下有效地提取特征点并进行匹配的要求，且具有较好的实时性和鲁棒性。

注：本文通讯作者为石朝侠。

参考文献

[1] 徐则中，庄燕滨.移动机器人定位方法对比研究[J].系统仿真学报，2009，21（7）：1891?1896.

[2] 张浩峰，赵春霞，王晓丽，等.面向室外自然环境的移动机器人视觉仿真系统[J].系统仿真学报，2006，18（3）：701?705.

[3] 王永明，王贵锦.图像局部不变性特征与描述[M].北京：国防工业出版社，2010.

[4] LEUTENEGGER S， CHLI M， SIEGWART R Y. Brisk： binary robust invariant scalable keypoints [C]// Proceedings of 2011 IEEE International Conference on Computer Vision. [S.l.]： IEEE， 2011： 2548?2555.

[5] 廖婷婷.基于特征匹配的图像检索算法研究[D].广州：华南理工大学，2012.

[6] BAY H， ESS A， TUYTELAARS T， et al. Surf： speeded up robust features [C]// Proceedings of 2006 IEEE International Conference on Computer Vision. [S.l.]： IEEE， 2006： 346?359.

[7] 张锐娟，张建奇，杨翠.基于SURF的图像配准方法研究[J].红外与激光工程，2009（1）：160?165.

[8] RUBLEE E， RABAUD V， KONOLIGE K， et al. ORB： an efficient alternative to SIFT or SURF [C]// Proceedings of 2011 IEEE International Conference on Computer Vision. [S.l.]： IEEE， 2011： 2564?2571.

[9] 许斌锋.增强现实中ORB与KLT相结合的特征点跟踪方法研究[D].南京：南京大学，2012.

[10] HARRIS C， STEPHENS M. A combined comer and edge detector [C]// Proceedings of 1988 the 4th IEEE Alvey Vision Conference. Manchester： IEEE， 1988： 147?151.

[11] SHI Jianbo， TOMASI C. Good features to track [C]// Procee?dings of 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Champaign： IEEE， 1994： 593?600.