Detection of image correspondence using radial cumulative similarity

• US 6,343,150 B1
• Filed: 11/25/1998
• Issued: 01/29/2002
• Est. Priority Date: 11/25/1997
• Status: Expired due to Term

• Current Assignee: Vulcan Patents LLC
• Original Assignee: Interval Research Corporation
• Inventors: Darrell, Trevor, Covell, Michele M.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/199,799
• Time in Patent Office: 1,161 Days
• Field of Search: 382/115, 382/124, 382/125, 382/215, 382/218, 382/219, 382/276, 382/278, 382/280, 382/281, 382/288, 382/181, 382/195, 382/201, 382/209
• US Class Current: 382/218
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/37 using transform domain methods
• CPC Class Codes: G06T 7/97 Determining parameters from multiple pictures depth or shape recovery from multiple images G06T7/55; stereo camera calibration G06T7/85

Abstract

A given point of interest in an image is defined by two properties, a local attribute, such as color, and a neighborhood function that describes a similarity pattern. The color value is not influenced by nearby background regions of the image, and functions as a descriptor for each location. The neighborhood function distinguishes locations of similar color from one another, by capturing patterns of change in the local color. The neighborhood function measures the similarity between the local color and colors at nearby points, and reduces the measured similarity values that lie beyond contrast boundaries. Through the computation of such a transform for points of interest in an image, corresponding points in other images can be readily identified.

Claims

1. A method for determining the correspondence between points in two images, comprising the steps of:

determining a representation for a point in a first image, comprising a central attribute value and a similarity function which identifies the similarity of points within a window containing said point in said first image to said central attribute value;

selecting a point in a second image;

determining a representation for said point in said second image; and

comparing said representation for said point in said first image with said representation for said point in said second image.

2. The method of claim 1, wherein said central attribute value is the color for the point.

3. The method of claim 1, wherein said central attribute value is the average color over an area of the image which includes the point.

4. The method of claim 1 including the steps of selecting a plurality of points in said second image, determining a representation for each selected point and comparing each such representation to the representation for the point in the first image, and identifying the selected point in the second image whose representation differs the least from the representation for the point in the first image as a corresponding point.

5. The method of claim 4, wherein a representation is determined for each point in the first image, and compared with plural points in the second image, to produce a dense map of image correspondences.

6. The method of claim 4, comprising the steps of computing a representation for each of a plurality of points in the first image which are nodal points on a closed contour, and identifying corresponding nodal points in the second image to track the closed contour in the second image.

7. The method of claim 6 further including the steps of:

determining the value of an attribute of the image at selected points on a line between two nodal points of the closed contour;

for each such point, determining the similarity of said attribute value to the attribute value for other points in the image in a direction of propagation from said selected point that is perpendicular to said line; and

combining the determined similarities for the selected points to produce a profile for the contour.

8. The method of claim 7, wherein the profile for the contour is compared to a profile for a contour defined by proposed node locations in said second image, to track the contour in the second image.

9. A method for generating a representation of a point in an image, comprising the steps of:

determining the value of an attribute of the image at a selected point in the image;

determining the similarity of said attribute value to the attribute value for other points in the image in radial directions of propagation from said selected point; and

combining the determined similarities to produce a neighborhood function that indicates the radial homogeneity of the attribute value.

10. The method of claim 9, wherein said similarities are combined by computing the integral of the similarities in a direction of radial propagation.

11. A method for determining the correspondence between points in two images, comprising the steps of:

determining a characteristic value for each of a plurality of points in first and second images

comparing the characteristic values for plural pairs of points, where each pair comprises a point in the first image and a point in the second image, to determine difference values; and

anisotropically smoothing said difference values by combining difference values for different pairs of points, while limiting the pairs of points that are combined in accordance with a mask function for each point.

12. The method of claim 11, wherein said mask identifies the points that are associated with a foreground portion of an image.

13. The method of claim 12, wherein said mask is defined by the steps of:

determining the value of an attribute of an image at a selected point in the image;

determining the similarity of said attribute value to the attribute value for other points in the image in radial directions of propagation from said selected point; and

combining the determined similarities to produce a neighborhood function that indicates the radial homogeneity of the attribute value.

14. The method of claim 12, wherein said mask is defined by the steps of:

determining the value of an attribute of an image at a selected point in the image;

measuring the difference between said attribute value and the attribute value for other points in the image;

propagating said measurement in different directions relative to said selected point until a dissimilarity is encountered in each such direction; and

defining a region of local homogeneity relative to the selected point, based on the propagated measurements.

15. A method for determining correspondence between images, comprising the steps of:

computing a local image transform which indicates a structure of a foreground region within a window, for each of a plurality of image points, wherein the structure of the foreground region is computed by;

determining a value of an attribute of an image at a selected point in the image,

measuring a difference between said attribute value and an attribute value for other points in the image,

propagating said measurement in different directions relative to said selected point until a dissimilarity is encountered in each such direction, and

defining a region of local homogeneity relative to the selected point, based on the propagated measurements; and

comparing the transforms for pairs of points to determine their correspondence.

16. A method for determining correspondence between images, comprising the steps of:

computing a local image transform which indicates a structure of a foreground region within a window, for each of a plurality of image points, wherein the structure of the foreground region is computed by;

determining a value of an attribute of an image at a selected point in the image,

determining a similarity of said attribute value to an attribute value for other points in the image in radial directions of propagation from said selected point, and

combining the determined similarities to produce a neighborhood function that indicates a radial homogeneity of the attribute value; and

comparing the transforms for pairs of points to determine their correspondence.