边缘分类SIFT算法

付永庆，宋宝森，吴建芳

(1.哈尔滨工程大学 水下智能机器人技术国防科技重点实验室，黑龙江 哈尔滨 150001;2.哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001)

引局部特征提取方法作为图像处理的关键技术，已被广泛地研究［1-3］.在已提出的方法中，具有代表性的方法是 Harris角点检测子［4］和 SIFT算法［5］.Harris角点检测子以图像中的拐角和梯度较大的区域作为特征，进行图像匹配，但是它对图像尺度变化特别敏感［5］.为解决该问题，David Lowe在1999 年提出 SIFT［1］，并在 2004 年将其完善［5］.虽然SIFT解决了场景部分遮挡、旋转缩放、视点变化引起的图像变形等问题，但是它仍存在诸如阈值较多且不好确定、特征描述符维数过高导致计算过于复杂等问题，故使实时应用受到限制.有学者优化了特征描述子［1，6-9］，但也同样忽视了对实时性的改进.

尽管SIFT算法已成功应用在图像全景拼接中［10］，但存在的主要问题是关键点具有很大的冗余性.根据Lowe的研究，将SIFT算法用于物体识别时，如果超过3个点能够匹配，则可以确定图像中存在目标物体［1］.而在一幅512×512像素点的图像中，SIFT可提供的关键点达1 000个左右，为了增强鲁棒性，大部分的关键点需要被滤除，也就是真正对生成描述符产生贡献的关键点仅为原有关键点的20%～50%，因此用于删除冗余关键点所需的计算成为重要的运算负荷.为了解决此问题，经过研究，发现SIFT的特征点几乎都在图像的边缘附近，基于此事实，改变了原有极值点的搜索方案.首先利用图像的几何不变矩［11］提取图像的边缘类，然后在边缘类对应的尺度空间中提取图像的关键点，由于边缘类已抛弃了生成绝大部分冗余关键点的图像区域，因此得到的关键点既符合SIFT特征点分布在边缘的特性，也极大提高了SIFT算法的运算速度.

1 标准SIFT算法

SIFT算法是一种局部特征提取方法，其算法主要由4个步骤组成:1)检测尺度空间极值点(以下称关键点);2)精确定位关键点;3)为每个关键点指定方向参数;4)生成特征点描述子.

1.1 尺度空间极值点检测

生成尺度空间:标准SIFT使用DOG算子来近似尺度归一化LOG算子，以生成尺度空间.尺度空间生成主要有2步:1)是构建图像金字塔，图像金字塔共O组，每组有S+3层，下一组的图像由上一组图像降采样得到，对每组的S+3幅图像都要进行高斯平滑;2)是由每组内部相邻图像相减得到S+2幅差分图像，O组全部完成相减后形成尺度空间.

极值点检测:每一个采样点要和它所有相邻点比较，即要与其同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点做比较，以确保在尺度空间和二维图像空间都检测到极值点.

1.2 精确定位关键点

为增强匹配稳定性、提高抗噪声能力，还需对关键点做以下3步处理:1)通过三维二次函数对像素插值以精确确定关键点的位置和尺度;2)利用门限(文献［1］中取0.03)去除低对比度的关键点;3)利用门限(文献［1］中取10)去除不稳定边缘响应的关键点(DOG算子会产生较强的边缘响应).

1.3 关键点方向分配

利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数.即在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向(梯度直方图的范围是0～360°，其中每10°一个柱，共36个柱)，直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向.

至此，图像的关键点已检测完毕，每个关键点有3个信息:位置、尺度、方向.

1.4 特征点描述子生成

利用邻域方向性信息联合的思想来构造特征描述子.即以关键点为中心取16×16的窗口，形成4×4个种子点，每个种子点对应一个4×4像素的区域，在该区域内分别计算8个方向的梯度累加值，绘制各梯度方向的方向直方图.最终由16个种子点可获得一个128维的特征描述子.

根据文献［5-7，9］介绍，SIFT 特征有以下特点:

1)对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性.

2)独特性好，信息量丰富，适用于在海量特征数据库中进行准确的匹配.

3)具有可扩展性，方便与其他形式的特征向量联合.

4)多量性，即使少数的几个物体也可以产生大量SIFT特征向量.因此用于全景拼接时，计算复杂度增加，计算效率下降.

2 改进SIFT算法

标准SIFT算法是把整个尺度空间搜索到的极值点都作为关键点，故产生冗余是很自然的事.为降低无效的计算负荷，提出一种关键点定位策略，它不是在整个尺度空间中寻找极值点，而是首先利用几何不变矩来提取图像的边缘类，然后在边缘类对应的尺度空间中搜索极值点，搜索完毕后的处理仍沿用SIFT方法，故称之为改进SIFT算法(EG-SIFT).

2.1 边缘类提取

2.1.1 边缘类的定义

边缘类定义为包含图像边缘信息区域的集合.一个说明实例如图1中斜线部分所示.

图1 图像边缘类Fig.1 Edge group of image

2.1.2 局部几何不变矩的计算

