Generating scene reconstructions from images

• US 10,152,828 B2
• Filed: 09/30/2016
• Issued: 12/11/2018
• Est. Priority Date: 09/30/2015
• Status: Active Grant

• Current Assignee: Umap Av Corp.
• Original Assignee: Umap Av Corp.
• Inventors: McCann, Robert M., Vander Jagt, Benjamin J.
• Primary Examiner(s): Kassa, Yosef
• Application Number:
  US15/282,733
• Publication Number:
  US 20170092015A1
• Time in Patent Office: 802 Days
• Field of Search: 382154, 382170, 382171, 382209, 382282, 382284, 382291, 382294, 345419, 345653
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/10021 Stereoscopic video; Stereoscopic image sequence
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/33 using feature-based methods

Abstract

Computer techniques and systems for decomposing a scene into small scene partitions that can be independently solved and merged into a single cohesive scene without loss in reconstruction quality.

Claims

1. A system for reconstructing metric 3D scene geometry, the system comprising:

an image source that provides a set of images of a scene;

a distributed computing platform that is programmed to generate a metric 3D scene geometry from the set of images, the distributed computing platform comprising;

a central computing module that is programmed to coordinate generation of the metric 3D scene geometry on the distributed computing platform, the central computing module comprising;

memory;

one or more interfaces to communicate with other computing modules that are part of the distributed computing platform;

a data storage device storing a first set of instructions;

one or more processors that is programmed to execute the first set of instruction using the memory and the one or more interfaces, causing the one or more processors to perform operations comprising;

identifying a plurality of image features from the set of images;

determining matches between the plurality of image features across the set of images;

generating an image graph based on the set of images and the determined matches, wherein image graph comprises (i) vertices that represent images from the set of images and (ii) edges that connect the vertices and that have weights that are determined based on the matches between the plurality of image features;

decomposing the image graph into a plurality of components that each include a portion of the image graph, wherein each of the plurality of components is generated to have at least a threshold level of quality and overlap with others components;

transmitting at least a portion of the plurality of components to the other computing modules in the distributed computing platform;

receiving a plurality of metric 3D scene geometries from the other computing modules in the distribute computing platform, the plurality of metric 3D scene geometries having been determined in parallel across the other computing modules; and

merging the plurality of metric 3D scene geometries to generate a solution providing the metric 3D scene geometry for the entirety of the image set; and

a plurality of distributed computing modules that are each programmed to process one or more of the plurality of components in parallel, each of the plurality of distributed computing modules comprising;

memory;

one or more interfaces to communicate with, at least, the central computing module;

a data storage device storing a second set of instructions;

one or more processors that is programmed to execute the second set of instruction using the memory and the one or more interfaces, causing the one or more processor to perform operations comprising;

receiving one or more of the plurality of components;

determining one or more metric 3D scene geometries for the one or more plurality of components, each of the one or more metric 3D scene geometries being determined individually; and

transmitting the one or more metric 3D scene geometries to the central computing module.

2. The system of claim 1, wherein the solution is an approximate solution, and

wherein the first instruction set further causes the one or more processors of the central computing unit to perform operations comprising:

modifying the approximate solution to be a final solution achieving a comprehensive metric 3D scene geometry for the entirety of the internet-scale image set.

3. The system of claim 2, wherein the modifying comprises performing a bundle block adjustment on the metric 3D scene geometry to generate the final solution, the bundle block adjustment aligning the set of images with scene points in the metric 3D scene geometry.

4. The system of claim 1, wherein the plurality of image features are identified by performing a scale invariant feature transform technique with regard to the set of images.

5. The system of claim 4, wherein the plurality of image features correspond to groupings of visually distinct pixels.

6. The system of claim 1, wherein

identifying the plurality of image features further comprises

generating description vectors for each of the plurality of image features, each of the description vectors including (i) a description of an image feature, (ii) an image from the image set containing the image feature, and (ii) a location identifier identifying location of the image feature in the image;

and

determining the matches comprises;

comparing the description vectors from the plurality of image features with each other to identify a set of potential feature matches for similar description vectors; and

performing geometric consistency tests on the set of potential feature matches to discard feature matches with location identifiers that do not coincide with each other across different images.

7. The system of claim 1, wherein:

the image graph further comprises edge weights for each of the edges that indicate a degree to which two images connected by an edge include common features,

decomposing the image graph into the plurality of components comprises;

identifying clusters of vertices within the image graph to generate an initial set of components;

removing poor quality components from the initial set of components based on an aggregate of the edge weights within the poor quality components being below a threshold level of quality for the plurality of components;

identifying adjacent components from the initial set of components; and

generating overlap between the adjacent components by adding vertices and edges from one adjacent component to another adjacent component so as to generate overlapping vertices and edges between the adjacent components, the overlapped adjacent components from the initial set of components comprising the plurality of components.

8. The system of claim 1, wherein the operations performed by the one or more processors of the central computing module further comprise:

removing components from the plurality of components that are sufficiently disconnected from others of the plurality of components based on a breadth-first graph traversal technique.

9. The system of claim 1, wherein determining the one or more metric 3D scene geometries comprises:

reconstructing one or more 3D scene geometries individually for each of the one or more of the plurality of components, and

