Viewpoint dependent brick selection for fast volumetric reconstruction

Patent metadata

Field	Value
Publication number	US-10636219-B2
Application number	US-201816229799-A
Country	US
Kind code	B2
Filing date	Dec 21, 2018
Priority date	Dec 22, 2017
Publication date	Apr 28, 2020
Grant date	Apr 28, 2020

Abstract

A method to culling parts of a 3D reconstruction volume is provided. The method makes available to a wide variety of mobile XR applications fresh, accurate and comprehensive 3D reconstruction data with low usage of computational resources and storage spaces. The method includes culling parts of the 3D reconstruction volume against a depth image. The depth image has a plurality of pixels, each of which represents a distance to a surface in a scene. In some embodiments, the method includes culling parts of the 3D reconstruction volume against a frustum. The frustum is derived from a field of view of an image sensor, from which image data to create the 3D reconstruction is obtained.

First claim

What is claimed is:

1. A method of operating a computing system to generate a three-dimensional (3D) reconstruction of a surface in a scene, wherein the computing system represents the scene by a plurality of bricks, each brick comprising a plurality of voxels, the method comprising:
capturing a depth image from a depth sensor worn by a user, the depth image comprising a plurality of pixels, each pixel indicating a distance to a region adjacent the surface in the scene;
conducting a first acceptance test for each of the plurality of bricks, wherein the first acceptance test comprises accepting said brick for further processing based at least in part on determining a pixel of the plurality of pixels intersects said brick; and
generating the 3D reconstruction based on the accepted bricks.

2. The method of claim 1 , further comprising:
conducting a second acceptance test comprising accepting bricks that have a position in front of a background as indicated by pixels in the depth image.

3. The method of claim 2 , wherein:
the second acceptance test comprises accepting bricks that have a position in front of a solid or holey background as indicated by pixels in the depth image.

4. The method of claim 3 , wherein:
generating the 3D reconstruction comprises selecting processing for accepted pixels based on whether the pixel was accepted in the first acceptance test or second acceptance test.

5. The method of claim 2 , wherein:
the first and second acceptance tests are performed in sequence such that the second acceptance test is performed on bricks neither accepted nor rejected in the first acceptance test.

6. The method of claim 1 , wherein:
determining a pixel of the plurality of pixels intersects said brick comprises:
computing a minimum and maximum distance, in coordinates of the depth image, to a bounding box around a projection of the brick into the depth image; and
accepting the brick when, for at least one pixel, the distance value of the pixel is between the minimum and maximum dimensions.

7. The method of claim 1 , further comprising:
conducting a second acceptance test on at least a portion of the bricks not accepted in the first acceptance test, the second acceptance test comprising for each such brick:
accepting the brick if the maximum dimension is less than the distance value for any pixel in the depth image.

8. The method of claim 7 , further comprising:
for each brick accepted in the second acceptance test, selecting processing for the accepted pixel based on whether the minimum dimension is greater than the distance value for any pixel in the depth image.

9. The method of claim 1 , further comprising:
rejecting said brick for further processing when bricks determined to be behind a surface represented in the depth image.

10. The method of claim 1 , wherein the further processing comprises:
updating the plurality of voxels of an accepted brick based on image data of the scene.

11. The method of claim 1 , wherein determining a pixel intersects said brick comprises projecting a brick silhouette of said brick into the depth image, the brick silhouette being a minimum bounding box for said brick projected on the depth image.

12. The method of claim 1 , wherein determining whether each of the portion of the plurality of pixels intersects said brick comprises:
computing minimum and maximum padded values for said brick;
for each of the portion of the plurality of pixels, comparing the distance indicated by said pixel against the minimum and maximum padded values of said brick; and
said pixel is determined as intersecting said brick when the distance indicated by said pixel is between the maximum and the minimum padded values.

13. The method of claim 1 , wherein:
the depth image corresponds to a camera frustum, the camera frustum being in the shape of a 3D trapezoidal prism;
the method comprises culling a portion of the plurality of bricks against the camera frustum so as to produce a reduced set of bricks before conducting the first acceptance test; and
the first acceptance test is conducted against the reduced set of bricks.

14. The method of claim 13 , wherein culling a portion of the plurality of bricks against the camera frustum comprises:
finding a cubic axis-aligned bounding box (AABB) to contain the trapezoidal prism;
conducting a third acceptance test, wherein the third acceptance test comprises:
dividing the AABB into a plurality of sub-AABBs,
determining each of the plurality of sub-AABBs intersects with the trapezoidal prism, and
rejecting bricks corresponding to a sub-AABB as outside the camera frustum when the sub-AABB is determined as not intersecting the camera frustum; and
repeating the third acceptance test until a sub-AABB corresponds to only one brick.

15. The method of claim 14 , wherein determining each of the plurality of sub-AABBs intersects with the trapezoidal prism comprises:
determining at least one corner point of the sub-AABB lies inside each of planes delimiting the camera frustum; and
determining every corner point of the camera frustum lies inside the sub-AABB.

16. A computing device configured to generate a three-dimensional (3D) reconstruction of a portion of a scene, the computing device comprising:
a support member;
a depth sensor coupled to the support member;
an image sensor coupled to the support member;
a central processing unit (CPU) coupled to receive a depth image from the depth sensor and a visual image from the image sensor; and
at least one non-transitory computer-readable medium comprising computer-executable instructions configured for execution on the CPU that, when executed by the CPU, perform a method comprising:
capturing a depth image from the depth sensor, the depth image comprising a representation of regions within the scene adjacent surfaces;
selecting bricks representing portions of the scene based at least in part on an intersection between the bricks and the depth image; and
computing a 3D representation based on portions of the visual image corresponding the selected bricks.

17. The computing device of claim 16 , wherein:
the support member comprises a wearable device; and
the CPU is coupled to the support member.

18. The computing device of claim 17 , wherein the support member comprises a portion of a head-mounted device.

19. The computing device of claim 18 , wherein the head-mounted device further comprises a display.

20. The computing device of claim 16 , wherein:
the image sensor has a field of view defining a frustum within the scene; and
the portion of the scene is defined by the frustum.

Assignees

• Magic Leap Inc

Inventors

• Steinbrücker Frank Thomas
• Molyneaux David Geoffrey
• Wu Zhongle
• Wei Xiaolin
• Min Jianyuan
• Zhang Yifu

Classifications

• G06T19/006 Primary

  Mixed reality (object pose determination, tracking or camera calibration for mixed reality G06T7/00) · CPC title

• G06T2210/12

  Bounding box · CPC title

• G06T7/50

  Depth or shape recovery · CPC title

• G06T7/0002

  Inspection of images, e.g. flaw detection · CPC title

• G06T2207/10028

  Range image; Depth image; 3D point clouds · CPC title