Device and method for merging 3D point clouds from sparsely distributed viewpoints

Patent metadata

Field	Value
Publication number	US-9858640-B1
Application number	US-201514800078-A
Country	US
Kind code	B1
Filing date	Jul 15, 2015
Priority date	Jul 15, 2015
Publication date	Jan 2, 2018
Grant date	Jan 2, 2018

Abstract

A method for merging 3D point clouds from sparsely distributed viewpoints includes collecting a plurality of 3D point cloud data sets using a 3D sensor, each 3D point cloud data set in a local reference frame of a viewpoint of the 3D sensor, downsampling the 3D point cloud data sets, registering the downsampled 3D point cloud data sets to a global reference frame using an initial transform T v for rotating and translating each downsampled 3D point cloud data set from the local reference frame to the global reference frame, deriving estimated transforms T v until the last derived transform T v converges to a stable transform T v , registering the plurality of 3D point cloud data sets to the global reference frame using the stable transform T v , and deriving second estimated transforms T v until the last derived transform T v converges to a second stable transform T v .

First claim

What is claimed is:

1. A method for merging 3D point clouds from sparsely distributed viewpoints comprising:
collecting a plurality of three dimensional (3D) point cloud data sets using a 3D sensor, each 3D point cloud data sets in a local reference frame of a viewpoint of the 3D sensor;
downsampling the three dimensional (3D) point cloud data sets to form a plurality of downsampled three dimensional (3D) point cloud data sets;
registering the downsampled 3D point cloud data sets to a global reference frame by
computing an initial transform for rotating and translating each downsampled 3D point cloud data set from the local reference frame of the viewpoint of the downsampled 3D point cloud data set to the global reference frame;
finding for each downsampled 3D point cloud data set corresponding points in other neighboring downsampled 3D point cloud data sets;
mapping the corresponding points to the global reference frame using the initial transform;
generating a list of each point in each downsampled 3D point cloud data set and the corresponding points;
deriving an estimated transform that optimally maps each point in each downsampled 3D point cloud data set onto the corresponding points; and
repeating the steps of generating and deriving an estimated transform for each downsampled 3D point cloud data set using a last derived estimated transform until the last derived estimated transform converges to a stable transform; and

registering the plurality of three dimensional (3D) point cloud data sets to the global reference frame by:
using the stable transform for rotating and translating each 3D point cloud data set from the local reference frame of the viewpoint of the 3D point cloud data set to the global reference frame;
finding for each 3D point cloud data set corresponding points in other neighboring 3D point cloud data sets;
mapping the corresponding points to the global reference frame using the stable transform;
generating a list of each point in each 3D point cloud data set and the corresponding points;
deriving a second estimated transform that optimally maps each point in each 3D point cloud data set onto the corresponding points; and
repeating the steps of generating and deriving a second estimated transform for each 3D point cloud data set using a last derived second estimated transform until the last derived second estimated transform converges to a second stable transform.

2. The method of claim 1 further comprising:
collecting an estimate of the viewpoint of the 3D sensor for each 3D point cloud data set using a viewpoint sensor.

3. The method of claim 1 further comprising:
filtering each 3D point cloud data set to remove redundant and isolated points from the 3D point cloud data set.

4. The method of claim 1 further comprising:
creating a mesh connectivity grid for each 3D point cloud data set and for each downsampled 3D point cloud data set.

5. The method of claim 1 further comprising:
creating a search tree for each 3D point cloud data set and for each downsampled 3D point cloud data set in the local reference frame of the viewpoint.

6. The method of claim 5 wherein creating a search tree comprises:
creating a Kd-tree, a Quadtree, a Octtree, an R-tree, or a B-tree.

7. The method of claim 1 wherein the 3D sensor comprises a LASER range finder, a plurality of 2D optical cameras, a 3D camera, or a plurality of 3D sensors.

8. The method of claim 2 wherein the viewpoint sensor is attached to the 3D sensor.

9. The method of claim 2 wherein the viewpoint sensor comprises an inertial sensor or an accelerometer.

10. The method of claim 1 wherein downsampling the 3D point cloud data sets to form downsampled 3D point cloud data sets comprises:
downsampling so that an average distance to a nearest neighbor point is greater than an average distance to a nearest neighbor point of the 3D point cloud data sets.

11. The method of claim 4 wherein creating a mesh connectivity grid for each 3D point cloud data set and for each downsampled 3D point cloud data set comprises:
projecting points onto a plane normal to the viewpoint of the sensor;
using Delaunay triangulation to connect points on the plane; and
for each triangle of connected points in the mesh connectivity grid, if the triangle is significantly non-regular removing the points in the triangle, removing a point that is not connected to any remaining triangles, if a point is connected to an edge that is only connected to one triangle, marking the point as a boundary point, and marking all other points as interior points.

12. The method of claim 1 wherein deriving an estimated transform that optimally maps each point in each downsampled 3D point cloud data set onto the corresponding points comprises minimizing a sum of squared differences between the corresponding point and the estimated transform times each point in each downsampled 3D point cloud data set.

13. The method of claim 1 wherein deriving a second estimated transform that optimally maps each point in each 3D point cloud data set onto the corresponding points comprises minimizing a sum of squared differences between the corresponding point and the second estimated transform times each point in each 3D point cloud data set.

14. The method of claim 1 wherein deriving an estimated transform that optimally maps each point in each downsampled 3D point cloud data set onto the corresponding points comprises using Horn's method.

15. The method of claim 1 wherein deriving a second estimated transform that optimally maps each point in each 3D point cloud data set onto the corresponding points comprises using Horn's method.

16. The method of claim 1 wherein registering the downsampled 3D point cloud data sets to a global reference frame comprises using pseudo code

Let T v be the transform from view V to the global reference frame

Let g denote the global reference frame.

Let P v be a point in the reference frame of view V.

while not converged do

 for each view V do

 let C = { }

 for all P v ε V do

  P g = T v * P v

  for each view N connected to V do

  P n = T n −1 * P g

  using the kd-tree of N, find a point Q n ε N that is nearest to P n

  if Q n is not a boundary point then

   Q g = T n * Q n

   C = C ∪ {(Q g , P v )}

  end if

  end for

 end for

find ⁢ ⁢ T v ⁢ ⁢ that ⁢ ⁢ minimizes ⁢ ⁢ the ⁢ ⁢ ∑ ( d , s ) ∈ C ⁢ norm ⁡ ( d - T v * s ) 2 ⁢ ⁢ using

Horn's method[5]

 end for

end while.

Assignees

• Hrl Lab Llc

Inventors

• Earl Darren J
• Hoffmann Heiko
• Uhlenbrock Ryan M

Classifications

• G06T7/0032

  Physics · mapped topic

• G06T2207/10028

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

• G06T2200/04

  involving 3D image data · CPC title

• G06T3/0075 Primary

  Physics · mapped topic

• G06T17/005

  Tree description, e.g. octree, quadtree · CPC title