Voxel based ground plane estimation and object segmentation

Patent metadata

Field	Value
Publication number	US-10444759-B2
Application number	US-201715622905-A
Country	US
Kind code	B2
Filing date	Jun 14, 2017
Priority date	Jun 14, 2017
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

Systems, methods, and apparatuses described herein are directed to performing segmentation on voxels representing three-dimensional data to identify static and dynamic objects. LIDAR data may be captured by a perception system for an autonomous vehicle and represented in a voxel space. Operations may include determining a drivable surface by parsing individual voxels to determine an orientation of a surface normal of a planar approximation of the voxelized data relative to a reference direction. Clustering techniques can be used to grow a ground plane including a plurality of locally flat voxels. Ground plane data can be set aside from the voxel space, and the remaining voxels can be clustered to determine objects. Voxel data can be analyzed over time to determine dynamic objects. Segmentation information associated with ground voxels, static object, and dynamic objects can be provided to a tracker and/or planner in conjunction with operating the autonomous vehicle.

First claim

What is claimed is:

1. A system comprising:
one or more processors; and
one or more computer readable storage media communicatively coupled to the one or more processors and storing instructions that are executable by the one or more processors to:
receive a LIDAR dataset representing an environment;
associate the LIDAR dataset with a voxel space, the voxel space including a plurality of voxels;
determine a surface normal vector associated with three-dimensional data associated with an individual voxel of the plurality of voxels;
determine a reference direction, the reference direction corresponding to an orientation of an autonomous vehicle;
determine that the individual voxel is a locally flat voxel based at least in part on the surface normal vector and the reference direction;
determine a ground cluster, the ground cluster representing a drivable surface for the autonomous vehicle, the ground cluster including a plurality of locally flat voxels, the plurality of locally flat voxels including the locally flat voxel;
remove the ground cluster from the voxel space to determine a subset of the voxel space;
cluster adjacent voxels in the subset of the voxel space to determine at least one object;
generate a trajectory for the autonomous vehicle based at least in part on the at least one object; and
navigate the autonomous vehicle based at least in part on the trajectory.

2. The system of claim 1 , wherein the instructions are further executable by the one or more processors to:
determine that an angle formed between the surface normal vector and the reference direction is below a threshold value; and
determine that the individual voxel is the locally flat voxel based at least in part on the angle being below the threshold value.

3. The system of claim 1 , wherein the ground cluster is a first cluster of locally flat voxels, wherein the instructions are further executable by the one or more processors to:
determine, as a first height, an average height of LIDAR data represented in the first cluster;
select, as a first selected voxel, a first voxel in the first cluster of locally flat voxels;
select, as a second selected voxel, a second voxel in a second cluster of locally flat voxels;
determine, as a second height, an average height of data represented in the second selected voxel;
determine a distance between a first representative point associated with the first selected voxel and a second representative point associated with the second selected voxel;
determine a height difference between the first height and the second height;
determine a gradient based at least in part on the distance and the height difference; and
determine an updated ground cluster including the first cluster of locally flat voxels and at least a portion of the second cluster of locally flat voxels based at least in part on the gradient being below a threshold value.

4. The system of claim 1 , wherein the LIDAR dataset is a first LIDAR dataset representing the environment at a first time, and wherein the instructions are further executable by the one or more processors to:
receive a second LIDAR dataset representing the environment at a second time;
associate the second LIDAR dataset with the voxel space;
determine that at least a portion of the first LIDAR dataset represents an object;
determine that at least a portion of the second LIDAR dataset represents the object;
determine, as a difference, that at least a portion of the second LIDAR dataset associated with the object maps to one or more voxels at the second time that were previously unoccupied by the object at the first time; and
determine, based at least in part on the difference, that the object is a dynamic object.

5. The system of claim 1 , wherein the LIDAR dataset is a first LIDAR dataset received at a first time, and wherein the instructions are further executable by the one or more processors to:
determine that the at least one object occupies a first subset of voxels of the voxel space at the first time;
receive a second LIDAR dataset at a second time;
determine that a vector associated with at least one LIDAR data point of the second LIDAR dataset traverses through at least a portion of the first subset of voxels at the second time;
determine that the at least the portion of the first subset of voxels is unoccupied at the second time; and
determine that the at least one object is a dynamic object based at least in part on the at least the portion of the first subset of voxels being unoccupied at the second time.

6. The system of claim 1 , wherein the instructions are further executable by the one or more processors to associate an object identifier with voxels representing the at least one object.

7. The system of claim 1 , wherein the instructions are further executable by the one or more processors to perform an eigenvalue decomposition on a covariance matrix based at least in part on the three-dimensional data associated with the individual voxel to determine the surface normal vector associated with individual voxel.

8. The system of claim 1 , wherein the ground cluster includes at least one voxel proximate to the autonomous vehicle as a seed point for growing the ground cluster.

9. A method comprising:
receiving a voxel space representing a LIDAR dataset associated with an environment;
determining, for a voxel of the voxel space, a surface normal vector associated with three-dimensional data represented by with the voxel;
determining, based at least in part on the surface normal vector associated with the voxel, that the voxel is a locally flat voxel;
determining a ground cluster, the ground cluster including a plurality of locally flat voxels, the plurality of locally flat voxels including the locally flat voxel; and
generating a trajectory for an autonomous vehicle based at least in part on the ground cluster representing a drivable surface for the autonomous vehicle.

10. The method of claim 9 , further comprising:
determining a reference orientation based at least in part on an orientation of the autonomous vehicle;
determining that an angle between the surface normal vector and a vector associated with the reference orientation is within a threshold value; and
determining that the voxel is the locally flat voxel based at least in part on the angle being below the threshold value.

11. The method of claim 9 , wherein the locally flat voxel is a first locally flat voxel, and wherein determining the ground cluster comprises:
selecting, as a seed voxel, the first locally flat voxel, wherein the seed voxel is proximate to the autonomous vehicle;
determining that a second locally flat voxel is adjacent to the seed voxel; and
associating the seed voxel and the second locally flat voxel with the ground cluster.

12. The method of claim 9 , further comprising:
extracting voxels associated with the ground cluster from the voxel space to identify a subset of the voxel space;
clustering a first group of voxels to determine a first object, individual first voxels of the first group of voxels adjacent to at least one other first voxel of the first group of voxels; and
clustering a second group of voxels to determine a second object, individual second voxels of the second group of voxels adjacent to at least one other second voxel of the second group of voxel s;
wherein the individual first voxels are not adjacent to the individual second voxels.

13. The method of claim 9 , further comprising;
determining a first cluster of first locally flat voxels;
determining a second cluster of second locally flat voxels;
determining a height gradient between t

Assignees

• Zoox Inc

Inventors

• Douillard Bertrand Robert
• Das Subhasis
• Wang Zeng
• Anguelov Dragomir Dimitrov
• Levinson Jesse Sol

Classifications

• G01S15/86

  Combinations of sonar systems with lidar systems; Combinations of sonar systems with systems not using wave reflection · CPC title

• G01S17/86

  Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders · CPC title

• G01S17/931

  of land vehicles · CPC title

• G06T17/05

  Geographic models · CPC title

• G06T7/187

  involving region growing; involving region merging; involving connected component labelling · CPC title