一种改进的图像局部不变特征提取方法

谭跃生 郑政宇 顾瑞春

一种改进的图像局部不变特征提取方法

谭跃生 郑政宇 顾瑞春

(内蒙古科技大学信息工程学院 内蒙古 包头 014010)

针对传统局部特征提取算法在提取特征点时效率不高，生成描述子需要计算主方向等问题，结合SURF算法和RGT(Radial Gradient Transform)，在精度损失尽可能小的情况下提高局部不变特征提取速度，提出一种改进的AR-SURF(加速径向SURF)算法。该方法在特征检测阶段，在定位特征点时减少构造尺度空间时所计算的响应层个数，将求取对应点响应放在定位阶段。在特征描述阶段，取消确定主方向的过程，将特征点周围区域的Haar小波响应进行RGT变换，然后将特征点周围区域划分为多个同心圆，并统计特征点周围圆形区域内的响应结果，最后利用小波响应结果得到旋转不变的特征描述子。实验结果表明，AR-SURF算法节省了时空损耗，提升了定位速度，提取效果更好，更加合适于海量图片处理。

Haar小波 径向梯度变换 旋转不变性

0 引 言

近年随着互联网的发展和海量图片处理的需要，图像局部特征提取算法的实时性的要求更加地彰显出来。以跟踪目标为例，通常目标跟踪处理的对象是实时传感器得到的一系列图像，如果不能达到规定帧处理速率便不能保证处理数据的实时性和连贯性，但是现有的图像局部特征提取领域的算法，在特征点定位和描述时需要大量的时间，不能满足需求。在一定精度下，提升提取的速度，满足海量图片的实时性检测，成为图像特征提取的研究重点。

1 相关研究

局部特征建立在尺度空间的理论基础上。一般来说，局部特征的提取分为两个步骤，即特征检测阶段和特征描述阶段。特征检测阶段通过尺度空间确定出特征点所在位置、尺度等信息。特征描述阶段则是构建一个对各种变化因素不敏感的特征描述子来描述特征点以及周围区域。利用这些特征就可以在各种因素的影响下依然很好地匹配图像。

在局部特征检测上常用检测子有Harris角点[1]、HOG(Histogram of Oriented Gradient)[2]、LoG(Laplacian of Gaussian)和DoG(Difference of Gaussian)[3]、Fast-Hessian[4]、SUSAN算子[5]等。FAST算法[6]属于计算较快的特征检测算子，应用于人脸识别，连续动作检测等方面，此算法采用检测物体边缘梯度变化，得到能够表示物体轮廓的特征点，对旋转、光照变化具有较强的鲁棒性。但是缺乏在尺度变化上的处理，使得其只能适用于特定数据集。Lowe[7]结合LoG算子和尺度空间提出了尺度不变特征变换算法SIFT(Scale Invariant Feature Transform)，特点是利用不同尺度下的图像构成尺度空间，然后利用三维非极大抑制对相邻尺度下的点筛选，得到鲁棒性强的检测算子。在尺度空间的框架下，出现了利用Harris-Laplace[8]等检测算子的类SIFT算法，相比SIFT算法上进一步提高了定位特征点的速度。典型的有2006年Bay等[9]提出的SURF算法，该算法基于Fast-Hessian和Haar小波响应，改变SIFT算法的尺度空间构建方式，并利用积分图像对卷积过程进行加速，降低在计算尺度空间时的复杂度，SURF算法能保证在旋转、亮度变化、尺度变化等条件下也有很高的鲁棒性，同时提升了速度。但是在应用时，构建尺度空间的效率依然是一个瓶颈，构建的过程具有大量不必要的重复性计算，有待进一步改进。

