SURF算法在小尺寸图像拼接中参数配置的优化

周宇浩崴，应忍冬，蒋乐天

上海交通大学电子工程系，上海 200240

SURF算法在小尺寸图像拼接中参数配置的优化

周宇浩崴，应忍冬，蒋乐天

上海交通大学电子工程系，上海 200240

1 引言

图像拼接分为直接拼接和融合技术，在目前融合技术中主要分为基于灰度信息和基于特征信息两种模式。基于特征信息的图像融合技术对图像的分辨率、旋转、平移、光照变化的敏感度较小，在处理复杂图像拼接以及图像受外界影响较大的情况下准确率较高。该技术的大致流程分为：图像中特征的选取（如特征点、边缘特征等），图像与图像之间的特征匹配，通过匹配特征建立图像与图像之间的映射变化关系，并最终生成融合后的图像。

SURF算法是2006年由Bay等人提出的基于特征信息的图像拼接算法，它的提出是针对Lowe等人提出的SIFT算法数据量大，时间复杂度高，时效性差等问题。SURF算法通过对高斯拉普拉斯算子的归一化近似来选取图像中的特征点，然后通过DoH（Determinant of Hessian）简化了SIFT算法中对特征点的描述，最后用最近邻匹配得到两幅图像中的匹配特征点，利用RANSAC和最小二乘法拟合出图像间的变换关系，获得拼接图像。SURF算法在保证了SIFT算法的鲁棒性的基础上，提高了运算效率，降低了时间复杂度，目前在实时图像拼接领域被广泛采用。

但由于SURF算法参数配置固定，对于不同应用领域并不能完全发挥出算法优秀的特性。为满足不同拼接环境对实时性与拼接准确性的个性化要求，本文针对SURF算法的三类参数提出了优化方法。这三类参数是：近似高斯拉普拉斯算子来选取特征点窗口滤波（Box Filter）方法中权值；生成描述子时，特征点子区域选取的范围；通过DoH对所选取特征点子区域内Haar小波变换的采样空间范围。基于目前主流的流媒体尺寸图像，分析研究了这三方面配置对算法性能的影响，进而提出SURF算法参数选择策略。该策略消除SURF算法参数固定的局限性，通过个性化的参数配置，在不同应用领域达到算法的最优化。

图1 对积分图像进行滤波，利用窗口滤波器近似离散化的高斯二阶偏导

2 SURF算法

（1）特征点选取

SURF算法选择了基于Hessian矩阵的检测子，将Hessian矩阵行列式的局部极值作为特征点。算法先对高斯卷积核做二次偏导数，再利用偏导数构成核卷积图像。

对图像I上的一点X(x，y)，在尺度空间σ上的Hessian矩阵表示为：

用Dxx、Dyy、Dxy代替Lxx、Lyy、Lxy，得到近似的Hessian矩阵Happrox，行列式为：

其中w为Hessian矩阵补偿误差，根据文献[1]，w一般取值为0.9。

遍历整幅图像不同尺度空间，进行非极大值抑制，对每个点的Hessian行列式的值与其周围3×3×3空间内26的值进行比较，如果该值为27个点中值最大的即确定为特征点。然后在特征点附近用三维二次函数进行拟合，以函数极值作为特征点精确位置的描述。

但是由于利用窗口滤波器近似高斯二阶导数与图像卷积后，会导致图像丢失一部分深度信息，根据文献[2]提出的方法，通过改进窗口滤波器的权值来对丢失的深度信息进行弥补。下面，将在第3章对这种改进进行分析。

（2）特征点描述

SURF算法特征点描述子确定首先以特征点为中心构造一个边长为20s（s为特征点尺度）的窗口区域，使用主方向为y轴，并将窗口区域分为4×4个子区域，每个子区域中取5×5个采样点，在每个采样点分别求X和Y方向的Haar小波响应，分别记为dx和dy。把每个子区域的dx和dy用高斯函数加权，再累积得到成描述子中的4维。而4×4个子区域里都有4维向量，因此一共得到一个4×4×4的64维向量，就是SURF算法的描述子。描述子构造过程如图2所示。

图2 SURF算法生成64维描述子

SURF算法在描述子生成中涉及到两个参数，是本文讨论的重点：第一为特征点周围子区域范围的选择，这将直接影响到SURF描述子的维数，SURF算法默认如上文所述，选取4×4的子区域，生成64维描述子。第二为在子区域内采样点范围的选择，如上文所述，SURF算法默认为在子区域选择5×5个采样点。

