Three-dimensional environment reconstruction

• US 8,587,583 B2
• Filed: 01/31/2011
• Issued: 11/19/2013
• Est. Priority Date: 01/31/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Newcombe, Richard, Izadi, Shahram, Molyneaux, David, Hilliges, Otmar, Kim, David, Shotton, Jamie Daniel Joseph, Hodges, Stephen Edward, Butler, David Alexander, Fitzgibbon, Andrew, Kohli, Pushmeet
• Primary Examiner(s): Hajnik, Daniel
• Assistant Examiner(s): PRINGLE-PARKER, JASON A
• Application Number:
  US13/017,690
• Publication Number:
  US 20120194516A1
• Time in Patent Office: 1,023 Days
• Field of Search: None
• US Class Current: 345/420
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2200/08 involving all processing steps from image acquisition to 3D model generation

Abstract

Three-dimensional environment reconstruction is described. In an example, a 3D model of a real-world environment is generated in a 3D volume made up of voxels stored on a memory device. The model is built from data describing a camera location and orientation, and a depth image with pixels indicating a distance from the camera to a point in the environment. A separate execution thread is assigned to each voxel in a plane of the volume. Each thread uses the camera location and orientation to determine a corresponding depth image location for its associated voxel, determines a factor relating to the distance between the associated voxel and the point in the environment at the corresponding location, and updates a stored value at the associated voxel using the factor. Each thread iterates through an equivalent voxel in the remaining planes of the volume, repeating the process to update the stored value.

Claims

1. A computer-implemented method of generating a 3D model of a real-world environment, comprising:

creating a three-dimensional volume in a memory device for storing the model, the volume comprising a plurality of voxels;

receiving data describing a location and orientation of a capture device and a depth image of at least a portion of the environment output from the capture device, the depth image comprising a plurality of pixels, each indicating a distance from the capture device to a point in the environment;

assigning a separate execution thread to each voxel in a plane of the volume;

each execution thread using the capture device location and orientation to determine a corresponding location in the depth image for its associated voxel, determining a factor relating to the distance between the associated voxel and the point in the environment at the corresponding location, and updating a stored value at the associated voxel using the factor; and

each execution thread iterating through an equivalent voxel in each remaining plane of the volume and repeating the steps of determining the factor and updating the stored value for each voxel,

wherein the step of updating the stored value at the associated voxel using the factor comprises summing the factor with a previous value stored at the associated voxel or wherein the step of determining the factor comprises calculating a signed distance function between the associated voxel and the point in the environment at the corresponding location, such that if the associated voxel is located at a first side of the point, then the factor has a positive value, and if the associated voxel is located at an opposite side of the point, then the factor has a negative value.

2. A method according to claim 1, further comprising the step of prior to determining the factor, determining whether the corresponding location is within the capture device frustum.

3. A method according to claim 1, wherein the volume is created on the memory device as linear pitched memory.

4. A method according to claim 1, wherein the step of using the capture device location and orientation to determine a corresponding location in the depth image for its associated voxel comprises:

determining the location of the voxel in real-world coordinates;

projecting the real-world coordinates through the capture device'"'"'s projection using the location and orientation determine corresponding coordinates in the depth image for the associated voxel.

5. A method according to claim 1, further comprising the step of generating an image of the model for display on a display device using ray-casting.

6. A method according to claim 5, wherein the step of generating the image of the model comprises:

receiving pose data for a virtual camera;

assigning an execution thread to each image pixel;

each image pixel execution thread determining a path of a ray emanating from the virtual camera through the associated pixel, transforming the path to coordinates in the volume, moving through the volume along the path until a voxel at a surface is detected, and calculating a shade for the associated pixel using the stored value at that voxel.

7. A method according to claim 1, further comprising the step of generating a polygon mesh from the model, and storing the polygon mesh at a storage device.

8. A method according to claim 7, wherein the step of generating a polygon mesh from the model comprises using a marching cubes algorithm to select polygons representing portions of the model.

9. A method according to claim 1, wherein the step of updating the stored value at the associated voxel using the factor comprises summing the factor with the previous value stored at the associated voxel.

