System and method for progressive stereo matching of digital images

• US 20050163367A1
• Filed: 03/17/2005
• Published: 07/28/2005
• Est. Priority Date: 05/04/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zhengyou, Shan, Ying
• Granted Patent: US 7,164,790 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 7/593 from stereo images
• 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
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: H04N 13/239 using two 2D image sensors having a relative position equal to or related to the interocular distance H04N13/243 takes precedence
• CPC Class Codes: H04N 13/243 using three or more 2D image sensors
• CPC Class Codes: H04N 2013/0081 Depth or disparity estimation from stereoscopic image signals

Abstract

A method and a system for progressive stereo matching of digital images representing a scene. In general, the present invention uses a progressive iterative technique that includes a disparity gradient limit principle and a least commitment strategy. Generally unambiguous pixel matches are found by beginning with a few reliable pixel matches and finding progressively more unambiguous pixel matches. Unambiguous pixel matches are used to define the search ranges for each pixel to guide matching in the current iteration. Unambiguous pixel matches then are found using a novel correlation technique and based on a correlation score associated with a pixel match. The search range is capable of being rotated, and is part of a novel correlation technique that provides a more robust estimate of pixel match reliability. Potential pixel matches found in the search ranges are tested for ambiguity and unambiguous matches are selected and added to the reliable pixel matches.

Claims

1. A method of stereo matching digital images representing a scene, comprising:

determining possible pixel matches between a target pixel from a first digital image and pixels from a second digital image;

evaluating a reliability of each of the possible pixel matches;

predicting a disparity between the target pixel and pixels from the second image;

estimating an uncertainty of the predicted pixel disparity; and

classifying a certain pixel match based on the reliability of the possible pixel matches.

2. The method of claim 1, wherein the pixels from the second image satisfy an epipolar constraint.

3. The method of claim 2, wherein the pixels from the second image satisfy a disparity gradient limit constraint.

4. The method of claim 1, wherein the reliability is evaluated using the least commitment strategy.

6. The method of claim 1, wherein classifying a certain pixel match comprises:

generating a list of candidate pixels from the pixels of the second image;

ordering the list of candidate pixels on an epipolar line;

determining a correlation score for each pixel on the list of candidate pixels; and

computing a correlation curve from the correlation scores.

11. A computer-readable medium having computer-executable instructions for performing the method recited in claim 1.

5. (canceled)

7-10. -10. (canceled)

12. A method of stereo matching digital images representing a scene, comprising:

determining possible pixel matches between a target pixel from a first digital image and pixels from a second digital image;

evaluating a reliability of each of the possible pixel matches using a least commitment strategy; and

classifying a certain pixel match based on the reliability of the possible pixel matches.

13. The method of claim 12, wherein the pixels from the second image satisfy an epipolar constraint.

14. The method of claim 13, wherein the pixels from the second image satisfy a disparity gradient limit constraint.

15. The method of claim 12, wherein evaluating the reliability comprises:

predicting a disparity between the target pixel and pixels from the second image; and

estimating an uncertainty of the predicted pixel disparity.

16. The method of claim 12, wherein classifying a certain pixel match comprises:

generating a list of candidate pixels from the pixels of the second image;

ordering the list of candidate pixels on an epipolar line;

determining a correlation score for each pixel on the list of candidate pixels; and

computing a correlation curve from the correlation scores.

17. A computer-readable medium having computer-executable instructions for performing the method recited in claim 12.

18. A method of stereo matching digital images representing a scene, comprising:

determining possible pixel matches between a target pixel from a first digital image and pixels from a second digital image;

evaluating a reliability of each of the possible pixel matches;

classifying a certain pixel match based on the reliability of the possible pixel matches;

generating a list of candidate pixels from the pixels of the second image;

ordering the list of candidate pixels on an epipolar line;

determining a correlation score for each pixel on the list of candidate pixels; and

computing a correlation curve from the correlation scores.

19. The method of claim 18, wherein the pixels from the second image satisfy an epipolar constraint.

20. The method of claim 19, wherein the pixels from the second image satisfy a disparity gradient limit constraint.

21. The method of claim 18, wherein the reliability is evaluated using the least commitment strategy.

22. The method of claim 18, wherein evaluating the reliability comprises:

predicting a disparity between the target pixel and pixels from the second image; and

estimating an uncertainty of the predicted pixel disparity.

23. A computer-readable medium having computer-executable instructions for performing the method recited in claim 18.