SIFT特征匹配算法

SIFT特征匹配算法（通用7篇）

SIFT特征匹配算法 篇1

0引言

图像匹配技术已成为遥感地形、图像处理、图像识别、 计算机视觉等领域的关键技术［１］。现有的基于面积、基于相位等算法对尺度变换、视角变换、遮挡等情况匹配效果均不理想。提取图像视觉特征内容能够根据图像内容进行匹配,获得较准确的匹配效果［２］。但由于全局特征不能很好地描述图像局部信息,因此匹配精度并不高,而SIFT特征具有旋转及尺度不变性,对于光线明暗变换、视角变换、缩放、遮挡等情况具有很好的鲁棒性［３］。本文对SIFT算法进行分析研究,获取SIFT特征进行图像匹配,实验表明SIFT算法在缩放、明暗、旋转、遮挡等情况下具有较好的匹配效果。

1 SIFT算法描述

SIFT特征考虑了在规模较大的图像库中可能具有多视角特征点的图像,且有较强的抗干扰性能,对于噪声干扰图像处理效果较好［４］。获取一幅图像SIFT特征的方法实质上就是将图像特征转变为多个点特征的集合,这个集合就是整个图像的SIFT特征,集合中每个特征分量都具有鲁棒性。图像SIFT特征向量的算法步骤如下:

1.1构造尺度空间

尺度空间实质上是引入不同的尺度参数,获得图像数据在不同尺度下的视觉内容细节,从而准确地挖掘图像视觉特征［５］。图像I(x,y)通过高斯函数获得不同尺度的LOG图像。

上式中G(x,y,σ)代表不同尺度相对的高斯函数,σ 为高斯尺度参数,代表该高斯图像的平滑度,其值大则表示在该尺度下的高斯图像较为平滑,即主要信息为原图像的概况信息;而σ值较小则表示该尺度参数对应的高斯图像包含的原图像的高频成分,即细节信息较多,因此这样的高斯尺度图像也较为清晰［６］。特征点的检测通常在差分金字塔空间即DOG空间中完成,实质上由LOG图像进行差分,可以得到DOG图像,公式如下:

SIFT算法在使用高斯函数获得尺度空间的同时原图像也会由于高斯平滑而丢失高频信息,从而引起图像失真。为了获得尺度空间,同时保证图像质量,必须在构造高斯尺度空间前将原图像进行放大处理,从而增加特征点数量。

1.2检测DOG空间极值点

在DOG空间检测其极大值点和极小值点作为图像特征点。尺度空间的极小值点和极大值点通过每个待测点与其本尺度和相邻两个尺度上3*3邻域内的所有像素点进行比较得到,若该待测点的值为最大或最小时,则判断该待测点为一个特征点。

1.3去除不准确的特征点

通过检测DOG空间的极大值和极小值仅能初步确定特征点位置,其精确度仅为像素精度［７］,并不准确,特征点中对比度较低或者对边缘响应稳定性较差的点被认为是非特征点需要删除。删除对比度低的点需要引入泰勒函数,从而获得每个极值的位置X’,若X′ >0.03,那么这个点就是对比度较低的非特征点;另一方面,去除不稳定边缘点则可使用曲率概念和DOG相结合的方法,从而构建一个2*2的海森矩阵,通过其轨迹(trace)以及行列式(determinant)进行推导,从而可获得:

其中,r为主曲率阈值,选择一定阈值,如果特征点不满足式(5),则表示该点为不稳定的边缘点,被认为是非特征点。

1.4确定特征点的方向

特征点的方向需根据特征点的邻域像素确定,以便于后续对图像进行的分析转换为对特征点尺度和方向的分析［８］。可根据高斯尺度图像(LOG)获得像素点的幅值以及方向,如下所示:

式(4)为点(x,y)处梯度方向幅值,而式(5)则表示点(x,y)处的方向。

1.5获取特征点梯度直方图

特征点描述通常采用一个4×4的网格作为特征点的邻域［９］,统计每一格中每45°共8个方向的信息,因此就构成了一个128维的特征描述向量,具体步骤如下:

(1)取特征点周围16×16的邻域作为采样窗口;

(2)将采样窗口中像素点归入4×4的网格,每格子就是描述子的一个种子,同一网格中的所有像素点之和就是描述子在该种子的值;

(3)每个网格中每45°设置一个方向,共8个方向,将采样点和特征点之间的相对方向根据高斯加权后归类到对应的每个网格的8个方向中,同一个格子中所有点在这8个方向上的分量作为描述子在该网格的值,这里使用采样点与特征点的相对方向构建方向直方图,从而保证SIFT特征的旋转不变性;

(4)由步骤(2)、(3)就能得到16个网格的8个方向的分量,也即特征点的梯度直方图,也就是特征点的SIFT特征描述。

2 SIFT特征点匹配

特征点的相似性通过计算两个特征点的SIFT特征向量即梯度直方图的欧氏距离获得。如果两个点的相似性小于一定的比例阈值,则判断这两个点为一对匹配的特征点。通过调整阈值可以调整获得的匹配点数量。阈值越低,则获得的匹配结果越稳定,同时匹配点的数目会越小;阈值越高则反之。

3实验结果与分析

针对SIFT算法,本文设计了5组实验以证明SIFT算法在图像匹配方面的有效性,实验中过滤不稳定的边缘点所使用的曲率半径。

图3展示了以lena图像作为测试图像的SIFT特征点以及特征点的描述向量。图3(b)为通过极值检测初步获得的特征点,图3(c)为去除了不稳定和对比度低的点后精确的特征点,图3(d)为特征点位置方向信息。可见SIFT算法可以有效确定图像特征点以及特征点的位置方向,从而有利于生成SIFT描述向量。

图4为由尺度缩放而来的两幅原图的匹配结果,其中左图采用SIFT算法获取了428个特征点,右图采用SIFT算法获取了330个特征点,连线的两端为匹配成功的一对特征点。由此可见,对于内容相同而缩放大小不同的两图图像,SIFT算法大部分特征点可以正确匹配,少数几个不能正确匹配,因而该算法对尺度缩放变换保持较好的稳定性。

图3是两幅亮度不同环境下拍摄的同一物体的匹配结果,虽然图像明亮有变化,但仍能成功匹配,由此可见, SIFT算法的图像匹配方法对于亮度变化保持稳定性,可降低光照的影响。

图4显示原图旋转90°且被部分遮挡的情况下仍然有较好的匹配结果,显示了SIFT算法较好的方向性及稳定性。

4结语

本文分析SIFT算法原理,研究基于SIFT特征的图像匹配方法,最后设计实验提取不同图像的SIFT特征,并且进行匹配,分别从尺度缩放变换、亮度变换、视角变化和遮挡等方面证明其匹配的稳定性和鲁棒性。实验表明,尽管图像发生了很大的视角变化、遮挡、尺度变化和亮度变化,但仍然能够匹配成功,证明了基于SIFT特征的图像相匹配方法是有效的,且SIFT特征匹配的准确性和稳定程度较高。

SIFT特征匹配算法 篇2

图像匹配技术是图像处理和计算机视觉领域的一项重要技术。图像匹配,就是在机器识别事物的过程中,将已知图像与陌生图像的全部或部分在空间上对准,根据已知模式的图像在一幅陌生图像中寻找对应该模式的子图像过程。图像匹配所涉及的应用领域包括工业检测、遥感地形匹配、光学和雷达图像跟踪、工业流水线自动监控、交通管理、医疗诊断、图像检索等诸多领域。

目前,图像匹配技术有基于与像素灰度相关的匹配、基于图像特征的匹配、基于语义网络的匹配以及基于神经网络和遗传算法的匹配等多类方法。近年来,基于局部不变量描述符的方法在图像匹配领域取得了显著进展。SIFT[1](scale invariant feature transform)方法是Lowe在2004年提出的一种局部不变特征点的提取方法。SIFT特征是图像的局部特征,对旋转、尺度缩放和亮度变化保持不变,对视角变化、仿射变换和噪声也保持一定程度的稳定性。SIFT还具有独特性、多量性和可扩展性等多项特点。基于SIFT特征的算法目前在图像拼接[2]、遥感图像[3]的配准等很多领域都得到了应用。

1 SIFT算法

SIFT是通过在图像的尺度空间内,将定位极值点作为匹配候选关键点,并提取极值点的方向参数,最后获得匹配所需关键点描述符的一种算法。使用SIFT算法实现图像匹配主要有以下几个步骤:

