opencv2.4.9源码分析――SIFT

1  opencv2.4.9源码分析——SIFT 赵春江blog.csdn.net/zhaocj一、SIFT算法 SIFT（尺度不变特征变换，Scale‐Invariant Feature Transform）是在计算机视觉领域中检测和描述图像中局部特征的算法，该算法于1999年被David Lowe提出，并于2004年进行了补充和完善。该算法应用很广，如目标识别，自动导航，图像拼接，三维建模，手势识别，视频跟踪等。不幸的是，该算法已经在美国申请了专利，专利拥有者为Lowe所在的加拿大不列颠哥伦比亚大学，因此我们不能随意使用它。 用SIFT算法所检测到的特征是局部的，而且该特征对于图像的尺度和旋转能够保持不变性。同时，这些特征对于亮度变化具有很强的鲁棒性，对于噪声和视角的微小变化也能保持一定的稳定性。SIFT特征还具有很强的可区分性，它们很容易被提取出来，并且即使在低概率的不匹配情况下也能够正确的识别出目标来。因此鲁棒性和可区分性是SIFT算法昀主要的特点。 SIFT算法分为4个阶段： 1、尺度空间极值检测：该阶段是在图像的全部尺度和全部位置上进行搜索，并通过应用高斯差分函数可以有效地识别出尺度不变性和旋转不变性的潜在特征点来； 2、特征点的定位：在每个候选特征点上，一个精细的模型被拟合出来用于确定特性点的位置和尺度。而特征点的昀后选取依赖的是它们的稳定程度； 3、方向角度的确定：基于图像的局部梯度方向，为每个特性点分配一个或多个方向角度。所有后续的操作都是相对于所确定下来的特征点的角度、尺度和位置的基础上进行的，因此特征点具有这些角度、尺度和位置的不变性； 4、特征点的描述符：在所选定的尺度空间内，测量特征点邻域区域的局部图像梯度，将这些梯度转换成一种允许局部较大程度的形状变形和亮度变化的描述符形式。 下面就详细阐述SIFT算法的这4个阶段： 1、尺度空间极值检测 特征点检测的第一步是能够识别出目标的位置和尺度，对于同一个目标在不同的视角下这些位置和尺度可以被重复的分配。并且这些检测到的位置是不随图像尺度的变化而改变的，因为它们是通过搜索所有尺度上的稳定特征得到的，所应用的工具就是被称为尺度空间的连续尺度函数。 2  真实世界的物体只有在一定尺度上才有意义，例如我们能够看到放在桌子上的水杯，但对于整个银河系，这个水杯是不存在的。物体的这种多尺度的本质在自然界中是普遍存在的。尺度空间就是试图在数字图像领域复制这个概念。又比如，对于某幅图像，我们是想看到叶子还是想看到整棵树，如果是树，那么我们就应该有意识的去除图像的细节部分（如叶子、细枝等）。在去除细节部分的过程中，我们一定要确保不能引进新的错误的细节。因此在创建尺度空间的过程中，我们应该对原始图像逐渐的做模糊平滑处理。进行该操作的唯一方法是高斯模糊处理，因为已经被证实，高斯函数是唯一可能的尺度空间核。 图像的尺度空间用L(x,y,σ)函数表示，它是由一个变尺度的高斯函数G(x,y,σ)与图像I(x,y)通过卷积产生，即 ,,,,,（1）其中，表示在x和y两个方向上进行卷积操作，而G(x,y,σ)为 ,,12            （2） σ是尺度空间因子，它决定着图像模糊平滑处理的程度。在大尺度下（σ值大）表现的是图像的概貌信息，在小尺度下（σ值小）表现的是图像的细节信息。因此大尺度对应着低分辨率，小尺度对应着高分辨率。(x,y)则表示在σ尺度下的图像像素坐标。需要说明的是，公式1中的图像I(x,y)是具有无限分辨率的图像，也就是说它的尺度σ=0，即I(x,y) =L(x,y,0)。因此公式1得到的尺度空间图像L(x,y,σ)是由尺度为0的图像L(x,y,0)生成的。很显然，尺度为0，即无限分辨率的图像是无法获得的，Lowe就是把初始图像的尺度设定为0.5。那么由L(x,y,σ1)得到L(x,y,σ2)，即由尺度为σ1的图像生成尺度为σ2的图像的公式为： ,,,,,,，             （3） 其中， ,,12          （4） 由于尺度为0的图像无法得到，因此在实际应用中要想得到任意尺度下的图像，一定是利用公式3生成的，即由一个已知尺度（该尺度不为0）的图像生成另一个尺度的图像，并且一定是小尺度的图像生成大尺度的图像。 利用LoG（高斯拉普拉斯方法，Laplacian of Gaussian），即图像的二阶导数，能够在不同的尺度下检测到图像的斑点特征，从而可以确定图像的特征点。但LoG的效率不高。因此3  SIFT算法进行了改进，通过对两个相邻高斯尺度空间的图像相减，得到一个DoG（高斯差分，Difference of Gaussians）的响应值图像D(x,y,σ)来近似LoG： ,,,,,,,,,,,       （5） 其中，k为两个相邻尺度空间倍数的常数。 可以证明DoG是对LoG的近似表示，并且用DoG代替LoG并不影响对图像斑点位置的检测。而且用DoG近似LoG可以实现下列好处：第一是LoG需要使用两个方向的高斯二阶微分卷积核，而DoG直接使用高斯卷积核，省去了卷积核生成的运算量；第二是DoG保留了个高斯尺度空间的图像，因此在生成某一空间尺度的特征时，可以直接使用公式1（或公式3）产生的尺度空间图像，而无需重新再次生成该尺度的图像；第三是DoG具有与LoG相同的性质，即稳定性好、抗干扰能力强。 为了在连续的尺度下检测图像的特征点，需要建立DoG金字塔，而DoG金字塔的建立又离不开高斯金字塔的建立，如下图所示，左侧为高斯金字塔，右侧为DoG金字塔：  图1 高斯金字塔和DoG金字塔 高斯金字塔共分O组（Octave），每组又分S层（Layer）。组内各层图像的分辨率是相同的，即长和宽相同，但尺度逐渐增加，即越往塔顶图像越模糊。而下一组的图像是由上一组图像按照隔点降采样得到的，即图像的长和宽分别减半。高斯金字塔的组数O是由输入图像的分辨率得到的，因为要进行隔点降采样，所以在执行降采样生成高斯金字塔时，一直到不能降采样为止，但图像太小又毫无意义，因此具体的公式为： logmin,2       （6） 4  其中，X和Y分别为输入图像的长和宽，⌊⌋表示向下取整。金字塔的层数S为：S=s+3（7）Lowe建议s为3。需要注意的是，除了公式7中的第一个字母是大写的S外，后面出现的都是小写的s。 高斯金字塔的创建是这样的：设输入图像的尺度为0.5，由该图像得到高斯金字塔的第0组的第0层图像，它的尺度为σ0，我们称σ0为基准层尺度，再由第0层得到第1层，它的尺度为kσ0，第2层的尺度为k2σ0，以此类推。这里的k为：2（8）我们以s=3为例，第0组的6（s+3=6）幅图像的尺度分别为： σ0，kσ0，k2σ0，k3σ0，k4σ0，k5σ0（9） 写成更一般的公式为： σ= krσ0  r∈[0,…,s+2]（10） 第0组构建完成后，再构建第1组。第1组的第0层图像是由第0组的倒数第3层图像经过隔点采样得到的。由公式10可以得到，第0组的倒数第3层图像的尺度为ksσ0，k的值代入公式8，得到了该层图像的尺度正好为2σ0，因此第1组的第0层图像的尺度仍然是2σ0。但由于第1组图像是由第0组图像经隔点降采样得到的，因此相对于第1组图像的分辨率来说，第0层图像的尺度为σ0，即尺度为2σ0是相对于输入图像的分辨率来说的，而尺度为σ0是相对于该组图像的分辨率来说的。这也就是为什么我们称σ0为基准层尺度的原因（它是每组图像的基准层尺度）。第1组其他层图像的生成与第0组的相同。因此可以看出，第1组各层图像的尺度相对于该组分辨率来说仍然满足公式10。这样做的好处就是编程的效率会提高，并且也保证了高斯金字塔尺度空间的连续性。而之所以会出现这样的结果，是因为在参数选择上同时满足公式7、公式8以及对上一组倒数第3层图像降采样这三个条件的原因。 那么第1组各层图像相对于输入图像来说，它们的尺度为： σ= 2krσ0  r∈[0,…,s+2]（11） 该公式与公式10相比较可以看出，第1组各层图像的尺度比第0组相对应层图像的尺度大了一倍。高斯金字塔的其他组的构建以此类推，不再赘述。下面给出相对于输入图像的5  各层图像的尺度公式： σ(o,r)= 2okrσ0 o∈[0,…,O-1], r∈[0,…,s+2]（12） 其中，o表示组的坐标，r表示层的坐标，σ0为基准层尺度。k用公式8代入，得：,2 ∈0,…,1, ∈0,…,2（13）在高斯金字塔中，第0组第0层的图像是输入图像经高斯模糊后的结果，模糊后的图像的高频部分必然会减少，因此为了昀大程度的保留原图的信息量，Lowe建议在创建尺度空间前首先对输入图像的长宽扩展一倍，这样就形成了高斯金字塔的第‐1组。设输入图像的尺度为0.5，那么相对于输入图像，分辨率扩大一倍后的尺度应为1，由该图像依次进行高斯平滑处理得到第‐1组的各个层的尺度图像，方法与其他组的一样。由于增加了第‐1组，因此公式13重新写为： ,2 ∈1,0,…,1, ∈0,…,2（14）DoG金字塔是由高斯金字塔得到的，即高斯金字塔组内相邻两层图像相减得到DoG金字塔。如高斯金字塔的第0组的第0层和第1层相减得到DoG金字塔的第0组的第0层图像，高斯金字塔的第0组的第1层和第2层相减得到DoG金字塔的第0组的第1层图像，以此类推。需要注意的是，高斯金字塔的组内相邻两层相减，而两组间的各层是不能相减的。因此高斯金字塔每组有s+3层图像，而DoG金字塔每组则有s+2层图像。 极值点的搜索是在DoG金字塔内进行的，这些极值点就是候选的特征点。 在搜索之前，我们需要在DoG金字塔内剔除那些像素值过小的点，因为这些像素具有较低的对比度，它们肯定不是稳定的特征点。 极值点的搜索不仅需要在它所在尺度空间图像的邻域内进行，还需要在它的相邻尺度空间图像内进行，如图2所示。 每个像素在它的尺度图像中一共有8个相邻点，而在它的下一个相邻尺度图像和上一个相邻尺度图像还各有9个相邻点（图2中绿色标注的像素），也就是说，该点是在3×3×3的立方体内被包围着，因此该点在DoG金字塔内一共有26个相邻点需要比较，来判断其是否为极大值或极小值。这里所说的相邻尺度图像指的是在同一个组内，因此在DoG金字塔内，每一个组的第0层和昀后一层各只有一个相邻尺度图像，所以在搜索极值点时无需在这两层尺度图像内进行，从而使极值点的搜索就只在每组的中间s层尺度图像内进行。 搜索的过程是这样的：从每组的第1层开始，以第1层为当前层，对第1层的DoG图6  像中的每个点取一个3×3×3的立方体，立方体上下层分别为第0层和第2层。这样，搜索得到的极值点既有位置坐标（该点所在图像的空间坐标），又有尺度空间坐标（该点所在层的尺度）。当第1层搜索完成后，再以第2层为当前层，其过程与第1层的搜索类似，以此类推。  图2 DoG中极值点的搜索 2、特征点的定位 通过上一步，我们得到了极值点，但这些极值点还仅仅是候选的特征点，因为它们还存在一些不确定的因素。首先是极值点的搜索是在离散空间内进行的，并且这些离散空间还是经过不断的降采样得到的。如果把采样点拟合成曲面后我们会发现，原先的极值点并不是真正的极值点，也就是离散空间的极值点并不是连续空间的极值点。在这里，我们是需要精确定位特征点的位置和尺度的，也就是要达到亚像素精度，因此必须进行拟合处理。 我们使用泰勒级数展开式作为拟合函数。如上所述，极值点是一个三维矢量，即它包括极值点所在的尺度，以及它的尺度图像坐标，即X=(x,y,σ)T，因此我们需要三维函数的泰勒级数展开式，设我们在X0=(x0,y0,σ0)T处进行泰勒级数展开，则它的矩阵形式为：  7  12        （15） 公式15为舍去高阶项的形式，而它的矢量表示形式为： ∂∂12               （16） 在这里X0表示离散空间下的插值中心（在离散空间内也就是采样点）坐标，X表示拟合后连续空间下的插值点坐标，设，则表示相对于