MVE - Multi-View Environment mve-devel
|
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. | |
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.
|
inline |
Definition at line 81 of file nearest_neighbor.h.
void sfm::NearestNeighbor< float >::find | ( | float const * | query, |
NearestNeighbor< float >::Result * | result | ||
) | const |
Definition at line 272 of file nearest_neighbor.cc.
void sfm::NearestNeighbor< short >::find | ( | short const * | query, |
NearestNeighbor< short >::Result * | result | ||
) | const |
Definition at line 216 of file nearest_neighbor.cc.
void sfm::NearestNeighbor< T >::find | ( | T const * | query, |
Result * | result | ||
) | const |
Find the nearest neighbor of 'query'.
void sfm::NearestNeighbor< unsignedshort >::find | ( | unsigned short const * | query, |
NearestNeighbor< unsigned short >::Result * | result | ||
) | const |
Definition at line 242 of file nearest_neighbor.cc.
|
inline |
Definition at line 111 of file nearest_neighbor.h.
|
inline |
For SfM, this is the descriptor length.
Definition at line 97 of file nearest_neighbor.h.
|
inline |
For SfM, this is the descriptor memory block.
Definition at line 90 of file nearest_neighbor.h.
|
inline |
For SfM, this is the number of descriptors.
Definition at line 104 of file nearest_neighbor.h.