System and method for performing corner guided curve matching of multiple images representing a scene

• US 6,665,440 B1
• Filed: 05/30/2000
• Issued: 12/16/2003
• Est. Priority Date: 05/30/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shan, Ying, Zhang, Zhengyou
• Primary Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/583,062
• Time in Patent Office: 1,295 Days
• Field of Search: 382/103, 382/154, 382/159, 382/181, 382/195, 382/199, 382/201-203, 382/206, 382/209, 382/216-218, 382/220, 382/254, 382/285, 382/291, 345/418, 345/419, 348/42, 348/51, 348/169, 356/12
• US Class Current: 382/209
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

The present invention is embodied in a curve matching system and method that is guided by a set of matched corners. The corner guided 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. For example, the images can be two dimensional image data, such as bitmap or raster image data. Curves of the images are then matched to correlate the two images of the scene for creating three dimensional (3D) curve information, such as 3D vector or mathematical 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 line segments defining a first set of curves and corners of a first image to a second set of curves and corners of a second image, comprising:

computing a set of similarity-invariant unary measurements and a similarity function for determining corner guidance;

defining the similarity function between two curves in a measurement space; and

matching line segments of the first image to corresponding line segments of the second image wherein the unary measurements are related to a distance from a corner to a curve of the image, and are used to control corner guidance on curve matching.

2. The method of claim 1, wherein the unary measurements are computed by approximating the curves with a set of line segments connected by separated seed points and obtaining the seed points in the first image by intersecting epipolar lines of the seed points of the first image with the curve to be matched to the second image.

3. The method of claim 1, wherein a corner is defined as a neighbor of a curve if its distance to the curve is less than a predefined threshold.

4. The method of claim 1, wherein a distance from a corner to a curve is defined by the minimum distance from the corner to midpoints of all line segments on the curve.

5. The method of claim 1, wherein an uncertainty of each unary measurement is related to the distance from a corner to a curve.

6. The method of claim 1, wherein the unary measurements include conventional quantities including at least one of neighborhood intensity, orientation, or local shape characteristics.

7. The method of claim 1 wherein a set of uncertainty measurements for the unary measurements is used to compute an optimal unary measurement for a complete curve and to control the impact of corner guidance on curve matching.

8. The method of claim 1, wherein the method operates in a computer readable medium.

9. A method for matching a first set of curves and corners of a first image to a second set of curves and corners of a second image, comprising:

defining line segments for the first set of curves and corners and for the second set of curves and corners;

determining corner guidance characteristics from a set of similarity-invariant unary measurements and a similarity function that is defined between two curves in a measurement space; and

matching line segments of the first image to corresponding line segments of the second image based on the corner guidance wherein the unary measurements are related to a distance from a corner to a curve of the image, and are used to control corner guidance with respect to curve matching.

10. The method of claim 9, wherein a distance from a corner to a curve is defined by the minimum distance from the corner to midpoints of all line segments on the curve.

11. The method of claim 9, wherein a corner is defined as a neighbor of a curve if its distance to the curve is less than a predefined threshold.

12. The method of claim 9, wherein predefined parameters of each unary measurement is related to the distance from a corner to a curve.

13. The method of claim 9, further comprising approximating the curves with a set of line segments connected by equally separated seed points.

14. The method of claim 13, further comprising obtaining the seed points in the first image by intersecting epipolar lines of the seed points of the first image with the curve to be matched to the second image.

15. The method of claim 9, wherein the unary measurements are represented by at least one of neighborhood intensity, orientation, or local shape characteristics.

16. The method of claim 9, further comprising using a set of uncertainty measurements for the unary measurements.

17. The method of claim 16, further comprising, computing an optimal unary measurement for a complete curve and controlling corner guidance with respect to curve matching.

18. A method for matching curves and corners of a first image to curves and corners of a second image, comprising:

approximating the curves with a set of line segments connected by seed points that are separated by a predetermined distance;

obtaining the seed points in the first image by intersecting epipolar lines of the seed points of the first image with the curve to be matched to the second image;

determining corner guidance characteristics from a set of similarity-invariant unary measurements and a similarity function that is defined between two curves in a measurement space; and

matching line segments of the first image to corresponding line segments of the second image based on the corner guidance.

19. The method of claim 18, wherein a corner is defined as a neighbor of a curve if its distance to the curve is less than a predefined threshold.

20. The method of claim 18, wherein the distance from a corner to a curve is defined by the minimum distance from the corner to midpoints of all line segments on the curve.

21. The method of claim 18, further comprising determining a distance from a corner to a curve and relating the distance as an uncertainty value for each unary measurement.

22. The method of claim 18, wherein the unary measurements include neighborhood intensity.

23. The method of claim 18, wherein a set of uncertainty measurements for the unary measurements is used to compute an optimal unary measurement for a complete curve.