approximate nearest neighbor search

[Xavier Delacour]

(resent with gzip'ed attachment, first message blocked b/c too large)

The attached change implements kd-trees and approximate nearest
neighbor search, allowing for log-linear-time matching of large sets
of high-dimensional feature vectors (such as those generated by SIFT,
SURF, etc). This is useful for object recognition and structure/motion
recovery. The paper

J.S. Beis and D.G. Lowe. Shape indexing using approximate
nearest-neighbor search in highdimensional spaces. In Proc. IEEE Conf.
Comp. Vision Patt. Recog., pages 1000--1006, 1997.
http://citeseer.ist.psu.edu/beis97shape.html

describes the approach. Usage is as follows: call cvCreateFeatureTree
with a matrix of feature vectors, cvFindFeatures to match new features
to those in the tree, and cvReleaseFeatureTree to free the tree.
Searching for a particular feature takes at most emax * log2(n) for n
features in the original set and a small constant emax (10 to 20 gives
good results).

There's a test for cvFindFeatures in tests/cv/src. Also another
function cvFindFeaturesBoxed does orthogonal range searching.

Feedback appreciated. I'd like to check this in after adding some docs.

Xavier


-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
Opencvlibrary-devel mailing list
Opencvlibrary-devel@...
https://lists.sourceforge.net/lists/listinfo/opencvlibrary-devel