考虑到SIFT算法不便处理彩色图像的情况，同时也为降低计算的复杂度，提取彩色图像的亮度信息作为计算图像局部几何矩的灰度值，计算公式为

g(i，j)=0.3R(i，j)+0.59G(i，j)+0.11B(i，j).(1)式中:R(i，j)、G(i，j)、B(i，j)分别为图像像素对应的红、绿和蓝色分量.

为计算图像的局部几何不变矩，将宽度和高度为m×n(m，n应为2的整数倍)的图像分割成N×N(N应为2的整数倍)的子块.为使图像子块的矩具有平移、旋转和尺度不变性，本文引用HU提出的第1 个不变矩［11］，其定义如下:

式中:l∈(0，m/N)和 k∈(0，n/N)为图像子块的索引值;为图像的中心矩，定义为式中:为图像矩心的模拟坐标位置;g(i，j)为像素灰度值，p+q 为矩的阶数，mpq为图像的几何矩，定义为

2.1.3 边缘类的提取

边缘类提取的思想，是将相邻矩值跳跃较大的局部不变矩对应的图像子块作为图像的边缘类，即把图像子块看作像素，把图像的几何不变矩看作像素的灰度值，取梯度后对小于门限部分归零处理，大于门限部分对应的图像子块的集合经过调整后作为图像的边缘类.

求取梯度的公式为

求得梯度后做归零处理的公式为

式中:T为门限值，不为零的F(l，k)所对应的图像子块为图像边缘类的侯选区域.为了能相对精确地提取边缘类，还要对侯选区域进行调整.

门限T的选取对于边缘类的提取是一个很关键的因素.在实验中，如果对于所有梯度值采用同一个固定的门限T，则T大时会遗漏部分边缘区域，而T小时会出现虚假边缘区域.为了取得折中值，可依下式选择门限T:

整幅图像局部亮度值可能不在一个数量级上，故采用固定门限不可能同时区分出不同数量级的亮度跳跃.根据局部亮度信息确定门限，可区分不同数量级的亮度跳跃.

2.2 边缘类调整

在分割图像的时候，边缘区域的图像子块并不是全部正好跨在图像的边缘线上，而是大部分子块都偏移，甚至有的正好以图像边缘线作为分割线，如图2所示(网格线为分割线).如果这样的子块作为图像的边缘类区域，则会大大降低边缘类包含的边缘信息.所以要对梯度处理后保留的子块进行调整，使其尽量正好跨在图像的边缘线上，这样才能保证边缘类中包含大部分的边缘信息.

调整Fl，k的起始坐标，并使用下式作为停止条件:

不等式右端是一个可变的门限，选取方法和选择梯度门限是一样的.

图2 图像子块分割Fig.2 Sub block of image

调整后，根据图像子块几何不变矩来构造一个新的参考图像，其像素值由下式确定:

式中:fl，k(x，y)为第l列k行的图像子块内的各个像素值，x和y在一个图像子块内(N×N)取值.

经过以上两步骤，提取的图像边缘类为参考图像中不为零的区域，极值点的检测将在原图像相应区域中进行.搜索完毕极值点的后续处理过程与SIFT相同.

2.3 改进SIFT算法实现

1)提取边缘类并建立参考图象金字塔.

对图像进行子块分割，计算子块几何不变矩的梯度，用梯度超过门限的图像子块创建一幅新的边缘类参考图像.

将边缘类参考图像依次降采样，取得O幅参考图像，分别与DOG图像金字塔的O组相对应.即DOG图像金字塔的每组S+2幅图像使用同一幅参考图像.

2)建立DOG图像金字塔.

建立DOG金字塔时同标准SIFT算法相同.

3)极值点检测.

搜索极值点时，首先看当前像素对应组参考图像中的对应像素是否为零，如果为零则转向下一个像素，不为零则继续与相邻的26个像素做比较，判断当前点是否为极值点.

找出所有极值点后的处理同SIFT算法，经过“精确定位关键点”、“关键点方向分配”和“特征点描述子生成”等步骤最后形成一定数量的特征点.显然，本文提出的改进SIFT算法比标准SIFT算法节省了在所有尺度空间检测极值点的时间，同时通过改变图像子块大小(N×N)，可不同程度地减少特征点冗余.

3 改进前后SIFT算法仿真和实验

为了比较改进SIFT算法和标准SIFT算法的运算速度及特征点冗余情况，组织了以下实验验证.

实验用计算机配置为:主频 1.8 GHz，内存1GByte;仿真软件为 Microsoft visual C++6.0;利用的函数库为OpenCV.

3.1 评价方法

为了对比改进前后SIFT算法运行时间的差异，分别对同一张图片进行特征点提取，用微秒级Windows API函数记录其各自的运行时间，并记录各自特征点个数然后进行显示.为客观评价改进SIFT算法在图像拼接中消除特征点冗余的性能，利用K-D树搜索近似最近邻的方法对两幅有重叠图中的对应特征点进行匹配，并记录改进前后特征点匹配对数.

针对图像全景拼接应用，给出了图像子块大小对SIFT特征点数目的影响曲线.

3.2 实验结果

3.2.1 运行时间和特征点数目对比

