Method for extracting planes from 3D point cloud sensor data

Patent metadata

Field	Value
Publication number	US-9412040-B2
Application number	US-201314096378-A
Country	US
Kind code	B2
Filing date	Dec 4, 2013
Priority date	Dec 4, 2013
Publication date	Aug 9, 2016
Grant date	Aug 9, 2016

Abstract

A method extracts planes from three-dimensional (3D) points by first partitioning the 3D points into disjoint regions. A graph of nodes and edges is then constructed, wherein the nodes represent the regions and the edges represent neighborhood relationships of the regions. Finally, agglomerative hierarchical clustering is applied to the graph to merge regions belonging to the same plane.

First claim

We claim:

1. A method for extracting planes from three-dimensional (3D) points, comprising the steps of:
acquiring a depth map with a 3D sensor, wherein the depth map has a two-dimensional grid of pixels and each pixel has a depth value;
back-projecting the depth map to generate a cloud of 3D points;
partitioning the 3D points into disjoint regions;
constructing a graph of nodes and edges, wherein the nodes represent the regions and the edges represent neighborhood relationships of the regions, wherein each node includes a set of 3D points, a plane fitted to the set of 3D points, and a mean squared error (MSE) of the set of 3D points to the plane; and
applying agglomerative hierarchical clustering to the graph to merge regions belonging to a same plane, wherein in each iteration of the agglomerative hierarchical clustering, a node with a minimum MSE is selected and merged with one of neighboring nodes having a minimum merging MSE among the neighboring nodes, wherein the steps are performed in a processor.

2. The method of claim 1 , wherein the 3D points are acquired by a 3D sensor.

3. The method of claim 1 , further comprising: applying region growing to refine boundaries of the planes.

4. The method of claim 1 , wherein planes are extracted from a sequence of images in real time.

5. The method of claim 1 , wherein the partitioning is uniform, and the regions are equal sized.

6. The method of claim 1 , wherein the 3D points are organized and have 2D indices.

7. The method of claim 6 , wherein the 2D indices are used for the partitioning and for the constructing.

8. The method of claim 1 , further comprising: maintaining first and second order statistics of all points in each region.

9. The method of claim 1 , wherein the 3D points are unorganized.

10. The method of claim 9 , further comprising: defining a set of voxels in a 3D space; assigning each 3D point to a voxel according to coordinates of the 3D point; determining voxels that have at least one 3D point as the nodes; and defining the edges between voxels if two voxels are next to each other in the 3D space.

11. The method of claim 1 , wherein the partitioning is non-uniform.

12. The method of claim 1 , further comprising: registering sets of 3D points defined in different coordinate systems by using the planes extracted from each set of 3D points.

13. The method of claim 12 , wherein the registering uses the 3D points and the planes.

14. The method of claim 1 , wherein the planes are used for determining coordinates of a 3D location.

15. The method of claim 14 , wherein the 3D location is specified manually.

16. The method of claim 14 , wherein the 3D location is determined automatically.

17. An image processing system for extracting planes from 3D points, the image processing system comprising:
a three-dimensional (3D) sensor configured to acquire a depth map, wherein the depth map has a two-dimensional grid of pixels, and wherein each pixel has a depth value;
a processor operatively connected to the 3D sensor to receive the depth map, wherein the processor is configured for
back-projecting the depth map to generate a cloud of 3D points;
partitioning the 3D points into disjoint regions;
constructing a graph of nodes and edges, wherein the nodes represent the regions and the edges represent neighborhood relationships of the regions, wherein each node includes a set of 3D points, a plane fitted to the set of 3D points, and a mean squared error (MSE) of the set of 3D points to the plane; and
applying agglomerative hierarchical clustering to the graph to merge regions belonging to a same plane, wherein in each iteration of the agglomerative hierarchical clustering, a node with a minimum MSE is selected and merged with one of neighboring nodes having a minimum merging MSE among the neighboring nodes.

18. The image processing system of claim 17 , wherein the 3D sensor is a one or combination of a depth camera, a time-of-flight camera, a structural light scanner, and a laser range finder.

19. A non-transitory computer readable medium storing a program causing a processor to execute an image process for extracting planes from three-dimensional (3D) points, the image process comprising:
acquiring a depth map with a 3D sensor, wherein the depth map has a two-dimensional grid of pixels and each pixel has a depth value;
back-projecting the depth map to generate a cloud of 3D points;
partitioning the 3D points into disjoint regions;
constructing a graph of nodes and edges, wherein the nodes represent the regions and the edges represent neighborhood relationships of the regions, wherein each node includes a set of 3D points, a plane fitted to the set of 3D points, and a mean squared error (MSE) of the set of 3D points to the plane; and

applying agglomerative hierarchical clustering to the graph to merge regions belonging to a same plane, wherein in each iteration of the agglomerative hierarchical clustering, a node with a minimum MSE is selected and merged with one of neighboring nodes having a minimum merging MSE among the neighboring nodes, wherein the steps are performed in a processor.

Assignees

• Mitsubishi Electric Res Laboratories Inc

Inventors

• Feng Chen
• Taguchi Yuichi
• Kamat Vineet

Classifications

• G06V10/46

  Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features (colour feature extraction G06V10/56) · CPC title

• G06T7/12 Primary

  Edge-based segmentation · CPC title

• G06V10/426

  Graphical representations · CPC title

• G06V10/457

  by analysing connectivity, e.g. edge linking, connected component analysis or slices · CPC title

• G06T2207/10028

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