好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

一种快速多尺度特征点匹配算法.doc

5页
  • 卖家[上传人]:第***
  • 文档编号:32840956
  • 上传时间:2018-02-12
  • 文档格式:DOC
  • 文档大小:1.52MB
  • / 5 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 一种快速多尺度特征点匹配算法摘 要 为了快速稳定地进行多尺度特征点的跟踪,提出了一种快速多尺度特征点的提取算法该算法首先利用快速局部窗口极值搜索算法提取出不同尺度空间的特征点的局部极值,然后对特征描述符进行小波变换后,再利用最近邻算法对特征点进行匹配实验结果表明,该算法的计算速度快于SIFT算法和MOPS算法,稳定性强于传统的Harris 算法,可以用于实时图像配准及目标跟踪3002关键词 特征点提取 特征点匹配 多尺度变换 MOPS SIFT Harris角点A Fast Multi-Scale Feature Matching AlgorithmAbstract This paper presents a Multi-Scale feature extraction algorithm, which computes maximum of the features in moving windows using fast algorithm and gets the matching features using nearest neighbor matching algorithm that indexes features based on their low frequency Haar wavelet coefficients. The experimental results show that this algorithm is faster than the SIFT and MOPS, and has more stability than Harris algorithm. The algorithm can be used in image registration and target tracking.Keywords feature extraction; feature matching; multi-scale transform; MOPS; SIFT; Harris corner1 引 言基于尺度空间的特征点提取算法是利用图像的特征不变描述符对不同尺度空间的特征点进行描述。

      Schmid 和 Mohr 最早利用高斯微分算子对传统的 Harris 算法 [1]进行改进,形成了旋转不变的特征描述 [2]Lowe 对此算法进行了改进,在不同尺度空间进行特征点的提取,形成了 SIFT(scale-invariant feature transform)算法 [3]SIFT 算法对图像的旋转、缩放及光照影响都具有一定的鲁棒性Brown 等人提出了 MOPS(multi-scale oriented patches)算法 [4],进行不同尺度上 Harris 特征点的提取,并利用窗口搜索算法对特征点的局部极值进行提取由于 SIFT 算法和 MOPS 算法对特征点的提取一般都采用穷举算法搜索,计算量较大,因而在图像实时处理中的应用受到限制本文利用快速局部窗口搜索算法进行多尺度特征点局部极值的提取,从而提高了特征点提取的速度2 多尺度Harris特征点提取进行多尺度 Harris 特征点提取时,要对灰度图像 先利用高斯平滑函数卷积形成图像金,Ixy字塔金字塔的最底层 ,更高层的金0,,PxyI字塔表示为(1),,,pllxyg%(2)1llsxy其中,l 表示金字塔的层数, 表示标准差,为 的高斯平滑窗口,s 为采样间隔,一般取 2。

      第 l 层坐标 处的 Harris 特征点检测矩阵可以,xy表示为(3)T,,,,ddilllPxygxyH其中, 表示在尺度 上的梯度,即(4),,,fxyfgxy@参考文献[4]将积分尺度 和微分尺度 的值分别id取为 1.5 和 1.0,并利用矩阵 H 特征值( )的调12,和平均检测函数 来检测特征点,即HMf(5)12det,,rlxyfxy当 大于某个阈值(一般取为 10),该点即为特征HMf点3 局部区域快速特征点选取算法由于特征点匹配的速度与特征点的个数直接相关,同时由于底层金字塔提取的 Harris 特征点主要集中在物体的边缘和角点处,分布很不均匀;若只将整幅图像中 最大的多个特征点提取出来HMf以减少特征点的个数,则可能使得这些特征点仅局限在某个局部区域,不利于重合区域较小的图像间的匹配因此,本文在不同尺度金字塔图像的一定半径范围内选取 的局部极值,并通过控HMf制采样窗口的大小来控制特征点的提取个数其中半径 r 的选取公式可选择如下:(6)72max,/2lblW其中, 、 分别表示金字塔第 l 层图像的宽度lWlH和高度。

      3.1 特征点局部极值的快速算法在传统的 Harris 算法中,若某个像素对应的值在周围 3×3 的邻域中是最大值,则该像素HMf即为特征点这里将邻域范围扩大到 w×w 窗口范围内来选取特征点,这就将特征点选取转化为在W×H 的图像中对大小为 w×w 的窗口中进行局部极值搜索的问题,若中心元素为极值,则判定该点为特征点一般采用穷举法来进行搜索,根据条件概率计算,平均要进行( )次比1WwHk21wL较,计算量较大本文利用形态学滤波中的极大值滤波的思想 [5-7],采用改进的 HGW (Herk-Gil-Werman)算法,并将最大值滤波的求取过程转化为2 维窗口内局部极值的求取,以加快运算速度具体步骤如下:(1) 设图像的像素用矩阵 X 表示,先将图像扩充到,其中 A 为 的全零X%(mod(,)HwW矩阵(mod 表示取余运算),这样可以将 均分为宽%度为 w 的多个子矩阵2) 将 2 维窗口内极值的计算分解为水平、垂直 2次 1 维窗口极值的计算:(7)max,max,wk wlklfylfxyl记 某一行的元素为 ,考虑 1 维数组的X%01,nK局部最大值,即计算 (i=0,…,n-w),则0axijjpy用序列 将该行元素分为多个小数1231,,wwx组,数组中间元素的下标记为 t。

      对于包括 的每tx个小数组,定义如下序列元素 和 (k=0,…,w-1):kRQ(8)11max,,max,kttkktRtQK该步骤对每个小数组需要 2(w-1)次比较这里采用如下的改进算法来提高 和 的计算速度:kRQ记(9)1mod22q先计算 (k=0,…,q-1)和 (k=q,…w),需要QkRt进行 q-1+w-q=w-1 次比较;然后比较 和1Q,由于 是非递减数列, 是非递1Rtk qt增数列,若 ,则 ;1q121RK最后计算 ,需要比较 次同理,,pK若 ,则无须计算 ,只要比较 q-11qQ1,qw次,即可计算 因此计算 和 平均共1,RkQ需要进行次比1max,1.5mod2/wqw较3) 合并该行元素的 和 ,即可得到以下窗口kRQ最大值的函数:(10)11max,,max,kjkjjwkkwt xRK考虑到及 ,若211wRR211wK,则对所有的 有iiQki,因此不需比较 的情况11kiS ki同理,当 时,则不需比较 的情况wi利用二叉树搜索的原理,该步骤对每个元素进行搜索的次数为 。

      这样就可将 的每个/lbX%元素用对应 1 维窗口的最大值 代替,得到矩阵ktY综合步骤运算平均到每个元素的比较次数为(11)l1mod2.5w若对矩阵 Y 进行列元素的 1 维局部极值求取,重复步骤(1),(2)即可得到 2 维窗口局部极值的分布矩阵 ,即 表示在某元素半径范围内的最大值%的分布情况原始图像及对底层金字塔进行局部最大值求取的结果如图 1 所示a) 原始图像 (b) 底层金字塔局部最大值图 1 原始图像及局部最大值分布图Fig.1 Original image and local maximum distributing将 中的扩充矩阵去掉,并将其与 X 矩阵对Y%应元素相减,若某元素的对应值为 0,则表示该值为 w×w 窗口的局部最大值,即在其周围 w×w 窗口的元素中没有比它更大的元素由于分别进行了一次水平方向和垂直方向的局部极值的求取,所以总共的比较次数为(12)2lb1mod23w常规算法、HGW 算法及改进的 HGW 算法每元素的比较次数如图 2 所示由图 2 可以看出,随着窗口的增大,改进的 HGW 算法的单个元素的比较次数趋向于 3,比较次数少于另外两种算法。

      窗口越大,该算法的优势越明显0 10 20 30 40 50 60 70 80 90 102345678910口口口口口口口口口口口口HGW口口口口HGW口口图 2 几种算法平均计算次数的比较Fig.2 Average number of comparisons of different algorithms3.2 特征点方向确定由于传统的 Harris 特征点检测方法提取的特征点不带有方向信息,因此对于图像的旋转容易产生误匹配采用 SIFT 算法的思想,利用特征点邻域像素的梯度方向分布特征为每个特征点指定方向对 L 层上的特征点邻域内的坐标( x,y)处的方向计算如下:(13),actn,1,xyLxyxy若用直方图统计邻域像素加权梯度方向的值,则其峰值即为该特征点的方向3.3 特征点描述符及特征点匹配结合 MOPS 算法,用特征点周围的 8×8 大小的像素的标准化灰度值来对特征点进行描述再进行 Haar 小波变换,即形成 64 维的特征描述向量特征点描述符形成后,采用次近邻算法(2-NN)[8]对不同图像间提取的特征点进行匹配,具体步骤可参考 MOPS 算法中的匹配过程。

      4 实验结果及不同算法性能比较为对比不同算法的特征点提取、匹配效果,对本文算法、SIFT 算法及 Harris 算法进行了对比实验运行环境为 PD820(2.8GHz),编程环境为V 结合 Opencv,采集图像的分辨率为640×480图中圆的半径大小代表特征点所在的尺度,圆圈内部短线表示特征点的方向从特征点提取的结果(图 3)看, Harris 算法提取的特征点更集中在边缘和角点处,而用本文提出的快速MOPS 算法提取的特征点分布比 SIFT 和 Harris 的特征点分布更为均匀由于快速 MOPS 算法是在运算速度上对 MOPS 算法的改进,而提取特征点的结果是一致的,在此不再分开讨论a)快速 MOPS 算法提取结果 (b) SIFT 算法提取结果 (c)Harris 算法提取结果图 3 快速 MOPS, SIFT, Harris 提取特征点分布图Fig.3 Features extracted by fast MOPS,SIFT and Harris图 4 利用快速 MOPS 进行匹配的结果Fig.4 Features matching using fast MOPS表 1 几种算法的比较Tab. 1 Compare of these algorithms算法 平均运行时间(s) 正确匹配的特征点个数 错误匹配的特征点个数SIFT 6.62 233 17MOPS 1.71 196 10快速 MOPS 1.36 196 10Harris 0.92s 211 116通过表 1 的比较可以看 7 出,Harris 算法运行速度最快,但该算法对于图像的旋转、缩放的稳定性不高,误匹配率较高,不适用于旋转和缩放变化较大的图像间的匹配。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.