Method and apparatus for recovering depth using multi-plane stereo and spatial propagation

• US 7,444,013 B2
• Filed: 08/10/2001
• Issued: 10/28/2008
• Est. Priority Date: 08/10/2001
• Status: Active Grant

• Current Assignee: STMicroelectronics Incorporated (STMicroelectronics NV)
• Original Assignee: STMicroelectronics Incorporated (STMicroelectronics NV)
• Inventors: Chen, George Q.
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): TUCKER, WESLEY J
• Application Number:
  US09/927,558
• Publication Number:
  US 20030072483A1
• Time in Patent Office: 2,636 Days
• Field of Search: 345/420, 345/424, 382/154, 356/611
• US Class Current: 382/154
• CPC Class Codes: G06T 7/596 from three or more stereo images
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image

Abstract

An image processing system recovers 3-D depth information for pixels of a base image representing a view of a scene. The system detects a plurality of pixels in a base image that represents a first view of a scene. The system the determines 3-D depth of the plurality of pixels in the base image by matching correspondence to a plurality of pixels in a plurality of images representing a plurality of views of the scene. The system then traces pixels in a virtual piecewise continuous depth surface by spatial propagation starting from the detected pixels in the base image by using the matching and corresponding plurality of pixels in the plurality of images to create the virtual piecewise continuous depth surface viewed from the base image, each successfully traced pixel being associated with a depth in the scene viewed from the base image.

Claims

1. A method of recovering depth information for pixels of a base image representing a view of a scene, the method comprising the steps of:

detecting a plurality of pixels in a base image that represents a first view of a scene, wherein the first view is one of at least three relative views of a scene;

determining 3-D depth of the plurality of pixels in the base image by contemporaneously matching image features between three or more relative images of a scene by matching correspondence to a plurality of pixels in three or more relative images representing the at least three relative views of the scene, wherein the three or more images are captured relative to each other and are of the same scene, and wherein each of the three or more images includes at least an overlapping portion of the scene relative to each other, wherein the at least three relative views of the scene are situated in a non-linear arrangement relative to each other and are further oriented in non-parallel planes relative to each other; and

tracing pixels in a virtual piecewise continuous depth surface by spatial propagation starting from the detected pixels in the base image by using the matching and corresponding plurality of pixels in the three or more relative images to create the virtual piecewise continuous depth surface viewed from the base image, each successfully traced pixel being associated with a depth in the scene viewed from the base image.

2. The method of claim 1, wherein the step of determining the 3-D depth comprises the steps of:

detecting a plurality of image pixels in a first image corresponding to a first view of a scene;

detecting a plurality of image pixels in at least a second image corresponding to a respective at least a second view of the scene, wherein the at least a second image deviates from the first image as a result of camera relative motion;

determining a first two-view correspondence between the plurality of detected image pixels in the first image and a plurality of detected image pixels in one of the at least a second image resulting in a potential two-view match set of candidate image pixels between the first image and the one of the at least a second image;

concatenating a plurality of two-view match sets to form a first multiple-view potential match set; and

determining a second multiple-view potential match set that is a refinement of the first multiple-view potential match set.

3. The method of claim 2, wherein the second multiple-view potential match set is based at least in part on a least median of squares computation of the reprojection errors related to matched pixels in the first multiple-view potential match set.

4. The method of claim 1, wherein the tracing step comprises the step of:

propagating a front of a virtual piece of a continuous depth surface to at least one neighboring pixel starting from the detected pixels in the base image.

5. The method of claim 4, wherein the tracing step comprises the step of:

determining when a boundary is reached between two propagating fronts of virtual pieces of a continuous depth surface.

6. The method of claim 4, wherein the tracing step comprises the steps of:

comparing the matching costs of the two propagating fronts about the reached boundary; and

stopping the propagation of the front with the higher compared matching cost.

7. The method of claim 1, wherein the tracing step comprises the step of:

propagating a front of a virtual piece of a continuous depth surface to at least one neighboring pixel surrounded by a predefined size window in the continuous depth surface.

8. The method of claim 7, wherein the tracing step comprises the step of:

