Three-dimensional-information reconstructing apparatus, method and program

• US 7,720,277 B2
• Filed: 08/08/2005
• Issued: 05/18/2010
• Est. Priority Date: 08/09/2004
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Hattori, Hiroshi
• Primary Examiner(s): PERUNGAVOOR, SATHYANARAYA V
• Application Number:
  US11/198,215
• Publication Number:
  US 20060050338A1
• Time in Patent Office: 1,744 Days
• Field of Search: 382/154
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 7/593 from stereo images

Abstract

Apparatus includes unit configured to compute parallax search range in (x-y-d) three-dimensional space formed of three variables (x and y providing first point (x, y) on first image and parallax candidate d), similarity unit configured to compute degree-of-similarity C (x, y, d) between point (x, y) and second point (x′, y′) corresponding to point (x, y), using sum of products of brightness levels of corresponding pixel pairs between first window on first image and second window on second image, first window including first point (x, y) second window including second point (x′, y′) and unit configured to compute parallax D between first point (x, y) and second point (x′, y′), based on C (x, y, d), where similarity unit includes unit configured to store sum, which is used for computing C (x, y, d) between new first point on first image and new second point on second image.

Claims

1. A three-dimensional-information reconstructing apparatus comprising:

a camera that captures an object in a three-dimensional space to acquire a first image of the object and a second image of the object;

a search range computing unit configured to compute, based on a geometrical relationship between the object and a reference plane in the three-dimensional space, a parallax search range in a (x-y-d) three-dimensional space formed of three variables, the three variables being an x value and a y value providing a first point (x, y) on the first image and a selected parallax candidate d, the parallax search range being on an epipolar line and a space on and above the reference plane and corresponding to a real space in which the object exists;

a similarity estimator which estimates, for each of parallax candidates in the parallax search range, a degree-of-similarity C (x, y, d) between the first point (x, y) and a second point (x′

, y′

) on the second image, the second point (x′

, y′

) corresponding to the first point (x, y), the degree-of-similarity C (x, y, d) being based on a sum of products of brightness levels of corresponding pixel pairs between a first window on the first image and a second window on the second image, the first window including the first point (x, y), the second window including the second point (x′

, y′

) and having a size identical to a size of the first window;

a parallax computing unit configured to compute a parallax D between the first point (x, y) on the first image and the second point (x′

, y′

) on the second image, based on the degree-of-similarity C (x, y, d); and

a window adjusting unit configured to adjust at least one of the size and a configuration of the first window and the second window, used for computing the degree-of-similarity C (x, y, d), in units of first points (x, y) on the first image, based on the computed parallax D, and wherein the similarity estimator re-computes the degree-of-similarity C (x, y, d) using the adjusted windows,

wherein the similarity estimator includes a storage unit configured to store the sum, the stored sum being used for computing a degree-of-similarity C (x, y, d) between a new first point on the first image and a new second point on the second image corresponding to the new first point.

2. The apparatus according to claim 1, wherein the search range computing unit sets, as the parallax search range, a space included in two spaces and containing the object, the two spaces being formed by dividing the (x-y-d) three-dimensional space along the reference plane.

3. The apparatus according to claim 1, wherein the search range computing unit computes an equation of the reference plane, based on a feature of the reference plane in the first image and the second image, and determines the parallax search range using the computed equation.

4. The apparatus according to claim 1, wherein the parallax computing unit computes, as the parallax D, the parallax candidate d when the parallax candidate d maximizes the degree-of-similarity C (x, y, d).

5. The apparatus according to claim 1, further comprising:

a search accuracy computing unit configured to compute accuracy of a parallax search in the (x-y-d) three-dimensional space, based on three-dimensional information reconstructed from the first image and the second image.

6. The apparatus according to claim 1, wherein the degree-of-similarity C (x, y, d) is obtained by a normalized cross-correlation between the first window and the second window.

7. The apparatus according to claim 1, wherein the degree-of-similarity C (x, y, d) is obtained by a sum of absolute values of differences in brightness between corresponding pixel pairs between the first window and the second window.

