Matching interest points

• US 8,666,173 B2
• Filed: 05/31/2011
• Issued: 03/04/2014
• Est. Priority Date: 01/18/2011
• Status: Active Grant

• Current Assignee: Aptina Imaging Corporation (ON Semiconductor Corporation)
• Original Assignee: Aptina Imaging Corporation (ON Semiconductor Corporation)
• Inventors: Huggett, Anthony R
• Primary Examiner(s): Akhavannik, Hadi
• Application Number:
  US13/149,824
• Publication Number:
  US 20120183228A1
• Time in Patent Office: 1,008 Days
• Field of Search: 382/219, 382/154
• US Class Current: 382/219
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

Interest points are markers anchored to a specific position in a digital image of an object. They are mathematically extracted in such a way that, in another image of the object, they will appear in the same position on the object, even though the object may be presented at a different position in the image, a different orientation, a different distance or under different lighting conditions. The goal is to match interest points in one image with corresponding interest points in another image. Typically, this involves the construction of a descriptor, which is both computationally expensive and resource-intensive. Methods and devices are described that match interest points without the construction of conventional descriptors and that permit the use of spatial coherency information to increase the accuracy of the match.

Claims

1. A method of matching interest points between images comprising:

from a dataset of interest points in a first image, the dataset comprising information identifying the position, scale and orientation of each interest point, calculating a first dataset of objects that each relate a base interest point to a satellite interest point, the calculated dataset comprising information identifying the normalized position of the satellite interest point relative to the base interest point and the normalized scale and orientation of the satellite interest point, wherein normalized means expressed relative to the scale and orientation of the base interest point;

from a dataset of interest points in a second image, the dataset comprising information identifying the position, scale and orientation of each interest point, calculating a second dataset of objects that each relate a base interest point to a satellite interest point, the calculated dataset comprising information identifying the normalized position of the satellite interest point relative to the base interest point and the normalized scale and orientation of the satellite interest point, wherein normalized means expressed relative to the scale and orientation of the base interest point;

generating matched pairs of objects by matching objects from the first calculated dataset to objects in the second calculated dataset;

from the matched pairs of objects, determining the interest points in the first dataset that are to be matched with interest points in the second dataset; and

matching the interest points accordingly, wherein, for each base interest point in the first dataset of interest points, the first calculated dataset of objects contains objects that relate that base interest point to a set of satellite interest points that is at most a subset of the remaining interest points in the first dataset of interest points and wherein, for each base interest point in the second dataset of interest points, the second calculated dataset of objects contains objects that relate that base interest point to a set of satellite interest points that is at most a subset of the remaining interest points in the second dataset of interest points.

2. The method of claim 1, wherein the subset of the remaining interest points in the first dataset of interest points contains the n interest points that are closest in position to the base interest point in question, where n is an integer.

3. The method of claim 2, wherein the subset of the remaining interest points in the second dataset of second interest points contains only the n interest points that are closest in position to the base interest point in question, where n is an integer.

4. The method of claim 3 wherein n is at least 16.

5. The method of claim 4 wherein n is at most 64.

6. The method of claim 5, comprising:

for each of a plurality of base interest points in the first dataset of interest points, identifying as satellite interest points a set of the n remaining interest points in the first dataset of interest points that are closest to the interest point in question; and

for each of the n satellite interest points so identified in the first dataset of interest points, calculating an object that relates the base interest point to the satellite interest point, comprising information identifying the normalized position of the satellite interest point relative to the base interest point and the normalized scale and orientation of the satellite interest point, wherein normalized means expressed relative to the scale and orientation of the base interest point.

7. The method of claim 6, comprising:

for each of a plurality of base interest points in the second dataset of interest points, identifying as satellite interest points a set of the n remaining interest points in the second dataset of interest points that are closest to the interest point in question; and

