基于sift特征点的图像匹配方法研究.ppt

基于特征点的图像匹配方法研究,目录,图像匹配介绍图像匹配分类图像匹配的一般步骤图像匹配的主要方法部分匹配方法的实验结果,1.图像匹配介绍-图像匹配的定义,图像匹配：图像匹配是指通过一定的匹配算法在两幅或多幅图像之间识别同名点，如二维图像匹配中通过比较目标区和搜索区中相同大小的窗口的相关系数，取搜索区中相关系数最大所对应的窗口中心点作为同名点。其实质是在基元相似性的条件下，运用匹配准则的最佳搜索问题。图像匹配主要可分为以灰度为基础的匹配和以特征为基础的匹配。,图像匹配是处理多源图像信息融合、目标识别等实际问题中的一个重要步骤。图像匹配广泛应用于军事、医学、航空等多个重要科研领域。经过图像匹配后配准，可以获得质量更高、清晰度更好、定位更准确的目标信息。,1.图像匹配介绍-图像匹配的意义,1.图像匹配介绍-图像匹配的应用领域,计算机视觉领域-视频监控-对跟踪的目标区域进行匹配跟踪,1.图像匹配介绍-图像匹配的应用领域,遥感领域-信息融合、环境监视、图像拼接、天气预报以及地图更新等,1.图像匹配介绍-图像配准的应用领域,军事领域-变化检测、运动目标指示、视点稳定、大视场重构、多通道融合、地形定位和导航,1.图像匹配介绍-图像配准的应用领域,医学领域-CT,MRT-图像匹配后进行融合可以得到更多的信息,2.图像匹配的分类,2.图像匹配方法的分类,2.1基于灰度的图像匹配算法 基于灰度的图像匹配算法是直接利用匹配图像的灰度值，选择某种相似性度量函数，然后再通过图像像素计算此度量值，最终根据计算结果进行全局优化后实现匹配。灰度匹配通过利用某种相似性度量度量函数可以是 MMSE(最小均方误差)、互相关值、SSDA 等。此类方法无需对图像进行分割和特征提取，自然避免了由这些预处理可能造成的图像信息丢失而引起的匹配精度降低。这类方法主要的特点是在收敛速度、统计模型、匹配精度及最终的估计误差方面均出现了较为成熟的研究成果，并且原理简单容易理解。,2.1基于灰度的图像匹配算法,缺点：匹配速度比较慢；对图像灰度值依赖性大；光照变化及噪声等方面敏感度高。结论：正是由于此类方法没有充分利用到灰度统计特性，因此不适应匹配对象存在旋转和缩放的情况下图像的匹配问题，而且算法匹配计算量较大，效率偏低。,2.图像匹配方法的分类,2.2基于特征的图像匹配算法 基于特征的图像匹配算法通常不直接依赖像素灰度值，而是会经过较为复杂的图像处理过程提取特征后再进行匹配。特征匹配是指通过分别提取两个或多个图像的特征（点、线、面等特征），对特征进行参数描述，然后运用所描述的参数来进行匹配的一种算法。其一般做法是利用两幅图像中对灰度变化、缩放、旋转等均具有不变性的特征，用相似性度量函数对其进行度量，从而得到相关值进而完成图像匹配。,2.2基于特征的图像匹配算法,优点：能够充分结合图像灰度等相关特性，同时还可以有效去除因光照背景等条件不同时带来的误匹配问题。算法在图像发生缩放变换和旋转变换等现象时敏感度低，适应性强，而对轻微扭曲或有一定噪声的图像较前者也有较好的匹配度。,2.2基于特征的图像匹配算法,缺点：算法涉及到大量的几何和形态学方面的计算，使得计算量比较大，最终的计算时间太长而难以达到实时应用的要求；由于此类算法通常需要针对不同的场合选择合适的特征，所以并无统一模型可遵循。,3.匹配算法的一般步骤,特征提取 特征匹配 估计变换模型 图像重采样及变换,3.匹配算法的一般步骤特征提取,特征提取是指分别提取两幅图像中共有的图像特征。这种特征是出现在两幅图像中对比例、旋转、平移等变换保持一致性的特征，如线交叉点、物体边缘角点、虚圆闭区域的中心等可提取的特征。特征包括：点、线和面三类。,点特征是最常采用的一种图像特征，包括物体边缘点、角点、线交叉点等；根据各特征点的兴趣值将特征点分成几个等级。对不同的目的，特征点的提取应有所不同。线特征是图像中明显的线段特征，如道路河流的边缘，目标的轮廓线等。线特征的提取一般分两步进行：首先采用某种算法提取出图像中明显的线段信息，然后利用限制条件筛选出满足条件的线段作为线特征；面特征是指利用图像中明显的区域信息作为特征。在实际的应用中最后可能也是利用区域的重心或圆的圆心点等作为特征。,3.匹配算法的一般步骤特征提取,特征点,3.匹配算法的一般步骤特征提取,直线,3.匹配算法的一般步骤特征提取,区域,3.1特征提取,点特征提取方法-Harris(Harris Corner Detector)算法 受信号处理中相关函数的启发，给出与自相关函数相联系的矩阵M，M矩阵的特征值是自相关函数的一阶曲率，如果两个曲率值都高，那么就认为该点是角点，此方法对图像旋转、亮度变化、视角变化和噪声的影响具有很好的鲁棒性。,3.1特征提取,点特征提取方法-Susan(Susan Corner Detector)算法 SUSAN算法使用一个圆形的模板在图像上滑动，将位于圆形模板中心的待检测的像素点称为核心点。假设图像为非纹理,核心点的邻域被划分为两个区域:其一为亮度值等于(或相似于)核心点亮度的区域,称为核值相似区(USAN),其二为亮度值不相似于核心点亮度的区域。,3.1特征提取,点特征提取方法-Harris-Laplace Harris算子能最稳定地在图像旋转、光照变化、透视变换条件下提取二维平面特征点，但在三维尺度空间中，Harris探测子的重复探测性能不好，不同尺度Harris特征点存在位置误差，Harris探测子不具有尺度和仿射不变性。而三维尺度空间中最稳定高效的特征尺度探测算子是归一化的Laplace算子。,3.1特征提取,点特征提取方法-Harris-Laplace K.Mikolajczyk和C.Schmid结合了Harris和Laplace算子的优点，提出了Harris-Laplace算子。Harris-Laplace特征点具有尺度和旋转不变的特性，且对光照变换和小范围视角变化具有稳定性。,3.1特征提取,点特征提取方法-SIFT特征点提取 使用Difference of Gaussian(DoG)filter来建立尺度空间。在尺度空间上提取极值点。,3.1特征提取,点特征提取方法-SURF特征点提取 基于Hessian矩阵，它依靠Hessian矩阵行列式的局部最大值定位兴趣点位置。对于图像I中的某点X在尺度空间上的Hessian矩阵定义为:,其中，表示高斯二阶偏导在X处与图像I的卷积。、具有相似的含义。,3.1特征提取,点特征提取方法-FAST特征点提取 FAST(Features from Accelerated Segment Test)是对SUSAN角点提取算法的简化，通过比较一个圆上16个像素点与中心像素点的灰度对比情况来判断中心像素点是否为特征点。,3.1特征提取,点特征提取方法-Harris-Affine-Hessian-Laplace-Hessian-Affine-Moravec算子-Forstner算子,3.1特征提取,线特征提取方法-Robert-Sobel-Prewitt-Kirsch-Gauss-Laplace-Canny,3.1特征提取,面特征提取方法-Mser 使用不同的阈值对图像进行二值化，这个过程中，所有阈值图像上形成的连接区域都是极小值区域，在阈值图像的变化过程中，形成了一系列嵌套的极值区域组。在每组嵌套区域里，有一类性质较为稳定的区域，这类区域在较大阈值范围内具有较小的变化，被定义为“最稳定极值区域”。,3.2特征匹配,(2)利用相似度准则进行特征匹配 常用的相似性测度准则:欧氏距离,马氏距离,Hausdorff 距离等。,特征匹配 特征匹配分两步：(1)对特征作描述 现有的主要特征描述子：SIFT特征描述子,SURF特征描述子，对比度直方图(CCH)，DAISY特征描述子，矩方法,3.2特征匹配,特征描述-SIFT特征描述子 主要思想：一种基于图像梯度分布的特征描述子。特点：抗干扰性好。但维数高，计算复杂度大。,3.2特征匹配,特征描述-SURF特征描述子 主要思想：将特征点的周围区域分成几个子区域，用每个子区域内像素点的X,Y方向的偏导和及其绝对值的和组成特征点的描述子。特点：有较好的抗亮度变化能力。但是该描述子要求使用积分图像，限定了其应用范围。,3.2特征匹配,特征描述-对比度直方图 主要思想：将特征点周围区域的像素点与特征点的对比度形成直方图来描述该特征点。特点：该方法比基于梯度的描述子要快。但描述力比基于梯度的要略微弱一点。,3.2特征匹配,特征描述-DAISY特征描述子 主要思想：受SIFT算法和GLOH算法的启发，将梯度加权和用几个高斯方向偏导滤波器与原图像进行积分代替。特点：该描述子有和SIFT特征算子相似的优点，但是速度比SIFT特征算子要快。,3.3估计变换模型,空间变换模型是所有配准技术中需要考虑的一个重要因素，各种配准技术都要建立自己的变换模型，变换空间的选取与图像的变形特性有关。常用的空间变换模型有：刚体变换、仿射变换、投影变换、非线性变换。,3.3估计变换模型,刚体变换模型刚体变换是平移、旋转与缩放的组合，适用于具有相同视角，但拍摄位置不同的来自同一传感器的两幅图像的配准。刚体变换模型下，若点，分别为参考图像和待配准图像中对应的两点，则它们之间满足以下关系：,3.3估计变换模型,仿射变换模型如果第一幅图像中的一条直线经过变换后，映射到第二幅图像上仍然为直线，且平行直线仍旧被映射为平行直线，这样的变换称为仿射变换。该变换保持直线间的平行关系，但由于引入了缩放参数，故它不能保持直线段的长度和角度，若点，分别为参考图像和待配准图像中对应的两点，则它们之间满足以下关系：,3.3估计变换模型,投影变换模型如果第一幅图像中的一条直线经过变换后，映射到第二幅图像上依然为直线，但平行关系不再保持，则称这样的变换称为投影变换。投影变换具有8个参数，可以将成像设备的运动（如平移、旋转、缩放等）描述得更为全面。若点，分别为参考图像和待配准图像中对应的两点，则它们之间满足以下关系：,3.3估计变换模型,非线性变换模型 若第一幅图像中的一条直线经变换后，映射至第二幅图像上不再是直线，我们把这样的变换称为非线性变换。在二维空间中，点 经非线性变换至点 变换公式为：F表示把第一幅图像映射到第二幅图像上的任意一种函数形式。典型的非线性变换如多项式变换，在2D空间中，多项式函数可写成如下形式：,3.4 图像重采样及变换,在得到两幅图像间的变换参数后，要将输入图像做相应参数的变换，使之与参考图像处于同一坐标系下，则校正后的输入图像与参考图像可用作后续的图像融合、目标变化检测处理或图像镶嵌；涉及输入图像变换后所得点坐标不一定为整像素数，则应进行插值处理。常用的插值算法有最近邻域法、双线性插值法和立方卷积插值法。,关键点的匹配可以采用穷举法来完成，但是这样耗费的时间太多，一般都采用一种叫k-d树的数据结构来完成搜索。搜索的内容是以目标图像的关键点为基准，搜索与目标图像的特征点最邻近的原图像特征点和次邻近的原图像特征点。,3.5关键点匹配,K-d树是一个平衡二叉树,SIFT 简介 1999年British Columbia大学大卫.劳伊（David G.Lowe）教授总结了现有的基于不变量技术的特征检测方法，并正式提出了一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子SIFT（尺度不变特征变换），这种算法在2004年被加以完善。SIFT 主要思想 SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量。,4、匹配的主要算法-SIFT算法,基于点特征-SIFT算法 SIFT特征匹配算法包括两个阶段，SIFT特征的生成与SIFT特征向量的匹配。SIFT特征向量的生成算法共包括4步：尺度空间极值检测，以初步确定关键点位置和所在尺度；拟和三维二次函数精确确定位置和尺度，同时去除低对比度的关键点和不稳定的边缘响应点；利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性；生成SIFT特征向量；,4.匹配的主要算法-SIFT算法,SIFT算法具体步骤：（1）检测尺度空间极值点（2）精确定位极值点（3）为每个关键点指定方向参数（4）关键点描述子的生成,4.匹配的主要算法-SIFT算法,尺度空间（scale space）定义：我们要精确表示的物体都是通过一定的尺度来反映的。现实世界的物体也总是通过不同尺度的观察而得到不同的变化。尺度空间理论最早在1962年提出，其主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。,4.SIFT算法-尺度空间的生成,4.SIFT算法-尺度空间的生成,尺度空间理论目的是模拟图像数据的多尺度特征。高斯卷积核是实现尺度变换的唯一线性核，一副二维图像的尺度空间定义为：其中 是尺度可变的高斯函数，（x，y）是空间坐标，是尺度坐标。大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的值对应粗糙尺度(低分辨率)，反之，对应精细尺度(高分辨率)。为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。,4.SIFT算法-尺度空间的生成,下图所示不同下图像尺度空间：,关于尺度空间的理解说明：2k中的2是必须的，尺度空间是连续的。在 Lowe的论文中，将第0层的初始尺度定为1.6（最模糊），图片的初始尺度定为0.5（最清晰）。在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以 Lowe 建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。尺度越大图像越模糊。,4.SIFT算法-图像金字塔的构建,以多分辨率来解释图像的一种有效但概念简单的结构就是图像金字塔。其优势很明显，某种分辨率下无法发现的特性在另一种分辨率下将很容易被发现。图像金字塔是一个图像集合，集合中所有的图像都源于同一个原始图像，而且是通过对原始图像连续降采样获得，直到达到某个中止条件才停止降采样。（当然，降为一个像素肯定是中止条件。）有两种类型的图像金字塔常常出现在文献和应用中：高斯金字塔用来向下降采样图像，而拉普拉斯金字塔则用来从金字塔低层图像中向上采样重建一个图像。,4.SIFT算法-图像金字塔的构建,要从金字塔第 i 层生成第i+1 层，我们先要用高斯核对第i 层进行卷积，然后删除所有偶数行和偶数列。当然，新得到的图像面积会变为源图像的四分之一。按上述过程对输入图像循环执行操作就可产生整个金字塔。Opencv为我们提供了从金字塔中上一级图像生成下一级图像的方法：cvPyrDown。同样，我们可以通过后面相似的函数（但不是降采样的逆操作）将现有的图像在每个维度上都放大两倍：cvPyrUp。在这种情况下，图像首先在每个维度上都扩大为原来的两倍，新增的行（偶数行）以0填充。然后给指定的滤波器进行卷积（实际上是一个在每一维上都扩大为两倍的过滤器）去估计”丢失“像素的近似值。我们之前注意到函数cvPyrUp并不是函数cvPyrDown的逆操作。之所以这样是因为cvPyrDown是一个会丢失信息的函数。为了恢复原来（更高的分辨率）的图像，我们需要获得由降采样操作丢失的信息。,4.SIFT算法-图像金字塔的构建,对于一幅图像I,建立其在不同尺度(scale)的图像，也成为子八度（octave），这是为了scale-invariant，也就是在任何尺度都能够有对应的特征点，第一个子八度的scale为原图大小，后面每个octave为上一个octave降采样的结果，即原图的1/4（长宽分别减半），构成下一个子八度（高一层金字塔）。,高斯金字塔,4.SIFT算法-图像金字塔的构建,生成的高斯差分图像,4.SIFT算法-图像金字塔的构建,4.SIFT算法-空间极值点检测,为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如下图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的92个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。,DoG尺度空间局部极值检测,4.SIFT算法-空间极值点检测,通过拟和三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。,4.SIFT算法-精确确定极值点位置,4.SIFT算法-关键点方向匹配,利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。式中 为梯度的模值，为方向公式。其中L所用的尺度为每个关键点各自所在的尺度。,4.SIFT算法-关键点方向匹配,在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0360度，其中每10度一个柱，总共36个柱。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向，如下图所示：至此，图像的关键点已检测完毕，每个关键点有三个信息：位置、所处尺度、方向。由此可以确定一个SIFT特征区域。,由梯度方向直方图确定主梯度方向,4.SIFT算法-特征点描述子生成,首先将坐标轴旋转为关键点的方向，以确保旋转不变性。接下来以关键点为中心取88的窗口。下图左部分的中央黑点为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，利用前面公式求得每个像素的梯度幅值,与梯度方向，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值。然后在每44的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如上图右部分所示。此图中一个关键点由22共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。,当两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。,4.SIFT算法-特征匹配,4.SIFT算法-特征匹配过程,Sift特征是图像的局部特征，对平移、旋转、尺度缩放、亮度变化、遮挡和噪声等具有良好的不变性，对视觉变化、仿射变换也保持一定程度的稳定性。独特性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。多量性，即使少数的几个物体也可以产生大量Sift特征向量。速度相对较快，经优化的Sift匹配算法甚至可以达到实时的要求。可扩展性强，可以很方便的与其他形式的特征向量进行联合。,4.SIFT算法的特性,4.实验结果视角和旋转变化,视角变化,旋转+尺度变化,4.实验结果光照和尺度变化,光照变化,尺度变化,来自网友的创意周正龙的老虎,图1周正龙的华南虎照片与年画上的华南虎照片12点匹配,图2周正龙的华南虎照片与真实的华南虎照片0点匹配,4.SIFT实验结果,SIFT在图像的不变特征提取方面拥有无与伦比的优势，但其并不是完美的，仍然存在着实时性不高、有时特征点较少、对边缘模糊的目标无法准确提取特征点等缺陷。自从1999年，SIFT算法问世以来，人们从未停止对它的优化和改进。,4.匹配算法的主要方法,4.匹配算法的主要方法,基于点-SIFT算法的几种扩展PCA-SIFT PCA-SIFT与标准sift有相同的亚像素位置（sub-pixel），尺度（scale）和主方向（dominant orientations），但在第4步计算描述子的时候，它用特征点周围的4141的像元计算它的主元，并用PCA-SIFT将原来的23939维的向量降成20维，以达到更精确的表示方式。GLOH(Gradient location-orientation histogram)把原来SIFT中44棋盘格的location bins改成仿射状的同心圆的17 location bins来表示，并计算其中的梯度方向直方图（梯度方向分为16种），因此共1617272维，之后再作PCA将其降成128维，因此保有跟SIFT一样精简的表示方法。,CSIFT（Colored scale invariant feature transform）彩色尺度特征不变变换，可以针对彩色图像进行图像的不变特征提取。由 Farag 2006年提出。,CSIFT,4.匹配算法的主要方法,SURF,SURF（SURF Speeded Up Robust Features），号称是SIFT算法的增强版，SURF算法的计算量小，运算速度快，提取的特征点几乎与SIFT相同，由Bay 2006年提出。,4.匹配算法的主要方法,4.匹配算法的主要方法,基于点-SIFT算法的几种扩展 ASIFT(Affine-SIFT)通过原始图像来模拟得到场景在各个视角下的图像，再对这些得到的图像提起SIFT特征点，然后进行匹配。其仿射性要好于SIFT,具有全仿射不变性。,4.部分匹配算法实验结果,特征点提取时间对比,5.部分匹配算法实验结果,匹配效果对比,5.匹配算法的主要方法比较,由此可见，SIFT在尺度和旋转变换的情况下效果最好，SURF在亮度变化下匹配效果最好，在模糊方面优于SIFT，而尺度和旋转的变化不及SIFT，旋转不变上比SIFT差很多。速度上看，SURF是SIFT速度的3倍。而PCA-SIFT在模糊和放射方面匹配比较好。,5.部分匹配算法实验结果,实验结果总结对于医学图像，常用的方法是互信息，因为其特征不明显。对于模板匹配，常用的方法是互相关。当两幅图像之间只有简单的旋转，平移和缩放，则可以用对数极坐标算法。当待匹配的图像特征十分明显时可以用SURF算法当待匹配的图像特征信息比较弱一些的话可以用SIFT算法。当待匹配的图像之间存在较大的视角变换的话可以用ASIFT算法。,谢谢！,