Occlusion handling in stereo imaging

• US 8,300,085 B2
• Filed: 08/03/2006
• Issued: 10/30/2012
• Est. Priority Date: 10/14/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Qiong, Deng, Yi, Tang, Xiaoou, Lin, Xueyin
• Primary Examiner(s): Senfi, Behrooz
• Assistant Examiner(s): Kim, Hee-Yong
• Application Number:
  US11/462,342
• Publication Number:
  US 20070086646A1
• Time in Patent Office: 2,280 Days
• Field of Search: 348/42
• US Class Current: 348/42
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• 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 10/755 Deformable models or variational models, e.g. snakes or active contours
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects

Abstract

The handling of occlusions in stereo imaging is disclosed. In one implementation, an association between a discontinuity in one stereo image and an occlusion in a second stereo image is utilized. In such an implementation, the first and second stereo images are segmented. A mapping of a discontinuity within the second stereo image is used to form at least part of a boundary of an occlusion in the first stereo image. The mapped discontinuity is found at a boundary between two segments in the second stereo image, and once mapped, divides a segment in the first stereo image into two patches. An energy calculation is made in an iterative manner, alternating with changes to a solution with the disparities and occlusions of the patches. Upon minimization, disparities and occlusions at the patch and pixel level are available.

Claims

1. One or more computer-readable random access memory devices comprising computer-executable instructions for occlusion handling in stereo imaging, the computer-executable instructions comprising instructions for:

segmenting a first stereo image to result in a coarse segmentation, the first stereo image being either a left or right image;

labeling the coarse segmentation of the first stereo image;

setting an initial estimate of a disparity and occlusions between the first stereo image and a second stereo image, the initial estimate based on the labeling of the coarse segmentation, the second stereo image being the other of the left or the right image;

segmenting the first and second stereo images to result in fine segmentations, the fine segmentations being more granular than the coarse segmentation;

optimizing energy within an alpha-expansion move, the alpha expansion move initially based on the fine segmentations and the initial estimate, and thereafter based on a current solution indicated by disparities and occlusions of the fine segmentations;

pairing two fine segmentations, the pairing performed by;

finding a first fine segmentation within the first stereo image and a second fine segmentation within the second stereo image, wherein a sum of absolute difference (SAD) error between the first and second fine segmentations is minimized;

calculating a measure of smoothness energy between the second fine segmentation and at least one neighbor of the second fine segmentation on the second stereo image, wherein the measure of smoothness energy is based on a difference between labels of two neighboring segments; and

evaluating the SAD error and the measure of smoothness energy to determine if the first fine segmentation within the first stereo image should be paired with the second fine segmentation within the second stereo image; and

obtaining disparities and occlusions of pixels in the matched pair of segmentations within the stereo images based on the energy optimization.

2. The one or more computer-readable random access memory devices of claim 1, wherein setting an initial estimate comprises instructions for:

defining a discrete space within which an optimal solution will be defined, wherein the defining is based on a coarse segmentation of one of the stereo images.

3. The one or more computer-readable random access memory devices of claim 1, wherein segmenting the first and second stereo images comprises instructions for:

mapping a discontinuity within the second stereo image to form at least part of a boundary of an occlusion in the first stereo image, wherein the discontinuity is a boundary between two segments in the second stereo image.

4. The one or more computer-readable random access memory devices of claim 1, wherein segmenting the first and second stereo images comprises instructions for:

mapping a segment in the first stereo image into the second stereo image, wherein the segment mapped into the second stereo image crosses a boundary between two segments within the second stereo image;

mapping the boundary crossed in the second stereo image into the first stereo image; and

dividing the segment in the first stereo image into two segments separated by the mapped boundary.

5. The one or more computer-readable random access memory devices of claim 1, wherein optimizing energy comprises instructions for:

minimize energy using graph-cuts within one alpha expansion framework with a current setting of alpha.

6. The one or more computer-readable random access memory devices of claim 1, wherein optimizing energy comprises instructions for:

constraining the segments formed to be fully occluded or fully visible.

7. A computing system, comprising:

one or more processors;

a memory device, configured for access by the one or more processors; and

processor executable instructions, defined on the memory device and executable by the one or more processors, for;

segmenting a first stereo image to result in a coarse segmentation;

using the coarse segmentation to define a space within which an optimal solution exists;

segmenting the first stereo image and a second stereo image to result in fine segmentations;

mapping discontinuities within one of the fine segmentations to discover disparities and occlusions in the other fine segmentation;

optimizing energy of a current solution within the defined space, wherein the current solution comprises the discovered disparities and occlusions;

pairing two fine segmentations, the pairing performed by;

finding a first fine segmentation within the first stereo image and a second fine segmentation within the second stereo image, wherein a sum of absolute difference (SAD) error between the first and second fine segmentations is minimized;

