Generation of depth image through interpolation and extrapolation of intermediate images derived from stereo image pair using disparity vector fields

• US 5,530,774 A
• Filed: 03/25/1994
• Issued: 06/25/1996
• Est. Priority Date: 03/25/1994
• Status: Expired due to Term

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Fogel, Sergei V.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US08/218,276
• Time in Patent Office: 823 Days
• Field of Search: 382/1, 382/41, 382/44, 382/45, 382/154, 382/276, 382/293, 382/295, 348/42, 348/46, 348/50, 395/119, 395/127, 354/110, 354/112
• 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/221 using the relative movement between cameras and objects
• CPC Class Codes: H04N 13/261 with monoscopic-to-stereoscopic image conversion
• CPC Class Codes: H04N 2013/0081 Depth or disparity estimation from stereoscopic image signals

Abstract

A depth image is generated from a pair of stereo images by means of a disparity vector field-based digital image processing methodology. Specifically, images corresponding to missing angular views are derived from the stereo image pair based upon an iteratively refined set of disparity vector fields that associate desired missing image locations with the pair of stereo images. For a reduced angular separation between the optically recorded pair of stereo images, the stereo images are employed as the images corresponding to intermediate angular viewing locations, and images corresponding to missing angular views are reconstructed by either digitally interpolating or digitally extrapolating the stereo image pair, depending on whether or not the missing angular view is between the angular views of the stereo image pair or outside the angular views of the stereo image pair. The missing images are then interlaced with the images of the stereo to derive the depth image. A system of nonlinear equations is formed relative to an unknown current estimate of the disparity vector field corresponding to the missing image. This system of nonlinear equations is then linearized from which initial estimates of the disparity vector fields are derived relative to the current estimates of the disparity vector fields. Solutions to the resulting set of linear equations are used to iteratively refine estimates of the disparity vector fields.

Claims

1. A method of generating a depth image of a scene comprising the steps of:

(a) providing first and second digital images of said scene derived at first and second scene observation locations spatially spaced apart from one another;

(b) for a plurality of spatially separated scene observation locations, spaced apart from one another and spaced apart from said first and second scene observation locations and associated with respective missing images of said depth image, generating missing angular digital images of said scene in accordance with an iteratively refined set of disparity vector fields that associate said plurality of spatially separated scene observation locations with said first and second digital images; and

(c) interlacing said missing angular digital images of said scene and said first and second digital images to derive said depth image.

2. A method according to claim 1, wherein step (b) comprises deriving a respective missing angular digital image of said scene, associated with one of said plurality of spatially separated scene observation locations, by either digitally interpolating or digitally extrapolating said first and second digital images, in dependence upon with whether or not the observation location of said missing angular digital image is spatially between said first and second image observation locations or spatially outside said first and second image observation locations.

3. A method according to claim 1, wherein step (a) comprises capturing first and second images, from which said first and second digital images are provided, at respective left and right viewing locations t_L and t_R, that are located in a common image observation plane and are spaced apart from one another along a first axis of a rectangular image viewing coordinate system, where a second axis thereof corresponds to depth into the image, and a third axis thereof is coplanar with said first axis.

4. A method according to claim 3, wherein respective ones t_i of said plurality of spatially separated scene observation locations are located in said common image observation plane.

5. A method according to claim 4, wherein step (b) comprises generating a respective missing angular digital image associated with a respective one t_i of said scene observation locations by deriving a prescribed correspondence between said respective missing angular digital image and said first and second digital images in accordance with a respective intermediate disparity vector field, said respective intermediate disparity vector field having a constant component along said third axis representative of alignment of said missing image with said first and second images, and a variable component along said first axis representative of depths of corresponding points in said scene.

6. A method according to claim 3, wherein said first and second digital images are digitized into first and second multi-banded digital images DI_L and DI_R, respectively, having a fixed number of bands, and wherein the band of each of said first and second multi-banded digital images DI_L and DI_R is comprised of a two-dimensional array of pixels, arrayed in said common image observation plane and having associated pixel values which represent prescribed image parameters taken from a two-dimensional array of points Ω

distributed throughout its associated captured image.

7. A method according to claim 6, wherein said first digital image comprises a plurality of first bands I_L,1, . . . , I_L,B, and said second digital image comprises a plurality of second bands I_R,1, . . . , I_R,B, and wherein step (b) comprises generating a plurality of disparity vector field estimates (U_k, V_k), where k=1, 2, . . . , L-1, L+1, . . . , R-1, R+1, . . . , K, in accordance with partial derivatives of filtered image bands for each image band I_L,1, . . . , I_L,B, I_R,1, . . . , I_R,B and a plurality of filters φ

