无人驾驶车辆基于角点和斑点的特征提取算法

冯玉朋,曾庆喜,，马 杉，方 啸

(1.南京航空航天大学无人驾驶车辆研究中心，江苏南京 210016；2. 吉林大学汽车仿真与控制国家重点实验室，吉林长春 130012；3. 奇瑞汽车前瞻技术研究院，安徽芜湖 241000)

无人驾驶车辆基于角点和斑点的特征提取算法

冯玉朋1,2,曾庆喜1,2,3，马 杉1,2，方 啸3

(1.南京航空航天大学无人驾驶车辆研究中心，江苏南京 210016；2. 吉林大学汽车仿真与控制国家重点实验室，吉林长春 130012；3. 奇瑞汽车前瞻技术研究院，安徽芜湖 241000)

针对运行在计算资源有限的车载嵌入式系统中的视觉里程计算法实时性较差的问题，提出一种基于Harris和SIFT相结合的图像匹配方法——Harris-SIFT算法。在介绍了SIFT算法的基础上，给出了Harris-SIFT算法的原理：使用Harris算法提取图像中的角点作为特征候选点，再利用SIFT算法在Harris的特征候选点中进行特征点提取。通过实例用Matlab软件对算法进行了仿真，并对算法的复杂度及各种性能进行了分析。结果表明，所提出的方法在特征检测模块中降低了算法的运算量、提高了特征点提取速度。Harris-SIFT算法可用于实时视觉里程计系统中，进而可使视觉里程计在车载嵌入式导航系统上得到广泛的应用。

车辆工程；无人驾驶车辆；特征提取；SIFT；Harris；RANSAC

精准的自定位对于无人驾驶车辆导航系统是至关重要的，是确保无人驾驶车辆完成自主行为的前提。近年来，基于视觉方法设计的里程计逐渐成为智能车辆定位的重要选择。相对于传统的车载传感器，视觉传感器具有成本低、体积小等优点，且视觉传感器可以提供丰富的感知信息，既可以满足车辆的自定位要求，又能够同时为其他重要的任务提供信息，如目标检测、避障等。

图像匹配是视觉里程计的关键技术之一，是将同一场景的不同时间、不同角度、不同设备等拍摄的图片进行匹配的过程。对于行驶在未知区域中的无人驾驶车辆而言，图像匹配在实现无人驾驶车辆位姿预测方面有着广泛的应用价值。目前，一般采用的匹配方法包括基于区域匹配的方法和基于特征匹配的方法[1]。基于区域的匹配方法[2-6]是从待匹配图像的灰度值出发，通过计算两幅图像的灰度相关性来作为图像匹配的标准，其局限性在于受灰度级分布和窗口形状的影响；而基于特征的图像匹配是通过提取2幅图像重叠区域的稳定特征来进行匹配的，该方法匹配速度快，具有较高的稳定性和鲁棒性，是图像匹配较常用的一种方法。

基于特征的图像匹配方法主要分为特征检测与匹配2个关键步骤，这2个步骤的好坏将直接影响图像匹配的结果。特征检测算法可以分为2类：一类是角点检测，提取角点的方法有很多[7-9]，如Harris角点[10]、Shi-Tomasi角点等；另一类是利用图像的灰度进行检测，如基于高斯滤波的高斯差、基于拉普拉斯变换的特征点检测等。在这些特征检测算子中，Harris角点检测算法简单且不受旋转、光照、噪声的影响，具有较好的检测效果[11]，但其不具有尺度不变性，可能会导致匹配结果不准确[12]。而特征匹配最常用的是SIFT算子[13]，它是目前研究中最为稳定的特征匹配算子，具有尺度、旋转不变性，对光照变化稳定性较高，但是算法中有大量的卷积运算及直方图统计，运算复杂，难以满足系统对实时性的要求。为了减少算法计算量，提高图像匹配速度，文献[14]提出了PCA-SIFT方法利用主成分分析把高维的特征向量进行降维，但计算量并没有明显地减少。BAY等[15]和郭晓冉等[16]提出了SURF方法，该方法利用积分代替卷积运算，通过统计特征点邻域的Haar小波特征来生成64维的特征描述子，大幅提高了图像匹配的速率，但是仍具有较大的计算量。也有很多研究考虑到Harris角点检测和SIFT算法两者的优缺点，将两种方法相结合去实现图像匹配。如许佳佳等[17-18]采用多尺度Harris算子检测角点特征，使用SIFT特征描述方法进行特征描述与匹配；文献[19—20]利用Harris角点和Harris亚像素角点与SIFT算法相结合，实现特征点的快速匹配，但直接对Harris角点进行SIFT描述符描述，会造成很多错误的匹配；吕恒利等[21]通过Harris算法对SIFT特征点进行过滤，先进行Harris角点检测和SIFT特征提取，然后选取Harris角点邻域内的SIFT特征点，郭晓冉等[16]提出了一种利用Harris算法对SIFT算法进行自适应化改进的具有鲁棒性的特征点提取算法。以上两种方法提高了特征点的稳定性，却增加了算法的计算量。

