SCREEN SPACE PLANE IDENTIFICATION

• US 20110069870A1
• Filed: 09/21/2009
• Published: 03/24/2011
• Est. Priority Date: 09/21/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Marais, Charles Claudius, Deaguero, Joel
• Granted Patent: US 8,428,340 B2
• Time in Patent Office: Days
• US Class Current: 382/106
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 7/75 involving models

Abstract

A method of finding and defining a plane includes screen-space scanning a plurality of rows of a depth image and interpolating a straight depth line through at least two depth values for each row. A pair of straight boundary lines are then fit to the endpoints of the straight depth lines, and a plane is defined to include these straight boundary lines.

Claims

1. A method of finding and defining a plane, comprising:

scanning in screen space a plurality of rows of a depth image;

identifying a first deepest value in a first region of each row;

identifying a second deepest value in a second region of each row;

interpolating a straight depth line through the first deepest value and the second deepest value for each row;

fitting a first straight boundary line using a subset of first endpoints of the straight depth lines;

fitting a second straight boundary line using a subset of second endpoints of the straight depth lines; and

defining the plane through the first straight boundary line and the second straight boundary line.

2. The method of claim 1, where the depth image is a depth history image.

3. The method of claim 1, where scanning in screen space the plurality of rows of the depth image includes scanning a bottom half of rows constituting the depth image.

4. The method of claim 1, where scanning in screen space the plurality of rows of the depth image includes scanning horizontal rows of the depth image.

5. The method of claim 1, where the first region is a left half of that row and the second region is a right half of that row.

6. The method of claim 1, where each straight depth line is held in a buffer as a plurality of points along that straight depth line.

7. The method of claim 1, where fitting the first straight boundary line and the second straight boundary line respectively includes applying a first-order least-squares line fitting algorithm to the subset of first endpoints and the subset of second endpoints.

8. The method of claim 1, where the first straight boundary line and the second straight boundary line are fit without using a straight depth line if a first endpoint of that straight depth line is not within a predetermined tolerance of a second endpoint of that straight depth line.

9. The method of claim 1, where the first straight boundary line and the second straight boundary line are fit without using a straight depth line if that straight depth line is isolated from other straight depth lines.

10. The method of claim 1, where the first straight boundary line and the second straight boundary line are fit without using a straight depth line if that straight depth line is skewed more than a predetermined amount relative to other straight depth lines.

11. The method of claim 1, where the first straight boundary line and the second straight boundary line are fit without using a straight depth line if a depth of that straight depth line jumps greater than a predetermined amount relative to depths of neighboring straight depth lines.

12. The method of claim 1, further comprising shifting the first straight boundary line and the second straight boundary line into a common plane prior to defining the plane through the first straight boundary line and the second straight boundary line.

13. The method of claim 1, where defining the plane through the first straight boundary line and the second straight boundary line includes defining a vector normal to the plane.

14. The method of claim 1, where defining the plane through the first straight boundary line and the second straight boundary line includes filling a floor buffer with linear interpolations between the first straight boundary line and the second straight boundary line.

15. The method of claim 1, further comprising identifying one or more edges intersecting the plane where depth values in the depth image begin to deviate from depth values defined by the plane.

16. The method of claim 1, where the plane is a floor.

17. A method of defining a plane, comprising:

screen-space scanning a plurality of rows of a depth image;

interpolating a straight depth line through at least two depth values for each row in the plurality of rows of the depth image;

fitting a pair of straight boundary lines to a subset of endpoints of the straight depth lines; and

defining the plane through the pair of straight boundary lines.

18. A computing system, comprising:

a depth camera configured to capture depth information useable to construct a depth image;

a logic subsystem operatively connected to the depth camera; and

a data-holding subsystem holding instructions executable by the logic subsystem to;

scan in screen space a plurality of rows of a depth image;

identify a first deepest value in a first region of each row;

identify a second deepest value in a second region of each row;

interpolate a straight depth line through the first deepest value and the second deepest value for each row;

fit a first straight boundary line using a subset of first endpoints of the straight depth lines;

fit a second straight boundary line using a subset of second endpoints of the straight depth lines; and

define a plane through the first straight boundary line and the second straight boundary line.

19. The computing system of claim 18, where instructions executable to fit the first straight boundary line and the second straight boundary line do not use a straight depth line if a first endpoint of that straight depth line is outside of a predetermined tolerance compared to a second endpoint of that straight depth line.

20. The computing system of claim 18, further comprising instructions executable to shift the first straight boundary line and the second straight boundary line into a common plane prior to defining the plane through the first straight boundary line and the second straight boundary line.