Patent Description:
Depth-map estimation is made with a pair of images obtained by two cameras for which precise location in space according to the so-called world coordinate system is known.

A common method for estimating depth associated with a pixel of an image of a first camera is to find a corresponding pixel in an image of a second camera that best matches the pixel of the first image. Such matching is determined using similarity estimators such as a L1 or L2 norm computed between the two pixels.

However, when the similiarity between two pixels is computed using only the color components of the pixels, such as the R,G, B components (for Red Green Blue), the depth estimation is very sensitive to noise.

To overcome this limitation, the similarity between two pixels may be computed using a patch of pixels surrounding the pixel being considered. This technique requires requires much more computation since it requires T<NUM> more computation for a patch of TxT pixels compared to computing similarity between <NUM> pixels.

Anders Olofsson addresses the problem of stereo correspondence between stereoscopic images in a report "Modern Stereo Correspondence Algorithms: Investigations and evaluation". This report provides a survey of stereo algorithms and a comparison between an algorithm relying on local winner-take-all optimization and another algorithm minimizing a global energy function formulated at the pixel level. This report acknowledges that computational complexity is an issue within stereo matching.

This is a critical point for real-time estimation and especially when embedded into mobile devices. Thus, there is a need for a new method for depth-map estimation that allows fast and accurate depth estimation.

A method for depth-map estimation between at least two images respectively captured by at least two cameras is disclosed. The method for depth-map estimation comprises:.

According to the present principle, depth for a pixel in an image is estimated by taking into account local spatial structure surrounding the pixel. Advantageously, local spatial structure descriptors can be determined ahead of depth estimation, for instance at the time images are captured by cameras.

According to an embodiment of the present principle, the number of local spatial structure descriptors obtained is lower than the number of pixels in the patch of pixels surrounding the pixel. According to this embodiment, comparing patches between two pixels necessitates less computation than in the prior art as fewer coefficients are used for describing a patch surrounding a pixel.

According to an embodiment of the present principle, transforming a patch of pixels surrounding each pixel further comprises:.

According to this embodiment, the patch of pixels surrounding each pixel can be described by few components characterizing its correlation with surrounding patches.

According to an embodiment of the present principle, the local spatial structure descriptors are determined from a transformation of the auto-correlation matrice.

According to an embodiment of the present principle, the auto-correlation matrice is <NUM> by <NUM> array of scalars with a null coefficient at the center.

According to an embodiment of the present principle, the local spatial structure descriptors are obtained from the auto-correlation matrice using the following transformation: <MAT> <MAT> with a, b, c, d,e, f, g, h being coefficients of the auto-correlation matrice.

According to another embodiment of the present principle, the patch of pixels is transformed using a Discrete Cosine Transform. Such an embodiment allows to take advantage of the decorrelation feature of the DCT transform which allows to extract the frequencies of the patch surrounding the considered pixel.

According to an embodiment of the present principle, the patch of pixels is a patch of 8x8 pixels.

According to an embodiment of the present principle, the local spatial structure descriptors are selected among the Discrete Cosine Transform coefficients.

It should be noted that a step of obtaining an element/value in the present document can be viewed either as a step of reading such element/value in a memory unit of an electronic device or a step of receiving such element/value from another electronic device via communication means, or also a step of computing or determining such element/value via a processor of an electronic device.

According to another aspect of the disclosure, an apparatus for depth-map estimation between at least two images respectively captured by at least two cameras is disclosed. Such an apparatus comprises:.

According to an embodiment of the present principle, the means for transforming a patch of pixels surrounding each pixel comprises:.

According to another embodiment of the present principle, the patch of pixels is transformed using a Discrete Cosine Transform.

One or more of the present embodiments also provide a computer readable storage medium having stored thereon instructions for depth-map estimation, according to any one of the methods described above. The present embodiments also provide a computer program product including instructions for performing any one of the methods described.

An exemplary method for depth-map estimation is disclosed herein in reference to <FIG>.

Depth estimation is made with a pair of images. The pair of images can be obtained from a stereo camera having a left view and a right view or from an array of cameras, considering at least <NUM> cameras. Depth estimation is made possible if the <NUM> cameras are precisely located in space according to the so-called world coordinate system.

In step <NUM>, the <NUM> cameras are located in space using a camera calibration procedure which for instance uses a chessboard observed at different positions from the <NUM> cameras. Several pictures are taken with the chessboard positioned at different positions from the cameras. On each picture, the 2D coordinate of the corners delimited by <NUM> black and <NUM> white squares of the chessboard are extracted. The 2D coordinates of the corners are associated with the 2D coordinates of the same corners observed by the second camera.