1.1 检测尺度空间极值点

尺度空间(Scale space)思想最早由Iijima于1962年提出,20世纪80年代Witkin和Koenderink[4]的奠基性工作使得尺度空间方法获得较快发展。1994年Lindeberg等人建立的线性尺度空间方法被广泛采用[5,6]。

尺度空间方法的基本思想是:在视觉信息的处理过程中引入一个尺度参数,通过连续变化的尺度参数获得不同尺度下的视觉处理信息,然后综合这些信息以便深入挖掘图像的本质特征[5]。

给定图像I(x,y),其所对应的尺度空间表示L(x,y)可以由一个卷积核和图像卷积得到[7]。

$\begin{array}{l}L(x,y;\delta )=g(x,y;\delta )*{\rm I}(x,y)(1)\\ g(x,y;\delta )=\frac{1}{2\text{π}\delta {}^2}\text{e}{}^{-(x{}^2+y{}^2)/(2\delta {}^2)}(2)\end{array}$

式中:g(x,y;δ)是高斯卷积核,也是尺度变换惟一的线性核[8],其中,δ是尺度参数,对应高斯核函数的方差,改变δ的值可以获得一组图像的尺度空间表示[2]。

对相邻尺度的图像做差分,可以获得一组DoG(difference of gauss)图像D(x,y;δ)。

$\begin{array}{l}D(x,y;\delta )=[g(x,y;k\delta )-g(x,y;\delta )]*{\rm I}(x,y)\\ =L(x,y;k\delta )-L(x,y;\delta )(3)\end{array}$

图像的空间极值点是该点与其相邻8个点及相邻两个尺度所对应位置的18个点共27个点中的最大值点[9],如图1所示。

1.2 精确定位极值点

DoG算子会产生较强的边缘响应,且在1.1节中检测到的极值点精度为像素级。

通过拟合三维二次函数可以将极值点插值定位到亚像素精度。将D(x,y;δ)Taylor展开可得:

$D(x)=D+\frac{\partial D{}^{{\rm T}}}{\partial X}X+\frac{1}{2}X{}^{{\rm T}}\frac{\partial {}^{2}D}{\partial X{}^2}X(4)$

式中:D及其导数是采样点的估计值;X是距采样点的偏移量。此时,极大值点的位置X′可以由下式确定:

$X^{\prime }=-\frac{\partial D{}^{-1}}{\partial X{}^2}\cdot \frac{\partial D}{\partial X}(5)$

一个定义不好的高斯差分算子的极值在横跨边缘处有较大的主曲率,而在垂直边缘的方向有较小的主曲率。主曲率是通过一个2×2的Hessian矩阵H求出的。即:

$\mathit{{\rm H}}=\left[\begin{array}{cc}D{}_{xx}& D{}_{xy}\\ D{}_{xy}& D{}_{yy}\end{array}\right](6)$

导数由采样点相邻差估计得到。主曲率由H的特征值计算得出,令α为最大特征值,β为最小特征值,令α=rβ,则主曲率由下式确定:

$\frac{\text{Τ}\text{r}(\mathit{{\rm H}}){}^2}{\text{D}\text{e}\text{t}(\mathit{{\rm H}})}=\frac{(\alpha +\beta ){}^2}{\alpha \beta }=\frac{(r+1){}^2}{r}(7)$

选取合适的主曲率阈值,可以去除不稳定的边缘响应点,从而获得精确定位的极值点作为关键点。

1.3 指定关键点方向参数

利用关键点邻域像素的梯度方向分布特性为每个点指定方向参数,可以使算子具有旋转不变性。

梯度m(x,y)和方向θ(x,y)可以由下面的公式计算:

$\begin{array}{l}m(x,y)=\sqrt{[L(x+1,y)-L(x-1,y)]{}^2+[L(x,y+1)-L(x,y-1)]{}^2}\\ \theta (x,y)=a\text{t}\text{a}\text{n}2[(L(x,y+1)-L(x,y-1)]/[L(x+1,y)-L(x-1,y)]\}(8)\end{array}$

实际计算时,在以关键点为中心的邻域窗口内采样,并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360°,其中每10°为一个柱。直方图的峰值代表了该关键点处邻域梯度的主方向,即作为该关键点的方向。

当存在另一个相当于主峰值80%能量的峰值时,将这个方向认为是该关键点的辅方向。一个关键点可以被指定具有多个方向,这可以增强匹配的鲁棒性。

至此,每个关键点已经检测完毕,每个关键点具有3个信息:位置、所处尺度和方向,由此可以确定1个SIFT特征区域。

1.4 生成关键点描述符

先将坐标轴旋转为关键点的方向,以确保旋转不变性;再以关键点为中心取8×8的窗口,图2左边的中央黑点为当前关键点的位置,每个小格代表关键点邻域所在尺度空间的一个像素,箭头方向代表该像素的梯度方向,长度代表梯度模值,圆形区域为高斯加权范围;然后在4×4的小区域上计算8个方向的梯度方向直方图,绘制每个梯度方向的累加值,即可形成1个种子点,如图的右部分所示。此图中一个关键点由2×2共4个种子点组成,每个种子点共有8个方向向量信息。邻域方向性信息联合的思想增强了算法的抗噪声能力,同时对于含有定位误差的特征匹配提供了较好的容错性。

这样,对于一个关键点就可以产生2×2×8共32个数据,形成一个32维的特征向量。此时的SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响。再继续将特征向量规一化,可以去除光照变化的影响。

1.5 匹配

生成2幅图像的特征向量后,采用关键点特征向量的欧几里德距离作为两幅图像中关键点相似性的判定度量。取一幅图像中的某个关键点,并找出其与另一幅图像中距离最近的前2个关键点,在这两个关键点中,如果最近的距离除以次近距离小于某个阈值Th,则接受这一对匹配点。降低这个比例阈值,匹配点数量会减少,但匹配过程更稳定。反之,匹配点数量会增多,但稳定性随之会变得稍差。

1.6 实验及结果

在图3(a)和图3(b)中各包含了两幅图像,每幅图像大小均为326×245像素。其中,右边为待匹配物品的图像,左边为待匹配物品放入复杂场景后所形成的图像。图中连线的两端是两幅图像中对应的匹配点。

为了增强匹配的稳健性,在匹配过程中,对每个关键点使用4×4共16个种子点描述,这样对于一个关键点会产生一个128维的特征向量。匹配过程中采用阈值Th=0.6,在去除不稳定响应点时采用r=10。

在图3(a)左边的图像中,除了匹配区域的尺度有变化外,被匹配的目标区域还发生了遮挡,但未遮挡部分仍与右侧图像中的模板图像正确匹配。图3(b)中的待匹配图像区域是物体在发生约90°旋转后所形成的,此时仍能正确匹配。

2 结 语

通过原理分析和实验结果验证,用SIFT算法提取的匹配关键点是一种局部描述符。使用SIFT算法实现图像匹配具有对尺度变化、旋转、光照和视角变化的稳定性。当发生部分遮挡时,仍可实现有效匹配。基于SIFT特征点实现图像匹配是一种有效方法。SIFT可进一步应用于图像检索,视频跟踪等多个领域。

参考文献

[1]LOWE D.Distinctive image features from scale-invariantkeypoints[J].International Journal of Computer Vision,2004;60(2):91-110.

[2]张朝伟,周焰,吴思励,等.基于SIFT特征匹配的监控图像自动拼接[J].计算机应用,2008,28(1):191-194.

[3]李晓明,郑链,胡占义.基于SIFT特征的遥感影像自动配准[J].遥感学报,2006,10(6):885-891.

[4]WITKIN A P.Scale-space filtering[C]//Proc.7th Interna-tional Joint Conference on Artificial Intelligence.[S.l.]:IJ-CAI,1993:1019-1022.

[5]孙剑,徐宗本.计算机视觉中的尺度空间方法[J].工程数学学报,2005,22(6):951-962.

[6]LOWE D.Object recognition from local scale-invariant fea-tures[C]//International Conference on Computer Vision.Greece:ICCV,1999:1150-1157.

[7]LINDEBERG T P.Internal report TRI TA-NA-P8808[R].Stockholm,Sweden:Royal Institute of Technology,2000.

[8]BABAUD J,WITKIN AP,BAUDIN M,et al.Uniquenessof the Gaussian kernel for scale-space filtering[J].IEEETransactions on Pattern Analysis and Machine Intelligence,1986,8(1):26-33.