determining when a boundary is reached between two propagating fronts of virtual pieces of a continuous depth surface.

9. The method of claim 7, wherein the tracing step comprises the steps of:

comparing the matching costs of the two propagating fronts about the reached boundary; and

stopping the propagation of the front with the higher compared matching cost.

10. The method of claim 9, wherein the matching cost is determined by computing the summation of all the normalized cross-correlations between a first image window of a pre-determined size in the base view, and a second image window of the same pre-determined size in one of at least one reference view.

11. The method of claim 10, further comprising a step of:

rectification of at least one pair of images corresponding to the base view of the scene and one of the at least one reference view.

12. An image processing system comprising:

a memory;

a controller/processor electrically coupled to the memory;

an image matching module, electrically coupled to the controller/processor and to the memory, for providing a plurality of seed pixels that represent 3-D depth of the plurality of pixels in the base image view of a scene by contemporaneously matching image features between three or more relative images of a scene by matching correspondence to a plurality of pixels in three or more relative images representing a plurality of relative views of the scene, wherein the three or more relative images are captured relative to each other and are of the same scene, and wherein each of the three or more images includes at least an overlapping portion of the scene relative to each other, wherein the base image view is one of at least three relative views of the scene, the at least three relative views of the scene being situated in a non-linear arrangement and are further oriented in non-parallel planes relative to each other; and

a propagation module, electrically coupled to the controller/processor and to the memory, for tracing pixels in a virtual piecewise continuous depth surface by spatial propagation starting from the provided plurality of seed pixels in the base image by using the matching and corresponding plurality of pixels in the three or more relative images to create the virtual piecewise continuous depth surface viewed from the base image, each successfully traced pixel being associated with a depth in the scene viewed from the base image.

13. The image processing system of claim 12, further comprising at least one camera interface, electrically coupled to the controller/processor, for sending image information from at least one camera to the controller/processor.

14. The image processing system of claim 12, wherein the controller/processor, the memory, the image matching module, and the propagation module, are implemented in at least one of an integrated circuit, a circuit supporting substrate, and a scanner.

15. The image processing system of claim 12, wherein the propagation module is further for determining when a boundary is reached between two propagating fronts of virtual pieces of a continuous depth surface.

16. The image processing system of claim 15, wherein the propagation module is further for

comparing the matching costs of the two propagating fronts about the reached boundary;

and

stopping the propagation of the front with the higher compared matching cost.

17. The image processing system of claim 12, wherein the propagation module is further for propagating a front of a virtual piece of a continuous depth surface to at least one neighboring pixel surrounded by a predefined size window in the continuous depth surface.

18. A non-transistory computer readable medium including computer instructions for a 3-D image reconstruction computer system, the computer instructions comprising instructions for:

detecting a plurality of pixels in a base image that represents a first view of a scene, wherein the first view is one of at least three relative views of a scene;

determining 3-D depth of the plurality of pixels in the base image by contemporaneously matching image features between three or more relative images of a scene by matching correspondence to a plurality of pixels in three or more relative images representing the at least three relative views of the scene, wherein the three or more images are captured relative to each other and are of the same scene, and wherein each of the three or more images includes at least an overlapping portion of the scene relative to each other, wherein the at least three relative views of the scene are situated in a non-linear arrangement relative to each other and are further oriented in non-parallel planes relative to each other; and

tracing pixels in a virtual piecewise continuous depth surface by spatial propagation starting from the detected pixels in the base image by using the matching and corresponding plurality of pixels in the three or more relative images to create the virtual piecewise continuous depth surface viewed from the base image, each successfully traced pixel being associated with a depth in the scene viewed from the base image.

19. The computer readable medium of claim 18, wherein the step of determining the 3-D depth comprises the steps of:

detecting a plurality of image pixels in a first image corresponding to a first view of a scene;

detecting a plurality of image pixels in at least a second image corresponding to a respective at least a second view of the scene, wherein the at least a second image deviates from the first image as a result of camera relative motion;

