2014, Vol. 25
2. 中国传媒大学 计算机学院, 北京 100024;
3. 中关村科技园区海淀园企业博士后, 北京 100089;
4. 中国科学院 自动化研究所, 北京 100190;
5. 北京科技大学 计算机与通信工程学院, 北京 100083;
6. 北京航空航天大学 机器人研究所, 北京 100191
2. School of Computer, Communication University of China, Beijing 100024, China;
3. Enterprise Postdoctoral of Zhongguancun Haidian Science Park, Beijing 100089, China;
4. Institute of Automation, The Chinese Academy of Sciences, Beijing 100190, China;
5. School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China;
6. Robotics Institute, BeiHang University, Beijing 100191, China
图像匹配技术已成为计算机视觉领域中一项非常重要的技术,该技术把不同摄像机或同一摄像机在不同时间、不同光照强度、不同视角条件下得到的同一景物的两幅或多幅图像在空间上进行映射,以确定出它们之间的空间对应关系.图像匹配技术在诸多领域有着广泛的应用,如地图和地形匹配、飞机导航、武器投射系统的末制导、光学雷达的图像模版跟踪、工业流水线的自动监控、工业仪表的自动监控、医学诊断、文字识别以及场景分析中的变化检测等等.
图像匹配算法大致分为两类:基于描述符的匹配算法和基于特征学习的匹配算法.基于描述符的匹配算法已广泛应用于各个领域,该类算法往往要求特征点和描述符对图像旋转、仿射形变及光照变化等具有强鲁棒性,从而导致特征点与描述符提取算法较为复杂,一定程度上影响了图像匹配算法的实时性.Columbia大学 Lowe教授提出的SIFT[1]描述符以其优越的性能及稳定表现成为特征匹配算法的标准.SIFT匹配算法由尺度空间极值检测、特征点提取、特征方向提取及特征点局部特征提取这4部分组成,其中,特征点提取需要估计特征尺度及方向信息.由于SIFT描述符较为复杂(128维向量),导致SIFT匹配算法的实时性较差.针对SIFT匹配算法实时性较差的问题,Bay提出了SURF[2, 3]算法,SURF对光照变化和仿射形变同样具有强鲁棒性,且其实时性提高了3~7倍.
考虑到SURF匹配算法实时性方面的优势,本文以其为参照标准进行算法的各种性能比较.
近些年,部分学者提出一种基于特征学习的匹配算法,该类算法相对于基于描述符的匹配算法具有更好的实时性和稳定性,但存在特征训练时间过长的缺陷.文献[4, 5]通过在特征数据库中搜索与给定特征点相似度较高的特征,粗略估计给定描述符的位置信息(特征数据库中的特征点包含相关的位置信息);然后,通过反向合成算法[6]和线性回归算法[7]获取准确的位置信息.文献[4, 5]都采用了Fern[8]分类器与线性分类器进行训练,但二者均需较长的训练时间.文献[9]首先对给定特征点的对应图像区域进行透视变换,生成不同视点下的区域图像,然后将各视点下的区域图像分成多组图像集(每个图像集覆盖较小的视角范围),再计算每个图像集对应区域像素点均值图像,从而获得该特征点对应的特征数据库.文献[9]提出了快速计算各视点下的多幅区域图像像素点均值的方法,显著缩短了算法的训练时间.文献[10]为了实现不同视角下图像的快速匹配,提出基于简单描述符与视点分解思想的图像快速匹配算法,通过对给定图像进行透视变换,生成多组不同视角下的图像集,并对每个图像集提取重复率较高的一定数量的FAST特征点.通过描述符索引等优化算法,该算法获得了非常理想的实时性,成功识别一幅分辨率为640x480的图像不到2ms.但该算法的离线训练时间较长,即使算法优化后[11]的训练时间仍需20min左右.
本文提出了一种基于描述符RIBRIEF的图像快速匹配算法,该算法克服了BRIEF[12]对图像旋转敏感的缺陷.与描述符BRIEF提取算法类似,RIBRIEF仅对某特征点周围区域的n对相对像素点进行简单比较,因此描述符具有提取速度快、易于量化等优点,同时对各种干扰(噪声、光照及模糊)及仿射形变具有较强的鲁棒性.描述符RIBRIEF的旋转不变性及对视点变化的强鲁棒性决定了它更加适用于视点分解,其对仿射形变的强鲁棒性决定了少量视点下的图像即可以覆盖整个视角范围,其理想的描述符提取速度决定了算法具有良好的实时性.基于FAST稳定特征点提取算法,通过减少图像视点分解数量和提高重复特征点提取速度以缩短特征训练时间,提高算法实时性.
本文第1节给出描述符RIBRIEF提取原理.第2节介绍提出的描述符特征方向提取方法.第3节介绍提出的描述符索引与聚类相结合的优化算法.第4节介绍提出的基于FAST的相对稳定特征点提取算法.第5节给出实验结果.第6节给出本文结论.
1 描述符RIBRIEF原理 1.1 BRIEF的基本原理描述符BRIEF[12]仅对特征点周围区域的n对像素点进行简单比较,具有提取速度快、识别能力强、易于量化等优点,并且可以通过逻辑运算计算描述符相似度,较大程度地提高了匹配算法的实时性.描述符BRIEF对图像的各种干扰(光照、噪声、模糊)以及尺度缩放、仿射变换均具有较强的鲁棒性.
描述符BRIEF的具体定义如下:
小块区域p(尺寸为SxS)对应的描述符d为
(1)
其中,p(x)为特征点k周围小块区域中点x=(u,v)T处像素值,通过高斯分布选取nd对像素点,并定义nd(x,y)为该特征点对应的二值化后的描述符.此时,nd维BRIEF描述符可定义为
(2)
描述符BRIEF虽然具有很多优点,但同样存在描述符对图像大角度旋转较为敏感的问题.本文提出的描述符RIBRIEF(rotation invariant binary robust independent elementary features)在继承BRIEF所有优点的基础上,克服了BRIEF对大角度旋转敏感的问题.为了实现描述符的旋转不变性,需获取特征方向作为参考方向,在特征方向已知的条件下,RIBRIEF仅对采样点的位置坐标进行简单的坐标变换即可实现描述符的旋转不变性.
图 1(a)为特征点p对应的小块图像区域,其中,b为特征点对应的特征方向,标号1~标号8为采样点.图 1(b)中的采样点1~采样点8为坐标变换(图 1(a)中采样点逆时针旋转b度)后的点,与图 1(a)中的采样点1~采样点8相对应.图 1(c)为图 1(a)顺时针旋转a度后的图像,其中,g为特征点对应的特征方向,点1~点8为图 1(c)对应的采样点,其与图 1(a)中的采样点具有相同的坐标值.图 1(d)中的采样点1~采样点8为坐标变换(图 1(c)中采样点逆时针旋转g度)后的点,与图 1(c)中采样点1~采样点8相对应.
 | Fig. 1 Coordinate transformation diagrams图 1 坐标变换示意图 |
