Back to results
US 9,177,227 B2Granted
Method and device for finding nearest neighbor
AssigneeIvisys Aps
InventorMoatasem Chehaiber
Life of this patent
Estimating the term…
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.
Claims10
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.
11 more elements
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, and
- f. Repeating steps vi.d. and vi.e. until all groups in said interval have been examined.
10 more elements
Dependencies are inferred from the claim text.