transforming the one or more 3D scene geometries to use a coordinate system based on location information for the set of images, the one or more 3D scene geometries being transformed into the one or more metric 3D scene geometries.

10. The system of claim 9, wherein:

the reconstructing is performed using a structure-from-motion reconstruction technique, and

the coordinate system comprises a global coordinate system that is different from local coordinate systems for each image in the set of images and for each of the plurality of components.

11. The system of claim 1, wherein merging the 3D scene geometries comprises:

generate a merged 3D scene that is initially empty;

for each of the plurality of metric 3D scene geometries;

determining, for each image in the metric 3D scene geometry, whether the camera is already included in the merged 3D scene,

in response to determining that the camera is not present, adding a ground point and a camera into the merged 3D scene for the camera, and

in response to determining that the camera is present, (i) combining a ground point for the camera with redundant ground points in the merged 3D scene and (ii) combining intrinsic and extrinsic properties for the camera with redundant camera information in the merged 3D scene;

removing ground points from the merged 3D scene that have less than a threshold number of corresponding cameras to generate the metric 3D scene geometry.

12. The system of claim 1, wherein the image set is an internet-sized image set.

13. The system of claim 1, wherein the distributed computing platform is a cloud computing system.

14. A method for reconstructing metric 3D scene geometry, the method comprising:

identifying, by a computer system, a plurality of image features from a set of images;

determining, by the computer system, matches between the plurality of image features across the set of images;

generating, by the computer system, an image graph based on the set of images and the determined matches, wherein image graph comprises (i) vertices that represent images from the set of images and (ii) edges that connect the vertices and that have weights that are determined based on the matches between the plurality of image features;

decomposing, by the computer system, the image graph into a plurality of components that each include a portion of the image graph, wherein each of the plurality of components is generated to have at least a threshold level of quality and overlap with others components;

determining, by the computer system, a plurality of metric 3D scene geometries based on individual processing of the plurality of components;

merging, by the computer system, the plurality of metric 3D scene geometries to generate an approximate solution providing metric 3D scene geometry for the entirety of the internet-scale image set; and

modifying, by the computer system, the approximate solution to be a final solution achieving a comprehensive metric 3D scene geometry for the entirety of the internet-scale image set.

15. The method of claim 14, wherein:

the image graph further comprises edge weights for each of the edges that indicate a degree to which two images connected by an edge include common features,

decomposing the image graph into the plurality of components comprises;

identifying clusters of vertices within the image graph to generate an initial set of components;

removing poor quality components from the initial set of components based on an aggregate of the edge weights within the poor quality components being below a threshold level of quality for the plurality of components;

identifying adjacent components from the initial set of components; and

generating overlap between the adjacent components by adding vertices and edges from one adjacent component to another adjacent component so as to generate overlapping vertices and edges between the adjacent components, the overlapped adjacent components from the initial set of components comprising the plurality of components.

16. The method of claim 14, further comprising:

removing components from the plurality of components that are sufficiently disconnected from others of the plurality of components based on a breadth-first graph traversal technique.

17. The method of claim 14, wherein determining the plurality of metric 3D scene geometries comprises:

reconstructing 3D scene geometries individually for each of the plurality of components, and

transforming the 3D scene geometries to use a coordinate system based on location information for the set of images, the 3D scene geometries being transformed into the plurality of metric 3D scene geometries.

18. The method of claim 17, wherein:

the reconstructing is performed using a structure-from-motion reconstruction technique, and

the coordinate system comprises a global coordinate system that is different from local coordinate systems for each image in the set of images and for each of the plurality of components.

19. The method of claim 14, wherein merging the plurality of 3D scene geometries comprises:

generate a merged 3D scene that is initially empty;

for each of the plurality of metric 3D scene geometries;

determining, for each image in the metric 3D scene geometry, whether the camera is already included in the merged 3D scene,

in response to determining that the camera is not present, adding a ground point and a camera into the merged 3D scene for the camera, and

in response to determining that the camera is present, (i) combining a ground point for the camera with redundant ground points in the merged 3D scene and (ii) combining intrinsic and extrinsic properties for the camera with redundant camera information in the merged 3D scene;

removing ground points from the merged 3D scene that have less than a threshold number of corresponding cameras to generate the metric 3D scene geometry.

20. A computer-implemented method for reconstructing metric 3D scene geometry, the method comprising:

identifying, by a computer system, a plurality of geographic regions that are covered by a set of images;

determining, by the computer system, overlapping areas between the plurality of geographic regions;

generating, by the computer system, an image graph based on the set of images and the determined overlapping areas, wherein image graph comprises (i) vertices that represent images from the set of images and (ii) edges that connect the vertices and that have weights that are determined based on the overlapping areas;

decomposing, by the computer system, the image graph into a plurality of components that each include a portion of the image graph, wherein each of the plurality of components is generated to have at least a threshold level of quality and overlap with others components;

determining, by the computer system, a plurality of metric 3D scene geometries based on individual processing of the plurality of components;

merging, by the computer system, the plurality of metric 3D scene geometries to generate an approximate solution providing metric 3D scene geometry for the entirety of the internet-scale image set; and

modifying, by the computer system, the approximate solution to be a final solution achieving a comprehensive metric 3D scene geometry for the entirety of the internet-scale image set.