从图 1(b)及图 1(d)可以看出:经过坐标变换后的采样点对应相同的图像位置,从而获得具有旋转不变性的描述符.下面具体分析RIBRIEF对应的坐标变换:
pcn=ra(pan) (3)
(4)
(5)
公式(3)为图 1(a)到图 1(c)采样点的坐标变换,公式(4)为图 1(a)~图 1(b)采样点的坐标变换,公式(5)为图 1(c) ~图 1(d)采样点的坐标变换,其中,rn(p)为点p顺时针旋转n度,
为点p逆时针旋转n度,pmn为m图所对应的采样点n,其中m对应图 1(a)~图 1(d)中的任意一幅图,n对应图 1(a)~图 1(d)中的任意采样点.
(6)
通过图 1(a)与图 1(c)的旋转变换,可以得到b=g-a,从而证明:
pdn=pbn (7)
2 特征方向提取
为了使描述符BRIEF具有旋转不变性,需提取特征点对应的特征方向,以该方向为参考方向进行坐标变换,实现描述符的旋转不变性.文献[11]通过计算特征点周围区域8组相对称像素点的梯度方向的和来获取该特征点对应的特征方向.该方法的特征方向提取速度快,但存在对图像噪声、仿射变换较为敏感的问题.本文针对以上问题,提出了改进算法.如图 2所示,图 2(a)中的p为特征点,an,bn(n=1,2,…,8)为采样区域,箭头方向为对称点对应区域的梯度方向,图 2(b)中的
为特征点p对应的特征方向,其定义为
(8)
(9)
(10)
(11)
 | Fig. 2 Feature direction extraction图 2 特征方向提取 |
