一种基于参考点距离的SIFT特征点匹配算法

第１０卷第３期一一一一一一一一一一一一一一智一能一系一统一学一报一一一一一一一一一一一一一Ｖｏｌ．１０?．３

２０１５年６月一一一一一一一一一一一一一ＣＡＡＩＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｔｅｌｌｉｇｅｎｔＳｙｓｔｅｍｓ一一一一一一一一一一一Ｊｕｎ．２０１５ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３?４７８５．２０１３１１０２０网络出版地址：ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／２３．１５３８．ｔｐ．２０１５０４０２．１５１８．００１．ｈｔｍｌ一种基于参考点距离的ＳＩＦＴ特征点匹配算法

唐坤１，韩斌２

（１．东南大学交通学院，江苏南京２１００９６；２．江苏科技大学计算机科学与工程学院，江苏镇江２１２０００）

摘一要：针对ＳＩＦＴ特征点匹配时间消耗大的问题，提出了一种基于参考点距离的ＳＩＦＴ特征点匹配算法 ＤＲＰ算法三该算法首先计算一次所有待匹配特征点到参考点之间的距离，对之进行快速排序并保存三然后计算待查询特征点到参考点的距离，并在已排序的距离中使用二分法搜索返回此距离的最近邻三最后以此最近邻为中心，在有限范围内搜索待查询特征点的近似最近邻三ＶＧＧ实验室ＡＣＦ图片库的测试结果表明，相比于经典的ＳＩＦＴ算法，ＤＲＰ算法可以在不损失匹配效果的前提下，有效降低ＳＩＦＴ特征点匹配的时间消耗三

关键词：ＳＩＦＴ；ＤＲＰ算法；特征点匹配；最近邻；参考点

中图分类号：ＴＰ３１９一文献标志码：Ａ一文章编号：１６７３?４７８５（２０１５）０３?０３７６?０５

中文引用格式：唐坤，韩斌．一种基于参考点距离的ＳＩＦＴ特征点匹配算法［Ｊ］．智能系统学报，２０１５，１０（３）：３７６?３８０．

英文引用格式：ＴＡＮＧＫｕｎ，ＨＡＮＢｉｎ．ＡＳＩＦＴｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｄｉｓｔａｎｃｅｔｏｒｅｆｅｒｅｎｃｅｐｏｉｎｔ［Ｊ］．ＣＡＡＩＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｔｅｌｌｉｇｅｎｔＳｙｓｔｅｍｓ，２０１５，１０（３）：３７６?３８０．

ＡＳＩＦＴｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｄｉｓｔａｎｃｅｔｏｒｅｆｅｒｅｎｃｅｐｏｉｎｔ

ＴＡＮＧＫｕｎ１，ＨＡＮＢｉｎ２

