课件：基于尺度不变特征变换的图像匹配.ppt

基于尺度不变特征变换的图像匹配,特征匹配 尺度不变特征变换（SIFT） 基于SIFT的图像匹配 匹配算法实验结果与分析,特征匹配,特征匹配是指通过分别提取两个或多个图像的特征（点、线、面等特征），对特征进行参数描述，然后运用所描述的参数来进行匹配的一种算法。 与基于灰度的匹配方法相比，特征相对于几何图象和辐射度影响来说更不易变化，但特征提取方法的计算代价通常较大。 图像匹配的核心问题：将不同的分辨率、不同的亮度属性、不同的位置（平移和旋转）、不同的比例尺、不同的非线性变形的图像对应起来。,尺度不变特征算法的提出,David G.Lowe在1999年所发表，2004年总结了现有的基于不变量技术的特征检测方法，并正式提出了一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子尺度不变特征变换（SIFT算法）。,图像尺度空间,高斯卷积核是实现尺度变换的唯一线性核,尺度空间理论是通过对原始图像进行尺度变换, 获得图像多尺度下的尺度空间表示序列, 对这些序列进行尺度空间主轮廓的提取, 并以该主轮廓作为一种特征向量,提取的特征点可能是角点、边缘点、暗区域的亮点以及亮区域的暗点等,尺度空间的生成：,Koendetink证明高斯卷积核是实现尺度变换的唯一变换核，而Lindeberg等人则进一步证明高斯核是唯一的线性核。二维高斯函数定义如下： 代表了高斯正态分布的方差。 一幅二维图像，在不同尺度下的尺度空间表示可由图像与高斯核卷积得到： 式中，(x,y)代表图像的像素位置，称为尺度空间因子，其值越小则表征该图像被平滑的越少，相应的尺度也就越小。大尺度对应于图像的概貌特征，小尺度对应于图像的细节特征。L代表了图像的尺度空间。 高斯尺度空间是一种模拟人眼视觉机理的理想数学模型。,SIFT变换思想,SIFT算法首先在尺度空间进行特征检测，并确定关键点(Keypoints)的位置和关键点所处的尺度，然后使用关键点邻域梯度的主方向作为该点的方向特征，以实现算子对尺度和方向的无关性。为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。,DOG算子计算简单，是尺度归一化的LoG算子的近似。,SIFT变换思想,Lowe在图像二维平面空间和DoG(Difference -of-Gaussian)尺度空间中同时检测局部极值以作为特征点，以使特征具备良好的独特性和稳定性。对于图像上的点，计算其在每一尺度下DoG算子的响应值，这些值连起来得到特征尺度轨迹曲线。特征尺度曲线的局部极值点即为该特征的尺度。尺度轨迹曲线上完全可能存在多个局部极值点，这时可认为该点有多个特征尺度。,SIFT特征匹配算法步骤,SIFT特征匹配算法包括两个阶段:第一阶段是SIFT特征的生成，即从多幅待匹配图像中提取出对尺度缩放、旋转、亮度变化无关的特征向量；第二阶段是SIFT特征向量的匹配。 一幅图像SIFT特征向量的生成算法总共包括4步： (1)尺度空间极值检测，以初步确定关键点位置和所在尺度。 (2)通过拟和三维二次函数以精确确定关键点的位置和尺度，同时去除低对比度的关键点和不稳定的边缘响应点。 (3)利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。 (4)生成SIFT特征向量。,SIFT特征向量的匹配,当两幅图像的SIFT特征向量生成后，采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。,建立DOG尺度空间,SIFT方法是通过寻找尺度空间中的极值来确定特征点，首先必须来构建图像的高斯差分(DOG)金字塔尺度空间，然后在DOG金字塔尺度空间中进行极值检测。 DOG差分尺度空间由不同尺度的高斯差分核与图像卷积生成： k为常数 在建立高斯金字塔过程中，高斯金字塔一般选择为4阶，每一阶有s层尺度图像，s一般选择为5层。其中，第1阶的第l层是放大2倍的原始图像，其目的是为了得到更多的特征点。在同一阶中相邻两层的尺度因子比例系数是k。下一阶的第l层由上一阶的中间层尺度图像进行子抽样获得，其尺度因子是上一层的k倍。,高斯差分金字塔,如下图1左图所示，DOG金字塔通过高斯金字塔中相邻尺度空间函数相减得到的，在图中，DOG金字塔的第l层的尺度因子与高斯金字塔的第l层是一致的，其他阶也一样。,高斯DOG金字塔,高斯差分金字塔,Lowe的sigma初值为常量，用户设定，实验时取1.6，做高斯卷积的时候可以取sigma,k*sigma,k*k*sigma.,这里k = pow( 2.0, 1.0 / intvls ，其中intvls就是你想做几层高斯金字塔，一般intvls=3,高斯金字塔与高斯差分金字塔,尺度空间极值检测,寻找范围：差分金字塔中的第0层和最上面的一层排除 中间的差分图像中，像素的横坐标或者纵坐标中任一个值与图像边界值之间的差值小于5的点排除。 为了检测到DOG空间的最大值和最小值，DOG尺度空间中的中间层(最底层和最顶层除外)的,每个像素点需要跟同一层的相邻8个像素点以及它上一层和下一层的9个相邻像素点总共26个相邻像素点进行比较，以确保在尺度空间和二维图像空间都检测到局部极值。初步确定关键点位置和所在尺度。,特征点过滤和位置确定,由于DOG值对噪声和边缘较敏感，因此，在上面DOG尺度中检测到局部极值点还要经过进一步的处理，将候选特征点中低对比度对噪声敏感的候选特征点或位于边缘的候选特征点过滤掉。然后才能确定稳定特征点的位置和尺度等信息。,得到候选的特征点后，需要利用其周围的数据对特征点进行精确的定位。SIFT特征是通过拟和三维二次函数来精确确定特征点的位置和尺度的.,关键点位置不精确三维曲面拟合 Taylor展开式,过滤低对比度点 过滤边缘响应点,特征点过滤和位置确定,X = (x, y,)T ,D是D(x, y, )在候选特征点处的值。令 =0可以得到特征点的精确位置和尺度：,可以用来衡量特征点的对比度，即如果 则 为不稳定的特征点。,在候选的特征点处用 Taylor 展开式得到：,特征点过滤和位置确定,因为DoG算子会产生较强的边缘响应，一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。,特征点两个方向导数的大小反映在Hessian矩阵的特征值中：,式中DXX、DXY、DYY均为二阶方向导数，设矩阵H的特征值为、()，则有：,精确确定关键点的位置和尺度,其中Tr(H)为矩阵的迹，Det(H)为矩阵行列式值，设=，则有：,对于边缘，由于在两个主方向的方向导数差别较大，(+1)2的值将会较大，因此对于不满足 （lows论文中=10）即可认为该点在边缘上，此时应该将其剔除。,(a)原始影像 (b) 在DoG检测的初始关键点 (c)用对比度限制 (d)用对比度和边缘响应去除,为每个关键点指定方向参数,在DOG尺度空间检测到的局部极值点在经过精确化点的位置、剔除低对比度的点、消除边缘响应后所保留的点被称为关键点(Keypoint)，此时的关键点信息包括位置信息及尺度信息。 SIFT算法以关键点邻域图元点的梯度方向分布特性作为指定方向参数，使算子具备旋转不变性。在实际计算时，以关键点为中心的邻域窗口采样，计算每个像素点的梯度向量，计算公式如下：,确定特征点主方向,在实际计算过程中，在以特征点为中心的邻域窗口内采样，并用梯度方向直方图统计邻域像素的梯度方向。梯度直方图的范围是0一360，其中每10为一柱，总共36柱。梯度方向直方图的峰值则代表了该特征点处邻域梯度的主方向，即作为该特征点的方向。一个关键点可能会被指定具有多个方向。,生成SIFT特征向量,通过以上步骤，已经得到了每个特征点的位置、尺度、方向。然后需要为每个特征点建立一个描述符，使其不随各种变化而变化，比如光线变化、视角变化等。并且特征点描述符要尽量与众不同，以便于特征点间的匹配。,生成SIFT特征向量,高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每44的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如图右，一个关键点由22共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。每一组梯度方向直方图占据的图像宽度hist_width = 1.5 * scl_octv 描述字计算所需要的图像宽度 radius = hist_width * sqrt(2) * ( d + 1.0 ) * 0.5 + 0.5,以关键点为中心取88的窗口。图5-4左部分的中央黑点为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，图中蓝色的圈代表,生成SIFT特征向量,实际计算过程中，为了增强匹配的稳健性，Lowe建议对每个关键点使用44共16个种子点来描述。首先将坐标轴旋转为特征点的方向，以保证旋转不变性；对任意一个特征点，在其所在的尺度空间(即高斯金字塔结构的某一层)，取以特征点为中心的16 16像素大小的邻域，再将此邻域均匀地分为4 4个子区域(每个子区域大小为4像素4像素)，对每个子区域计算梯度方向直方图(直方图均匀分为8个方向)。然后，对4 4个子区域的8方向梯度直方图根据位置依次排序，这样就构成了一个448=128维的向量，即为SIFT特征向量，此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。,2019/8/25,27,可编辑,SIFT特征向量特性,SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定； 独特性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。 多量性，即使少数的几个物体也可以产生大量SIFT特征向量。 高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。 可扩展性，可以很方便的与其他形式的特征向量进行联合。,Illumination,Scale,Rotation,Affine,基于SIFT的图像匹配,当两幅图像的SIFT特征向量生成后，下一步采用特征向量的距离作为两幅图像中关键点的相似性判定度量。有多种距离可以衡量两个特征之间的差别，欧氏距离、Hausdorff距离等。 用KD树搜索算法搜索最近邻点，也可以用其他优化方法提高特征点的匹配效率，如BBF(Best Bin First)搜索算法。然后，使用RANSAC方法消除错匹配点对。最后，采用双向匹配方法去除重复匹配点对，得到用于计算图像间变换的同名特征点集。,RANSAC算法去除外点,RANSAC算法的基本思想是：在进行参数估计时，不是不加区分地对待所有可用的输人数据，而是迭代地在输入数据中采样所谓的最小点集，根据每次采样所得到的最小点集估计出所要确定的模型参数，同时根据一定的判断准则来判别输入数据中哪些是与该参数相一致的，即内点，哪些是不一致的，即外点。如此迭代一定次数后，将对应输人数据中内点比例最高的所估计参数值以及所筛选出来的内点作为RANSAC最后解。将此解作为其他方法的初始值进一步优化计算，从而得到最终估计参数。RANSAC算法中有3个需要确定的参数：区分内点与外点的距离阈值t、随机采样的最大次数N以及最小内点个数比例。RANSAC算法剔除SIFT外点的流程如图：随机抽样一次性算法去除外点，随机选择3个特征点进行圆线拟合，可降低匹配特征点共线的风险同时在一定程度上避免了内点过近，多次循环R算法，,几点注意和通用做法,噪声对提取极值点的影响，通常先对图像进行归一化处理，然后扩大图像为原来的两倍，预滤波剔除噪声，然后建立高斯差分金字塔尺度空间； 特征点提取人工干预设定阈值，阀值大则提出的特征多，但干扰点也多，且计算复杂；阀值小则极值点数目会减少，但更加稳定； SIFT算法在确定特征点主方向时采用梯度直方图统计法，算法简单但不科学，后广泛采用主成分变换； 两幅影像间的相似性度量标准：欧式距离、Hausdorff距离等； 原始K-D树搜索算法存在对高维度空间搜索效率降低的缺点，为提高匹配匹配效率，常采用优化搜索方法，如改进BBF（近似的最近邻算法），通过限制K-D树中叶子结点数，对叶结点设一个最大数目从而可以缩短搜索时间； 匹配结束后，使用RANSAC方法消除错匹配点对。,SIFT算法存在的缺点,在相同参数下，背景复杂的图像提取的特征点多，而背景简单的图像提取的特征点少，即SIFT算法对纹理简单的图像特征提取效果不理想； 背景高度相似的图像，在特征匹配时可能出现错误匹配，即sift算法对背景存在高度相似性的图像匹配效果不令人满意； 特征提取时，可能提取到位于运动目标上的特征点，其运动趋势与背景运动趋势有较大差异； 当背景某些区域纹理丰富而某些区域纹理简单时，提取的特征很集中，特征点分布不均匀； SIFT特征提取与匹配速度慢，无法达到实时处理的要求； SIFT特征匹配采用欧式距离作为相似性测度，但该阈值需人工干预，无法达到自适应要求。,实验结果与分析,实验资料：两幅视角不同的自然场景图像， 实验目的：提取不变尺度特征并进行图像匹配，然后对原始图像进行旋转变化、噪声