System and method for matching curves of multiple images representing a scene

• US 6,718,062 B1
• Filed: 05/30/2000
• Issued: 04/06/2004
• Est. Priority Date: 05/30/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zhengyou, Shan, Ying
• Primary Examiner(s): Dastouri, Mehrdad
• Assistant Examiner(s): KIBLER, VIRGINIA M
• Application Number:
  US09/584,013
• Time in Patent Office: 1,407 Days
• Field of Search: 382/154, 382/215, 382/199, 382/190, 382/195, 382/205, 382/209, 382/218, 382/219, 345/419, 345/420, 356/2, 356/12
• US Class Current: 382/218
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/35 using statistical methods
• CPC Class Codes: G06T 7/564 from contours
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/752 Contour matching

Abstract

The present invention is embodied in a system and method for curve matching multiple images of a scene. The curve matching produces a geometrical representation of the scene from the images, which can be used for any suitable application, such as computer and stereo vision applications. In general, first, multiple images depicting a scene are digitally received by the system. The images are graphical images digitally received and processed as two dimensional image data, such as bitmap or raster image data. Curve matching of the images is then performed to correlate the two images of the scene for creating three dimensional (3D) curve information, such as 3D vector information, of the scene. This 3D vector information can then be used in any suitable manner, for example, to digitally reconstruct the scene for stereo vision applications.

Claims

1. A method for matching sets of corresponding curves, wherein each curve represents a portion of corresponding images, comprising:

performing epipolar breaking to break the curves into shorter pieces so that a seed point on one of the curves matches no more than one seed point on another corresponding curve, wherein said epipolar breaking comprises breaking a curve into parts at points where a tangent line of the curve is parallel to the epipolar line passing through that point;

representing each curve with line segments;

computing representative measurements for each line segment of each curve;

matching the line segments between corresponding curves of the images; and

progressively modeling uncertainty in the representative measurements for reducing ambiguities in the matching.

2. The method of claim 1, wherein matching the line segments includes computing similarity-invariant measurements for each line segment.

3. The method of claim 2, wherein the similarity-invariant measurements are computed with binary measurements.

4. The method of claim 1, further comprising computing similarity-invariant unary measurements for each line segment.

5. The method of claim 1, wherein the line segments are created by approximating a piece-wise linear model with the line segments.

6. The method of claim 1, wherein the similarity-invariant measurements for each line segment includes a combination of unary and binary measurements.

7. The method of claim 1, further comprising determining similarities between the curves and compatibilities of the curves among neighborhood matches of the curves.

8. A method for matching a first curve of a first image to at least a second curve of a second image, comprising:

performing epipolar breaking to break the curves into shorter pieces so that a seed point on one of the curves matches no more than one seed point on the other curve, wherein said epipolar breaking comprises breaking a curve into parts at points where a tangent line of the curve is parallel to the epipolar line passing through that point, unless said point is a reflection point;

representing each curve with plural line segments;

matching the line segments of the first curve to the line segments of the second curve by computing similarity-invariant binary measurements for each line segment of each curve;

combining the binary measurements; and

progressively modeling uncertainty in the combined binary measurements for reducing ambiguities in matching.

9. The method of claim 8 further comprising computing similarity-invariant unary measurements for each line segment for corner guidance.

10. The method of claim 9, wherein the unary measurements determine attributes representing at least one of orientation of a curve, intensity in a predefined neighborhood of a curve and local shape characteristics of a curve.

11. The method of claim 9, wherein the similarity-invariant measurements for each line segment includes a combination of unary and binary measurements.

12. The method of claim 8, wherein the binary measurements include attributes representing angle and distance between a pair of neighboring curves.

13. The method of claim 8, wherein the line segments are created by approximating a piece-wise linear model with the line segments.

14. A method for matching a first curve of a first image to a second curve of a second image, each being represented by line segments in an epipolar geometrical relationship, the method comprising:

determining whether each curve intersects an epipolar line more than once;

breaking the curve into multiple curves if the curve intersects an epipolar line more than once, wherein said breaking comprises breaking the curve at Points where a tangent line of the curve is parallel to the epipolar line passing through that point;

representing each curve associated with the first and second curves with plural line segments;

matching the line segments of the curves associated with the first curve to the line segments of the curves associated with the second curve by computing similarity-invariant measurements for each line segment of each curve; and

progressively modeling uncertainty in the measurements for reducing ambiguities in matching.

15. The method of claim 14, further comprising ensuring that the curves approximate a suitable piece-wise linear model.

16. The method of claim 15, wherein ensuring that the curves approximate a suitable piece-wise linear model includes breaking the curves at high curvature points.

17. The method of claim 15, wherein the similarity-invariant measurements are computed with binary measurements.

18. The method of claim 17, further comprising computing similarity-invariant unary measurements for each line segment.

19. The method of claim 18, wherein the similarity-invariant measurements for each line segment includes a combination of the unary and the binary measurements.

20. The method of claim 18, wherein the binary measurements determine similarities between the curves and compatibilities of the curves among neighborhood matches of the curves.

21. The method of claim 18, wherein the unary measurements determine attributes representing at least one of orientation of a curve, intensity in a predefined neighborhood of a curve and local shape characteristics of a curve.

22. The method of claim 15, further comprising determining similarities between the curves and compatibilities of the curves among neighborhood matches of the curves.