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
sift feature matching algorithm is a hot field of image feature matching ,... leads to sift image registration algorithm for the current field of the ...
Image Registration Metho... 5页 10财富值 A ...Keywords-SIFT method ;Image Matching ;feature ...Simplified SIFT algorithm for fast image V ...
Modified sift descriptor... 7页 2财富值 A fast sift feature matc... ...algorithm to produce better invariant feature points for image matching under ...
Fast Parametric Elastic ... 16页 2财富值 A fast sift feature matc......Project Fast Image Registration 10 / 42 Iterative Closest Point Algorithm Pro...
A fast sift feature matc... 5页 1财富值 ...Matching algorithm Rajesh Kumar,Anurag Singh Tomar ...For large-size image registration, the main ...
matching SIFT key points, for registration under ...algorithm in compare with some other registration ...ed into two main approaches: feature-based ...
2014 doi:10.3969/j.issn.1673-9833.2014.01.015 基于 SIFT 特征匹配的图像...A Image Mosaic Algorithm Based on SIFT Feature Matching Liao Fei,Ye ...
SIFT feature-based image registration for a ...Image Fusion Image matching SIFT algorithm RANSAC ...
a number of matching algorithm, which feature matching algorithm has higher ...Key Words:SIFT; Image Registration; Scale space; extreme points; eigenvector...
A fast sift feature matc... 5页 1财富值 ...vector Features 一个 feature matching algorithm 被... SIFT 是一个 transformation,它会把一个 image 换...
热门文档