基于改进SIFT和RANSAC的物体特征提取和匹配的研究
张春林 陈劲杰
摘 要：使用基于RANSAC提纯的改进SIFT算子和SIFT算子分别在两张不同视角的图像中提取并匹配特征点对，通过实验结果验证了基于改进的SIFT算提取特征点的准确率和匹配的精度都要比SIFT算子和Harris算子高，改进SIFT算子提取匹配出的特征点对更加的有利于目标物体的三维重建工作。
关键词：物体特征提取和识别；SIFT；RANSAC；三维重建
中图分类号：TP391 文献标识码：A
文章编号：2096-1472（2018）-11-07-03
1 引言（Introduction）
目前现有的几种常用的图像特征提取算子，例如：SUSAN算子、Harris特征提取算子、SIFT（Scale Invariant Feature Transform）特征提取匹配算子等。Harris特征提取算法则是C.Harris和J.Stephens于1998年提出的一种特征提取算子[1]。具体提取步骤：运算所有的像素点梯度，然后选取两个方向上的梯度都是最大值的点作为Harris角点。这种算子能够提前去除信息较强的角点，是一种很经典的算子。SUSAN算子和Harris算子都是基于像素级别的特征提取算子，提取出来的特征的精度并不是很高，对后面的三维重建势必会造成一定的影响。而David Lowe在总结优化了这几种算子的研究过程中，提出了一种不受图像尺度和旋转变化，甚至不受光线强度和拍摄角度变化的特征提取算子—SIFT算子[2]。所以说SIFT算子是一种比较优秀的特征提取算法。但仍然存在容易误匹配等缺点。
为此，本文提出将RANSAC算法与改进的SIFT算子结合[3]，通过实验对比其与SIFT算子及Harris的在特征提取和匹配效果。
2 基于Harris算法的角点检测（Corner detection based on Harris algorithm）
2.1 Harris特征提取
Harris角点检测算法首先计算所有像素的梯度，随后选取两个方向都是最大梯度的点，并以此作为Harris的角点[4]。图像内的角点就是指目标物体的轮廓上曲率的局部极大值，它是通过目标物体曲率较大的区域或者两条、多条边缘的角点所构成的，位于不同图像亮区域的交界线上。Harris的角点检测器公式如下：
如果大于某个阈值，而且成为相邻区域最大值的时候，我们就能判断这个点为角点。其中阈值的选取依靠场景实际图像的尺寸、纹理和对比度等。选取阈值的步骤是：通过确定图像中最大数量的特征点来选取灰度值最大的一些像素点作为特征点。再依据所有灰度值的排列序号，选取前个特征点，然后对特征点进行加权重心化。并且为了降低噪声对角点选取的影响，我们可以先用高斯平滑对图像进行处理。
其中，和分别是在灰度图像中的点处u和v两个方向上的偏微分。则是二阶的混合偏导。X和Y为一阶偏导，可以分别的运用微分算法在u和v方向与灰度图像进行卷积处理得到。
2.2 Harris角点匹配
归一化互相关是一种非常经典的匹配算法，并且它具有一定的抗噪声性能，而且比较容易实现。但是它的计算量比较大，对于试验计算和分析来看，这种匹配算法的运行速度太慢，需要进一步的优化。两张图像之间的匹配就是比较两者之间的相似度，同理，我们应用在图像的特征点匹配也是这样的，具体就是把特征点作为中心，进而比较模板之间的相似程度。
3 基于SIFT的物体特征提取与匹配（Object feature extraction and matching based on SIFT）
SIFT（Scale Invariant Feature Transform）特征匹配算法是一种鲁棒性很高的局部特征描述子，运用SIFT生产的图像特征向量的性能稳定，对旋转、缩放、目标遮挡、噪声等都有良好的不变性。特征提取主要包括四个步骤：
（1） 尺度空间极值检测。
首先对图像进行高斯差分塔金字塔得到高斯差分图像，然后对高斯差分图像在多尺度范围内进行关键点检测。
通过高斯函数与原始图像的卷积可以得到图像的尺度空間。
在DoG空间进行极值检测时，需要将关键点与同一尺度的八个相邻和上下相邻尺度的9×2个点，共26个点进行比较。如果该关键点在DoG尺度空间中，本层和相邻两层的26个领域中都是最大或者最小，那么该点就可以作为图像的一个特征点。
（2） 特征点精确定位。
在得到大量图像的候选特征点之后，通过拟合三维二次函数以精确确定关键点的位置和尺度，同时去除低对比度的关键点和不稳定的边缘响应点，以增强匹配稳定性、提高抗噪声能力。
（3） 特征点方向标定。
利用图像的局部性质，运用关键点领域像素的梯度分布特性为每个关键点指定方向参数，从而保证算子具有旋转不变性。图像中某一像素（x，y）处梯度幅值可以用式（9）来表示：
通过这些大小和方向的数据，可以创建方向直方图，从而可以计算每一个关键点的主导方向。
（4） 特征描述子的生成。
特征描述子可以通过高斯窗口区域内所有点的梯度和方向唯一表征。将每一个关键点周围的16×16邻域，分割成16个4×4的子区域，然后在每一个4×4的子区域中计算生成一个8方向直方图。通过对该关键点的所有子区域都进行上述计算，可以产生一个4×4×8=128维的特征向量（SIFT描述子）。每一个关键点都可以由它的特征向量唯一确定[5]。
4 基于RANSAC和改进SIFT的特征提取匹配算法
即使运用抗干扰能力比较强的SIFT特征提取算子，在匹配时也会不可避免的出现少量错配特征点对，为了满足实验的需要，结合RANSAC算法对提出出的特征点进行提纯[6]。RANSAC算法选取大量的样本，依次评估它们的参数，并且每次也随机的选取大量的数据运算参数模型，随后对依次得出的参数进行分类，把在误差范围内的点称为内点，误差范围外的点称为外点。并且RANSAC对错误匹配率超过50%的点仍然进行分析。RANSAC算法具体步骤如下：
首先假设初始的最佳内点数有0个，随机从I对待分配的特征点对中选取四对原始的特征匹配点对，两个平面之间的投影变换矩阵参数能够依据四组点进行线性运算。
随后运算剩余下的I-4个特征点對，将它们依次通过变换矩阵获得坐标值，以及它们与对应的待匹配点间的距离。
如果它们的距离比阀值T小，那么就判断这个特征匹配点对是内点，反之就是外点。
将当前的内点数量进行比较，如果数量大于，那么当前的变换矩阵参数H是最佳的矩阵估计，并且将进行更新。
通过运算大量的随机特征点对后，选取内点数量最多，并且误差函数最小的变换矩阵参数，并用这个参数作为匹配图像之间的投影变换矩阵，通过这种变换矩阵能够提高匹配的精度。
采用RANSAC算法对匹配之后的错误匹配点对进行提纯[7]，并且还估算出了图像间的变换矩阵参数，进而明确了待匹配图像的精确特征点对。
5 实验结果与分析（Experimental results and analysis）
实验平台为VS2015+Opencv2.4.13，操作系统为Windows 10，GPU为GTX1050ti，显存为4GB。采用GPU并行计算，运用了NVIDIA提供的CUDA通用并行计算架构和cuDNN计算加速方案。
5.1 特征提取实验结果与分析
5.1.1 特征提取的实验结果
为了证明本文的物体特征提取的效果，通过两组图片进行对比分析，图片大小都是640×480，如图1（a）所示。
（1）Harris特征提取。在OpenCV中，Harris角点提取是通过cornerHarris（）函数提取角点的，将cornerHarris（）函数进行封装，获得一个检测角点类。调整阈值为70时，特征提取效果如图1（b）所示。
（2）SIFT特征提取。实验中运用OpenCV函数库中的SiftFeatureDetector类对图像进行特征检测，特征提取效果如图1（c）所示。
（3）改进SIFT特征提取。使用基于尺度、方向和距离约束来去除错误匹配点对，从特征点的匹配精度和特征匹配的数目上进行优化改良，提高了提取特征点的精度，特征提取效果的如图1（d）所示。
5.1.2 特征提取结果分析
通过图1和表1可以发现，Harris算子提取的特征点最少，改进SIFT算子提取的特征点最多，同时改进SIFT算法的特征点提取的效果分布比Harris、SIFT都均匀。
5.2 特征匹配实验结果与分析
5.2.1 特征匹配实验结果
为了验证基于改进SIFT算子的特征匹配的效果，采用两组图像来进行特征的提取与匹配实验，如图2所示。
通过实验知道，OpenCV函数库的GoodFeatureToTrack函数的qualityLevel取值0.04时，提取匹配的效果更好，本文以下的实验都把qualityLevel取值0.04。
5.2.2 特征匹配实验分析
从图2和表2可以看出，经RANSAC算法剔除错误匹配（提纯）后[8]，已经去除大量的错误匹配点，SIFT算子还存在少量的错误匹配，而基于改进的SIFT算法的特征点提取匹配基本没有了错误匹配。
6 结论（Conclusion）
通过物体特征提取和匹配实验将Harris、SIFT、改进SIFT算法进行对比，改进的SIFT算法通过RANSAC剔除错误匹配后，克服了其他两种算法的缺点，在特征提取和匹配上效果更好。
参考文献（References）
[1] 李鹏程，曾毓敏，张梦.一种改进的Harris角点检测算法[J].南京师大学报（自然科学版），2014，37（02）：49-54.
[2] 周颖.基于SIFT算法的图像特征匹配[J].现代计算机，2015（5）：63-68.
[3] 曾峦，王元钦，谭久彬.改进的SIFT特征提取和匹配算法[J].光学精密仪器，2011，19（06）：1392-1396.
[4] S.Bell，C.L.Zitnick，K.Bala，et al.Inside-outside net：Detecting objects in context with skip pooling and recurrent neural net works[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Reco}nition_2016：2874-2883.
[5] Fang Xianyong，Zhang Mingmin，Pan Zhigeng，et al.A new method of manifold mosaic for large displacement images[J].Journal of Computer Science and Technology，2006，21（2）：214-223.
[6] 锥伟群，高屹.基于改进RANSAC算法的图像拼接方法[J].科技创新与应用，2015，26（5）：21-22.
[7] Kasar T，Ramakrishnaa A G.Block-based feature detection and matching for mosaicing of camera-captured document images [C].Pros of IEEE region 10 conference.Taipei：IEEE.
[8] 周建平，杨金坤，郑宇.基于改进SIFT特征匹配的视频拼接—在倒车系统中的应用[J].企业技术开发，2011，30（22）：70-71.
作者简介：
张春林（1987-），男，硕士生.研究领域：智能制造.
陈劲杰（1969-），男，硕士，副教授.研究领域：智能制造.
摘 要：使用基于RANSAC提纯的改进SIFT算子和SIFT算子分别在两张不同视角的图像中提取并匹配特征点对，通过实验结果验证了基于改进的SIFT算提取特征点的准确率和匹配的精度都要比SIFT算子和Harris算子高，改进SIFT算子提取匹配出的特征点对更加的有利于目标物体的三维重建工作。
关键词：物体特征提取和识别；SIFT；RANSAC；三维重建
中图分类号：TP391 文献标识码：A
文章编号：2096-1472（2018）-11-07-03
1 引言（Introduction）
目前现有的几种常用的图像特征提取算子，例如：SUSAN算子、Harris特征提取算子、SIFT（Scale Invariant Feature Transform）特征提取匹配算子等。Harris特征提取算法则是C.Harris和J.Stephens于1998年提出的一种特征提取算子[1]。具体提取步骤：运算所有的像素点梯度，然后选取两个方向上的梯度都是最大值的点作为Harris角点。这种算子能够提前去除信息较强的角点，是一种很经典的算子。SUSAN算子和Harris算子都是基于像素级别的特征提取算子，提取出来的特征的精度并不是很高，对后面的三维重建势必会造成一定的影响。而David Lowe在总结优化了这几种算子的研究过程中，提出了一种不受图像尺度和旋转变化，甚至不受光线强度和拍摄角度变化的特征提取算子—SIFT算子[2]。所以说SIFT算子是一种比较优秀的特征提取算法。但仍然存在容易误匹配等缺点。
为此，本文提出将RANSAC算法与改进的SIFT算子结合[3]，通过实验对比其与SIFT算子及Harris的在特征提取和匹配效果。
2 基于Harris算法的角点检测（Corner detection based on Harris algorithm）
2.1 Harris特征提取
Harris角点检测算法首先计算所有像素的梯度，随后选取两个方向都是最大梯度的点，并以此作为Harris的角点[4]。图像内的角点就是指目标物体的轮廓上曲率的局部极大值，它是通过目标物体曲率较大的区域或者两条、多条边缘的角点所构成的，位于不同图像亮区域的交界线上。Harris的角点检测器公式如下：
如果大于某个阈值，而且成为相邻区域最大值的时候，我们就能判断这个点为角点。其中阈值的选取依靠场景实际图像的尺寸、纹理和对比度等。选取阈值的步骤是：通过确定图像中最大数量的特征点来选取灰度值最大的一些像素点作为特征点。再依据所有灰度值的排列序号，选取前个特征点，然后对特征点进行加权重心化。并且为了降低噪声对角点选取的影响，我们可以先用高斯平滑对图像进行处理。
其中，和分别是在灰度图像中的点处u和v两个方向上的偏微分。则是二阶的混合偏导。X和Y为一阶偏导，可以分别的运用微分算法在u和v方向与灰度图像进行卷积处理得到。
2.2 Harris角点匹配
归一化互相关是一种非常经典的匹配算法，并且它具有一定的抗噪声性能，而且比较容易实现。但是它的计算量比较大，对于试验计算和分析来看，这种匹配算法的运行速度太慢，需要进一步的优化。两张图像之间的匹配就是比较两者之间的相似度，同理，我们应用在图像的特征点匹配也是这样的，具体就是把特征点作为中心，进而比较模板之间的相似程度。
3 基于SIFT的物体特征提取与匹配（Object feature extraction and matching based on SIFT）
SIFT（Scale Invariant Feature Transform）特征匹配算法是一种鲁棒性很高的局部特征描述子，运用SIFT生产的图像特征向量的性能稳定，对旋转、缩放、目标遮挡、噪声等都有良好的不变性。特征提取主要包括四个步骤：
（1） 尺度空间极值检测。
首先对图像进行高斯差分塔金字塔得到高斯差分图像，然后对高斯差分图像在多尺度范围内进行关键点检测。
通过高斯函数与原始图像的卷积可以得到图像的尺度空間。
在DoG空间进行极值检测时，需要将关键点与同一尺度的八个相邻和上下相邻尺度的9×2个点，共26个点进行比较。如果该关键点在DoG尺度空间中，本层和相邻两层的26个领域中都是最大或者最小，那么该点就可以作为图像的一个特征点。
（2） 特征点精确定位。
在得到大量图像的候选特征点之后，通过拟合三维二次函数以精确确定关键点的位置和尺度，同时去除低对比度的关键点和不稳定的边缘响应点，以增强匹配稳定性、提高抗噪声能力。
（3） 特征点方向标定。
利用图像的局部性质，运用关键点领域像素的梯度分布特性为每个关键点指定方向参数，从而保证算子具有旋转不变性。图像中某一像素（x，y）处梯度幅值可以用式（9）来表示：
通过这些大小和方向的数据，可以创建方向直方图，从而可以计算每一个关键点的主导方向。
（4） 特征描述子的生成。
特征描述子可以通过高斯窗口区域内所有点的梯度和方向唯一表征。将每一个关键点周围的16×16邻域，分割成16个4×4的子区域，然后在每一个4×4的子区域中计算生成一个8方向直方图。通过对该关键点的所有子区域都进行上述计算，可以产生一个4×4×8=128维的特征向量（SIFT描述子）。每一个关键点都可以由它的特征向量唯一确定[5]。
4 基于RANSAC和改进SIFT的特征提取匹配算法
即使运用抗干扰能力比较强的SIFT特征提取算子，在匹配时也会不可避免的出现少量错配特征点对，为了满足实验的需要，结合RANSAC算法对提出出的特征点进行提纯[6]。RANSAC算法选取大量的样本，依次评估它们的参数，并且每次也随机的选取大量的数据运算参数模型，随后对依次得出的参数进行分类，把在误差范围内的点称为内点，误差范围外的点称为外点。并且RANSAC对错误匹配率超过50%的点仍然进行分析。RANSAC算法具体步骤如下：
首先假设初始的最佳内点数有0个，随机从I对待分配的特征点对中选取四对原始的特征匹配点对，两个平面之间的投影变换矩阵参数能够依据四组点进行线性运算。
随后运算剩余下的I-4个特征点對，将它们依次通过变换矩阵获得坐标值，以及它们与对应的待匹配点间的距离。
如果它们的距离比阀值T小，那么就判断这个特征匹配点对是内点，反之就是外点。
将当前的内点数量进行比较，如果数量大于，那么当前的变换矩阵参数H是最佳的矩阵估计，并且将进行更新。
通过运算大量的随机特征点对后，选取内点数量最多，并且误差函数最小的变换矩阵参数，并用这个参数作为匹配图像之间的投影变换矩阵，通过这种变换矩阵能够提高匹配的精度。
采用RANSAC算法对匹配之后的错误匹配点对进行提纯[7]，并且还估算出了图像间的变换矩阵参数，进而明确了待匹配图像的精确特征点对。
5 实验结果与分析（Experimental results and analysis）
实验平台为VS2015+Opencv2.4.13，操作系统为Windows 10，GPU为GTX1050ti，显存为4GB。采用GPU并行计算，运用了NVIDIA提供的CUDA通用并行计算架构和cuDNN计算加速方案。
5.1 特征提取实验结果与分析
5.1.1 特征提取的实验结果
为了证明本文的物体特征提取的效果，通过两组图片进行对比分析，图片大小都是640×480，如图1（a）所示。
（1）Harris特征提取。在OpenCV中，Harris角点提取是通过cornerHarris（）函数提取角点的，将cornerHarris（）函数进行封装，获得一个检测角点类。调整阈值为70时，特征提取效果如图1（b）所示。
（2）SIFT特征提取。实验中运用OpenCV函数库中的SiftFeatureDetector类对图像进行特征检测，特征提取效果如图1（c）所示。
（3）改进SIFT特征提取。使用基于尺度、方向和距离约束来去除错误匹配点对，从特征点的匹配精度和特征匹配的数目上进行优化改良，提高了提取特征点的精度，特征提取效果的如图1（d）所示。
5.1.2 特征提取结果分析
通过图1和表1可以发现，Harris算子提取的特征点最少，改进SIFT算子提取的特征点最多，同时改进SIFT算法的特征点提取的效果分布比Harris、SIFT都均匀。
5.2 特征匹配实验结果与分析
5.2.1 特征匹配实验结果
为了验证基于改进SIFT算子的特征匹配的效果，采用两组图像来进行特征的提取与匹配实验，如图2所示。
通过实验知道，OpenCV函数库的GoodFeatureToTrack函数的qualityLevel取值0.04时，提取匹配的效果更好，本文以下的实验都把qualityLevel取值0.04。
5.2.2 特征匹配实验分析
从图2和表2可以看出，经RANSAC算法剔除错误匹配（提纯）后[8]，已经去除大量的错误匹配点，SIFT算子还存在少量的错误匹配，而基于改进的SIFT算法的特征点提取匹配基本没有了错误匹配。
6 结论（Conclusion）
通过物体特征提取和匹配实验将Harris、SIFT、改进SIFT算法进行对比，改进的SIFT算法通过RANSAC剔除错误匹配后，克服了其他两种算法的缺点，在特征提取和匹配上效果更好。
参考文献（References）
[1] 李鹏程，曾毓敏，张梦.一种改进的Harris角点检测算法[J].南京师大学报（自然科学版），2014，37（02）：49-54.
[2] 周颖.基于SIFT算法的图像特征匹配[J].现代计算机，2015（5）：63-68.
[3] 曾峦，王元钦，谭久彬.改进的SIFT特征提取和匹配算法[J].光学精密仪器，2011，19（06）：1392-1396.
[4] S.Bell，C.L.Zitnick，K.Bala，et al.Inside-outside net：Detecting objects in context with skip pooling and recurrent neural net works[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Reco}nition_2016：2874-2883.
[5] Fang Xianyong，Zhang Mingmin，Pan Zhigeng，et al.A new method of manifold mosaic for large displacement images[J].Journal of Computer Science and Technology，2006，21（2）：214-223.
[6] 锥伟群，高屹.基于改进RANSAC算法的图像拼接方法[J].科技创新与应用，2015，26（5）：21-22.
[7] Kasar T，Ramakrishnaa A G.Block-based feature detection and matching for mosaicing of camera-captured document images [C].Pros of IEEE region 10 conference.Taipei：IEEE.
[8] 周建平，杨金坤，郑宇.基于改进SIFT特征匹配的视频拼接—在倒车系统中的应用[J].企业技术开发，2011，30（22）：70-71.
作者简介：
张春林（1987-），男，硕士生.研究领域：智能制造.
陈劲杰（1969-），男，硕士，副教授.研究领域：智能制造.