3 SURF算法中参数分析

实验中图像的分辨率为640×480，是目前主流流媒体如监视摄像头、网络摄像头等采用的分辨率。通过最近相邻距离以及RANSAC算法实现两幅图像匹配，从特征点选取数量、特征点匹配数量、运算时间三个方面来对算法的窗口滤波器权值的选取，描述子生成的子区域范围，即描述子维数以及子区域内采样空间的范围三方面参数进行评估。在不同的应用领域，对算法的准确性和时效性要求不同，如实时视频拼接对实时性的要求比一般静态图像要高，为保证实时性，牺牲一部分准确性也是可行的。

图3 窗口滤波器的权值的改进

3.1 窗口滤波器权值设置

根据文献[2]中所提到的SURF算法窗口滤波器卷积后会导致图像部分深度信息丢失的问题，提出丰富窗口滤波器的权值弥补损失的图像深度信息，以增加特征点选取的精确性及算法的稳定性，具体细节如图3所示，在图像上的浅灰色的区域以0.5权值标定，在中心区域以-1和+1权值标定。由于利用了积分图像，所以图像在和滤波器卷积的时间复杂度并没有增加，而利用更加细化的窗口滤波器，达到了补充图像中深度信息，精确特征点选取的目的。

用丰富后的窗口滤波器选取特征点，并与原SURF算法的结果进行对比，如图4，同时引入了特征点匹配率的概念：

图4 改进窗口滤波器权值后SURF算法特征点选取及匹配结果

特征点匹配率越大说明图像匹配的效率越高，见表1。

表1 改进窗口滤波器后算法在特征点匹配上的比较

由表1可以看出，改进窗口滤波器权值后算法在特征点选取的数量上明显少于SURF算法。这是由于丰富了窗口滤波器的权值以后，图像各像素点与滤波器卷积时得出的结果较原算法平滑，各像素点间的Hessian行列式值差距较小，故在遍历尺度空间内的点取极大值时选出的点的数量有所减少，但是特征点匹配率较高，有效特征点数目较多，说明特征点选取的准确度有所提升。

3.2 SURF特征点子区域范围选择

选取特征点以后，在生成特征点描述子的过程中，标准的SURF算法采用的是在特征点周围选取4×4的16个子区域，然后对每个子区域求取采样点的小波变换的高斯加权，形成4维向量这样整个16个子区域就构成了该特征点的64维向量，即为SURF描述子，根据文献[1]中的命名规范，称为SURF-64描述子。

针对实时图像处理领域图像尺寸小，对速度要求高的特点，本文尝试缩小特征点周围子区域选择的范围，利用3×3的9个子区域生成36维描述子对特征点进行描述。比较了SURF-36描述子和传统的SURF-64描述子在特征点匹配以及图像拼接准确性上的差异，并相对于算法速度的提高，从描述子效率的角度进行分析。

在特征点选取上，为了保证准确性，仍采用原始SURF算法提供的窗口滤波器。由于特征点选取过程不变，所以两种方法在特征点的数量上是完全一样的。为了更清楚地比较描述子的效率，引入了匹配效率的概念：匹配效率越高，算法的效率越高。

从图5以及表2中的结果可以看出，SURF-36在对640× 480级别的图像处理上，匹配成功的特征点数量与SURF-64的差异很小，而在运算速度上提升却非常显著，减少了约25%，特征点匹配率上提高了近1/3。可以看出36维描述子在对图像分辨率要求不高的情况下，完全可以代替64维描述子，而且在图像拼接的速度上有很大提高。

图5 SURF-36描述子特征点匹配结果

表2 SURF-64与SURF-36描述子比较

3.3 子区域中采样点范围选择

本文尝试在子区域中使用不同的采样范围，比较特征点匹配的准确率以及运行的速度。根据SURF算法，子区域的采样范围越大，计算出的子区域内的描述特征向量的容错性越佳，特征点描述子的鲁棒性越好。对64维描述子的SURF算法和36维描述子的SURF算法分别进行了测试，从特征点子区域采样范围3×3到12×12进行，对两幅640×480图像之间特征点匹配时间以及匹配成功的特征点的数目进行比较，并绘制了曲线，如图6所示。

图6 SURF-36和SURF-64描述子，特征点子区域采样范围的特征点匹配曲线