determining a first two-view correspondence between the plurality of detected image pixels in the first image and a plurality of detected image pixels in one of the at least a second image resulting in a potential two-view match set of candidate image pixels between the first image and the one of the at least a second image;

concatenating a plurality of two-view match sets to form a first multiple-view potential match set; and

determining a second multiple-view potential match set that is a refinement of the first multiple-view potential match set.

20. The computer readable medium of claim 19, wherein the second multiple-view potential match set is based at least in part on a least median of squares computation of the reprojection errors related to matched pixels in the first multiple-view potential match set.

21. The computer readable medium of claim 18, wherein the tracing step comprises the step of:

propagating a front of a virtual piece of a continuous depth surface to at least one neighboring pixel starting from the detected pixels in the base image.

22. The computer readable medium of claim 21, wherein the tracing step comprises the step of:

determining when a boundary is reached between two propagating fronts of virtual pieces of a continuous depth surface.

23. The computer readable medium of claim 21, wherein the tracing step comprises the steps of:

comparing the matching costs of the two propagating fronts about the reached boundary; and

stopping the propagation of the front with the higher compared matching cost.

24. The computer readable medium of claim 18, wherein the tracing step comprises the step of:

propagating a front of a virtual piece of a continuous depth surface to at least one neighboring pixel surrounded by a predefined size window in the continuous depth surface.

25. The computer readable medium of claim 24, wherein the tracing step comprises the step of:

determining when a boundary is reached between two propagating fronts of virtual pieces of a continuous depth surface.

26. The computer readable medium of claim 24, wherein the tracing step comprises the steps of:

comparing the matching costs of the two propagating fronts about the reached boundary; and

stopping the propagation of the front with the higher compared matching cost.

27. The computer readable medium of claim 26, wherein the matching cost is determined by computing a normalized cross-correlation between the windows associated with the two propagating fronts about the reached boundary.

28. The computer readable medium of claim 27, further comprising a step of:

rectification of at least one pair of images corresponding to at least one pair of views of the scene.

29. A method of recovering depth information for pixels of a base image representing a view of a scene, the method comprising the steps of:

capturing a base image representing a view of a scene;

tracing at least one parameter surface associated with the base image, each of the at least one parameter surface traced starting from at least one predetermined seed pixel point associated with the base image;

calculating a derivative of function E(g) with respect to parameter g by using finite difference to minimize the following equation

$E<br><br>\left(g\right)=\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>\left\{1-\underset{\mathrm{\omega <br><br>}}{\mathrm{NCC}}<br><br>\left[I_i<br><br>\left(\stackrel{\_}{u}<br><br>\left(g\right),\stackrel{\_}{v}<br><br>\left(g\right)\right),I_0<br><br>\left(u_j,v_j\right)\right]\right\},$

where

$N<br><br>\underset{\mathrm{\omega <br><br>}}{C}<br><br>C<br><br>\lfloor <br><br>I_i<br><br>\left(\stackrel{\_}{u},\stackrel{\_}{v}\right),I_0<br><br>\left(u_j,v_j\right)\rfloor <br><br>$

is a normalized cross-correlation between I_i(ū

, v) and I₀(u_j, v_j);

 

I_i(ū

, v) is a first window of size ω

×

ω

centered at pixel (ū

, v) in I_i,

 

I₀(u_j, v_j) is a second window of size ω

×

ω

centered at pixel (u_j, v_j) in I₀,

 

I_i is a reference image,

 

I₀ is a base image,

 

(ū

, v) is a pixel point closest to P_i(C₀+gL(u_j, v_j));

 

C₀+gL(u_j, v_j) is a 3-D point that projects to (u_j, v_j) in the base view, and to P_i(C₀+gL(u_j, v_j)) in the i^th reference view;

 

C₀ is the base image camera'"'"'s center of projection;

 

L(u_j, v_j) is the unit vector from C₀ to the point on the image plane that corresponds the pixel (u_j, v_j);

 

g is a depth parameter; and

storing the calculated derivative of the function E(g) in a memory; and

generating a three-dimensional image of at least a portion of the scene using at least the calculated derivative of the function E(g) that has been stored in memory.