本文结合Harris算法和SIFT算法各自的优缺点，提出一种利用Harris算法来简化SIFT算法的具有鲁棒性的特征点检测与匹配算法。首先利用Harris算法将图像中的角点检测出来，然后只对角点邻域进行SIFT特征提取，从而实现图像的精确匹配。

1 SIFT算法

SIFT是1999年David G Lowe提出的一种特征描述算法，在2004年Lowe在大量的研究基础上，对该算法做了更为全面的总结，正式提出一种基于尺度空间的局部特征描述符——SIFT(尺度不变特征变换)。SIFT算子具有尺度不变性、旋转不变性，对光照的变化、仿射变换、噪声等具有鲁棒性，已成为视觉领域最常用的描述符。算法步骤为构建尺度空间—尺度空间极值点检测—特征点精确定位—确定关键点方向参数—生成特征描述子。

1.1 构建尺度空间

SIFT算法是基于尺度空间来对图像进行处理的，其目的是模拟图像数据的多尺度特征。该算法是利用高斯核与原图像进行卷积，通过高斯卷积核中参数σ的变化，获得多尺度空间下的图像，实现了图像的尺度变换。

二维图像的尺度空间定义：

(1)

(2)

式中：L(x,y,σ)为图像的尺度空间；G(x,y,σ)为尺度可变高斯函数；*为卷积运算符；I(x,y)为图像函数；σ为尺度空间因子。

当完成高斯金字塔的建立后，按照式(3)建立DoG金字塔，即将高斯金字塔中相邻尺度的图像相减即可得到DoG金字塔：

(3)

图1 尺度空间极值检测Fig.1 Scale space extrema detection

1.2 尺度空间极值点检测

在DoG尺度空间检测极值点时，需要把每一个采样点与其邻域及上下层中的26点进行比较，如图1所示。当采样点的像素均大于或小于这26个点时，该点为极值点。

1.3 特征点精确定位

通过上一步检测出的极值点中包括一些低对比度点和不稳定的边缘响应点，所以需要进一步进行筛选。通过拟合三维二次函数可以去除低对比度点，一般采用的是D(x,y,σ)的泰勒展开式。但是高斯差函数在边缘部分会有相对较大的变化，这些不稳定的极值点需要剔除，极值点的主曲率通过一个2×2的Hessian矩阵H求出：

(4)

然后根据该矩阵的迹与其行列式之间的关系来去除不稳定的边缘响应点。

根据关键点周围邻域像素点的梯度方向为每一个关键点指定方向参数，使算子具有旋转不变性。关键点(x,y)处梯度的模值和方向如下：

(5)

(6)

图2 关键点周围16×16区域Fig.2 16×16 area around keypoints

其中L所用的尺度是每个关键点各自所在的尺度。在实际计算时，在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360°，其中每45°一个柱，总共8个柱，或者每10°一个柱，总共36个柱。直方图的峰值则代表了该关键点处邻域梯度的主方向，作为该关键点的方向。

1.4 生成特征描述子

以关键点为中心选取一个16×16大小的区域，如图2所示，然后把这个区域分成4×4个大小为4×4的小区域，每个小区域内计算加权梯度直方图，每个子区域直方图分为8方向，最后得到4×4×8=128维的向量，作为该点的SIFT描述子。

2 Harris-SIFT算法

2.1 研究背景

如何提高视觉里程计特征提取与匹配算法的效率，降低算法计算复杂度，是视觉里程计系统中急需解决的一个问题，也是利用视觉里程计进行实时定位的关键问题。在特征检测、提取和匹配过程中涉及到的大量的像素运算和高维的向量运算，是造成算法消耗时间长和效率较低的原因。

图3 算法流程图Fig.3 Flow chart of the algorithm

