Classes | Public Types | Public Member Functions | Protected Member Functions | Private Types | Private Member Functions | Private Attributes
rtflann::KMeansIndex< Distance > Class Template Reference

#include <kmeans_index.h>

Inheritance diagram for rtflann::KMeansIndex< Distance >:
Inheritance graph
[legend]

List of all members.

Classes

struct  Node
struct  PointInfo

Public Types

typedef NNIndex< Distance > BaseClass
typedef Distance::ResultType DistanceType
typedef Distance::ElementType ElementType
typedef bool needs_vector_space_distance

Public Member Functions

void addPoints (const Matrix< ElementType > &points, float rebuild_threshold=2)
 Incrementally add points to the index.
BaseClassclone () const
void findNeighbors (ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const
int getClusterCenters (Matrix< DistanceType > &centers)
flann_algorithm_t getType () const
void initCenterChooser ()
 KMeansIndex (const Matrix< ElementType > &inputData, const IndexParams &params=KMeansIndexParams(), Distance d=Distance())
 KMeansIndex (const IndexParams &params=KMeansIndexParams(), Distance d=Distance())
 KMeansIndex (const KMeansIndex &other)
void loadIndex (FILE *stream)
KMeansIndexoperator= (KMeansIndex other)
void saveIndex (FILE *stream)
template<typename Archive >
void serialize (Archive &ar)
void set_cb_index (float index)
int usedMemory () const
virtual ~KMeansIndex ()

Protected Member Functions

void buildIndexImpl ()

Private Types

typedef BranchStruct< NodePtr,
DistanceType
BranchSt
typedef NodeNodePtr

Private Member Functions

void addPointToTree (NodePtr node, size_t index, DistanceType dist_to_pivot)
void computeClustering (NodePtr node, int *indices, int indices_length, int branching)
void computeNodeStatistics (NodePtr node, const std::vector< int > &indices)
void copyTree (NodePtr &dst, const NodePtr &src)
int exploreNodeBranches (NodePtr node, const ElementType *q, Heap< BranchSt > *heap) const
template<bool with_removed>
void findExactNN (NodePtr node, ResultSet< DistanceType > &result, const ElementType *vec) const
template<bool with_removed>
void findNeighborsWithRemoved (ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const
template<bool with_removed>
void findNN (NodePtr node, ResultSet< DistanceType > &result, const ElementType *vec, int &checks, int maxChecks, Heap< BranchSt > *heap) const
void freeIndex ()
void getCenterOrdering (NodePtr node, const ElementType *q, std::vector< int > &sort_indices) const
DistanceType getDistanceToBorder (DistanceType *p, DistanceType *c, DistanceType *q) const
int getMinVarianceClusters (NodePtr root, std::vector< NodePtr > &clusters, int clusters_length, DistanceType &varianceValue) const
void swap (KMeansIndex &other)

Private Attributes

int branching_
float cb_index_
flann_centers_init_t centers_init_
CenterChooser< Distance > * chooseCenters_
int iterations_
int memoryCounter_
PooledAllocator pool_
NodePtr root_

Detailed Description

template<typename Distance>
class rtflann::KMeansIndex< Distance >

Hierarchical kmeans index

Contains a tree constructed through a hierarchical kmeans clustering and other information for indexing a set of points for nearest-neighbour matching.

Definition at line 83 of file kmeans_index.h.


Member Typedef Documentation

template<typename Distance>
typedef NNIndex<Distance> rtflann::KMeansIndex< Distance >::BaseClass

Definition at line 89 of file kmeans_index.h.

template<typename Distance>
typedef BranchStruct<NodePtr, DistanceType> rtflann::KMeansIndex< Distance >::BranchSt [private]

Alias definition for a nicer syntax.

Definition at line 454 of file kmeans_index.h.

template<typename Distance>
typedef Distance::ResultType rtflann::KMeansIndex< Distance >::DistanceType

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 87 of file kmeans_index.h.

template<typename Distance>
typedef Distance::ElementType rtflann::KMeansIndex< Distance >::ElementType

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 86 of file kmeans_index.h.

template<typename Distance>
typedef bool rtflann::KMeansIndex< Distance >::needs_vector_space_distance

Definition at line 91 of file kmeans_index.h.

template<typename Distance>
typedef Node* rtflann::KMeansIndex< Distance >::NodePtr [private]

Definition at line 449 of file kmeans_index.h.


Constructor & Destructor Documentation

template<typename Distance>
rtflann::KMeansIndex< Distance >::KMeansIndex ( const Matrix< ElementType > &  inputData,
const IndexParams params = KMeansIndexParams(),
Distance  d = Distance() 
) [inline]

Index constructor

Params: inputData = dataset with the input features params = parameters passed to the hierarchical k-means algorithm

Definition at line 107 of file kmeans_index.h.

template<typename Distance>
rtflann::KMeansIndex< Distance >::KMeansIndex ( const IndexParams params = KMeansIndexParams(),
Distance  d = Distance() 
) [inline]

Index constructor

Params: inputData = dataset with the input features params = parameters passed to the hierarchical k-means algorithm

Definition at line 131 of file kmeans_index.h.

template<typename Distance>
rtflann::KMeansIndex< Distance >::KMeansIndex ( const KMeansIndex< Distance > &  other) [inline]

Definition at line 146 of file kmeans_index.h.

template<typename Distance>
virtual rtflann::KMeansIndex< Distance >::~KMeansIndex ( ) [inline, virtual]

Index destructor.

Release the memory used by the index.

Definition at line 187 of file kmeans_index.h.


Member Function Documentation

template<typename Distance>
void rtflann::KMeansIndex< Distance >::addPoints ( const Matrix< ElementType > &  points,
float  rebuild_threshold = 2 
) [inline, virtual]

Incrementally add points to the index.

Parameters:
pointsMatrix with points to be added
rebuild_threshold

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 215 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::addPointToTree ( NodePtr  node,
size_t  index,
DistanceType  dist_to_pivot 
) [inline, private]

Definition at line 969 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::buildIndexImpl ( ) [inline, protected, virtual]

Builds the index

Implements rtflann::NNIndex< Distance >.

Definition at line 329 of file kmeans_index.h.

template<typename Distance>
BaseClass* rtflann::KMeansIndex< Distance >::clone ( ) const [inline, virtual]

Implements rtflann::NNIndex< Distance >.

Definition at line 193 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::computeClustering ( NodePtr  node,
int *  indices,
int  indices_length,
int  branching 
) [inline, private]

The method responsible with actually doing the recursive hierarchical clustering

Params: node = the node to cluster indices = indices of the points belonging to the current node branching = the branching factor to use in the clustering

TODO: for 1-sized clusters don't store a cluster center (it's the same as the single cluster point)

Definition at line 542 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::computeNodeStatistics ( NodePtr  node,
const std::vector< int > &  indices 
) [inline, private]

Computes the statistics of a node (mean, radius, variance).

Params: node = the node to use indices = the indices of the points belonging to the node

Definition at line 495 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::copyTree ( NodePtr dst,
const NodePtr src 
) [inline, private]

Definition at line 467 of file kmeans_index.h.

template<typename Distance>
int rtflann::KMeansIndex< Distance >::exploreNodeBranches ( NodePtr  node,
const ElementType q,
Heap< BranchSt > *  heap 
) const [inline, private]

Helper function that computes the nearest childs of a node to a given query point. Params: node = the node q = the query point distances = array with the distances to each child node. Returns:

Definition at line 802 of file kmeans_index.h.

template<typename Distance>
template<bool with_removed>
void rtflann::KMeansIndex< Distance >::findExactNN ( NodePtr  node,
ResultSet< DistanceType > &  result,
const ElementType vec 
) const [inline, private]

Function the performs exact nearest neighbor search by traversing the entire tree.

Definition at line 835 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::findNeighbors ( ResultSet< DistanceType > &  result,
const ElementType vec,
const SearchParams searchParams 
) const [inline, virtual]

Find set of nearest neighbors to vec. Their indices are stored inside the result object.

Params: result = the result object in which the indices of the nearest-neighbors are stored vec = the vector for which to search the nearest neighbors searchParams = parameters that influence the search algorithm (checks, cb_index)

Implements rtflann::NNIndex< Distance >.

Definition at line 283 of file kmeans_index.h.

template<typename Distance>
template<bool with_removed>
void rtflann::KMeansIndex< Distance >::findNeighborsWithRemoved ( ResultSet< DistanceType > &  result,
const ElementType vec,
const SearchParams searchParams 
) const [inline, private]

Definition at line 715 of file kmeans_index.h.

template<typename Distance>
template<bool with_removed>
void rtflann::KMeansIndex< Distance >::findNN ( NodePtr  node,
ResultSet< DistanceType > &  result,
const ElementType vec,
int &  checks,
int  maxChecks,
Heap< BranchSt > *  heap 
) const [inline, private]

Performs one descent in the hierarchical k-means tree. The branches not visited are stored in a priority queue.

Params: node = node to explore result = container for the k-nearest neighbors found vec = query points checks = how many points in the dataset have been checked so far maxChecks = maximum dataset points to checks

Definition at line 755 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::freeIndex ( ) [inline, private, virtual]

Helper function

Implements rtflann::NNIndex< Distance >.

Definition at line 460 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::getCenterOrdering ( NodePtr  node,
const ElementType q,
std::vector< int > &  sort_indices 
) const [inline, private]

Helper function.

I computes the order in which to traverse the child nodes of a particular node.

Definition at line 880 of file kmeans_index.h.

template<typename Distance>
int rtflann::KMeansIndex< Distance >::getClusterCenters ( Matrix< DistanceType > &  centers) [inline]

Clustering function that takes a cut in the hierarchical k-means tree and return the clusters centers of that clustering. Params: numClusters = number of clusters to have in the clustering computed Returns: number of cluster centers

Definition at line 301 of file kmeans_index.h.

template<typename Distance>
DistanceType rtflann::KMeansIndex< Distance >::getDistanceToBorder ( DistanceType p,
DistanceType c,
DistanceType q 
) const [inline, private]

Method that computes the squared distance from the query point q from inside region with center c to the border between this region and the region with center p

Definition at line 902 of file kmeans_index.h.

template<typename Distance>
int rtflann::KMeansIndex< Distance >::getMinVarianceClusters ( NodePtr  root,
std::vector< NodePtr > &  clusters,
int  clusters_length,
DistanceType varianceValue 
) const [inline, private]

Helper function the descends in the hierarchical k-means tree by spliting those clusters that minimize the overall variance of the clustering. Params: root = root node clusters = array with clusters centers (return value) varianceValue = variance of the clustering (return value) Returns:

Definition at line 926 of file kmeans_index.h.

template<typename Distance>
flann_algorithm_t rtflann::KMeansIndex< Distance >::getType ( ) const [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 95 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::initCenterChooser ( ) [inline]

Definition at line 165 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::loadIndex ( FILE *  stream) [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 266 of file kmeans_index.h.

template<typename Distance>
KMeansIndex& rtflann::KMeansIndex< Distance >::operator= ( KMeansIndex< Distance >  other) [inline]

Definition at line 158 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::saveIndex ( FILE *  stream) [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 260 of file kmeans_index.h.

template<typename Distance>
template<typename Archive >
void rtflann::KMeansIndex< Distance >::serialize ( Archive &  ar) [inline]

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 234 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::set_cb_index ( float  index) [inline]

Definition at line 199 of file kmeans_index.h.

template<typename Distance>
void rtflann::KMeansIndex< Distance >::swap ( KMeansIndex< Distance > &  other) [inline, private]

Definition at line 1010 of file kmeans_index.h.

template<typename Distance>
int rtflann::KMeansIndex< Distance >::usedMemory ( ) const [inline, virtual]

Computes the inde memory usage Returns: memory used by the index

Implements rtflann::IndexBase.

Definition at line 208 of file kmeans_index.h.


Member Data Documentation

template<typename Distance>
int rtflann::KMeansIndex< Distance >::branching_ [private]

The branching factor used in the hierarchical k-means clustering

Definition at line 1025 of file kmeans_index.h.

template<typename Distance>
float rtflann::KMeansIndex< Distance >::cb_index_ [private]

Cluster border index. This is used in the tree search phase when determining the closest cluster to explore next. A zero value takes into account only the cluster centres, a value greater then zero also take into account the size of the cluster.

Definition at line 1039 of file kmeans_index.h.

template<typename Distance>
flann_centers_init_t rtflann::KMeansIndex< Distance >::centers_init_ [private]

Algorithm for choosing the cluster centers

Definition at line 1031 of file kmeans_index.h.

template<typename Distance>
CenterChooser<Distance>* rtflann::KMeansIndex< Distance >::chooseCenters_ [private]

Algorithm used to choose initial centers

Definition at line 1059 of file kmeans_index.h.

template<typename Distance>
int rtflann::KMeansIndex< Distance >::iterations_ [private]

Maximum number of iterations to use when performing k-means clustering

Definition at line 1028 of file kmeans_index.h.

template<typename Distance>
int rtflann::KMeansIndex< Distance >::memoryCounter_ [private]

Memory occupied by the index.

Definition at line 1054 of file kmeans_index.h.

template<typename Distance>
PooledAllocator rtflann::KMeansIndex< Distance >::pool_ [private]

Pooled memory allocator.

Definition at line 1049 of file kmeans_index.h.

template<typename Distance>
NodePtr rtflann::KMeansIndex< Distance >::root_ [private]

The root node in the tree.

Definition at line 1044 of file kmeans_index.h.


The documentation for this class was generated from the following file:


rtabmap
Author(s): Mathieu Labbe
autogenerated on Sat Jul 23 2016 11:44:32