#include <mbl_cluster_tree.h>
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)<=Dd(t1,t3)+Dd(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.
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. | |
| mbl_cluster_tree< T, D >::mbl_cluster_tree | ( | ) |
| void mbl_cluster_tree< T, D >::empty | ( | ) | [private] |
| void mbl_cluster_tree< T, D >::add_object | ( | unsigned | 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.
Definition at line 109 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.
| void mbl_cluster_tree< T, D >::set_data | ( | const vcl_vector< T > & | data | ) |
Copy in data.
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 >::push_back | ( | const T & | t | ) |
| const vcl_vector<T>& mbl_cluster_tree< T, D >::data | ( | ) | const [inline] |
| 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_tree | ( | vcl_ostream & | os | ) | const |
| short mbl_cluster_tree< T, D >::version_no | ( | ) | const |
| void mbl_cluster_tree< T, D >::print_summary | ( | vcl_ostream & | os | ) | const |
| void mbl_cluster_tree< T, D >::b_write | ( | vsl_b_ostream & | bfs | ) | const |
| void mbl_cluster_tree< T, D >::b_read | ( | vsl_b_istream & | bfs | ) |
vcl_vector<T> mbl_cluster_tree< T, D >::data_ [private] |
vcl_vector<mbl_clusters<T,D> > mbl_cluster_tree< T, D >::cluster_ [private] |
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.5.1