k-distance transformations

Independently from the research on distance transformations, people defined nearest-neighbor and k-nearest-neighbors (k-NN) rules for multi-channel data classification [24,23,71,63,59,60,4,82]. Given a training set consisting of N prototype patterns (vectors in D dimensions where D is the number of channels), and the corresponding correct classification of each prototype into one of C classes, a pattern of unknown class is classified as class c if most of the k-closest prototypes are from class c.

Warfield [175] shows that - with a large number N of prototypes and a large number F of patterns to classify - a k-distance transformation (k-DT) is a very efficient implementation of k-NN classification, provided each channel is or can be quantized into a reasonable number of discrete values. First, a synthetic D-dimensional image is created, where each dimension corresponds to one channel. The bounds of the image are set so that they cover all possible patterns. Object pixels corresponding to the prototype patterns are inserted and the signed k-DT is computed over the image. The k-distance map can then be used as a look-up table to find the k-nearest neighbors of the patterns to classify.

With 2 channels, i.e. in 2D, he proposes to do this by adapting Borgefors' chamfer(3:4) algorithm [10]. In D-dimensions (D>2), he adapts Ragnelmam's corner EDT algorithm [128], that requires 2^D scans using corner masks containing D neighbors each. Both algorithms were described in sections and , respectively. They scan the image several times with different masks. At their core, the value of a pixel is updated as the minimum of its old value and the values computed from those of its neighbors that belong to the current mask.

Instead, Warfield uses a unique identifier for every prototype pattern (object pixel). At the core of the algorithm, he gathers into a single list the k identifiers of the current pixel and those of its masked neighbors. Then, he sorts the list so that he can select the k nearest patterns from it.

With 2^D scans using masks of D neighbors, this algorithm requires O (2^DF(D+1)k) distance computations, where F is the number of patterns to classify, i.e. the number of points of the D-dimensional synthetic image. Sorting of the lists of (D+1)k nearest patterns for each pixel requires O $(2^DF(D+1)k.\log((D+1)k))$ comparisons. Warfield compares this to the k-NN algorithms proposed by Friedman [59] and shows that k-DT is at least an order of magnitude faster for the type of applications he considers.