现有的图像局部特征描述子通过统计特征点位置周围区域的特征来描述局部区域的变化构建描述局部区域的描述子。例如SIFT算法统计方向梯度直方图，首先统计周围区域每个点的方向，得到此区域的主方向，然后参照主方向将周围区域划为16个子区，统计子区基于主方向的8个梯度方向的直方图，得到128维描述向量。SIFT描述子具有很强的抗噪声能力和匹配误差容错能力，是最经典的局部不变特征描述子。分析SIFT算法的描述过程，主方向确定保证描述子的旋转不变能力，但需计算周围区域的特征，而旋转后仍然周围区域又需要一次计算，造成算法在时空间上的浪费，很大程度上限制了算法速度的提升；描述子的构建方式影响描述过程的计算量，维数的确定影响匹配时的精度和速度，128维特征向量难以满足实时匹配的要求。多数文献针对描述子的构建过程进行改进。SURF描述子参考SIFT，利用Haar小波在特征点的尺度的响应代替梯度方向直方图，本质上和SIFT描述子相同，且效率相近。GLOH、GDOH[10]等算法利用不同的子区划分方式，减少描述子维数，而PCA-SIFT[11]算法利用主成份分析求得主要描述特征，可以将维数控制在20～40维，拥有较快的匹配速度，但是建立描述子的过程花费了大量的时间，20维的特征也造成了信息的丢失。以上方法都有一定的效果，但是对求取主方向的改进，却很少有人提出。

针对以上问题，本文提出一种改进的局部特征提取算法(AR-SURF)，包括特征点提取和特征描述两个部分的改进。通过对特征点定位阶段的过程进行改进，减少构建尺度空间时的计算量，提高定位的速度。在特征点描述阶段去掉类SIFT算法的确定主方向的过程，将特征点周围区域的Haar小波响应进行RGT[12]变换，然后利用同心圆的区域划分保证描述子的旋转不变性，最后统计得到的变换后的响应，构成描述子。实验表明，本文的特征提取算法相较SURF算法速度有很大提升，且在旋转变化、亮度变化和尺度变化下都有很好的效果。

2 基本理论

2.1 特征点检测算法

一般局部特征提取算法的特征检测阶段细分为两个部分，即建立尺度金字塔和关键点定位。需要对图像建立尺度空间，在尺度空间中，每一个金字塔中的每一层都是图像在当前尺度下与相对应尺度的高斯核函数卷积。

定义图像I的Hessian 矩阵在尺度σ时如下：

(1)

其中，Lxx(x,σ)是高斯二阶偏导数在x处与图像I的卷积。

SURF算法构造了一种9×9的盒型滤波器来近似二阶高斯滤波，计算Dxx，Dyy，Dxy；每个像素点的计算完成后，就得到一幅图像的响应图。利用不同尺寸的滤波器对同一幅图像进行滤波，得到其在不同尺度的响应图，进一步构成尺度空间。之后对尺度空间内像素采用非极大抑制，即若某个像素点的Dxx×Dyy-Dxy×Dxy的值比其相邻的的26个点大，则认为该点为特征点。最后仿照SIFT[7]利用三维二次函数精确定位，并去除边缘响应点。文献[9]证明，只要选取适当的参数，SURF算法不仅能够大大提升算法速度，而且保持了较高的准确性。实际运算中，可以利用积分图像快速求出卷积核。

2.2 特征点描述

大多数局部特征提取算法的特征点描述阶段都分为两个阶段，即确定特征区域主方向和生成特征描述子。确定主方向的目的是为了使得特征点描述子具有旋转不变性，应对图像的旋转；描述子则是统计概括出特征点周围所有点的性质，用来描述特征点及其周围点的描述因子，为之后的匹配提供依据。

以SURF为例，主方向的确定利用特征点周围区域点的Haar小波响应，具体做法为[9]：

1) 以6倍所在尺度s为半径，圈定一个圆形区域，以1s为步长，利用4s大小的Haar小波计算x，y两个方向的小波响应。得到小波响应通常还要计算以特征点为中心的高斯加权，一般取σ=2s。

2) 设置一个大小为π/3的滑动窗口，统计窗口内的响应总和，即局部方向矢量。将最长的局部方向矢量作为对该特征点的主方向。

