Approximate all nearest neighbor search for high dimensional entropy estimation for image registration

Information theoretic criteria such as mutual information are often used as similarity measures for inter-modality image registration. For better performance, it is useful to consider vector-valued pixel features. However, this leads to the task of estimating entropy in medium to high dimensional spaces, for which standard histogram entropy estimator is not usable. We have therefore previously proposed to use a nearest neighbor-based Kozachenko–Leonenko (KL) entropy estimator.Here we address the issue of determining a suitable all nearest neighbor (NN) search algorithm for this relatively specific task.We evaluate several well-known state-of-the-art standard algorithms based on k-d trees (FLANN), balanced box decomposition (BBD) trees (ANN), and locality sensitive hashing (LSH), using publicly available implementations. In addition, we present our own method, which is based on k-d trees with several enhancements and is tailored for this particular application.We conclude that all tree-based methods perform acceptably well, with our method being the fastest and most suitable for the all-NN search task needed by the KL estimator on image data, while the ANN and especially FLANN methods being most often the fastest on other types of data. On the other hand, LSH is found the least suitable, with the brute force search being the slowest.

► Kozachenko–Leonenko entropy estimator is based on nearest neighbor (NN) distances.
► Our target application is image registration.
► We use tight bounding boxes, all-NN best-bin-first search, handle multiplicites.
► We compare ANN, FLANN, LSH and our own BBF all-NN search algorithms.
► FLANN and ANN very good for general data, our method the best for image data.