[9]LINDEBERG Tony.discrete derivative approximations withscale-space properties:a basis for low-level feature extrac-tion[J].Journal of Mathematical Imaging and Vision,1993,3(4):349-376.

SIFT特征匹配算法 篇3

在特征点匹配研究领域中, 具有局部不变性的特征点的提取有三种流行方法, 分别是金字塔[1], 小波算法[2]和尺度空间方法[3]。其中尺度空间方法是目前生成局部不变量的最流行最有效的方法, 广泛应用于计算机视觉与图形图像处理等各个领域。基于尺度空间的匹配算法的步骤是首先对待匹配的图像进行特征点检测, 然后通过特征点及其邻域点设计局部不变量描述子, 最后通过这些描述子的匹配确定对应点。该算法能提取大量稳定的局部特征, 可以处理两幅图像之间发生平移、旋转、尺度、剪切、视角和光照变换下的匹配问题, 具有很强的鲁棒性。通过对多种基于局部不变量描述子的特征检测算法的总结, DavidG.Lowe在1999年提出了一种新的图像局部特征提取算法——SIFT算法[3], 并在2004年完善总结。与此同时, Mikolajczyk和Schmidml对这类方法的性能进行了测试[4], 分别在不同光照, 尺度, 旋转, 剪切, 图像模糊和压缩等六种情况下, 对多种最具代表性的特征描述子进行了性能评价, 实验结果表明, SIFT描述子的性能最好。如今, SIFT算法已经在图像拼接、图像匹配、模式识别等方面得到了广泛的应用。

SIFT算法的实现过程主要分为四个步骤, 第1个步骤是建立图像的尺度空间, 通过构造图像的高斯金字塔分层结构, 对采样点与周围局部区域内2 6个点进行比较, 将结果作为候选特征点;第2个步骤通过消除边缘响应去掉不稳定点, 得到稳定特征点;第3个步骤利用特征点邻域像素的梯度方向分布特性为每个特征点指定方向参数, 这时, 特征点已经具备尺度、位置、方向等相关信息;第4个步骤是组织这些信息形成特征描述符, 并实现匹配。

一般认为, SIFT算法的效果主要取决于两个环节:

1) 寻找到稳定特征点的数量

2) 特征点的正确匹配率

针对影响SIFT算法效果的两个问题, 本文通过研究尺度选择理论, 改进尺度空间的构造过程, 证明了尺度选择与可找到特征点数目的关系, 并通过调整尺度选择与最优点选择策略, 在图像上寻找到更多的特征点;通过限制匹配点的尺度关系减小了错配概率, 并通过改进原始匹配策略提高了匹配算法的准确率。

2. 尺度空间构造与特征提取

2.1 尺度选择

尺度选择是构造尺度空间的一个关键问题, 它直接影响尺度空间的结构和应用尺度空间的特征提取算法的性能[5,6]。通过研究尺度选择理论, 我们可以改进尺度空间的构造过程, 从而找到更多的特征点。

SIFT算法通过运用尺度参数σ不同的高斯函数做差构造了高斯差分函数 (DOG) , DOG函数是拉普拉斯高斯函数 (LOG) 的近似[3]。LOG函数与一幅图像或者一个信号进行卷积, 并对其结果求同尺度内极值, 可以检测到该信号或图像的斑点 (BLOB) 点。我们先来简要分析斑点的分布, 为了使过程明确, 我们假设图像以参数曲线的形式出现:

给定任意参数曲线, 假设变换不同的σ, 得到X, Y参数和曲率K随参数T的变化规律如下图所示[7]:

横坐标是曲率参数T, 纵坐标是函数的函数值, 在不同尺度参数条件下, X, Y和曲率K的变化曲线, 可见随着尺度的增加, X, Y和曲率K的变化剧烈程度随着T的变化减弱。

设定M (弧长参数) 是一个可变正数, N (曲率参数) 是一个可变正数。

当T=M时, 不同σ参数作用下X, Y, K可能不同;

当K=N时, 不同σ参数条件下T可能不同;

当T=M时, K对应于不同σ条件下的不同值;取连续增长的σ和固定的T, 随着σ的增加, T与σ的对应点代表在不同σ的条件下K等于相同的N值点;取连续增长的T和固定的σ, 随着T的增加, T与σ的对应点代表在不同T的条件下K等于相同的N值点。所以可以得到在任意K=N的条件下, T与σ的对应关系如图下所示[7]:

横坐标是曲率参数T, 纵坐标是尺度参数σ。对于某一参数T, 所对应的σ是有限的。当σ大于σmax, 将检测不到特征点。

可知, 随着σ的增加, 将存在σmax使得对于任意T弧长所能对应的K=N最多, 对于σ>σmax, 取固定的T和连续增加的σ都无法产生与T对应的K=N点;同理, 存在σmin, 对于σmin<σ<σmax, σ连续变化对应着离散的K=N值, σ从M I N到M A X变化区间中采样频率越高, K=N值点概率越大。所以若找到对于某一K=N值点对应的T-SIGMA坐标, 需要取集合{σ1, σ2.....σk}, 其中σ2-σ1=无穷小, σ1<=σmin, σk>=σmax。

高斯尺度空间对一幅图像的特征点的检测集中在某些连续的尺度之内, 小于或大于这个尺度区间的BLOB点或区域将无法被检测到。而这个由特定的最小尺度值和最大尺度值构成的特征区间就是BLOB区域的检测区间, 这个区域的大小由BLOB点或区域的自身结构决定[5,6]。对于一幅图像来说, 其所有BLOB点或区域为定值, 所以其整体的检测区间为定值。对于任意图像来说, 检测区间不确定, 可以根据统计规律得出历史的最大值与最小值作为经验检测区间, 由于我们并不一定能够知道任意图像或某一类型图像的经验检测区间。所以一般我们需要通过快速搜索的办法来估计一幅图像的检测区间。

我们根据LOWE算法的经验值选取一个初始检测区间, 以2倍速度增长该区间, 当在连续增长3次时无新的特征点出现, 我们便认为该区间的上限为整体检测区间的上限, 同理确定检测区间的下限。由于LOG函数的跨尺度极值检测到的是原图像的斑点或者斑点区域。随着图像结构的不同, 一个斑点区域在尺度空间的不同尺度内表现出的结果也不同:

灰度信息特征越明显, 特征点检测过程中被检测到的概率就越高。灰度信息变化越剧烈, 特征点的检测概率即稳定性就越高。

因此, 当我们设置一个阈值Threshold, 当Maxima of the DOG>threshold, 我们认为它是该图像的一个稳定的斑点。阈值越大, 代表该斑点越稳定, 但是相应的所找到的特征点数量也越少。

2.2 实验结果与分析

基于尺度空间改造的方法, 我们通过图像的特征提取实验来观察尺度空间改造前后所提取的特征点数量的变化, 并判断所找到的特征点是否稳定, 能够有效匹配。

实验图像来自3 D网格表面模型 (图1-3a) , 我们选定该3D人脸模型上两组完整人脸深度图像进行特征提取实验, 如图所示, 图1-3 b与图1-3 c即为两张完整人脸深度图像, 它们有比较大的共同部分, 但图1-3b包括更多的头发与额头部分, 而图1-3c包括更多的下颌部分。通过基于原始尺度空间的sift算法在两幅图像上分别找到3, 4个特征点, 可以正确匹配的对应点为3对:通过基于改进尺度空间的sift算法在两幅图像上分别找到1 9, 1 7个特征点, 可以正确匹配的对应点为12对。说明我们通过改造尺度空间, 不仅在该图像上找到了更多的特征点, 并且保证所找到的特征点性质稳定, 能够有效匹配。

3. 特征描述子匹配

3.1 SIFT描述子

原始SIFT匹配方法是首先将坐标轴旋转为特征点的方向, 以确保旋转不变性。接下来以特征点为中心取8×8的窗口。中央黑点为特征点, 每个格子代表尺度空间中特征点邻域的一个像素, 小箭头代表该像素的梯度方向, 小箭头长度代表梯度模值, 蓝色圆代表高斯加权的范围。在每4×4的小块上计算8个方向的梯度方向直方图, 绘制每个梯度方向的累加值, 即可形成一个种子点[8], 如图所示。此图中一个关键点由2×2共4个种子点组成, 每个种子点有8个方向向量信息。这种邻域方向信息聚合的思想增强了算法抗干扰的能力。