在构建描述子阶段，以特征点为中心，沿主方向划分一个20s大小的方形区域。区域内的点分配到4×4的子区域，而后计算5×5个像素点的归一化Haar小波响应。dx,dy分别为水平和垂直方向上的Haar小波响应。最后统计每个子域的4个特征，最终得到64维的特征向量。

3 AR-SURF算法

AR-SURF改进定位过程的方法，对特征点定位进行优化加速；改进描述子构建方式，优化描述子构建速度，配合积分图像法，最终提高算法的整体运行速度。

3.1 积分图像法

积分图像是计算的某一矩阵内的像素和。积分图像法可以对图像预处理，得到图像中每一个位置x的积分响应，借助这些响应可以帮助提高Haar小波响应的计算速度。积分图IΣ(x)在位置x=(x,y)T处的定义如下：

(2)

图1 积分图像原理

如图1所示，计算矩形ABCD的响应值，只需对4个顶点的响应进行四则运算，就可以得到这幅图像中的任意一个矩形区域内的像素点的求和，并且求和算子独立于矩形区域的大小，不受矩形大小的影响。

积分图像算法的伪代码如算法1所示。

算法1：积分图像

Input：待积分图像I

Output：积分后图像Img

Begin

//得到图像的大小参数

[h,w]=size(I);

//计算积分图像

For i=1:h

For j=1:w

Im(i,j)=sum(I(1:i,1:j));

End

End

Return Im

End

3.2 特征点检测

特征检测阶段最耗费时间的环节是构建尺度空间，每个尺度空间一般要建立4～5个尺度金字塔，而每个金字塔又要包含4～5层响应。AR-SURF算法不计算尺度金字塔的首末层，仅对金字塔的中间层进行滤波，得到中间层的滤波响应如图2所示，提升了构建尺度空间的速度[4]。

图2 AR-SURF中的4×4尺度空间

为了保证检测结果的准确性，AR-SURF算法比较检测点周围26个点的响应大小。检测的原理依据式(3)-式(5)。

Det(H)=DxxDyy-ω2DxyDxy

(3)

(4)

(5)

其中Det(H)为近似的Hessian矩阵的行列式值；Dxx、Dyy和Dxy则是滤波模板对高斯函数的近似，这里可以利用积分图像对计算过程加速。Sig表示Laplace算子Dxx+Dyy的符号，主要用于区分特征点的亮暗。D定义为Fast-Hessian的特征点检测依据，最后作为采样点值存入尺度空间。如果Det(H)<0则直接赋0值；若Det(H)>0则存储Sig和Det(H)的乘积，特征点的亮暗程度可在尺度空间中得到标识。

由于没有首末两层，对于与首末两层相邻的点，AR-SURF将其比较过程分为两个阶段：

1) 如图3所示，先进行去掉首末两层的比较，即邻近首末两层的点，只比较除去首末层之后剩余的17个点，并利用非极大抑制得到初次定位的点的坐标、尺度等信息。

图3 初次定位示意图

2) 如图4所示，在初次定位后的点的位置，分别求取对应首层或者末层的相邻9个点的响应，然后比较初次定位点与这9个点的响应的大小，采取非极大抑制，判断是否为特征点。

图4 二次定位示意图

从上述过程可以看出，首末层需要的点只有之后第一次定位所得到点对应的9个点，运算量明显是小于计算所有点响应，由此AR-SURF算法可减少40%～50%的运算量。其次，AR-SURF算法的二次定位特征点严格依照式(3)-式(5)进行非极大抑制，得到的响应点的位置与同样采用这一原理的SURF相同。特征点位置计算算法如算法2所示。

算法2：特征点位置计算

Input：待处理图像I

Output：特征点ip(x,y)的集合ipts

参数：金字塔个数Octave(默认为4)、每个金字塔层数Scale(默认为4)

Begin

1.初始化尺度空间

T(x,y,Octave,Scale)=0

2.第一次滤波

