Combining narrow-baseline and wide-baseline stereo for three-dimensional modeling

• US 8,463,024 B1
• Filed: 05/25/2012
• Issued: 06/11/2013
• Est. Priority Date: 05/25/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Golovinskiy, Aleksey, Lin, Michael Hongmai, Reinhardt, Tilman, Gallup, David
• Primary Examiner(s): Liu, Li
• Application Number:
  US13/480,875
• Time in Patent Office: 382 Days
• Field of Search: None
• US Class Current: 382/154
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 7/596 from three or more stereo images

Abstract

In an embodiment, a method determines a three-dimensional model from a plurality of images taken of a geographic region by one or more cameras from different perspectives. The method includes determining, using a first stereo reconstruction technique: (i) a plurality of three-dimensional candidate surface points from the plurality of images, and (ii) which of the images in the plurality of images view each of the plurality of candidate surface points. The method also includes identifying an empty space between each of the plurality of candidate surface points and each camera model for the respective images determined to view the candidate surface point. The method further includes for each of a plurality of pairs of images from the plurality of images, determining, using a second stereo reconstruction technique, a surface estimate for the pair of images. The method also includes merging the surface estimates to identify a final surface.

Claims

1. A method for determining a three-dimensional model from a plurality of images taken of a geographic region by one or more cameras from different perspectives, comprising:

(a) determining, using a first stereo reconstruction technique;

(i) a plurality of three-dimensional candidate surface points from the plurality of images, and (ii) which of the images in the plurality of images view each of the plurality of candidate surface points;

(b) identifying an empty space between each of the plurality of candidate surface points and each camera model for the respective images determined in (a) to view the candidate surface point;

(c) for each of a plurality of pairs of images from the plurality of images, determining, using a second stereo reconstruction technique, a surface estimate for the pair of images, the determining a surface estimate (c) for the pair of images comprising;

(i) determining a likelihood of each point in a volume of interest being a surface point based on an empty space identified in (b) such that the likelihood of the point being a surface point is less when the point is inside the empty space than when the point is outside the empty space; and

(ii) determining a surface estimate for the pair of images based on the likelihoods determined in (c)(i),

wherein a distance between positions of cameras used to generate the pair of images for the second stereo reconstruction technique is less than a distance between positions of cameras used to generate a pair of images used in the first stereo reconstruction technique; and

(d) merging the surface estimates determined in (c) to identify a final surface.

2. The method of claim 1, wherein the likelihood of each point in the volume of interest being a surface point is represented as a voxel grid, the method further comprising:

(e) determining a shortest distance between each point in the voxel grid and a surface estimate determined in (c)(ii); and

(f) determining signed distance functions for each point in the voxel grid based on the shortest distances determined in (e),

wherein the merging (d) includes merging the signed distance functions determined in (f).

3. The method of claim 2, wherein the determining (a) includes determining a surface normal for each of the plurality of candidate surface points, the method further comprising:

(g) determining a surface estimate for each of the plurality of candidate surface points based on the surface normal; and

(h) determining a signed distance function for each surface estimate determined in (g),

wherein the merging (d) includes merging the signed distance functions determined in (h).

4. The method of claim 1, wherein the determining (a) includes providing visibility rays indicating the empty space as output and the identifying an empty space (b) includes identifying the visibility rays.

5. The method of claim 1, further comprising identifying the volume of interest based on the candidate surface points.

6. The method of claim 1, wherein the determining a surface estimate for the pair of images (c)(ii) includes identifying points having a likelihood of being a surface point that matches a threshold.

7. The method of claim 6, wherein the three-dimensional points included in the empty space do not satisfy the threshold.

8. The method of claim 1, wherein the determining a surface estimate (c)(ii) includes augmenting graph weights such that the surface estimate passes through points that satisfy the threshold and does not pass through the empty space.

9. The method of claim 1, wherein the determining a likelihood of each point in a volume of interest being a surface point (c)(i) includes determining a plane including a point in the volume of interest and projecting images determined to view the point onto the plane.

10. The method of claim 1, wherein the first stereo reconstruction technique is wide-baseline stereo and the second stereo reconstruction technique is narrow-baseline stereo.

11. The method of claim 1, wherein each of the images is an oblique image of a geographic area.

12. The method of claim 1, wherein the final surface is a representation of the geographic area.

13. A system for determining a three-dimensional model from a plurality of images taken of a geographic region by one or more cameras from different perspectives, comprising:

at least one computing device;

a wide-baseline stereo engine, implemented on the at least one computing device, configured to determine;

