網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150402.1518.001.html

一種基于參考點距離的SIFT特征點匹配算法

唐坤1，韓斌2

(1.東南大學(xué) 交通學(xué)院，江蘇 南京 210096；2.江蘇科技大學(xué) 計算機科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212000)

摘要：針對SIFT特征點匹配時間消耗大的問題，提出了一種基于參考點距離的SIFT特征點匹配算法—DRP算法。該算法首先計算一次所有待匹配特征點到參考點之間的距離，對之進行快速排序并保存。然后計算待查詢特征點到參考點的距離，并在已排序的距離中使用二分法搜索返回此距離的最近鄰。最后以此最近鄰為中心，在有限范圍內(nèi)搜索待查詢特征點的近似最近鄰。VGG實驗室ACF圖片庫的測試結(jié)果表明，相比于經(jīng)典的SIFT算法，DRP算法可以在不損失匹配效果的前提下，有效降低SIFT特征點匹配的時間消耗。

關(guān)鍵詞：SIFT；DRP算法；特征點匹配；最近鄰；參考點

DOI:10.3969/j.issn.1673-4785.201311020

中圖分類號：TP319 文獻標(biāo)志碼：A

收稿日期：2013-11-28. 網(wǎng)絡(luò)出版日期：2014-04-02.

基金項目：國家自然科學(xué)基金資助項目(61374195)；中央高校基本科研業(yè)務(wù)費專項資金資助項目；江蘇省普通高校研究生科研創(chuàng)新計劃資助項目(KYLX_0180).

作者簡介：

中文引用格式：唐坤，韓斌. 一種基于參考點距離的SIFT特征點匹配算法[J]. 智能系統(tǒng)學(xué)報, 2015, 10(3): 376-380.

英文引用格式：TANG Kun, 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 Kun1, 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 neighbor 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

通信作者：唐坤. E-mail: tkpaperzc@sina.cn.

Lowe提出的尺度不變特征變換(scale invariant feature transform, SIFT)[1]是一種魯棒性強的圖像局部特征提取算法，具有對旋轉(zhuǎn)、光照、尺度變化等保持不變性[2]，廣泛應(yīng)用于三維重建、目標(biāo)識別、圖像融合等領(lǐng)域[3]。SIFT算法由特征點檢測及描述與特征點匹配兩部分構(gòu)成，其中，SIFT特征點匹配實質(zhì)上可以轉(zhuǎn)化為在高維空間中搜索特征點最近鄰的問題，并且在很多情況下，只需要得到查詢特征點的近似最近鄰就足夠了[4]。據(jù)此近年來提出了一些相關(guān)算法，其中，Lowe提出的最優(yōu)節(jié)點優(yōu)先算法(best bin first, BBF)[5]在K-D樹索引的基礎(chǔ)上，使用優(yōu)先隊列和限制回溯查詢次數(shù)來提高搜索最近鄰的效率。va+-file算法[6]將數(shù)據(jù)集轉(zhuǎn)換到KLT域，然后采用均勻量化劃分來提高va-file算法[7]的過濾效率。iDistance算法[8]對高維數(shù)據(jù)空間進行劃分，使用B+-tree結(jié)果來組織參考點并搜索最近鄰。LSH(locality sensitive hashing, LSH)算法[9-10]通過Hash函數(shù)將鄰近高維點集映射到Hash表的同一個桶中，從而提高搜索最近鄰效率?；诰垲惙治龅腂+-tree算法[11]采用類B+-tree索引結(jié)構(gòu)，通過更加細致的劃分數(shù)據(jù)來加快搜索速度。MRSVQH[12]根據(jù)選擇子向量的L2范數(shù)來量化和散列特征向量，僅考慮具有與查詢向量相同Hash值的集合，從而提高了搜索速度。

本文在以上研究的基礎(chǔ)上，提出了一種基于參考點距離的SIFT特征點匹配算法—DRP算法，并通過實驗與經(jīng)典的BBF算法相比，來驗證基于DRP算法的SIFT特征點匹配效果。

1DRP算法

1.1DRP算法原理