在现有的特征提取算法中，SIFT特征算法是视觉里程计研究中最为常用的一种特征提取与描述算法。通过该算法提取的特征不会因为两幅图像的尺度不同、视角不同或是旋转关系而发生变化，同时对光照的变化、仿射变换、噪声等不敏感。SIFT特征提取算法是在多尺度空间下对图像进行特征提取，其尺度空间是利用二维高斯核函数与图像进行卷积构建的，并且在关键点分配主方向和生成128维的特征描述子时有大量的直方图运算，故SIFT特征算法计算量比较大，消耗时间比较长。Harris算法利用图像的灰度变化来判断角点，没有那么大的运算量，并且几乎可以检测到所有的角点，但角点匹配困难，出错率较高。为了提高视觉里程计的实时性，就必须降低算法计算复杂度，提高特征点提取速度，在保证各种性能的前提下，尽量减少算法的计算量。基于两种算法的特点，本文提出了一种基于SIFT和Harris深度融合的特征提取算法。

2.2 算法基本原理

首先，利用Harris算法把图像中的角点检测出来，然后，在Harris角点邻域内进行SIFT特征点提取，这些特征点将同时具有Harris角点和SIFT特征点的共同特征。利用SIFT描述子的特征描述方法对提取的特征点进行描述。该算法流程图如图3所示，具体实现步骤如下。

步骤1：首先在采集的图像序列中提取Harris角点作为候选特征点。

Harris算法是以Moravec算法为基础的，其原理是以目标像素点为中心的窗口向任意方向移动，计算移动前后的灰度变化来判断像素点是否为角点。若在该像素点处，水平和垂直2个方向的变化均较大，则该像素点属于角点。计算公式如式(7)所示。

(7)

式中：w(x,y)=exp(-(x2+y2)/(2σ2)),为窗口函数，Ix,Iy分别为图像在x,y方向上的偏导数。

则图像I在(x,y)处的局部自相关函数为

(8)

Harris角点的响应函数R定义为

(9)

式中：det(M)为矩阵M的行列式，tr(M)为矩阵M的迹，k=[0.04，0.06]。采用8领域非最大值抑制(即寻找局部最大值，将非极大值点所对应的灰度值置为0)来选择那些响应度够大的点，这些点即为角点。

步骤2：根据检测到的角点的坐标选择SIFT特征点的区域，建立局部的高斯金字塔和DoG金字塔。遍历所有角点的坐标，若在一个角点的邻域内出现另一个角点，则认为它们属于同一区域，根据角点的分布情况将图像进行分块，将不含角点和面积较小(面积的大小根据在所建的DoG金字塔中检测极值时的图像层数s决定)的图像块去掉。然后利用式(1)—式(3)在选定的区域内建立局部的高斯金字塔和DoG金字塔。

步骤3：在每个角点的局部尺度空间检测极值点。将每个角点与其图像域和空间域相邻的26个像素点进行比较，如图1所示。在角点领域的DoG尺度空间中，如果一个点的像素值在本尺度以及上下两尺度的26个领域像素点的像素值中是最值(最大或最小)时，则认为该像素点是它所在尺度下图像的一个特征点。如果该角点领域的DoG尺度空间内存在特征点，则保留该尺度空间；否则，删除该尺度空间。

步骤4：为特征点分配主方向。利用式(5)和式(6)计算特征点梯度的模值和方向，然后在以特征点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向来确定特征点的主方向。

步骤5：生成特征点描述子。因为角点特征本身具有旋转不变性，所以直接以特征点为中心选取一个16×16大小的区域，然后在每个4×4的小区域内计算8方向的梯度信息，最后得到4×4×8=128维的向量，该向量作为该点的Harris-SIFT描述子。

3 仿真及分析

为了验证算法的性能，对大量的实验图像进行了测试，实验结果均较为理想。实验是在PC机上实现的，硬件环境为Intel Core i5，内存4G，软件开发环境为Windows 7操作系统，Matlab 2012b版。实验所用的3组匹配图像分别取自不同的场景，如图4所示。第1组图像大小为720×480；第2组图像大小为640×480；第3组图像大小为1 280×960。

图4 待匹配图像Fig.4 Images to be matched

首先，通过实验对比来验证本文方法在特征点检测时间上相较于现有算法的优势。分别利用Harris角点检测算法、SIFT算法、PCA-SIFT算法、SURF算法以及Harris-SIFT算法对图4中的3组图像进行特征点提取，单个特征点检测时间如表1所示。由表1可知，由于Harris算法不需要构建尺度空间和卷积运算，采用Harris算法检测特征点具有明显的时间优势；SIFT算法的运行时间最长；PCA-SIFT算法的特征提取模块与SIFT算法一样，所以其单个特征点检测所用时间和得到的特征点的数量与SIFT算法相同；而在SURF算法中，通过积分代替SIFT算法中的微分计算，减少了算法的计算量；Harris-SIFT算法特征检测时间相对SIFT算法有明显的减少。这是因为Harris-SIFT算法不需要在整幅图像中进行特征点检测，而只需要在Harris角点邻域中进行检测，所需要计算的像素点的数量大大减少，节省了一部分计算时间。

