Real-time camera tracking using depth maps

• US 8,401,242 B2
• Filed: 01/31/2011
• Issued: 03/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, Kohli, Pushmeet, Fitzgibbon, Andrew, Hodges, Stephen Edward, Butler, David Alexander
• Primary Examiner(s): Fitzpatrick, Atiba O
• Application Number:
  US13/017,587
• Publication Number:
  US 20120196679A1
• Time in Patent Office: 778 Days
• Field of Search: 382100-107, 73488-490, 348154-156, 356 27- 30
• US Class Current: 382/107
• CPC Class Codes: A63F 13/00 Video games, i.e. games using an electronically generated display having two or more dimensions gaming systems which provide a financial reward G07F17/32
• CPC Class Codes: A63F 13/213 comprising photodetecting means, e.g. cameras, photodiodes or infrared cells A63F13/219, A63F13/655 take precedence
• CPC Class Codes: A63F 13/42 by mapping the input signals into game commands, e.g. mapping the displacement of a stylus on a touch screen to the steering angle of a virtual vehicle
• CPC Class Codes: A63F 13/65 automatically by game devices or servers from real world data, e.g. measurement in live racing competition
• CPC Class Codes: A63F 2300/1087 comprising photodetecting means, e.g. a camera
• CPC Class Codes: A63F 2300/69 Involving elements of the real world in the game world, e.g. measurement in live races, real video
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/10048 Infrared image
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/251 involving models
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

Real-time camera tracking using depth maps is described. In an embodiment depth map frames are captured by a mobile depth camera at over 20 frames per second and used to dynamically update in real-time a set of registration parameters which specify how the mobile depth camera has moved. In examples the real-time camera tracking output is used for computer game applications and robotics. In an example, an iterative closest point process is used with projective data association and a point-to-plane error metric in order to compute the updated registration parameters. In an example, a graphics processing unit (GPU) implementation is used to optimize the error metric in real-time. In some embodiments, a dense 3D model of the mobile camera environment is used.

Claims

1. A method of real-time camera tracking comprising:

receiving a sequence of depth map frames from a moving mobile depth camera each depth map frame comprising a depth value at each image element that depth value being related to a distance from the mobile depth camera to a surface in the scene captured by the mobile depth camera;

tracking the position and orientation of the mobile depth camera by computing registration parameters for each depth map frame, those registration parameters being parameters of a transformation for aligning each depth map frame and a preceding depth map frame;

wherein computing the registration parameters comprises using an iterative process to;

identify corresponding points in pairs of depth map frames without computing shapes depicted within the depth map frames and by using a parallel computing unit to optimize an error metric applied to the identified corresponding points such that the error metric is applied to each of the identified corresponding points in parallel.

2. A method as claimed in claim 1 which further comprises receiving input from a second sensor associated with the mobile depth camera and using that to form an initial estimate of the registration parameters, the second sensor being selected from any of:

an orientation sensor, an RGB video camera, a game system, a map of the environment in which the mobile depth camera is moving, a movement sensor, a position sensor.

3. A method as claimed in claim 1 which comprises receiving the sequence of depth map frames at a frame rate of at least 30 frames per second.

4. A method as claimed in claim 1 wherein using the parallel computing unit to optimize an error metric comprises, for each pair of corresponding points, forming a linear system for a numerical least squares optimization and reducing the linear systems to a single 6 by 6 matrix at the parallel computing unit.

5. A method as claimed in claim 4 which comprises passing the 6 by 6 matrix to a central processing unit (CPU) to be solved.

6. A method as claimed in claim 1 which comprises estimating the preceding depth map frame from a dense 3D model of the scene captured by the mobile depth camera.

7. A method as claimed in claim 6 wherein estimating the preceding depth map frame from a dense 3D model of the scene comprises predicting a surface location of a point by projecting a ray into the 3D model and stepping along the ray to find a first positive to negative zero crossing of a surface density function.