为特征点p与区域an中心点间的方向,
为特征点p与区域bn中心点间的方向,pmi为区域m中第i个像素点对应的像素值,rm为区域m对应的像素均值,
为区域an与区域bn对应的梯度方向,s为区域rm对应的像素点数量.
3 索引与聚类
3.1 描述符相似度计算 文献[10, 11, 13]提出通过简单的逻辑运算获取描述符之间的相似度,从而在降低内存使用量的同时,提高描述符的匹配速度.描述符RIBRIEF可直接通过异或逻辑运算计算相似度,定义模板特征点i及待匹配图像特征点q,分别提取特征点对应的描述符di和dq,通过异或逻辑运算计算描述符di和dq对应的相似度值s:
(12)
通过公式(12),可以显著提高描述符的匹配计算速度.但当描述符数量过多时,仍存在匹配速度较慢的问题.此时,可通过描述符索引、聚类等方法进一步提高匹配算法的实时性.
描述符索引的基本思想是:通过某种方式对描述符进行编码,通过码值快速获取描述符间的对应关系.聚类的基本思想是:将相似度较高的描述符归类,计算给定的描述符与某类描述符的相似度量值,并将该相似度量值与给定阈值进行比较:当该量值小于阈值时,排除该类对应的所有描述符;否则,对该类内部描述符进行逐个匹配.文献[10]通过特征点周围的13个采样点对该特征点对应的描述符进行编码,实验结果表明:由于文献[10]采用了较多的采样点,一定程度上影响了获得匹配点的准确性.针对文献[10]存在的问题,本文提出了描述符索引与描述符聚类相结合的优化算法,其基本思想是:采用较少的采样点对描述符进行编码(这样可以保证获取足够多的正确匹配点),然后,通过描述符聚类进一步降低匹配点搜索计算的次数.如图 3所示,其中,0为以特征点为中心对应区域(区域尺寸为16x16),1~8为以采样点为中心对应区域(区域尺寸为9x9),R1与R2为特征点与采样点之间的距离.描述符的码值定义如下:
(13)
(14)
 | Fig. 3 Index code图 3 索引编码示意图 |
文献[10]通过提取不同视点图像下的FAST特征点,并剔除重复率较低的点,以此减少用于匹配的特征点,提高在线匹配算法的实时性.针对这种离线特征学习方式存在实时性较差这一缺陷,本文提出基于FAST[14]的相对稳定特征点提取算法,该算法可以通过设置相应参数来控制特征点的数量.根据FAST特征点提取算法的原理,当阈值T越大时,所提取的特征点越稳定(即对光照变化、噪声及模糊具有更强的鲁棒性).给定一幅模板图像,通过改变阈值T迭代提取特征点,当提取特征点的数量满足设定的数量时(如50~150个)即停止迭代提取,此时所获得的点即为最终的相对稳定特征点.实际应用中,通过给定图像估算满足特征点数量条件下阈值T的范围,在提取其他图像时仅在此范围内进行特征点迭代提取,此时,迭代2~3次即可获取满足条件的特征点.而FAST特征点提取算法处理一幅分辨率为640x480的图像仅需几毫秒,保证了稳定特征点提取算法的实时性.
5 实验仿真实验内容包括描述符RIBRIEF鲁棒性检验及实时性检验两个方面,其中,鲁棒性检验主要针对各种干扰(光照变化、噪声和模糊)、仿射形变、旋转、尺度缩放等几个方面,实时性检验主要包括特征点提取速度、描述符提取速度及描述符匹配速度等几个方面.
5.1 实验环境实验硬件平台:AMD双核处理器(主频2.6GHz,内存2GB);软件环境:算法实现基于VC2005及OpenCV2.2,测试图像均由普通网络摄像头获取,图像尺寸为640x480.测试图像包括鲁棒性测试图像集(旋转图像集、仿射形变图像集以及干扰图像集)和实时性测试图像集(computer,book,scene及paper图像集).
5.2 描述符RIBRIEF鲁棒性测试鲁棒性测试包括旋转不变性、干扰鲁棒性及仿射形变鲁棒性这3个方面.所有测试均采用相同图像集,特征点提取采用OpenCV提供的SURF特征点提取算法,这样可以保证所有算法均可获取相同数量的特征点. SURF及BRIEF描述符提取算法同样采用OpenCV提供的源码,3种算法均采用最优匹配点搜索方式,通过比较最终获取正确匹配点的数量来评估各种算法的鲁棒性.如图 4所示,其中横轴表示图像索引值,纵轴表示正确匹配点数量.
 | Fig. 4 Experimental results of algorithm robustness图 4 算法鲁棒性测试结果 |