₁, . . . , φ

_F, through which each band of said first and second images are filtered.

8. A method according to claim 7, wherein step (b) comprises initially setting a coarsest spatial resolution level disparity vector field estimate of a respective missing image to a preselected constant, and thereafter iteratively modifying said coarsest spatial resolution level disparity vector field estimate of said respective missing image until final estimates of disparity vector fields are obtained.

9. A method according to claim 8, wherein step (b) comprises iteratively modifying a disparity vector field estimate of said respective missing image in accordance with a multi-level spatial resolution pyramid, wherein, at each increasingly finer resolution pyramid level, filtered images, their associated spatial partial derivatives and estimates of disparity vector fields corresponding to missing images are defined on subgrids of digital image observation points at increasingly finer degrees of spatial resolution.

10. A method according to claim 9, wherein, in step (b), at a given spatial resolution level, disparity vector fields associated with missing images are defined on a matrix of points Ω

of an image plane comprised of N rows of pixels in a first direction corresponding to said first axis by M columns of pixels in a third direction corresponding to said third axis, and wherein said spatial partial derivatives are taken with respect to said third and first directions.

11. A method according to claim 10, wherein, in step (b), bands of filtered first images, spatial partial derivatives of said bands of filtered first images, bands of filtered second images, and spatial partial derivatives of bands of filtered second images are defined on a common matrix of points Ω

'"'"' in an image plane having a size of N'"'"' rows by M'"'"' columns of pixels.

12. A method according to claim 9, wherein, in step (b), disparity vector fields corresponding to missing images at a respective spatial resolution level are defined by a system of non-linear equations expressed in terms of the respective direction partial derivative variables taken with respect to said third and first axes.

13. A method according to claim 12, wherein, in step (b), for a respective index gε

G specifying a prescribed filter and a particular image band, spatial partial derivatives of a prescribed optical flow function g_t are formed with respect to components of a current estimate of the disparity vector along said third and first axes, corresponding to an index g as defined on a grid Ω

sum, scaled by a prescribed factor, representative of the ratio of the difference between the observation point of a missing image of interest and said first and second scene observation locations spatially separation ratio factor, of spatial partial derivatives of estimated first and second filtered image bands.

14. A method according to claim 13, wherein said prescribed optical flow function g_t is defined, relative to the matrix of viewpoint locations Ω

, as the difference between an estimated left filtered image band and an estimated right filtered image band, as viewed along said first axis.

15. A method according to claim 14, wherein, in step (b), bands of filtered first images, spatial partial derivatives of said bands of filtered first images, bands of filtered second images, and spatial partial derivatives of bands of filtered second images are defined on a common matrix of points Ω

'"'"' in an image plane having a size of N'"'"' rows by M'"'"' columns of pixels.

16. A method according to claim 15, wherein said estimated left and right filtered image bands are defined relative to respective arrays of image points taken from said first and second scene observation locations, respectively, having associated perspective projections on said common image observation plane estimated from a respective missing image viewpoint, said right and left filtered images being interpolated from said common matrix of image points Ω

'"'"'.

17. A method according to claim 16, wherein said respective arrays of image points are defined by respective shifts of each image point of matrix of viewpoint locations Ω

, by an amount corresponding to scaling factors of the estimated disparity vector defined at that grid point.

18. A method according to claim 17, wherein step (b) comprises, for each vector s from a set S specifying a particular direction in said common image observation plane, forming a directional smoothness function (s,∇

u), for a variable component u of the current estimate of the disparity vector field along said first axis, corresponding to the missing image, as a finite difference approximation to the directional derivative of said variable component u of the estimate of the disparity vector field corresponding to the missing image along said first axis, where s denotes a vector on the image plane specifying one of a plurality of different directions in said common image observation plane, and S denotes a set of vectors.

19. A method according to claim 18, wherein said directional smoothness function (s,∇

u) is defined on a rectangular subgrid Ω

_S of said matrix of viewpoint locations Ω

, and wherein each grid point of said rectangular subgrid Ω

_S has a nearest neighbor on the rectangular grid Ω

.

20. A method according to claim 19, wherein, at each grid point of the rectangular subgrid Ω