Having all the couple of 2D coordinates of corners observed by the <NUM> cameras and also for the different exposures, it is possible to estimate the position of the cameras according to a world coordinate system. In this system, the center of the entry pupil of the camera i is positioned in space by a translation vector Ti = (X, Y, Z)t, and the optical axis is defined by a 3D rotation matrix Ri. The pose matrix of the camera i is defined by <MAT>. The extrinsic matrix of the camera i is defined by <MAT>. From the camera calibration at step <NUM>, the so-called extrinsic camera parameters (a translation vector T and a rotation matrix R) are deduced. Such extrinsic parameters allow to convert a 3D world coordinate into a 2D camera coordinate.

Now, we describe in reference with <FIG>, a method for estimating depth of a 3D point in space. Let xL(x, y) being the pixel from the left camera which observes the object in space at X(X, Y, Z). OL is the optical center of the left camera. Any object Xi which lies on the line (OL, X) is observed by the left camera at the same pixel xL. On the right camera, object Xi are observed at coordinates xr which all lie on one line on the sensor, the so-called epipolar line.

A common method for estimating the depth associated with a pixel is made using the epipolar line.

One considers one pixel pref(x, y) of the reference camera at pixel coordinate (x, y). The pixel pref is de-projected into the world coordinate system at various distance candidates Zc with the rotation and translation matrix associated with the reference camera. The minimum and maximum values for Zc are selected depending on the nearest and farthest objects lying in the scene. The interval between these two values is cut linearly into N slices which defines the N distance candidate Zc.

The number of slices depends on the desired speed and accuracy of the depth-estimation process. For instance, between <NUM> and <NUM> slices may be used. Several 3D points in the world coordinate system are thus obtained at coordinates Pref(Xc, Yc, Zc). All these 3D points Pref(Xc, Yc, Zc) are all observed by the pixel pref(x, y) in the image of the reference camera.

For instance, a number N of candidates are evaluated. An exemplary method for depth estimation is given in <NPL>. For instance, N is equal to <NUM> for a good depth estimation. The number N is also named the number of slices, as the candidates Zc define planes which cut the 3D space in parallel slices where depth-map is estimated.

The obtained candidates Pref are then projected into the second camera according to the extrinsic and intrasic camera parameters. One deduces N coordinates psec(xzc, yzc) on the second camera which all depends on the distance candidate Zc.

The distance Zpref of the real physical object Pref observed at pixel pref on the reference camera is equal to the distance candidate Zc for which pref(x, y) is the most similar to psec(xzc, yzc). Such similarity may be computed using various estimators. For instance, an L1 norm computed between <NUM> pixels may be used.

If the pixel p being observed is a color pixel defined by <NUM> scalars corresponding to the <NUM> color components Red, Green and Blue (pR, pG, pB). The L1 norm between <NUM> pixels pref(x, y) and psec(xzc, yzc) is defined by sL<NUM>(pref(x, y), psec(xzc,yzc)) = |pref,R(x,y) - psec,R(xzc, yzc)| + |pref,G(x, y) - psec,G(xzc, yzc)| + |pref,B(x, y) - psecB(xzc, yzc)|. From the N candidates psec(xzc,yzc), the pixel having the smallest L1 norm with pref(x, y) is said to observe to same object in space. The estimated depth of the pixel pref is thus the candidate Zc corresponding to the candidate psec(xzc, yzc) having the smallest L1 norm with pref(x, y).

According to another example, an L2 norm computed between <NUM> pixels may be used. The L2 norm is similar to the L1 norm except that the similarity measure is defined by sL<NUM>(pref, psec) = |pref,R - psec,R|<NUM> + |pref,G - psec,G|<NUM> + |pref,B - psec,B|<NUM>. In practice if the similarity is estimated only with the color component of one pixel, the depth estimation is very sensitive to noise. To overcome this limitation the similarity between <NUM> pixels may be computed using a patch of few surrounding pixels. This technique refers to cross-patch depth-estimation.

Obviously, such a method requires much more computation since for each candidate, similarity measure has to be computed between patches of T × T pixels. Therefore, the method requires T<NUM> more computation for a patch of T × T pixels compared to similarity measured between only <NUM> pixels. This is a critical point for real time estimation and especially when embedded into mobile devices.