从图6中可以看出，随着对特征点周围子区域内采样点范围的增加，运算时间增加较为平滑，接近线性，在之后采样范围9×9每增加一级采样空间的范围，两幅图像中匹配特征点数量几乎不增加，而运算时间却增加较多，这是由于图像分辨率有限，子区域在9×9采样时已经接近极限，所以此时即使再增加采样范围，只是增加了无谓的运算量，子区域内采样点密度没有实质改变。从图中可以直观地看出5×5、6×6采样范围左右的效率较高，即图中用红色线段最长，说明匹配的数量时间比较高。在低采样范围时，SURF-36与SURF-64差异较大，这是因为SURF-64描述子选取特征点周围的子区域较多，每个子区域对最终描述子的贡献比例较小，而SURF-36由于采样的子区域只有9个，在子区域内的低采样范围容易造成特征点描述子鲁棒性降低，所以在低采样范围如3×3、4×4时，匹配的特征点数量较低。

对于分辨率较低的图像，如本例采用的640×480的图像，子区域内采样点范围在5×5、6×6时效果较好；另外比较图6中纵轴“拼接特征点数”，可以发现采样点范围在5×5、6×6以上时，SURF-36描述子对于SURF-64描述子在匹配成功的特征点数量上没有明显劣势，而运算速度却有明显的提升。

4 SURF算法中参数配置的选择策略

采用控制变量的方法，综合比较以上三方面对SURF算法的参数配置在特征点匹配中的功效。图4中所示的640×480的图像分别对是否改进窗口滤波器、特征点子区域的范围和子区域内采样范围进行控制，得到表3中测试结果。其中子区域采样范围分别取9×9、5×5、3×3，由于在子区域采样范围在3×3时匹配特征点数量已经很少，所以没有对其进行改进窗口滤波器测试。

从表3中可以分析，可以通过比较表3中的“SURF-64 9×9”、“SURF-64 5×5”、“SURF-64 5×5方”、“SURF-36 5×5”四列，以SURF算法最初始的配置“SURF-64 5×5”为基准，单纯从整个运算时间上考虑，扩大特征点子区域内采样范围的时间代价最大，运算时间增加了45%；其次为特征点选取中使用改进权值后窗口滤波器，总运算增加了20%；而降低特征点描述子维数（从64到36）则使时间减少了约18%。可见子区域内采样范围对整个算法的运算时间影响最大。

表3 控制变量法对SURF算法中不同参数方案的比较1）

从算法特征点匹配数量上考虑，特征点描述子维数越多，子区域内采样范围越大，匹配的特征点数目越多，而改进后的窗口滤波器，对特征点的匹配数量上没有提升。从特征点匹配率上来看，丰富窗口滤波器的权值，补偿图像中部分深度信息的方法，提高了特征点选取的准确程度；64维描述子比36维描述子的匹配率高；子区域采样范围大的匹配率高。因为图像中特征点选取数量不变，而维数高，采样范围大的描述子使得匹配成功的特征点数量增加。从匹配效率上来讲，SURF-36整体上要高于SURF-64，这是因为对于本例中640×480的图像，36维描述子已经足够满足精度，所以描述子维度虽然降低了，但是匹配的特征点数目却没有大幅减少，反而省去了多余的计算，使运算时间大幅减少。

综上所述，可以总结出如图7所示的SURF算法在处理低分辨率图像上参数选择策略，对于实时性要求较高的应用，为提高算法运算速度，首先考虑降低SURF描述子维数，因为在低分辨率的图像上，低维数的描述子准确度降低不明显但运算速度更快；其次考虑缩小特征点周围子区域内采样点的范围。若特征点相对密集，图像间重合部分较小，两幅图像相对角度较大，对拼接准确性要求较高的情况下，可以扩大特征点周围子区域内采样点范围。若错误匹配特征点较多，则可以通过改进窗口滤波器权值补偿像素点的深度信息来精确对特征点的遴选。

图7 SURF算法在实时低分辨率处理上参数策略

5 结束语

本文讨论了SURF算法中一些可配置参数对算法时效性、准确性和鲁棒性的影响。在特征点选取中对窗口滤波器的选择，特征点描述时对特征点周围子区域的选择以及子区域内采样点范围的选择三方面，基于目前视频流中最常采用的分辨率为640×480的图像进行特征点匹配，采用控制变量法，从特征点匹配率和匹配效率分别对不同配置对特征点匹配的结果进行分析与比较，提出针对低分辨率实时图像处理中SURF算法参数配置策略。