_s, said directional smoothness function (s, ∇

u) corresponds to the difference between the value of the component u of the current estimate of the disparity vector field corresponding to the missing image at the nearest neighbor, in the direction s, of said grid point and the value of the horizontal component u of the current estimate of the disparity vector field corresponding to the missing image at said grid point.

21. A method according to claim 18, wherein step (b) comprises forming a system of nonlinear equations relative to the unknown current estimate of the disparity vector field corresponding to the missing image by combining said optical flow function g_t and associated spatial partial derivatives g_tu, g_tv, taken along said first and third axes, respectively, for each filter and each image band specified by said index g ε

G, together with said directional smoothness function (s,∇

u) for each image direction.

22. A method according to claim 7, wherein step (b) comprises forming a system of nonlinear equations relative to the unknown current estimate of the disparity vector field corresponding to the missing image, linearizing said system of nonlinear equations from which initial estimates of the disparity vector fields are derived relative to the current estimates of the disparity vector fields, and employing solutions to the resulting set of linear equations to modify current estimates of said disparity vector fields.

23. A method according to claim 22, wherein step (b) further comprises modifying said estimates of disparity vector fields to a prescribed degree of spatial resolution and error and estimating missing images at a plurality of prescribed finest spatial resolution viewpoints, and wherein step (c) comprises interlacing said missing images at said plurality of prescribed finest spatial resolution viewpoints of said scene and said first and second digital images to derive said depth image.

24. A method of generating a depth image of a scene comprising the steps of:

(a) generating respective left and right images of said scene derived at stereo scene observation locations spaced apart from one another;

(b) for a plurality of spatially separated scene observation locations, spaced apart from one another and spaced apart from said stereo scene observation locations, and associated with respective missing images of said depth image, generating missing digital images of said scene in accordance with an iteratively refined set of disparity vector fields that associate said plurality of spatially separated scene observation locations with said left and right images; and

(c) interlacing said missing images of said scene and said left and right images to derive said depth image.

25. A method according to claim 24, wherein step (b) comprises deriving a respective missing image of said scene, associated with one of said plurality of spatially separated scene observation locations, by the interpolation or extrapolation of said left and right images, in dependence upon with whether or not the observation location of said missing image is spatially between said left and right image observation locations or spatially outside said left and right image observation locations.

26. A method according to claim 24, wherein step (a) comprises capturing said left and right images at respective left and right viewing locations t_L and t_R, that are located in a common image observation plane and are spaced apart from one another along a first, horizontal axis of a rectangular image viewing coordinate system, where a second, depth axis thereof corresponds to depth into the image, and a third, vertical axis thereof is coplanar with said first, horizontal axis.

27. A method according to claim 26, wherein respective ones t_i of said plurality of spatially separated scene observation locations are located in said common image observation plane.

28. A method according to claim 27, wherein step (b) comprises generating a respective missing image associated with a respective one t_i of said scene observation locations by deriving a prescribed correspondence between said respective missing image and said left and right images in accordance with a respective intermediate disparity vector field, said respective intermediate disparity vector field having a constant component along said vertical axis representative of alignment of said missing image with said left and right images, and a variable component along said horizontal axis representative of depths of corresponding points in said scene.

29. A method according to claim 28, wherein said left and right images are digitized into left and right multi-banded digital images DI_L and DI_R, respectively, having a fixed number of bands, and wherein the band of each of said left and right multi-banded digital images DI_L and DI_R is comprised of a two-dimensional array of pixels, arrayed in said common image observation plane and having associated pixel values which represent prescribed image parameters taken from a two-dimensional array of points Ω

distributed throughout its associated captured image.

30. A method according to claim 29, wherein said left multi-banded digital image comprises a plurality of left bands I_L.,1, . . . , I_L,B, and said right multi-banded digital image comprises a plurality of right bands I_R,1, . . . , I_R,B, and wherein step (b) comprises generating a plurality of disparity vector field estimates (U_k, V_k), where k=1, 2, . . . , L-1, L+1, . . . , R-1, R+1, . . . , K, in accordance with partial derivatives of filtered image bands for each image band I_L,1, . . . , I_L,B, I_R,1, . . . , I_R,B and a plurality of filters φ

₁, . . . , φ

_F, through which each band of said left and right multi-banded digital images are filtered.

