MVE - Multi-View Environment mve-devel
Loading...
Searching...
No Matches
Classes | Public Member Functions | List of all members
sfm::NearestNeighbor< T > Class Template Reference

Nearest (and second nearest) neighbor search for normalized vectors. More...

#include <nearest_neighbor.h>

Classes

struct  Result
 Unlike the naming suggests, these are square distances. More...
 

Public Member Functions

 NearestNeighbor (void)
 
void find (float const *query, NearestNeighbor< float >::Result *result) const
 
void find (short const *query, NearestNeighbor< short >::Result *result) const
 
void find (T const *query, Result *result) const
 Find the nearest neighbor of 'query'.
 
void find (unsigned short const *query, NearestNeighbor< unsigned short >::Result *result) const
 
int get_element_dimensions (void) const
 
void set_element_dimensions (int element_dimensions)
 For SfM, this is the descriptor length.
 
void set_elements (T const *elements)
 For SfM, this is the descriptor memory block.
 
void set_num_elements (int num_elements)
 For SfM, this is the number of descriptors.
 

Detailed Description

template<typename T>
class sfm::NearestNeighbor< T >

Nearest (and second nearest) neighbor search for normalized vectors.

Finding the nearest neighbor for a query Q in a list of candidates Ci boils down to finding the Ci with smallest distance ||Q - Ci||, or smallest squared distance ||Q - Ci||^2 (which is cheaper to compute).

||Q - Ci||^2 = ||Q||^2 + ||Ci||^2 - 2 * <Q | Ci>.

If Q and Ci are normalized, ||Q - Ci||^2 = 2 - 2 * <Q | Ci>. Thus, we want to quickly compute and find the largest inner product <Q, Ci> corresponding to the smallest distance.

Notes: For SSE accellerated dot products, vector dimension must be a factor of 8 (i.e. 128 bit registers for SSE). Query and elements must be 16 byte aligned for efficient memory access.

The following types are supported:

Definition at line 46 of file nearest_neighbor.h.

Constructor & Destructor Documentation

◆ NearestNeighbor()

template<typename T >
sfm::NearestNeighbor< T >::NearestNeighbor ( void  )
inline

Definition at line 81 of file nearest_neighbor.h.

Member Function Documentation

◆ find() [1/4]

void sfm::NearestNeighbor< float >::find ( float const *  query,
NearestNeighbor< float >::Result *  result 
) const

Definition at line 272 of file nearest_neighbor.cc.

◆ find() [2/4]

void sfm::NearestNeighbor< short >::find ( short const *  query,
NearestNeighbor< short >::Result *  result 
) const

Definition at line 216 of file nearest_neighbor.cc.

◆ find() [3/4]

template<typename T >
void sfm::NearestNeighbor< T >::find ( T const *  query,
Result result 
) const

Find the nearest neighbor of 'query'.

◆ find() [4/4]

void sfm::NearestNeighbor< unsignedshort >::find ( unsigned short const *  query,
NearestNeighbor< unsigned short >::Result *  result 
) const

Definition at line 242 of file nearest_neighbor.cc.

◆ get_element_dimensions()

template<typename T >
int sfm::NearestNeighbor< T >::get_element_dimensions ( void  ) const
inline

Definition at line 111 of file nearest_neighbor.h.

◆ set_element_dimensions()

template<typename T >
void sfm::NearestNeighbor< T >::set_element_dimensions ( int  element_dimensions)
inline

For SfM, this is the descriptor length.

Definition at line 97 of file nearest_neighbor.h.

◆ set_elements()

template<typename T >
void sfm::NearestNeighbor< T >::set_elements ( T const *  elements)
inline

For SfM, this is the descriptor memory block.

Definition at line 90 of file nearest_neighbor.h.

◆ set_num_elements()

template<typename T >
void sfm::NearestNeighbor< T >::set_num_elements ( int  num_elements)
inline

For SfM, this is the number of descriptors.

Definition at line 104 of file nearest_neighbor.h.


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