一个关键点由2×2共4个种子点组成, 每个种子点有8个方向向量信息

为了增强匹配的稳健性, Lowe对每个关键点使用4×4共16个种子点来描述, 每个种子点有8个方向向量信息, 依次顺时针排列, 那么一个关键点可以产生4×4×8=128个数据, 即最终形成128维的SIFT特征向量。

当两幅图像的SIFT特征向量生成后, 我们采用特征点特征向量的欧式距离作为两幅图像中特征点的相似性判定度量。即:d (PQ) =||Pi-Qj||, Pi and Qj是两个特征点的具有1 2 8维特征向量。

取图像1中的某个特征点, 找出其与图像2中欧式距离最近的前两个特征点, 在这两个特征点中, 如果最近的距离除以次近的距离少于某个比例阈值, 即

thresh*best<=second_best,

则接受这一对匹配点。比例阀值与SIFT匹配特征点即对应点的数量及稳定性都成正比。

3.2 SIFT描述子匹配改进方法

在实际匹配实验中, 我们常常会遇到这种情况:两个特征点并不对应, 最近距离比较大, 但是由于次近距离更大反而导致比值较小, 出现错误匹配, 如图3-2所示:

A是左图上找到的特征点, B, C是右图上找到的特征点, 点A与点C的匹配是错误的, 其中d (AC) 比较大, 但是由于d (AB) 更大, 所以仍然满足d (AC) /d (AB) <thresh, 出现错配。

所以我们对最近距离 (best) 的范围进行了限制。

如果一个特征点所具有的特征结构比较明显, 那么在该图像中重复找到该点的概率就较大, 当图像发生光照和放射等变化后找到该点的概率也较大, 此时我们称该特征点比较稳定。稳定的特征点和不稳定的特征点结构的明显程度可能不同, 但在结构的特征上可以相似, 体现在图像上就是特征点和其周围的邻域相似, 这可能导致在sift特征提取过程中, 寻找到不够稳定的特征点, 或者找到的特征点由于周围信息较为相似而导致在匹配过程中出现误匹配。

点B与点D之间匹配为错误匹配, 点B与点E在相近尺度上找到, 点D是在与点B相差较远的尺度上找到的, 但是由于B, D, E三点的邻域所提取的128维特征向量较为相近, 导致d (BD) 与d (BE) 都比较小, 出现错配。

所以我们考虑通过限制匹配点的尺度比值来减少错配。两幅图像中的每一个特征点所在的尺度都在该图像的检测区间中, 即尺度值大于检测区间的最小尺度, 小于检测区间的最大尺度。所以两幅图像特征点的尺度比值会在 (σmin, σmax) 区间中, 于是, 设有n对匹配特征点, 每一对匹配特征点的尺度分别为pi, 则应有

所以在特征点进行特征描述与匹配后, 我们根据公式1, 2对匹配点的尺度比值进行检测, 排除误匹配点。

3.3 实验结果与分析

我们选定松鼠灰度图像作为特征描述匹配的实验图像, 首先实现基于原sift描述子及匹配方法的的结果, 然后实现对尺度比值范围进行限制的结果, 同时实现对最近距离的范围进行限制的结果, 结果如图2-4所示。

分别计算三幅图中的正确匹配点数, 错误匹配点数与正确匹配率, 如表2所示。

可以看出, 限制尺度比值后, 松鼠头部的错配点已经消除, 正确匹配率是71.40%, 比原sift提高了7.8 0%, 限制尺度并限制最近距离后, 尾部的错误匹配点消失, 正确匹配率提高到100%。

4. 未来的工作

本文通过改进sift算法, 不仅增多了寻找到特征点的数量, 还提高了正确匹配率, 这就为特征匹配、模式识别等具体应用提供了良好基础, 在下一步工作中, 我们会进一步改进尺度空间构造过程中的尺度选择方法, 通过观察尺度空间中特征点的分布情况来构造一个细化选择尺度的策略, 以此来寻找更多更稳定的特征点, 并将此方法应用到特征提取与匹配算法中。

摘要：图像特征提取与匹配是计算机视觉、图形图像领域的一个重要问题, 具有仿射不变性、光照不变性、部分遮挡不变性的特征, 提取和匹配是这个问题的核心内容。尺度空间技术是具备了多尺度分析技术众多优点的新兴技术, SIFT (Scale Invariant Feature Transform) 算法是线性尺度空间技术的一个成功应用。对于如何在一帧图像中运用尺度空间技术手段寻找更多的特征点、以及如何对特征点进行准确的描述与正确的匹配是该领域的难点, 尤其前者在近年内进展缓慢。文章通过论述尺度空间的构造过程, 证明了尺度选择与可找到特征点数目和位置的关系, 通过调整尺度选择与最优点选择策略, 在图像上寻找到更多的特征点, 并根据判据量化判定了特征点的稳定性;通过限制匹配点的尺度关系减小了错配概率, 通过改进原始匹配策略提高了匹配算法的准确率。实验表明, 改进后的SIFT能够比传统的SIFT找到更多的特征点, 提高了匹配的准确率, 算法的鲁棒性得到了进一步提高。

关键词：尺度空间,SIFT,尺度选择,特征提取,特征匹配

参考文献

[1]SG.Mallat.A theory for multiresolution:The wavelet representation.IEEETrans, Pattern Analysis and Machine Intell, vol11, 1989:673一694

[2]JMorlet, GAiens, 1Forgeau, DGiard.Wave ProPagation and SamPling Theory.GeoPhysies, 1982 (47) :202一236

[3]Lowe, D.G.1999.Object recognition from local scale-invariant features.In International Conference on Computer Vision, Corfu, Greece, pp.1150-1157

[4]Mikolajczyk, K.and Schmid, C.:Scale and affine invariant interest point detectors, Int.Journal of Computer Vision, 60:1, 63-86, 2004

[5]Lindeberg, T.1993.Detecting salient blob-like image structures and their scales with a scale-space primal sketch:a method for focus-of-attention.International Journal of Computer Vision, 11 (3) :283-318

[6]Lindeberg, T.1994.Scale-space theory:A basic tool for analysing structures at different scales.Journal of Applied Statistics, 21 (2) :224-270

[7]T.Lindeberg.Scale-Space Theory in Computer Vision.TheKluwer International Series in Engineering and Computer Science.Kluwer Academic Publishers, Dordrecht, the Netherlands, 1994.2, 19

SIFT特征匹配算法 篇4

关键词：特征匹配,尺度特征不变算法,邻域特征描述子,高维特征矢量

图像匹配是图像处理和机器视觉中重要的研究内容。在目标跟踪、目标识别、图像拼接等领域广泛应用[1]。特征匹配和灰度匹配是图像匹配的两种方法。特征匹配可以减少灰度匹配在匹配过程的计算量。同时,能够减少噪声的影响,提高匹配的精确程度,成为图像匹配的主要方法[2]。

2004年Lowe提出了SIFT[3](Scale Invariant Feature Transform)局部特征,利用金字塔和高斯核滤波差分来快速地求解高斯拉普拉斯空间中的极值点,加快了特征提取的速度。SIFT特征在尺度变换和仿射变换的条件下都有很好的鲁棒性。为改进其特征点的128维描述子在匹配过程中计算量太大的缺点,进一步提高SIFT的匹配效果。很多学者提出了改进算法。Ye和Suktinankar提出PCA-SIFT[4]。与SIFT相比,在保留特征不变性的同时,特征矢量维数降低,使得特征点匹配速度大大提高。但需要一组典型图像的学习,计算的投影矩阵只适应于同类的输入图像。Mikolajczyk提出了GlOH[5]描述子,在对数-极坐标上计算16个方向上的梯度方向直方图,并通过PCA降维形成128维特征向量。与PCA-SIFT类似,GOLH也需要大量的样本进行学习。Moreno P等采用Gabor滤波器改进SIFT特征描述子[6],使其提高了特征匹配的精确度,但算法的复杂性增加。C. Singh等人采用Zernike矩对SIFT算法进行改进[7],当仿射变换程度较大时,SIFT特征描述子的相关性能最佳[8]。

文中针对SIFT局部特征高维特征描述子进行了降维,增强了特征点邻域像素信息,改善了匹配速率和匹配效果。

1SIFT特征检测与匹配算法

尺度不变特征检测与匹配包括以下步骤:尺度空间的建立及关键点检测、关键点定位、关键点方向分配、关键点特描述子生成以及关键点特征匹配。

