METHOD AND DEVICE FOR FINDING NEAREST NEIGHBOR
First Claim
Patent Images
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, dgroup, 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, dspecific, 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, dspecfic;
c. Identifying the vector or vectors within the identified group or groups having the closest distance, dminimum, 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 dspecific−
dmmimum to dspecific+dmmimum; and
e. Repeating steps v.c. and v.d. until all groups in said interval have been examined.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
18 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, dgroup, 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, dspecific, 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, dspecfic; c. Identifying the vector or vectors within the identified group or groups having the closest distance, dminimum, 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 dspecific−
dmmimum to dspecific+dmmimum; ande. Repeating steps v.c. and v.d. until all groups in said interval have been examined. - View Dependent Claims (2, 3, 4, 5, 6, 7, 10, 12, 17, 18)
-
-
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, dgroup, 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. - View Dependent Claims (9)
-
-
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, dgroup, 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, dspecific, 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, dspecific; c. Identifying the vector or vectors within the identified group or groups having the closest distance, dminimum, 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 dspecific−
dmmimum to dspecific+dmmimum; ande. Repeat v.c. and v.d. until all groups in said interval have been examined. - View Dependent Claims (13, 14)
-
-
15. (canceled)
-
16. (canceled)
Specification