对440×340像素点的彩色图像用SIFT法提取的特征点如图3(a)所示(黑色箭头线起点是特征点位置，长度代表方向模值).提取特征点315个，花费时间1 173 ms，其中建立DOG图像金字塔时间为357 ms.用改进SIFT法提取的特征点如图3(b)所示，采用的图像子块为14×14像素点，提取特征点173个，花费时间817 ms，其中提取边缘类、建立边缘类参考图像金字塔为27 ms，建立DOG图像金字塔为357 ms.

图3 改进前后SIFT算法提取特征点对比Fig.3 Feature point contrast of EG-SIFT and SIFT

3.2.2 消除冗余特征点对比

利用K-D树搜索近似最近邻法对两幅有重叠图像进行了特征点匹配，如图4所示，(a)为标准SIFT算法提取的特征点经过匹配后的图像，其中黑色线连接的是两幅图像中相对应的特征点，经过匹配后，找到41对匹配点;图4(b)为改进SIFT算法提取的特征点经过匹配后的图像，找到12对匹配点.

图4 改进前后SIFT特征点K-D树匹配的特征点对比Fig.4 Counterpart points contrast of of EG-SIFT and SIFT

3.2.3 图像子块大小和特征点数目曲线

使用图3的原图像，并从6×6到20×20更改图像子块的大小，记录提取出的特征点数，结果曲线如图5所示.

3.3 实验结果分析

由图3可见，改进SIFT的特征点要明显少于标准SIFT的特征点，由315降至173，SIFT改进前后耗时由1 173 ms降至817 ms，节省了总运行时间的30.3%.通过对描述子生成过程的跟踪，发现生成每个描述子的时间约为 2.6 ms，173个特征点需450 ms，加上DOG金字塔生成时间357 ms和边缘类参考图像生成时间27 ms，理论上耗时834 ms而实际为817 ms，节省的17 ms为在搜索关键点时直接抛弃不属于边缘类的点所得.

图5 图像子块大小和特征点数目关系曲线Fig.5 Relation of sub-block and feature points

由图4可见SIFT匹配对由改进前41对下降到12对，冗余度大大降低.根据文献［3］知，3对正确的匹配对可以完成几何关系校正矩阵参数的求解，而7对以上就可以更好的求解各参数.现在改进SIFT算法有至少12对可利用，完全可以实现图像拼接过程中的几何关系校正，且使计算复杂度和计算时间大幅度降低.

从图5可见，子块从6×6到18×18的时候，特征点的数目会少量增加，而到20×20以后呈少量下降趋势，主要是因为在18×18以下时，边缘类提取算法可以很好的提取边缘信息区域，而当子块为20×20以上时，不能正确提取边缘类造成边缘信息丢失，从而特征点数目会下降一些.通过实验，推荐子块大小在8×8到14×14之间选择.该实验中选择的子块是14×14.

4 结论

本文提出的改进SIFT算法通过引入矩不变性，建立图像边缘类，可在2个方面相对标准SIFT算法获得性能改善:

1)缩小了极值点的搜索范围，大幅度提高了SIFT算法极值点搜索速度.

2)较大幅度地减少了冗余特征点，使匹配处理时间和计算复杂性大幅度下降.

3)由于改进算法是基于边缘信息的，所以其适用于边缘信息相对丰富的图像.

后续研究将结合基于边缘类和描述子2个方面作出进一步改进，以达到真正在实时场合应用的目的.

［1］LOWE D G.Object recognition from local scale-invariant features［C］//Proceedings of the International Conference on Computer Vision.Corfu，Greece，1999:1150-1157.

［2］MIKOLAJCZYK K，SCHMID C.Scale and affine invariant interest point detectors［J］.Int＇l J Computer Vision，2004，1(60):63-86.

［3］GOOL L V，MOONS T，UNGUREANU D.Affine/photometric invariants for planar intensity patterns［C］//Proc.Fourth European Conf Computer Vision，Cambridge，England.1996:642-651.

［4］HARRIES C，STEPHENS M.A combined corner and edge detector［C］//Fourth Alvey Vision Conference.Manchester，UK，1988:147-151.

［5］LOWE D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91-110.

［6］KE Y，SUKTHANKAR R.PCA-SIFT:a more distinctive representation for local image descriptors［C］//Proc Conf Computer Vision and Pattern Recognition.Washington D.C.，USA，2004:511-517.

［7］MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis And Machine Intelligence，2005(10):1615-1630.

［8］MORENO P，BERNARDINO A.Improving the SIFT descriptor with smooth derivative filters［J］.Pattern Recognition Letters，2009，30(1):18-26.

［9］ZHOU H Y，YUAN Y，SHI C M.Object tracking using SIFT features and mean shift［J］.Computer Vision and Image Understanding，2009，113(3):345-352.

［10］BROWN M，LOWE D.Recognising panoramas［C］//Proc Ninth Int＇l Conf Computer Vision.Washington D.C.，USA，2003:1218-1227.

［11］HU M K.Visual pattern recognition by moment invariants［J］.IRE Trans Inf Theory，1962，8(2):179-187.