Multi-image feature matching using multi-scale oriented patches

• US 20050238198A1
• Filed: 04/27/2004
• Published: 10/27/2005
• Est. Priority Date: 04/27/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brown, Matthew, Szeliski, Richard
• Granted Patent: US 7,382,897 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A system and process for identifying corresponding points among multiple images of a scene is presented. This involves a multi-view matching framework based on a new class of invariant features. Features are located at Harris corners in scale-space and oriented using a blurred local gradient. This defines a similarity invariant frame in which to sample a feature descriptor. The descriptor actually formed is a bias/gain normalized patch of intensity values. Matching is achieved using a fast nearest neighbor procedure that uses indexing on low frequency Haar wavelet coefficients. A simple 6 parameter model for patch matching is employed, and the noise statistics are analyzed for correct and incorrect matches. This leads to a simple match verification procedure based on a per feature outlier distance.

Claims

1. A computer-implemented process for identifying corresponding points among multiple images of a scene, comprising using a computer to perform the following process actions:

identifying interest points in each image, at varying resolutions, whose locations within the image depicting the point are defined by at least one property attributable to the pixels in a first prescribed-sized neighborhood around the point, and which can be assigned a unique orientation based on least one property attributable to the pixels in a second prescribed-sized neighborhood around the point;

generating a descriptor for each of the interest points which characterizes each point in a manner that is substantially invariant to changes in image location, orientation, and scale, as well as to changes in the intensity of the pixels used to define the location and orientation of the point;

finding substantially matching descriptors among the images; and

designating the interest points associated with each set of matching descriptors that appear in different images as corresponding points.

2. The process of claim 1, wherein the process action of identifying interest points in each image, comprises, for each image, the actions of:

forming an image resolution pyramid, and for each level of the pyramid,

identifying locations in the image under consideration representative of a corner feature,

identifying the orientation of each corner feature,

designating the identified location of each corner feature as a separate interest point, and

assigning the identified orientation of each corner feature to the interest point associated with that feature.

3. The process of claim 2, wherein the process action of identifying locations in the image under consideration representative of a corner feature, comprises the actions of:

identifying the location of each corner feature which exhibits a corner strength that is a local maximum of a pixel neighborhood of a prescribed minimum neighborhood radius that is centered on the location and which exceeds a prescribed minimum strength threshold;

incrementing the neighborhood radius by a prescribed integer value, and identifying those previously identified locations whose corner strength is still a local maximum of the pixel neighborhood currently under consideration and which still exceeds the prescribed minimum strength threshold;

repeating the incrementing and second identifying actions until the number of locations identified is no larger than a prescribed maximum number; and

designating each of the remaining identified locations as representative of a separate corner feature.

4. The process of claim 2, wherein the process action of designating the identified location of each corner feature as a separate interest point, comprises an action of designating as the location of each interest point, the location where the maximum intensity of a 2D quadratic surface fitted over a local neighborhood of a prescribed size which is centered on the identified location under consideration, is exhibited.

5. The process of claim 2, wherein the process action of identifying the orientation of each corner feature comprises an action of identifying the orientation of each corner feature using a blurred gradient approach.

6. The process of claim 2, wherein each corner feature is a Harris corner.

7. The process of claim 1, wherein the process action of generating a descriptor for each of the interest points, comprises, for each interest point, the actions of:

establishing a descriptor region of a prescribed p×

p size which is centered on the interest point location under consideration and which is oriented according to the orientation of the interest point;

forming a prescribed-sized d×

d descriptor vector that is smaller than the descriptor region and sampled therefrom using bilinear interpolation of the intensity values of the pixels within the region in a manner that results in sampling roughly once per pixel;

normalizing the descriptor vector; and

performing a Haar wavelet transformation on the descriptor vector to produce a transformed vector.

8. The process of claim 7, wherein the process action of finding substantially matching descriptors among the images, comprises an action of matching the transformed descriptor vectors to a prescribed number of its nearest neighbors in feature space.

9. The process of claim 8, wherein the process action of matching the transformed descriptor vectors, comprises the actions of:

generating a 3D hash table from a prescribed number (n) of the wavelet coefficients of each transformed descriptor vector to form a hash table of n-coefficient vectors;

for each bin of the hash table, computing the distance between each n-coefficient vector found in the bin under consideration;

for each n-coefficient vector, identifying a prescribed number of its nearest neighbors based on the computed distances which reside in the same bin but which are not associated with the same image as the vector under consideration to form sets of potentially matching vectors;

designating the interest points associated with the vectors in each set of potentially matching vectors as corresponding points depicting the same part of the scene in the associated images.

10. The process of claim 9, wherein the hash table has 10 bins per dimension and each bin has overlapping ranges of one half, and wherein the prescribed number (n) of the wavelet coefficients comprises the first three non-zero wavelet coefficients thereby forming a hash table of three-coefficient vectors.