設(shè)d維歐式空間Rd中2個點P1=(x1,x2,…,xd)，P2=(y1,y2,…,yd)，兩點對應(yīng)的向量分別為V1=[x1x2…xd]，V2=[y1y2…yd]。則P1、P2兩點之間的歐式距離D(P1,P2)為

(1)

若集合Fd中所有特征點與設(shè)定參考點Pr構(gòu)成的向量PrPi與PrPquery之間的夾角不都為θ時，即不相等時，上述結(jié)論并不一定成立。如圖1的三維空間所示。

圖1　不同夾角時的最小距離 Fig. 1　The minimum distance of different angle

圖2　在一定區(qū)域內(nèi)搜索最近鄰 Fig. 2　Search the nearest neighbor in a specified area

1.2DRP算法描述

設(shè)d維歐式空間Rd中的2個點集合：

圖3　DRP算法搜索最近鄰 Fig. 3　Search the nearest neighbor with DRP algorithm

基于以上分析，在向量集合Fd中搜索向量Vq的最近鄰的步驟如下：

1)在d維歐式空間Rd中任意選取一點Pr作為參考點，設(shè)定一個閾值th(正整數(shù))。

2)對于任一屬于集合Fd中的點Pi(i=1,2,…,m)，計算其與參考點Pr之間的距離，保存于數(shù)組Dri中，并建立Dri與Pi的映射。

在步驟6)中涉及到距離的計算，為進一步提高算法的效率，均采用如下所述的距離累計算法。當(dāng)d維點Px與Pquery的前i(i∈[1,d])維的歐式距離已經(jīng)超過上一次比較的最小距離時，無論后面d-i維的距離情況如何，將必定大于已經(jīng)產(chǎn)生的最小距離。因此，也無需計算它們后面d-i維的距離，直接剔除跳出，進行下一特征點的比較。

2SIFT特征點快速匹配算法

SIFT算法提取的圖像特征點包括極大值與極小值2種類型，顯而易見，只有極值類型相同的特征點才可能正確匹配。因此，本文在特征點匹配之前進行特征點類型的判斷，僅當(dāng)2個特征點具有相同類型時，才進行接下來的匹配運算，否則直接跳出，轉(zhuǎn)而比較下一個特征點。這在一定程度上可以提高匹配的效率。

對于2幅含有同一場景的圖像Iq(x,y)和Is(x,y)，本文介紹的DRP算法按如下步驟進行。

3)采用隨機抽樣一致性原則(randomsampleconsensus,RANSAC)算法剔除誤匹配的特征點。

3實驗結(jié)果與分析

本文實驗采用的代碼由GitHub上Rob Hess維護的Opensift庫[13]改進而來。實驗采用的測試圖片來自牛津大學(xué)VGG實驗室的Affine Covariant Features(ACF)圖片庫[14]。實驗硬件環(huán)境為CPU Inter(R) Core(TM)2 T6600，主頻2.20 GHz，內(nèi)存2 GB DDR3 RAM；軟件環(huán)境為OS Windows7 32 bit、IDE Microsoft Visual Studio 2010、 GTK+2.24圖形工具包和Opencv2.4機器視覺庫。

(a) 特征點正確匹配率與搜索閾值th的關(guān)系

(b)正確匹配特征點總數(shù)與搜索閾值th的關(guān)系

(c)平均匹配時間與搜索閾值th的關(guān)系

由圖4(a)可知，在特征點正確匹配率方面，DRP算法與BBF算法具有相同的趨勢。當(dāng)搜索閾值th小于200時，隨著th的增大而增大；當(dāng)搜索閾值th大于200時，特征點正確匹配率很難得到進一步的改善，趨于穩(wěn)定。總體來看，這2個算法在特征點匹配率的表現(xiàn)上相差無幾。由圖4(b)可知，在正確匹配特征點總數(shù)方面，DRP的算法略遜于BBF算法，但是，隨著搜索閾值th的增大，兩者的差距逐漸縮小。由圖4(c)可知，在匹配時間上，DRP算法與BBF算法都隨著搜索閾值th的增大而呈線性增長趨勢，但是，BBF的增長速率顯著大于DRP算法，由此可知，在匹配時間上，DRP算法較BBF算法具有明顯的優(yōu)勢。綜上所述，相對于經(jīng)典的BBF算法，本文介紹的DRP算法能獲得滿意匹配效果的同時，有效降低匹配時間。

