Fractal Approximate Nearest Neighbour Search in Log-Log Time

Nearest neighbour searches in the image plane are among the most frequent problems in a variety of computer vision and image processing tasks. They can be used to replace missing values in image filtering, or to group close objects in image segmentation, or to access neighbouring points of interest in feature extraction. In particular, we address two nearest neighbour problems: The nearest neighbour problem is usually stated independently of the application as returning the point p ∈ S,S = {(x1,y1), . . . ,(xn,yn)} that minimises the Euclidean distance ||p− q||2 to a query point q = (x,y). The simple solution of a linear scan comprises a comparison of q to all elements of S, which is too time-consuming for most applications, especially those with real-time requirements. If the nearest neighbour p ∈ S must be found for every coordinate q ∈ I of an image I = {(0,0),(0,1),(0,2), . . . ,(W,H)} of width W and height H, we obtain the all nearest neighbours problem. This problem occurs frequently in modern saliency based approaches, where only robustly detectable image regions are processed (for example in SIFT). In this paper, we introduce an approximate solution to solve these problems that is based on using a space filling curve. The central idea of the proposed approach is to map the image plane to one dimension using the Hilbert curve (Fig. 1). The nearest-neighbour problem is then solved efficiently in one dimension and mapped back to the 2D-plane.