639 计算机学报 2010 年等因素也可保持较好的可匹配性. 局部特征建立在到极值的角点.Bay 等人 [13] 于 206 年提出 Fast 尺度空间的理论上, 一般说来, 提取局部特征可以分 Hesian 特征检测算法, 该算法基于汉森矩阵定位为两个关键步骤, 即特征检测阶段和特征描述阶段.

Size: px

Start display at page:

Download "639 计算机学报 2010 年等因素也可保持较好的可匹配性. 局部特征建立在到极值的角点.Bay 等人 [13] 于 206 年提出 Fast 尺度空间的理论上, 一般说来, 提取局部特征可以分 Hesian 特征检测算法, 该算法基于汉森矩阵定位为两个关键步骤, 即特征检测阶段和特征描述阶段."

斧白
5 years ago
Views:

1 第 3 卷第 5 期 2010 年 5 月计算机学报 CHINESEJOURNALOFCOMPUTERS Vol.3No.5 May2010 一种新的局部不变特征检测和描述算法杨恒王庆 ( 西北工业大学计算机学院西安 71072) 摘要局部不变特征已经被成功地用来解决计算机视觉领域诸多实际问题. 文中提出一种新的局部不变特征检测和描述算法, 提取出的特征能够对旋转尺度缩放光照等变化, 甚至弱仿射变换保持不变. 一般说来, 局部特征的提取分为特征检测和描述两个关键步骤. 在特征检测阶段, 首先在每一层尺度图像上提取 Haris 角点, 然后在以 Haris 角点为中心的固定大小的搜索窗内搜索三维尺度空间的极值点作为局部特征点的位置和特征尺度, 最后为每个特征点计算主方向. 文中的特征检测算法具有良好的可重复率性能. 在特征描述阶段, 建立了梯度的距离和方向直方图来描述局部特征, 文中的特征描述子不但具有良好的匹配性能, 而且维数更低, 十分有利于提高图像特征的匹配速度. 大量的图像匹配与图像检索实验结果验证了文中算法的有效性. 关键词局部特征 ; 特征检测 ; 特征描述子 ; 不变性 ; 图像匹配中图法分类号 TP391 犇犗犐号 : /SP.J 犃犖狅狏犲犾犔狅犮犪犾犐狀狏犪狉犻犪狀狋犉犲犪狋狌狉犲犇犲狋犲犮狋犻狅狀犪狀犱犇犲狊犮狉犻狆狋犻狅狀犃犾犵狅狉犻狋犺犿 YANGHengWANGQing ( 犛犮犺狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犈狀犵犻狀犲狉犻狀犵, 犖狅狉狋犺狑犲狊狋犲狉狀犘狅犾狔狋犲犮犺狀犻犮犪犾犝狀犻狏犲狉狊犻狋狔, 犡犻犪狀 71072) 犃犫狊狋狉犪犮狋 Localinvariantfeatureshavebensucesfulyapliedinmanyaplicationsincomput ervision.thispaperproposesanovelocalfeaturedetectionanddescriptionalgorithm.thefea turesareinvariantoimagerotation,scaleandiluminationchanges,andevencanbeinvarianto weakafinetransformations.ingeneral,thelocalfeatureextractionprocescanbedividedinto twokeystepswhicharefeaturedetectionstepandfeaturedescriptionstep.inthedetectionstep, firstly,thehariscornersaredetectedineveryscalelevelimage.secondly,thelocalscale space extremaisearchedwithinawindowwhichiscenter localizedonthemulti scalehariscorners. Finaly,thepredominantorientationiscomputedforeachkeypoint.Theproposedfeaturedetec tionalgorithmhasgodrepeatabilityperformance.inthedescriptionstep,anovelocaldescrip toriscreatedbasedonthegradientdistanceandorientationhistogram(gdoh).gdohnotonly hasgodmatchingperformance,butalsohaslowdimensionality,whichresultsinmuchfaster featurematchingsped.extensiveexperimentalresultshavedemonstratedtheefectivenesand eficiencyoftheproposedalgorithm. 犓犲狔狑狅狉犱狊 localfeature;featuredetection;featuredescriptor;invariance;imagematching 视觉的许多领域, 如宽基线图像匹配全景图拼接目标识别图像检索以及场景重建 [1 6]. 局部特征能够对图像间旋转尺度缩放视点变换光照变化等图像变化因素保持不变性, 对物体运动遮挡噪声 1 引言局部不变特征已经越来越广泛地应用在计算机收稿日期 : ; 最终修改稿收到日期 : 本课题得到国家自然科学基金 ( ) 和国家八六三高技术研究发展计划项目基金 (207A01Z314,209A01Z32) 资助. 杨恒, 男,1980 年生, 博士研究生, 主要研究方向为图像处理与计算机视觉, 研究兴趣包括局部不变特征提取图像分类与检索等. 王庆 ( 通信作者 ), 男,1969 年生, 博士, 教授, 博士生导师, 主要研究领域为图像处理和计算机视觉, 研究兴趣包括基于图像的建模与渲染图像分类与识别动态光场信息处理与应用等.E mail:qwang@nwpu.edu.cn.

