Determine the nearest neighbouring points to a given set of points. More...
Functions | |
AFAPI void | nearestNeighbour (array &idx, array &dist, const array &query, const array &train, const dim_t dist_dim=0, const unsigned n_dist=1, const af_match_type dist_type=AF_SSD) |
C++ interface wrapper for determining the nearest neighbouring points to a given set of points. More... | |
AFAPI af_err | af_nearest_neighbour (af_array *idx, af_array *dist, const af_array query, const af_array train, const dim_t dist_dim, const unsigned n_dist, const af_match_type dist_type) |
C++ interface wrapper for determining the nearest neighbouring points to a given set of points. More... | |
Determine the nearest neighbouring points to a given set of points.
A "point" is simply a geometric point's coordinates in an n-dimensional space, which can be specified along the dimension specified by dist_dim
(can be 0 or 1). A list of such points can be enumerated along the dimension other than the one specified by dist_dim
(excluding dim2 and dim3). By default, dist_dim
is 0, so a point's coordinates in this case must be specified along dim0, and the list of points must be enumerated along dim1. Consequently, if dist_dim
is 1, then a point's coordinates must be specified along dim1, and the list must be enumerated along dim0.
The arrays train
and query
are both a list of points, and one must have the same data layout as the other. This function calculates which points in the train
are nearest to each point in query
, based on the distance metric specified by dist_type:
AF_SAD (sum of absolute differences), AF_SSD (sum of squared differences, the default option), or AF_SHD (hamming distance). The resulting n_dist
nearest neighboring points are described in two output arrays:
idx:
contains the index of each result that corresponds to the point in train
dist:
contains the distance from the query point to the result's corresponding point in train
In both the output arrays idx
and dist
, the nearest neighbor results for a single query are enumerated along dim0, in which the \(ith\) result is the \(ith\) nearest point to the query point. The result set for each query point is placed along dim1 (columns) of idx
and dist
, in the order that the queries appear in query
. Therefore, the output arrays will have a shape of n_dist
\(\times\) the number of queries (regardless of the data layout of the input arrays, or the value of dist_dim
).
For illustration, a simple example is given below for 1 query in 1-dimensional space. There are 6 points in train
, and 3 nearest neighbors are queried for (n_dist
is 3), so there are 3 elements in the results for this single query, enumerated along dim0. The results idx
and dist
contain the 3 points closest to 1.25, ordered from nearest to farthest: point 0 in train
(1.) with an SSD distance of 0.0625 from the query, point 1 (2.) with a distance of 0.5625, and point 2 (3.) with a distance of 3.0625.
A slightly more complicated example is given below. There are 2 query
points and 6 train
points, and they are in 3-dimensional space (each point's coordinates are specified along dim0, and the list of points is enumerated along dim1). Note that in the output arrays idx
and dist
, there are 2 sets of results now, one for each query. The result set located on the the first column of idx
and dist
correspond to the first query (the first column in query
), and the result set on the second column of idx
and dist
correspond to the second query (second column in query
). Thus, for example, the second query point is (7.5, 9., 1.), and the point closest to it in train
is point 3, which is (8., 9., 1.), which has a SSD distance of 0.25 from the query point.
Note that it does not make sense for the train
and query
array shapes to have a third and fourth dimension, because a 2-dimensional array is sufficient to describe a list of points, no matter how long the list is or how many dimensions in space do the points span. Therefore, this function requires both input arrays to be at most 2-dimensional.
AFAPI af_err af_nearest_neighbour | ( | af_array * | idx, |
af_array * | dist, | ||
const af_array | query, | ||
const af_array | train, | ||
const dim_t | dist_dim, | ||
const unsigned | n_dist, | ||
const af_match_type | dist_type | ||
) |
C++ interface wrapper for determining the nearest neighbouring points to a given set of points.
[out] | idx | is an array of \(M \times N\) size, where \(M\) is n_dist and \(N\) is the number of queries. The value at position \(i,j\) is the index of the point in train along dim1 (if dist_dim is 0) or along dim 0 (if dist_dim is 1), with the \(ith\) smallest distance to the \(jth\) query point. |
[out] | dist | is an array of \(M \times N\) size, where \(M\) is n_dist and \(N\) is the number of queries. The value at position \(i,j\) is the distance from the \(jth\) query point to the point in train referred to by idx ( \(i,j\)). This distance is computed according to the dist_type chosen. |
[in] | query | is the array containing the points to be queried. The points must be described along dim0 and listed along dim1 if dist_dim is 0, or vice versa if dist_dim is 1. |
[in] | train | is the array containing the points used as training data. The points must be described along dim0 and listed along dim1 if dist_dim is 0, or vice versa if dist_dim is 1. |
[in] | dist_dim | indicates the dimension that the distance computation will use to determine a point's coordinates. The train and query arrays must both use this dimension for describing a point's coordinates |
[in] | n_dist | is the number of nearest neighbour points to return (currently only values <= 256 are supported) |
[in] | dist_type | is the distance computation type. Currently AF_SAD (sum of absolute differences), AF_SSD (sum of squared differences), and AF_SHD (hamming distances) are supported. |
AFAPI void nearestNeighbour | ( | array & | idx, |
array & | dist, | ||
const array & | query, | ||
const array & | train, | ||
const dim_t | dist_dim = 0 , |
||
const unsigned | n_dist = 1 , |
||
const af_match_type | dist_type = AF_SSD |
||
) |
C++ interface wrapper for determining the nearest neighbouring points to a given set of points.
[out] | idx | is an array of \(M \times N\) size, where \(M\) is n_dist and \(N\) is the number of queries. The value at position \(i,j\) is the index of the point in train along dim1 (if dist_dim is 0) or along dim 0 (if dist_dim is 1), with the \(ith\) smallest distance to the \(jth\) query point. |
[out] | dist | is an array of \(M \times N\) size, where \(M\) is n_dist and \(N\) is the number of queries. The value at position \(i,j\) is the distance from the \(jth\) query point to the point in train referred to by idx ( \(i,j\)). This distance is computed according to the dist_type chosen. |
[in] | query | is the array containing the points to be queried. The points must be described along dim0 and listed along dim1 if dist_dim is 0, or vice versa if dist_dim is 1. |
[in] | train | is the array containing the points used as training data. The points must be described along dim0 and listed along dim1 if dist_dim is 0, or vice versa if dist_dim is 1. |
[in] | dist_dim | indicates the dimension that the distance computation will use to determine a point's coordinates. The train and query arrays must both use this dimension for describing a point's coordinates |
[in] | n_dist | is the number of nearest neighbour points to return (currently only values <= 256 are supported) |
[in] | dist_type | is the distance computation type. Currently AF_SAD (sum of absolute differences), AF_SSD (sum of squared differences), and AF_SHD (hamming distances) are supported. |