北京化工大学毕业设计（论文）
第2.2节 基于特征的匹配算法
基于特征的匹配算法根据两幅图像相同特征的集合关系计算配准参数，而图像的低级别特征主要有点、边缘及面特征等。但是面特征提取比较麻烦，耗时多，因此基于特征的匹配算法主要是研究利用特征点和边缘特征进行匹配。
基于特征点的图像匹配主要有点点匹配和点集匹配两种。点点匹配首先按一定的约束关系得到两个点集，然后利用其它的约束条件剔除错误匹配点，最好确定点与点的一一对应关系。点集匹配不需要建立明确的点点对应关系，只需要利用点的位置和相互关系进行匹配。Hausdorff距离不需要精确的点点对应关系，对非相似变形不敏感，因此该匹配方法广泛应用于特征图像的匹配[9]。
图像特征分为两类，第一类是局部特征，比如说角点，边缘点，短的边缘或线段，
小块区域等；第二类是全局特征，通常由几个多边形或是几个对图像内容更为复杂的描述构成。特征匹配首先对图像进行预处理来提取其高层次的特征，然后建立两幅图像之间特征的匹配对应关系，通常使用的特征基元有点特征、边缘特征和区域特征。特征匹配需要用到许多诸如矩阵的运算、梯度的求解、还有傅立叶变换和泰勒展开等数学运算。
基于特征的匹配方法主要涉及到两个关键步骤：
（1）特征提取：正如上文提到的，图像特征分为局部特征和全局特征。有些方法采用角点作为局部特征，如也有些方法采用线段，比如通过提取高分辨率遥感城市图像中的道路作为特征来匹配也可以是边缘，轮廓，小块区域等其他更为复杂的特征，比如以多边形区域作为待匹配特征。而全局特征就是局部特征的组合。常用的特征提取与匹配方法有：模型法、几何参数法、几何法、边界特征法、信号处理法、傅氏形状描述法、统计方法、形状不变矩法等。
（2）特征匹配：特征匹配是指在两幅图像的特征之间建立对应关系的过程。特征匹配方法涉及到对特征描述的定义和特征匹配策略两点。对特征描述的定义即如何量化地描述一个特征，一个好的特征描述定义应该尽量做到以下几点：来自两幅图像的特征应该就有几何不变性，特征值受噪声的影响应该小；要使特征值尽量分散，即不同的特征应该有不同的特征值，这样才可以避免歧义性；一个特征有多个特征可匹配，要使特征的描述尽量简单，过于复杂的描述会增加计算复杂度。在多数情况下这几点是矛盾的，所以一个好的特征描述定义应该很好的权衡好这几点问题。特征匹配策略
9
北京化工大学毕业设计（论文）
是指如何快速准确地找到特征之间的对应关系。常用的基于特征的匹配算法有距离匹配方法、最小均方误差匹配、金字塔小波匹配等，以及现在很热门的SIFT算法。
基于特征的图像匹配方法流程如图2·1： 特征提取 特征匹配 图2·1图像匹配方法流程图
图像变换 2.2.1特征点的描述
如何准确提取稳定的特征点是基于特征的图像匹配算法首先需要解决的问题，能否准确提取稳定的特征点直接影响匹配算法的实现，因此对特征点提取算法进行研究具有重要的意义。本章对特征点的提取算法进行分析，的能找出一种快速有效的特征点提取算法[10]。
理想的特征点中含有反映图像的重要结构信息，容易与别的像素点区别，并且当图像发生变换或者获取图像的视觉发生变化时，仍然能保持独立性。在常见的特征点有灰度局部极大值点、边缘点、角点和拐点等等。由于特征点的定义又很大差异，征点的提取方法也各有各的特点，但是一个理想的特征点提取算法具有以下的特性：
(1)能够提取出所有特征点；
(2)提取的特征点位置精确,即不存在位置偏差； (3)对噪声不敏感；
(4)不能提取出错误的特征点； (5)能够实时提取特征点；
在实际的操作过程中，由于各种原因不能完全满足以上的要求，但是可以根据所需要可以偏重某一方面的性能。例如有的特征点的提取算法运算量非常大，在加上算法精度很高，无法实现实时处理。还有的就是虽然算法定位精度和运算速度很理想，但是有噪声影响，导致其性能下降。此外，现有的特征点提取算法很难保证不存在漏检某些特征点以及提取一些错误的特征点。
由于理想的特征点提取难以实现,但可以根据各个特征点的特性来确定一个特征点提取算法的评价标准，为以下四个方面:
(1)有效性。提取算法能够提取出图像中尽可能多地特征点。 (2)特征点位的精确性。提取的特征点尽可能接近其真实位置。
10
北京化工大学毕业设计（论文）
(3)稳定性。当图像受到例如噪声等干扰时，仍然能够踢除相应的特征点并且不存在位置偏差。
(4)简单性。特征点提取算法越简单，运行速度越快，则就比较容易满足实际的要求，其使用价值就越大。
就目前来说，基于特征点匹配的算法很多，基本上可以分为基于边缘的特征点提取算法和基于灰度的特征点提取算法。其中基于边缘的特征点的提取算法的中心思想是：特征点是两条获多条边界交叉点的特殊边界点，因此这些算法要先对图像进行分割，提取图像的边界信息，然后通过对图像的边界点进行分析提取特征点。基于灰度特征点提取算法主要根据像素点的灰度或梯度特征提取特征点。基于边缘特征点的提取算法对图像分割的依赖性相对较大，基于灰度的特征点提取算法则可以通过图像的灰度信息直接提取特征点。
2.2.2特征点的提取算法
特征点提取与匹配是计算机图形学中最基础的一个研究课题，现在已经有很多研究成果和应用项目，每种方法都有其优点。SIFT(Scale Invariance Feature Transform)方法是由David Lowe 提出的，利用SIFT 方法从图像中提取出的特征点可以用于一个物体或场景不同视角下的可靠匹配，提取出的特征点对图像尺度和旋转保持不变，对光线变化、噪声、仿射变化都具有鲁棒性，另外，SIFT提取出的特征点具有很高的独特性，因此从某种意义上说一个特征点可以在多幅图像提取出的特征点库中得到正确匹配的概率极高。
SIFT算法的主要思路是：首先建立图像的尺度空间表示，然后在尺度空间中搜索图像的极值点，由极值点建立特征描述向量。采用SIFT方法提取的图像特征具有放缩不变性、旋转不变性，还有一定的抗光照变化和抗视点变换性能。 1. SIFT特征点的提取[11]
David G. Lowe 在2004 年总结了现有的基于不变量技术的特征检测方法，并正式提出了一种基于尺度空间的，对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子-SIFT 算子，全称Scale Invariant Feature Transform ，即尺度不变特征变换。SIFT 算法首先在尺度空间进行特征检测，并确定关键点的位置和关键点所处的尺度，然后使用关键点邻域梯度的主方向作为该点的方向特征，以实现算子对尺度和
11
北京化工大学毕业设计（论文）
方向的无关性。
SIFT 算法的实现主要包括4个步骤:
(1) 检测尺度空间极值，以初步确定关键点位置和所在尺度。
(2) 精炼特征点位置。通过拟和三维二次函数以精确确定关键点的位置和尺度，同时去除低对比度的关键点和不稳定的边缘响应点（因为DOG算子会产生较强的边缘响应），以增强匹配稳定性、提高抗噪声能力。
(3) 计算特征点的描述信息，利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。
(4) 生成本地特征点描述符。 2. SIFT特征匹配
SIFT 特征匹配算法包括两个阶段：第一阶段是SIFT 特征的生成，即从多幅待匹配图像中提取出对尺度缩放、旋转、亮度变化无关的特征向量；第二阶段是SIFT 特征向量的匹配。
当两幅图像的SIFT 特征向量生成后，下一步采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。
给定N 个数据点组成的数据集合P，假设它们中的绝大多数是由一个参数未知的特定的模型产生的，该模型的参数至少需要n个数据点求出，N > n。现在所要解决的问题就是要求出这个模型的参数。 将下述过程运行k次：
(1) 从P中随机选取n个数据点的子集Sl ； (2) 由选取的这n个数据点计算出一个模型M ；
(3) 对数据集合中其余的N - n 个数据点，计算出它们与模型M之间的距离,记录在Ml 的某个误差允许范围内的P中数据点的个数count 。
在重复步骤( 1) ～ ( 3) k次之后，对应最大count值的模型即为所求模型，数据集合p 中的这count个数据即为内点，其余的N - count个数据点即为外点。
在提纯应用中，透视矩阵由4 个匹配点得出。文中将第二幅图像平面分成16个小方格，每次选取4个包含特征点的方格，再在每个方格内随机选取一个点，由这四个点计算透视矩阵。选用内点阈值为1. 25 ，即特征点提取标准差为0. 5107个像素值，定义阈值计算公式为dv = d2 ( x′- Mx )，小于等于阈值的特征点对为M的内点，大于阈值的则为外点。以前后两次内点数目不发生变化为迭代终止条件。从而可以得到了
12
北京化工大学毕业设计（论文）
优化的内点集合来进一步计算透视矩阵M。
第2.3节 基于边缘特征的匹配算法
边缘无疑是图像中最显著和直观的特征，它存在于图像的目标区域和背景之间，对应着图像中更抽象的信息和匹配时比区域匹配更少的计算量。图像的边缘主要表现为图像局部特征的不连续性，是图像中灰度变换比较剧烈的地方。图像的边缘划分为阶跃状和屋顶状。阶跃状边缘中边缘两边的灰度值有明显的变化；而屋顶状边缘中边缘位于灰度增加与减少的交界处。在数学上可以利用灰度的导数来描述边缘点的变化，对阶跃状边缘、屋顶状边缘分别求其一阶、二阶导数。为了求取边缘方向直方图，需要提取图像中目标的边缘。基于形状的图像检索技术对于边缘的定位要求很高，这将会直接影响到最终的检索效果。目前，用于边缘检测的算子有很多，如Roberts 算子、Sobel 算子、Prewitt 算子和Canny算子。其中Canny算子是比较常用的方法，下面将简单介绍上述的边缘特征提取方法[12]。
2.3.1 Roberts 边缘检测算子
任意一对相互垂直方向上的差分可以看成求梯度的近似方法，Roberts 边缘检测算子利用该原理，采用对角线方向相邻两像素之差代替梯度，即
fx=f(i,j)- f(i+1,j+1) (2·4) fy=f(i,j+1)- f(i+1,j) (2·5)
梯度幅值近似为
R(i,j)=错误！未找到引用源。或R(i,j)=|fx|+|fy|
(2·6)
通过差分可以求得Roberts 算子在差分点(i +1/2, j +1/2)处连续梯度幅度的近似值R(i, j)。适当选取阈值τ ，如果R(i, j) >τ ，则认为点(i, j)是边缘点。Roberts 边缘检测算子采用对角线方向相邻两像素之差进行梯度幅度检测，其检测水平、垂直方向边缘检测性能要好于斜线方向边缘，并且检测定位精度比较高，但对噪声敏感。
13
基于特征的图像匹配算法-毕业论文(含源代码)
