SIFT算法原理

3.1.1尺度空间极值检测尺度空间理论最早出现于计算机视觉领域，当时其目的是模拟图像数据的多尺度特征。随后Koendetink利用扩散方程来描述尺度空间滤波过程，并由此证明高斯核是实现尺度变换的唯一变换核。Lindeberg，Babaud等人通过不同的推导进一步证明高斯核是唯一的线性核。因此，尺度空间理论的主要思想是利用高斯核对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间特征提取。二维高斯函数定义如下：222()/221(,,)2xyGxye（5）一幅二维图像，在不同尺度下的尺度空间表示可由图像与高斯核卷积得到：(,,(,,)*(,)LxyGxyIxy（6）其中(x,y)为图像点的像素坐标，I(x,y)为图像数据,L代表了图像的尺度空间。σ称为尺度空间因子，它也是高斯正态分布的方差，其反映了图像被平滑的程度，其值越小表征图像被平滑程度越小，相应尺度越小。大尺度对应于图像的概貌特征，小尺度对应于图像的细节特征。因此，选择合适的尺度因子平滑是建立尺度空间的关键。在这一步里面，主要是建立高斯金字塔和DOG(DifferenceofGaussian)金字塔，然后在DOG金字塔里面进行极值检测，以初步确定特征点的位置和所在尺度。(1)建立高斯金字塔为了得到在不同尺度空间下的稳定特征点，将图像(,)Ixy与不同尺度因子下的高斯核(,,)Gxy进行卷积操作，构成高斯金字塔。高斯金字塔有o阶，一般选择4阶，每一阶有s层尺度图像，s一般选择5层。在高斯金字塔的构成中要注意，第1阶的第l层是放大2倍的原始图像，其目的是为了得到更多的特征点；在同一阶中相邻两层的尺度因子比例系数是k，则第1阶第2层的尺度因子是k，然后其它层以此类推则可；第2阶的第l层由第一阶的中间层尺度图像进行子抽样获得，其尺度因子是2k，然后第2阶的第2层的尺度因子是第1层的k倍即3k。第3阶的第1层由第2阶的中间层尺度图像进行子抽样获得。其它阶的构成以此类推。(2)建立DOG金字塔DOG即相邻两尺度空间函数之差，用(,,)Dxy来表示，如公式(3)所示：(,,)((,,)(,,))*(,)(,,)(,,)DxyGxykGxyIxyLxykLxy(7)DOG金字塔通过高斯金字塔中相邻尺度空间函数相减即可，如图1所示。在图中，DOG金字塔的第l层的尺度因子与高斯金字塔的第l层是一致的，其它阶也一样。图1高斯图像金字塔（S=2）与DOG金字塔(3)DOG空间的极值检测在上面建立的DOG尺度空间金字塔中，为了检测到DOG空间的最大值和最小值，DOG尺度空间中中间层(最底层和最顶层除外)的每个像素点需要跟同一层的相邻8个像素点以及它上一层和下一层的9个相邻像素点总共26个相邻像素点进行比较，以确保在尺度空间和二维图像空间都检测到局部极值，如图2所示。图2DOG空间局部极值检测在图3中，标记为叉号的像素若比相邻26个像素的DOG值都大或都小，则该点将作为一个局部极值点，记下它的位置和对应尺度。3.1.2精确定位特征点位置由于DOG值对噪声和边缘较敏感，因此，在上面DOG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点。下面对局部极值点进行三维二次函数拟和以精确确定特征点的位置和尺度，尺度空间函数(,,)Dxy在局部极值点00(,,)xy处的泰勒展开式如公式（8）所示。20021(,,)(,,)2TTDDDxyDxyXXXXX（8）r其中(,,)TXxy，DxDDXyD，22222222222222DDDxxyxDDDDXyxyyDDDxy。公式(4)中的一阶和二阶导数是通过附近区域的差分来近似求出的，列出其中的几个，其它的二阶导数以此类推。通过对公式(8)求导，并令其为0，得出精确的极值位置maxX，如公式(9)所示：12max2DDXXX（9）在上面精确确定的特征点中，同时要去除低对比度的特征点和不稳定的边缘响应点，以增强匹配稳定性、提高抗噪声能力。去除低对比度的特征点：把公式(9)代到公式(8)中，只要前两项，得到公式(10)：max1()2TDDXDX（10）通过式(6)计算出max()DX，若max()0.03DX，则该特征点就保留下来，否则就丢弃。去除不稳定的边缘响应点：海森矩阵如公式(11)所示，其中的偏导数是上面确定的特征点处的偏导数，它也是通过附近区域的差分来近似估计的。xxxyxyyyDDHDD（11）通过2×2的海森矩阵日来计算主曲率，由于D的主曲率与H矩阵的特征值成比例，根据文献[5]，不具体求特征值，求其比例ratio。设是最大幅值特征，是次小的，则radio如公式(12)所示。222222()()()()()()(1)()xxyyxxyyxytrHDDDetHDDDtrHradioDetH（12）由公式（12）求出radio，常取10r，若2(1)rradior则保留该特征点，否则就丢弃。3.1.3确定特征点主方向利用特征点邻域像素的梯度方向分布特性为每个特征点指定方向参数，使算子具备旋转不变性。（13）公式(13)为(,)xy处的梯度值和方向。L为所用的尺度为每个特征点各自所在的尺度，(,)xy要确定是哪一阶的哪一层。在实际计算过程中，在以特征点为中心的邻域窗口内采样，并用梯度方向直方图统计邻域像素的梯度方向。梯度直方图的范围是0~360，其中每10一个柱，总共36个柱。梯度方向直方图的峰值则代表了该特征点处邻域梯度的主方向，即作为该特征点的方向。在梯度方向直方图中，当存在另一个相当于主峰值80％能量的峰值时，则将这个方向认为是该特征点的辅方向。一个特征点可能会被指定具有多个方向(一个主方向，一个以上辅方向)，这可以增强匹配的鲁棒性。通过上面的3步，图像的特征点已检测完毕，每个特征点有3个信息：位置、对应尺度、方向。3.1.4生成SIFT特征向量首先将坐标轴旋转为特征点的方向，以确保旋转不变性。接下来以特征点为中心取8×8的窗口(特征点所在的行和列不取)。在图3左边，中央黑点为当前特征点的位置，每个小格代表特征点邻域所在尺度空间的一个像素，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，图中圈内代表高斯加权的范围(越靠近特征点的像素，梯度方向信息贡献越大)。然后在每4×4的图像小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，形成一个种子点，如图3右边图所示。此图中一个特征点由2×2共4个种子点组成，每个种子点有8个方向向量信息，可产生2×2×8共32个数据，形成32维的SIFT特征向量，即特征点描述器，所需的图像数据块为8×8。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。实际计算过程中，为了增强匹配的稳健性，文献[5]建议对每个特征点使用4×4共16个种子点来描述，每个种子点有8个方向向量信息，这样对于一个特征点就可以产生4×4×8共128个数据，最终形成128维的SIFT特征向量，所需的图像数据块为16×16。此时SIFF特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除,光照变化的影响。22(,)((1,)(1,))((,1)(,1))(1,)(1,)(,)arctan(,1)(,1)mxyLxyLxyLxyLxyLxyLxyxyLxyLxy图3像梯度（左）及特征点描述器（右）当两幅图像的SIFT特征向量，即特征描述器生成后，下一步就是进行特征向量的匹配。3.1.4SIFT特征向量的匹配首先，进行相似性度量。一般采用各种距离函数作为特征的相似性度量，如欧氏距离、马氏距离等。通过相似性度量得到图像间的潜在匹配。本文中采用欧氏距离作为两幅图像问的相似性度量。获取SIFT特征向量后，采用优先k—d树进行优先搜索来查找每个特征点的2近似最近邻特征点。在这两个特征点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。其次，消除错配。通过相似性度量得到潜在匹配对，其中不可避免会产生一些错误匹配，因此需要根据几何限制和其它附加约束消除错误匹配，提高鲁棒性。常用的去外点方法是RANSAC随机抽样一致性算法，常用的几何约束是极线约束关系。