8. A method as claimed in claim 1 wherein identifying corresponding points in pairs of depth map frames comprises using a projective data association process whereby an estimated position of the mobile camera is used to project a point from a source depth map frame onto a destination point in a current depth map frame and the projective data association process comprises searching for candidate corresponding points around the destination point.

9. A method as claimed in claim 8 wherein searching for candidate corresponding points comprises taking into account surface normals of the points.

10. A method as claimed in claim 1 wherein optimizing the error metric comprises optimizing a point-to-plane error metric that metric comprising a sum of squared distances from a source point to a plane which contains a destination point and which is oriented approximately perpendicular to a surface normal of the destination point.

11. A method as claimed in claim 1 wherein identifying corresponding points comprises extracting planes from the depth map frames.

12. A method as claimed in claim 1 wherein computing the registration parameters comprises, for each depth map frame, calculating a surface normal for each point and forming a histogram with a plurality of bins for different ranges of surface normal values, and taking a uniform sampling of points across the bins;

and computing the registration parameters using only points from the uniform sampling of points.

13. A real-time camera tracker comprising:

an input arranged to receive a sequence of depth map frames from a moving mobile depth camera each depth map frame comprising a depth value at each image element that depth value being related to a distance from the mobile depth camera to a surface in the scene captured by the mobile depth camera;

a frame alignment engine arranged to track the position and orientation of the mobile depth camera by computing registration parameters for each depth map frame, those registration parameters being parameters of a transformation for aligning each depth map frame and a preceding depth map frame;

the frame alignment engine being arranged to compute the registration parameters using an iterative process to;

identify corresponding points in pairs of depth map frames without computing shapes depicted within the depth map frames;

the frame alignment engine comprising a parallel computing unit arranged to optimize an error metric applied to the identified corresponding points as part of the iterative process such that the error metric is applied to each of the identified corresponding points in parallel at the parallel computing unit.

14. A real-time camera tracker as claimed in claim 13 wherein the graphics processing unit is arranged to optimize the error metric by, for each pair of corresponding points, forming a linear system for a numerical least squares optimization and reducing that linear system to a single 6 by 6 matrix.

15. A real-time camera tracker as claimed in claim 14 wherein the frame alignment engine comprises a central processing unit (CPU) and where the parallel computing unit is arranged to pass the 6 by 6 matrix to the CPU to be solved.

16. A real-time camera tracker as claimed in claim 14 wherein the graphics processing unit stores a dense 3D model of a scene captured by the mobile depth camera and wherein the frame alignment engine is arranged to estimate the preceding depth map frame from the dense 3D model.

20. A game system comprising a mobile infra-red time-of-flight depth camera that uses structured light and a real-time tracker as recited in claim 14 for tracking the mobile depth camera, the mobile depth camera and the real-time tracker being arranged to operate at least 30 frames per second, the game system being arranged to influence the course of a game in relation to the tracking of the mobile depth camera.

17. A method of real-time camera tracking comprising:

receiving a sequence of depth map frames from a moving mobile depth camera each depth map frame comprising a depth value at each image element that depth value being related to a distance from the mobile depth camera to a surface in the scene captured by the mobile depth camera;

tracking the position and orientation of the mobile depth camera by computing registration parameters for each depth map frame, those registration parameters being parameters of a transformation for aligning each depth map frame and a preceding depth map frame, the preceding depth map frame being estimated from a dense 3D model of the scene;

wherein computing the registration parameters comprises using an iterative process to;

identify corresponding points in pairs of depth map frames without computing shapes depicted within the depth map frames and by using a parallel computing unit to optimize an error metric applied to each of the identified corresponding points in parallel at the parallel computing unit.

18. A method as claimed in claim 17 wherein using the parallel computing unit to optimize an error metric comprises, for each pair of corresponding points, forming a linear system for a numerical least squares optimization and reducing that linear system to a single 6 by 6 matrix at the parallel computing unit.

19. A method as claimed in claim 18 which comprises calculating a weight related to the measurement characteristics of the depth camera for each of the corresponding points and using the weights during the process of applying the error metric to the corresponding points.