for each of the n satellite interest points so identified in the second dataset of interest points, calculating an object that relates the base interest point to the satellite interest point, comprising information identifying the normalized position of the satellite interest point relative to the base interest point and the normalized scale and orientation of the satellite interest point, wherein normalized means expressed relative to the scale and orientation of the base interest point.

8. The method of claim 7 wherein each of the objects in the first dataset of objects includes a first component and a second component, the first component independently identifying the normalized position of the satellite interest point relative to the base interest point and the second component independently identifying the normalized scale and orientation of the satellite interest point and wherein each of the objects in the second dataset of objects includes a first component and a second component, the first component independently identifying the normalized position of the satellite interest point relative to the base interest point and the second component independently identifying the normalized scale and orientation of the satellite interest point.

17. The method of claim 1 further comprising:

identifying an object in the first image, wherein the object has a first outline in the first image, wherein calculating the first dataset of objects comprises calculating the first dataset of objects from a first subset of the dataset of interest points in the first image, and wherein the first subset is limited to interest points that lie within the outline of the object in the first image; and

identifying the object in the second image, wherein the object has a second outline in the second image, wherein calculating the second dataset of objects comprises calculating the first dataset of objects from a second subset of the dataset of interest points in the second image, and wherein the second subset is limited to interest points that lie within the outline of the object in the second image.

9. A method of matching interest points between images comprising:

from a first dataset of objects that each relate a base interest point to a satellite interest point in a first image, the first dataset comprising information identifying the normalized position of the satellite interest point relative to the base interest point and the normalized scale and orientation of the satellite interest point, wherein normalized means expressed relative to the scale and orientation of the base interest point, and a second dataset of objects that each relate a base interest point to a satellite interest point in a second image, the second dataset comprising information identifying the normalized position of the satellite interest point relative to the base interest point and the normalized scale and orientation of the satellite interest point, generating matched pairs of objects by matching objects from the first dataset to objects in the second dataset;

constructing a first array wherein;

each row of the first array represents a particular interest point in the first image;

each column of the first array represents a particular interest point in the second image; and

each element of the first array has a value that represents the number of matched pairs of objects that relate the interest point of the corresponding row and the interest point of the corresponding column as base interest points;

locating an element in the first array that has a value representing a maximum number of matched pairs of objects to identify the pair of interest points corresponding to the row and column of that array element; and

matching the pair of interest points so identified, wherein the first array is constructed by;

initializing the elements of the first array to default values representative of no matched pairs of objects; and

for every matched pair of objects that relates an interest point in the first dataset or image and an interest point in the second dataset or image as base interest points, adjusting the value of the element of the first array that is in the row corresponding to the interest point in the first dataset or image and the column corresponding to the interest point in the second dataset or image, so as to increase by one the number of matched pairs of objects it represents, wherein;

each element of the first array has a value equal to the number of matched pairs of objects that relate the interest point of the corresponding row and the interest point of the corresponding column as base interest points.

10. The method of claim 9 wherein the first array is constructed by:

initializing the elements of the first array to zero; and

for every matched pair of objects that relates an interest point in the first dataset or image and an interest point in the second dataset or image as base interest points, increasing by one the value of the element of the first array that is in the row corresponding to the interest point in the first dataset or image and the column corresponding to the interest point in the second dataset or image.

11. The method of claim 10 further comprising:

in respect of a matched pair of objects that relates a base interest point to a satellite interest point in the first dataset or image and a base interest point to a satellite interest point in the second dataset or image, for which the satellite interest point in the first dataset or image and the satellite interest point in the second dataset or image are a matched pair, adjusting the value of the element of the first array that is in the row corresponding to the base interest point in the first dataset or image and the column corresponding to the base interest point in the second dataset or image, so as to increase the number of matched pairs of objects it represents;

then identifying an unmatched pair of interest points that have a maximum number of matched pairs of objects relating them as base interest points; and

matching the pair of base interest points so identified.

12. The method of claim 10 comprising:

in respect of all matched pairs of objects that relate base interest points to satellite interest points in the first dataset or image and base interest point to satellite interest points in the second dataset or image, for which the respective satellite interest point in the first dataset or image and the respective satellite interest point in the second dataset or image are a matched pair, adjusting the value of the element of the first array that is in the row corresponding to the respective base interest point in the first dataset or image and the column corresponding to the respective base interest point in the second dataset or image, so as to increase the number of matched pairs of objects it represents;

then identifying an unmatched pair of base interest points that have a maximum number of matched pairs of objects relating them as base interest points; and

matching the pair of base interest points whose identities are so determined.

13. The method of claim 12 further comprising:

in respect of a matched pair of objects that relates base interest points in the first and second datasets or images to the pair of base interest points whose identities are so determined as satellite interest points, adjusting the value of the element of the first array that is in the row corresponding to the base interest point in the first dataset or image and the column corresponding to the base interest point in the second dataset or image, so as to increase the number of matched pairs of objects it represents;

then determining the identity of an unmatched pair of base interest points that have a maximum number of matched pairs of objects relating them; and

matching the pair of base interest points whose identities are so determined.

14. The method of claim 13 further comprising:

until a termination condition is met, continuing, in respect of matched pairs of objects that relate base interest points to the pair of base interest points whose identities are so determined as satellite interest points, to adjust the values of the corresponding elements of the first array, so as to increase the number of matched pairs of objects they represent, to determine the identities of an unmatched pair of base interest points that have a maximum number of matched pairs of objects relating them and to match the pairs of base interest points whose identities are so determined.

15. The method of claim 14 further comprising:

in respect of a matched pair of objects that relates base interest points in the first and second datasets or images to one of the pair of base interest points whose identities are so determined and one other interest point as satellite interest points, adjusting the value of the element of the first array that is in the row corresponding to the base interest point in the first dataset or image and the column corresponding to the base interest point in the second dataset or image, so as to decrease the number of matched pairs of objects it represents;

then determining the identity of an unmatched pair of base interest points that have a maximum number of matched pairs of objects relating them; and

matching the pair of base interest points whose identities are so determined.

16. A method of matching interest points between images comprising:

from a dataset of interest points in a first image, the dataset comprising information identifying the position, scale and orientation of each interest point, calculating a first dataset of objects that each relate a base interest point to a satellite interest point, the calculated dataset comprising information identifying the normalized position of the satellite interest point relative to the base interest point and the normalized scale and orientation of the satellite interest point, wherein normalized means expressed relative to the scale and orientation of the base interest point;

from a dataset of interest points in a second image, the dataset comprising information identifying the position, scale and orientation of each interest point, calculating a second dataset of objects that each relate a base interest point to a satellite interest point, the calculated dataset comprising information identifying the normalized position of the satellite interest point relative to the base interest point and the normalized scale and orientation of the satellite interest point, wherein normalized means expressed relative to the scale and orientation of the base interest point;

generating matched pairs of objects by matching objects from the first calculated dataset to objects in the second calculated dataset;

constructing a first array wherein;

each row of the first array represents a particular base interest point in the first dataset; and

each column of the first array represents a particular base interest point in the second dataset;

constructing a second array wherein;

each row of the second array represents a respective interest point in the first dataset;

each column of the second array represents a respective interest point in the second dataset; and

the elements of the second array are used to represent the confidence with which the corresponding interest points have been matched and are initialized to default values;

initializing the elements of the first array, whereby the value of the element of the first array that is in the row corresponding to a base interest point in the first dataset and the column corresponding to a base interest point in the second dataset, is initialized to the sum over all matched pairs of objects that relate the base interest point of the row to a satellite interest point in the first dataset and the base interest point of the column to a satellite interest point in the second dataset, of the default values of the elements of the second array that are in the respective row corresponding to the satellite interest point in the first dataset and the respective column corresponding to the satellite interest point in the second dataset;

locating an element in the first array that has a maximum value to identify the pair of interest points corresponding to the row and column of that array element; and

matching the pair of interest points so identified.