每个Octave的中间两个Scale滤波，利用算法1加速

3.特征点初次定位

比较每个点在中间两层相邻的17个点的值，如果为极值，则记录该点的位置

4.第二次定位

将初次定位的特征点对应的在首层或者末层的相邻点进行滤波；

比较已知特征点与相邻首末层点的值，若是极值则保留，否则排除

5.插值精确定位

End

3.3 特征点描述

特征点描述阶段，确定主方向的过程造成整个特征点描述过程中需要要计算两次特征点周围区域的响应，对计算速度影响很大。考虑到这个问题，本文提出的AR-SURF算法把这个过程舍弃，利用旋转不变的区域划分方法和新的描述子来弥补没有主方向造成的旋转不变性丧失。

3.3.1 图像的划分

图5 图像划分方式

传统的图像划分方式基于笛卡儿坐标系对区域划分，不具备旋转不变特性。AR-SURF依据极坐标系，采用如图5所示的划分方式，将图像划分成若干个的同心圆环区域，每个圆环区域宽w，为了增强鲁棒性一般设定w为2s到4s，使每个圆环包含一定数量的像素点。圆环划分方式的特点是当图像旋转一定的角度时，每一个圆环所包含的图像像素点不变，即具有旋转不变的性质，利用这一特点就能构造旋转不变的特征描述子。

3.3.2 特征描述方法

图6 RGT旋转原理

将特征点周围划分为圆环区域，则每个区域拥有可旋转性，但是点的响应依然参考没有旋转不变性的直角坐标系，为解决这个问题，考虑将响应投影到旋转不变的极坐标系。AR-SURF算法采用基于RGT变换和Haar小波响应的特征描述方法达到旋转不变性。RGT变换的原理如图6所示。

图中圆形区域的中心点为c，p为圆周上任意一点。r和t为两个正交的单位向量，其中r表示p点径向方向的单位向量，t表示p点切向方向的单位向量。式(6)和式(7)[13]为r与t的计算公式，其中Rπ/2表示旋转π/2的旋转矩阵。

(6)

t=Rπ/2r

(7)

其中，g表示p点的梯度。将p点的梯度g投影到相互垂直的r和t两个方向，即将梯度g分解两个方向的向量之和(gTr)r+(gTt)t，得到g以r、t为基向量的坐标(gTr,gTt)。文献[14]证明了以r、t为基向量的坐标系本身具有旋转不变性，以此为基础的响应也具有旋转不变性。

Haar小波是对梯度g在x与y方向的近似，由积分图像计算得到，将Haar小波在两个方向上的响应分别分解成法向与径向的响应再合成，等同g在法向与径向两个方向的分解，即对Haar小波进行RGT运算。通过对Haar小波响应运用RGT算法，得到每个点所在位置的径向与法向的特征响应，这种响应忽略每个位置本身的方向。结合RGT所得到的特征点周围区域响应信息与环形的分区方法，得到一种新的旋转不变的特征描述子。特征描述的算法流程如算法3所示。

算法3：构建特征描述子

Input：特征点位置ip(x,y,Octave,Scale)

Output：特征描述子Descriptor

Begin

1.获取特征点周围半径12×Scale的区域iimg;

2.利用积分图像计算每个点的x与y方向的Haar响应

3.将每个点按本身对中心点的方向进行旋转，计算旋转之后的响应

4.将中心点周围按照步长为3划分为8个同心圆区域

5.每个区域计算dx、dy、abs(dx)、abs(dy)的和，得到8×4=32维特征向量

End

3.4 AR-SURF算法流程

AR-SURF算法的整体流程如算法4所示。

算法4：

Input：待提取图像I

Output：图像特征向量集Descriptor

参数：M=4 尺度空间阶数(Octave)

N=4 每阶中尺度(Scale)的数量

S 特征点定位的阀值

//计算原始图像的积分图像

Call 算法1

Return Im

//定位极值点

Call算法2

Return ipts

//生成描述子