The similarity operator described above (L1 and L2 norms) may be used for patches surrounding a pixel. The L1 norm computed between <NUM> patches may be computed as follows. Let Pref,T(x, y) being a T by T pixels patch surrounding the pixel pref(x, y) and respectively let Psec,T(xzc, yzc) being a T by T pixels patch surrounding the pixel psec(xzc, yzc). The L1 norm between the <NUM> patches is defined by <MAT>. From the N candidates psec(xzc, yzc), the one having the smallest L1 norm with pref(x, y) is said to observe to same object in space. The corresponding Zc is the depth estimation associated with pixel pref(x, y). Similarity estimators which use patches allow more accurate depth estimation but with a higher computational cost. The use of patches for similarity estimation between the <NUM> pixels (pref and psec), allows to take into account the local spatial structure of the pixels being compared, by computing the similarity measure on the color components of the surrounding pixels. The use of patches prevents for instance to estimate that <NUM> pixels are similar if they have the same color (pref(x, y) ≈ psec(x, y) but having different spatial structure (one pixel is lying on an edge and the other one on a flat area for instance). Only patches permit to discriminate pixels considering the underlying spatial structures around the pixels.

According to the principle disclosed herein, depth-map is estimated taking into account of local spatial structure. According to an embodiment of the present principle, local spatial structure of a pixel is determined ahead of the depth-map estimation by determining characteristics of a patch surrounding the pixel, also called local spatial structure descriptors. Back to <FIG>, in step <NUM>, local spatial structure of each pixel of the <NUM> images is determined. Embodiments for such determination are further discussed in reference with <FIG>. According to the present principle, local spatial structure descriptors are determined for each pixel of the two images, by transforming a patch of T by T pixels surrounding each pixel. According to the present principle, the number L of local spatial structure descriptors determined at step <NUM> from the patch surrounding each pixel is lower than the number of pixels in the patch. In this way, the similarity measure computation necessitates less computation than in the prior art because fewer coefficients are used for describing a patch surrounding a pixel.

For each pixel of the <NUM> images to be compared, the L local structure descriptors determined are stick to the <NUM> scalars corresponding to the <NUM> color components of each pixel. One derives <NUM> new special images where each pixel is made of L+<NUM> components. In step <NUM>, depth is estimated for each pixel pref(x, y) of the reference image in a way similar as the one disclosed above.

More particularly, in step <NUM>, the 2D pixel coordinate pref(x, y) is de-projected into 3D coordinates P(Xc, Yc, Zc) in the world coordinate system for N candidates Zc according to the extrinsic parameters of the reference camera.

In step <NUM>, the N 3D coordinates candidates P(Xc, Yc, Zc) are projected into the 2D coordinates psec(xZc, yZc) of the second camera according to the extrinsic parameter of the second camera.

In step <NUM>, the similarity measure is computed between the reference pixel pref(x, y) and each of the pixel candidate psec(xZc, yZc). The similarity is computed using the L local spatial structure descriptors determined at step <NUM> and the <NUM> color components of the pixels pref(x, y) and psec(xZc, yZc). For instance, if the L1 norm is used, the similarity measure is computed as <MAT> where k ∈ [<NUM>, L + <NUM>] is the is kth component of the pixels, the components of a pixel being given by the <NUM> color components of the pixel and the L local spatial structure descriptors determined at step <NUM>.

In step <NUM>, the similarity measures computed at step <NUM> are compared and the pixel psec(xZc,yZc) that minimizes the similiarity measure is selected as the best candidate. That is the best candidates c is selected if pref(x, y) is the most similar to psec(xZc, yZc). In step <NUM>, the depth associated with the pixel coordinate pref(x, y) is equal to the distance Zc of the best candidate c.

According to the present principle, the method for depth-map estimation allows to describe the patches surrounding the pixels to be compared with few coefficients such that comparing <NUM> patches requires less computation. Furthermore, the local spatial structure of the patches can be estimated per pixel prior to the depth-estimation.

A method for local spatial structure estimation of a pixel is disclosed below in reference with <FIG> according to an embodiment of the present disclosure. According to the embodiment disclosed herein, local spatial structure descriptors are computed for describing a patch of 3x3 pixels P<NUM>(x, y) surrounding the pixel P(x, y) such as disclosed in <FIG>.

The patch P<NUM>(x, y) is characterized by estimating the L1-norm L(i, j) between P<NUM>(x, y) and the <NUM> × <NUM> surrounding patches P<NUM>(x - i - <NUM>,y - j - <NUM>) with (i, j) ∈ [<NUM>,<NUM>]<NUM>. <FIG> illustrates in bolded lines the central patch P<NUM>(x, y) surrounding pixel P(x,y) (in grey on <FIG>), and <FIG> patches P<NUM>(x - <NUM>,y - <NUM>) and P<NUM>(x + <NUM>,y) in dotted lines. In step <NUM>, an auto-correlation matrice L(i, j) is determined between the central patch P<NUM>(x, y) and the surrounding 3x3 patches as follows: <MAT> L(i, j) is a <NUM> by <NUM> array of scalars with a null coefficient in the middle. The <NUM> other coefficients depend on the local spatial structures of the <NUM> × <NUM> pixels around p(x, y). In step <NUM>, <NUM> local spatial structure descriptors are then computed from the auto-correlation matrice. According to the embodiment disclosed herein, the <NUM> coefficients of the auto-correlation matrice are compressed into <NUM> coefficients following the transformation given below: <MAT> where a, b, c, d, e, f, g, h are the <NUM> coefficients of the array L(i, j).

The scalar I represents how the <NUM> pixels are similar: I is close to <NUM> for flat areas, and I has high values for textured areas.

The <NUM> scalars (dx, dy) represent the asymmetry of the array L. The values are close to <NUM> for pixels belonging to flat area. The values become positives and negatives on both side of an edge with an intensity which depends on the contrast of the edge.

The <NUM> scalars (Δx, Δy) represent the orientation of an edge if any.

The <NUM> scalars (I, dx, dy, Δx, Δy) permit to describe the local spatial structure for the pixel p(x, y).

The original images are made of <NUM> scalars per pixel corresponding to the <NUM> color components. With the local spatial structure estimation disclosed above, one adds <NUM> components to describe a pixel. For each pixel of the input image, one forms a new image where each pixels is made of <NUM> components [R; G; B; sII; sddx; sddy; sΔΔx; sΔΔy], where sI, sd, sΔ are <NUM> scale-factors which controls the amplitude of the <NUM> scalars versus the <NUM> color components. A method for local spatial structure estimation of a pixel is disclosed below in reference with <FIG> according to another embodiment of the present disclosure.

According to the embodiment disclosed herein, local spatial structure descriptors are computed for describing a patch of 8x8 pixels P<NUM>(x, y) surrounding the pixel P(x, y) such as disclosed in <FIG>.

In the embodiment disclosed herein, the local spatial descriptor are based on the Discrete Cosine Transform (DCT) computed on a patch of <NUM> × <NUM> pixels P<NUM>(x, y) surrounding a pixel P(x, y) as illustrated in <FIG>. The DCT transform allows to extract the frequencies which lies within a patch of <NUM> by <NUM> pixels. Selecting some coefficients provided by the DCT transform allows to characterize the shape of the patch surrounding the pixel P(x, y). In step <NUM>, DCT transform is applied on the patch P<NUM>(x, y) surrounding the pixel P(x, y). The <NUM> × <NUM> DCT(u, v) coefficients with (u, v) ∈ [<NUM>,<NUM>[<NUM> are computed as follows: <MAT> For each pixel p(x, y), <NUM> values of the DCT(u, v) are obtained.

In step <NUM>, L characteristics associated with the pixel P(x, y) are selected from these <NUM> values. Several selections can be used.

For example, with L = <NUM>, the selected DCT values are: DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), and DCT(<NUM>,<NUM>).

According to another example, with L = <NUM>, the selected DCT values are the coefficients (u, v) such that u + v < <NUM>: DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>)and DCT(<NUM>,<NUM>). According to yet another example, with L = <NUM>, the selected DCT values are the coefficients (u, v) such that u + v < <NUM>: DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>), DCT(<NUM>,<NUM>) and DCT(<NUM>,<NUM>). Using L = <NUM> provides an accurate spatial descriptor with only <NUM> coefficients per pixel compared to the <NUM> values of the DCT.

