利用算法实现图像自动拼接

利用算法实现图像自动拼接第一页，共三十二页，编辑于2023年，星期五1999年BritishColumbia大学大卫.劳伊（DavidG.Lowe）教授总结了现有的基于不变量技术的特征检测方法，并正式提出了一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子－SIFT（尺度不变特征变换），这种算法在2004年被加以完善。SIFT提出的目的和意义DavidG.LoweComputerScienceDepartment

2366MainMall

UniversityofBritishColumbia

Vancouver,B.C.,V6T1Z4,CanadaE-mail:lowe@cs.ubc.ca

SIFT简介第二页，共三十二页，编辑于2023年，星期五SIFT算法实现细节

SIFT算法实现步骤简述SIFT算法的实质可以归为在不同尺度空间上查找特征点（关键点）的问题。第三页，共三十二页，编辑于2023年，星期五所谓关键点，就是在不同尺度空间的图像下检测出的具有方向信息的局部极值点。根据归纳，我们可以看出特征点具有的三个特征：

尺度

方向

大小关键点检测的相关概念1.哪些点是SIFT中要查找的关键点（特征点）？

这些点是一些十分突出的点不会因光照条件的改变而消失，比如角点、边缘点、暗区域的亮点以及亮区域的暗点，既然两幅图像中有相同的景物，那么使用某种方法分别提取各自的稳定点，这些点之间会有相互对应的匹配点。5/25/20234第四页，共三十二页，编辑于2023年，星期五尺度空间理论最早在1962年提出，其主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。尺度空间方法的基本思想是：在视觉信息(图像信息)处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得不同尺度下的视觉处理信息，然后综合这些信息以深入地挖掘图像的本质特征。构建尺度空间的目的是检测对于图像的尺度变化具有不变性的位置，可以使用尺度的连续函数也就是尺度空间在所有可能的尺度中寻找稳定的特征。尺度空间（scalespace

）关键点检测的关键点检测的相关概念第五页，共三十二页，编辑于2023年，星期五

根据文献《Scale-spacetheory:Abasictoolforanalysingstructuresatdifferentscales》我们可知，高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间，L（x,y,σ),定义为原始图像I(x,y)与一个可变尺度的2维高斯函数G(x,y,σ)卷积运算。关键点检测高斯函数关键点检测的相关概念第六页，共三十二页，编辑于2023年，星期五当尺度因子σ逐渐增大时的一组高斯尺度空间。第七页，共三十二页，编辑于2023年，星期五为了在尺度空间中有效的检测稳定关键点的位置，Lowe提出了高斯差分卷积DOG（DifferenceofGaussians）关键点检测——DOG第八页，共三十二页，编辑于2023年，星期五DoG（DifferenceofGaussian）函数 关键点检测——DOG5/25/20239第九页，共三十二页，编辑于2023年，星期五关键点检测——DOG第十页，共三十二页，编辑于2023年，星期五高斯差分函数DOG的优点？1）计算效率高：由于L对于每个尺度空间都是需要计算的，而D只需在此基础上做减法操作；2）高斯差分函数DoG（Difference-of-Gaussian）是尺度归一化算子LoG（LaplacianofGaussian）的近似第十一页，共三十二页，编辑于2023年，星期五LOG算子与高斯核函数的关系通过推导可以看出，LOG算子与高斯核函数的差有直接关系，由此引入一种新的算子DOG（DifferenceofGaussians），即高斯差分算子。关键点检测——DOG第十二页，共三十二页，编辑于2023年，星期五高斯金字塔的构建过程可分为两步：（1）对图像做高斯平滑；（2）对图像做降采样。

为了让尺度体现其连续性，在简单下采样的基础上加上了高斯滤波。一幅图像可以产生几组（octave）图像，一组图像包括几层（interval）图像。关键点检测高斯金字塔第十三页，共三十二页，编辑于2023年，星期五DoG高斯差分金字塔 对应DOG算子，我们要构建DOG金字塔左侧的每一阶的尺度空间是由初始图像重复与高斯函数卷积生成的一组高斯尺度空间图像，右侧是相邻两个高斯图像经差分得到的一组高斯差分尺度空间。每一阶的第一个图像是由高斯图像经因子为2的亚采样得到的关键点检测——DOG第十四页，共三十二页，编辑于2023年，星期五为了检测D(x,y,σ)的局部极大值和极小值，每个采样点都要和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点相比较。只有当它比所有相邻点都大或者都小的时候这个点才被选择。这个检查的花费是相当的低，因为大部分的采样点在头一些检查中就被淘汰了。局部极值点的检测第十五页，共三十二页，编辑于2023年，星期五上一步被选择的点称为候选点，但是如果要进行下一步确定关键点的位置、尺度、主曲率，还需剔除那些低对比度（对噪声很敏感）的点和处于边缘的点。1）滤除低对比度的点2）去除边缘响应DoG算子在边缘处有很强的响应，由于边缘的位置很难确定，故而对噪声的影响很敏感。一个DOG空间极值点的主曲率的大小跟其所在的位置有关，它在与边缘相互垂直处较小，而在边缘处较大，所以可以根据这一特点来去除位于边缘的极值点。局部极值点的检测第十六页，共三十二页，编辑于2023年，星期五

关键点精确定位

为了提高关键点的稳定性，需要对尺度空间DoG函数进行曲线拟合。利用DoG函数在尺度空间的Taylor展开式：其极值点