31. A method according to claim 24, wherein step (b) comprises forming a system of nonlinear relationships with regard to an unknown current estimate of the disparity vector field corresponding to the missing image, linearizing said system of nonlinear relationships from which initial estimates of the disparity vector fields are derived relative to the current estimates of the disparity vector fields, and employing solutions to the resulting set of linear relationships to modify current estimates of said disparity vector fields.

32. A method according to claim 31, wherein step (b) further comprises modifying said estimates of disparity vector fields to a prescribed degree of spatial resolution and error and estimating missing images at a plurality of prescribed finest spatial resolution viewpoints, and wherein step (c) comprises interlacing said missing images at said plurality of prescribed finest spatial resolution viewpoints of said scene and said left and right digital images to derive said depth image.

33. A method according to claim 32 wherein step (b) comprises initially setting a coarsest spatial resolution level disparity vector field estimate of a respective missing image to a preselected constant, and thereafter iteratively modifying said coarsest spatial resolution level disparity vector field estimate of said respective missing image until final estimates of disparity vector fields are obtained.

34. A method according to claim 24 wherein step (b) comprises iteratively modifying a disparity vector field estimate of said respective missing images in accordance with a multi-level spatial resolution pyramid, wherein, at each increasingly finer resolution pyramid level, filtered images, their associated spatial partial derivatives and estimates of disparity vector fields corresponding to missing images are defined on subgrids of digital image observation points at increasingly finer degrees of spatial resolution.

35. A method according to claim 34, wherein, in step (b), at a given spatial resolution level, disparity vector fields associated with missing images are defined on a matrix of points of an image plane comprised of plural rows of pixels arranged in a horizontal direction along a horizontal axis, and by multiple columns of pixels arranged in a vertical direction along a vertical axis, and wherein said partial spatial derivatives are taken with respect to said vertical and horizontal directions.

36. A method according to claim 35, wherein, in step (b), disparity vector fields corresponding to missing images at a respective spatial resolution level are defined by a system of non-linear equations expressed in terms of the respective direction partial derivative variables taken with respect to said vertical and horizontal axes.

37. A method according to claim 36, wherein, in step (b), for a respective index specifying a prescribed filter and a particular image band, spatial partial derivatives of a prescribed optical flow function are formed with respect to components of a current estimate of the disparity vector along said vertical and horizontal directions, corresponding to an index defined on a grid sum, scaled by a prescribed factor, representative of the ratio of the difference between the observation point of a missing image of interest and said left and right scene observation locations spatially separation ratio factor, of spatial partial derivatives of estimated left and right filtered image bands.

38. A method according to claim 37, wherein said prescribed optical flow function is defined, relative to said matrix of points of said image plane, in accordance with the difference between an estimated left filtered image band and an estimated right filtered image band, as viewed along said horizontal axis.

39. A system for generating a depth image of a scene comprising:

an image capture apparatus which is operative to capture respective left and right images of said scene at stereo scene observation locations that are spaced apart from one another in a common image plane and to output respective left and right digital images, each of said left and right digital images being comprised of a matrix of multiband pixels encoded to a prescribed digital code width; and

a digital image processor, which is coupled to receive said left and right digital images and generates, for a plurality of spatially separated scene observation locations, spaced apart from one another and spaced apart from said stereo scene observation locations, and associated with respective missing images of said depth image, missing digital images of said scene, by processing said left and right digital images in accordance with an iteratively refined set of disparity vector fields that associate said plurality of spatially separated scene observation locations with said left and right images, and interlaces said missing images of said scene and said left and right images to produce said depth image.

40. A system according to claim 39, wherein said digital image processor is operative to generate a respective missing image of said scene, associated with one of said plurality of spatially separated scene observation locations, by interpolating or extrapolating said left and right images, in dependence upon with whether or not the observation location of said missing image is spatially between said left and right image observation locations or spatially outside said left and right image observation locations.

41. A system according to claim 39, wherein said image capture apparatus is operative to capture said left and right images at respective left and right viewing locations t_L and t_R, that are located in a common image observation plane and are spaced apart from one another along a first, horizontal axis of a rectangular image viewing coordinate system, where a second, depth axis thereof corresponds to depth into the image, and a third, vertical axis thereof is coplanar with said first, horizontal axis.

42. A system according to claim 41, wherein respective ones t_i of said plurality of spatially separated scene observation locations are located in said common image observation plane.