For i=1:length(ipts)

Call 算法3

Return Descriptor(i)

End

Return Descriptor

End

4 实验及结果分析

4.1 特征点定位时间比较

特征点提取时间分为两个部分：(1) 特征点的定位时间；(2) 特征描述时间。特征点的定位时间分为四个阶段：积分图像、构建尺度空间、粗定位、插值定位。统计SURF算法和AR-SURF在四种不同大小图片中提取出特征点的时间，记录多次提取求平均时间，得到如表1所示。可以看出AR-SURF在定位速度上有很大的提升，这是因为AR-SURF保留了SURF算法的定位原理，减少构建尺度空间所需运算量，即每座金字塔中减少2层的计算，在尺度空间的构建时间上节省近一半的时间。减少的两层在后面的粗定位中，利用两次定位的方式，针对每个待确定点周围的点进行运算。相比计算整个尺度下所有点，计算待确定点周围的点所需时间大幅减少，二次定位不会影响算法整体的加速。

表1 特征点定位比较

4.2 生成描述子时间比较

生成描述子的时间比较实验采用两种算法针对四个不同大小的图片进行比较，图中的特征点是由4.1节SURF算法得到，利用AR-SURF中的描述子生成算法计算得到描述子。由表2可以看出，在生成同样个数的描述子的情况下，AR-SURF的速度提高了30%以上。这是由于AR-SURF省略通常SURF计算主方向的过程，改为对特征点周围区域的Haar响应计算RGT变换。SURF算法中对每个点都要计算两次响应值(确定主方向一次，旋转后一次)变为只需计算一次。需要注意的是计算RGT的时候因为每个点都需要得到本身的方向并旋转，不能得到理想中50%的提速。

表2 生成描述子比较

结合特征点定位和描述两个阶段，得到如图7所示，可以看出AR-SURF特征点提取的时间相较SURF提升近30%，而且对于大图片速度提升效果呈增长趋势。

图7 提取总时间比较

4.3 特征匹配效果实例

图8给出四组特征匹配结果的实例，实验数据来自文献[15]所用数据集，包括JPEG压缩、模糊变化、亮度变化、尺度和旋转变化。匹配算法依据向量的欧氏距离，计算得到最相似点与次相似点，如果两点距离比值小于阀值(一般取0.65)，则记录为匹配点。比较AR-SURF算法与SURF算法的描述子匹配效果。从图中可以看出，AR-SURF的描述子匹配效果与SURF算法相近，同样在四组图片中得到了大量正确的匹配点。实验表明AR-SURF算法同样对特征有很好的描述效果。

图8 特征匹配实例

5 结 语

本文提出一种新的局部不变的特征提取算法AR-SURF，旨在尽可能少损失精度的情况下，提高图像局部特征的提取速度。改进特征检测阶段的定位流程，在不修改特征点定位原理的情况下，将减少构建尺度空间时不必要的两层尺度，减少特征点定位的时间。在生成特征描述子阶段，创新地取消主方向确定过程，同时保证描述子的旋转不变性，加快构造速度，而更低的维数也能保证描述子匹配的速度。实验结果证明，AR-SURF相较于速度较快的SURF算法依然有明显的速度优势，在亮度变化、模糊、压缩下依然有很好的表现，在旋转与尺度综合变化不大的情况下也有很好的表现，适合应用在实时图像处理和海量图片提取。下一步工作将利用更有效的匹配机制，发挥算法的速度优势，实现对图片特征的实时提取和处理。

[1] Schmid C,Mohr R,Bauckhage C.Evaluation of interest point detectors[J].International Journal of computer vision,2000,37(2):151-172.

[2] Dalal N,Triggs B.Histograms of oriented gradients for human detection[C]//Computer Vision and Pattern Recognition,2005 CVPR,IEEE Computer Society Conference on,IEEE,2005,1:886-893.

[3] Lindeberg T.Scale-space theory:A basic tool for analyzing structures at different scales[J].Journal of applied statistics,1994,21(1-2):225-270.

