FLANN

OpenCV incorporates the FLANN library in cv::flann namespace.

FLANN provides a library of feature matching methods. It can provide automatic selection of index tree and parameter based on the user's optimization preference on a particular data-set. They are chosen according to the user's preferences on the importance between between build time, search time and memory footprint of the index trees. The type of index trees are KD, randomized KD and Hierachical K-Means.

FLANN uses the Hierachical K-means Tree for generic feature matching. Nearest neighbors are discovered by choosing to examine the branch-not-taken nodes along the way. FLANN uses a priority-queue (Best-Bin-First) to do ANN from Hierachical K-Means Tree.
See background here:OpenCV Adventure: Algorithms used in FLANN

Sample in C (find_obj)

• The program attempts to locate an object from an image. Looking at the supplied pair (box, box_in_scene), the box is actually partly obscured. Besides using FLANN from OpenCV, the program also implements a primitive(naive) matching method. Using the output from either matching method, a perspective transform matrix will by obtained by cvHomography() with the corresponding key-points. The 4 corners from the source object will be mapped to the corresponding location on the image. A box will be drawn with the new corners. At the end, the straight-lines will be drawn between the corresponding key-point pairs.
• The feature points are detected with SURF detectors and represented in SURF-128 descriptors. The program by default set up 4 Randomized KDTrees and search for 2-nearest-neighbors. The matched key-point is only counted when the second of the nearest-neighbors is doubly farther than the first.
• The 'naive' NN search simply do the search linearly of each object key-point (~593) from the image key-points (782). It does however, keep track of the nearest 2 neighbors and  made sure the nearest is indeed dominant before being accepted. The 'naive' distance is simply a sum of squared- differences between the SURF descriptor tuples.
• Tried using 'auto-tuned' method. The choice is Linear! Perhaps the feature point are too few?
• Tricky namespaces: ::cv:flann and ::cvflann
• Perspective transform equation: see eqn(2.21) from the book by Szeliski 2010.

Code

• http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN
  There is link to both User Manual of FLANN library and Academic Paper behind it.

Resource

• Computer Vision: Algorithms and Applications, Szeliski 2010
• OCR sample with KNN http://blog.damiles.com/2008/11/basic-ocr-in-opencv/
• Another OCR sample with KNN http://www.aishack.in/2010/10/k-nearest-neighbors-in-opencv/