1.1尺度空间的建立及关键点的检测

图像的尺度空间可表示成一个函数L(x,y,σ),它是由一个变尺度的高斯函数G(x,y,σ)与图像I(x,y)卷积产生的。即

L(x,y,σ)= G(x,y,σ)⨂I(x,y) (1)

SIFT算法建议,在某一尺度上对关键点的检测,可以通过对两个相邻高斯尺度空间的图像尺度函数L(x,y,σ)相减,得到一个DoG (Difference of Gaussians)的响应值图像D(x,y,σ)。通过对响应图像D(x,y,σ)进行非最大值抑制(局部极大搜索),在位置空间和尺度空间中定位关键点。其中

D(x,y,σ)=(G(x,y,σ)- G(x,y,σ))⨂I(x,y)= L(x,y,kσ)- L(x,y,σ) (2)

1.2关键点定位

检测到的候选关键点还需要删除响应过小的点和边缘效应的点,才能确定关键点。

极值点的搜索是在离散空间中进行的,检测到的极值点并不是真正意义上的极值点。为此,通过用离散空间的极值点插值得到连续空间的极值点。利用二维函数二阶泰勒展开式进行插值$D(X)=D+\frac{\partial D{}^{\text{Τ}}}{\partial X}X+\frac{1}{2}X{}^{\text{Τ}}\frac{\partial {}^{2}D}{\partial {}^{2}X}X$。当X在任何方向上的偏移大于0.5时,意味着插值中心已经偏移到它的邻近点上,所以这样的点要删除。另外,当|D(X)|<0.03时,其相应值过小,这样的点易受噪声的干扰而变得不稳定,这样的点也删除。

通过Hessian矩阵H的特征值与D的主曲率成比例可以删除有边缘效应的关键点。其中

${\rm H}=\left[\begin{array}{cc}D{}_{xx}& D{}_{xy}\\ D{}_{xy}& D{}_{yy}\end{array}\right](3)$

α、β是矩阵H的特征值,则

$\frac{\text{Τ}\text{r}({\rm H}){}^2}{\text{D}\text{e}\text{t}({\rm H})}=\frac{(\alpha +\beta ){}^2}{\alpha \beta }=\frac{(\gamma \beta +\beta ){}^2}{\gamma \beta {}^2}=\frac{(\gamma +1){}^2}{\gamma }(4)$

因此要检验主曲率的比率低于某一个阈值,只需检验$\frac{\text{Τ}\text{r}({\rm H}){}^2}{\text{D}\text{e}\text{t}({\rm H})}<\frac{(\gamma +1){}^2}{\gamma }$。当不等式不成立时,则删除该点。

1.3关键点方向分配

为了实现图像旋转的不变性,需要根据检测到的关键点的局部图像结构求得一个方向基准。使用有限差分,计算以特征点为中心,以3×1.5σ为半径的区域内图像梯度的幅角和幅值。计算公式如下

$m(x,y)=\{L(x+1,y)-L[x-1,y)]{}^2+[L(x,y+1)-L(x,y-1)]{}^2\}{}^{\frac{1}{2}}$;

$\theta (x,y)=\arctan \left(\frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1,y)}\right)(5)$

统计梯度直方图,每10°为一个格子,共36个格子。直方图的峰值代表了该关键点的主方向。

1.4特征点特征矢量生成

将坐标轴旋转至关键点的主方向,在特征点的16×16邻域内等间隔划分4×4的子区域。每个子区域计算8个方向的梯度直方图,绘制每个梯度方向高斯加权后进行累加,形成一个种子点。由于存在4×4个子区域,所以共有4×4×8=128个数据,最终形成128维的SIFT特征矢量。

1.5关键点特征匹配

关键点匹配时,用欧式距离度量两幅图像关键点的相似性,采用穷尽搜索的方法对特征点进行匹配,并用比值提纯法对匹配结果进行提纯。在待匹配图像中找到关键点N1,与N1最近邻的点记为N2,次近邻的点记为N3,记Dij表示两个关键点之间的距离,如果距离比$\frac{D{}_{12}}{D{}_{13}}$大于某个阈值TH,则认为N1与N2相匹配,否则则没有匹配点。

2 改进的SIFT算法

通过在高斯差分尺度空间内检测并确定关键点,SIFT算法达到了尺度和旋转不变性的要求。但由于128维特征描述子在关键点匹配的过程中时间开销较大,使算法不能满足实时性的要求。故针对高维特征描述子进行改进。SIFT算法中联合邻域方向性特征的思想增强了算法的抗噪能力,改善了算法的鲁棒性。也将采用邻域特征构造特征描述子。

改进的64维特征描述子构造方法:以关键点为中心,八邻域向外扩展三个像素为第一组,计算像素的梯度幅值和幅角,幅角以每22.5°为一个格,统计16个方向分组的梯度幅值累加和。以此类推在上一组的8邻域方向上继续扩展三个像素,得到第三、第四组邻域圈,如图2所示。为简化,仅取两组邻域,得到两组梯度方向值。为避免特征描述子的误差过大,统计梯度直方图前,对关键点邻域进行高斯加权,以减少距离关键点较远的像素对关键点特征描述的影响。将第一组得到的16个方向的梯度幅值累加和作为新特征描述子向量的第1到第16个元素,第二组的累加和作为向量的第17到第32个元素。依此类推,将四组梯度幅值累加和排为16×4=64元素的特征描述子向量。新特征描述子向量将维数由128维降到64维,包含邻域像素为25×25,大于原算法邻域面积。

将第一组16个方向的累加值作为特征描述子的第1到第16个元素,以此类推,得到的描述子为16×4=64维的特征描述子。选取的特征点邻域为25×25像素尺寸,大于原邻域16×16的范围,增大了邻域像素的信息量,而特征描述子的维数小于原特征描述子。特征描述子统计16个方向分组的梯度幅值累加和,使特征描述更为准确。由于穷尽搜索的匹配方法没有利用数据的结构特征,在高维空间进行特征匹配时计算量大,时间开销大,文中采用基于BBF的Kd-树对特征匹配过程进行改进。对匹配的结果采用比值提纯法进行提纯,以提高特征匹配的精度。

3 实验结果及分析

实验平台为Windows XP操作系统,CPU主频2.0GHz,内存1G的个人电脑,编程环境为VC6.0集成开发环境。采用多种图像进行实验,并对图像进行旋转、尺度变换检测算法的性能。采用欧氏距离度量关键点之间的相似性,遍历图像中关键点的特征描述子,采用基于BBF的Kd-树进行关键点匹配,并使用比值提纯法对匹配结果进行提纯。图像的初始尺度σ=1.6,尺度空间各层迭代关系为σ=σ×21/S,其中S=5。

通过实验,改进的SIFT算法的匹配速率比原算法提高5%到15%(见图3),特征匹配的准确率(见图4)与原算法相近。

分析实验结果,在待匹配关键点数量比较少时,改进算法在匹配速率上并没有明显提高,这是因为新的算法在采用基于BBF的Kd-树进行关键点匹配时,与原算法相比增加了建立Kd-树的时间。当待匹配的关键点数量增加时,由于Kd-树利用了高维特征向量的数据结构,匹配速率明显加快。

通过实验,表明当图像比较复杂,特征描述子数量比较多时,改进算法与原算法相比提高了正确匹配率。

以下是三组实验结果。

(1)实验一的图片视角和大小完全相同,两种算法的匹配结果如图5所示。表1列举了原算法与改进算法检测到的关键点个数、关键点匹配正确率以及关键点匹配所用时间。

由实验一可见,改进后算法与原算法匹配正确率大致相同,匹配速度有明显提高。

(2)实验二使匹配图片旋转任意角度,两种算法的匹配结果如图6所示。表2列举了两种算法匹配结果的比较情况。

实验二可见,改进的SIFT算法,对图像的旋转变换具有一定的适应能力。

(3)实验三使匹配图片压缩或放大任意倍数,两种算法的匹配结果如图7所示。表3列举了两种算法匹配结果的对比。

实验三表明,改进算法对图像的尺度变换具有较好的抗干扰能力。新的特征描述子扩展了关键点邻域范围,使特征描述子更加独特,对有较多局部相似的区域,可以降低其误匹配。

4 结语

