METHOD AND DEVICE FOR FINDING NEAREST NEIGHBOR

• US 20130251269A1
• Filed: 12/15/2011
• Published: 09/26/2013
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Ivisys Sweden AB
• Original Assignee: Ivisys APS
• Inventors: Chehaiber, Moatasem
• Granted Patent: US 9,177,227 B2
• Time in Patent Office: Days
• US Class Current: 382/197
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects

Abstract

The present invention relates to a method and a device for finding nearest neighbor. In particular, it relates to a sorting, searching and matching multiple dimensional data, such as vectors, in order to find the nearest neighbor. The method is particularly useful as part of a SIFT algorithm.

Claims

1. A method for matching a specific vector among a data set consisting of a plurality of vectors, wherein the vectors represent scale invariant features, to identify scale invariant features in at least one image, the method comprising:

i. Selecting a reference point vector;

ii. Calculating the distances between said reference point vector and the vectors of the data set, d;

iii. Sorting the vectors of the data set into groups of vectors having the same distance, d_group, from said reference point vector;

iv. Subsequently rearranging each of the groups, which comprises more than two vectors, such that the second vector of the group has minimum distance to the first vector of the group, and each subsequent vector of the group has minimum distance to the previous vector of the group;

v. Identifying the best match for said specific vector by;

a. Calculating the distance, d_specific, between said reference point vector and said specific vector;

b. Identifying the group or groups having vectors with a distance, d, closest to said calculated distance, d_specfic;

c. Identifying the vector or vectors within the identified group or groups having the closest distance, d_minimum, to said specific vector;

d. Identifying any additional group with distances, d, from said reference point vector in the interval from the larger of zero and d_specific−

d_mmimum to d_specific+d_mmimum; and

e. Repeating steps v.c. and v.d. until all groups in said interval have been examined.

2. The method according to claim 1, wherein the next group to be examined is the unexamined group having the distance d closest to d_specific.

3. The method according to claim 1, wherein the vectors are multiple dimensional.

4. The method according to claim 1, wherein said distances, d, d_group, d_specific and d_minimum, are calculated as a distance selected among the group consisting of Euclidean, Mahalanobis, Manhattan, Chebyshe and Minkowski distance.

5. The method according to claim 1, wherein said distances, d, d_group, d_specific and d_minimum, are calculated as Euclidean distance.

6. The method according to claim 1, wherein said reference point vector is selected among the data set.

7. The method according to claim 1, wherein said reference point vector is selected as the midpoint of the data set.

10. The method according to claim 1 for identifying image features which are stable across different scales in an original image defined by a plurality of pixels, the method comprising:

a. Obtaining multiple difference images from an original image by calculating the difference obtained by applying different degrees of blurring to said original image;

b. Locating pixel amplitude extrema in said multiple difference images;

c. Producing a pixel gradient vector for each pixel in each difference image;

d. Associating vector orientations with respective actual maximal and minimal amplitude pixels associated with each difference image.

12. The image processing device according to claim 11, said image processing device comprising multiple chips, each chip configured to perform part of the identification of the best match for the specific vector of step v of claim 1.

17. A software program implementing the method according to claim 1.

18. The software program according to claim 17, adapted to identify scale invariant features in an image defined by a plurality of pixels.

8. A method for arranging a data set consisting of a plurality of vectors for subsequent matching a specific vector among the data set, the vectors representing scale invariant features in at least one image, for subsequently identifying scale invariant features in at least one image, the method comprising the steps of:

i. Selecting a reference point vector;

ii. Calculating the distances between said reference point vector and the vectors of the data set, d;

iii. Sorting the vectors of the data set into groups of vectors having the same distance, d_group, from said reference point vector; and

iv. Subsequently rearranging each of the groups, which comprises more than two vectors, such that the second vector of the group has minimum distance to the first vector of the group, and each subsequent vector of the group has minimum distance to the previous vector of the group.

9. A method according to claim 8, used for matching a specific vector among a data set consisting of a plurality of vectors, for identifying scale invariant features in at least one image, the method further comprising:

v. Identifying the best match for the specific vector by;

a. Calculating the distance, d_specific, between said reference point vector and said specific vector;

b. Identifying the group or groups having vectors with a distance, d, closest to said calculated distance, d_specific;

c. Identifying the vector or vectors within the identified group or groups having the closest distance, d_minimum, to said specific vector;

d. Identifying any additional group with distances, d, from said reference point vector in the interval from the larger of zero and d_specific−

d_mmimum to d_specific+d_mmimum; and

e. Repeating steps v.c. and v.d. until all groups in said interval have been examined.

11. An image processing device for identifying scale invariant features in an image defined by a plurality of pixels, said image processing device comprising a processor circuit configured to:

i. Select a reference point vector;

ii. Calculate the distances between said reference point vector and the vectors of the data set, d;

iii. Sort the vectors of the data set into groups of vectors having the same distance, d_group, from said reference point vector;

iv. Subsequently rearrange each of the groups, which comprises more than two vectors, such that the second vector of the group has minimum distance to the first vector of the group, and each subsequent vector of the group has minimum distance to the previous vector of the group;

v. Identify the best match for said specific vector by;

a. Calculating the distance, d_specific, between said reference point vector and said specific vector;

b. Identifying the group or groups having vectors with a distance, d, closest to said calculated distance, d_specific;

c. Identifying the vector or vectors within the identified group or groups having the closest distance, d_minimum, to said specific vector;

d. Identifying any additional group with distances, d, from said reference point vector in the interval from the larger of zero and d_specific−

d_mmimum to d_specific+d_mmimum; and

e. Repeat v.c. and v.d. until all groups in said interval have been examined.

13. The image processing device according to claim 11, said image processing device comprising at least one element selected among the group consisting of a GPU, DSP, FPGA and an ASIC.

14. The image processing device according to claim 11, said image processing device comprising:

Means for storing the reference point vector, the sorted vectors of the data set, the distances, d and d_group; and

means for receiving the specific vector.

15. (canceled)

16. (canceled)