2 639 计算机学报 2010 年等因素也可保持较好的可匹配性. 局部特征建立在到极值的角点.Bay 等人 [13] 于 206 年提出 Fast 尺度空间的理论上, 一般说来, 提取局部特征可以分 Hesian 特征检测算法, 该算法基于汉森矩阵定位为两个关键步骤, 即特征检测阶段和特征描述阶段. 局部特征. 特征检测阶段的任务是在尺度空间确定出关键点的 (2) 特征描述位置特征尺度及其主方向, 这些参数就可以描述出 Johnson 等 [14] 引入了一种可以描述物体形状的一个局部图像区域. 特征描述阶段的任务是为这个纺线图 (spinimage) 作为描述子, 该描述子能够对局部图像区域建立描述子, 该描述子应该能对图像特征点的刚性变换保持不变.Brown 间的各种变化因素保持不变, 以确保特征能够在这 [2] 对关键点周围的点进行采样组成一个 8 8 大小的图像片, 再对些变化因素的影响下保持较好的可匹配性近十几形成的 64 维描述向量进行规范化以消除光照影响, 年来, 许多局部特征检测和描述算法被提出. 最后对特征向量进行 Har 小波变换, 用前三个非 (1) 特征检测零小波系数作为索引以提高特征匹配速度.Gol Schmid 等 [7] 利用 Haris 角点检测算法提取局引入了广义颜色矩反映信号的多谱特征 [15], 这些矩特部特征, 该局部特征能够抗旋转变换.Haris 特征征描述了区域的形状和颜色特征.Florack 等 [16] 用检测器对噪声和光照变化具有很强的鲁棒性, 但是一组不同阶的微分算子组成描述子, 该描述子可以它对图像间的尺度缩放不具备不变性 [8].Dufour 保持旋转不变性.Schafalitzky 等 [1] 提出了一组复 naud 等 [9] 提出了多尺度 Haris 特征检测算法, 即在滤波器, 这种方法避免了特征主方向的估计问题, 此各个尺度图像上用 Haris 算子进行特征提取, 该方外复滤波器是正交的, 因此可以用欧氏距离作为相法可以解决不同尺度图像间的特征匹配问题. 似性度量准则.Lowe Brown 等 [2] 使用了改进的多尺度 Haris 特征提取 [1] 提出了著名的 SIFT 描述子, 该描述子对特征周围一定区域内像素点梯度的算法, 用 Haris 矩阵特征值的调和平均值作为极值模值和方向用三维直方图进行统计, 统计时对关键的判别函数. 多尺度的 Haris 特征检测算法虽然可点附近 4 4 个子区域都计算 8 个方向直方图, 最终以解决存在尺度缩放的图像间匹配特征的问题, 但形成 128 维特征向量.SIFT 描述子具有很强的抗噪是对于同一个图像局部结构, 该算法会提取出许多声能力, 同时对于含有定位误差的特征匹配也提供重复的特征, 而这些特征仅仅在位置和尺度上略有了较好的容错性. 但是由于 SIFT 提出的特征描述不同, 这种大量的重复性会增加误配率和匹配计算子维数较高, 使得进行图像匹配时速度较慢. 为了降的复杂度. 为了克服这个缺点,Lindeberg [10] 在深入低 SIFT 特征维数,Ke 等 [17] 在 SIFT 算法基础上提研究尺度空间理论的基础上, 提出 LoG(Laplacian 出了 PCA SIFT 算法, 先对每个关键点周围 of Gausian) 尺度空间的三维局部极值点可以作区域内像素统计梯度的两个垂直分量组成 3042 维的为稳定的局部特征.Lowe [1] 提出了著名的尺度不描述向量, 然后使用主成分分析 (PCA) 将高维特征变特征变换算法 SIFT(ScaleInvariantFeature 向量投影到前 20 维特征向量空间, 由于 PCA SIFT Transform),SIFT 在特征检测阶段采用 DoG 的维数低, 使得其匹配速度大大增加.Mikolajczyk (Diference of Gausian) 算子, 搜索尺度空间上的等 [18] 比较评价了各种建立描述子的算法性能, 并通局部三维极值点, 并以此来确定局部特征的位置和过实验表明 SIFT 算法的性能是最优异的, 同时尺度, 再通过拟和三维二次函数进行位置和尺度的 Mikolajczyk 还提出了一种扩展 SIFT 的描述子精确定位, 同时去除低对比度的特征点和不稳定的 GLOH(GradientLocationandOrientationHisto 边缘响应点, 以提高抗噪声能力.DoG 算子是 LoG gram),gloh 采用对数极坐标的形式对关键点周算子的近似, 但是其计算速度更快.Mikolajczyk 分析并指出 [12] 围划分出 17 个位置区域, 对每一个位置区域内的梯 DoG 和 LoG 算子的缺点是提取出来的度统计 16 个方向的直方图, 这样共形成 272 维特征特征未必都是稳定的. 因为这些极值点有可能会位描述向量, 最后再用主成分分析的方法将特征维数于亮度只在一个方向变化的边缘上, 这样的点容易降至 128 维. 受到噪声或者细小纹理变化的干扰. 同时,Mikola 本文提出一种新的尺度不变局部特征检测和描 jczyk 还提出 Haris Laplace 尺度不变特征检测算述算法, 提取出来的特征能够对图像间旋转尺度缩法. 该算法首先在每一层尺度图像上检测 Haris 放线性光照变化以及部分视点变换保持不变性. 在角点, 然后用 Laplace 函数去除掉不在尺度轴上达特征检测阶段, 我们在多尺度 Haris 角点附近一定

