文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > A fast sift feature matching algorithm for image registration
侵权投诉

A fast sift feature matching algorithm for image registration

2011 International Conference on Multimedia and Signal Processing

A Fast SIFT Feature Matching Algorithm for Image Registration

Kun Li, Shangbo Zhou

College of Computer Science, Chongqing University, Chongqing, China

lk@cqu.edu.cn, shbzhou@cqu.edu.cn

Abstract—In this paper, a novel fast SIFT (Scale Invariant

Feature Transform) feature matching algorithm for image registration is presented. Firstly, for fast SIFT feature matching, we propose a method to optimize the priority k-d tree search algorithm by choosing a proper number of leaf nodes examined (denoted as Emax) in a single k-d tree. In order to get the relationships among the number of SIFT features, Emax and the precisions achieved by the priority k-d tree search algorithm in a single k-d tree, the properties of a single k-d tree and that of the priority k-d tree search algorithm are combined. Referring to these relationships, a

can be selected to achieve an proper value of Emax

approximate precision in fast time. And then, in image registration, in order to improve matching precision, we have designed the bidirectional priority k-d tree search algorithm in this paper. I. e. the priority k-d tree search algorithm is used twice.

priority search can be optimized to achieve the approximate precisions.

In image registration, many robust fitting methods like RANSAC and Least Median of Squares perform poorly when matching precision is below 50%. In order to improve matching precision, in this paper, we design the bidirectional priority k-d tree search algorithms (we will shortly call it as “the bidirectional priority search” in the following of this paper). I. e. the priority search is used twice in image registration. II.

STANDARD K-D TREE SEARCH AND PRIORITY K-D TREE

SEARCH ALGORITHM

A. Standard k-d tree search algorithm

In paper [2], the standard k-d tree search algorithm was proposed. The main steps of the standard k-d tree search algorithm can be summarized as follows:

Keywords-SIFT feature matching; priority k-d tree search Step 1: Apply branch-and-bound search in the descent down algorithm; bidirectional priority k-d tree search algorithm; the tree, until reaching a leaf node. matching precision Step 2: The first leaf node reached is as the candidate NN

for the query feature. The leaf node is the current node.

I. INTRODUCTION Step 3: If the distance from the query feature to the

In paper [10, 11], Lowe proposed a feature called SIFT candidate is smaller than the distance to the hyperrectangle that represented the image gradients within the local region corresponding to the sibling of the current node, turn to Step

7. of an image. The SIFT feature is invariant to the changes in

scale, illumination, and local affine distortions. Because of Step 4: If the distance from the query feature to the the invariant to image transformations, in recent years, candidate is smaller than the distance to the candidate’s feature-based methods using SIFT in image registration [1, father, turn to Step 6.

3] has been widely researched and applied. The Step 5: The candidate’s father is as the candidate NN.

dimensionality of SIFT feature is 128 and very high, so it Step 6: Apply branch-and-bound search in the descent down critically effects the performance of image registration the sibling of the current node to search the NN.

Step 7: If the current node is the root, stop the program, system.

The priority k-d tree search algorithm (we will shortly otherwise, back to the father of the current node, and the

father becomes the current node. Turn to Step 3. call it as “the priority search” in the following of this paper)

proposed in [4, 5, 7], is an efficient and approximate nearest B. Priority k-d tree search algorithm neighbor search algorithm. The priority search is the main

method for SIFT feature matching recently, and has been In paper [5], the priority search was improved on base of

the standard k-d tree search. The priority search is an

integrated into many systems [6, 10, 11]. The parameter

efficient algorithm, using a sorted list to store subtrees

Emax is the factor which seriously affects the performance (branches of the tree) that are in the order of increasing of the priority search. In order to get the relationships of the distance between the query feature and the hyperrectangle number of SIFT features, precisions and Emax, we find out corresponding to the subtree. The subtree with nearest the properties of a single k-d tree and that of the priority distance is prior to be examined. The difference between the search. Associate with the properties of the k-d tree and the standard and priority search is just the backtracking process. properties of the priority search, the relationships of how The priority search only examines the subtrees stored in the precisions are relative to the number of SIFT features and sorted list. The main steps of the priority search can be

summarized as follows: Emax are summarized. Referring to these relationships, the

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email