(i) a plurality of three-dimensional candidate surface points from the plurality of images, and (ii) which of the images in the plurality of images view each of the plurality of candidate surface points;

an empty space identifier, implemented on the at least one computing device, configured to identify an empty space between each of the plurality of candidate surface points and each camera model for the respective images determined by the wide-baseline stereo engine to view the candidate surface point;

a volume of interest identifier, implemented on the at least one computing device, configured to, for each of a plurality of pairs of images from the plurality of images, identify a volume of interest in the pair of images;

a voxel grid, implemented on the at least one computing device, configured to store photo-consistency scores for each point in the volume of interest;

a narrow-baseline stereo engine, implemented on the at least one computing device, configured to, for each of a plurality of pairs of images from the plurality of images;

(i) determine a plane in the volume of interest, (ii) project images determined to view the point onto the plane, (iii) compute the photo-consistency score for each point in the plane based on the projection, wherein a photo-consistency score of a first point inside the empty space is less than a photo-consistency score of a second point outside the empty space, and (iv) determine a surface estimate based on the photo-consistency scores in the voxel grid, wherein the surface estimate includes photo-consistency scores that satisfy a threshold; and

a merging engine, implemented on the at least one computing device, configured to merge the surface estimates determined by the narrow-baseline stereo engine to determine a final surface.

14. The system of claim 13, wherein the final surface is a representation of the geographic area.

15. The system of claim 13, wherein the wide-baseline stereo engine is configured to provide visibility rays indicating the empty space as output, and the empty space identifier is configured to identify the empty space including the visibility rays.

16. The system of claim 13, wherein the merging engine is configured to determine a signed distance function for each narrow-baseline surface estimate, and, when the merging engine merges the surface estimates determined by the narrow-baseline stereo engine, the merging engine merges the signed distance functions for each narrow-baseline surface estimate to determine the final surface.

17. The system of claim 16, wherein the merging engine is configured to extract the final surface as the zero-distance isosurface surface of the signed distance function.

18. The system of claim 13, wherein the wide-baseline stereo engine is configured to determine:

(iii) a surface normal for each of the plurality of three-dimensional candidate surface points, and (iv) a wide-baseline surface estimate for each of the plurality of three-dimensional candidate surface points based on the three-dimensional candidate surface points and surface normals of the three-dimensional candidate surface points; and

when the merging engine merges the surface estimates determined by the narrow-baseline stereo engine to determine a final surface, the merging engine is configured to merge the surface estimates determined by the narrow-baseline stereo engine with the wide-baseline surface estimates determined by the wide-baseline stereo engine.

19. A computer readable storage medium encoded with a computer program, the program comprising instructions that when executed by one or more processors cause the one or more processors to perform operations to:

(a) determine, using a first stereo reconstruction technique;

(i) a plurality of three-dimensional candidate surface points from the plurality of images, and (ii) which of the images in the plurality of images view each of the plurality of candidate surface points;

(b) identify an empty space between each of the plurality of candidate surface points and each camera model for the respective images determined in (a) to view the candidate surface point;

(c) for each of a plurality of pairs of images from the plurality of images, determine, using a second stereo reconstruction technique, a surface estimate for the pair of images, wherein the program comprising instructions that when executed by one or more processors cause the one or more processors to perform operations to determine, using a second stereo reconstruction technique, a surface estimate for the pair of images further cause the one or more processors to perform operations to;

(i) determine a likelihood of each point in a volume of interest being a surface point based on an empty space identified in (b) such that the likelihood of the point being a surface point is less when the point is inside the empty space than when the point is outside the empty space; and

(ii) determine a surface estimate for the pair of images based on the likelihoods determined in (c)(i),

wherein a distance between positions of cameras used to generate the pair of images for the second stereo reconstruction technique is less than a distance between positions of cameras used to generate a pair of images used in the first stereo reconstruction technique; and

(d) merge the surface estimates determined in (c) to identify a final surface.

20. The computer readable storage medium of claim 19, wherein the final surface is a representation of the geographic area.

21. A method for determining a three-dimensional model from a plurality of images taken of a geographic region by one or more cameras from different perspectives, comprising:

(a) determining, using wide-baseline stereo, a plurality of three-dimensional candidate surface points from the plurality of images;

(b) identifying, using wide-baseline stereo, an empty space between each of the plurality of candidate surface points and each camera model for the respective images that view the candidate surface point;

(c) for each of a plurality of pairs of images from the plurality of images, determining, using narrow-baseline stereo, a surface estimate for the pair of images based on the plurality of candidate surface points and the empty space; and

(d) merging the surface estimates determined in (c) to identify a final surface.