改进的SIFT算法构造的64维特征描述子,较原算法降低了特征描述子的维数。增加了关键点邻域的统计范围,增强了邻域信息。实验表明,改进的SIFT算法的匹配速率比原算法提高5%到15%。如果图像特征复杂,有多个局部相似的区域,改进的特征描述子相对原算法的描述子有更好的特征独特性。较SIFT算法提高的正确匹配率,提高了匹配精度。

参考文献

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

[2]刘萍萍,赵宏伟,臧雪柏,等.一种快速局部特征描述算法.自动化学报,2010;36(1):40-45

[3]Lowe D G.Distinctive image features from scale-invariant key-points.International Journal of Computer Vision,2004;60(2):91-110

[4]Ye K,Suktinankar R.PCA-SIFT:A more distinctive representationfor local image descriptors.In:Proceedings of the Conference on Com-puter Vision and Pattern Recognition,Washington,USA:IEEE,2004;1:511-517

[5]Mikolajczyk K,Schmid C.Aperformance evaluation of local descrip-tors.IEEE transactions on pattern analysis and machine intelligence,2005;27(10):1615-1630

[6]Moreno P,Bernardino A,Victor S J.Improving the SIFT descriptorwith smooth derivative filters.Pattern Recognition Letters,2009;30(1):18-26

[7]Singh C,Walia E.Fast and numerically stable methods for the com-putation of Zernike moments.Pattern Recognition,2010;43(7):2497-2506

SIFT特征匹配算法 篇5

