Quick search of nearest neighbours using KD ferns

摘要

Vehicle (50) comprising:a controller (60);a digital camera (14) capturing a digital image (12A) of an object (15) to be detected in or in front of the vehicle (50); and a system (10) comprising:a transmitter receiver (T) receiving the digital image (12A) from the digital camera (14);a processor (CPU);a database (DB) containing a variety of data points;wherein the processor (CPU) is designed to construct a multi-level KD fern using the plurality of data points in the database (DB), having a set of nodes as an ordered set of partition dimensions d and thresholds τ,where all nodes at the same level of the KD fern have the same partition dimension d and the same threshold β; andwhere, for each node, the division dimension d with maximum mean variance with respect to the data points is selected and the threshold value τ is selected in such a way that an entropy measure of the distribution of the data points after the division is maximized; andan accessible, non-volatile and computer-readable memory (MEM) containing instructions for performing an NN search;where the system (10) takes a query point from the digital image (12A), causes the processor (CPU) to execute the instructions, causing the processor (CPU):independently generates a binary (0- or 1-)bit for each of the KD fern nodes describing a corresponding decision with threshold comparison for that particular node;assigns each of a plurality of binary addresses in the binary figure to a corresponding index of a nearest neighbor;determines the binary address of the query point; andreturns a result (16) of a nearest neighbour to the controller by means of the transmitter receiver (T) by extracting the corresponding nearest neighbour for the query point from the binary figure; andwherein the controller (60) is designed to perform a control measure related to a property of the vehicle (50) in response to the returned result (16) of the nearest neighbor.