11. The process of claim 9, wherein the process action of designating the interest points associated with the vectors in each set of potentially matching vectors as corresponding points, comprises the actions of:

for each of the potentially matching vectors, eliminating any three-coefficient vectors from consideration as a potentially matching vectors whose associated interest points do not actually correspond to an interest point in another image associated with another of the three-coefficient vectors in the same set of vectors; and

for each of the three-coefficient vectors remaining in each set of potentially matching vectors, designating the interest points associated with the vectors as corresponding points in the associated images.

12. The process of claim 11, wherein the process action of eliminating any three-coefficient vectors from consideration as a potentially matching vectors whose associated interest points do not actually correspond to an interest point in another image associated with another of the three-coefficient vectors in the same set of vectors, comprises, for each set of matched vectors, the actions of:

computing an outlier distance for the set of matching vectors under consideration;

determining if the distance computed for any of the matching vectors is more than about 65% of the outlier distance; and

whenever a matching vector is found to have a distance that is more than about 65% of the outlier distance, eliminating the interest point associated with that vector as a corresponding point.

13. The process of claim 11, wherein the process action of eliminating any three-coefficient vectors from consideration as a potentially matching vectors whose associated interest points do not actually correspond to an interest point in another image associated with another of the three-coefficient vectors in the same set of vectors, comprises, for each set of matched vectors, the actions of:

performing a geometric outlier rejection procedure; and

eliminating the interest point associated with any vector as a corresponding point that is found to be an outlier.

14. The process of claim 8, wherein the process action of matching the transformed descriptor vectors, comprises the actions of:

generating a 3D hash table from the first three non-zero wavelet coefficients of each transformed descriptor vector to form a hash table of three-coefficient vectors;

for each bin of the hash table, computing the distance between each three-coefficient vector found in the bin under consideration;

for each three-coefficient vector, identifying the nearest neighbors found in the same bin that are associated with each image respectively, except the image associated with the vector under consideration, up to a prescribed number for each image, based on the computed distances, to form sets of potentially matching vectors;

designating the interest points associated with the vectors in each set of potentially matching vectors as corresponding points depicting the same part of the scene in the associated images.

15. The process of claim 14, wherein the hash table has 10 bins per dimension and each bin has overlapping ranges of one half.

16. The process action of claim 1, wherein the first and second prescribed-sized neighborhoods are the same size.

17. A system for identifying corresponding points among multiple images of a scene, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

identify interest points representing potential corresponding points in each image, wherein each interest point is defined by a location and orientation assigned to it based on the pattern formed by a prescribed property of the pixels in a neighborhood centered around the point;

generate a descriptor for each of the interest points which characterizes each point in a manner that is substantially invariant to changes in image location, orientation, and scale, as well as to changes in the bias and gain of the pixels used to define the location and orientation of the point;

find substantially matching descriptors among the images; and

designate the interest points associated with each set of matching descriptors that appear in different images as corresponding points.

18. The system of claim 17, wherein the program module for identifying interest points, comprises, for each image, the sub-modules of:

(a) forming an image resolution pyramid;

(b) selecting a previously unselected pyramid level;

(c) identifying the location of each Harris corner occurring in the selected level;

(d) selecting a previously unselected Harris corner;

(e) determining if the corner strength of the selected Harris corner is a local maximum in a pixel neighborhood of a prescribed minimum neighborhood radius centered on a point representing the location of the corner and exceeds a prescribed minimum strength threshold;

(f) whenever the corner strength is a local maximum and exceeds a prescribed minimum strength threshold, designating it as a candidate corner;

(g) determining if there are any previously unselected Harris corners remaining, and whenever there are remaining corners repeat sub-modules (d) through (g) until all the corners have been considered;

(h) incrementing the last-used neighborhood radius by a prescribed integer value;

(i) selecting a previously unselected candidate corner;

(j) determining if the corner strength of the selected candidate corner exceeds the prescribed minimum strength threshold and is a local maximum in a pixel neighborhood centered on a point representing the location of the selected corner and whose size is defined by of the current neighborhood radius;

(k) whenever the corner strength is a local maximum and exceeds a prescribed minimum strength threshold, retaining its designation as a candidate corner and otherwise removing the designation;

(l) determining if there are any previously unselected candidate corners remaining, and whenever there are remaining corners repeat sub-modules (i) through (l) until all the candidate corners have been considered;

(m) determining whether the number of Harris corners still designated as candidate corners exceeds a prescribed maximum allowable number;

(n) whenever the number of candidate corners exceeds the prescribed maximum allowable number, repeating sub-modules (h) through (n) until the number of candidate corner no longer exceeds the maximum allowable number;

(o) designating the points which define the location of each of the remaining candidate corners as interest points for the image under consideration;