后续研究将针对于重合区域较小的图像以及分辨率较高的图像在利用SURF算法拼接过程中相应参数的配置，从而完善SURF算法参数配置理论，使得算法在不同侧重点的应用中都能最大地发挥优越性。

[1]Bay H，Ess A，Tuytelaars T，et al.Speeded-Up Robust Features（SURF）[J].Computer Vision and Image Understanding（CVIU），2008，110（3）：346-359.

[2]Huang Xiangsheng，Wang Jie，Zhang Mandun，et al.Gradual-SURF[C]//Proceedings of the 4th International Congress on Image and Signal Processing，2011：906-909.

[3]Chen Xiaoming，Bao Jing，Jiang Letian，et al.Integrated multidirectional panoramic image processing system[C]//Proceedings of the World Congress on Engineering and Technology，2011.

[4]Senarathne C N，Ransiri S，Arangala P，et al.A faster image registration and stitching algorithm[C]//Proceedings of the 6th International Conference on Industrial and Information Systems，2011.

[5]林武，洪景新，张昊.快捷有效的视频图像序列拼接方法[J].计算机工程与应用，2009，45（2）：173-175.

[6]时磊，谢晓方，乔永军.基于SURF算法和OpenCV的人脸特征检测技术研究[J].计算机与数字工程，2010，38（2）：124-126.

[7]张锐娟，张建奇，杨翠.基于SURF的图像配准方法研究[J].红外与激光工程，2009，38（1）：160-165.

[8]Ihme T，Wetzelsberger K，Speckert M，et al.Real-time image processing based on a task-pair scheduling concept[C]//Proceedings of the 2011 IEEE International Conference on Robotics and Automation，2011：5596-5601.

ZHOU Yuhaowei,YING Rendong,JIANG Letian

Department of Electronic Engineering,Shanghai Jiao Tong University,Shanghai 200240,China

In the field of image stitching,SURF algorithm is widely used for its excellent real-time procedure and robust.Due to the fixed parameter settings in interest point detection and description,the adjustability of SURF algorithm to different applying situation is relatively weak.In order to improve the range of SURF application,this paper looks into three aspects in the algorithm: the weight of box filter,the sub-region selection and the Haar wavelet sampling point range within the sub-region.In comparing the real-time quality,the stitching accuracy and the robust quality of the algorithm,the experiments using variable control method propose a parameter setting strategy based on small scale image which is widely used in nowadays stream media.In analyzing the interest points match rate and efficiency,the strategies proposed in characterizing the algorithm can extend the use of SURF in real-time field.

Speeded Up Robust Features（SURF）algorithm;image stitching;small scale image;parameter settings;interest points matching;box filter;sub-region of interest points

在图像拼接领域，SURF算法因其出众的时效性和鲁棒性，有着十分广泛的应用。针对SURF算法中特征点提取和描述过程中参数固定，对侧重点不同的图像拼接应用存在变通性较差的问题，提出了从窗口滤波器权值，特征点周围子区域的选择以及子区域内Haar小波变换的采样点范围三方面进行参数配置优化。针对目前主流的流媒体尺寸图像，利用控制变量法在不同的SURF参数配置下，对算法的时效性、准确性和鲁棒性等性能进行了分析；通过特征点匹配率和特征点匹配效率的比较，给出了SURF算法参数的选择策略。仿真结果表明该策略可以有效提高SURF算法在图像拼接中的运算速度和准确性，丰富算法在实时领域的应用。

加速鲁棒特征（SURF）算法；图像拼接；小尺寸图像；参数配置；特征点匹配；窗口滤波器；特征点子区域

A

TP391

10.3778/j.issn.1002-8331.1206-0003

ZHOU Yuhaowei,YING Rendong,JIANG Letian.Parameter setting optimization in SURF algorithm based on small scale image.Computer Engineering and Applications,2013,49（19）：191-195.

周宇浩崴（1987—），男，硕士，研究方向为图像拼接算法；应忍冬（1975—），男，博士，副教授，研究方向为导航信号处理，SoC芯片架构，嵌入式系统；蒋乐天（1975—），男，博士，副教授，研究方向为系统可靠性与可用性研究，软件可靠性研究，嵌入式系统与结构。E-mail：yuhaowei.zhou@sjtu.edu.cn

2012-06-01

2012-08-29

1002-8331（2013）19-0191-05

CNKI出版日期：2012-09-25http://www.cnki.net/kcms/detail/11.2127.TP.20120925.1002.053.html

◎信号处理◎