Method for performing stereo matching to recover depths, colors and opacities of surface elements

• US 5,917,937 A
• Filed: 04/15/1997
• Issued: 06/29/1999
• Est. Priority Date: 04/15/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Szeliski, Richard Stephen, Golland, Polina
• Primary Examiner(s): Chang, Jon
• Assistant Examiner(s): Wu, Jingge
• Application Number:
  US08/843,326
• Time in Patent Office: 805 Days
• Field of Search: 382/154, 382/162, 345/419-424, 345/139, 345/427, 348/42, 348/43
• 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: G06V 10/10 Image acquisition document image scanning and transmission H04N1/00; control of digital cameras H04N23/60
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects
• CPC Class Codes: H04N 13/117 the virtual viewpoint locations being selected by the viewers or determined by viewer tracking
• CPC Class Codes: H04N 13/15 for colour aspects of image signals
• CPC Class Codes: H04N 13/243 using three or more 2D image sensors
• CPC Class Codes: H04N 13/289 Switching between monoscopic and stereoscopic modes
• CPC Class Codes: H04N 13/296 Synchronisation thereof; Control thereof
• CPC Class Codes: H04N 13/324 Colour aspects
• CPC Class Codes: H04N 13/366 using viewer tracking
• CPC Class Codes: H04N 13/398 Synchronisation thereof; Control thereof
• CPC Class Codes: H04N 2013/0081 Depth or disparity estimation from stereoscopic image signals

Abstract

A stereo matching method simultaneously recovers disparities, colors and opacities from input images to reconstruct 3-dimensional surfaces depicted in the input images. The method includes formulating a general disparity space by selecting a projective sampling of a 3D working volume, and then mapping the input images into cells in the general disparity space. After computing statistics on the color samples at each cell, the method computes initial estimates of color and opacity from the statistics (e.g., the mean and variance of the color samples). The method uses opacity to compute visibility and then uses this visibility information to make more accurate estimates by giving samples not visible from a given camera less or no weight. The method uses the initial estimates as input to refining process which tries to match re-projected image layers to the input images.

Claims

1. A method for performing stereo matching comprising:

selecting a general disparity space representing a projective sampling of 3D space, where the projective sampling includes an array of cells in the 3D space;

transforming k input images into a group of cells of the general disparity space, where k is two or more and the input images are comprised of pixels each having color values, such that each cell in the group has a set of color samples, where each color sample in the set originates from a color value of a pixel of one of the input images that maps to the cell;

computing a color for each of the cells in the group based on the set of color samples for the cell;

computing for each of the cells in the group a probability that the cell represents a visible surface element of an object depicted in the input images based on the set of color samples for the cell; and

estimating an opacity for each of the cells in the group based on the probability that the cell represents a visible surface element.

2. The method of claim 1 including aggregating evidence from neighboring cells in the general disparity space to compute confidence values for the cell indicating likelihood that the cell represents a visible surface element of the object depicted in the input images, and

using the confidence values to estimate an opacity for the cell.

3. The method of claim 1 including:

using the estimated opacities to compute a visibility map indicating whether the cells are visible from an input camera corresponding to an input image; and

using the visibility map to refine the computed colors.

4. The method of claim 1 including:

re-projecting the computed colors from general disparity space to input cameras for the input images to compute re-projected images; and

computing error values between the re-projected images and the input images by comparing the color values in the re-projected images with color values in the input images at corresponding pixel locations.

5. The method of claim 4 wherein re-projecting includes:

transforming disparity planes in general disparity space to input cameras, where each of the disparity planes comprises an array of computed colors and estimated opacities; and

compositing the transformed disparity planes into the re-projected images of the input cameras using the estimated opacities.

6. The method of claim 4 including:

adjusting the computed colors for the cells based at least in part on the error values to compute current color values.

7. The method of claim 6 including:

adjusting the estimated opacities for the cells based at least in part on the error values to compute current color values and opacity estimates.

8. The method of claim 6 including:

adjusting the computed colors and estimated opacities based at least in part on the error values and a smoothness constraint on the computed colors.

9. The method of claim 6 including:

re-projecting the current color values from general disparity space to input cameras to compute a new set of re-projected images;

computing new error values between the new set of re-projected images and the input images; and

adjusting the current color values based at least in part on the new error values.

10. The method of claim 7 including:

re-projecting the current color values and opacity estimates from general disparity space to input cameras to compute a new set of re-projected images;

computing new error values between the new set of re-projected images and the input images; and

adjusting the current color values and opacity estimates based at least in art on the new error values.

11. The method of claim 6 including adjusting the computed colors using a cost minimization function based at least in part on minimizing the error values.

