Nearest Neighbor Classification for Quadtree representations of binary images

摘要

This report presents an accelerated Nearest Neighbor (NN) classifier for quadtree representations of binary images generated by color target detection. This method finds the NN prototype to the input quadtree from many prototypes and classifies the input to the prototype class. For this purpose, we add the density information to the grey nodes of the tree. In the coarse-to-fine comparison between two trees, we can calculate the upper and lower bounds of the distance between these trees by referring the density information at any level. Using these upper and lower bounds, we can reduce the NN candidates to the input in the similar way to the branch-and-bound or A{sup}* algorithms. We modified this method by performing best-first search for accelerating the decreasing speed of the minimum upper bound. This enables further reduction of the NN candidates. The classification speed can further be accelerated depending on the fact that the problem is not a NN search problem but a NN classification. That is, if all the NN candidates belong to a single class, we can classify the input immediately. Through the experiments, we confirmed that our method is over forty times faster than the brute force NN search.