Method, system and apparatus for object detection in point clouds

Patent metadata

Field	Value
Publication number	US-11010920-B2
Application number	US-201816153064-A
Country	US
Kind code	B2
Filing date	Oct 5, 2018
Priority date	Oct 5, 2018
Publication date	May 18, 2021
Grant date	May 18, 2021

Abstract

A method of detecting objects on a support structure includes: obtaining a point cloud of the support structure supporting an object; obtaining a position of a back of the support structure in the point cloud; discarding a portion of the point cloud based on the position of the back of the support structure; generating a three-dimensional occupancy grid from the point cloud, the occupancy grid having a plurality of cells each indicating whether the cell is one of occupied and unoccupied; identifying a contiguous region of occupied cells in the occupancy grid corresponding to the object; and generating a detected object position based on the contiguous region.

First claim

The invention claimed is:

1. A method of detecting objects on a support structure, the method comprising:
obtaining a point cloud of the support structure supporting an object;
obtaining a position of a back of the support structure in the point cloud by obtaining a plane definition corresponding to a front of the support structure;
discarding a portion of the point cloud based on the position of the back of the support structure;
generating a three-dimensional occupancy grid from the point cloud, the occupancy grid having a plurality of cells each indicating whether the cell is one of occupied and unoccupied, wherein generating the three-dimensional occupancy grid comprises, for each position on the plane definition: (a) determining a first depth of a point nearest to the plane definition, and (b) storing, in a cell of the occupancy grid containing the point, an occupied indicator and storing, in each cell of the occupancy grid having the position on the plane definition and a greater depth than the first depth, an unoccupied indicator;
identifying a contiguous region of occupied cells in the occupancy grid corresponding to the object; and
generating a detected object position based on the contiguous region.

2. The method of claim 1 , wherein the detected object position comprises a bounding box.

3. The method of claim 1 , wherein obtaining the position of the back of the support structure further includes obtaining a depth from the plane definition to the back of the support structure.

4. The method of claim 3 , wherein discarding the portion of the point cloud based on the position of the back of the support structure includes discarding points within a threshold depth matching the depth from the plane definition to the back of the support structure.

5. The method of claim 3 , wherein the point cloud defines a plurality of points according to a common frame of reference; the method further comprising:
before discarding the portion, transforming the points from the common frame of reference to a secondary frame of reference defining, for each point, a position on the plane definition and a depth orthogonal to the plane definition.

6. The method of claim 1 , wherein identifying the contiguous region comprises:
in a first set of cells having a first common depth, identifying a first contiguous sub-region;
in a second set of cells having a second common depth, identifying a second contiguous sub-region;
determining whether to merge the first and second contiguous sub-regions; and
when the determination is affirmative, merging the first and second contiguous sub-regions to generate the contiguous region.

7. The method of claim 6 , wherein determining whether to merge the first and second contiguous sub-regions comprises: determining whether a first position on the plane definition of the first contiguous sub-region abuts a second position on the plane definition of the second contiguous sub-region.

8. The method of claim 1 , further comprising:
prior to identifying the contiguous region, discarding a portion of the cells corresponding to support structure edge positions.

9. A computing device for detecting objects on a support structure, comprising:
a memory storing (i) a point cloud of the support structure supporting an object, and (ii) a position of a back of the support structure in the point cloud;
an imaging controller connected to the memory, the imaging controller configured to:
retrieve, from the memory, the point cloud;
obtain the position of the back of the support structure in the point cloud by retrieving from the memory a plane definition corresponding to a front of the support structure;
discard a portion of the point cloud based on the position of the back of the support structure;

generate a three-dimensional occupancy grid from the point cloud, the occupancy grid having a plurality of cells each indicating whether the cell is one of occupied and unoccupied, wherein the imaging controller is further configured to generate the occupancy grid by, for each position on the plane definition: (a) determining a first depth of a point nearest to the plane definition, and (b) storing, in a cell of the occupancy grid containing the point, an occupied indicator and storing, in each cell of the occupancy grid having the position on the plane definition and a greater depth than the first depth, an unoccupied indicator;
identify a contiguous region of occupied cells in the occupancy grid corresponding to the object; and
generate a detected object position based on the contiguous region.

10. The computing device of claim 9 , wherein the detected object position comprises a bounding box.

11. The computing device of claim 9 , wherein the imaging controller is further configured, to obtain the position of the back of the support structure, to:
retrieve from the memory a depth from the plane definition to the back of the support structure.

12. The computing device of claim 11 , wherein the imaging controller is further configured, to discard the portion of the point cloud based on the position of the back of the support structure, to: discard points within a threshold depth matching the depth from the plane definition to the back of the support structure.

13. The computing device of claim 11 , wherein the point cloud defines a plurality of points according to a common frame of reference; and wherein the imaging controller is further configured to:
before discarding the portion, transform the points from the common frame of reference to a secondary frame of reference defining, for each point, a position on the plane definition and a depth orthogonal to the plane definition.

14. The computing device of claim 9 , wherein the imaging controller is further configured, to identify the contiguous region, to:
in a first set of cells having a first common depth, identify a first contiguous sub-region;
in a second set of cells having a second common depth, identify a second contiguous sub-region;
determine whether to merge the first and second contiguous sub-regions; and
when the determination is affirmative, merge the first and second contiguous sub-regions to generate the contiguous region.

15. The computing device of claim 14 , wherein the imaging controller is further configured, to determine whether to merge the first and second contiguous sub-regions, to:
determine whether a first position on the plane definition of the first contiguous sub-region abuts a second position on the plane definition of the second contiguous sub-region.

16. The computing device of claim 9 , wherein the imaging controller is further configured to:
prior to identifying the contiguous region, discard a portion of the cells corresponding to support structure edge positions.

17. A non-transitory computer-readable medium storing a plurality of computer-readable instructions executable by a processor of a computing device, wherein execution of the instructions configures the computing device to:
obtain a point cloud of a support structure supporting an object;
obtain a position of a back of the support structure in the point cloud by obtaining a plane definition corresponding to a front of the support structure;
discard a portion of the point cloud based on the position of the back of the support structure;
generate a three-dimensional occupancy grid from the point cloud, the occupancy grid having a plurality of cells each indicating whether the cell is one of occupied and unoccupied, wherein the occupancy grid is generated by, for each position on the plane definition:

Assignees

• Zebra Tech Corp

Inventors

• Yu Yuanhao
• Phan Raymond

Classifications

• G06T7/11

  Region-based segmentation · CPC title

• G06V20/64 Primary

  Three-dimensional [3D] objects · CPC title

• G06V10/255

  Detecting or recognising potential candidate objects based on visual cues, e.g. shapes · CPC title

• G06V20/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) · CPC title

• G06T7/73 Primary

  using feature-based methods · CPC title