System and method for progressive stereo matching of digital images

• US 20050123190A1
• Filed: 12/30/2004
• Published: 06/09/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,272,256 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

Method and a system for correlating pixels between two digital images. In general, the present invention uses a progressive iterative technique that finds generally unambiguous pixel matches by beginning with a few reliable pixel matches and finding progressively more unambiguous pixel matches. Unambiguous pixel matches in the current iteration then are found using the 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 of the present invention that provides a more robust estimate of pixel match reliability. Potential pixel matches found in the search ranges are tested for ambiguity and any unambiguous matches are selected and added to the set of reliable pixel matches. The ambiguity testing includes determining a correlation score for the pixel match and classifying the match based on the correlation score.

Claims

1. A method of correlating pixels between a first and a second digital image, comprising:

defining a first correlation window around a first candidate pixel in the first digital image and a second correlation window around a second candidate pixel in the second digital image;

determining a first epipolar line for the first digital image and a second epipolar line for the second digital image;

rotating the first correlation window to align with the first epipolar line and the second correlation window to align with the second epipolar line; and

determining a correlation between the first candidate pixel contained in the first correlation window and the second candidate pixel contained in the second correlation window.

2. The method of claim 1, wherein rotating the first and second correlation windows is based on an angle between each of the respective epipolar lines.

3. The method of claim 1, wherein one side of at least one of the first and second correlation windows is approximately parallel to its respective epipolar line.

4. The method of claim 1, wherein the first and second correlation windows are rectangular.

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

6. A computer-implemented process for correlating a pixel in a first image to a pixel in a second image, comprising:

a definition step for defining a first correlation window within the first image and a second correlation window within the second image, wherein the first correlation window is aligned with a first epipolar line in the first image;

a rotation step for rotating the second correlation window parallel to a second epipolar line in the second image; and

a computation step for computing a correlation score using the first and second correlation windows representing a correlation between the pixel in the first image and the pixel in the second image.

7. The computer-implemented process as set forth in claim 6, further comprising a first centering step for centering the first correlation window around the pixel in the first image.

8. The computer-implemented process as set forth in claim 7, wherein the first correlation window has a rectangular shape and further comprising a positioning step for positioning one side of the first correlation window parallel to the first epipolar line.

9. The computer-implemented process as set forth in claim 6, further comprising a first construction step for constructing the first epipolar line through the pixel in the first image.

10. The computer-implemented process as set forth in claim 7, further comprising a second centering step for centering the second correlation window around the pixel in the second image.

11. The computer-implemented process as set forth in claim 10, further comprising:

a selection step for selecting a pixel in the first correlation window that is not the pixel in the first image and selecting a pixel in the second correlation window that is not the pixel in the second image;

a first intensity step for computing an intensity of the pixel in the first correlation window; and

a second intensity step for computing an intensity of the pixel in the second correlation window.

12. The computer-implemented process as set forth in claim 11, further comprising a correlation step for computing the correlation score using the intensity of the pixel in the first correlation window and the intensity of the pixel in the second correlation window.

13. The computer-implemented process as set forth in claim 6, further comprising:

a first assignment step for setting the correlation score equal to 1 if the pixel in the first image and the pixel in the second image are identical; and

a second assignment step for setting the correlation score equal to −

1 if the pixel in the first image and the pixel in the second image are different.

14. A computer-readable medium having computer-executable instructions for correlating a pixel m_i in a first image with a pixel m′

_i in a second image, comprising;

selecting a first pixel m in the first image and a second pixel m′

in the second image;

drawing a corresponding first epipolar line/through the first pixel m and a second epipolar line l through the second pixel m and

computing a correlation score between pixel m_i and pixel m′

, using the first pixel m, the second pixel m′

, the first epipolar line/and the second epipolar line l′

.

15. The computer-readable medium of claim 14, further comprising computing an angle, θ

, between the first epipolar line l and the second epipolar line l′

.

16. The computer-readable medium of claim 15, further comprising computing the correlation score using the formula:

m′

_i=R(θ

)(m_i−

m)+m,

wherein R(θ

) is a two-dimensional rotation matrix.

17. The computer-readable medium of claim 16, further comprising:

finding a correlation score equal to 1 if the pixel m_i and the pixel m′

_i are identical; and

finding a correlation score equal to −

1 if the pixel m_i and the pixel m′

_i are completely different.

18. The computer-readable medium of claim 14, further comprising computing an intensity of pixel m′

_i using bilinear interpolation.

19. The computer-readable medium of claim 18, further comprising using four neighboring pixels of the pixel m′

_i to perform the bilinear interpolation.

20. The computer-readable medium of claim 18, further comprising:

defining a first rectangle correlation window centered at the first pixel m;

defining a second rectangle correlation window centered at the second pixel m′

;

rotating the first correlation window such that one side is parallel to the first epipolar line l; and

rotating the second correlation window such that one side is parallel to the second epipolar line l′

.