Method and device for finding nearest neighbor
First Claim
Patent Images
1. A method comprising:
- identifying scale invariant features in at least one image by matching a specific vector among a dataset consisting of a plurality of vectors, wherein the vectors represent scale invariant features, comprising;
i. Selecting a reference point vector, wherein the reference point vector is selected among the data set;
ii. Calculating the distances, d, between said reference point vector and each of the vectors of the data set;
iii. Re-arranging the plurality of vectors of the data set as a function of ascending distance, d, to the reference point vector;
iv. Sorting the vectors of the data set into groups of vectors having the same distance, dgroup, from said reference point vector;
v. Subsequently rearranging the vectors of each of the groups of vectors, which comprises more than two vectors, such that the second vector of the group has a minimum distance to the first vector of the group, and each subsequent vector of the group has a minimum distance to the previous vector of the group;
vi. Identifying the best match for said specific vector by;
a. Calculating the distance, dspecific, between said reference point vector and the specific vector;
b. Comparing the calculated distance, dspecific, and a distance between the reference point vector and a vector positioned in the middle of the re-arranged plurality of vectors;
c. Identifying, using successive approximation and based on the distance between the reference point vector and a vector positioned in the middle of the re-arranged plurality of vectors, the group of vectors having vectors with a distance, d, closest to said calculated distance, dspecific;
d. Identifying the vector or vectors within the identified group or groups having the closest distance, dminimum, to said specific vector;
e. Identifying any additional group with distances, d, from said reference point vector in an interval from the larger of zero and dspecific−
dminimum to dspecific+dminimum; and
f. Repeating steps vi.d. and vi.e. 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.
18 Citations
10 Claims
-
1. A method comprising:
-
identifying scale invariant features in at least one image by matching a specific vector among a dataset consisting of a plurality of vectors, wherein the vectors represent scale invariant features, comprising; i. Selecting a reference point vector, wherein the reference point vector is selected among the data set; ii. Calculating the distances, d, between said reference point vector and each of the vectors of the data set; iii. Re-arranging the plurality of vectors of the data set as a function of ascending distance, d, to the reference point vector; iv. Sorting the vectors of the data set into groups of vectors having the same distance, dgroup, from said reference point vector; v. Subsequently rearranging the vectors of each of the groups of vectors, which comprises more than two vectors, such that the second vector of the group has a minimum distance to the first vector of the group, and each subsequent vector of the group has a minimum distance to the previous vector of the group; vi. Identifying the best match for said specific vector by; a. Calculating the distance, dspecific, between said reference point vector and the specific vector; b. Comparing the calculated distance, dspecific, and a distance between the reference point vector and a vector positioned in the middle of the re-arranged plurality of vectors; c. Identifying, using successive approximation and based on the distance between the reference point vector and a vector positioned in the middle of the re-arranged plurality of vectors, the group of vectors having vectors with a distance, d, closest to said calculated distance, dspecific; d. Identifying the vector or vectors within the identified group or groups having the closest distance, dminimum, to said specific vector; e. Identifying any additional group with distances, d, from said reference point vector in an interval from the larger of zero and dspecific−
dminimum to dspecific+dminimum; andf. Repeating steps vi.d. and vi.e. until all groups in said interval have been examined. - View Dependent Claims (2, 3, 4, 9, 10)
-
-
5. An image processing device, said image processing device comprising a processor circuit configured to:
-
Identify scale invariant features in an image defined by a plurality of pixels by; i. Selecting a reference point vector, wherein the reference point vector is selected among the data set; ii. Calculating the distances, d, between said reference point vector and each of the vectors of the data set; iii. Re-arranging the plurality of vectors of the data set as a function of ascending distance, d, to the reference point vector; iv. Sorting the vectors of the data set into groups of vectors having the same distance, dgroup, from said reference point vector; v. Subsequently rearranging the vectors of each of the groups of vectors, which comprises more than two vectors, such that the second vector of the group has a minimum distance to the first vector of the group, and each subsequent vector of the group has a minimum distance to the previous vector of the group; vi. Identifying the best match for said specific vector by; a. Calculating the distance, dspecific, between said reference point vector and the specific vector; b. Comparing the calculated distance, dspecific, and a distance between the reference point vector and a vector positioned in the middle of the re-arranged plurality of vectors; c. Identifying, using successive approximation and based on the distance between the reference point vector and a vector positioned in the middle of the re-arranged plurality of vectors, the group of vectors having vectors with a distance, d, closest to said calculated distance, dspecific; d. Identifying the vector or vectors within the identified group or groups having the closest distance, dminimum, to said specific vector; e. Identifying any additional group with distances, d, from said reference point vector in an interval from the larger of zero and dspecific−
dminimum to dspecific+dminimum, andf. Repeating steps vi.d. and vi.e. until all groups in said interval have been examined. - View Dependent Claims (6, 7, 8)
-
Specification