5.2.1 旋转不变性
图 4(a)所示为旋转不变性测试曲线图,可以看出:SURF算法对图像的旋转具有一定的鲁棒性,但对于部分旋转图像获取的匹配点数量较少;描述符RIBRIEF几乎对所有图像均能获取足够多的匹配点;而描述符BRIEF仅对部分存在小角度变化的图像获得了正确匹配点,对于大部分图像无法获取正确匹配点.综上所述,相对于SURF及BRIEF,描述符RIBRIEF在旋转不变性方面具有明显的优势.
5.2.2 干扰鲁棒性图 4(b)所示为鲁棒性测试曲线图,其中,索引0~25为高斯噪声图像,索引26~55为不同光照强度下的图像,索引56~75为不同程度高斯模糊的图像.可以看出,3种算法对于噪声干扰、光照变化及图像模糊均具有强鲁棒性,即使在各种干扰情况较严重时,仍可获取大量的正确匹配点,以满足各种实际应用.
5.2.3 仿射形变鲁棒性图 4(c)所示为仿射形变测试曲线图,可以看出:与SURF描述符相比,描述符RIBRIEF总体上可以获取更多的匹配点.对于部分视角下的图像,SURF无法获取匹配点,而RIBRIEF同样可以获取大量匹配点,从而证明在仿射形变鲁棒性方面,描述符RIBRIEF(相对于SURF)具有更好的稳定性和鲁棒性.由于仿射形变图像集中的图像存在较大的旋转角度变化,描述符BRIEF无法获取正确的匹配点.
5.3 描述符RIBRIEF实时性测试与SURF算法及BRIEF算法相比,本文通过采用描述符索引与聚类等方法,使得RIBRIEF描述符具有强实时性.实时性检验包括两个部分:
(1) SURF,BRIEF及RIBRIEF算法的特征点提取速度、描述符提取速度和匹配速度实时性比较;
(2) 测试特征点数量与算法实时性及正确匹配点数量的关系.图 5为部分匹配结果示意图.
 | Fig. 5 Matching result diagrams图 5 匹配结果示意图 |
5.3.1 特征点提取、描述符提取、匹配速度实时性分析
任意选取两幅图像(640x480)作为测试图像,除RIBRIEF描述符提取算法及匹配算法外,所有算法均采用OpenCV提供的源码.由于实验环境不同,测试结果与各算法文献提供的数据略有不同,但并不影响算法的性能比较.表 1为各项性能的测试结果,其中,特征点提取主要对比SURF特征点提取算法与RIBRIEF特征点提取算法(FAST)的实时性,可以看出,FAST算法在实时性方面具有明显的优势;通过提取特征点对应的描述符来对比各算法的描述符提取速度,可以看出,SURF描述符提取时间是BRIEF及RIBRIEF的几十倍,RIBRIEF略优于BRIEF.本文采用描述符索引与聚类等算法对匹配速度进行优化,匹配速度的测试结果表明:本文所提优化算法对于匹配速度的提高作用显著,但描述符索引和聚类会导致部分匹配点的丢失.表 1数据显示:与SURF算法相比,本文所提算法匹配速度提高了90倍,仅仅丢失了513个特征点,仍可获取958个匹配点,满足了实际应用需求.
|
Table 1 Comparison of real-time performance 表 1 算法实时性比较 |
5.3.2 特征点数量与算法实时性及匹配点数量的关系
图 6为特征点数量与匹配时间关系曲线图,其中纵轴为匹配时间.图 7为特征点数量与匹配点数量曲线图,其中纵轴为正确匹配点数量.图 6与图 7中的横轴表示图像索引,T表示每个模板对应的特征点数量,Q表示待匹配图像对应的特征点数量.
 | Fig. 6 Relationship curves of feature points and matching time图 6 特征点与匹配时间关系曲线图 |
 | Fig. 7 Relationship curves of feature and matching points图 7 特征点与匹配点关系曲线图 |
