2. 国网安庆供电公司 安全监察质量部, 安徽 安庆 246000 ;
3. 安徽大学 电子信息工程学院, 合肥 230601 ;
4. 安徽南瑞继远电网技术有限公司, 合肥 230088
2. Safety Supervision Quality Department, State Grid Anqing Electric Power Supply Corporation, Anqing Anhui 246000, China ;
3. School of Electronics and Information Engineering, Anhui University, Hefei Anhui 230601, China ;
4. Anhui Nari Jiyuan Electric Power System Technology Company Limited, Hefei Anhui 230088, China
目标匹配、图像拼接、3D重建、目标识别等计算机视觉应用都依赖于图像配准。图像配准的通用方法是提取图像中的关键点进行比对处理。寻找有效的关键点描述子,使其对尺度变换、旋转变换、仿射变换和噪音等都具有较高的鲁棒性,成为近十几年的研究热点。随着大数据的发展和视觉算法在智能手机及嵌入式设备上的应用,使描述子同时具备简洁的描述方式、良好的表征能力和快速的比对计算过程,成为新的研究趋势。
由于二进制数据的高效计算能力,多种二进制串描述子被提出来用于提高图像配准的效率,如二进制鲁棒独立成分特征(Binary Robust Independent Elementary Feature, BRIEF)[1]、二进制鲁棒尺度不变特征(Binary Robust Invariant Scalable Keypoint, BRISK)[2]、旋转二进制鲁棒独立位特征(Oriented FAST and Rotated BRIEF, ORB)[3]、快速视网膜特征(Fast REtinA Keypoint, FREAK)[4]等。FREAK描述子基于人眼视网膜原理,以关键点为中心设计一种由粗到细的采样模式,由采样点对的关系构成一种二进制串的描述子, 具有尺度不变性、旋转不变性、对噪声的鲁棒性等多种优点。
虽然FREAK描述子通过计算模式方向实现了旋转不变性,但对于旋转尺度变化较大的情况匹配性能并不理想,误匹配率较高。本文算法在基于FREAK视网膜采样模式和Hamming距离匹配的基础上进行了两处改进:首先,对每一个关键点采样模式添加最小距离阈值Dmin,生成长距离点对。因为局部梯度会互相抵消,所以仅由长距离点对生成角度信息。然后,加权Hamming距离,对任意两关键点描述子异或得到的二进制位串的每一位进行加权,使粗略的距离计算更加精细化。结果显示,在改善FREAK旋转不变性的同时,匹配精度明显提升。
1 相关技术图像配准中所使用的一些关键点,即一些突出的局部特征点。斑点和角点是两类常用的局部特征点。高斯拉普拉斯算子(Laplace of Gaussian, LOG)[5]和Hessian行列式(Determinant of Hessian, DOH)[5]是两个检测斑点的有效算子,Harris算子[6]则是提取角点的常用算子。
在检测和提取局部特征点的基础上,还需要使用合适的特征描述方法,对特征点的特性进行描述和表达,便于不同图像之间特征点的匹配。好的特征描述方法还应具有尺度不变性、旋转不变性等特性。应用广泛的关键点描述子有:尺度不变特征变换(Scale-Invariant Feature Transform, SIFT)[7]、加速鲁棒特征(Speeded Up Robust Features, SURF)[8]、二进制鲁棒独立成分特征(BRIEF)[1]、二进制鲁棒尺度不变特征(BRISK)[2] 、旋转二进制鲁棒独立位特征(ORB)[3]、快速视网膜特征(FREAK)[4]等。
SIFT和SURF都是浮点型特征描述子[9]。SIFT是Lowe提出的一种高效的尺度不变特征变换算法,利用原始图像与高斯核的卷积来建立尺度空间,并在高斯差分空间金字塔上提取出尺度不变性的特征点,使用邻域梯度直方图统计作为其特征描述。由于SIFT对尺度、旋转以及一定视角和光照变化等都具有不变性,且具有很强的可区分性,自它提出以来,很快在物体识别、宽基线图像匹配、三维重建、图像检索中得到了应用,其良好的效果也使得局部图像特征描述子在计算机视觉领域内得到了更加广泛的关注。SURF 是基于SIFT算法的思路提出的一种加速鲁棒特征。该算法主要针对于SIFT算法速度慢、计算量大的缺点,使用了近似Harr小波方法来提取特征点,这种方法就是基于Hessian行列式(DoH)的斑点特征检测方法。通过在不同的尺度上利用积分图像可以有效地计算出近似Harr小波值,简化了二阶微分模板的构建,提高了尺度空间特征检测的效率。其他一些作者在SIFT或SURF的基础上进行了多种改进[10-14]。
BRIEF、BRISK、ORB、FREAK等则是基于二进制独立位串的描述子[15]。这类描述子时间代价和计算复杂度都大幅减小,匹配速度呈数量级提升。BRIEF利用局部图像邻域内随机点对的灰度大小关系来建立局部图像特征描述子,得到的二值特征描述子不仅匹配速度快,而且存储要求内存少。ORB算法使用加速分割测试特征(Features from Accelerated Segment Test, FAST)进行特征点检测,然后用BRIEF进行特征点的特征描述,并在BRIEF基础上引入了方向的计算方法,在点对的挑选上使用贪婪搜索算法,挑出了一些区分性强的点对用来描述二进制串。BRISK算法在特征点检测部分选用了稳定性更强的自适应通用加速分割检测(Adaptive and Generic Accelerated Segment Test, AGAST)算法。在特征描述子的构建中,BRISK算法采用了邻域采样模式,即以特征点为圆心,构建多个不同半径的离散化Bresenham同心圆,然后在每一个同心圆上获得具有相同间距的N个采样点,再使用和BRIEF一样的方式,构建级联的二进制比特串来描述每个特征点。随后一些作者针对BRISK、ORB提出了一些改进的方法[16-20]。
2 基于FREAK的特征点配准改进算法 2.1 算法总体流程如图 1所示,算法总体分为关键点检测、特征描述子生成、特征点配准、图像转换处理等四个步骤。第一步先对图像进行预处理并通过SIFT或SURF等算法中的关键点检测操作获取图像的所有关键点。第二步基于改进的FREAK构建关键点特征描述子。第三步使用改进的配准算法进行特征点距离计算及匹配操作。第四步根据匹配结果计算图像变换模型,进行图像变换处理,变换过程中使用双线性插值方法进行插值重采样。
第一步和第四步使用的是成熟方法,不再详细介绍。本文重点描述第二步和第三步的处理。
2.2 特征描述子生成 2.2.1 特征点邻域采样首先对特征点邻域进行FREAK采样,采样模式仍然采样FREAK视网膜模式,即以图像中每一个检测到的关键点为中心,采样点均匀分布在各个同心圆上;越靠近中心点采样点越密集重叠;多个采样像素点计算产生一个关键点的描述,如图 2所示。
FREAK采样模式中(如图 2)共43个采样点,7个同心圆上各均匀分布6个,形成C432=903个点对,所有点对比较产生903位的二进制串。但由于采样点的混叠,采样点对具有很高的相关性,所以在对特征点描述之前,需要选择低相关性点对。选择相同尺寸的大量图片进行训练,对每一个检测到的关键点进行全部点对描述,形成N×903的矩阵;计算矩阵每一列0、1的均值,越接近0.5,该列相应点对相关性越低;按均值与0.5的差值绝对值从小到大的顺序排列,取前M位,并记住这M位点对的索引,那么这M位点对索引就是训练产生的结果。在进行匹配操作时使用这些低相关性点对就计算得到了低相关性描述子。
为了避免噪声的影响,对每一个采样模式中的像素点进行高斯平滑,标准差σ随点与中心点之间的距离以指数方式改变。设低相关性采样点对构成集合P⊇pi(i∈0, 1, …, M-1) , 其中一个点对记为(pi1, pi2),滤波后记为(pi1σ1, pi2σ2)。
2.2.3 基于长距离点对的方向预测FREAK采用人为指定的45个点作特征点的模式方向预测,虽然也实现了旋转不变的性能,但对于旋转尺度变化较大的情况匹配性能并不理想,误匹配率较高。本文对原有FREAK算法添加类似BRISK的长距离点对,设定阈值Dmin,只利用关键点采样模式中距离较远的点来生成角度信息。这样通过改变阈值大小可以获得不同数量的长距离点对。通过训练样本计算不同阈值下的方向预测准确度,选择预测准确度最高时的阈值进行后续测试样本的处理,此时匹配效果较其他值更好,且优于原算法的性能,更适用于旋转尺度变化较大的情况。
设方向点对构成集合G⊇gj(j∈0, 1, …, K-1) ,则每一个特征点的模式方向为:
$O = \left[ \begin{array}{l} {o_x}\\ {o_y} \end{array} \right] = \frac{1}{K}\sum\limits_{{g_j} \in G} {(I({g_{j1}}^{\sigma 1})} - I({g_{j2}}^{\sigma 2}))\frac{{{g_{j1}}^{\sigma 1} - {g_{j2}}^{\sigma 2}}}{{{{\left\| {{g_{j1}}^{\sigma 1} - {g_{j2}}^{\sigma 2}} \right\|}^2}}}$ | (1) |
$\theta = \arctan ({o_y},{o_x})$ | (2) |
把采样模式围绕中心点旋转θ角,由M个低相关性点对(pi1σ1, θ, pi2σ2, θ)计算产生该特征点的描述子。
2.3 特征点配准 2.3.1 粗配准根据生成的二进制串描述子,使用常规的Hamming距离进行匹配计算,得到多个粗略的匹配点。
经过快速的粗配准,剔除90%的候选匹配点,对剩下的匹配点进行准确配准操作,即可使用更为精细的配准技术。
2.3.2 细配准距离算子在粗配准中,Hamming距离的计算仅仅是求取两描述子二进制序列异或后的“1”的个数,它对所有位上出现的“1”同等看待,距离计算太过粗略。在细配准时,距离算子改为加权的Hamming:对两描述子异或后的二进制串的每一位“1”进行加权,记权值为w,权重设计如下:
$w = {e^{ - {{(mean - 0.5)}^2}/2{\sigma ^2}}}$ | (3) |
其中,mean代表低相关性列选择时每一列计算得到的平均值。 mean越接近0.5,所包含的能量越高,点对相关性越低,因而权重应该越大。所设计的高斯权重正好反映出这一点。
对加权后的二进制串每一位“1”,计算浮点值总和sum,则该sum值就是加权Hamming距离。实验表明,改进后的Hamming距离更加精确,匹配性能更高。
2.3.3 细配准方法特征向量包含了特征点邻域的信息,本文采用最近邻(K-Nearest Neighbor, KNN)匹配法穷举搜索潜在的匹配点对而无需进行额外的信息量的计算。设两特征点对集合S1、S2,对S1中的任意一点s1i,在S2中寻找距离最近(dmin)和次近(dsec-min)的两点s2i1、s2i2,当dmin/dsec-min <t满足时,则认为两点s1i和s2i1为匹配对。本文选择t=0.6[21],此阈值下错误匹配点较少。
在细配准过程中,采用随机抽样一致(RANdom SAmple Consensus, RANSAC)方法剔除误匹配点对,并迭代估算变换模型H参数,其中H是一个3×3的矩阵,然后对待配准图像进行插值重采样得到同一坐标系下的配准结果。本文选择RANSAC默认阈值1.0(为OpenCV函数参数默认值)。
3 实验结果及分析本文所有测试统一采用SURF关键点检测方法,在不同的尺度空间进行高斯平滑,去掉了部分噪声干扰,保证了尺度不变性。实验环境为Windows XP系统,Intel i5-2400,2.98 GB RAM,采用VS2010和OpenCV2.4.8 软件编程。使用参考文献[1]中常用测试图像数据库boat系列进行算法性能的评价和比较,从img1到img6的旋转和尺度变化逐渐增强,如图 3所示。对img1进行多种旋转变化和尺度缩放,得到30幅结果图片,作为匹配前的选择点对的训练图片。所有图片均预处理为相同尺寸大小。
用于方向预测的长距离点对选取阈值计算:通过训练样本进行计算,得出当Dmin=18.0时方向预测最准,选取出90个长距离点对,比原算法多了一倍,包含更多的方向信息。
分别用BRISK算法、原FREAK算法、本文改进FREAK算法进行特征点描述,匹配效果和执行效率的比较结果如图 4所示。
从图 4中的折线图可以看出,对于boat系列从img2到img6,随着旋转和尺度变化增强,三种算法匹配性能都大幅下降。从img2到img3,由于FREAK特殊的视网膜采样模式和低相关性采样点的选择,原FREAK和本文改进算法都优于BRISK。从img4到img6,由于本文改进FREAK算法添加了长距离点对和加权Hamming距离,使得匹配精度更高,匹配效果明显好于原FREAK。从时间对比表 1中可以看出,由于FREAK和本文算法较BRISK采样点数较少,描述步骤更简洁,所以时间花费也较少。在描述子生成阶段,本文算法虽然添加长距离点对花费了少量时间,但相比原FREAK 512位的描述子,本文只采用前128位,描述时间明显缩短。在匹配阶段,本文算法由于对Hamming距离加权,距离计算较复杂,所以时间花费有所增加。总体比较来看,本文改进FREAK与原FREAK算法花费时间大致相同。
本文对FREAK描述子模式方向的预测作了改进,添加长距离点对,只利用采样模式中距离较远的点对生成角度信息;同时改进了Hamming距离的计算方法,对距离二进制串每一位进行高斯加权,提高了精确度。实验结果显示,本文算法更适用于旋转尺度变化较大的场景下对匹配精度要求较高的场合。本文算法基于FREAK进行改进,由于构建FREAK描述子仅使用了采样点强度值,特征不够丰富,仍有改进空间。另外,算法中部分参数如最近邻与次近邻距离比等使用经验值,后续将采用合适的学习方法加以优化。
[1] | CALONDER M, LEPETIT V, STRECHA C, et al. BRIEF:binary robust independent elementary features[C]//Proceedings of the 11th European Conference on Computer Vision:Part IV. Berlin:Springer-Verlag, 2010:778-792. |
[2] | LEUTENEGGER S, CHLI M, SIEGWART R Y. BRISK:binary robust invariant scalable keypoints[C]//Proceedings of the 2011 IEEE International Conference on Computer Vision. Piscataway, NJ:IEEE, 2011:2548-2555. |
[3] | RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB:an efficient alternative to SIFT or SURF[C]//Proceedings of the 2011 IEEE International Conference on Computer Vision. Washington, DC:IEEE Computer Society, 2011:2564-2571. |
[4] | ALAHI A, ORTIZ R, VANDERGHEYNST P. FREAK:fast retina keypoint[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2012:510-517. |
[5] | LINDEBERG T. Feature detection with automatic scale selection[J]. International Journal of Computer Vision, 1998, 30 (2) : 79-116. doi: 10.1023/A:1008045108935 |
[6] | HARRIS C G, STEPHENS M J. A combined corner and edge detector[J]. Manchester:Alvety Vision Club, 1988 : 147-151. |
[7] | LOWE D G. Object recognition from local scale-invariant features[C]//Proceedings of the 1999 IEEE International Conference on Computer Vision. Washington, DC:IEEE Computer Society, 1999, 2:1150-1157. |
[8] | BAY H, TUYTELAARS T, VAN GOOL L. SURF:Speeded up robust features[C]//Proceedings of the 9th European Conference on Computer Vision-Part I. Berlin:Springer-Verlag, 2006:404-417. |
[9] | LUO J, GWUN O. A comparison of SIFT, PCA-SIFT and SURF[J]. International Journal of Image Processing, 2009, 3 (4) : 143-152. |
[10] | YAN K, SUKTHANKAR R. PCA-SIFT:A more distinctive representation for local image descriptors[C]//Proceedings of the 2004 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2004:506-513. |
[11] | 郑永斌, 黄新生, 丰松江. SIFT和旋转不变LBP相结合的图像匹配算法[J]. 计算机辅助设计与图形学学报, 2010, 22 (2) : 286-292. ( ZHENG Y B, HUANG X S, FENG S J. An image matching algorithm based on combination of SIFT and the rotation invariant LBP[J]. Journal of Computer-Aided Design & Computer Graphics, 2010, 22 (2) : 286-292. ) |
[12] | 唐朝伟, 肖健, 邵艳清, 等. 一种改进的SIFT描述子及其性能分析[J]. 武汉大学学报(信息科学版), 2012, 37 (1) : 11-16. ( TANG C W, XIAO J, SHAO Y Q, et al. An improved SIFT descriptor and its performance analysis[J]. Geomatics and Information Science of Wuhan University, 2012, 37 (1) : 11-16. ) |
[13] | 张锐娟, 张建奇, 杨翠. 基于SURF的图像配准方法研究[J]. 红外与激光工程, 2009, 38 (1) : 160-165. ( ZHANG R J, ZHANG J Q, YANG C. Image registration approach based on SURF[J]. Infrared and Laser Engineering, 2009, 38 (1) : 160-165. ) |
[14] | 杜振鹏, 李德华. 基于KD-Tree搜索和SURF特征的图像匹配算法研究[J]. 计算机与数字工程, 2012, 40 (2) : 96-98. ( DU Z P, LI D H. Image matching algorithm research based on KD-Tree search and SURF features[J]. Computer & Digital Engineering, 2012, 40 (2) : 96-98. ) |
[15] | 索春宝, 杨东清, 刘云鹏. 多种角度比较SIFT、SURF、BRISK、ORB、FREAK算法[J]. 北京测绘, 2014 (4) : 23-26. ( SUO C B, YANG D Q, LIU Y P. Comparing SIFT, SURF, BRISK, ORB and FREAK in some different perspectives[J]. Beijing Surveying and Mapping, 2014 (4) : 23-26. ) |
[16] | 曹建, 谢晓方, 梁捷, 等. 基于BRISK改进的快速角点特征算法[J]. 舰船电子工程, 2013, 33 (5) : 44-47. ( CAO J, XIE X F, LIANG J, et al. Improved fast corner algorithm based on BRISK[J]. Ship Electronic Engineering, 2013, 33 (5) : 44-47. ) |
[17] | 杜军. 基于BRISK特征的图像配准提取与描述研究[J]. 十堰职业技术学院学报, 2012, 25 (1) : 106-109. ( DU J. On characteristics of BRISK image registration extraction and description[J]. Journal of Shiyan Technical Institute, 2012, 25 (1) : 106-109. ) |
[18] | 石祥滨, 孙奇, 张德园, 等. 一种自适应阈值分块BRISK的图像配准方法[J]. 沈阳航空航天大学学报, 2014, 31 (6) : 65-72. ( SHI X B, SUN Q, ZHANG D Y, et al. Method of image registration based on adaptive threshold and block BRISK algorithm[J]. Journal of Shenyang Aerospace University, 2014, 31 (6) : 65-72. ) |
[19] | 何林阳, 刘晶红, 李刚, 等. 改进BRISK特征的快速图像配准算法[J]. 红外与激光工程, 2014, 43 (8) : 2722-2727. ( HE L Y, LIU J H, LI G, et al. Fast image registration approach based on improved BRISK[J]. Infrared and Laser Engineering, 2014, 43 (8) : 2722-2727. ) |
[20] | 李小红, 谢成明, 贾易臻, 等. 基于ORB特征的快速目标检测算法[J]. 电子测量与仪器学报, 2013, 27 (5) : 455-460. ( LI X H, XIE C M, JIA Y Z, et al. Rapid moving object detection algorithm based on ORB features[J]. Journal of Electronic Measurement and Instrument, 2013, 27 (5) : 455-460. ) |
[21] | ZHANG R.SIFT特征提取分析[EB/OL].[2016-03-06]. http://blog.csdn.net/abcjennifer/article/details/7639681/. ( ZHANG R. SIFT feature extraction and analysis[EB/OL].[2016-03-06]. http://blog.csdn.net/abcjennifer/article/details/7639681/ ) |