An improved best bin first algorithm for fast image registration

Image registration is the significant part in some image processing applications. The scale invariant feature transform (SIFT) is the most commonly used as feature-based image registration algorithm. This algorithm will produce high dimensional feature descriptors. The best bin first (BBF) is a very efficient algorithm to find the nearest neighbor from a large number of high dimensional feature descriptors. But this algorithm has a shortage: it may not obtain the correct matching feature points when large scale exits among images. In this paper, we overcome the shortage through improving best bin first search algorithm; this approach is named improved BBF. The paper improves BBF from two aspects. First, we add a flag in data structure of k-d tree node, which represents whether the specified feature descriptor need search. This improving makes up the shortage effectively. Second, we build the k-d tree by selecting the most feature descriptors. This improving further improves the searching speed. Through large experiments, we demonstrate the effectiveness of the improved BBF search algorithm and the execution speed will increase above 10%.