4結(jié)束語

本文介紹了一種基于參考點距離的SIFT特征點匹配算法，并使用牛津大學(xué)VGG實驗室的ACF圖片庫進行SIFT特征點匹配實驗。實驗結(jié)果表明，與經(jīng)典BBF最近鄰搜索算法相比，使用本文介紹的DRP算法進行SIFT特征點匹配，不僅可以獲得滿意的匹配效果，并且可以有效地降低匹配時間消耗，提高匹配速度。尤其在搜索閾值th較大的情況下，DRP算法在時間成本上較經(jīng)典的BBF算法具有明顯的優(yōu)勢。另外，DRP算法還有一些可以改進的地方，如對提取的SIFT特征點分布情況進行分析、參考點選擇方法的分析等都可能進一步提高特征點的匹配效率。對于不同的特征點分布情況，如何選取一個合適的參考點，從而盡可能改善匹配效果是下一步的工作重心。

參考文獻:

[1]LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[2]吳偉交, 王敏, 黃心漢, 等. 基于向量夾角的SIFT特征點匹配算法[J]. 模式識別與人工智能, 2013, 26(1): 123-127.

WU Weijiao, WANG Min, HUANG Xinhan, et al. SIFT feature matching algorithm based on vector angle. Pattern Recognition and Artificial Intelligence, 2013, 26(1): 123-127.

[3]KRYSTIAN M, CORDELIA S. A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615-1630.

[4]GIONIS A, INDYK P, MOTWANI R. Similarity search in high dimensions via hashing[C]//Proceedings of the 25th International Conference on Very Large Data Bases. San Francisco, USA, 1999: 518-529.

[5]BEIS J S, LOWE D G. Shape indexing using approximate nearest-neighbor search in high-dimensional spaces[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. San Juan, Puerto Rico, 1997: 1000-1006.

[6]FERHATOSMANOGLU H, TUNCEL E, AGRAWAL D, et al. Vector approximation based indexing for non-uniform high dimensional data sets[C]//Proceedings of the International Conference on Information and Knowledge Management. McLean, USA, 2000: 202-209.

[7]WEBER R, SCHEK H J, BLOTT S. A quantitative analysis and performance study for similarity-search methods in high dimensional spaces[C]//Proceedings of the International 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 vectors to analyze an image with database templates[C]//Proceedings of the 5thInternational 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.

[11]張軍旗, 周向東, 王梅, 等. 基于聚類分解的高維度量空間索引B+-tree[J]. 軟件學(xué)報, 2008, 19(6): 1401-1412.

ZHANG Junqi, ZHOU Xiangdong, WANG Mei, et al. Cluster splitting based high dimensional metric space index B+-tree[J]. Journal of Software, 2008, 19(6): 1401-1412.

[12]楊恒, 王慶, 何周燦. 面向高維圖像特征匹配的多次隨機子向量量化哈希算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2010, 22(3): 494-502.

YANG Heng, WANG Qing, HE Zhoucan. Mutiple randomized sub-vectors quantization hashing for high-dimensional image feature matching[J]. Journal of Computer-Aided Deasign & Computer Graphics, 2010, 22(3): 494-502.

[13]LOWE D. OpenSIFT—An open-source SIFT library[EB/OL]. [2013-11-15]. http://robwhess.github.io/opensift/.

[14]The Visual Geometry Group. Affine covariant features[EB/OL]. (2007-07-15)[2013-11-15]. http://www.robots.ox.ac.uk/~vgg/research/affine/index.html.

唐坤，男，1988年生，博士研究生，主要研究方向為數(shù)字圖像處理、智能交通。

韓斌，男，1968年生，教授，博士，主要研究方向為數(shù)字圖像處理、智能檢測、并行計算。