SIFT特征匹配技术

SIFT特征匹配技术ScaleInvariantFeatureTransformSIFT算法提出及其改进SIFT算法由D.G.Lowe1999年提出，2004年完善总结。[1]DavidG.Lowe,Objectrecognitionfromlocalscale-invariantfeatures,InternationalConferenceonComputerVision,Corfu,Greece(September1999),pp.1150-1157.[2]DavidG.Lowe,Distinctiveimagefeaturesfromscale-invariantkeypoints,InternationalJournalofComputerVision,60,2(2004),pp.91-110.后来Y.Ke将其描述子部分用PCA代替直方图的方式，对其进行改进。[3]Y.KeandR.Sukthankar.PCA-SIFT:AMoreDistinctiveRepresentationforLocalImageDescriptors.ComputerVisionandPatternRecognition,2004SIFT算法主要思想SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量。SIFT算法的主要特点：a)SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。b)独特性(Distinctiveness)好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。c)多量性，即使少数的几个物体也可以产生大量SIFT特征向量。d)高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。e)可扩展性，可以很方便的与其他形式的特征向量进行联合。图像多尺度表示(x,y)代表图像的像素位置，σ称为尺度空间因子，其值越小则表征该图像被平滑的越少，相应的尺度也就越小。SIFT算法SIFT算法SIFT算法步骤:Sift特征匹配算法主要包括两个阶段，一个是Sift特征的生成，即从多幅图像中提取对尺度缩放、旋转、亮度变化无关的特征向量；第二阶段是Sift特征向量的匹配。Sift特征的生成一般包括以下几个步骤：1、构建尺度空间，检测极值点，获得尺度不变性；2、特征点过滤并进行精确定位；3、为特征点分配方向值；4、生成特征描述子。构建尺度空间设输入图像经过s次卷积后可以得到高斯卷积函数为G(x,y,2σ)的输出图像,所有σ从到2σ的图像构成一个octave,每个octave固定有s个平面。每一层Ip=G(x,y,kpσ)*I,p=1,2,…,s.而ks=2。根据高斯函数的性质可得:),(),,(),,(yxIyxGyxL构建尺度空间建立高斯金字塔为了得到在不同尺度空间下的稳定特征点,将图像I(x,y)与不同尺度因子下的高斯核G(x,y,σ)进行卷积操作,构成高斯金字塔。高斯金字塔有o阶,一般选择4阶,每一阶有s层尺度图像,s一般选择5层。建立高斯金字塔在高斯金字塔的构成中要注意,第1阶的第1层是放大2倍的原始图像,其目的是为了得到更多的特征点;在同一阶中相邻两层的尺度因子比例系数是k,则第1阶第2层的尺度因子是kσ,然后其它层以此类推则可;第2阶的第1层由第一阶的中间层尺度图像进行子抽样获得,其尺度因子是k2σ,然后第2阶的第2层的尺度因子是第1层的k倍即k3σ。第3阶的第1层由第2阶的中间层尺度图像进行子抽样获得。其它阶的构成以此类推。构建尺度空间需确定的参数σ－尺度空间坐标O－octave坐标S－sub-level坐标和O、S的关系，σ(O,S)=2o+s/S,o∈omin+[0,...,O-1],s∈[0,...,S-1]其中σ0是基准层尺度。o-octave坐标，s-sub-level坐标。注：octaves的索引可能是负的。第一组索引常常设为0或者-1,当设为-1的时候，图像在计算高斯尺度空间前先扩大一倍。空间坐标x是组octave的函数，设是x0组的空间坐标，则Scale-spaceDefinition:whereKeypointsaredetectedusingscale-spaceextremaindifference-of-GaussianfunctionDCloseapproximationtoscale-normalizedLaplacianofGaussian,),(),,(),,(yxIyxGyxL2222/)(221),,(yxeyxG),()),,(),,((),,(yxIyxGkyxGyxD),,(),,(yxLkyxLG22RelationshipofDtoDiffusionequation:Approximate∂G/∂σ:giving,Therefore,WhenDhasscalesdifferingbyaconstantfactoritalreadyincorporatestheσ2scalenormalizationrequiredforscale-invarianceG22GG2kyxGkyxGG),,(),,(GkyxGkyxG22)1(),,(),,(GkyxGkyxG2),,(),,(建立DOG金字塔DOG金字塔通过高斯金字塔中相邻尺度空间函数相减即可,如图2所示。在图中,DOG金字塔的第1层的尺度因子与高斯金字塔的第1层是一致的,其它阶也一样。Imagespacetoscalespacek4σk3σk2σkσσDOG空间的极值检测在上面建立的DOG尺度空间金字塔中,为了检测到DOG空间的最大值和最小值,DOG尺度空间中中间层(最底层和最顶层除外)的每个像素点需要跟同一层的相邻8个像素点以及它上一层和下一层的9个相邻像素点总共26个相邻像素点进行比较,以确保在尺度空间和二维图像空间都检测到局部极值。标记为叉号的像素若比相邻26个像素的DOG值都大或都小,则该点将作为一个局部极值点,记下它的位置和对应尺度。LocalextremadetectionFindmaximaandminimainscalespace精确定位特征点位置由于DOG值对噪声和边缘较敏感,因此,在上面DOG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点。下面对局部极值点进行三维二次函数拟和以精确确定特征点的位置和尺度,尺度空间函数D(x,y,σ)在局部极值点处的泰勒展开式如公式(4)所示。精确的极值位置公式(4)中的一阶和二阶导数是通过附近区域的差分来近似求出的,列出其中的几个,其它的二阶导数以此类推。通过对公式(4)求导,并令其为0,得出精确的极值位置,如公式(5)所示:去除低对比度的特征点在上面精确确定的特征点中,同时要去除低对比度的特征点和不稳定的边缘响应点,以增强匹配稳定性、提高抗噪声能力。去除低对比度的特征点:把公式(5)代到公式(4)中,只要前两项,得到公式(6):通过式(6)计算出D(Xmax),若|D(Xmax)|≥0.03,则该特征点就保留下来,否则就丢弃。去除不稳定的边缘响应点海森矩阵如公式(7)所示,其中的偏导数是上面确定的特征点处的偏导数,它也是通过附近区域的差分来近似估计的。去除不稳定的边缘响应点通过2×2的海森矩阵H来计算主曲率,由于D的主曲率与H矩阵的特征值成比例,不具体求特征值,求其比例ratio。设α是最大幅值特征,β是次小的，r=α/β，则ratio如公式(8)所示。通过公式(8)求出ratio,常取r=10,若ratio≤(r+1)2/r,则保留该特征点,否则就丢弃。确定特征点主方向利用特征点邻域像素的梯度方向分布特性为每个特征点指定方向参数,使算子具备旋转不变性。公式(9)为(x,y)处的梯度值和方向。L所用的尺度为每个特征点各自所在的尺度,(x,y)要确定是哪一阶的哪一层。在实际计算过程中,在以特征点为中心的邻域窗口内采样,并用梯度方向直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360°,其中每10°一个柱,总共36个柱。梯度方向直方图的峰值则代表了该特征点处邻域梯度的主方向,即作为该特征点的方向。在梯度方向直方图中,当存在另一个相当于主峰值80%能量的峰值时,则将这个方向认为是该特征点的辅方向。一个特征点可能会被指定具有多个方向(一个主方向,一个以上辅方向),这可以增强匹配的鲁棒性。通过上面的3步,图像的特征点已检测完毕,每个特征点有3个信息:位置、对应尺度、方向。生成SIFT特征向量首先将坐标轴旋转为特征点的方向,以确保旋转不变性。接下来以特征点为中心取8×8的窗口(特征点所在的行和列不取)。在图4(a)中,中央黑点为当前特征点的位置,每个小格代表特征点邻域所在尺度空间的一个像素,箭头方向代表该像素的梯度方向,箭头长度代表梯度模值,图中圈内代表高斯加权的范围(越靠近特征点的像素,梯度方向信息贡献越大)。然后在每4×4的图像小块上计算8个方向的梯度方向直方图,绘制每个梯度方向的累加值,形成一个种子点,如图4(b)所示。此图中一个特征点由2×2共4个种子点组成,每个种子点有8个方向向量信息,可产生2×2×8共32个数据,形成32维的SIFT特征向量即特征点描述器,所需的图像数据块为8×8。这种邻域方向性信息联合的思想增强了算法抗噪声的能力,同时对于含有定位误差的特征匹配也提供了较好的容错性。生成SIFT特征向量实际计算过程中,为了增强匹配的稳健性,建议对每个特征点使用4×4共16个种子点来描述,每个种子点有8个方向向量信息,这样对于一个特征点就可以产生4×4×8共128个数据,最终形成128维的SIFT特征向量,所需的图像数据块为16×16。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响,再继续将特征向量的长度归一化,则可以进一步去除光照变化的影响。SIFT特征向量的匹配首先,进行相似性度量。一般采用各种距离函数作为特征的相似性度量,如欧氏距离、马氏距离等。通过相似性度量得到图像间的潜在匹配。本文中采用欧氏距离作为两幅图像间的相似性度量。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。采用优先k-d树近似BBF搜索算法进行优先搜索来查找每个特征点的2个近似最近邻特征点。其次,消除错配。通过相似性度量得到潜在匹配对,其中不可避免会产生一些错误匹配,因此需要根据几何限制和其它附加约束消除错误匹配,提高鲁棒性。常用的去外点方法是RANSAC随机抽样一致性算法,常用的几何约束是极线约束关系。。随机抽样一致性算法(RANSAC)是一种鲁棒的变换估计算法,利用特征集合的内在几何约束关系进一步剔除错误的匹配。RANSAC算法的主要思想:首先随机地选择两个点,这两个点确定了一条直线,在这条直线一定距离范围内的点称为这条直线的支撑。随机选择重复数次,具有最大支撑特征集的直线被确认为是样本点集的拟和。在拟和的误差距离范围内的点称为内点,反之则为外点。RANSAC算法由于共线的匹配特征点在透视变换参数计算的过程中易出现奇异情况,导致图像拼接错误。一种改进的RANSAC算法:根据RANSAC算法的思想,随机地选择3个特征点确定一个圆线进行拟和。这样做可以降低匹配特征点共线的风险,同时在一定程度上避免了内点过于临近,相对于多次循环RANSAC算法,改进后的圆线形RANSAC算法提高了消除错配的效率,增强了图像配准算法稳健性。MATLAB代码~lowe/keypoints/可以下载。RobHess基于GSL和Opencv编写了C