(p) refining the location of each interest point by designating its location to be the point where the maximum intensity of a 2D quadratic surface fitted over a local neighborhood of a prescribed size, which is centered on the selected point, occurs;

(q) assigning an orientation to each interest point determined using a blurred gradient approach; and

(r) repeating sub-modules (b) through (q), until all the pyramid levels have been considered.

19. The system of claim 17, wherein the program module for generating a descriptor for each of the interest points, comprises, for each interest point, the sub-modules of:

(a) establishing a descriptor region of a prescribed size p×

p, which is centered on the interest point location and oriented according to the orientation of the interest point;

(b) forming a descriptor vector of a smaller prescribed size d×

d from the descriptor region using bilinear interpolation sampling of the intensity values of the region;

(c) normalizing the descriptor vector in regard to bias and gain;

(d) subjecting the normalized descriptor vector to a Haar wavelet transformation to form the descriptor of the interest point under consideration;

20. The system of claim 19, wherein the program module for finding substantially matching descriptors among the images, comprises sub-modules for:

(e) generating a 3D hash table from the first three non-zero wavelet coefficients of each interest point descriptor;

(f) computing the distance between each descriptor in each bin of the hash table;

(g) selecting a previously unselected descriptor;

(h) identifying a prescribed number of the selected descriptors nearest neighbors in the same bin that are not associated with the same image as the selected descriptor;

(i) computing an outlier distance for the selected descriptor and its nearest neighbors;

(j) respectively determining if the computed distance between the selected descriptor and each of its nearest neighbors is less than about 65% of the outlier distance;

(k) whenever it is found that the computed distance between the selected descriptor and one its nearest neighbors is less than about 65% of the outlier distance, designating the nearest neighbor descriptor as a matching descriptor with regard to the selected descriptor; and

(l) performing a geometric-based outlier rejection procedure to determine if any of the interest points corresponding to the descriptors designated as matching the selected descriptor does not substantially correspond to the location of the interest point of selected descriptor;

(m) eliminating as a matching descriptor any descriptor designated as matching the selected descriptor that does not substantially correspond to the location of the interest point of selected descriptor; and

(n) repeating sub-modules (g) through (m) until all the remaining descriptors have been considered.

21. The system of claim 19, wherein the program module for finding substantially matching descriptors among the images, comprises sub-modules for:

(e) generating a 3D hash table from the first three non-zero wavelet coefficients of each interest point descriptor;

(f) computing the distance between each descriptor in each bin of the hash table;

(g) selecting a previously unselected descriptor;

(h) identifying a prescribed number of the selected descriptors nearest neighbors in the same bin that are not associated with the same image as the selected descriptor;

(i) computing an outlier distance for the selected descriptor and its nearest neighbors;

(j) respectively determining if the computed distance between the selected descriptor and each of its nearest neighbors is less than about 65% of the outlier distance;

(k) whenever it is found that the computed distance between the selected descriptor and one its nearest neighbors is less than about 65% of the outlier distance, designating the nearest neighbor descriptor as a matching descriptor with regard to the selected descriptor; and

(l) repeating sub-modules (g) through (k) until all the remaining descriptors have been considered.

22. The system of claim 19, wherein the program module for finding substantially matching descriptors among the images, comprises sub-modules for:

(e) generating a 3D hash table from the first three non-zero wavelet coefficients of each interest point descriptor;

(f) computing the distance between each descriptor in each bin of the hash table;

(g) selecting a previously unselected descriptor;

(h) identifying a prescribed number of the selected descriptors nearest neighbors in the same bin that are not associated with the same image as the selected descriptor;

(i) performing a geometric-based outlier rejection procedure to determine which of the interest points corresponding to the nearest neighbor descriptors substantially correspond to the location of the interest point of selected descriptor;

(j) designating a nearest neighbor descriptor as a matching descriptor with regard to the selected descriptor only if it is found that the interest point corresponding to the nearest neighbor descriptor substantially corresponds to the location of the interest point of selected descriptor.

(k) repeating sub-modules (g) through (j) until all the remaining descriptors have been considered.

23. A computer-readable medium having computer-executable instructions for identifying corresponding points among multiple images of a scene, said computer-executable instructions comprising:

identifying interest points representing potential corresponding points in each image, wherein each interest point corresponds to a location in an image that is identifiable by a unique pattern formed by a prescribed property of the pixels in a neighborhood centered around the location;

assigning an orientation to each interest point, wherein the orientation is derived from said pattern formed by the prescribed property of the pixels in the neighborhood centered around the interest point;

generating a descriptor for each of the interest points which characterizes each point in a manner that is substantially invariant to changes in image location, orientation, and scale, as well as to changes in the bias and gain of the pixels used to define the location and orientation of the point;

finding substantially matching descriptors among the images; and

designating the interest points associated with each set of matching descriptors that appear in different images as corresponding points.