由于DoG值对噪声和边缘较敏感,因此,在上面DoG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点。第十七页，共三十二页，编辑于2023年，星期五

上式去除那些对比度较低的不稳定极值点。Lowe的试验显示，所有取值小于0.04的极值点均可抛弃（像素灰度值范围[0，1]）。

在计算过程中，分别对图像的行、列及尺度三个量进行了修正，其修正结果如下：为修正值在Lowe的程序中，对坐标进行了五次修正。将修正后的结果代入式

求解得第十八页，共三十二页，编辑于2023年，星期五

去除边缘响应

仅仅去除低对比度的极值点对于极值点的对于特征点稳定性是远远不够的。DoG函数在图像边缘有较强的边缘响应，因此我们还需要排除边缘响应。

DoG函数的（欠佳的）峰值点在横跨边缘的方向有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率可以通过计算在该点位置尺度的2×2的Hessian矩阵得到，导数由采样点相邻差来估计：表示DOG金字塔中某一尺度的图像x方向求导两次第十九页，共三十二页，编辑于2023年，星期五

在两特征值相等时达最小，随r的增长而增长。Lowe论文中建议r取10。

D的主曲率和H的特征值成正比，为了避免直接的计算这些特征值，而只是考虑它们的之间的比率。令为最大特征值，为最小的特征值，则时将关键点保留，反之剔除第二十页，共三十二页，编辑于2023年，星期五在以特征点为中心的邻域内采样，该特征点处的梯度方向利用梯度方向直方图来计算。直方图把360度的范围平均划分成36等份来统计，找到梯度方向直方图的峰值，这个峰值就是特征点的主方向。如果存在一个能量相当于主峰值80%的峰值，则将它作为特征点的辅方向。特征点可能不存在辅方向也可能存在一个或多个辅方向，这样也增强了算法的鲁棒性。为了能够确保生成的SIFT特征描述符具有旋转不变性，需要利用特征点邻域像素的梯度特性为每个特征点指定一个主方向。确定特征点主方向第二十一页，共三十二页，编辑于2023年，星期五生成特征点描述子特征点描述子的生成过程具体如下：1）以关键点为圆心将关键点邻域旋转θ°（调整至0°），其中θ为关键点的方向，从而保证了旋转的不变性；2）在旋转后的图像中，以关键的中心取8

*

8的邻域窗口，图中左图即为关键点的邻域窗口，每个小格代表关键点邻域窗口中的一个像素，箭头的长度为像素的模值，箭头的方向为像素的方向，这个方向就是旋转后的像素方向；3）将8

*8的矩形窗口均匀分为16个4*4个子区域，见图中右图，采用高斯模糊的方法，高斯模糊的方法有利于增加与关键点较近邻域的权重值，并降低与关键点较远邻域的权重值，然后计算每个区域中8个方向（0°、45°、90°、135°、180°、225°、270°、315°）的梯度累加值，累加每个方向的值就生成了一个种子点4）每一个特征点具有4个种子点，每个种子点有8个方向，形成了一个32维的SIFT特征描述符第二十二页，共三十二页，编辑于2023年，星期五关键点匹配

分别对模板图（参考图，referenceimage）和实时图（观测图，observationimage）建立关键点描述子集合。目标的识别是通过两点集内关键点描述子的比对来完成。具有128维的关键点描述子的相似性度量采用欧式距离。5/25/202323第二十三页，共三十二页，编辑于2023年，星期五关键点匹配原图像目标图像穷举匹配2023/5/2524第二十四页，共三十二页，编辑于2023年，星期五

模板图中关键点描述子：实时图中关键点描述子：

任意两描述子相似性度量：

要得到配对的关键点描述子，需满足：关键点匹配5/25/202325第二十五页，共三十二页，编辑于2023年，星期五关键点的匹配可以采用穷举法来完成，但是这样耗费的时间太多，一般都采用一种叫kd树的数据结构来完成搜索。搜索的内容是以目标图像的关键点为基准，搜索与目标图像的特征点最邻近的原图像特征点和次邻近的原图像特征点。关键点匹配Kd树是一个平衡二叉树5/25/202326第二十六页，共三十二页，编辑于2023年，星期五关键点匹配并不能标志着算法的结束，因为在匹配的过程中存在着大量的错配点。消除错配点图中交叉的绿线为错配点5/25/202327第二十七页，共三十二页，编辑于2023年，星期五消除错配点

RANSAC（RandomSampleConsensus，随机抽样一致

）是一种鲁棒性的参数估计方法。RANSAC简介RANSAC实质上就是一个反复测试、不断迭代的过程。RANSAC的基本思想：

首先根据具体问题设计出某个目标函数，然后通过反复提取最小点集估计该函数中参数的初始值，利用这些初始值把所有的数据分为“内点”（inlier）和“外点“（outlier），最后用所有的内点重新计算和估计函数的参数。5/25/202328第二十八页，共三十二页，编辑于2023年，星期五消除错配点RANSAC事例如何估计最佳直线？重复进行，拟合最优直线随机取两样本点拟合直线拟合直线：Back5/25/202329第二十九页，共三十二页，编辑于2023年，星期五SIFT算子的性能评价：(1)SIFT算子提取的图像局部的特征，对亮度变化、尺度缩放以及旋转保持不变性，而且对物体噪声、仿射变换、视角变化保持稳定性。(2)描述符独特性好，信息量丰富，适用于海量特征数据的匹配，与Harris算子匹配方式相比准确率较高。(3)由于SIF