US5917937A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for performing stereo matching to recover depths, colors and opacities of surface elements
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-04-15
•
Granted: 1999-06-29
•
Expires: 2017-04-15
Abstract
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.
Inventors
- 👤 Richard Stephen Szeliski
- 👤 Polina Golland
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:59
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/50; G06T7/55; G06T7/593; G06V; G06V10/00; G06V10/10; H; H04; H04N; H04N13/00; H04N13/10; H04N13/106; H04N13/111; H04N13/117; G06T2207/00; G06T2207/10; G06T2207/10004; G06T2207/10012; G06V2201/00; G06V2201/12; H04N13/15; H04N13/20; H04N13/204; H04N13/243; H04N13/286; H04N13/289; H04N13/296; H04N13/30; H04N13/324; H04N13/366; H04N13/398; H04N2013/0074; H04N2013/0081
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
185 words
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.
Claim 2
Independent Claim
185 words
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.
Claim 3
Dependent Claim
53 words
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.
Claim 4
Dependent Claim
40 words
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.
Claim 5
Dependent Claim
57 words
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.
Claim 6
Dependent Claim
51 words
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.
Claim 7
Dependent Claim
27 words
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.
Claim 8
Dependent Claim
30 words
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.
Claim 9
Dependent Claim
30 words
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.
Claim 10
Dependent Claim
57 words
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.
Claim 11
Dependent Claim
63 words
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.
Claim 12
Dependent Claim
25 words
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.
Claim 13
Dependent Claim
28 words
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.
Claim 14
Dependent Claim
16 words
The method of claim 10 wherein adjusting the computed colors includes using a gradient descent method.
Claim 15
Dependent Claim
19 words
The method of claim 13 wherein adjusting the computed colors and estimated opacities includes using a gradient descent method.
Claim 16
Dependent Claim
33 words
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.
Claim 17
Dependent Claim
24 words
The method of claim 1 including selecting a subset of cells that are likely to lie on a visible surface based on the probabilities.
Claim 18
Dependent Claim
24 words
The method of claim 16 wherein the probabilities are derived from the mean and variance of color samples at each cell in the group.
Claim 19
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps recited in claim 1.
Claim 20
Dependent Claim
18 words
The method of claim 1 wherein the color values, color samples, and computed colors are gray scale values.
Claim 21
Independent Claim
177 words
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.
Claim 22
Independent Claim
177 words
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.
Claim 23
Dependent Claim
13 words
The method of claim 20 wherein the color values are gray scale values.
Claim 24
Dependent Claim
12 words
The method of claim 20 wherein the color values are color triplets.
Claim 25
Dependent Claim
26 words
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.
Claim 26
Dependent Claim
43 words
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.
Claim 27
Dependent Claim
87 words
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.
Claim 28
Independent Claim
283 words
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.
Claim 29
Independent Claim
283 words
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.
Claim 30
Independent Claim
156 words
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.
Claim 31
Independent Claim
156 words
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.
Claim 32
Dependent Claim
36 words
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.
Claim 33
Dependent Claim
48 words
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.
References Cited (Backward Citations)
US4745562A
Cited
US5381518A
Cited
US5309356A
Cited
US5016173A
Cited
US5555352A
Cited
US5179441A
Cited
JPH07332970A
Cited
US5719954A
Cited
US5582173A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-06-28 | 2002-12-28 | 2003-06-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-06-28 | 2006-12-28 | 2007-06-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-06-28 | 2010-12-28 | 2011-06-29 | $7700.00 | Window Closed / Lapsed |