A simple KD tree implementation. More...
#include <SIFT/KDTree.H>
Classes | |
| struct | BBFdata |
Public Member Functions | |
| KDTree (const std::vector< rutz::shared_ptr< Keypoint > > &keys, const std::vector< uint > &objindices=std::vector< uint >()) | |
| Constructor from a flat list of Keypoint objects. | |
| ~KDTree () | |
| Destructor. | |
| bool | isEmpty () const |
| Return true if we are empty (no pivot, no subtrees). | |
| bool | isLeaf () const |
| Return true if we are a leaf (valid pivot but no subtrees). | |
| uint | nearestNeighbor (const rutz::shared_ptr< Keypoint > &target, int &distsq1, int &distsq2) const |
| Find the nearest neighbor to hyperspace point 'target' in kd-tree. | |
| uint | nearestNeighborBBF (const rutz::shared_ptr< Keypoint > &target, const int searchSteps, int &distsq1, int &distsq2) const |
| Limited Best-Bin-First k-d-tree nearest neighbour search. | |
A simple KD tree implementation.
This class recursively constructs a KD tree from a flat list of exemplars. Then, it allows for efficient finding of the exemplar in the tree that is nearest a given target point, of of the set of exemplars in the tree that are within some distance of a given target point.
Definition at line 88 of file KDTree.H.
| KDTree::KDTree | ( | const std::vector< rutz::shared_ptr< Keypoint > > & | keys, | |
| const std::vector< uint > & | objindices = std::vector<uint>() | |||
| ) |
Constructor from a flat list of Keypoint objects.
Note that it is okay to destroy 'keys' as an internal copy will be kept. You may want to keep it around, however, and to not modify it, since the nearest neighbor functions in KDTree return indices in that original array of keys. Optionally, the array 'objindices' may be passed which contains an object number for each Keypoint; if it is specified, then second-matches will only be considered which belong the the same object as the best match.
Definition at line 42 of file KDTree.C.
References ASSERT, and rutz::shared_ptr< T >::reset().
| bool KDTree::isEmpty | ( | ) | const [inline] |
Return true if we are empty (no pivot, no subtrees).
Definition at line 274 of file KDTree.H.
References rutz::shared_ptr< T >::is_invalid().
| bool KDTree::isLeaf | ( | ) | const [inline] |
Return true if we are a leaf (valid pivot but no subtrees).
Definition at line 278 of file KDTree.H.
References rutz::shared_ptr< T >::is_invalid(), and rutz::shared_ptr< T >::is_valid().
| uint KDTree::nearestNeighbor | ( | const rutz::shared_ptr< Keypoint > & | target, | |
| int & | distsq1, | |||
| int & | distsq2 | |||
| ) | const |
Find the nearest neighbor to hyperspace point 'target' in kd-tree.
The index of the nearest keypoint in the list passed at construction is returned. After return 'distsq1' contains the absolute squared distance between the target point and the returned nearest neighbor point. 'distsq2' contains the squared distance between the target point and the second best match found during the search (the second best match is not returned; distsq2 is useful to check the quality of the best match).
| uint KDTree::nearestNeighborBBF | ( | const rutz::shared_ptr< Keypoint > & | target, | |
| const int | searchSteps, | |||
| int & | distsq1, | |||
| int & | distsq2 | |||
| ) | const |
Limited Best-Bin-First k-d-tree nearest neighbour search.
The index of the nearest keypoint in the list passed at construction is returned. Find the approximate nearest neighbour to the hyperspace point 'target' within the kd-tree using 'searchSteps' tail recursions at most (each recursion deciding about one neighbours' fitness). After return 'distsq1' contains the absolute squared distance between the target point and the returned nearest neighbor point. 'distsq2' contains the squared distance between the target point and the second best match found during the search (the second best match is not returned; distsq2 is useful to check the quality of the best match).
1.6.3