改进Harris-SIFT算法在双目立体视觉中的应用*

刘雨婷，王晓东，2，吴建德，2，范玉刚，2，黄国勇，2

（1.昆明理工大学，云南 昆明 650500;2.云南省矿物管道输送工程技术研究中心，云南昆明 650500）

0 引言

立体匹配是三维重建中一个至关重要且最为复杂的一个环节，是近年来数字图像处理和计算机视领域备受关注的前沿方向和研究热点。根据特征空间、相似性度量、搜索空间和搜索策略的不同，已经形成了许许多多各具特色的特征匹配算法，但如何合理提取图像的特征点并对其进行高精度匹配，仍然是计算机视觉技术的一个瓶颈，至今还未完全得到解决。

近年来，相继出现了各种匹配算法，并且结合了许多数学理论和方法，继而有新的匹配算法被不断提出。比如:早期的 Moravec 检测算子、Harris 检测算子［1，2］、SUSAN 检测算子［3］和目前较新的 SIFT（scale invariant feature transform）算法［4，5］，以及PCA-SIFT 算法、SVD 匹配法、积分图像法［6］。其中，SIFT 算子［7，8］是目前最成功的局部特征提取算子，研究表明:SIFT特征点定位准确，具有很好的尺度、旋转、视角和光照不变性，优于其他局部特征提取算子。但由于SIFT提取的特征点在图像上并没有实际的物理特征即非视觉上的角点，并且SIFT计算量大、特征点多、实时性较差，难以应对于对实时性要求较高的系统，如基于双目立体视觉的实时跟踪系统。而Harris算子［9，10］只用到了灰度的一阶差分与滤波，使得计算简单，具有较好的重复性与信息量;同时，Harris算子对图像中的每一个点都计算其兴趣值，通过领域选优，使得角点分布均匀，是一种简单、有效、稳定的角点提取算法。

本文针对SIFT算法的实时性差问题，结合Harris提取角点的显著性和SIFT描述子，并由于Harris算子的尺度敏感性，提出了一种改进Harris-SIFT算法，并应用于双目立体视觉图像匹配中，实验结果表明了该方法在保持很好匹配速率时能降低算法复杂度、提高算法效率。

1 特征点提取算法

1.1 SIFT算法与分析

SIFT算法是一种基于尺度空间、图像缩放、旋转甚至仿射变换保持不变性的图像局部特征提取算法［11，12］。其算法步骤可分为以下4步:

1）检测尺度空间极值点:Lowe首先定义了用DOG算子来作用于图像得到差值图像，在差值图像的各像素点的26邻域内，若其灰度值为最大或最小，则记录此点的位置和它所在的尺度，作为候选特征点。

2）精确定位极值点:通过拟和三维二次函数以精确确定关键点的位置和尺度，同时过滤低对比度的关键点和不稳定的边缘响应点，以增强匹配稳定性、提高抗噪声能力。

3）每个关键点指定方向参数:利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。

4）关键点描述子的生成:为确保特征向量旋转不变性，先将坐标轴旋转到特征点主方向上，采用高斯圆形窗口对梯度模值进行高斯加权，以特征点为中心取16×16的窗口，将这个窗口分成4×4个子区域，每个区域通过梯度直方图统计8个方向，共产生一个包括128个特征信息的特征向量。

1.2 改进Harris算法

针对经典Harris角点检测算子对尺度比较敏感的这一缺点，以尺度空间为基础，从空间域和尺度域来确定特征点，从而使改进的检测算子具有特殊的尺度不变性，具体的就是把2个域中的极值点确定为角点，这样检测到的角点在具有合适参数的情况下能提高稳定性［13］。改进的Harris检测算子如式（1）所示

式中Ix，Iy分别为图像在x和y方向上的偏导数，σl为积分尺度，σD为微分尺度且σl=sσD，其中s为一个不大于1的常数，⊗为对函数进行卷积运算。角点的定义跟自相关矩阵M的特征值有关，当某点的M求解得到2个足够大的特征值λ1和λ2时，此点就是角点。

2 改进Harris-SIFT算法

当应用于对实时性要求较高的双目立体视觉系统时，SIFT特征提取算法主要有如下缺点:特征提取复杂度太高，计算时间太长;生成的特征点太多，影响匹配和搜索速度;SIFT特征点不能准确定位角点，大部分特征点不能反映图像的结构。所以，为了解决SIFT算法的实时性问题，可以用改进Harris特征检测算子取代SIFT中的提取算法，然后再用SIFT特征描述符来构建特征向量，从而进行特征匹配。具体步骤如下:

1）检测图像角点

首先选择方差进行高斯卷积，在每一尺度对每个角点采取局部非极大抑制法提高定位精度，得到该尺度下的粗略角点。然后对上步中每个尺度下检测出来的角点，用3×3的模板覆盖该尺度所有的角点，如存在多于一个角点，则取最大值作为角点，得到该尺度下的最终角点;接着从第2个尺度开始，核对在当前尺度下的每个角点，看其在前一尺度中是否出现过，如果没有，则保留;如果有，则剔除。最后累计从第3步得到的全部角点，就是本文算法提取出的角点。

2）确定角点的特征向量

对得到的每一个角点处，定义其梯度幅值和方向如公式（2）、式（3）所示

分别对其3×3的邻域内的9个像素点，按照上式求其梯度幅值和方向，取累加后的幅值最大的前2个方向，一个主方向，一个辅方向，再加角点自身的梯度向量，作为角点的特征向量，从而得到反映角点特征的2个方向向量和1个梯度向量。