图 6(a)与图 7(a)对应book图像集测试结果,图 6(b)与图 7(b)对应computer图像集测试结果,图 6(c)与图 7(c)对应card图像集测试结果.其中,匹配时间由图像像素点累计值[15](OpenCV对应于Integral函数)、特征方向提取、特征点提取、描述符提取、描述符索引与聚类及描述符匹配几个部分决定.图中的T表示每个模板对应的特征点数量,Q表示待匹配图像对应的特征点数量.
图 6与图 7表明:随着特征点数量的减少,匹配时间缩短,同时匹配点的数量也随之减少;当T控制在0~500个,Q控制在0~200个点时,匹配时间可以缩短到10ms左右,匹配点数量为50个左右.
6 结 论本文提出一种具有强实时性和强鲁棒性的图像匹配算法.该算法首先以RIBRIEF描述符的特征方向为参考方向,对描述符的采样点进行坐标变换,使其对图像旋转具有不变性,克服了描述符BRIEF对图像旋转敏感的缺陷;然后,采用描述符索引与聚类相结合的优化算法,使描述符的搜索次数显著降低,从而提高了描述符的匹配速度;最后,通过基于FAST稳定特征点提取算法,快速提取图像重复率较高的特征点,控制提取特征点的数量.实验结果表明:与SURF及BRIEF相比,描述符RIBRIEF在实时性、仿射形变鲁棒性等方面具有明显优势.
描述符RIBRIEF具有旋转不变性和对视点变化的强鲁棒性,因而,进行视点分解时仅需少量各视点下的模板图像,所以在特征学习的速度方面将明显优于文献[12].因此,在保障实时性的同时,采用文献[10, 11]中视点分解的思想,通过增加各视角下的模板图像实现算法对视点变化的不变性,将成为基于RIBRIEF描述符图像匹配算法的重要研究方向.
| [1] | Lowe D. Distinctive image features from scale-invariant keypoints. Int’l Journal of Computer Vision, 2004,60(2):91-110 . |
| [2] | Bay H, Tuytelaars T, Gool LV. SURF: Speed up robust features. In: Proc. of the European Conf. on Computer Vision. 2006. 404-417 . |
| [3] | Bay H, Ess A, Tuytelaars T, Gool LV. Speeded-Up robust features (SURF). Computer Vision and Image Understanding, 2008, 110(3):346-359 . |
| [4] | Hinterstoisser S, Benhimane S, Lepetit V, Navab N.Simultaneous recognition and homography extraction of local patches with a simple linear classifier. In: Proc. of the British Machine Vision Conf. 2008. 1-10 . |
| [5] | Hinterstoisser S, Benhimane S, Navab N, Fua P, Lepetit V. Online learning of patch perspective rectification for efficient object detection. In: Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition. 2008. 1-8 . |
| [6] | Baker S, Matthews I. Lucas-Kanade 20 years on: A unifying framework. Int’l Journal of Computer Vision, 2004,56(3):221-255 . |
| [7] | Jurie F, Dhome M. Hyperplane approximation for template matching. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2002,24(7):996-100 . |
| [8] | Ozuysal M, Fua P, Lepetit V. Fast keypoint recognition in ten lines of code. In: Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition. 2007. 1-8 . |
| [9] | Hinterstoisser S, Kutter O, Navab N, Fua P, Lepetit V. Real-Time learning of accurate patch rectification. In: Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition. 2009. 2945-2952 . |
| [10] | Taylor S, Rosten E, Drummond T. Robust feature matching in 2.3ms. In: Proc. of the Conf. on Computer Vision and Pattern Recognition. 2009. 15-22 . |
| [11] | Taylor S, Drummond T. Multiple target localization at over 100 fps. In: Proc. of the British Machine Vision Conf. 2009. 58.1-58.11 . |
| [12] | Calonder M, Lepetit V, Fua P. BRIEF: Binary robust independent elementary features. In: Proc. of the 11th European Conf. on Computer Vision. Heraklion, Crete. 2010. 778-792 . |
| [13] | Hinterstoisser S, Lepetit V, Illic S, Fua P, Navab N. Dominant orientation templates for real-time detection of texture-less objects. In: Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition. 2010. 2257-2264 . |
| [14] | Rosten E, Drummond T. Machine learning for high speed corner detection. In: Proc. of the 9th European Conf. on Computer Vision. 2006. 430-443 . |
| [15] | Viola P, Jones M. Rapid object detection using a boosted cascade of simple features. In: Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition. 2001. 511-518 . |