12. The method of claim 7 including adjusting the computed colors and estimated opacities using a cost minimization function based at least in part on minimizing the error values.

13. The method of claim 10 wherein adjusting the computed colors includes using a gradient descent method.

14. The method of claim 13 wherein adjusting the computed colors and estimated opacities includes using a gradient descent method.

15. The method of claim 1 wherein the cells are located at (x,y,d) coordinates in the 3D space, and wherein (x,y) represents a rectangular coordinate on a disparity plane d, and d represents disparity.

16. The method of claim 1 including selecting a subset of cells that are likely to lie on a visible surface based on the probabilities.

17. The method of claim 16 wherein the probabilities are derived from the mean and variance of color samples at each cell in the group.

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

19. The method of claim 1 wherein the color values, color samples, and computed colors are gray scale values.

20. A method for performing stereo matching comprising:

selecting a general disparity space representing a projective sampling of 3D space, where the projective sampling includes an array of cells in the 3D space;

transforming k input images from screen coordinates of corresponding input cameras to the general disparity space, where k is two or more and the input images are comprised of pixels each having color values;

from the color values that map from the input images to the cells in the general disparity space, computing probabilities that the cells represent visible surface elements of an object depicted in the input images;

computing initial estimates of color at the cells based on the probabilities;

computing initial estimates of disparities of the visible surface elements based on the probabilities;

computing initial estimates of opacities at the cells based on the probabilities;

using the opacities to compute visibility values for the cells indicating whether the cells are visible with respect to the input cameras; and

revising the initial color and disparity estimates based on the visibility values at the cells.

21. The method of claim 20 wherein the color values are gray scale values.

22. The method of claim 20 wherein the color values are color triplets.

23. The method of claim 20 wherein the probabilities are derived from mean and variance of k color value estimates at the cells in general disparity space.

24. The method of claim 23 wherein estimating the initial disparities includes comparing the variance of cells in an (x,y) column in the general disparity space to assess likelihood that one of the cells in the (x,y) column lies on a visible surface element.

25. The method of claim 20 including:

projecting the initial opacity estimates from the general disparity space to a (u,v,d) space of each of the input cameras;

computing visibilities at the (u,v,d) coordinates of each of the input cameras; and

transforming colors from the input images and the visibilities to the general disparity space such that updated colors in general disparity space have an associated visibility value; and

using the associated visibility values to weight statistics on the updated colors at the cells in the general disparity space.

26. A method for performing stereo matching comprising:

selecting a general disparity space representing a projective sampling of 3D space, where the projective sampling includes an array of cells at (x,y,d) coordinates in the 3D space, and d represents disparity planes comprised of (x,y) coordinates;

transforming k input images from screen coordinates of corresponding input cameras to the general disparity space, where k is two or more and the input images are comprised of pixels each having color values;

from the color values that map from the input images to the cells in the general disparity space, computing mean and variance of the color values at each cell;

computing initial estimates of color at the cells based on the mean at each cell;

computing initial estimates of disparities of visible surface elements based at least in part on the variance;

computing initial estimates of opacities at the cells based at least in part on the variance at each cell;

using the opacities to compute visibility values for the cells indicating whether the cells are visible with respect to the input cameras;

revising the initial color and disparity estimates based on the visibility values; and

refining estimates of color and opacity comprising;

a) transforming current estimates of color and opacity from general disparity space to the (u,v,d) coordinate space of each of the input cameras;

b) compositing the transformed, current estimates of color and opacity into re-projected images for each input camera;

c) comparing the re-projected images with the input images to compute error values for each of the input cameras;

d) adjusting the current estimates of color and opacity based on the error values; and

e) repeating steps a-d to minimize the error values.

27. A method for performing stereo matching comprising:

selecting a general disparity space representing a projective sampling of 3D space, where the projective sampling includes an array of cells in the 3D space;

transforming k input images into the general disparity space, where k is two or more and the input images are comprised of pixels each having color values;

estimating colors for the cells in the general disparity space based on the color values of the pixels from the k input images that map to the cells in the general disparity space;

computing probabilities that the cells represent visible surface elements of an object depicted in the input images; and

estimating opacities for the cells based on the probabilities, wherein the opacities are estimated by assigning totally opaque opacity values to cells that have a color variance below a threshold, and assigning totally transparent opacity values to cells that have a color variance above the threshold.

28. The method of claim 27 wherein the estimated opacities comprise binary opacities for (x,y) columns in the disparity space;

and further including;

passing the binary opacities through a low pass filter to refine the opacity estimates.

29. The method of claim 27 wherein the estimated opacities comprise binary opacities for (x,y) columns in the disparity space;

and further including;

refining the binary opacities by changing at least some of the binary opacities to non-binary opacities based on an intensity gradient of the estimated color values.