表1 单个特征点检测时间

然后，在上述实验环境下分别利用SIFT算法、PCA-SIFT算法、SURF算法和Harris-SIFT算法对图4中3组实验图像进行特征点提取与匹配，其提取特征点的数量以及匹配对数见表2和表3。通过对比表2、表3中的数据可知，采用本文方法所获得的特征点的数量比SIFT算法、PCA-SIFT算法和SURF算法得到的特征点数量要少，但也节省了匹配过程中所消耗的时间。基于Harris-SIFT的视觉里程计位姿估计模块基础矩阵的求解一般至少需要7对匹配点，这是由于可能存在误匹配点对，且匹配点对的坐标受噪声干扰也有误差。本文方法获得的正确匹配的特征点对的数量相比于其他3种算法来说较少，但足以通过由其获得的匹配点对计算得到摄像机的位姿。

表2 5种算法提取特征的数量统计

表3 不同算法的特征点匹配对数

4 结 语

根据Harris算法和SIFT算法各自的特点，提出一种基于Harris角点和SIFT相结合的图像匹配方法，先提取Harris角点，然后在角点中寻找具备SIFT特征的特征点，采用SIFT描述子对特征点进行描述，最后以少量特征点实现图像的匹配。本算法同时具备2种算法的优点，提高了特征点提取速度，并保持了良好的匹配效率，对于实时车载视觉里程计系统的开发具有一定的参考价值。未来可考虑融合其他传感器，建立组合导航系统，进一步提高视觉里程计的性能。

/References：

[1] 李昱川，田铮，刘向增. SAR图像多尺度配准的小波域最小割模型方法[J]. 电子学报，2010，38(9): 2122-2127. LI Yuchuan, TIAN Zheng, LIU Xiangzeng. A minimum-cut model method in wavelet domain for SAR image multiscale registration[J]. Acta Electronica Sinica, 2010，38(9): 2122-2127.

[2] ZHAI Bo, ZHENG Jin, LI Bo. Digital image stabilization based on adaptive motion filtering with feedback correction[J]. Journal of Multimedia Tools and Applications, 2016, 75(19): 12173-12200.

[3] SHUKLA D, JHA R K, OJHA A. Digital image stabilization using similarity transformation over constrained differential-radon warping vectors[J]. Journal of Signal Processing-Image Communication, 2016, 47: 115-130.

[4] YANG Weiping, ZHANG Zhilong, ZHANG Yan, et al. Real-time digital image stabilization based on regional field image gray projection[J]. Journal of Systems Engineering and Electronics, 2016, 27(1): 224-231.

[5] 张艳超，王芳，赵建，等. 投影特征峰匹配的快速电子稳像[J]. 光学精密工程，2015, 23(6): 1768-1773. ZHANG Yanchao, WANG Fang, ZHAO Jian,et al. Fast digital image stabilization based on characteristic peak of projection matching[J]. Optics and Precision Engineering, 2015, 23(6): 1768-1773.

[6] KIR B, KURT M, URHAN O. Local binary pattern based fast digital image stabilization[J]. Journal of Signal Processing Letters, 2015, 22(3): 341-345.

[7] RASSEM T H, KHOO B E. Performance evaluation of new colour histogram-based interest point detectors[J]. Journal of Multimedia Tools and Applications, 2015, 74(24): 11357-11398.

[8] ZIOMEK A, OSZUST M. Evaluation of interest point detectors in presence of noise[J]. Journal of Intelligent Systems and Applications, 2016, 8(3): 26-33.

[9] LANG S R, LUERSSEN M H, POWERS D M W. Automated evaluation of interest point detectors[J]. Journal of Software Innovation, 2014, 2(1): 86-105.

[10]HARRIS C, STEPHENS M. A combined corner and edge detector[C]//Proc of 4th Alvey Vision Conference. [S.l.]: [s.n.], 1988：147-151.

[11]KARTHIK O S,VARUN D, RAMASANGU H. Localized Harris-FAST interest point detector[C]//India Conference.[S.l.]:IEEE, 2016.

[12]LOWE D U. Distinctive image features from scale-invariant keypoints[J]. Journal of Computer Vision, 2004, 60(2): 91-110.

[13]KE Y, SUKTHANKAR R. PCA-SIFT: A more distinctive representation for local image description[C]//Proc of IEEE Computer Vision and Pattern Recognition Conference.[S.l.]:[s.n.], 2004: 506-513.

