The k-DT algorithm.

In terms of k-NN classification, the k-DT problem can be formulated as follows: given a set of N prototype patterns q(l) labeled from l=0 to l=N-1, determine the labels of the k nearest prototypes kNN $(p) = \{ \mathrm{NN}_i(p) \; , \; 0 \leq i < k \}$ for every possible pattern p in the pattern space I.
Similarly, the k-DT problem can be described in familiar image terms: given a set of N object pixels $q(l) \in O$ labeled from l=0 to l=N-1, determine the k nearest object pixels kNN(p) for every pixel p in the image I.
Although both formulations look similar, there is a minor difference in the fact that the ``image'' formulation supposes that prototypes are unique, i.e. that $q(l_1)=q(l_2) \Rightarrow l_1=l_2$. The ``pattern space'' formulation does not make this assumption. There can be several identical patterns among the prototypes.
The key to our approach is to notice that in algorithm , a lot of computational power is wasted in two ways. First, as pointed out by Ragnelmam in [127], the raster scanning procedure propagates the information further than needed. This is especially true for pattern spaces in higher dimensions, where 2^D scans are performed. Secondly, a large part of the computational cost is due to the sorting procedure.
We propose to generate the k-DT using ordered propagation to scan the pattern space, starting from the prototype patterns, then to their neighbors, their neighbors' neighbors, ... by order of increasing distance. The ordered propagation is achieved by bucket sorting the patterns in the propagation front, similarly to the Euclidean DT algorithm of chapter 2. The benefits of the method are twofold. First the propagation of every label is restricted to the zone of influence of the pattern it represents. Secondly, it is possible, by delaying the updates of the propagated patterns, to avoid the sorting procedure completely.
For every pixel p in the propagation front, we store both its coordinates (p_x1 , p_x2 , ... , p_xD) and the propagating label l. The propagation front is implemented as a number of buckets bucket(index). A propagating label l at pixel p is stored in bucket(dist_E(p,q(l))). By emptying the buckets by increasing index value, we scan the image in order of increasing distances.
In addition to the kNN(p) label maps that we generate, we store three additional temporary information for each pixel p. i_cur(p) indicates how many labels have reached p at any step of the algorithm. d_cur is the value of the distance from p to the prototype of the last label to have reached p, i.e d_cur=dist_E(p,q(NN_icur-1(p))). If more than one label among kNN(p) correspond to a prototype at distance d_cur, then i_dcur stores the first i for which d_cur=dist_E(p,q(NN_i(p))).
Let us now consider that distance d has been reached, i.e all buckets(d'), d' < d have been emptied and that the couples (p,l) in bucket(d) are being processed. Label l should be added to kNN(p) if two conditions are fulfilled. First, there should be less than k labels in kNN(p) already, since all labels in there are such that $dist_E(p,q(l)) \leq d$, and therefore better candidates than l. This is easily tested by checking that i_cur<k. Secondly, label l should not belong to kNN(p) yet. If d_cur(p) < d, it obviously does not. Otherwise, i.e when d_cur(p) = d, all labels NN_i(p) with $i_{dcur} \leq i < i_{cur}$ should be checked.
Finally, when a couple (p,l) is added to kNN(p), label l is then propagated towards p's neighbors. Of course, only those neighbors $n \in N$ that lead to dist_E(p+n,q(l)) > d need to be considered, i.e. those in the same direction as p-q(l). Practically, we use the 2D-direct neighborhood, for which this test is extremely simple. For instance, in 2 dimensions, with the 4-direct neighborhood, neighbor n=(1,0) is used if $p_x-q(l)_x \geq 0$, n=(-1,0) is used if $p_x-q(l)_x \leq 0$, ...

Algorithm 12   k-DT algorithm by bucket-sorting propagation.  

As usual, the implementation of this algorithm requires a special attention. In particular, the dynamic data structure used to implement the buckets should allocate memory in chunks and not element by element. In the experiments below, we use chunks of 2048 elements each. On the other hand, the k NN_i label maps and the additional temporary information are stored statically.
Finally, the computation of dist_E(p,q) is fastened by using small lookup tables for the squares of integers, i.e. $dist_E(p,q)= \sum_{i=1}^D \mathrm{sq}[ p_{x_i}-q_{x_i} ]$ with sq[n]=n² for all integer n within the useful range. Of course, any other integer-value metric could be used instead of dist_E.