Method for extracting planes from 3D point cloud sensor data

• US 9,412,040 B2
• Filed: 12/04/2013
• Issued: 08/09/2016
• Est. Priority Date: 12/04/2013
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Feng, Chen, Taguchi, Yuichi, Kamat, Vineet
• Primary Examiner(s): Park, Chan
• Assistant Examiner(s): Kholdebarin, Iman K
• Application Number:
  US14/096,378
• Publication Number:
  US 20150154467A1
• Time in Patent Office: 979 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices
• CPC Class Codes: G06V 10/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 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

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.

Claims

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.