10. A method according to claim 9, further comprising the step of determining a weighted average using the stored value and a weighting function relating to the distance of the associated voxel from the capture device.

11. A method according to claim 1, wherein the step of determining the factor comprises calculating the signed distance function between the associated voxel and the point in the environment at the corresponding location, such that if the associated voxel is located at the first side of the point, then the factor has the positive value, and if the associated voxel is located at the opposite side of the point, then the factor has the negative value.

12. A method according to claim 11, wherein the step of determining the factor further comprises:

determining whether the factor is greater than a predefined positive threshold value, and, if so, truncating the factor to the positive threshold value; and

determining whether the factor is less than a predefined negative threshold value, and, if so, truncating the factor to the negative threshold second value.

13. A method according to claim 12, wherein the positive threshold value is +1 and the negative threshold value is −

1.

14. A method according to claim 11, wherein the factor has a value of zero when the associated voxel is coincident with the point in the environment.

15. A method according to claim 1, wherein the data describing the location and orientation of the capture device comprises a six degree-of-freedom pose for the capture device relative to real-world coordinates, and is determined by a transform aligning the depth image to a previously received depth image.

16. A graphics processing system for generating a 3D model of a real-world environment, comprising:

a communication interface arranged to receive data describing a location and orientation of a capture device and a depth image of at least a portion of the environment output from the capture device, the depth image comprising a plurality of pixels, each indicating a distance from the capture device to a point in the environment;

a graphics processing unit arranged to provide concurrent execution of a plurality of threads; and

a memory device,

wherein the graphics processing unit is arranged to;

create a three-dimensional volume in the memory device for storing the model, the volume comprising a plurality of voxels;

assign a separate thread to each voxel in a plane of the volume; and

, for each execution thread, use the capture device location and orientation to determine a corresponding location in the depth image for its associated voxel, determine a factor relating to the distance between the associated voxel and the point in the environment at the corresponding location, update a stored value at the associated voxel using the factor, and iterate through an equivalent voxel in each remaining plane of the volume and repeat the determination of the factor and update of the stored value for each voxel,

wherein the graphics processing unit being arranged to update the stored value at the associated voxel using the factor includes the graphics processing unit being arranged to sum the factor with a previous value stored at the associated voxel or wherein the graphics processing unit being arranged to determine the factor includes the graphics processing unit being arranged to calculate a signed distance function between the associated voxel and the point in the environment at the corresponding location, such that if the associated voxel is located at a first side of the point, then the factor has a positive value, and if the associated voxel is located at an opposite side of the point, then the factor has a negative value.

17. A system according to claim 16, wherein the capture device is a video camera providing a plurality of depth images at a frame rate, and the graphics processing unit is further arranged to repeatedly update the stored value of each voxel in the volume at the frame rate.

18. A system according to claim 16, wherein the capture device comprises a depth camera.

19. A system according to claim 18, wherein the depth camera comprises at least one of:

a structured light emitter;

a time-of-flight camera; and

a stereo camera.

20. One or more computer storage media, the one or more computer storage media being hardware, with device-executable instructions that, when executed by a graphics processing unit, direct the graphics processing unit to perform steps comprising:

creating a three-dimensional volume in a memory device for storing a 3D model of a real-world environment, the volume comprising a plurality of voxels;

receiving data describing a six degrees-of-freedom pose of a depth camera and a depth image of at least a portion of the environment output from the depth camera, the depth image comprising a plurality of pixels, each indicating a distance from the depth camera to a point in the environment;

assigning a separate execution thread to each voxel in a plane of the volume; and

concurrently executing each execution thread on the graphics processing unit, each execution thread performing steps comprising;

using the depth camera pose to determine corresponding coordinates in the depth image for its associated voxel;

calculating a truncated signed distance function from the distance between the associated voxel and the point in the environment at the corresponding coordinates of the depth image;

updating a stored value at the associated voxel using the truncated signed distance function output; and

iterating through an equivalent voxel in each remaining plane of the volume and repeating the steps of determining the factor and updating the stored value for each equivalent voxel.