Claim 1:
A computer-implemented method for depth-map estimation between at least two images respectively captured by at least two cameras, comprising:
- obtaining (<NUM>) extrinsic and intrinsic parameters of the at least two cameras,
- for each pixel of the at least two images, applying a first transform to a patch of pixels surrounding the pixel to obtain (<NUM>) a first set of coefficients representative of a local spatial structure of the patch of pixels, wherein a second transform is applied to the first set of coefficients to compress the first set of coefficients in a second set of coefficients representative of the local spatial structure of the patch of pixels, wherein the patch of pixels surrounding the pixel comprises a first number of pixels, and the second set of coefficients comprises a second number of coefficients that is lower than the first number of pixels of the patch of pixels,
- obtaining (<NUM>) depth for at least one pixel of a first image among the at least two images, among at least two depth candidates, each depth candidate being associated with a corresponding pixel in a second image of the at least two images, said corresponding pixel in the second image being obtained according to the extrinsic and intrinsic parameters, wherein obtaining depth comprises:
- determining (<NUM>) a similarity measure between the at least one pixel of the first image and each corresponding pixel in the second image, the similarity measure taking into account color components and the second set of coefficients of the corresponding pixel and the at least one pixel of the first image,
- selecting (<NUM>) a pixel among the corresponding pixels in the second image that minimizes the similarity measure.