8. The apparatus according to claim 1, wherein the degree-of-similarity C (x, y, d) is obtained by a sum of squares of differences in brightness between corresponding pixel pairs between the first window and the second window.

9. The apparatus according to claim 1, wherein the window adjusting unit adjusts at least one of the size and a configuration of the first window and the second window in units of first points (x, y) on the first image, based on variation in the parallax D between first points included in a certain range defined on the first image with respect to each of the first points (x, y).

10. The apparatus according to claim 1, wherein the window adjusting unit acquires a depth in a three-dimensional space corresponding to each of first points (x, y) on the first image, based on the computed parallax D, and adjusts at least one of the size and a configuration of the first window and the second window in units of first points (x, y) on the first image, based on variation in the depth between first points included in a certain range defined on the first image with respect to each of the first point (x, y).

11. A three-dimensional-information reconstructing processor implemented method comprising:

capturing an object in a three-dimensional space to acquire a first image of the object and a second image of the object;

computing, based on a geometrical relationship between the object and a reference plane in the three-dimensional space, a parallax search range in a (x-y-d) three-dimensional space formed of three variables, the three variables being an x value and a y value providing a first point (x, y) on the first image and a selected parallax candidate d, the parallax search range being on an epipolar line and a space on and above the reference plane and corresponding to a real space in which the object exists;

estimating, for each of parallax candidates in the parallax search range, a degree-of-similarity C (x, y, d) between the first point (x, y) and a second point (x′

, y′

) corresponding to the first point (x, y), the degree-of-similarity C (x, y, d) being based on a sum of products of brightness levels of corresponding pixel pairs between a first window on the first image and a second window on the second image, the first window including the first point (x, y), the second window including the second point (x′

, y′

) and having a size identical to a size of the first window;

computing a parallax D between the first point (x, y) on the first image and the second point (x′

, y′

) on the second image, based on the degree-of-similarity C (x, y, d); and

adjusting at least one of the size and a configuration of the first window and the second window, used for computing the degree-of-similarity C (x, y, d), in units of first points (x, y) on the first image, based on the computed parallax D, and wherein the similarity estimator re-computes the degree-of-similarity C (x, y, d) using the adjusted windows,

wherein computing the degree-of-similarity includes storing the sum, the stored sum being used for computing a degree-of-similarity C (x, y, d) between a new first point on the first image and a new second point on the second image corresponding to the new first point.

12. A three-dimensional-information reconstructing program stored in a medium which is read by a computer, the program comprising instructions of:

capturing an object in a three-dimensional space to acquire a first image of the object and second image of the object;

computing, based on a geometrical relationship between the object and a reference plane in the three-dimensional space, a parallax search range in a (x-y-d) three-dimensional space formed of three variables, the three variables being an x value and a y value providing a first point (x, y) on the first image and a selected parallax candidate d, the parallax search range being on an epipolar line and a space on and above the reference plane and corresponding to a real space in which the object exists;

estimating, for each of parallax candidates in the parallax search range, a degree-of-similarity C (x, y, d) between the first point (x, y) and a second point (x′

, y′

) on the second image, the second point (x′

, y′

) corresponding to the first point (x, y), the degree-of-similarity C (x, y, d) being based on a sum of products of brightness levels of corresponding pixel pairs between a first window on the first image and a second window on the second image, the first window including first point (x, y), the second window including the second point (x′

, y′

) and having a size identical to a size of the first window;

computing a parallax D between the first point (x, y) on the first image and the second point (x′

, y′

) on the second image, based on the degree-of-similarity C (x, y, d); and

adjusting at least one of the size and a configuration of the first window and the second window, used for computing the degree-of-similarity C (x, y, d), in units of first points (x, y) on the first image, based on the computed parallax D, and wherein the similarity estimator re-computes the degree-of-similarity C (x, y, d) using the adjusted windows,

wherein the degree-of-similarity computing instruction includes an instruction of instructing the computer to store the sum, the stored sum being used for computing a degree-of-similarity C (x, y, d) between a new first point on the first image and a new second point on the second image corresponding to the new first point.