第10卷第3期 智能系统学报 Vol.10 No.3 2015年6月 CAAI Transactions on Intelligent Systems Jum.2015 D0:10.3969/j.issn.1673-4785.201311020 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150402.1518.001.html 一种基于参考点距离的SIFT特征点匹配算法 唐坤，韩斌 (1.东南大学交通学院，江苏南京210096：2.江苏科技大学计算机科学与工程学院，江苏镇江212000) 摘要：针对SFT特征点匹配时间消耗大的问题，提出了一种基于参考点距离的SFT特征点匹配算法一DRP算法。 该算法首先计算一次所有待匹配特征点到参考点之间的距离，对之进行快速排序并保存。然后计算待查询特征点 到参考点的距离，并在已排序的距离中使用二分法搜索返回此距离的最近邻。最后以此最近邻为中心，在有限范围 内搜索待查询特征点的近似最近邻。VGG实验室ACF图片库的测试结果表明，相比于经典的SIFT算法，DRP算法 可以在不损失匹配效果的前提下，有效降低ST特征点匹配的时间消耗。 关键词：SIFT:DRP算法；特征点匹配：最近邻：参考点 中图分类号：TP319文献标志码：A文章编号：1673-4785(2015)03-0376-05 中文引用格式：唐坤，韩斌.一种基于参考点距离的ST特征点匹配算法[J].智能系统学报，2015,10(3)：376-380. 英文引用格式：TANGKun,HAN Bin.A SIFT matching algorithm based on the distance to reference point[J].CAAI Transactions on Intelligent Systems,2015,10(3):376-380. A SIFT matching algorithm based on the distance to reference point TANG Kun',HAN Bin2 (1.School of Transportation,Southeast University,Nanjing 210096,China;2.School of Computer Science and Engineering,Jiangsu University of Science and Technology,Zhenjiang 212000,China) Abstract:To address the high time cost of feature point matching in scale invariant feature transform (SIFT),a new SIFT feature point matching algorithm based on the distance to reference point-DRP algorithm is put forward. Firstly,distances from the reference point to every feature point to be matched is computed using DRP algorithm. Then,these distances computed previously is ordered and saved in a dataset named as distance of ordering.Next, distances from the reference point to the feature point to be queried is also computed.After that,the nearest neigh- bor of the distance in distance of ordering is retrieved with binary search and returned as index of center.Finally, the nearest neighbor of feature point to be queried is searched one by one in a certain range whose center is index of center.It is proven by experiment tested on ACF (affine covariant features)pictures from VGG(visual geometry group)laboratory that DRP algorithm can effectively decrease the time cost of SIFT feature points matching without loss of matching results compared with the classical SIFT algorithm. Keywords:scale invariant feature transform (SIFT);distance to reference point (DRP)algorithm;feature point matching;nearest neighbor;reference point Lowe提出的尺度不变特征变换(scale invariant 部特征提取算法，具有对旋转、光照、尺度变化等保 feature transform,SIFT)是一种鲁棒性强的图像局 持不变性)，广泛应用于三维重建、目标识别、图像 融合等领域]。ST算法由特征点检测及描述与 收稿日期：2013-11-28.网络出版日期：2014-04-02. 基金项目：国家自然科学基金资助项目(61374195)：中央高校基本科 特征点匹配两部分构成，其中，SFT特征点匹配实 研业务费专项资金资助项目：江苏省普通高校研究生科研 质上可以转化为在高维空间中搜索特征点最近邻的 创新计划资助项目(KYLX0180). 通信作者：唐坤.E-mail:tkpaperze(@sina.cm 问题，并且在很多情况下，只需要得到查询特征点的
第 １０ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．３ ２０１５ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３１１０２０ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０４０２．１５１８．００１．ｈｔｍｌ 一种基于参考点距离的 ＳＩＦＴ 特征点匹配算法 唐坤１ ，韩斌２ （１．东南大学 交通学院，江苏 南京 ２１００９６；２．江苏科技大学 计算机科学与工程学院，江苏 镇江 ２１２０００） 摘 要：针对 ＳＩＦＴ 特征点匹配时间消耗大的问题，提出了一种基于参考点距离的 ＳＩＦＴ 特征点匹配算法—ＤＲＰ 算法。 该算法首先计算一次所有待匹配特征点到参考点之间的距离，对之进行快速排序并保存。 然后计算待查询特征点 到参考点的距离，并在已排序的距离中使用二分法搜索返回此距离的最近邻。 最后以此最近邻为中心，在有限范围 内搜索待查询特征点的近似最近邻。 ＶＧＧ 实验室 ＡＣＦ 图片库的测试结果表明，相比于经典的 ＳＩＦＴ 算法，ＤＲＰ 算法 可以在不损失匹配效果的前提下，有效降低 ＳＩＦＴ 特征点匹配的时间消耗。 关键词：ＳＩＦＴ；ＤＲＰ 算法；特征点匹配；最近邻；参考点 中图分类号：ＴＰ３１９ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０３⁃０３７６⁃０５ 中文引用格式：唐坤，韩斌． 一种基于参考点距离的 ＳＩＦＴ 特征点匹配算法［Ｊ］． 智能系统学报， ２０１５， １０（３）： ３７６⁃３８０． 英文引用格式：ＴＡＮＧ Ｋｕｎ， ＨＡＮ Ｂｉｎ． Ａ ＳＩＦＴ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｉｓｔａｎｃｅ ｔｏ ｒｅｆｅｒｅｎｃｅ ｐｏｉｎｔ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（３）： ３７６⁃３８０． Ａ ＳＩＦＴ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｉｓｔａｎｃｅ ｔｏ ｒｅｆｅｒｅｎｃｅ ｐｏｉｎｔ ＴＡＮＧ Ｋｕｎ １ ， ＨＡＮ Ｂｉｎ ２ （１． Ｓｃｈｏｏｌ ｏｆ Ｔｒａｎｓｐｏｒｔａｔｉｏｎ， Ｓｏｕｔｈｅａｓｔ Ｕｎｉｖｅｒｓｉｔｙ， Ｎａｎｊｉｎｇ ２１００９６， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｚｈｅｎｊｉａｎｇ ２１２０００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏ ａｄｄｒｅｓｓ ｔｈｅ ｈｉｇｈ ｔｉｍｅ ｃｏｓｔ ｏｆ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｍａｔｃｈｉｎｇ ｉｎ ｓｃａｌｅ ｉｎｖａｒｉａｎｔ ｆｅａｔｕｒｅ ｔｒａｎｓｆｏｒｍ （ ＳＩＦＴ）， ａ ｎｅｗ ＳＩＦＴ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｉｓｔａｎｃｅ ｔｏ ｒｅｆｅｒｅｎｃｅ ｐｏｉｎｔ—ＤＲＰ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｕｔ ｆｏｒｗａｒｄ． Ｆｉｒｓｔｌｙ， ｄｉｓｔａｎｃｅｓ ｆｒｏｍ ｔｈｅ ｒｅｆｅｒｅｎｃｅ ｐｏｉｎｔ ｔｏ ｅｖｅｒｙ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｔｏ ｂｅ ｍａｔｃｈｅｄ ｉｓ ｃｏｍｐｕｔｅｄ ｕｓｉｎｇ ＤＲＰ ａｌｇｏｒｉｔｈｍ． Ｔｈｅｎ， ｔｈｅｓｅ ｄｉｓｔａｎｃｅｓ ｃｏｍｐｕｔｅｄ ｐｒｅｖｉｏｕｓｌｙ ｉｓ ｏｒｄｅｒｅｄ ａｎｄ ｓａｖｅｄ ｉｎ ａ ｄａｔａｓｅｔ ｎａｍｅｄ ａｓ ｄｉｓｔａｎｃｅ ｏｆ ｏｒｄｅｒｉｎｇ． Ｎｅｘｔ， ｄｉｓｔａｎｃｅｓ ｆｒｏｍ ｔｈｅ ｒｅｆｅｒｅｎｃｅ ｐｏｉｎｔ ｔｏ ｔｈｅ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｔｏ ｂｅ ｑｕｅｒｉｅｄ ｉｓ ａｌｓｏ ｃｏｍｐｕｔｅｄ． Ａｆｔｅｒ ｔｈａｔ， ｔｈｅ ｎｅａｒｅｓｔ ｎｅｉｇｈ⁃ ｂｏｒ ｏｆ ｔｈｅ ｄｉｓｔａｎｃｅ ｉｎ ｄｉｓｔａｎｃｅ ｏｆ ｏｒｄｅｒｉｎｇ ｉｓ ｒｅｔｒｉｅｖｅｄ ｗｉｔｈ ｂｉｎａｒｙ ｓｅａｒｃｈ ａｎｄ ｒｅｔｕｒｎｅｄ ａｓ ｉｎｄｅｘ ｏｆ ｃｅｎｔｅｒ． Ｆｉｎａｌｌｙ， ｔｈｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｏｆ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｔｏ ｂｅ ｑｕｅｒｉｅｄ ｉｓ ｓｅａｒｃｈｅｄ ｏｎｅ ｂｙ ｏｎｅ ｉｎ ａ ｃｅｒｔａｉｎ ｒａｎｇｅ ｗｈｏｓｅ ｃｅｎｔｅｒ ｉｓ ｉｎｄｅｘ ｏｆ ｃｅｎｔｅｒ． Ｉｔ ｉｓ ｐｒｏｖｅｎ ｂｙ ｅｘｐｅｒｉｍｅｎｔ ｔｅｓｔｅｄ ｏｎ ＡＣＦ （ ａｆｆｉｎｅ ｃｏｖａｒｉａｎｔ ｆｅａｔｕｒｅｓ） ｐｉｃｔｕｒｅｓ ｆｒｏｍ ＶＧＧ（ ｖｉｓｕａｌ ｇｅｏｍｅｔｒｙ ｇｒｏｕｐ） ｌａｂｏｒａｔｏｒｙ ｔｈａｔ ＤＲＰ ａｌｇｏｒｉｔｈｍ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｄｅｃｒｅａｓｅ ｔｈｅ ｔｉｍｅ ｃｏｓｔ ｏｆ ＳＩＦＴ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ ｍａｔｃｈｉｎｇ ｗｉｔｈｏｕｔ ｌｏｓｓ ｏｆ ｍａｔｃｈｉｎｇ ｒｅｓｕｌｔｓ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｃｌａｓｓｉｃａｌ ＳＩＦＴ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｓｃａｌｅ ｉｎｖａｒｉａｎｔ ｆｅａｔｕｒｅ ｔｒａｎｓｆｏｒｍ （ＳＩＦＴ）； ｄｉｓｔａｎｃｅ ｔｏ ｒｅｆｅｒｅｎｃｅ ｐｏｉｎｔ （ＤＲＰ） ａｌｇｏｒｉｔｈｍ； ｆｅａｔｕｒｅ ｐｏｉｎｔ ｍａｔｃｈｉｎｇ； ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ； ｒｅｆｅｒｅｎｃｅ ｐｏｉｎｔ 收稿日期：２０１３⁃１１⁃２８． 网络出版日期：２０１４⁃０４⁃０２． 基金项目：国家自然科学基金资助项目（６１３７４１９５）；中央高校基本科 研业务费专项资金资助项目；江苏省普通高校研究生科研 创新计划资助项目（ＫＹＬＸ＿０１８０）． 通信作者：唐坤． Ｅ⁃ｍａｉｌ： ｔｋｐａｐｅｒｚｃ＠ ｓｉｎａ．ｃｎ． Ｌｏｗｅ 提出的尺度不变特征变换（ ｓｃａｌｅ ｉｎｖａｒｉａｎｔ ｆｅａｔｕｒｅ ｔｒａｎｓｆｏｒｍ， ＳＩＦＴ） ［１］是一种鲁棒性强的图像局 部特征提取算法，具有对旋转、光照、尺度变化等保 持不变性［２］ ，广泛应用于三维重建、目标识别、图像 融合等领域［３］ 。 ＳＩＦＴ 算法由特征点检测及描述与 特征点匹配两部分构成，其中，ＳＩＦＴ 特征点匹配实 质上可以转化为在高维空间中搜索特征点最近邻的 问题，并且在很多情况下，只需要得到查询特征点的
第3期 唐坤，等：一种基于参考点距离的SFT特征点匹配算法 ·377. 近似最近邻就足够了)。据此近年来提出了一些 需要在F,中搜索Pn的最近邻。设定一个参考点 相关算法，其中，Lowe提出的最优节点优先算法 卫，则对于每一个需要搜索的P,Pm与参考点 (best bin first,BBF)[s)在K-D树索引的基础上，使 P,构成向量P,P是确定的（长度和方向），若F,中 用优先队列和限制回溯查询次数来提高搜索最近邻 所有点与设定参考点P,构成的向量P,P:与P,Pm 的效率。va+-file算法[将数据集转换到KLT域， 之间的夹角都为0时，则使向量|P,P:→ 然后采用均匀量化划分来提高va-le算法[)的过 |P,Pcos的点P:就是Pn的最近邻。 滤效率。iDistance算法[]对高维数据空间进行划 若集合F:中所有特征点与设定参考点P,构成 分，使用B+-tree结果来组织参考点并搜索最近邻。 的向量P,P:与P,P之间的夹角不都为6时，即 LSH(locality sensitive hashing,LSH)算法[9-1o通过 不相等时，上述结论并不一定成立。如图1的三维 Hash函数将邻近高维点集映射到Hash表的同一个 空间所示。 桶中，从而提高搜索最近邻效率。基于聚类分析的 B+-tree算法[)采用类B+-tree索引结构，通过更加 IP.Pl-cos(P.P,P.PIP.P 细致的划分数据来加快搜索速度。MRSVQH2]根 P,P.-cos(P.P.P,P)P,P 据选择子向量的L2范数来量化和散列特征向量，仅 考虑具有与查询向量相同Hash值的集合，从而提高 了搜索速度。 本文在以上研究的基础上，提出了一种基于参 P PP P:l 考点距离的SFT特征点匹配算法一DRP算法，并 通过实验与经典的BBF算法相比，来验证基于DRP 算法的SIFT特征点匹配效果。 图1不同夹角时的最小距离 1 DRP算法 Fig.1 The minimum distance of different angle 尽管|P,P=cos(P,P,P,Pm〉P,Pen|, 1.1DRP算法原理 设d维欧式空间R中2个点P,=(x1,x2,…, 而|P,P,|>cos(P,P,P,Pm）P,Pm|。但是， xa),P2=(（y1y2,…,ya),两点对应的向量分别为 P2相对于卫1更靠近Pn。 V,=[x1x2…x],V2=[y2…ya]。则P、,两 为了尽可能的得到P,的最近邻，本文将搜索 范围扩大到集合F中的所有点。如图2所示。 点之间的欧式距离D(P,P2)为 F=(Pi Ri PP |V2=x好+x号+…+x |V22=y好+y经+…+y P PPP X Vi V2=x1y1+x2y2+.+xyd 图2在一定区域内搜索最近邻 (1) Fig.2 Search the nearest neighbor in a specified area 式中：|V,|、|V2|为向量V,与V2的模，〈V,V2)》 为向量V,与V2之间的夹角。 若将搜索范围扩大到以P,为球心，R,为半径 由式(1)可知，若|V,|确定且V,与V2的夹角 的球外，R为半径的球内区域，则可得到P的真 一定时，当|V2→|V,cos(V1,V2〉时，向量V,与 正最近邻P2。随着R,的减小和R的增大，搜索到 V,对应的P,与P,两点之间的距离D(P,P,)取最 P的真正最近邻的概率也随之增大。由此可知， 小值。 当F,中所有点与设定参考点P构成的向量P,P:与 设d维欧式空间R中的一个点集合F,= P,P之间的夹角不相等时，只需要选择一个合适 {P:lPeR,i=1,2,…,n},对于PeryER, 的搜索范围R与R击，仍然可以搜索到P的真正 最近邻
近似最近邻就足够了［４］ 。 据此近年来提出了一些 相关算法，其中， Ｌｏｗｅ 提出的最优节点优先算法 （ｂｅｓｔ ｂｉｎ ｆｉｒｓｔ， ＢＢＦ） ［５］ 在 Ｋ⁃Ｄ 树索引的基础上，使 用优先队列和限制回溯查询次数来提高搜索最近邻 的效率。 ｖａ＋⁃ｆｉｌｅ 算法［６］ 将数据集转换到 ＫＬＴ 域， 然后采用均匀量化划分来提高 ｖａ⁃ｆｉｌｅ 算法［７］ 的过 滤效率。 ｉＤｉｓｔａｎｃｅ 算法［８］ 对高维数据空间进行划 分，使用 Ｂ＋⁃ｔｒｅｅ 结果来组织参考点并搜索最近邻。 ＬＳＨ（ ｌｏｃａｌｉｔｙ ｓｅｎｓｉｔｉｖｅ ｈａｓｈｉｎｇ， ＬＳＨ） 算法［９－１０］ 通过 Ｈａｓｈ 函数将邻近高维点集映射到 Ｈａｓｈ 表的同一个 桶中，从而提高搜索最近邻效率。 基于聚类分析的 Ｂ＋⁃ｔｒｅｅ 算法［１１］ 采用类 Ｂ＋⁃ｔｒｅｅ 索引结构，通过更加 细致的划分数据来加快搜索速度。 ＭＲＳＶＱＨ ［１２］ 根 据选择子向量的 Ｌ２范数来量化和散列特征向量，仅 考虑具有与查询向量相同 Ｈａｓｈ 值的集合，从而提高 了搜索速度。 本文在以上研究的基础上，提出了一种基于参 考点距离的 ＳＩＦＴ 特征点匹配算法—ＤＲＰ 算法，并 通过实验与经典的 ＢＢＦ 算法相比，来验证基于 ＤＲＰ 算法的 ＳＩＦＴ 特征点匹配效果。 １ ＤＲＰ 算法 １．１ ＤＲＰ 算法原理 设 ｄ 维欧式空间 Ｒ ｄ 中 ２ 个点 Ｐ１ ＝ （ｘ１ ，ｘ２ ，…， ｘｄ ） ， Ｐ２ ＝ （ｙ１ ，ｙ２ ，…，ｙｄ ） ，两点对应的向量分别为 Ｖ１ ＝ ［ｘ１ ｘ２ … ｘｄ ］ ， Ｖ２ ＝ ［ｙ１ ｙ２ … ｙｄ ］ 。 则 Ｐ１ 、 Ｐ２ 两 点之间的欧式距离 Ｄ（Ｐ１ ，Ｐ２ ） 为 Ｄ（Ｐ１ ，Ｐ２ ） ＝ （ｘ１ － ｙ１ ） ２ ＋ （ｘ２ － ｙ２ ） ２ ＋ … ＋ （ｘｄ － ｙｄ ） ２ ＝ Ｖ１ ２ ＋ Ｖ２ ２ － ２ Ｖ１ Ｖ２ ＝ Ｖ１ ２ ＋ Ｖ２ ２ － ２ Ｖ１ Ｖ２ ｃｏｓ〈Ｖ１ ，Ｖ２ 〉 Ｖ１ ２ ＝ ｘ ２ １ ＋ ｘ ２ ２ ＋ … ＋ ｘ ２ ｄ Ｖ２ ２ ＝ ｙ ２ １ ＋ ｙ ２ ２ ＋ … ＋ ｙ ２ ｄ Ｖ１ Ｖ２ ＝ ｘ１ ｙ１ ＋ ｘ２ ｙ２ ＋ … ＋ ｘｄ ｙｄ （１） 式中： Ｖ１ 、 Ｖ２ 为向量 Ｖ１ 与 Ｖ２ 的模， 〈Ｖ１ ，Ｖ２ 〉 为向量 Ｖ１ 与 Ｖ２ 之间的夹角。 由式（１）可知，若 Ｖ１ 确定且 Ｖ１ 与 Ｖ２ 的夹角 一定时，当 Ｖ２ → Ｖ１ ｃｏｓ〈Ｖ１ ，Ｖ２ 〉 时，向量 Ｖ１ 与 Ｖ２ 对应的 Ｐ１ 与 Ｐ２ 两点之间的距离 Ｄ（Ｐ１ ，Ｐ２ ） 取最 小值。 设 ｄ 维欧式空间 Ｒ ｄ 中的一个点集合 Ｆｄ ＝ Ｐｉ Ｐｉ ∈ Ｒ ｄ { ， ｉ ＝ １，２，…，ｎ} ，对于 ∀ Ｐｑｕｅｒｙ ∈ Ｒ ｄ ， 需要在 Ｆｄ 中搜索 Ｐｑｕｅｒｙ 的最近邻。 设定一个参考点 Ｐｒ ，则对于每一个需要搜索的 Ｐｑｕｅｒｙ ， Ｐｑｕｅｒｙ 与参考点 Ｐｒ 构成向量 Ｐｒ Ｐｑｕｅｒｙ 是确定的（长度和方向），若 Ｆｄ 中 所有点与设定参考点 Ｐｒ 构成的向量 Ｐｒ Ｐｉ 与 Ｐｒ Ｐｑｕｅｒｙ 之 间 的 夹 角 都 为 θ 时， 则 使 向 量 Ｐｒ Ｐｉ → Ｐｒ Ｐｑｕｅｒｙ ｃｏｓθ 的点 Ｐｉ 就是 Ｐｑｕｅｒｙ 的最近邻。 若集合 Ｆｄ 中所有特征点与设定参考点 Ｐｒ 构成 的向量 Ｐｒ Ｐｉ 与 Ｐｒ Ｐｑｕｅｒｙ 之间的夹角不都为 θ 时，即 不相等时，上述结论并不一定成立。 如图 １ 的三维 空间所示。 图 １ 不同夹角时的最小距离 Ｆｉｇ． １ Ｔｈｅ ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ ｏｆ ｄｉｆｆｅｒｅｎｔ ａｎｇｌｅ 尽管 Ｐｒ Ｐ１ ＝ ｃｏｓ〈Ｐｒ Ｐ１ ，Ｐｒ Ｐｑｕｅｒｙ〉 Ｐｒ Ｐｑｕｅｒｙ ， 而 Ｐｒ Ｐ２ ＞ ｃｏｓ〈Ｐｒ Ｐ１ ，Ｐｒ Ｐｑｕｅｒｙ〉 Ｐｒ Ｐｑｕｅｒｙ 。 但是， Ｐ２ 相对于 Ｐ１ 更靠近 Ｐｑｕｅｒｙ 。 为了尽可能的得到 Ｐｑｕｅｒｙ 的最近邻，本文将搜索 范围扩大到集合 Ｆ ′ ｄ 中的所有点。 如图 ２ 所示。 Ｆ ′ ｄ ＝ Ｐｉ Ｒ － ｔｈ ＜ Ｐｒ Ｐｉ ＜ Ｒ ＋ ｔｈ ，Ｒ － ｔｈ ，Ｒ ＋ { ｔｈ ≥ ０} 图 ２ 在一定区域内搜索最近邻 Ｆｉｇ． ２ Ｓｅａｒｃｈ ｔｈｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｉｎ ａ ｓｐｅｃｉｆｉｅｄ ａｒｅａ 若将搜索范围扩大到以 Ｐｒ 为球心， Ｒ － ｔｈ 为半径 的球外， Ｒ ＋ ｔｈ 为半径的球内区域，则可得到 Ｐｑｕｅｒｙ 的真 正最近邻 Ｐ２ 。 随着 Ｒ － ｔｈ 的减小和 Ｒ ＋ ｔｈ 的增大，搜索到 Ｐｑｕｅｒｙ 的真正最近邻的概率也随之增大。 由此可知， 当 Ｆｄ 中所有点与设定参考点 Ｐｒ 构成的向量 Ｐｒ Ｐｉ 与 Ｐｒ Ｐｑｕｅｒｙ 之间的夹角不相等时，只需要选择一个合适 的搜索范围 Ｒ － ｔｈ 与 Ｒ ＋ ｔｈ ，仍然可以搜索到 Ｐｑｕｅｒｙ 的真正 最近邻。 第 ３ 期 唐坤，等：一种基于参考点距离的 ＳＩＦＴ 特征点匹配算法 ·３７７·
·378. 智能系统学报 第10卷 1.2DRP算法描述 5)使用二分查找法从Dmr中快速查找Dn的最 设d维欧式空间R中的2个点集合： 近邻D,,并得到D,对应的点P及其索引 Q=(PP E R,i=1,2,...,m) index(j）。 Qa={P|P。∈R,q=1,2,…,n 6)对Damr中索引范围在[index(U)-th, 对于HP,∈Q:,需要在集合Q中搜索其最近 index()+th]对应的所有点中，利用穷举搜索法查 邻。引入一个参考点（可随机选取）P,∈R,若 找Pn的最近邻。 P.aa（P.a∈Q.)是P,的最近邻，则Paa应该 在步骤6)中涉及到距离的计算，为进一步提高 出现在Pn的附近，即向量P,P。与向量P,Pm之间 算法的效率，均采用如下所述的距离累计算法。当 的夹角〈P,P,P,P〉应该趋向于零，此时 d维点P与P的前i(i∈[1，d])维的欧式距离 lP,Pa|=P,P,|×cos(P,P,P,P〉→ 已经超过上一次比较的最小距离时，无论后面d-i |P,P,|。因此，当|P,Pam=|P,P,|时，点 维的距离情况如何，将必定大于已经产生的最小距 P为查询点P,的最近邻。由此，对于HP,∈ 离。因此，也无需计算它们后面d-i维的距离，直 Q,不需要逐一计算P,与Q集合中所有点的距离， 接剔除跳出，进行下一特征点的比较。 而只要计算P,与参考点P,之间的距离D。,然后在 2SIFT特征点快速匹配算法 点集合Q:中搜索，就可能得到P,的真正最近邻，即 P,的真正最近邻落在集合Q,所表示的范围中。 SFT算法提取的图像特征点包括极大值与极 Q4= 小值2种类型，显而易见，只有极值类型相同的特征 点才可能正确匹配。因此，本文在特征点匹配之前 {P:dm-△di<|P,P:<dm+△di,P:∈Qa} 以图3所示的三维空间为例，如果搜索向量P。 进行特征点类型的判断，仅当2个特征点具有相同 的最近邻，只需要在P,为球心，半径为dm-△di的 类型时，才进行接下来的匹配运算，否则直接跳出， 转而比较下一个特征点。这在一定程度上可以提高 球以外和半径为d。+△d以内的空间搜索，就可以 匹配的效率。 得到P,的真正最近邻。 对于2幅含有同一场景的图像I(x,y)和I,(x, y),本文介绍的DRP算法按如下步骤进行。 1)使用ST算法分别提取图像I,(x,y)与图 d+△d 像I,(x,y)的特征点，生成的特征点构成的集合分 别为P,和p2。 2)对于HP:∈P,28,使用本文介绍的DRP算 P PP PI 法在集合P!28中搜索得到查询点P,的最近邻特征 PPP P 点Pat,对应的最近邻距离为daa,次近邻特征 点Pea2,对应的次近邻距离daa2,若比值 图3DRP算法搜索最近邻 daaa/dea2小于已知的阈值rh,则认为P:与 Fig.3 Search the nearest neighbor with DRP algorithm Pa两点之间正确匹配。 基于以上分析，在向量集合F中搜索向量V 3)采用随机抽样一致性原则(random sample 的最近邻的步骤如下： consensus,RANSAC)算法剔除误匹配的特征点。 1)在d维欧式空间R中任意选取一点P,作为 3实验结果与分析 参考点，设定一个阈值th(正整数)。 2)对于任一属于集合F,中的点P:(i=1,2, 本文实验采用的代码由GitHub上Rob Hess维 …,m),计算其与参考点P,之间的距离，保存于数 护的Opensift库13]改进而来。实验采用的测试图片 组Da中，并建立D。与P:的映射。 来自牛津大学VGG实验室的Affine Covariant Fea- 3)使用快速排序算法对D。中的距离按升序 tures(ACF)图片库14]。实验硬件环境为CPU Inter (或降序)进行排序，得到D。 (R)Coe(TM)2T6600,主频2.20GHz,内存2GB 4)从待匹配点集合F,中任取一待匹配点 DDR3RAM:软件环境为OS Windows732bit、IDE Mi- P,计算Pm与参考点卫，之间的距离D= crosoft Visual Studio2010、GTK+2.24图形工具包和 lP,Po。 Openev2.4机器视觉库
１．２ ＤＲＰ 算法描述 设 ｄ 维欧式空间 Ｒ ｄ 中的 ２ 个点集合： Ｑｄ ＝ Ｐｉ Ｐｉ ∈ Ｒ ｄ { ， ｉ ＝ １，２，…，ｍ} Ｑ ′ ｄ ＝ Ｐｑ Ｐｑ ∈ Ｒ ｄ { ， ｑ ＝ １，２，…，ｎ} 对于 ∀ Ｐｑ ∈ Ｑ ′ ｄ ，需要在集合 Ｑｄ 中搜索其最近 邻。 引入一个参考点（可随机选取） Ｐｒ ∈ Ｒ ｄ ，若 Ｐｎｅａｒｅｓｔ （ Ｐｎｅａｒｅｓｔ ∈ Ｑｄ ）是 Ｐｑ 的最近邻，则 Ｐｎｅａｒｅｓｔ 应该 出现在 Ｐｑ 的附近，即向量 Ｐｒ Ｐｑ 与向量 Ｐｒ Ｐｎｅａｒｅｓｔ 之间 的夹 角 〈 Ｐｒ Ｐｑ， Ｐｒ Ｐｎｅａｒｅｓｔ〉 应 该 趋 向 于 零， 此 时 Ｐｒ Ｐｎｅａｒｅｓｔ ＝ Ｐｒ Ｐｑ × ｃｏｓ〈 Ｐｒ Ｐｑ， Ｐｒ Ｐｎｅａｒｅｓｔ〉 → Ｐｒ Ｐｑ 。 因 此， 当 Ｐｒ Ｐｎｅａｒｅｓｔ ＝ Ｐｒ Ｐｑ 时， 点 Ｐｎｅａｒｅｓｔ 为查询点 Ｐｑ 的最近邻。 由此，对于 ∀ Ｐｑ ∈ Ｑ ′ ｄ ， 不需要逐一计算 Ｐｑ 与 Ｑｄ 集合中所有点的距离， 而只要计算 Ｐｑ 与参考点 Ｐｒ 之间的距离 Ｄｒｑ ，然后在 点集合 Ｑ ″ ｄ 中搜索，就可能得到 Ｐｑ 的真正最近邻，即 Ｐｑ 的真正最近邻落在集合 Ｑ ″ ｄ 所表示的范围中。 Ｑ ″ ｄ ＝ Ｐｉ ｄｒｑ － Δｄ － ｔｈ ＜ Ｐｒ Ｐｉ ＜ ｄｒｑ ＋ Δｄ ＋ ｔｈ ，Ｐｉ ∈ Ｑ ′ ｄ { } 以图 ３ 所示的三维空间为例，如果搜索向量 Ｐｑ 的最近邻，只需要在 Ｐｒ 为球心，半径为 ｄｒｑ － Δｄ － ｔｈ 的 球以外和半径为 ｄｒｑ ＋ Δｄ － ｔｈ 以内的空间搜索，就可以 得到 Ｐｑ 的真正最近邻。 图 ３ ＤＲＰ 算法搜索最近邻 Ｆｉｇ． ３ Ｓｅａｒｃｈ ｔｈｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｗｉｔｈ ＤＲＰ ａｌｇｏｒｉｔｈｍ 基于以上分析，在向量集合 Ｆｄ 中搜索向量 Ｖｑ 的最近邻的步骤如下： １）在 ｄ 维欧式空间 Ｒ ｄ 中任意选取一点 Ｐｒ 作为 参考点，设定一个阈值 ｔｈ（正整数）。 ２）对于任一属于集合 Ｆｄ 中的点 Ｐｉ （ｉ ＝ １，２， …，ｍ） ，计算其与参考点 Ｐｒ 之间的距离，保存于数 组 Ｄｒｉ 中，并建立 Ｄｒｉ 与 Ｐｉ 的映射。 ３）使用快速排序算法对 Ｄｒｉ 中的距离按升序 （或降序）进行排序，得到 Ｄ ｏｒｄｅｒ ｒｉ 。 ４） 从待匹配点集合 Ｆ ′ ｄ 中任取一待 匹 配 点 Ｐｑｕｅｒｙ ，计算 Ｐｑｕｅｒｙ 与参考点 Ｐｒ 之间的距离 Ｄｑｒ ＝ Ｐｒ Ｐｑｕｅｒｙ 。 ５）使用二分查找法从 Ｄ ｏｒｄｅｒ ｒｉ 中快速查找 Ｄｒｑ 的最 近邻 Ｄｒｊ ， 并 得 到 Ｄｒｊ 对 应 的 点 Ｐ ｎｅａｒｅｓｔ ｊ 及 其 索 引 ｉｎｄｅｘ（ｊ） 。 ６） 对 Ｄ ｏｒｄｅｒ ｒｉ 中 索 引 范 围 在 ［ｉｎｄｅｘ（ｊ） － ｔｈ， ｉｎｄｅｘ（ｊ） ＋ ｔｈ］ 对应的所有点中，利用穷举搜索法查 找 Ｐｑｕｅｒｙ 的最近邻。 在步骤 ６）中涉及到距离的计算，为进一步提高 算法的效率，均采用如下所述的距离累计算法。 当 ｄ 维点 Ｐｘ 与 Ｐｑｕｅｒｙ 的前 ｉ （ｉ ∈ ［１，ｄ］） 维的欧式距离 已经超过上一次比较的最小距离时，无论后面 ｄ － ｉ 维的距离情况如何，将必定大于已经产生的最小距 离。 因此，也无需计算它们后面 ｄ － ｉ 维的距离，直 接剔除跳出，进行下一特征点的比较。 ２ ＳＩＦＴ 特征点快速匹配算法 ＳＩＦＴ 算法提取的图像特征点包括极大值与极 小值 ２ 种类型，显而易见，只有极值类型相同的特征 点才可能正确匹配。 因此，本文在特征点匹配之前 进行特征点类型的判断，仅当 ２ 个特征点具有相同 类型时，才进行接下来的匹配运算，否则直接跳出， 转而比较下一个特征点。 这在一定程度上可以提高 匹配的效率。 对于 ２ 幅含有同一场景的图像 Ｉｑ（ｘ，ｙ） 和 Ｉｓ（ｘ， ｙ） ，本文介绍的 ＤＲＰ 算法按如下步骤进行。 １）使用 ＳＩＦＴ 算法分别提取图像 Ｉｑ（ｘ，ｙ） 与图 像 Ｉｓ（ｘ，ｙ） 的特征点，生成的特征点构成的集合分 别为 Ｐ １２８ ｑ 和 Ｐ １２８ ｓ 。 ２）对于 ∀ Ｐｉ ∈ Ｐ １２８ ｑ ，使用本文介绍的 ＤＲＰ 算 法在集合 Ｐ １２８ ｓ 中搜索得到查询点 Ｐｉ 的最近邻特征 点 Ｐｎｅａｒｅｓｔ ，对应的最近邻距离为 ｄｎｅａｒｅｓｔ ，次近邻特征 点 Ｐｎｅａｒｅｓｔ２ ， 对 应 的 次 近 邻 距 离 ｄｎｅａｒｅｓｔ２ ， 若 比 值 ｄｎｅａｒｅｓｔ ／ ｄｎｅａｒｅｓｔ２ 小 于 已 知 的 阈 值 ｒｔｈ ， 则 认 为 Ｐｉ 与 Ｐｎｅａｒｅｓｔ 两点之间正确匹配。 ３）采用随机抽样一致性原则（ ｒａｎｄｏｍ ｓａｍｐｌｅ ｃｏｎｓｅｎｓｕｓ， ＲＡＮＳＡＣ）算法剔除误匹配的特征点。 ３ 实验结果与分析 本文实验采用的代码由 ＧｉｔＨｕｂ 上 Ｒｏｂ Ｈｅｓｓ 维 护的 Ｏｐｅｎｓｉｆｔ 库［１ ３ ］改进而来。 实验采用的测试图片 来自牛津大学 ＶＧＧ 实验室的 Ａｆｆｉｎｅ Ｃｏｖａｒｉａｎｔ Ｆｅａ⁃ ｔｕｒｅｓ（ＡＣＦ）图片库［１ ４ ］ 。 实验硬件环境为 ＣＰＵ Ｉｎｔｅｒ （Ｒ） Ｃｏｒｅ（ＴＭ） ２ Ｔ６６００，主频 ２．２０ ＧＨｚ，内存 ２ ＧＢ ＤＤＲ３ ＲＡＭ；软件环境为 ＯＳ Ｗｉｎｄｏｗｓ７ ３２ ｂｉｔ、ＩＤＥ Ｍｉ⁃ ｃｒｏｓｏｆｔ Ｖｉｓｕａｌ Ｓｔｕｄｉｏ ２０１０、 ＧＴＫ＋２．２４ 图形工具包和 Ｏｐｅｎｃｖ２．４ 机器视觉库。 ·３７８· 智 能 系 统 学 报 第 １０ 卷
第3期 唐坤，等：一种基于参考点距离的SFT特征点匹配算法 ·379· 1.00 Trees、Graf、Bark、Boat、Leuven6组图片每组中的 0.98 0.96 Imgl/mg2、mgl/mg3、mgl/mg43对图片各进行 20.94 10次SIFT特征点匹配实验。统计得到特征点的正 证0.92 确匹配率、正确匹配特征点总数以及平均每幅图像 匹配时间与搜索阈值h的关系如图4所示。 由图4(a)可知，在特征点正确匹配率方面 0.84 一O一BBF算法 DRP算法与BBF算法具有相同的趋势。当搜索阈 0.82 合一DRP算法 0.80 值h小于200时，随着h的增大而增大：当搜索阈 0100150200250300350400450500 值th大于200时，特征点正确匹配率很难得到进一 搜索國值th 步的改善，趋于稳定。总体来看，这2个算法在特征 (a)特征点正确匹配率与搜索阈值th的关系 点匹配率的表现上相差无几。由图4(b)可知，在正 10*10 确匹配特征点总数方面，DRP的算法略逊于BBF算 法，但是，随着搜索阈值山的增大，两者的差距逐渐 6 > 缩小。由图4(c)可知，在匹配时间上，DRP算法与 6 BBF算法都随着搜索阈值h的增大而呈线性增长 5 趋势，但是，BBF的增长速率显著大于DRP算法，由 4 3 此可知，在匹配时间上，DRP算法较BBF算法具有 -O-BBF算法 明显的优势。综上所述，相对于经典的BBF算法， A一DRP算法 本文介绍的DRP算法能获得满意匹配效果的同时， '50100150200250300350400450500 有效降低匹配时间。 搜索阈值th 4结束语 (b)正确匹配特征点总数与搜索阈值山的关系 1.0 本文介绍了一种基于参考点距离的SFT特征 0.9 O一BBF算法 点匹配算法，并使用牛津大学VGG实验室的ACF 0.8 A一DRP算法 0.7 图片库进行SFT特征点匹配实验。实验结果表明， 与经典BBF最近邻搜索算法相比，使用本文介绍的 0.5 DRP算法进行SFT特征点匹配，不仅可以获得满 0.3 意的匹配效果，并且可以有效地降低匹配时间消耗， 0.2 提高匹配速度。尤其在搜索阈值h较大的情况下， 0.1 DRP算法在时间成本上较经典的BBF算法具有明 0 0100150200250300350400450500 显的优势。另外，DRP算法还有一些可以改进的地 搜索圆值th 方，如对提取的ST特征点分布情况进行分析、参 (c)平均匹配时间与搜索阈值山的关系 考点选择方法的分析等都可能进一步提高特征点的 图4DRP算法与BBF算法实验对比结果 匹配效率。对于不同的特征点分布情况，如何选取 Fig.4 The comparison results of DRP algorithm and 一个合适的参考点，从而尽可能改善匹配效果是下 BBF algorithm 一步的工作重心。 为了验证DRP算法的有效性，本文进行了在不 参考文献： 同搜索阈值h下，DRP算法与经典BBF算法的对 比实验。简便起见，所有实验中的参考点均采用坐 [1]LOWE D G.Distinctive image features from scale-invariant 标原点，即P.=(),=0j=1,2,…,128。其中， keypoints[J].International Journal of Computer Vision, 2004,60(2):91-110. 交叉验证两算法的最近邻与次近邻距离阈值比 [2]吴伟交，王敏，黄心汉，等.基于向量夹角的SFT特征 保持为O.56。BBF算法中除搜索阈值KDTREE_ 点匹配算法[J].模式识别与人工智能，2013,26(1)： BBF_MAX_NN_CHKS变化外，其他所有参数保持默 123-127. 认。实验中搜索阈值h以50为步长在[50,500] WU Weijiao,WANG Min,HUANG Xinhan,et al.SIFT 范围内变化，在不同搜索阈值h条件下，对Biks、 feature matching algorithm based on vector angle.Pattern
（ａ） 特征点正确匹配率与搜索阈值 ｔｈ 的关系 （ｂ）正确匹配特征点总数与搜索阈值 ｔｈ 的关系 （ｃ）平均匹配时间与搜索阈值 ｔｈ 的关系 图 ４ ＤＲＰ 算法与 ＢＢＦ 算法实验对比结果 Ｆｉｇ． ４ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｒｅｓｕｌｔｓ ｏｆ ＤＲＰ ａｌｇｏｒｉｔｈｍ ａｎｄ ＢＢＦ ａｌｇｏｒｉｔｈｍ 为了验证 ＤＲＰ 算法的有效性，本文进行了在不 同搜索阈值 ｔｈ 下，ＤＲＰ 算法与经典 ＢＢＦ 算法的对 比实验。 简便起见，所有实验中的参考点均采用坐 标原点，即 Ｐｒ ＝ ｘ ｊ ｒ ( ) ， ｘ ｊ ｒ ＝ ０，ｊ ＝ １，２，…，１２８。 其中， 交叉验证两算法的最近邻与次近邻距离阈值比 ｒｔｈ 保持为 ０． ５６。 ＢＢＦ 算法中除搜索阈值 ＫＤＴＲＥＥ ＿ ＢＢＦ＿ＭＡＸ＿ＮＮ＿ＣＨＫＳ 变化外，其他所有参数保持默 认。 实验中搜索阈值 ｔｈ 以 ５０ 为步长在［５０， ５００］ 范围内变化，在不同搜索阈值 ｔｈ 条件下，对 Ｂｉｋｅｓ、 Ｔｒｅｅｓ、Ｇｒａｆ、 Ｂａｒｋ、 Ｂｏａｔ、 Ｌｅｕｖｅｎ ６ 组图片每组中的 Ｉｍｇ１ ／ Ｉｍｇ２、Ｉｍｇ１ ／ Ｉｍｇ３、Ｉｍｇ１ ／ Ｉｍｇ４ ３ 对图片各进行 １０ 次 ＳＩＦＴ 特征点匹配实验。 统计得到特征点的正 确匹配率、正确匹配特征点总数以及平均每幅图像 匹配时间与搜索阈值 ｔｈ 的关系如图 ４ 所示。 由图 ４ （ ａ） 可知，在特征点正确匹配率方面， ＤＲＰ 算法与 ＢＢＦ 算法具有相同的趋势。 当搜索阈 值 ｔｈ 小于 ２００ 时，随着 ｔｈ 的增大而增大；当搜索阈 值 ｔｈ 大于 ２００ 时，特征点正确匹配率很难得到进一 步的改善，趋于稳定。 总体来看，这 ２ 个算法在特征 点匹配率的表现上相差无几。 由图 ４（ｂ）可知，在正 确匹配特征点总数方面，ＤＲＰ 的算法略逊于 ＢＢＦ 算 法，但是，随着搜索阈值 ｔｈ 的增大，两者的差距逐渐 缩小。 由图 ４（ｃ）可知，在匹配时间上，ＤＲＰ 算法与 ＢＢＦ 算法都随着搜索阈值 ｔｈ 的增大而呈线性增长 趋势，但是，ＢＢＦ 的增长速率显著大于 ＤＲＰ 算法，由 此可知，在匹配时间上，ＤＲＰ 算法较 ＢＢＦ 算法具有 明显的优势。 综上所述，相对于经典的 ＢＢＦ 算法， 本文介绍的 ＤＲＰ 算法能获得满意匹配效果的同时， 有效降低匹配时间。 ４ 结束语 本文介绍了一种基于参考点距离的 ＳＩＦＴ 特征 点匹配算法，并使用牛津大学 ＶＧＧ 实验室的 ＡＣＦ 图片库进行 ＳＩＦＴ 特征点匹配实验。 实验结果表明， 与经典 ＢＢＦ 最近邻搜索算法相比，使用本文介绍的 ＤＲＰ 算法进行 ＳＩＦＴ 特征点匹配，不仅可以获得满 意的匹配效果，并且可以有效地降低匹配时间消耗， 提高匹配速度。 尤其在搜索阈值 ｔｈ 较大的情况下， ＤＲＰ 算法在时间成本上较经典的 ＢＢＦ 算法具有明 显的优势。 另外，ＤＲＰ 算法还有一些可以改进的地 方，如对提取的 ＳＩＦＴ 特征点分布情况进行分析、参 考点选择方法的分析等都可能进一步提高特征点的 匹配效率。 对于不同的特征点分布情况，如何选取 一个合适的参考点，从而尽可能改善匹配效果是下 一步的工作重心。 参考文献： ［１］ＬＯＷＥ Ｄ Ｇ． Ｄｉｓｔｉｎｃｔｉｖｅ ｉｍａｇｅ ｆｅａｔｕｒｅｓ ｆｒｏｍ ｓｃａｌｅ⁃ｉｎｖａｒｉａｎｔ ｋｅｙｐｏｉｎｔｓ ［ Ｊ ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， ２００４， ６０（２）： ９１⁃１１０． ［２］吴伟交， 王敏， 黄心汉， 等． 基于向量夹角的 ＳＩＦＴ 特征 点匹配算法［ Ｊ］． 模式识别与人工智能， ２０１３， ２６（ １）： １２３⁃１２７． ＷＵ Ｗｅｉｊｉａｏ， ＷＡＮＧ Ｍｉｎ， ＨＵＡＮＧ Ｘｉｎｈａｎ， ｅｔ ａｌ． ＳＩＦＴ ｆｅａｔｕｒｅ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｖｅｃｔｏｒ ａｎｇｌｅ． Ｐａｔｔｅｒｎ 第 ３ 期 唐坤，等：一种基于参考点距离的 ＳＩＦＴ 特征点匹配算法 ·３７９·
·380· 智能系统学报 第10卷 Recognition and Artificial Intelligence,2013,26(1):123- [11]张军旗，周向东，王梅，等.基于聚类分解的高维度量 127. 空间索引B+-tree[J].软件学报，2008,19(6)：1401- [3]KRYSTIAN M,CORDELIA S.A performance evaluation of 1412. local descriptors[].IEEE Transactions on Pattern Analysis ZHANG Junqi,ZHOU Xiangdong,WANG Mei,et al. and Machine Intelligence,2005,27(10):1615-1630. Cluster splitting based high dimensional metric space index [4]GIONIS A,INDYK P,MOTWANI R.Similarity search in B'-tree[J].Journal of Software,2008,19(6):1401- high dimensions via hashing[C]//Proceedings of the 25th 1412. International Conference on Very Large Data Bases.San [12]杨恒，王庆，何周灿.面向高维图像特征匹配的多次随 Francisco.USA,1999:518-529. 机子向量量化哈希算法[J].计算机辅助设计与图形学 [5]BEIS J S,LOWE D G.Shape indexing using approximate 学报，2010,22(3)：494-502. nearest-neighbor search in high-dimensional spaces[C]// YANG Heng,WANG Qing,HE Zhoucan.Mutiple ran- Proceedings of the IEEE Conference on Computer Vision domized sub-vectors quantization hashing for high-dimen- and Pattern Recognition.San Juan,Puerto Rico,1997: sional image feature matching[J].Journal of Computer-Ai- 1000-1006. ded Deasign Computer Graphics,2010,22(3):494- [6]FERHATOSMANOGLU H,TUNCEL E,AGRAWAL D,et 502. al.Vector approximation based indexing for non-uniform [13]LOWE D.OpenSIFT-An open-source SIFT library [EB/ high dimensional data sets[C]//Proceedings of the Interna- OL].[2013-11-15].http://robwhess.github.io/opensift/. tional Conference on Information and Knowledge Manage- [14]The Visual Geometry Group.Affine covariant features[EB/ ment.McLean,USA,2000:202-209. 0L].(2007-07-15)[2013-11-15].http://www.obots.ox. [7]WEBER R,SCHEK H J,BLOTT S.A quantitative analysis ac.uk/~vgg/research/affine/index.html. and performance study for similarity-search methods in high 作者简介： dimensional spaces [C]//Proceedings of the International 唐坤，男，1988年生，博士研究 Conference on Very Large Databases.New York,1998: 生，主要研究方向为数字图像处理、 194-205. 智能交通。 [8]JAGADISH H V,OOI B C,TAN K L,et al.IDistance:an adaptive B'-tree based indexing method for nearest neighbor search[J].ACM Transactions on Database Systems,2005, 30(2):364-398. [9]AUCLAIR A,COHEN L D,VINCENT N.How to use SIFT 韩斌.男，1968年生，教授，博士，主 vectors to analyze an image with database templates[C]// 要研究方向为数字图像处理、智能检 Proceedings of the 5h International Workshop on Adaptive 测、并行计算。 Multimedia Retrieval.Paris,France,2008:224-236. [10 SLANEY M,CASEY M.Locality-sensitive hashing for finding nearest neighbors [J].IEEE Signal Processing Magazine,2008,25(2):128-131
Ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１３， ２６（１）： １２３⁃ １２７． ［３］ＫＲＹＳＴＩＡＮ Ｍ， ＣＯＲＤＥＬＩＡ Ｓ． Ａ ｐｅｒｆｏｒｍａｎｃｅ ｅｖａｌｕａｔｉｏｎ ｏｆ ｌｏｃａｌ ｄｅｓｃｒｉｐｔｏｒｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００５， ２７（１０）： １６１５⁃１６３０． ［４］ＧＩＯＮＩＳ Ａ， ＩＮＤＹＫ Ｐ， ＭＯＴＷＡＮＩ Ｒ． Ｓｉｍｉｌａｒｉｔｙ ｓｅａｒｃｈ ｉｎ ｈｉｇｈ ｄｉｍｅｎｓｉｏｎｓ ｖｉａ ｈａｓｈｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａ Ｂａｓｅｓ． Ｓａｎ Ｆｒａｎｃｉｓｃｏ， ＵＳＡ， １９９９： ５１８⁃５２９． ［５］ ＢＥＩＳ Ｊ Ｓ， ＬＯＷＥ Ｄ Ｇ． Ｓｈａｐｅ ｉｎｄｅｘｉｎｇ ｕｓｉｎｇ ａｐｐｒｏｘｉｍａｔｅ ｎｅａｒｅｓｔ⁃ｎｅｉｇｈｂｏｒ ｓｅａｒｃｈ ｉｎ ｈｉｇｈ⁃ｄｉｍｅｎｓｉｏｎａｌ ｓｐａｃｅｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｓａｎ Ｊｕａｎ， Ｐｕｅｒｔｏ Ｒｉｃｏ， １９９７： １０００⁃１００６． ［６］ＦＥＲＨＡＴＯＳＭＡＮＯＧＬＵ Ｈ， ＴＵＮＣＥＬ Ｅ， ＡＧＲＡＷＡＬ Ｄ， ｅｔ ａｌ． Ｖｅｃｔｏｒ ａｐｐｒｏｘｉｍａｔｉｏｎ ｂａｓｅｄ ｉｎｄｅｘｉｎｇ ｆｏｒ ｎｏｎ⁃ｕｎｉｆｏｒｍ ｈｉｇｈ ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ ｓｅｔｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｍａｎａｇｅ⁃ ｍｅｎｔ． ＭｃＬｅａｎ， ＵＳＡ， ２０００： ２０２⁃２０９． ［７］ＷＥＢＥＲ Ｒ， ＳＣＨＥＫ Ｈ Ｊ， ＢＬＯＴＴ Ｓ． Ａ ｑｕａｎｔｉｔａｔｉｖｅ ａｎａｌｙｓｉｓ ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ ｓｔｕｄｙ ｆｏｒ ｓｉｍｉｌａｒｉｔｙ⁃ｓｅａｒｃｈ ｍｅｔｈｏｄｓ ｉｎ ｈｉｇｈ ｄｉｍｅｎｓｉｏｎａｌ ｓｐａｃｅｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａｂａｓｅｓ． Ｎｅｗ Ｙｏｒｋ， １９９８： １９４⁃２０５． ［８］ＪＡＧＡＤＩＳＨ Ｈ Ｖ， ＯＯＩ Ｂ Ｃ， ＴＡＮ Ｋ Ｌ， ｅｔ ａｌ． ＩＤｉｓｔａｎｃｅ： ａｎ ａｄａｐｔｉｖｅ Ｂ ＋ ⁃ｔｒｅｅ ｂａｓｅｄ ｉｎｄｅｘｉｎｇ ｍｅｔｈｏｄ ｆｏｒ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｓｅａｒｃｈ［Ｊ］． ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ， ２００５， ３０（２）： ３６４⁃３９８． ［９］ＡＵＣＬＡＩＲ Ａ， ＣＯＨＥＮ Ｌ Ｄ， ＶＩＮＣＥＮＴ Ｎ． Ｈｏｗ ｔｏ ｕｓｅ ＳＩＦＴ ｖｅｃｔｏｒｓ ｔｏ ａｎａｌｙｚｅ ａｎ ｉｍａｇｅ ｗｉｔｈ ｄａｔａｂａｓｅ ｔｅｍｐｌａｔｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ａｄａｐｔｉｖｅ Ｍｕｌｔｉｍｅｄｉａ Ｒｅｔｒｉｅｖａｌ． Ｐａｒｉｓ， Ｆｒａｎｃｅ， ２００８： ２２４⁃２３６． ［ １０］ ＳＬＡＮＥＹ Ｍ， ＣＡＳＥＹ Ｍ． Ｌｏｃａｌｉｔｙ⁃ｓｅｎｓｉｔｉｖｅ ｈａｓｈｉｎｇ ｆｏｒ ｆｉｎｄｉｎｇ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒｓ ［ Ｊ ］． ＩＥＥＥ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｍａｇａｚｉｎｅ， ２００８， ２５（２）： １２８⁃１３１． ［１１］张军旗， 周向东， 王梅， 等． 基于聚类分解的高维度量 空间索引 Ｂ＋⁃ｔｒｅｅ［ Ｊ］． 软件学报， ２００８， １９（６）： １４０１⁃ １４１２． ＺＨＡＮＧ Ｊｕｎｑｉ， ＺＨＯＵ Ｘｉａｎｇｄｏｎｇ， ＷＡＮＧ Ｍｅｉ， ｅｔ ａｌ． Ｃｌｕｓｔｅｒ ｓｐｌｉｔｔｉｎｇ ｂａｓｅｄ ｈｉｇｈ ｄｉｍｅｎｓｉｏｎａｌ ｍｅｔｒｉｃ ｓｐａｃｅ ｉｎｄｅｘ Ｂ ＋ ⁃ｔｒｅｅ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ， ２００８， １９ （ ６）： １４０１⁃ １４１２． ［１２］杨恒， 王庆， 何周灿． 面向高维图像特征匹配的多次随 机子向量量化哈希算法［Ｊ］． 计算机辅助设计与图形学 学报， ２０１０， ２２（３）： ４９４⁃５０２． ＹＡＮＧ Ｈｅｎｇ， ＷＡＮＧ Ｑｉｎｇ， ＨＥ Ｚｈｏｕｃａｎ． Ｍｕｔｉｐｌｅ ｒａｎ⁃ ｄｏｍｉｚｅｄ ｓｕｂ⁃ｖｅｃｔｏｒｓ ｑｕａｎｔｉｚａｔｉｏｎ ｈａｓｈｉｎｇ ｆｏｒ ｈｉｇｈ⁃ｄｉｍｅｎ⁃ ｓｉｏｎａｌ ｉｍａｇｅ ｆｅａｔｕｒｅ ｍａｔｃｈｉｎｇ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ⁃Ａｉ⁃ ｄｅｄ Ｄｅａｓｉｇｎ ＆ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ， ２０１０， ２２ （ ３）： ４９４⁃ ５０２． ［１３］ ＬＯＷＥ Ｄ． ＯｐｅｎＳＩＦＴ—Ａｎ ｏｐｅｎ⁃ｓｏｕｒｃｅ ＳＩＦＴ ｌｉｂｒａｒｙ［ＥＢ／ ＯＬ］． ［２０１３⁃１１⁃１５］． ｈｔｔｐ： ／ ／ ｒｏｂｗｈｅｓｓ．ｇｉｔｈｕｂ．ｉｏ ／ ｏｐｅｎｓｉｆｔ ／ ． ［１４］Ｔｈｅ Ｖｉｓｕａｌ Ｇｅｏｍｅｔｒｙ Ｇｒｏｕｐ． Ａｆｆｉｎｅ ｃｏｖａｒｉａｎｔ ｆｅａｔｕｒｅｓ［ＥＢ／ ＯＬ］． （２００７⁃０７⁃１５）［２０１３⁃１１⁃１５］． ｈｔｔｐ： ／ ／ ｗｗｗ．ｒｏｂｏｔｓ．ｏｘ． ａｃ．ｕｋ ／ ～ ｖｇｇ ／ ｒｅｓｅａｒｃｈ ／ ａｆｆｉｎｅ ／ ｉｎｄｅｘ．ｈｔｍｌ． 作者简介： 唐坤， 男， １９８８ 年 生， 博 士 研 究 生，主要研究方向为数字图像处理、 智能交通。 韩斌，男，１９６８ 年生，教授，博士，主 要研究方向为数字图像处理、智能检 测、并行计算。 ·３８０· 智 能 系 统 学 报 第 １０ 卷