基于局部特征的图像匹配方法.docx

基于局部特征的图像匹配方法李静，张海波(西安工业大学 电子信息T程学院，西安710032)摘要：为了提高图像匹配的速度和精度，利用SIFT算法对两幅图像的特征点进行提取和 描述，然后建立Kd-W(K-dimension tree)对特征点数据进行检索，最后•使用随机抽样一致性 (R ANS AC——Random Sample Consensus)算法对匹配对进行提纯，最终得到更为精确的 特征点匹配对最后通过实验结果证明了算法的有效性关键词：局部特征；SIFT：特征点提取；匹配对提纯长久以来，计算机视觉一直是人们研究的热点然而，即使是一个十分简单的物体，要 使用计算机去识别它都是一件十分不容易的事情其中，最为关键的莫过于物体的表示或描 述，也就是说，究竟提取什么样的特征才能够用于区别一个物体与另一个物体局部不变特 征的出现，较好的解决这一问题局部特征成功的真正原因在于它提供了一种具有统计意 义的图像内容描述这种图像内容表达方式避免了图像处理中语义层次上的图像分割玄利川局部特征进行图像检测最常川的就是角点检测算法但定角点检测就其木质而言只 是某种滤波函数的响应结果，滤波函数对图像中的灰度突变的敏感稈度决定其精确度，且角 点相关特征区域仅为角点周围的有限邻域，区域特性不够育观。

SIFT特征匹配算法是一种 稳定的局部特征匹配算法，该算法以其优良的尺度和旋转不变性以及对光照和视角变化的鲁 棒性，被广泛应用于机器人视觉、三维目标重建、医学图像配准等领域但在现实条件的复 杂性使得这种算法在运行时产生大最不必要的特征点，在时间和空间上均造成了大量的浪 费，这不仅严重影响了算法的实时性，也导致了算法的精度的下降因此，需要建立高效的 阻配策略和提取有效的特征点的方法为了提高图像匹配的速度和精度，在利用SIFT算法对两幅图像的特征点进行提取和描 述示，采用一种改进的Kd■树最近邻杏询算法对特征点进行检索，提高特征点匹配的效率； 最麻使用随机抽样一致性(RANSAC Random Sample Consensus)算法对匹配对进彳亍提 纯，得到更为精确的特征点匹配对收稿日期：2011-09-26 作者简介：李静(1972-),女，西安工业大学电了信息工稈学院，副教授，主要研究方向为: 动态测试，信息融合，先进控制理论E-mail:gem991i@ .：13572293012. 通讯作者：张海波,Email: haibo 0325@,:15991746948.1基于SIFT的图像特征提取算法将图像的尺度空间表示成一个函数厶（x,yd）,它是由一个变尺度的高斯函数G（x,yo）与图像/（x,y）卷积产生的。

即L（x, y,（r） = G（x,y,a）®/（x,y）其中，®表示在x和）,两个方向上进行卷积操作，而G（x,），为G(x,y,cr)=1 -(a-2 + v2)/2

搜索过程从每纟R的第二层开始，以第二层为当前层，对第二层的DoG图像中 的每个点取一个3x3的立方体，立方体上下层为第一层和第三层这样，搜索得到的极值点 既有位置坐标（DoG的图像坐标），又有空间尺度坐标（层坐标）当第二层搜索完成后， 再以第三层作为当前层，其过程与第二层的搜索类似……为了得到稳定的特征点，只是删除DoG响应值低的点是不够的由于DoG对图像中的 边缘有比较强的响应值，而一旦特征点落在图像的边缘上，这些点就是不稳定的点一方面 图像边缘上点是很难定位的，具有定位的歧义性；另一方面这样的点很容易受到噪声的干扰 而变得不稳定⑸个平坦的DoG响应峰值往往在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率而主曲率可以通过2x2的Hessian矩阵H求出■:»xv\x^y） Dy”（兀,y）式中，D值可以通过求取邻近点像元的差分得到H的特征值与D的主曲率成正比例 要想检查主曲率的比值小于某一阈值y ,只要检查下式是否成立："（77）2 二（冷|）2Del（H）＜ y~对于主曲率比值大于10的特征点将被删除，否则，这些斑点将被保留2图像特征匹配前面已经探讨了图像特征点提取与描述。

特征点往往是代表图像中结构最稳是的局部区 域，当光照、旋转、尺度等发生变化时，期望特征点的位置和相应的描述矢量只有很小的变 化，也就是说，局部特征的检测和描述是一个良态问题S这样，对同一个场累拍摄得到的 两幅图像会有以下性质：如果提取的两个特征点描述矢量间距离很小，这两个特征点在对M 场景的同一位置；反Z,如果距离很大，这两个特征点在对应场景的不同位置特征点匹配 技术就是利用这个原理，从两组特征点集合中找到两两距离最近的特征点匹配对，这个匹恥 对对应的是场景同一个位置2.1 Kd・树算法Kd■树是英文K-dimension tree的缩写，是对数据点在k维空间中划分的一种数据结构 Kd■树是一个二叉树，每个节点表示的是一个空间范围Kd■树的优点主要体现在以下几个 方血首先，Kd■树比较容易刻慚数据的聚簇性质，在建树时分割平面会随数据的统计特性 移动，这样，就能比较容易区分不同簇的数据点其次,Kd•树切分空间的局部分辨率也是 可以调整的，rfl于树的深度可调，在空间大而且数据点稀疏的地方树的深度可以比较小，在 数据点密集的空间则采用更深的树结构来充分切割空间再次，Kd■树切割面的法相也可以 调整的。

