Neighbourhood Approximation using Randomized Forests

Leveraging available annotated data is an essential component of many modern methods for medical image analysis. In particular, approaches making use of the neighbourhood structure between images for this purpose have shown significant potential. Such techniques achieve high accuracy in analysing an image by propagating information from its immediate neighbours within an annotated database. Despite their success in certain applications, wide use of these methods is limited due to the challenging task of determining the neighbours for an out-of-sample image. This task is either computationally expensive due to large database sizes and costly distance evaluations, or infeasible due to distance definitions over semantic information, such as ground truth annotations, which is not available for out-of-sample images.

This article introduces Neighbourhood Approximation Forests (NAF), a supervised learning algorithm providing a general and efficient approach for the task of approximate nearest neighbour retrieval for arbitrary distances. Starting from an image database and a user-defined distance between images, the algorithm learns a small set of appearance-based features that are able to capture the distance-induced neighbourhood structure. NAF is able to efficiently infer nearest neighbours of an out-of-sample image using the learned appearance-based features, even when the original distance is based on semantic information. We perform experimental evaluation in two different scenarios: i) age prediction from brain MRI and ii) patch-based segmentation of unregistered, arbitrary field of view CT images. The results demonstrate the performance, computational benefits, and potential of NAF for different image analysis applications.