第２８卷第３期 吉林建筑工程学院学报 Ｖ０Ｉ．２８ Ｎｏ．３ ２０１１年６月 Ｊｏｕｒｎａｌ ｏｆ Ｊｉｌｉｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ａｒｃｈｉｔｅｃｔｕｒｅ＆Ｃｉｖｉｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｊｕｎ．２０１１ 基于局部特征图像匹配算法改进冰 郭秀娟 杨 磊 （１：吉林建筑工程学院计算机科学与工程学院，长春吉林建筑工程学院电气与电子信息学院，长春１３０１ １８； ２：１３０１１８） 摘要：本文针对ＳＩＦＴ算法存在着特征提取及匹配速度慢，在灰度变化相似的区域产生误匹配的缺陷，讨论了ＳＩＦＴ 的改进算法一ＳＵＲＦ算法的原理及应用方法，对算法进行检验，指出ＳＵＲＦ算法在提取特征点时更偏重于提取鲁棒 性较强的点，同时，摒弃一些鲁棒性较弱的点，对鲁棒性强的特征进行匹配以减少计算时间，使ＳＵＲＦ在实时性处理 和大量图片搜索的应用上具有更广阔的空间． 关键词：ＳＩＦＴ算法￣ＳＵＲＦ算法；特征点；鲁棒性 中图分类号：ＴＰ ３９１．４ 文献标志码：Ａ 文章编号：１００９—０１８５（２０１１）０３—００７９—０４ Ａ Ｎｅｗ Ｉｍａｇｅ Ｍａｔｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ Ｌｏｃａｌ Ｆｅａｔｕｒｅ ＧＵＯ Ｘｉｕ—ｊｕａｎ ，ＹＡＮＧ Ｌｅｉ （１：Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉｌｉｎ Ｉｎｓｔｉｔｕｔｅ ｏｆＡｒｃｈｉｔｅｃｔｕｒｅ ａｎｄ Ｃｉｖｉｌ Ｅｎｇｉｎｅｅｉｒｎｇ，Ｃｈａｎｇｃｈｕｎ，Ｃｈｉｎａ １３０１１８； ２：＆ｈｏｄ ｏｆＥｌｅｃｔｒｉｃａｌ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃ ｌｎｔｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉｌｉｎ Ｉｎｓｔｉｔｕｔｅ ｏｆＡｒｃｈｉｔｅｃｔｕｒｅ ａｎｄ Ｃｉｖｉｌ Ｅｎｇｎｅｅｒｉｎｇ， 删 Ｏｒ／ｈａ １３０１１８） Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ ａｔ ｔｈｅ ｓｌｏｗｌｙ ｍａｔｃｈ ｏｆ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ，ｓｉｍｉｌａｒ ｍｉｓｍａｔｃｈ ｄｅｆｅｃｔｓ ｉｎ ｔｈｅ ｇｒａｙ ａｒｅａ，ｔｈｅ ｐａｐｅｒ ｄｉｓ— ｃｕｓｓｅｄ ｔｈｅ ｔｈｅｏｒｙ ａｎｄ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｈｅ ｔｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｈｍ ＳＵＲＦ，ｗｈｉｔｃｈ ｉｓ ｄｅｒｉｖｅｄ ｆｒｏｍ ＳＩＦＴ．Ｏｎ ｔｅｓｔｉｎｇ ｔｈｅ ａｌｇｏ— ｒｉｈｍ，ｗｅ ｆｔｉｎｄ ｏｕｔ ｈａｔｔ ＳＵＲＦ ｗｏｕｌｄ ｍｏｒｅ ｒｏｂｕｓｔ ｅｍｐｈａｓｉｓ ｏｎ ａ ｓｔｏｎｇ ｐｏｉｒｎｔ ｗｈｉｌｅ ｅｘｔｒａｃｔｉｎｇ．Ａｎｄ ｗｈａｔ ｉｓ ｍｏｒｅ，ｔｈｅ ａｌｇｏｒｉｈｔｍ ｒｅｊｅｃｔｅｄ ａ ｎｕｍｂｅｒ ｏｆ ｔｈｅ ｐｏｉｎｔｓ ｏｆ ｗｅａｋ ｒｏｂｕｓｔｎｅｓｓ，ｗｈｉｃｈ ｗｉｌｌ ｒｅｄｕｃｅ ｔｈｅ ｃｏｍｐｕｔｉｎｇ ｔｉｍｅ ｗｈｉｌｅ ｍａｔｃｈｉｎｇ ｈｅ ｒｔｏｂｕｓｔ ｆｅａｔｕｒｅｓ．Ｓｏ ＳＵＲＦ ｗｉｌｌ ｈａｖｅ ｍｏｒｅ ｐｒｏｓｐｅｃｔｓ ｏｎ ｒｅａｌ—ｔｉｍｅ ｐｒｏｃｅｓｓｉｎｇ ａｎｄ ｔｈｅ ｍａｓｓ ｉｍａｇｅ ｓｅａｒｃｈ． Ｋｅｙｗｏｒｄｓ：ＳＩＦＴ ａｌｇｏｒｉｔｈｍ；ＳＵＲＦ ａｌｇｏｒｉｔｈｍ；ｆｅａｔｕｒｅ ｐｏｉｎｔｓ；ｒｏｂｕｓｔｎｅｓｓ ０ 引言 图像模式识别算法，按其特征可分为基于全局特征和基于局部特征．主流的图像匹配算法，是试图提取 目标在某种条件下的不变量…作为特征，在不同图像中匹配这些特征，以达到对目标进行识别的目的．不同 尺度下提取的特征，可分为大尺度全局特征和小尺度局部特征两大类．最具代表性的是Ｌｏｗｅ于１９９９年在 ＩＣＣＶ上提出 并于２００４年发展成熟 的ＳＩＴ算法．由于ＳＩＦＦＴ算法拥有抵抗尺度、旋转变化，以及部分抗 光照均匀变化的能力，研究人员已尝试将其应用于图像导航避障 领域，但该算法存在着特征提取及匹配 速度慢，在灰度变化相似的区域产生误匹配的缺陷，了该算法的应用，尤其是在讲求实时性且存在明显 视角变化的图像导航中的应用．因此，学者们从降低描述器维数【５ 和增强描述器鲁棒性［６ 两方面对其进行 有效改进．目前，ＳＵＲＦ是最成功的针对ＳＩＦＴ改进的算法之一． １ ＳＵＲＦ算法描述 鲁棒特征加速（ＳＵＲＦ）是Ｂａｙ等人于２００６年在ＥＣＣＶ上提出的针对ＳＩＴ运算速度慢而进行改进的算 Ｆ收稿日期：２０１０—１１—０５． 作者简介：郭秀娟（１９６１一），女，吉林省德惠人，教授，博士． ＋基金项目：建设部软科学研究项目（２０１０一Ｋ９—４３）；吉林省教育厅“十一五”科学技术研究项目（吉教科合字２０１０第３０３号） ８０ 吉林建筑工程学院学报 第２８卷 法Ｌ６ Ｊ，已被研究人员用于陕速虹膜检测，计算速度较ＳＩＦＴ快，且鲁棒性较ＳＩＴ并未有较明显地下降．Ｆ １．１ ＳＵＦＲ探测器方案 不同于ＳＩＴ算法，ＦＳＵＲＦ的探测器的设计是基于Ｈｅｓｓｉａｎ矩阵的． 设，（ ，Ｙ）为输入图像， 为卷积运算符，６为尺度变量，则Ｇ（ ，Ｙ，６）可定义为： Ｇ（ ，Ｙ，占）＝ ＿ｅ （１） 则图像中任意一点 ＝（ ，Ｙ）处尺度 的Ｈｅｓｓｉａｎ矩阵可定义为： 日ｃ ，ｙ， ＝ｆ “’ｙ’， Ｌ（ ｘｙ８￣ｙ ，； 二 ： ： ；］ ，Ｌｒｙ ）＝ ｃ２ （３） 其中 ＝ ）＝ 在实际应用中需要对高斯函数进行离散化处理，因此，ＳＵＲＦ算法采用盒形滤波器（ｂｏｘ—ｆｉｌｔｅｒ）和积分 图像近似不同尺度的ＬｏＧ．盒形滤波器系数由Ｈｅｓｓｉａｎ矩阵的Ｆ范数进行约束，表示为行列式的形式： ｌＩ （１ ２ ） ．一ｏ－ ９ ・ｌＩ Ｄ （９）ｌＩ， …～ … ㈩ （５） 可得出：ｄｅｔ（Ｈ）＝Ｄ Ｄ 一（０．９Ｄ ）２ 根据（５）式，为保证其Ｆ范数在任意尺寸的滤波器模板上都是常数，滤波器的响应按其模板的大小进行 规范化． 在ＳＩＴ中，图像被高斯平滑后再进行亚抽样以获得更高一层的尺度金字塔，而ＳＵＲＦ使用了盒型滤波 Ｆ器和积分图像近似，对于不同的层数可使用相应大小的滤波器，避免了对上一层进行亚抽样的步骤，计算速 度明显加快．为了提取尺度不变的特征点，ＳＵＲＦ也采用了尺度插值和３ ３ ３的非极值抑制方法． １．２ ＳＵＲＦ描述器方案 ＳＵＲＦ描述器所描述的是兴趣点周围的梯度矢量，采用Ｈａａｒ小波分别计算区域内水平和垂直方向响应， 小波的尺度与盒型滤波器所逼近的尺度是一致的．令：Ｓ（ ）为Ｈａａｒ尺度函数， （ ）为Ｈａａｒ小波函数，则水 平和垂直方向的小波函数可分别表示为：ｓ（，，） （ ）和ｓ（ ） （），）． 将检测到的响应归为４个维度： ， ，Ｉ Ｉ，Ｉ研Ｉ．由于ＳＵＲＦ描述器的检测范围是４，一＝４的子区域，因 此描述器大小是４ ４ ４，表征为６４维的描述器特征向量．为获得旋转不变和一定的抗剪切、抗照度变化的 能力，ＳＵＲＦ描述器也进行了单位化． ２算法试验 ２．１图片检测 本文采用标准测试图片和较模糊的实拍图片进行试验，旨在比较不同环境下两种算法的结果． ２．１．１ 测试图组 标准测试图片一Ｌｅｎａ，左是原始图片，右是旋转９０。且加入 ＝０．０２的高斯噪声的图片，旨在比较两种 算法抗旋转和抗噪声的能力．图１为ＳＩＴ匹配的直观效果（匹配特征点区域为采用连线表示）；Ｆ图２为ＳＵＲＦ 算法匹配的直观效果（匹配特征点区域的采用圆圈表示）． ２．１．２ 实拍图组 较模糊的实拍图——室内实拍场景，左为水平拍摄，右为垂直拍摄，背景明显较为复杂，且有拍摄过程 中产生的运动模糊，旨在比较两种算法在复杂背景下、不同视角重现特征点以及抗运动模糊的能力．图３为 ＳＩＦｒ匹配的直观效果；图４为ＳＵＲＦ匹配的直观效果． ８２ 吉林建筑工程学院学报 第２８卷 ３ 结语 本文针对ＳＩＦＴ算法存在着特征提取及匹配速度慢，在灰度变化相似的区域产生误匹配的缺陷，讨论了 ＳＵＲＦ算法的探测器和描述器方案，并通过标准和实拍图片进行算法检验，表明ＳＵＲＦ算法在提取鲁棒性强 的特征时摒弃鲁棒性弱的特征，进而对鲁棒性强的特征进行匹配以削减计算时间，使ＳＵＲＦ在实时性处理和 大量图片搜索应用上拥有巨大价值，也为今后算法改进与加速而提供明确的指导思想，且具有重大的借鉴 意义． 参考文献 【１］丁雪梅，王维雅，黄向东．基于差分和特征不变量的运动目标检测和跟踪［Ｊ］．光学精密程，２００７，１５（４）：５７０—５７６． ［２］ＬＯＷＥ Ｄ Ｇ．Ｏｂｊｅｃｔ ｒｅｃｏｇｎｉｔｉｏｎ ｆｒｏｍ ｌｏｃａｌ ｓｃａｌｅ—ｉｎｖａｒｉａｎｔ ｆｅａｔｕｒｅｓ［Ｃ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，１９９９：１１５０一ｌ１５７． ［３］ＬＯＷＥ Ｄ Ｇ．Ｄｉｓｔｉｎｃｔｉｖｅ ｉｍａｇ ｅ ｆｅａｔｕｒｅｓ ｆｒ ｏｍ ｓｃａｌｅ ｉｎｖａｒｉａｎｔ ｋｅｙｐｏｉｎｔｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｎｒａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，２００４，６０（２）：９１—１１０． ［４］ＣＨＡＶＥＳ Ａ，ＧＵＳＴＡＦＵＳＯＮ Ｄ．Ｖｉｓｉｏｎ—Ｂａｓｅｄ Ｏｂｓｔａｃｌｅ Ａｖｏｉｄａｎｃｅ Ｕｓｉｎｇ ＳＩＦＴ Ｆｅａｕｔｒｅｓ［ｃ］．Ｐｒｃｏｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ａｄｖａｎｃｅｓ ｉｎ Ｖｉｓｕａｌ Ｃｏｍｐｕｔｉｎｇ，２００９：５５０—５５７． ［５］Ｋｅ Ｙ，ＳＵＫＴＨＡＮＫＡ Ｒ．．ＰＣＡ—ＳＩＴＦ：Ａ ｍｏｒｅ ｄｉｓｔｉｎｃｔｉｖｅ ｅｒｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒｌｏｃａｌ ｉｍａｇｅ ｄｅｓｃｒｉｐｔｏｒｓ［Ｃ］．ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ｎａｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，２００４：５０６—５１３． ［６］纪华，吴元吴，孙宏海，王延杰．结合全局信息的ＳＩＴＦ特征匹配算法［Ｊ］．光学精密工程，２００９，１７（２）：４３９—４４４． （上接第７８页） ＝（ｗｄ一 ｍ）） （ｗｄ—ｗｆ（ｍ））＋ １７１＂， Ｄ Ｄｍ （３１ａ） 近似线性式为： ＝（ｗｙ—ｗＡｘ） （ｔｏｙ—ｗＡｘ）＋ （ｍ。＋ ） Ｄ Ｄ（ｍ。＋ ） （３１ｂ） 参数校正解可表为： ＝［（ｗＡ） ｗＡ＋ ，］ ［（ｗＡ） ｗｙ一 玑。］ （３２） 其迭代公式为： “ ｍ＝ｍ ＋［（ ） ＋ ，］ ［（黝） 一 ｍ ］ （３３） 因为Ｄ＝ｊ，这里 ｊ以控制求解的步长，而 ｍ 有助于减小其向零矢量ｈ的偏置，我们将这种方法称为 平滑度约束反演或最小偏置算法． 参考文献 ［１］李兴斯．非线性极大极小问题的一个有效解法［Ｊ］．科学通报，１９９９（１９）：１０一ｌ２． ［２］周德龙，高文，赵德斌．基于奇异值分解和判别式ＫＬ投影的人脸识别［Ｊ］．软件学报，２００３（４）：７８３—７８９ ［３］王芳，陈生昌．解非线性反演问题的新策略［Ｊ］．石油物探，１９９９（３）：７６—８５．