（１．ＳｃｈｏｏｌｏｆＴｒａｎｓｐｏｒｔａｔｉｏｎ，ＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００９６，Ｃｈｉｎａ；２．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＪｉａｎｇｓｕＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｚｈｅｎｊｉａｎｇ２１２０００，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｔｏａｄｄｒｅｓｓｔｈｅｈｉｇｈｔｉｍｅｃｏｓｔｏｆｆｅａｔｕｒｅｐｏｉｎｔｍａｔｃｈｉｎｇｉｎｓｃａｌｅｉｎｖａｒｉａｎｔｆｅａｔｕｒｅｔｒａｎｓｆｏｒｍ（ＳＩＦＴ），ａｎｅｗＳＩＦＴｆｅａｔｕｒｅｐｏｉｎｔｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｄｉｓｔａｎｃｅｔｏｒｅｆｅｒｅｎｃｅｐｏｉｎｔ ＤＲＰａｌｇｏｒｉｔｈｍｉｓｐｕｔｆｏｒｗａｒｄ．Ｆｉｒｓｔｌｙ，ｄｉｓｔａｎｃｅｓｆｒｏｍｔｈｅｒｅｆｅｒｅｎｃｅｐｏｉｎｔｔｏｅｖｅｒｙｆｅａｔｕｒｅｐｏｉｎｔｔｏｂｅｍａｔｃｈｅｄｉｓｃｏｍｐｕｔｅｄｕｓｉｎｇＤＲＰａｌｇｏｒｉｔｈｍ．Ｔｈｅｎ，ｔｈｅｓｅｄｉｓｔａｎｃｅｓｃｏｍｐｕｔｅｄｐｒｅｖｉｏｕｓｌｙｉｓｏｒｄｅｒｅｄａｎｄｓａｖｅｄｉｎａｄａｔａｓｅｔｎａｍｅｄａｓｄｉｓｔａｎｃｅｏｆｏｒｄｅｒｉｎｇ．Ｎｅｘｔ，ｄｉｓｔａｎｃｅｓｆｒｏｍｔｈｅｒｅｆｅｒｅｎｃｅｐｏｉｎｔｔｏｔｈｅｆｅａｔｕｒｅｐｏｉｎｔｔｏｂｅｑｕｅｒｉｅｄｉｓａｌｓｏｃｏｍｐｕｔｅｄ．Ａｆｔｅｒｔｈａｔ，ｔｈｅｎｅａｒｅｓｔｎｅｉｇｈ?ｂｏｒｏｆｔｈｅｄｉｓｔａｎｃｅｉｎｄｉｓｔａｎｃｅｏｆｏｒｄｅｒｉｎｇｉｓｒｅｔｒｉｅｖｅｄｗｉｔｈｂｉｎａｒｙｓｅａｒｃｈａｎｄｒｅｔｕｒｎｅｄａｓｉｎｄｅｘｏｆｃｅｎｔｅｒ．Ｆｉｎａｌｌｙ，ｔｈｅｎｅａｒｅｓｔｎｅｉｇｈｂｏｒｏｆｆｅａｔｕｒｅｐｏｉｎｔｔｏｂｅｑｕｅｒｉｅｄｉｓｓｅａｒｃｈｅｄｏｎｅｂｙｏｎｅｉｎａｃｅｒｔａｉｎｒａｎｇｅｗｈｏｓｅｃｅｎｔｅｒｉｓｉｎｄｅｘｏｆｃｅｎｔｅｒ．ＩｔｉｓｐｒｏｖｅｎｂｙｅｘｐｅｒｉｍｅｎｔｔｅｓｔｅｄｏｎＡＣＦ（ａｆｆｉｎｅｃｏｖａｒｉａｎｔｆｅａｔｕｒｅｓ）ｐｉｃｔｕｒｅｓｆｒｏｍＶＧＧ（ｖｉｓｕａｌｇｅｏｍｅｔｒｙｇｒｏｕｐ）ｌａｂｏｒａｔｏｒｙｔｈａｔＤＲＰａｌｇｏｒｉｔｈｍｃａｎｅｆｆｅｃｔｉｖｅｌｙｄｅｃｒｅａｓｅｔｈｅｔｉｍｅｃｏｓｔｏｆＳＩＦＴｆｅａｔｕｒｅｐｏｉｎｔｓｍａｔｃｈｉｎｇｗｉｔｈｏｕｔｌｏｓｓｏｆｍａｔｃｈｉｎｇｒｅｓｕｌｔｓｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｃｌａｓｓｉｃａｌＳＩＦＴａｌｇｏｒｉｔｈｍ．

Ｋｅｙｗｏｒｄｓ：ｓｃａｌｅｉｎｖａｒｉａｎｔｆｅａｔｕｒｅｔｒａｎｓｆｏｒｍ（ＳＩＦＴ）；ｄｉｓｔａｎｃｅｔｏｒｅｆｅｒｅｎｃｅｐｏｉｎｔ（ＤＲＰ）ａｌｇｏｒｉｔｈｍ；ｆｅａｔｕｒｅｐｏｉｎｔｍａｔｃｈｉｎｇ；ｎｅａｒｅｓｔｎｅｉｇｈｂｏｒ；ｒｅｆｅｒｅｎｃｅｐｏｉｎｔ收稿日期：２０１３?１１?２８．一网络出版日期：２０１４?０４?０２．

基金项目：国家自然科学基金资助项目（６１３７４１９５）；中央高校基本科

研业务费专项资金资助项目；江苏省普通高校研究生科研

创新计划资助项目（ＫＹＬＸ＿０１８０）．

通信作者：唐坤．Ｅ?ｍａｉｌ：ｔｋｐａｐｅｒｚｃ＠ｓｉｎａ．ｃｎ．一一Ｌｏｗｅ提出的尺度不变特征变换（ｓｃａｌｅｉｎｖａｒｉａｎｔｆｅａｔｕｒｅｔｒａｎｓｆｏｒｍ，ＳＩＦＴ）［１］是一种鲁棒性强的图像局

部特征提取算法，具有对旋转二光照二尺度变化等保持不变性［２］，广泛应用于三维重建二目标识别二图像融合等领域［３］三ＳＩＦＴ算法由特征点检测及描述与特征点匹配两部分构成，其中，ＳＩＦＴ特征点匹配实质上可以转化为在高维空间中搜索特征点最近邻的问题，并且在很多情况下，只需要得到查询特征点的