[14]BAY H, TUYTELAARS T, VAN-GOOL L. SURF: Speeded-up robust features(SURF)[C]//Proc of European Conference on Computer Vision.[S.l.]:[s.n.], 2006: 404-417.

[15]BAY H, ESS A, TUYTELAARS T, et al. Speeded-up robust features(SURF)[J]. Journal of Computer Vision and Image Understanding, 2008, 110(3): 346-359.

[16]郭晓冉，崔少辉. 基于局部特征点匹配的图像拼接算法[J]. 半导体光电，2014，35(1): 89-94. GUO Xiaoran, CUI Shaohui. Image mosaic approach using local feature points registration[J]. Journal of Semiconductor Optoelectronics, 2014, 35(1): 89-94.

[17]许佳佳，张叶，张赫. 基于改进Harris-SIFT算子的快速图像配准算法[J]. 电子测量与仪器学报，2015，29(1): 48-54. XU Jiajia, ZHANG Ye, ZHANG He. Fast image registration algorithm based on improved Harris-SIFT descriptor[J]. Journal of Electronic Measurement and Instrumentation, 2015, 29(1): 48-54.

[18]许佳佳. 结合Harris与SIFT算子的图像快速配准算法[J]. 中国光学，2015，8(4): 574-581. XU Jiajia. Fast image registration method based on Harris and SIFT algorithm[J]. Journal of Chinese Optics, 2015, 8(4): 574-581.

[19]HE H,CHEN X,LIU B,et al. A sub-Harris operator coupled with SIFT for fast images matching in low-altitude photogrammetry[J]. International Journal of Signal Processing, Image Processing and Pattern Recognition, 2014, 7(3): 395-406.

[20]SHARMA K, GOYAL A. Very high resolution image registration based on two step Harris-Laplace detector and SIFT descriptor[C]//International Conference on Computing.[S.l.]:[s.n.], 2013:1-5.

[21]吕恒利，尚振宏，刘辉，等. 基于Harris角点和SIFT算法的车辆图像匹配[J]. 昆明理工大学学报(自然科学版)，2015，40(1): 49-54. LYU Hengli, SHANG Zhenhong, LIU Hui, et al. Vehicle image matching based on Harris corner and SIFT algorithm[J]. Journal of Kunming University of Science and Technology(Natural Science Edition), 2015, 40(1): 49-54.

A feature extraction algorithm based on corner and spots in self-driving vehicles

FENG Yupeng1,2, ZENG Qingxi1,2,3, MA Shan1,2, FANG Xiao3

(1.Self-driving Vehicle Research Center, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu 210016, China; 2. State Key Laboratory of Automotive Simulation and Control, Jilin University, Changchun, Jilin 130012, China;3.Prospective Technology Research Institute of Chery Automobile Company Limited, Wuhu, Anhui 241000, China)

To solve the poor real-time performance problem of the visual odometry based on embedded system with limited computing resources, an image matching method based on Harris and SIFT is proposed, namely the Harris-SIFT algorithm. On the basis of the review of SIFT algorithm, the principle of Harris-SIFT algorithm is provided. First, Harris algorithm is used to extract the corners of the image as candidate feature points, and scale invariant feature transform (SIFT) features are extracted from those candidate feature points. At last, through an example, the algorithm is simulated by Matlab, then the complexity and other performance of the algorithm are analyzed. The experimental results show that the proposed method reduces the computational complexity and improves the speed of feature extraction. Harris-SIFT algorithm can be used in the real-time vision odometer system, and will bring about a wide application of visual odometry in embedded navigation system.

vehicle engineering; self-driving vehicles; feature extraction; SIFT; Harris; RANSAC

1008-1542(2017)03-0237-07

10.7535/hbkd.2017yx03004

2017-02-28；

2017-04-10；责任编辑：冯 民

国家自然科学基金(51505221)；中国博士后科学基金(YBA16027)；国家重点实验室开放基金；南京航空航天大学研究生创新基地(实验室)开放基金(kfjj20160216)

冯玉朋(1992—)，男，安徽滁州人，硕士研究生，主要从事无人驾驶车辆视觉导航系统方面的研究。

曾庆喜博士。E-mail：cheliang@nuaa.com

TP391.4

A

冯玉朋，曾庆喜，马 杉，等.无人驾驶车辆基于角点和斑点的特征提取算法[J].河北科技大学学报,2017,38(3):237-243. FENG Yupeng，ZENG Qingxi，MA Shan，et al.A feature extraction algorithm based on corner and spots in self-driving vehicles[J].Journal of Hebei University of Science and Technology,2017,38(3):237-243.