Record trees of clusters of data, for fast neighbour finding. More...
#include <mbl_cluster_tree.h>
Public Member Functions | |
| mbl_cluster_tree () | |
| Default constructor. | |
| void | set_max_r (const vcl_vector< double > &r) |
| Define number of levels and max radius of clusters at each level. | |
| void | set_data (const vcl_vector< T > &data) |
| Copy in data. | |
| void | push_back (const T &t) |
| Add an extra element to data(). | |
| const vcl_vector< T > & | data () const |
| List of objects. | |
| unsigned | nearest (const T &t, double &d) const |
| Return index of nearest object in data() to t. | |
| void | print_tree (vcl_ostream &os) const |
| Print ancestry of every element. | |
| short | version_no () const |
| Version number for I/O. | |
| void | print_summary (vcl_ostream &os) const |
| Print class to os. | |
| void | b_write (vsl_b_ostream &bfs) const |
| Save class to binary file stream. | |
| void | b_read (vsl_b_istream &bfs) |
| Load class from binary file stream. | |
Private Member Functions | |
| void | empty () |
| Empty clusters. | |
| void | add_object (unsigned i) |
| Append new object with index i and assign to clusters. | |
Private Attributes | |
| vcl_vector< T > | data_ |
| Storage for objects. | |
| vcl_vector< mbl_clusters< T, D > > | cluster_ |
| Clusters. | |
| vcl_vector< vcl_vector < unsigned > > | parent_ |
| Indicate which cluster each object is assigned to. | |
Record trees of clusters of data, for fast neighbour finding.
Used to record clusters of objects of type T. D::d(T t1, T t2) is a measure of distance between two objects. It must obey the triangle inequality: D::d(t1,t2)<=D::d(t1,t3)+D::d(t2,t3).
The class is designed to allow fast location of the nearest example in a set objects to a given new object. It represents the data as a set of key point positions, together with a list of indices into the external data for each cluster. Each cluster is in turn assigned to a large cluster at a higher level.
Thus to find the nearest neighbour, we first check for proximity to the keypoints, and only consider objects in the clusters which are sufficiently close.
Definition at line 27 of file mbl_cluster_tree.h.
| mbl_cluster_tree< T, D >::mbl_cluster_tree | ( | ) |
Default constructor.
Definition at line 20 of file mbl_cluster_tree.txx.
| void mbl_cluster_tree< T, D >::add_object | ( | unsigned | new_i | ) | [private] |
Append new object with index i and assign to clusters.
Assumes that new object data()[i] is available. Deduce which clusters belongs to and add it. Create new clusters if further than max_r() from any.
Assumes that new object data()[i] is available. Deduce which cluster it belongs to and add it. Create new cluster if further than max_r() from any.
Definition at line 109 of file mbl_cluster_tree.txx.
| void mbl_cluster_tree< T, D >::b_read | ( | vsl_b_istream & | bfs | ) |
Load class from binary file stream.
Definition at line 250 of file mbl_cluster_tree.txx.
| void mbl_cluster_tree< T, D >::b_write | ( | vsl_b_ostream & | bfs | ) | const |
Save class to binary file stream.
Definition at line 238 of file mbl_cluster_tree.txx.
| const vcl_vector<T>& mbl_cluster_tree< T, D >::data | ( | ) | const [inline] |
List of objects.
Definition at line 67 of file mbl_cluster_tree.h.
| void mbl_cluster_tree< T, D >::empty | ( | ) | [private] |
Empty clusters.
Definition at line 27 of file mbl_cluster_tree.txx.
| unsigned mbl_cluster_tree< T, D >::nearest | ( | const T & | t, |
| double & | d | ||
| ) | const |
Return index of nearest object in data() to t.
Nearest object in data() to t is given by data()[nearest(t,d)]; The distance to the point is d
Definition at line 79 of file mbl_cluster_tree.txx.
| void mbl_cluster_tree< T, D >::print_summary | ( | vcl_ostream & | os | ) | const |
| void mbl_cluster_tree< T, D >::print_tree | ( | vcl_ostream & | os | ) | const |
Print ancestry of every element.
Definition at line 205 of file mbl_cluster_tree.txx.
| void mbl_cluster_tree< T, D >::push_back | ( | const T & | t | ) |
Add an extra element to data().
Definition at line 68 of file mbl_cluster_tree.txx.
| void mbl_cluster_tree< T, D >::set_data | ( | const vcl_vector< T > & | data | ) |
Copy in data.
Define external data array (pointer retained).
Empty existing clusters, then process every element of data to create clusters, by calling add_object()
Definition at line 57 of file mbl_cluster_tree.txx.
| void mbl_cluster_tree< T, D >::set_max_r | ( | const vcl_vector< double > & | r | ) |
Define number of levels and max radius of clusters at each level.
Definition at line 38 of file mbl_cluster_tree.txx.
| short mbl_cluster_tree< T, D >::version_no | ( | ) | const |
Version number for I/O.
Definition at line 232 of file mbl_cluster_tree.txx.
vcl_vector<mbl_clusters<T,D> > mbl_cluster_tree< T, D >::cluster_ [private] |
Clusters.
Definition at line 34 of file mbl_cluster_tree.h.
vcl_vector<T> mbl_cluster_tree< T, D >::data_ [private] |
Storage for objects.
Definition at line 31 of file mbl_cluster_tree.h.
vcl_vector<vcl_vector<unsigned> > mbl_cluster_tree< T, D >::parent_ [private] |
Indicate which cluster each object is assigned to.
parent_[0][i] indicates which cluster in cluster_[0] data_[i] is assigned to. parent_[j][i] (j>0) indicates which cluster in level above cluster_[j-1].p()[i] is assigned to.
Definition at line 41 of file mbl_cluster_tree.h.
1.7.5.1