3）生成SIFT特征描述子

在本文的实际应用中，对每个角点、梯度向量保持不变，然后分别旋转坐标轴到主方向。

如图1所示，在以角点为中心的8×8邻域内，按照上一步，得到2个32维方向向量和1个2维梯度向量。当角点的特征向量生成以后，接下来采用欧氏距离法作为向量相似的的判定。

图1 由角点邻域梯度信息生成特征点描述子Fig 1 Corner point neighborhood gradient information to generate feature point descriptor

4）特征匹配

图2显示了特征匹配的一般步骤，在前文已经进行了特征点的提取和描述，接下来对2幅图像进行匹配。

图2 特征匹配的步骤Fig 2 Feature matching step

对SIFT特征描述子进行相似度量时，采用欧氏距离作为相似性准则［14］

D越小，表明特征点对距离越“近”，相似程度越高。

匹配的过程是:对于左图像中的特征点，采用最近邻法搜索右图像中的特征点，在右图像中找到距离最近和次近的2个特征点，如果最近距离和次近距离的比值小于设定的阈值，则接受这一对匹配点。由此得到的初始匹配结果，难免存在一些误匹配点，因此，需要进一步剔除误匹配点，常采用的方法是RANSAC（随机抽样一致性算法）［15］。

3 实验结果与分析

本文在VC++6.0与Open CV平台上实现图像匹配，主要用C++语言实现了改进Harris-SIFT算法，并对本文提出的改进Harris-SIFT算法与原SIFT算法的匹配性能进行了实验分析和比较。

图3、图4和图5、图6为2组图像的匹配实验结果，可以看出:SIFT算法提取的不是角点，不能反映图像的视觉角点，而本文算法结合改进Harris和SIFT算法提取的特征点都是角点，并降低了特征提取的复杂度，大大提高了原SIFT算法的实时性，并保证了图像的正确匹配。

图3 SIFT匹配Fig 3 SIFT matching

由表1、表2匹配实验结果可知，在一定程度上，本算法解决了SIFT算法的2个问题:

1）SIFT算法要进行多次高斯卷积检测特征点，并运算高斯差分图像，从而占用大量时间。本算法在生成SIFT特征描述之前用Harris算子检测角点，而Harris算子计算量小，并去除了大量不显著特征点，同时也降低了特征描述生成阶段的计算量。因此，改进Harris-SIFT算法大大提高了实时性。

2）改进Harris-SIFT算法生成的特征点数量远少于SIFT算法，所提取的特征点即为角点，反映了图像结构，有利于正确匹配，并且减少了待匹配特征点数，从而待匹配时间缩短。

图5 SIFT匹配Fig 5 SIFT matching

图6 改进Harris-SIFT匹配Fig 6 Improved Harris-SIFT matching

表1 匹配结果统计Tab 1 Match result statistics

表2 匹配结果统计Tab 2 Match result statistics

4 结束语

SIFT算法在图像匹配中应用广泛，但应用于实时性要求较高的双目立体视觉中，该算法的复杂度较高，实时性很差，且该算法的优势很难体现出来。本文提出的改进Harris-SIFT算法，有效地集成了改进Harris特征提取算子和SIFT描述子的特性，降低了特征提取和特征匹配的复杂度，大大提高了算法的实时性。通过双目立体视觉的匹配结果可以看出:本算法有较好的实时性。

［1］唐永鹤，陶华敏.一种基于Harris算子的快速图像匹配算法［J］.武汉大学学报，2012，37（4）:406-414.

［2］王旭光，王志衡.Harris相关与特征匹配［J］.模式识别与人工智能，2009，22（4）:505-513.

［3］Smith S M，Brady M.SUSAN——A new approach to low level image processing［J］.International Journal of Computer Vision，1997，23（1）:45-78.

［4］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60（2）:91-110.

［5］Tuytelaars T，Mikolajczyk K.Local invariant feature detectors:A survey［J］.Foundations and Trends in Computer Graphics and Vision，2008，3（1）:177-280.

［6］艾海舟，兴军亮.计算机视觉——算法与应用［M］.北京:清华大学出版社，2012:332-358.

［7］唐朝伟，肖 健.全局结构化SIFT描述子在图像匹配中的应用［J］.华中科技大学学报，2012，40（1）:15-20.

［8］Mikolajczyk K，Schmid C.A performance evaluation of localdescriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）:1615-1630.

［9］高 健，黄心汉.基于Harris角点和高斯差分的特征点提取算法［J］.模式识别与人工智能，2008，21（2）:171-176.

［10］孔 军，汤心溢.多尺度特征提取的双目视觉匹配［J］.计算机工程与应用，2010，46（33）:1-4.

［11］孟 浩，程 康.基于SIFT特征点的双目视觉定位［J］.哈尔滨工程大学学报，2009，30（6）:649-652.

［12］王 民，刘伟光.基于改进SIFT特征的双目图像匹配算法［J］.计算机工程与应用，2013，49（2）:203-207.

［13］肖得胜，刘桂华.多尺度Harris角点检测的FPGA实现［J］.通信技术，2012，45（11）:85-87.

［14］邵 暖，刘 乐.基于特征匹配算法的双目视觉测距［J］.燕山大学学报，2012（1）:57-61.

［15］常 青，张 斌.基于SIFT和RANSAC的特征图像匹配方法［J］.华东理工大学学报，2012（6）:747-751.