实际上，每一个树节点都包含一耳光分割超面方稈，建树时可按照这个方稈计算出 数据点应该属于哪一侧，从而进一步使用数据集的统计分布特性2. 2改进的Kd•树量近邻査询算法标准的Kd■树杳询的搜索过程中的“冋溯”是由“杳询路径”來决定的，并没有考虑杳询路径上数据点木身的一些性质将“查询路径”上的节点进行扌非序，如按各白分割超平面（也称Bin）的树节点开始这个思路就是Best-Bin-First（BBF）查询机制,它能确保优先检索包含最近邻点可能性较高的空间此外，BBF机制还设置了一个运行超时限定，当优先级队列中所有的节点祁经过检杳或超岀时间限制时，检索算法将返I叫当前找到的最好结果作为近似的最近邻采用BBF杏询机制，Kd・树就可以扩展到高维数据集上图1为基于BBF的Kd■树检索流稈图图1 Kd・树检索流程图3匹配对的提纯使用前面介绍数据匹配算法，对于特征丰富的图像，往往可以得到数以百计的特征点匹 配对，而图像间变换关系的计算，只需要4个匹配对便可完成，因此，这是一个数值分析中 的过定问题求一般的过定问题，可以使用最小二乘法求解，但直接使用战小二乘法计算变 换关系式不可行的因此，要使用一致性提纯法来消除错误数据对图像变换关系的影响。

随机抽样一致性RAN SAC (Random Sample Consensus)是一种佔计数学模世的参数的 迭代算法，主要特点是模型的参数随着迭代次数的增加，其正确概率会逐步得到提高主要 思路是通过采样和验证的策略，求解大部分样木都能满足的数学模型的参数迭代时，每次 从数据中采集模型需要的最少数目样木，计算模型的参数，然品在数据集中统计符合该模型 的参数的样木的数目，最多样木符合的参数就被认为是最终模型的参数值符合模型的样木 点叫做内点(Inliers),不符合模型的样本点叫做外点或野点(Outliers)o RANSAC算法的 中心思想就是将数据分为内点和外点，只使用内点来进行模型的参数挂机这种方案能有效 剔除不准确的测量数据，得到更鲁棒的估计结果在RANSAC算法中，有3个参数会对其性能产生影响这3个参数分别是：判定内外 点距离阈值，估计次数和一致性集合大小阈值D内外点距离阈值这个阈值用來判定数据点是内点或者外点一般没有一个统一 的方法来估计该阈值，只能通过实验得到2) 估计次数N令w为数据时真实数据模型内点的概率，"为确定模型参数的最少 点数，如要确定变换关系式1~3,则需要四个匹配对，即n = 40这样，一次估计中使用的 所有〃个点都为内点的概率就是(每次估计需采样〃个数据点)。

如果要保证经过N此至 少有一次估计中的所有数据点都是内点的概率是p ,那么N需要满足：L沙十log(l-v/)(3) 一致性集合大小阈值估计得到模型的参数后，还要统计整个数据集中符合该模 型的内点数目八 令数据点是错谋模型内点的概率为y,很显然错谋模型的内点数目f越小 越好，即厂" < 儿其中，儿的值很小，一般取0.05o)，通常都是无法精确的佔计，如果数据集中真实模 型的内点占-优势，y—般比w小，即,y < w o4实验仿真为了验证该算法的有效性，进行一组实验仿真，在不同尺度及旋转、不同视角、不同光 线的情况下与原SIFT算法的效果进行比较结果如图2〜6所示,其中2 (a)、3 (a)、4 (a). 5 (a)所示为原SIFT算法寻找到得特征点匹配对，2 (b)、3 (b)、4 (b)、5 (b)为经过提 纯和去除误匹配示得到的特征点匹配对图2所示为不同尺度及旋转情况下的特征点匹配, 图3所示为不同视角下的特征点匹配，图4为不同光线下的特征点匹配，图5为在复杂背呆 中特定物体的特征点匹配343 tentative matches131 (38.19%) inliner matches out of 343(a)(b)图2不同尺度及旋转情况下的特征点匹配153 tentative matches(a)110 (71 90%) inliner matches out of 153(b)图3不同视角下的特征点匹配645 tentative matches390 (60.47%) inliner matches out of 645(b)图4不間光线下的特征点匹配60 tentative matches(a)49 (81.67%) inliner matches out of 60(b)图5复杂背景中特定物体的特征点匹配通过实验仿真，nJ'以看出在各种。