Editing Scale-invariant feature transform (section)

=== Feature matching and indexing ===
Indexing consists of storing SIFT keys and identifying matching keys from the new image. Lowe used a modification of the [[k-d tree]] algorithm called the '''[[Best bin first|best-bin-first]] search''' (BBF) method<ref name="Beis1997" /> that can identify the [[nearest neighbor search|nearest neighbors]] with high probability using only a limited amount of computation. The BBF algorithm uses a modified search ordering for the [[k-d tree]] algorithm so that bins in feature space are searched in the order of their closest distance from the query location. This search order requires the use of a [[heap (data structure)|heap]]-based [[priority queue]] for efficient determination of the search order. We obtain a candidate for each keypoint by identifying its nearest neighbor in the database of keypoints from training images. The nearest neighbors are defined as the keypoints with minimum [[Euclidean distance]] from the given descriptor vector. The way Lowe<ref name=Lowe2004 /> determined whether a given candidate should be kept or 'thrown out' is by checking the ratio between the distance from this given candidate and the distance from the closest keypoint which is not of the same object class as the candidate at hand (candidate feature vector / closest different class feature vector), the idea is that we can only be sure of candidates in which features/keypoints from distinct object classes don't "clutter" it (not geometrically clutter in the feature space necessarily but more so clutter along the right half (>0) of the real line), this is an obvious consequence of using [[Euclidean distance]] as our nearest neighbor measure. The ratio threshold for rejection is whenever it is above 0.8. This method eliminated 90% of false matches while discarding less than 5% of correct matches. To further improve the efficiency of the best-bin-first algorithm search was cut off after checking the first 200 nearest neighbor candidates. For a database of 100,000 keypoints, this provides a speedup over exact nearest neighbor search by about 2 orders of magnitude, yet results in less than a 5% loss in the number of correct matches.