视频图像序列中的运动目标检测是许多视觉系统中一个基础的部分[1〗。在监控应用中,识别非静态区域是所有更高层处理的前提,如目标识别、跟踪、行为分析等。许多算法是建立在背景模型的基础上进行的,前景是由观察图像和存储的背景之间的统计差异确定的。

目标检测主要有两种模式:摄像机静止—目标运动和摄像机运动—目标运动[2]。对于视频监控任务,图像通常是静止的,因此,背景模型已知,目标检测相对容易。背景模型估计和背景差技术在这种情况下得到广泛应用。摄像机运动时,由于摄像机运动产生了背景运动,使得运动目标检测任务变得更有挑战性[3]。静止摄像机情况下的目标检测跟踪技术已经比较成熟,运动摄像机情况下的目标检测和跟踪还在发展中。许多重要的应用,如机器人导航、航拍图像的目标检测跟踪、视频压缩等等,都与运动摄像机情况下的目标检测跟踪密不可分。

在国外,1992年就有人开始研究运动摄像机情况下的运动目标检测,而国内的研究处于起步阶段,下面介绍一下国内外的研究现状:文献[4]等人提出了基于运动矢量置信测量度目标跟踪的算法,该算法由于引进了置信水平测量,达到了更精确的全局估计,减小了变化检测的背景补偿误差。但是此算法在求运动矢量时用的是块匹配法,准确性不能保证,而且用帧差检测运动目标,检测的结果缺少完整性。文献[5]等用前向后向运动历史图定位热成像图中的运动目标,缺点在于运动历史图的产生需要若干帧,所以在检测过程中要引进一个检测的滞后,这对高速运动目标的检测是不适合的。文献[6]等提出的基于稀疏采样的局部补偿误差函数泰勒展开算法,它能快速的寻找出背景运动的仿射模型参数,在寻找相邻两帧之间的对应点时,采用的是图像匹配算法,由于这个算法是通过对不同邻域内的运动矢量做聚类运算得到的最终的目标定位,故对于不同的邻域或同一邻域内运动矢量差异较大的块,都将被视为不同的运动目标。此方法易受光照、噪声、矢量聚类的门限以及设定的步长的影响。文献[7]等提出的基于鲁棒背景运动补偿的运动目标检测,该算法能有效消除摄像机运动引起的背景运动,在摄像机运动的情况下得到完整的目标。此算法是在补偿后的前一帧和当前帧之间做光流,用光流的大小判定前景和背景,而光流易受光照和灰度等级变化的影响,在判断前景背景上容易出现问题,而且该算法计算复杂、运算时间长。文献[8]等人提出的动摄像机的自动目标识别与分类,用文献[9]的方法估计相邻两帧之间的光流,并假设目标没有覆盖图像的每个角落,在这样的情况下,图像角上显著的运动就是摄像机的运动。模型的参数可以通过线性最小二乘解来估计。如果出现异常(孤立点),线性最小二乘估计的性能就会变坏。像丢失特征、缺少背景纹理或者目标占据了一个角,都将成为异常(孤立点)。该算法用的也是易受影响的光流法,在选取点的问题上,选取的是四个角上不容易出现目标的点区域来求解仿射模型参数。如果目标出现在角上,就会使参数不准确,运动补偿失败。

针对运动摄像机情况下运动补偿中出现的难点:对应点选取的准确性和异常点剔除等,本文提出了基于SIFT[10]特征匹配的运动补偿技术,它能很好地解决上述问题,利用SIFT算法提取鲁棒的特征点(每个特征点用一个特征矢量表示)对图像的旋转、尺幅缩放、亮度变换等都保持不变的特点。建立特征点的KD-TREE,用两点间的欧氏距离快速准确地找出相邻两幅图像中的对应点。用RANSAC[11]算法剔除选在目标上的特征对应点,最后利用背景差实现目标的检测,同时进行阴影和鬼影的去除。采用背景动态更新模型的背景差算法完整地检测出了前景目标。

1 基于SIFT特征匹配的运动目标检测算法

整个检测算法主要包括SIFT特征点的提取与匹配、运动补偿及背景建模,如图1所示。首先,提取输入图像帧的特征点,用欧氏距离作为相似度准则,求得当前输入帧中特征点在前一帧中的匹配特征点,然后采用RANSAC的方法剔除选在目标上的异常特征点对,精确求得仿射模型的参数。最后,对前一帧更新后的背景帧作仿射变换,消除由于摄像机运动产生的背景运动,用当前帧和仿射变换后的背景帧作差,检测运动目标。为了使背景更新法则能够正常有效地运行,在处理过程中加入了阴影和鬼影的检测及去除,防止由于阴影或产生的鬼影的存在使整个更新过程恶化。

1.1 SIFT特征点提取与匹配

SIFT全称为尺度不变特征变换,其特征点的特征矢量具有很强的鲁棒性。它是一种提取局部特征的算法,可以把图像数据转化成尺度不变坐标的局部特征。

SIFT特征是图像的局部特征,其对旋转、尺度缩放、亮度变化保持不变性,对视角变化、仿射变换、噪声也保持一定的稳定性;独特性好,信息量丰富,适用于在海量特征数据库中进行快速、准确的匹配;多量性,即使少数的几个物体也可以产生大量的SIFT特征向量;高速性,经优化的SIFT匹配算法甚至可以达到实时的要求;可扩展性,可以很方便地与其他形式的特征向量进行联合。

SIFT主要算法步骤:检测尺度空间极值点;精确定位极值点;为每个关键点指定方向参数;关键点描述子的生成。

求出SIFT特征矢量后,采用欧氏距离判断两幅图像中关键点的相似性,在寻找两幅图像中最相似的两个对应点时,我们采用了KD-TREE的方式寻找。

1.2 全局运动补偿与背景建模

摄像机的运动状态主要包括左右转动、上下转动,焦距变化、追平追踪、垂直追踪等,而仿射变换具有平行线转换成平行线和有限点映射到有限点的一般特性,平移、旋转、缩放及反射等是二维仿射变换的特例,因此仿射变换一直是运动估计的标准模型,仿射模型有三参数、四参数、六参数等模型,参数越多,运动估计也就越准确,不过计算也就越复杂,为了既能准确地描述摄像机的运动,又能降低运算的复杂度,我们一般采用六参数仿射模型。

六参数的仿射模型如下:

其中fxt表示在t时刻的图像帧的x坐标,fyt表示在t时刻的图像帧的y坐标;(a0,a1,a3,a4)表示图像的旋转和缩放,(a2,a5)表示图像的平移。

前面求出的两幅图中的对应匹配点,一部分在背景上,另一部分在运动目标上。相对于背景来说,目标比较小,对应的匹配点个数也是少量的,但是如果用在运动模型中求解参数就会影响参数的准确性,因此在求解过程中需要采用RANSAC的方法来精确求解模型参数。

得到全局运动模型的参数后,对背景进行运动补偿。背景更新的基本原则是检测为前景的区域用仿射变换后的背景模型更新,检测为背景的用当前帧来更新,基本算法如下:

(1)背景初始化,用第一帧作为背景B0(x,y)。

(2)运动目标检测:

(3)背景更新法则:

其中B′t(x,y)=F(Bt-1(x,y)),F(·)表示仿射变换。M(x,y)表示背景差掩模。Th为检测前景目标的阈值。0表示背景区域,1表示前景区域。

1.3 阴影和鬼影的检测及去除

阴影去除结合了统计无参类(SNP)和确定非模型(DNM1和DNM2)两种方法,这两种方法能够快速有效地检测出阴影。阴影检测的基本原理:与背景相比,阴影具有相似的色度和更低的亮度。文献[12]等人的文章详细论述了统计无参类,该算法考虑人眼对颜色不变性的感知能力以及利用Lambertian假设把颜色作为辐射和反射的一种结果。计算亮度失真以及像素期望的色彩值和它当前图像中的色彩值之间的色度失真,利用得到的亮度失真和色度失真设定阈值把像素分为四类。文献[13]描述了一种DNM1,这个算法是基于HSV空间的,主要因为HSV空间更接近人对颜色的感知以及能够更准确辨别阴影[14]。作者利用阴影通常降低背景饱和度以及投射在背景上的阴影并不显著改变背景色度[15]的信息。阴影区域,背景差图中此区域设为背景像素,在背景更新时,这部分用仿射变换后的背景帧更新。

鬼影的检测结合了帧差图信息判断当前背景差结果图中前景块是否存在鬼影,鬼影在帧差图中是检测不到的。对背景差掩膜先进行膨胀,得出帧差图检测到目标的外边缘,再对其进行腐蚀,得到帧差图检测到的目标的内边缘,然后,膨胀和腐蚀后的掩膜做差,差值等于1的区域包含了帧差图中的目标轮廓,然后计算区域中总的像素个数和对应区域帧差图中为前景像素的个数。由于鬼影在帧差中是检测不到的,所以如果此块为前景,对应的帧差图中前景像素的个数几乎为零,如果是真的前景目标,则对应的帧差图中前景像素的个数将接近这块区域的总个数。如果判断为鬼影,在结果图中去掉此块,并在此块的位置用当前帧更新背景帧。鬼影检测过程如下:

其中Dilate(·)表示图像的膨胀操作,Erode(·)表示图像的腐蚀操作,Maskt(x,y)表示图像膨胀和腐蚀后作差的掩模。

设模板Maskt(x,y)中像素值为1的像素个数为N1,像素点(x,y)在模板Maskt(x,y)中像素值为1,并且在帧差图DFt(x,y)中检测为前景的像素个数为N2。

Ratio=N2/N1,如果Ratio大于设定的阈值,判定此块为前景,否则判定为鬼影块。

2 实验结果及分析

实验采用运动摄像机拍摄的分辨率为576×720的室内和室外场景中人和车辆的视频来检验算法的性能,为了减小每帧处理时间,实际处理时将图像转化为240×320处理。在VC2003.NET下,利用Intel Open CV,在Petium4 2.8G的PC机上实现算法。

在SIFT特征提取中,生成关键点描述子时,以关键点为中心取16×16的窗口,在4×4的小块上计算8个方向的梯度方向直方图,绘制梯度方向的累加值,形成一个种子点,这样每个关键点就有4×4共16个种子点,每个种子点有8个方向的信息,每个特征点的特征矢量也就是128维的。生成运动掩模的阈值Th为15。检测过程中同时进行阴影和鬼影的检测,并进行去除,消除在检测过程中可能产生的阴影和鬼影。在阴影检测中,统计无参类方法中设定亮度失真高门限1.2,消除由光照引起的误判前景判决门限,在1.0和1.2之间判定为光照;色度失真度低门限0.5,阴影判决门限,在0.5至1.0之间判定为阴影。如果RGB值都小于80,则不参与阴影检测。颜色失真度平方的门限设为300.0。非确定模型方法中的参数按照文献[15]中的参数设定。在鬼影检测中,Ratio设定为0.08,小于此阈值的则判为鬼影。

本文提出的基于SIFT特征匹配的算法和具有代表性的文献[8]等人提出的基于光流法目标检测进行对比。Ninad Thakoor算法,在四个角上距离边缘为10 pixel的区域选择了20×20区域共1600个点用来求解仿射变换模型参数,采用Lucas&Kanade算法求解光流。

图2-图4所示的实验图中,基于光流的算法显示的结果噪声比较多,是因为光流法受限制比较多,光流法除受光照影响比较大外,还受灰度等级的影响比较大,即一块表面平坦、颜色均匀一致区域的光流将会很小。这一算法在选取匹配特征点上是从四个角上选取,选取的特征点光流都比较小,得出的仿射模型参数不准确,在室内箱柜隔板等杂物比较多,室外高楼、树等复杂环境下和棱角比较多的情况下,最终的检测结果噪声必然会很大。而且帧差法只检测出目标的轮廓,目标有空洞、不够饱满。而采用的SIFT算法非常适应复杂环境,在复杂环境下,提取的环境中的不变特征点就会更多,目标上的特征点相对就越少,再用RANSAC算法剔除异常点,获得的仿射模型参数就更准确,在实验中出现的噪声就更少,检测到的目标就更准确,由于用的是背景差,检测出的目标饱满,适合继续跟踪。

图2-图4显示了两种算法的运动目标检测情况,从表1-表3可以看出基于SIFT特征匹配的算法平均耗时约为0.65s,而基于光流法的算法平均耗时为0.2s。相比之下,基于SIFT特征匹配的算法耗时比较大,这是因为提取稳定的特征点过程复杂,费时比较大。本文提出算法的优点在于利用鲁棒性的SIFT特征点进行匹配,并且用RANSAC方法剔除异常点,精确地求得仿射模型参数,并且动态更新背景,进行背景差,检测到清晰完整的目标。而基于光流的算法只做到了帧差,而且在复杂环境下,噪音特别大。

3 结论

本文提出的基于SIFT匹配和动态背景建模的运动摄像机目标检测算法,利用SIFT算法提取的稳定的特征点,采用KD-TREE有效而准确地建立匹配关系,利用RANSAC方法不断修正参数,剔除仿射模型估计中用到的异常点,极大地降低了参数的误差,提高了参数的准确度。对场景中的光线变化、背景干扰,甚至图像由于摄像机的运动而带来的变形都有很好的鲁棒性。由于算法耗时比较大,未来的工作就是优化算法,使之能够适应实时性。

摘要：运动摄像机情况下的运动目标检测是视频监控中的难点和热点问题。为了能够有效地检测出运动目标,提出了一个基于SIFT(Scale Invariant Feature Transform)特征匹配和动态背景建模的背景差算法。首先利用SIFT算法提取特征点,采用RANSAC(Random Sample Consensus)方法求得仿射变换模型参数并实现图像的全局运动补偿,然后用背景差方法实现运动目标的检测,同时进行阴影和鬼影的去除。SIFT特征点匹配的准确性和RANSAC方法去除异常点的有效性使得仿射变换模型参数计算准确,动态更新背景模型的背景差则完整地检测出了前景目标。与Ninad Thakoor实验结果对比说明:该算法能够准确地检测出运动目标,并且保持了前景目标的完整性。

SIFT特征匹配算法 篇6

图像匹配的方法大致上可以分为针对区域和针对特征两种类型。基于区域的匹配算法是对包含在该区域的所有像素进行匹配, 计算量较大, 而且对原始图像样本的旋转角度、光照条件有着较高的要求[1]。基于特征的匹配算法是对原始图像样本进行特征点提取, 寻找不同图片之间相同的特征点, 工作量较小。常见的算法有SIFT、SURF、Harris等, 其中SIFT算法相对于其他算法在图像尺度、视角变化、光照等方面的变化有较好的鲁棒性[2]。

1 SIFT算法

SIFT算法是David Lowe在1999年发表, 于2004年总结并提出的一种基于尺度空间的图像缩放、旋转方向变换保持不变性的特征匹配算法。其核心思路是首先构建尺度空间, 检测极值点, 获得尺度不变性。其次对特征点过滤并进行精确定位, 剔除不稳定的特征点, 并且在特征点处提取特征描述符, 为特征点分配方向值, 并生成特征描述子, 利用特征描述符寻找匹配点[3,4]。具体操作步骤如下:

(1) 尺度空间极值检测

在不同尺度参数σ变化时, 高斯函数G (x, y, σ) 和输入图像I (x, y) 卷积可以得到输入图像的尺度空间L (x, y, σ) :

其中σ是尺度因子, 该值越大图像被平滑得越大;该值越小图像被平滑得越小。

SIFT算法检测尺度空间主要采用Do G算子, 其中Do G算子定义为两个不同尺度的高斯核的差分。

(2) 特征点的方向分配

利用关键点邻域像素的梯度方向分布特征为每个关键点指定方向参数, 使算子具备旋转不变性。

上式为 (x, y) 处梯度的模值和方向公式, 其中L所用的尺度为每个关键点各自所在的尺度。

(3) SIFT特征向量

首先把坐标轴旋转为关键点的方向, 以确保旋转不变性。实际计算过程中对每个关键点使用16个种子点来描述, 这样对每一个关键点产生128维的SIFT特征向量, 从而提高匹配的稳定性。

(4) 特征点匹配

生成SIFT特征向量后, 查找每一个特征点在另外一个图像中的最邻近点, 也就是对两个样本进行特征向量相似度计算, 理想情况下两个样本之间相同部分的特征点应具有相同的特征向量。为了去掉因图像本身产生的没有匹配关系的特征点, 比较最临近距离和次邻近距离。当他们的比值小于设定的阈值时判定为错误匹配点, 将错误的匹配点去掉。

2 实验结果及分析

为了验证SIFT算法的特点本实验中采取了两组图片样本进行分析。

样本一为建筑风景图片。我们对该图片进行了局部裁剪, 然后进行等比放大, 属于局部放大图像匹配, 用来测试SIFT算法对几何变形的图像的匹配能力。

样本二为书本图片。我们对该原始样本进行了不同角度的拍摄, 具有较大的倾斜角度, 属于旋转图像匹配, 用来测试SIFT算法对不同方位的图像的匹配能力。

为了达到匹配感官度的统一性, 对一组样本中的前后两张图片均采用了相同的分辨率。本算法用MATLAB (2010a) 进行编程, 样本图片的比例阈值我们设为0.47, 结果如下图。

图1是第一组样本的匹配结果, 可以看出两张图像的SIFT特征的方向、尺度信息较为准确, 与直观观感判断相吻合。图2是第二组样本的匹配结果, 从图中可以看出两张图像中对应的SIFT特征得到了很好的匹配, 在较大旋转角度下SIFT算法保持了良好的方向性。对两组试验的具体数据进行统计, 可得表1。

由上表中可以看出SIFT特征匹配算法可以对不同方位、具有一定倾斜角度的图像进行准确的匹配, 体现出SIFT算法的特点。但是从第一组样本数据中可以看到, 随着图像复杂度增加, SIFT算法需要对各个尺度进行复杂度较高的计算, 因而计算用时会大幅度增加。

3 结语

本文利用SIFT算法的特征实现了二维图像的匹配, 验证了SIFT算法具有良好的尺度、旋转、光照等不变的特征, 其识别速度较慢等缺点可以通过与其他图像匹配算法的结合来弥补具有较好的研究价值。

摘要：SIFT算法是基于尺度空间的算法, 具有良好的尺度、旋转、光照等不变的特征。本文利用SIFT算法研究了二维图像匹配, 并对其结果进行了分析。

关键词：SIFT算法,尺度空间,图像匹配

参考文献

[1]吴建波, 赵新民, 朱信忠, 等.基于一种SIFT优化算法的图像检索[J].微型电脑应用, 2011, 27 (5) :4-7.

[2]孔晓东, 屈磊, 桂国富, 等.基于极约束和边缘点检测的图像密集匹配[J].计算机工程, 2004 (20) :178-179.

[3]Lowe D.Distinctive Image Feature from Scale-Invariant Key-points[J].International Journal of Computer Vision, 2004, 60 (2) :90-110.

SIFT特征匹配算法 篇7

1 SIFT特征提取算子

SIFT[2,3,4,5]算子全称是Scale Invariant Feature Transform, 即尺度不变特征。它首先在高斯差分多尺度空间检测特征点, 以确定特征点的位置和特征点所处的尺度, 然后用特征点邻域梯度的主方向作为该点的方向, 最后利用梯度直方图生成特征描述符。SIFT特征匹配算法的流程如图1所示.

利用SIFT算子提取的角点结果如图2:

2 特征点匹配

特征点匹配是指找出两幅图像 (准参考图像和待配准图像) 中的唯一对应特征点, 来确立两个点集之间的对应关系, 然后利用对应关系来求解变换模型参数, 该文利用LTS Hausdorff距离[6]来匹配特征点。

Hausdorff距离是匹配点特征的一种方法, 它不需要建立特征点之间的一一对应关系, 只是计算两个点集之间的相似程度 (最大距离) , 所以它可以有效地处理很多特征点的情况。1991年Daniel P.Huttenlocher与William J.Rucklidge等人提出了一种基于Hausdorff距离的计算图像间的相似度的方法。然而在图像配准中, 单纯的Hausdorff距离对于噪声和孤立点的比较敏感, 于是Sim、Kwon和Park提出了改进的LTS (Least Trimmed Square) Hausdorff距离, LTS Hausdorff距离在数字图像的配准中的精确度与稳定性都比较理想。鉴于此, 该文的图像配准算法采用LTS Hausdorff距离。

LTS Hausdorff距离定义如下:

其中,

hL (A, B) 表示是将集合A中所有点到集合B的“距离”进行排序, 取第L个距离作为集合A到B的Partial Hausdorff距离, 其大小取决于参数f, f=L/NA, 这里NA是集合A中点的个数, 0

根据上述定义, 提出了改进的Hausdorff距离定义——LTS Hausdorff距离, 定义为:

其中, 是集合A中点的个数, dB (a) 表示表示A集合中的点a到B集的距离, dB (a) (i) 表示排序后的第i个距离且有关系。使用这种测度的好处是可以消除图像中的噪声从而提高图像匹配的准确度, 该文采用该测度作为图像相似性度量。

3 消除误匹配

消除误匹配对一般采用随机抽样一致性算法 (RANSAC算法) , 该算法是计算机视觉领域中应用较广的比较稳健的一种估计方法。该文主要介绍由Fischler和Bolles于1951年提出的RANSAC基本算法。

RANSAC算法的输入是测量数据的一个集合μ。在集合中有一定比例的数据满足参数未知的某种模式, 这些数据被称为内点。剩余的不满足参数未知的某种模式的数据被称为外点。

以直线拟合为例说明RANSAC算法的思想:在数据集合图3 (a) 中随机选取两点形成一条直线, 并通过一定的阈值来寻找此直线的内点, 由这个内点集合线性解出新的直线, 再根据此新直线寻找它对应的内点, 不断地重复这样的随机采样, 直到某一次采样使内点数量最大, 那么这次获得的直线估计就是此集合的最好估计。如图3 (b) 所示。

4 实验结果

基于matlab仿真平台, 得到基于SIFT特征点的图像匹配结果如图4:

5 结束语

对基于特征点的图像配准, 该文提出了一种基于SITT角点LTS Hausdorff距离的图像配准技术, 该方法克服了传统方法的许多不足, 其优点如下: (1) 算法简单, 易于实现; (2) 由于是基于特征点匹配, 运算量大大减少; (3) 匹配的精度相对于其它方法比较高。

摘要：图像配准是遥感、医学、计算机视觉等很多领域中的一个基本问题。针对特征点的匹配, 该文首先采用LTS Haus dorff距离进行特征点的初匹配, 然后采用基于Sampson距离的随机抽样一致性算法去除伪匹配的特征点对。实验证明, 该方法可以实现图像的精确配准。

关键词：SIFT角点,LTS Hausdorff距离,图像匹配技术

参考文献

[1]刘传山, 贺道德, 文开庭.基于数字景区的图像配准技术应用研究[J].电脑知识与技术, 2013, 15 (6) .

[2]张羽, 朱丹, 王玉良.一种改进的快速SIFT特征匹配算法[J].微计算机信息 (管控一体化) , 2008, 24 (11) :220-222.

[3]肖若秀, 蔡光程, 贾建波.利用旋转模板匹配方法对SIFT算法的改进[J].计算机技术与发展, 2009, 19 (5) :127-130.

[4]骞森, 朱剑英.基于改进的SIFT特征的图像双向匹配算法[J].机械科学与技术, 2007, 26 (9) :1179-1182.

[5]Huttenlocher D P, Klanderman G A, Rucklidge W J, Comparing images using the Hausdorff distance, IEEE Transactions on PAMI[J], 1993, 15 (9) :850-863.