How does it work comparing/matching images with kd-trees and nearest neighbor search?

Question

I have been querying google for some material about kd-trees and image comparison but I couldn't make the 'link' between the technics for image comparison using kd-trees. Firstly, I found some articles talking about speed improvement with randomized kd-trees, then I was introduced to SIFT. After understanding basically how SIFT works, I read about nearest neighbor search.

My real question is: If I have a mesh of points from SIFT, then I create the kd-tree for every image. How the nearest neighbor search can help me compare the images? At first, I thought that comparing images with a tree would work with some algorithm checking the tree structure and how near every point is from an image A from a point in the same node in and image B.

If the question is too dumb, please suggest material or some topic for search.

Thank you!

Answer 1

I'd suggest first understanding slow feature matching, without kdtrees.

• input: 1000 reference features, e.g. of faces or flowers; call these F1 .. F1000
• a query feature Q: which face or flower feature is most like, nearest, Q ?

As you know, SIFT reduces an image feature to 128 8-bit numbers, scaled so that
  similarity( feature F, feature Q ) = Euclidean distance( SIFT(F), SIFT(Q) ).

The simplest way to find which of F1 .. F1000 is most like Q is just to look at F1, F2 ... one by one:

# find the feature of F1 .. F1000 nearest Q
nearestdistance = infinity
nearestindex = 0
for j in 1 .. 1000:
    distance = Euclideandistance( SIFT(Fj), SIFT(Q) )  # 128 numbers vs. 128 numbers
    if distance < nearestdistance:
        nearestdistance = distance
        nearestindex = j

(Of course one computes the SIFT numbers outside the loop.)

A Kdtree is just a way of finding nearby vectors quickly; it has little to do with what is being matched (vectors of numbers representing ...), or how (Euclidean distance). Now kdtrees are very fast for 2d, 3d ... up to perhaps 20d, but may be no faster than a linear scan of all the data above 20d. So how can a kdtree work for features in 128d ? The main trick is to quit searching early. The paper by Muja and Lowe, Fast approximate nearest neighbors with automatic algorithm configuration, 2009, 10p, describes multiple randomized kdtrees for matching 128d SIFT features. (Lowe is the inventor of SIFT.)

To compare two images I and Q, one finds a set of feature vectors -- several hundred up to a few thousand SIFT vectors -- for each, and looks for near matches of these sets. (One may think of images as molecules, features as atoms; near-matching molecules is much harder than near-matching atoms, but it helps to be able to match atoms quickly.)

Hope this helps.