calculating a measure of smoothness energy between the second fine segmentation and at least one neighbor of the second fine segmentation on the second stereo image, wherein the measure of smoothness energy is based on a difference between labels of two neighboring segments; and

evaluating the SAD error and the measure of smoothness energy to determine if the first fine segmentation within the first stereo image should be paired with the second fine segmentation within the second stereo image; and

obtaining disparities and occlusions of pixels in the pair of segmentations within the stereo images from the energy optimization.

8. The computing system of claim 7, wherein mapping discontinuities comprises instructions for:

forming patches in both of the stereo images, wherein the patches are formed using a relationship between an occlusion in the first stereo image and a discontinuity in the second stereo image.

9. The computing system of claim 8, wherein forming patches comprises instructions for:

mapping a boundary separating two segments on the second stereo image to the first stereo image, wherein the mapped boundary defines at least part of a boundary of an occlusion in the first stereo image and at least part of a boundary of a discontinuity in the second stereo image, and wherein two patches are formed within the first stereo image by the mapping.

10. The computing system of claim 7, wherein mapping discontinuities comprises instructions for:

mapping a segment in the first stereo image into the second stereo image, wherein the segment mapped into the second stereo image crosses a boundary between two segments within the second stereo image;

mapping the boundary crossed in the second stereo image into the first stereo image; and

dividing the segment in the first stereo image into two patches separated by the mapped boundary, wherein each of the two patches is constrained to be fully occluded or fully visible.

11. The computing system of claim 7, wherein optimizing energy of the current solution comprises instructions for:

minimizing energy in an iterative α

-expansion framework, wherein each iteration implements an α

-move of a configuration comprising a labeling result or a solution to an optimization problem, and computes a minimum of the currently implemented α

-expansion framework.

12. The computing system of claim 7 additionally comprising instructions for:

iteratively changing the current solution and optimizing energy until a minimal energy has been found; and

performing an alpha expansion move wherein disparities and occlusions of some fine segmentations are assigned a value α

in an α

-expansion framework.

13. The computing system of claim 12 additionally comprising instructions for:

performing a sequence of α

-expansion moves until a minimal energy for all available α

values has been found; and

obtaining a disparity value, occlusions and patch information for the images upon the minimal energy.

14. The computing system of claim 13, wherein the obtained disparity value and occlusions are based on patches.

15. A computer implemented method for occlusion handling in stereo imaging, comprising:

segmenting a first stereo image to result in a coarse segmentation, the first stereo image being either a left or right image;

labeling the coarse segmentation of the first stereo image;

setting an initial estimate of a disparity and occlusions between the first stereo image and a second stereo image, the initial estimate based on the labeling of the coarse segmentation, the second stereo image being the other of the left or the right image;

segmenting the first and second stereo images to result in fine segmentations, the fine segmentations being more granular than the coarse segmentation;

mapping a portion of a border of a discontinuity in the second stereo image to indicate an occlusion in the first stereo image;

computing an energy level of a current solution comprising occlusions and disparities determined by the mapping, the computing of the energy level based on the initial estimate and the fine segmentations;

optimizing the energy level, initially based on the initial estimate, and thereafter using an α

-expansion framework;

pairing two fine segmentations, the pairing performed by;

finding a first fine segmentation within the first stereo image and a second fine segmentation within the second stereo image, wherein a sum of absolute difference (SAD) error between the first and second fine segmentations is minimized;

calculating a measure of smoothness energy between the second fine segmentation and at least one neighbor of the second fine segmentation on the second stereo image, wherein the measure of smoothness energy is based on a difference between labels of two neighboring segments; and

evaluating the SAD error and the measure of smoothness energy to determine if the first fine segmentation within the first stereo image should be paired with the second fine segmentation within the second stereo image; and

obtaining disparities and occlusions of pixels in the paired fine segmentations based on the optimized energy level.

16. The method of claim 15, wherein the mapping comprises:

mapping a segment in the first stereo image into the second stereo image, wherein the segment mapped into the second stereo image crosses a boundary between two segments within the second stereo image;

mapping the boundary crossed in the second stereo image into the first stereo image; and

dividing the segment in the first stereo image into two patches separated by the mapped boundary.

17. The method of claim 15, wherein optimizing the energy level comprises:

selecting a value from a disparity between the images to be alpha;

optimizing energy in one alpha-expansion move using graph cuts;

comparing optimized energy of different solutions;

replacing a solution depending on the comparison;

checking all alpha values; and

outputting disparities and occlusions of patches.

18. The method of claim 15, wherein the α

-expansion framework computes labels of segments and visibility of each pair of fine segmentations.

19. The method of claim 15, wherein in each iteration of the α

-expansion framework, a local minimum is computed using graph-cuts.

20. The method of claim 15, wherein segmenting the first and the second stereo images results in fine segmentations, and wherein the discontinuity in the second stereo image is based on the segmenting.