3 5 期杨恒等 : 一种新的局部不变特征检测和描述算法区域内搜索 DoG 尺度空间的局部极值点, 以确定特征的位置和尺度, 再采用与 SIFT 一样的方法统计每个特征点的主方向. 在特征描述阶段, 我们在特征点周围的圆形区域内统计梯度的距离和方向直方图, 并以此建立描述子. 实验表明, 本文的特征检测算法在图像间具有尺度缩放旋转变换光照变化噪声干扰以及小视点变换的情况下都具有良好的可重复率. 另外, 本文提出的特征描述子不但与 SIFT, PCA SIFT 以及 GLOH 描述子具有相当的性能, 而且特征向量维数更低, 使得在图像特征匹配的应用中具有明显的速度优势. 2 关键点检测我们首先简要分析 Haris Laplace 检测算法 [12], 并在此基础上提出本文的 Haris Diference 特征检测算法. 2.1 犎犪狉犻狊犔犪狆犾犪犮犲特征检测算法 Haris Laplace 算法首先在每一层尺度图像上使用 Haris 函数 ( 如式 (1) 来定位图像中的角点, 如果 Haris 函数在周围 8 个点中取得极值, 则该点就为 Haris 角点. 其中 σ 犐表示积分尺度,σ 犇是差分尺度, 犔 ( 狓,σ 狀 )= 犌 (σ 狀 ) 犐 ( 狓 ) 表示尺度空间函数, 由标准高斯核犌 (σ 狀 ) 与图像犐 ( 狓 ) 卷积得到.μ 是 Haris 矩阵, 犱犲狋 () 表示矩阵的行列式, 狋狉犪犮犲 () 是矩阵的迹,α 是常数, 取值为 0.04, 犔狓和犔狔分别是尺度函数对狓和狔的偏导数. 犱犲狋 (μ( 狓,σ 犐,σ 犇 )-α 狋狉犪犮犲 2 ( μ( 狓,σ 犐,σ 犇 )(1) 其中, [ μ( 狓,σ 犐,σ 犇 )=σ 2 犇犌 (σ 犐 ) 犔 2 狓 (,σ 犇 ) 犔狓犔狔 ( 狓,σ 犇 ) ] 犔狓犔狔 ( 狓,σ 犇 ) 犔 2 狔 ( 狓,σ 犇 ). 然后, 对于每个 Haris 角点, 用 Laplace 函数选择特征尺度, 即如果 Laplace 函数值在尺度轴上与附近两个点比较达到极值并且大于给定阈值 ( 如式 (2), 则该角点作为稳定的特征点予以保留 ; 否则就排除这个 Haris 角点. 犔狅犌 ( 狓,σ 狀 )=σ 2 狀犔狓 ( 狓,σ 狀 )+ 犔狔 ( 狓,σ ) > 狋犺狉犲狊犺狅犾犱, 犔狅犌 ( 狓,σ 狀 )> 犔狅犌 ( 狓,σ 狆 ), 狆 { 狀 -1, 狀 +1} (2) 其中犔狅犌表示 Laplace 函数, 犔狓与犔狔分别是尺度函数对狓和狔的二阶偏导数, 狋犺狉犲狊犺狅犾犱是给定的阈值. 然而在实验中我们发现, 如果用 Laplace 函数选择特征尺度, 仅有不到 10% 的初始角点能够得到保存, 绝大多数的 Haris 角点将会被滤除掉. 另外, 选择的 Haris 角点也只是在一维尺度轴上的极值点, 并不是三维尺度空间的局部极值点, 这可能会导致不稳定的特征提取. 2.2 犎犪狉犻狊犇犻犳犲狉犲狀犮犲特征检测算法针对 Haris Laplace 算法的不足, 本文提出 Haris Diference 特征检测算法, 该算法可以保留相对较多的和相对稳定的 Haris 角点或者其附近点, 提高特征检测的性能.Haris Diference 特征检测算法分为以下 3 个步骤. 1. 先用文献 [1] 的方法构造金字塔尺度空间, 然后在不同尺度图像上检测 Haris 角点. 2. 使用多尺度 Haris 角点作为初始点, 在其附近一个固定大小的窗口内搜索 DoG 函数在三维局部空间 (3 3 3) 上的极值点, 如式 (3), 其中犽是常数, 与金字塔每一层内不同尺度图像的个数有关. DoG( 狓,σ 狀 )= 犔 ( 狓, 犽 σ 狀 )- 犔 ( 狓,σ 狀 ) (3) 2.1. 选择一幅尺度图像上的一个 Haris 角点, 验证其 DoG 函数值是否是三维局部空间 (3 3 3) 的极值点, 如果是, 保留该 Haris 角点并作为特征点, 跳转至步 2.3; 否则, 去除该 Haris 角点, 跳转至步在以当前角点为中心的 5 5 大小的窗口内, 搜索 DoG 函数在局部三维空间 (3 3 3) 的极值点. 如果找到这样的点, 只保留距离搜索窗中心最近的点并作为特征点, 然后跳转至步 2.3; 否则, 直接跳转至步如果每一层尺度图像上的所有 Haris 角点都已经计算过, 则保存所有特征点的位置和尺度信息, 结束步 2; 否则, 跳转至步 2.1. 图 1 显示了两组不同变换条件下图像对随着搜索窗尺寸变化的可重复率曲线 ( 见 5.1 节 ), 可以看出, 在搜索窗大小为 5 的时候, 可重复率最高, 当搜索窗大于 5 以后, 检测算法的性能反而会略有下降. 原因是当搜索窗过大后, 虽然可以找到更多的特征点, 但这些点未必是稳定的, 它们并不能保证可重复率会提高. 因此, 在本文的后续实验中, 搜索窗大小都设置成使用文献 [1] 中的方法, 为每个特征点计算主方向. 在后面建立描述子的过程中, 通过旋转坐标至主方向上, 可以使得描述子具有旋转不变性. 图 1 随搜索窗口大小变化的可重复率曲线 739

839 计算机学报 2010 年图 2 是本文算法在两幅标准图像上提取出来的局部特征点的示例, 左右两幅图像大小分别是 512 348 和 850 684, 分别检测到 896 个和 6762 个局部特征点. 特征点用箭头表示, 箭头末端表示特征点位置, 箭头长度表示特征尺度大小, 箭头指向表示特征点主方向.

建立新描述子的目标是保持与 SIFT PCA SIFT 以及 GLOH 这些描述子相当的性能, 同时降低描述向量的维数, 以减小图像特征匹配的时间复杂度. 本文提出的描述子基于梯度的距离和方向直方图 (GradientDistanceandOrientationHistogram, GDOH), 图 3 解释了建立描述子的过程.

4 839 计算机学报 2010 年图 2 是本文算法在两幅标准图像上提取出来的局部特征点的示例, 左右两幅图像大小分别是和 , 分别检测到 896 个和 6762 个局部特征点. 特征点用箭头表示, 箭头末端表示特征点位置, 箭头长度表示特征尺度大小, 箭头指向表示特征点主方向. 图 2 本文提出的 Haris Diference 算法在两幅图像上检测出来的局部特征示例 3 局部特征描述子图像的局部特征描述子应该能够对图像间的旋转尺度缩放光照变化甚至小视点变换保持不变性, 而且具有很高的区分力和鲁棒性. 受 SIFT 描述子的启发, 本文的描述子也是基于特征点邻域梯度统计的思想, 以增强描述子的抗噪声能力以及对定位误差的容错性. 建立新描述子的目标是保持与 SIFT PCA SIFT 以及 GLOH 这些描述子相当的性能, 同时降低描述向量的维数, 以减小图像特征匹配的时间复杂度. 本文提出的描述子基于梯度的距离和方向直方图 (GradientDistanceandOrientationHistogram, GDOH), 图 3 解释了建立描述子的过程. 首先, 计算特征点周围圆形区域内的梯度的模值和方向 ( 如图 3(a) 中的箭头 ), 圆形区域的大小与特征点的尺度成正比. 然后, 用一个高斯窗函数对每一个梯度模值加权, 高斯窗大小与圆形区域大小一致 ( 如图 3(a) 中的最外层圆形点画线 ). 高斯窗加权的目的是为了减少距离中心远的点的影响. 接着, 将每个梯度方向旋转至主方向以保证旋转不变性, 同时计算每个梯度点到中心点的距离. 根据距离和旋转后的方向, 建立具有 48 个单元 ( 距离划分 6 个单元, 方向划分 8 个单元 ) 的直方图, 直方图每个单元的统计值是由加权的梯度模值累加得到的, 描述子如图 3 (b) 所示. 一般来讲, 计算出来的距离单元和方向单元都不是整数, 为了使得相邻距离单元以及相邻方向单元间过渡平滑, 我们采用双线性插值算法来分配梯度模值对相邻单元间的贡献. 最终形成的 48 维描述子向量就对应着直方图的每个单元的值, 如图 3(b) 中的箭头长度. 最后, 将特征向量归一化以进一步去除光照的影响. 图 3GDOH 描述子建立过程示意图在实验中, 我们发现距离划分 6 个单元且方向划分 8 个单元或者距离划分 8 个单元且方向划分 8 个单元都可以取得最优的性能, 这两种方案分别可以产生 48 维和 64 维的特征描述向量, 考虑到向量维数对后面匹配速度的影响, 我们在后续实验中都选择前一种划分方法, 即为每一个特征建立一个 48 维的描述向量. 4 特征匹配特征描述子建立好以后, 使用 BF(Best Bin First) [1] 算法进行特征点间的粗匹配.BF 是一种

5 5 期杨恒等 : 一种新的局部不变特征检测和描述算法近似的最近邻搜索算法, 能够以很高的概率找到待匹配点的最近邻点和次近邻, 如果最近邻和待匹配点的距离与次近邻和匹配点的距离之比小于匹配门限阈值 ( 实验中取 0.4), 则认为该最近邻点是待匹配点的候选匹配. 在对所有点进行粗配之后, 使用 RANSAC(RANdomSampleConsensus) 算法估计两个图像对之间的单应变换矩阵并作为几何约束, 进而去除误配, 完成特征点之间的精确匹配. 5 实验结果和分析实验中选用的测试图像均来自标准图像数据集 1, 该图像数据库中图像包含了各种变换条件下的场景图像. 实验采用的评价准则包括 : (1) 可重复率 (repeatability) [14], 评价特征检测算法. ( 2) 查全率查错率 (recalvs.1 precision) 曲线 [17], 评价描述子的性能. (3) 匹配的时间代价, 比较特征匹配的速度. (4) 特征匹配实例, 主观比较匹配性能. (5) 图像检索应用, 验证本文算法在实际应用中的性能. 所有的实验都运行在 2.80GHzCPU 和 512MB 内存的 PC 机环境上, 采用 VC6.0 编程语言实现. 5.1 可重复率可重复率是指在两幅图像上检测到的对应特征数的比率, 它体现了特征检测算法的性能, 是衡量检测算法的重要指标. 如果检测算法在两幅待匹配图像上的相同区域内分别检测出犿 1 和犿 2 个特征点, 则可重复率狉犚计算如下 : 狉犚 = 犆 ( 犿 1, 犿 2) min( 犿 1, 犿 2) (4) 其中 min( 犿 1, 犿 2) 为两幅图像中最少的特征点数. 犆 ( 犿 1, 犿 2) 指的是对应特征点数, 对应的特征点需要满足如下两个条件 [12]: (1) 特征点的位置误差 ε 犔 = 狓犪 - 犎狓犫 < 误差限阈值, 其中犎是两幅图像间的单应变换矩阵, 误差限阈值是设定好的常数 (3 像素 ). (2) 特征区域的表面误差 ε 犛 =1- 狊 2σ 2 犪 σ 2 <0.2, 犫其中狊是图像间实际的尺度缩放因子,σ 犪和 σ 犫分别是两个特征点的特征尺度. 图 4~ 图 8 分别给出了随着图像间的尺度变化旋转变化光照变化噪声干扰以及视点变换的 939 条件下,DoG Haris Laplace Fast Hesian 以及本文的 Haris Diference 特征检测算法的可重复率变化曲线. 图 4(a)1 为参考图像,2~5 分别是尺度放大 2 倍 ~5 倍的变换图像, 从图 4(b) 可以看出在有尺度缩放变化的条件下,DoG 算法可以获得最好的可重复率性能, 而本文的 Haris Diference 算法要略微低于 DoG 算法, 但是要高于 Fast Hesian 以及 Haris Laplace 算法. 图 5(a)1 为参考图像,2~7 分别是旋转角度为 30,60,90,120,150 以及 180 的变换图像, 从图 5(b) 可以看出,4 种算法的可重复率曲线都具有周期性, 当旋转角度为 90 和 180 时出现峰值, 本文 Haris Diference 算法的可重复率略微低于 DoG 算法, 但仍然高于 Fast Hesian 以及 Haris Laplace 算法.DoG 算法在尺度和旋转变换中都获得了最好的检测性能, 原因是 DoG 算法检测了尺度空间中所有的局部极值点. 但是 DoG 检测出来的特征点可能是不稳定的, 因为它检测的这些极值点有可能会落在亮度信号只在一个方向变化的边缘附近, 这就导致这些检测出来的特征点对于噪声干扰或者细微的纹理变化很敏感. 而基于 Haris 的检测算法以及基于 Hesian 矩阵的算法检测的是图像角点特征, 即亮度信号在两个正交方向同时变化比较明显的图像特征点, 这种特性使得这类算法具有较高的鲁棒性和抗干扰能力, 这种特性在图 6 图 7 和图 8 的结果中得到了体现. 图 6(a)1 为参考图像,2~6 分别是亮度增强 2 倍 ~6 倍的变换图像, 从图 6(b) 可以看出在有亮度变化的条件下,4 种算法的可重复率性能相当, 而 Haris Diference 算法要略微优于其它 3 种算法. 图 7(a)1 为参考图像, 2~6 是加入了高斯噪声的模糊图像, 其高斯半径 σ 分别为 1,1.5,2,2.5,3, 从图 7(b) 可以看出在有噪声污染的条件下,Haris Diference Haris Laplace 和 Fast Hesian3 种算法的可重复率都要明显高于 DoG 算法, 而 Haris Diference 算法的性能是最优的. 图 8 给出了在视点变换条件下的实验结果,(a)1 为参考图像,2~6 的视点变换角度分别为 20,30, 40,50 以及 60, 从图 8(b) 中可以看出在视点变换不大的情况下 ( 不超过 40 ),Haris Diference 算法的可重复率要高于其它 3 种算法, 而当视点变换超过 40 时, 由于图像间发生较大的畸变,4 种算法的可重复率均降为 0. 综合以上实验结果可以得出结 1 实验图像数据集来源.htp:/lear.inrialpes.fr/people/ mikolajczyk/

6 049 计算机学报 2010 年论,Haris Diference 算法在图像间具有几何变换 ( 旋转和尺度变换 ) 的条件下, 可重复率要略低于 DoG 算法 ; 而在图像间具有光照变化高斯污染以及视点变换的条件下,Haris Diference 算法性能要优于 DoG 算法. 此外, 在任何条件下, 本文算法都优于 Haris Laplace 和 Fast Hesian 算法. 这说明本文提出的 Haris Diference 算法具有良好的特征检测性能. 图 64 种算法随着亮度变化的可重复率曲线图 44 种算法随着尺度变化的可重复率曲线图 54 种算法随着旋转角度变化的可重复率曲线图 74 种算法随着不同程度高斯噪声干扰情况下的可重复率曲线 5.2 查全率查错率曲线查全率查错率曲线是对描述子性能的评价, 查全率 (recal) 是指正确匹配数占对应 (corespon dence) 特征数目的比率, 查错率是错误匹配数目占整个匹配数目 ( 正确匹配与错误匹配之和 ) 的比率. 查全率查错率曲线评价准则的思想就是增加正确匹配数目的同时减少查错率. 图 9 是评价查全率查错率性能的 4 组实验数据,(a) 中图像对间存在 5 的旋转变换和 1.6 倍的尺度缩放 ;(b) 中图像间存在着 20 的视点变换 ;(c) 中图像对间存在着 1.2 倍的

7 5 期杨恒等 : 一种新的局部不变特征检测和描述算法亮度变化 ;(d) 中图像存在高斯噪声污染, 高斯半径 σ=3. 图 10 分别给出了对应图 9 中的 4 组实验数据的 SIFT PCA SIFT GLOH 以及本文的 GDOH 算法随着不同的匹配门限做出的查全率查错率曲线图, 从图 10(a) 中可以看出, 当图像间存在几何变换 ( 旋转和尺度缩放 ) 时,4 种描述子的性能是接近的, 当查错率小于 0.3 时,GLOH 的性能最优, 而当查错率大于 0.3 时,GDOH 的性能最优. 当图像间存 149 图 84 种算法随着视点变换角度变化的可重复率曲线图 9 评价查全率查错率性能的 4 组实验数据图 10 分别对应图 9 的 4 组不同变换类型下的 4 种描述子的查全率查错率曲线比较

249 计算机学报 2010 年在较小的视点变换时 ( 见图 10(b),GDOH 的性能最优, 尤其是在查错率低于 0.2 的情况下,GDOH 的优势较为明显, 在查错率高于 0.2 时,4 种描述子的性能十分接近. 图 10(c) 的结果表明, 在光照变化的情况下,4 种描述子都可以达到很好的性能 ( 查全率都在 0.8 以上 ), 而 GDOH 获得了最优的性能.

综合这些实验结果可以得出结论, 本文的 GDOH 描述子的性能和目前优秀的 SIFT PCA SIFT 以及 GLOH 描述子性能相当, 甚至在某些变换条件下 GDOH 性能更优, 比如小视点变换和光照变化. 5.3 特征匹配的时间复杂度比较我们从图像数据集中选取 79 对图像, 包括各种不同的图像变换类型 ( 见表 1), 比较 SIFT 算法和本文算法的特征检测和特征匹配的时间复杂度.

8 249 计算机学报 2010 年在较小的视点变换时 ( 见图 10(b),GDOH 的性能最优, 尤其是在查错率低于 0.2 的情况下,GDOH 的优势较为明显, 在查错率高于 0.2 时,4 种描述子的性能十分接近. 图 10(c) 的结果表明, 在光照变化的情况下,4 种描述子都可以达到很好的性能 ( 查全率都在 0.8 以上 ), 而 GDOH 获得了最优的性能. 在图像间存在噪声干扰的情况下 ( 见图 10(d), 当查错率低于 0.5 时,4 种描述子性能相当 ; 当查错率高于 0.5 时,PCA SIFT 描述子的性能要明显低于其它 3 种描述子. 综合这些实验结果可以得出结论, 本文的 GDOH 描述子的性能和目前优秀的 SIFT PCA SIFT 以及 GLOH 描述子性能相当, 甚至在某些变换条件下 GDOH 性能更优, 比如小视点变换和光照变化. 5.3 特征匹配的时间复杂度比较我们从图像数据集中选取 79 对图像, 包括各种不同的图像变换类型 ( 见表 1), 比较 SIFT 算法和本文算法的特征检测和特征匹配的时间复杂度. 表 1 给出实验结果, 可以看出本文算法的平均特征检测时间与 SIFT 几乎一样, 没有很明显的速度增益, 但是总的平均匹配时间仅为 SIFT 的 40.9%(1419/ 3468), 特征匹配的速度增益非常显著, 这是由于本文提出的描述子向量维数更低. 表 1 本文提出的算法与犛犐犉犜算法的时间代价比较平均检测时间 SIFT/ms 平均匹配时间本文算法 /ms 平均检测时间平均匹配时间旋转 & 尺度缩放 (29 对 ) 视点变换 (25 对 ) 光照变化 (25 对图像 ) 总平均特征匹配实例图 1 给出了一组匹配结果的实例, 左图和右图分别显示了 SIFT 算法和本文算法的匹配结果, 设定的误差限是 1.5 个像素, 这里只显示前 10 个特征匹配作为比较. 匹配的图像对之间的旋转变化和尺度缩放都比较大, 而且图像细节信息比较丰富. 可以看出, 在这个例子当中本文算法的正确匹配率明显高于 SIFT 算法,SIFT 算法的正确匹配率仅有 50%, 而本文的算法对于所有的匹配都正确. 同时可以发现,SIFT 算法在这种具有丰富细节信息的图像间进行特征匹配的表现并不理想, 比较容易受到细小纹理的干扰, 导致查错率比较高. 图 1SIFT 算法和本文算法的匹配实例比较 5.5 图像检索应用我们在一个小的图像数据库上 1 进行图像检索实验以验证本文提出算法的有效性. 该数据库一共有 30 幅图像, 包含 10 组不同的物体场景, 每组是由 3 幅包含同一物体场景的不同变换的图像组成. 我们分别用 SIFT 算法和本文提出的算法分别提取图像局部特征, 然后为每个局部特征计算描述子向量, 接着对每两幅图像进行特征匹配, 并将匹配的特征个数作为图像间相似度测量准则. 最后按照文献 [17] 的计分规则, 对于每一幅图像返回 2 幅检索到的最相似图像, 如果这两幅图像和待检索图像在同一组, 加 2 分 ; 如果有一幅在同一组, 加 1 分 ; 否则, 没有加分. 在这样的规则下满分可以达到 60 分. 用两种算法得到的分数分别除以 60 就可以得到图像检索的正确率. 表 2 分别列出了 SIFT 算法和本文算法的图像检索的正确率, 以及两种算法的平均特征检测时间和平均特征匹配时间. 可以看出, 在这个实验中本文算法的图像检索性能要优于 SIFT 算法, 比 SIFT 算法的检索正确率高出 6.7%; 在特征检测速度方面, 两种算法基本持平 ; 而由于本文描述子维数更低, 使得本文算法的图像特征匹配速度优势明显, 比 SIFT 算法的速度提高 62.4%. 表 2 两种算法在图像检索实验中的性能比较图像检索平均特征检测平均特征匹配正确率 /% 时间 /ms 时间 /ms SIFT 本文算法图像检索数据库,htp:/ w.cs.cmu.edu/~yke/ pcasift/

5 期杨恒等 : 一种新的局部不变特征检测和描述算法 6 结论本文提出了一种新的局部不变特征检测和描述算法, 并应用于宽基线的图像匹配与检索. 在局部特征检测方面, 本文提出 Haris Diference 算法, 首先以多尺度的 Haris 角点作为初始点, 然后在其附近一定范围内搜索 DoG 函数的局部空间极值点作为特征点的位置和尺度信息, 最后为每个特征点计算主方向.

9 5 期杨恒等 : 一种新的局部不变特征检测和描述算法 6 结论本文提出了一种新的局部不变特征检测和描述算法, 并应用于宽基线的图像匹配与检索. 在局部特征检测方面, 本文提出 Haris Diference 算法, 首先以多尺度的 Haris 角点作为初始点, 然后在其附近一定范围内搜索 DoG 函数的局部空间极值点作为特征点的位置和尺度信息, 最后为每个特征点计算主方向.Haris Diference 具有比 Haris Laplace 和 Fast Hesian 更高的可重复率, 并且比 DoG 算法具有更好的抗干扰能力. 在特征描述方面, 本文提出的 GDOH 描述子不但与目前优秀的 SIFT,PCA SIFT 以及 GLOH 描述子性能相当, 甚至在某些变换条件下 GDOH 性能更优, 比如小视点变换和光照变化, 而更为重要的是 GDOH 特征向量的维数更低, 十分有利于提高图像特征匹配的速度. 大量图像匹配和检索的实验结果验证了本文算法的有效性. 参考文献 [1]SchafalitzkyF,ZisermanA.Multi viewmatchingforunor deredimagesets,or howdoiorganizemyholidaysnaps? / Procedingsofthe7thEuropeanConferenceonComputer Vision.Copenhagen,202: [2]BrownM,SzeliskiR,WinderS.Multi imagematchingusing multi scaleorientedpatches/procedingsoftheiecon ferenceoncomputervisionandpaternrecognition.san Diego,205: [3]SnavelyN,SeitzSM,SzeliskiR.Phototourism:Exploring photocolectionsin3d.acmtransactionsongraphics, 206,25(3): [4]BrownM,LoweDG.Automaticpanoramicimagestitching usinginvariantfeatures.internationaljournalofcomputer Vision,207,74(1):59 73 [5]MikolajczykK,LeibeB,SchieleB.Localfeatureforobject clasrecognition/procedingsofthe10thieinternation alconferenceoncomputervision.beijing,205: [6]MingAn Long,MaHua dong.region SIFTdescriptor basedcorespondencebetwenmultiplecameras.chinese 犢犃犖犌犎犲狀犵,bornin1980,Ph.D. candidate.hisresearchinterestsare imageprocesingandcomputervision, includinglocalinvariantfeatureextrac tion,imageclasificationandretrieval. JournalofComputers,208,31(4):650 61(inChinese) ( 明安龙, 马华东. 多摄像机之间基于区域 SIFT 描述子的目标匹配. 计算机学报,208,31(4):650 61) [7]SchmidC,MohrR.Localgrayvalueinvariantsforimagere trieval.ietransactionsonpaternanalysisandmachine Inteligence,197,19(5): [8]SchmidC,MohrR,BauckhageC.Evaluationofinterest pointdetectors.internationaljournalofcomputervision, 20,37(2): [9]DufournaudY,SchmidC,HoraudR.Matchingimageswith diferentresolutions/procedingsoftheieconferenceon ComputerVisionandPaternRecognition.HiltonHead Island,SouthCarolina,20: [10]LindebergT.Featuredetectionwithautomaticscaleselec tion.internationaljournalofcomputervision,198,30 (2):79 16 [1]LoweDG.Distinctiveimagefeaturesfromscale invariant keypoints.internationaljournalofcomputervision,204, 60(2):91 10 [12]MikolajczykK,SchmidC.Scale&afineinvariantinterest pointdetectors.internationaljournalofcomputervision, 204,60(1):63 86 [13]BayH,TuytelarsT,GolLV.SURF:Spededuprobust features/procedingsofthe9theuropeanconferenceon ComputerVision.Graz,Austria,206: [14]JohnsonAE,HebertM.Recognizingobjectsbymatching orientedpoints/procedingsoftheiecomputersociety ConferenceonComputerVisionandPaternRecognition. PuertoRico,197: [15]GolLV,MonsT,UngureanuD.Afine/photometricin variantsforplanarintensitypaterns/procedingsofthe4th EuropeanConferenceonComputerVision.Cambridge,UK, 196: [16]FlorackL,RomenyBH,KoenderinkJJ,ViergeverMA. Generalintensitytransformationsanddiferentialinvariants. JournalofMathematicalImagingandVision,194,4(2): [17]KeY,SukthankarR.PCA sift:amoredistinctiverepresen tationforlocalimagedescriptors/procedingsoftheie ComputerSocietyConferenceonComputerVisionandPat ternrecognition.washington,dc,204: [18]MikolajczykK,SchmidC.Aperformancevaluationoflocal descriptors.ietransactionsonpaternanalysisandma chineinteligence,205,27(10): 犠犃犖犌犙犻狀犵,bornin1969,Ph.D.,profesor,Ph.D. supervisor.hisresearchinterestsareimageprocesingand computervision,includingimagebasedmodelingandrender ing,imagecategorizationandrecognitionanddynamiclight fieldphotograph. 349

10 49 计算机学报 2010 年犅犪犮犽犵狉狅狌狀犱 Thispaperfocusesontheisuesoflocalfeaturedetec searchanddevelopmentprogram(863program)ofchina tionanddescriptionwhichcanbewidelyapliedincomputer (grantno.207a01z314).thensfcprojectistosolve visionaplications,suchaswide baselineimagematching theisuesoffeaturecorespondenceandoptimizationfrom andimageretrieval.infeaturedetectionaspect,recentlitera largescaleunorderedwidebaselineimages.the 863 pro turesarealbasedonthescalespacetheory.theproposed jectaimsat4dscenereconstructionbasedonmultipleweb Haris Diferencealgorithmoutperformsothertraditionalal baselineimages.theimagesareautomaticalygroupedac gorithms,suchasharis LaplaceandFast Hesian,interms cordingtothetimesequenceandthecorespondentrecon ofrepeatabilitycriterion.furthermore,itobtainshigherper structed3dscenecanbeviewedontimeline.thesystem formanceinnoiseresistancethandogalgorithm.infeature providesusersaneficientwaytoorganizelargeamountun descriptionaspect,theproposedgdoh(gradientdistance orderedimagesinthetemporalandspatialorders.somesys andorientationhistogram)algorithmcanachievesimilar temsonthereconstructionfromimageshavebendeveloped andevenbeterfeaturematchingperformancethanthestate inrecentyears.themostrepresentativeoneisthephoto of the artdescriptors,suchassift,pca SIFTandGLOH, Tourism,whichcanreconstruct3Dscenefromhundredsof whicharewidelyusedinvisionaplications.moreover,the imagesinafewdays.theprojectaimstoimprovingthere dimensionalityofthegdohdescriptorismuchlowerthan constructionacuracyandspedbasedonlargerscaleimage thesewidelyuseddescriptorswhichresultsinhighereficien set.thefirsttaskoftheprojectsistoimprovethefeature cyinfeaturebasedimagematchingandretrievalsystems. matchingperformance,whichisthekeyandimportantstep Theresearchworkandtheresultofthispaperisapartofthe ofthewholesystem.thispaperistoadressuchisue. projectsuportedbynationalnaturalsciencefoundationof Theproposedmethodcanimprovetheperformanceofeature China(No )andNationalHighTechnologyRe matchinginboththedetectionanddescriptionaspects.

JournalofSoiland WaterConservation Vol.32No.1 Feb.,2018!"#$%&' 1, 2, 3, 1, 4, 5, 1 ( , :;, ; ( ),0 5 <-. 4, ;3

321 20182 JournalofSoiland WaterConservation Vol.32No.1 Feb.,2018!"#$%&' 1, 2, 3, 1, 4, 5, 1 (1. 23 4,567089 :;, 100083; 2. 23 ( ),0 5 4,?@ 750021; 4.A-2