[4] 韩冰,王永明,孙继银.加速的Fast Hessian多尺度斑点特征检测[J].光学精密工程,2011,19(7):1686-1694.

[5] Smith S M,Brady J M.SUSAN—a new approach to low level image processing[J].International journal of computer vision,1997,23(1):45-78.

[6] 郭莉莎,李俊山,朱英宏,等.基于多尺度FAST-9的图像快速匹配算法[J].计算机工程,2012,38(12):208-210.

[7] Lowe D G.Distinctive image features from Scale-invariant keypoints[J].International journal of computer vision,2004,60(2):91-110.

[8] Mikolajczyk K,Schmid C.Scale & affine invariant interest point detectors[J].International journal of computer vision,2004,60(1):63-86.

[9] Bay H,Ess A,Tuytelaars T,et al.Speeded-up robust features (SURF)[J].Computer vision and image understanding,2008,110(3):346-359.

[10] 杨恒,王庆.一种新的局部不变特征检测和描述算法[J].计算机学报,2010,33(5):935-944.

[11] Ke Y,Sukthankar R.PCA-SIFT:A more distinctive representation for local image descriptors[C]//Computer Vision and Pattern Recognition,2004 CVPR 2004,Proceedings of the 2004 IEEE Computer Society Conference on,IEEE,2004,2:506-513.

[12] Takacs G,Chandrasekhar V,Tsai S,et al.Rotation-invariant fast features for large-Scale recognition and real-time tracking[J].Signal Processing:Image Communication,2013,28(4):334-344.

[13] Takacs G,Chandrasekhar V,Tsai S S,et al.Fast Computation of Rotation-Invariant Image Features by an Approximate Radial Gradient Transform[J].IEEE Transactions on Image Processing,2013,22(8):2970-2982.

[14] 汤彪,左峥嵘,李明.基于旋转不变HOG特征的图像匹配算法[EB/OL].北京:中国科技论文在线[2013-01-24].http://www.paper.edu.cn/releasepaper/content/201301-1025.

[15] 李婷婷,汤进,江波,等.迭代的图变换匹配算法[J].中国图象图形学报,2014,19(5):723-729.

AN IMPROVED METHOD FOR EXTRACTING IMAGE’S LOCAL INVARIANT FEATURE

Tan Yuesheng Zheng Zhengyu Gu Ruichun

(SchoolofInformationEngineering,InnerMongoliaUniversityofScienceandTechnology,Baotou014010,InnerMongolia,China)

For some disadvantages existing in traditional local feature extraction algorithm, such as the inefficiency when extracting feature points and the need to calculate principal direction when generating descriptor, etc., we propose in this paper an improved accelerated radial SURF algorithm by combining SURF algorithm and RGT (radial gradient transform) and speeding up the process of local invariant feature extraction in the circumstance of lesser precision loss as much as possible. In the step of feature detection, the algorithm decreases the number of response layers calculated in constructing the dimension space when locating the feature points, and places the course of corresponding point calculation in localisation phase. In the step of feature description, it cancels the process of determining principal direction, and conducts RGT transformation on Haar wavelet response in surrounding regions of feature point, then divides these regions into concentric circles and counts the response results within the surrounding circle regions of feature points as well, finally it uses these wavelet responding results to obtain the rotation-invariant feature descriptors. Experimental result demonstrates that AR-SURF algorithm saves the loss of time and space, increases the speed of localisation with better extraction effect, so it is more suitable for mass images processing.

Haar wavelet Radial gradient transform Rotational invariance

2014-11-28。国家自然科学基金项目(61462069)；内蒙古自然科学基金项目(2014MS0622)；内蒙古科技大学校内基金项目(2011NCL054)。谭跃生，教授，主研领域：大规模图像数据处理与挖掘。郑政宇，硕士生。顾瑞春，讲师。

TP393

A

10.3969/j.issn.1000-386x.2016.04.044