43. A system according to claim 42, wherein said digital image processor is operative to generate a respective missing image associated with a respective one t_i of said scene observation locations by deriving a prescribed correspondence between said respective missing image and said left and right images in accordance with a respective intermediate disparity vector field, said respective intermediate disparity vector field having a constant component along said vertical axis representative of alignment of said missing image with said left and right images, and a variable component along said horizontal axis representative of depths of corresponding points in said scene.

44. A system according to claim 43, wherein said left and right images are digitized into left and right multi-banded digital images DI_L and DI_R, respectively, having a fixed number of bands, and wherein the band of each of said left and right multi-banded digital images DI_L and DI_R is comprised of a two-dimensional array of pixels, arrayed in said common image observation plane and having associated pixel values which represent prescribed image parameters taken from a two-dimensional array of points Ω

distributed throughout its associated captured image.

45. A system according to claim 44, wherein said left digital image comprises a plurality of left bands I_L,1, . . . , I_L,B, and said right digital image comprises a plurality of right bands I_R,1, . . . , I_R,B, and wherein step (b) comprises generating a plurality of disparity vector field estimates (U_k, V_k), where k=1, 2, . . . , L1, L+1, . . . , R-1, R+1, . . . , K, in accordance with partial derivatives of filtered image bands for each image band I_L,1, . . . , I_L,B, I_R,1, . . . , I_R,B and a plurality of filters φ

₁, . . . , φ

_F, through which each band of said left and right digital images are filtered.

46. A system according to claim 39, wherein said digital image processor is operative to generate a system of nonlinear equations relative to an unknown current estimate of the disparity vector field corresponding to the missing image, to linearize said system of nonlinear equations from which initial estimates of the disparity vector fields are derived relative to the current estimates of the disparity vector fields, and to modify current estimates of said disparity vector fields in accordance with solutions to the resulting set of linear equations.

47. A system according to claim 46, wherein said digital image processor is operative to modify said estimates of disparity vector fields to a prescribed degree of spatial resolution and error and estimating missing images at a plurality of prescribed finest spatial resolution viewpoints, and to interlace said missing images at said plurality of prescribed finest spatial resolution viewpoints of said scene with said left and right digital images to derive said depth image.

48. A system according to claim 47, wherein said digital image processor is operative to initially set a coarsest spatial resolution level disparity vector field estimate of a respective missing image to a preselected constant, and thereafter iteratively modify said coarsest spatial resolution level disparity vector field estimate of said respective missing image until final estimates of disparity vector fields are obtained.

49. A system according to claim 39, wherein said digital image processor is operative to iteratively modify a disparity vector field estimate of said respective missing images in accordance with a multi-level spatial resolution pyramid, and wherein, at each increasingly finer resolution pyramid level, filtered images, their associated spatial partial derivatives and estimates of disparity vector fields corresponding to missing images are defined on subgrids of digital image observation points at increasingly finer degrees of spatial resolution.

50. A system according to claim 49, wherein said digital image processor is operative, for a given spatial resolution level, to define disparity vector fields associated with missing images on a matrix of points of an image plane comprised of plural rows of pixels arranged in a horizontal direction along a horizontal axis, and by multiple columns of pixels arranged in a vertical direction along a vertical axis, and wherein said partial spatial derivatives are taken with respect to said vertical and horizontal directions.

51. A system according to claim 50, wherein said digital image processor is operative to define disparity vector fields corresponding to missing images at a respective spatial resolution level by a system of non-linear equations expressed in terms of the respective direction partial derivative variables taken with respect to said vertical and horizontal axes.

52. A system according to claim 51, wherein said digital image processor is operative, for a respective index specifying a prescribed filter and a particular image band, to form spatial partial derivatives of a prescribed optical flow function with respect to components of a current estimate of the disparity vector along said vertical and horizontal directions, corresponding to an index defined on a grid sum, scaled by a prescribed factor, representative of the ratio of the difference between the observation point of a missing image of interest and said left and right scene observation locations spatially separation ratio factor, of spatial partial derivatives of estimated left and right filtered image bands.

53. A system according to claim 52, wherein said prescribed optical flow function is defined in accordance with the difference between an estimated left filtered image band and an estimated right filtered image band, as viewed along said horizontal axis.

54. The system as set forth in claim 39 wherein said digital image processor further includes electronic means for receiving said left and right digital images and providing, in response thereto, a set of multiband pixel electrical signals representative of said multiband pixels, said missing digital images being in the form of missing digital image electrical signals, said processor being responsive to said multiband pixel electrical signals and said missing digital image electrical signals for providing output signals representative of said depth image.