Automatic registration

Patent metadata

Field	Value
Publication number	US-9740711-B2
Application number	US-201414558243-A
Country	US
Kind code	B2
Filing date	Dec 2, 2014
Priority date	Nov 7, 2013
Publication date	Aug 22, 2017
Grant date	Aug 22, 2017

Abstract

A method, system, apparatus, article of manufacture, and computer-readable storage medium provide the ability to merge multiple point cloud scans. A first raw scan file and a second raw scan file (each including multiple points) are imported. The scan files are segmented by extracting segments. Features are extracted from the segments. A set of candidate matching feature pairs are acquired by registering/matching/pairing features from one scan to features from another scan. The candidate pairs are refined based on an evaluation of all of the matching pairs. The candidate pairs are further refined by extracting sample points from the segments (within the matched pairs) and refining the pairs based on the points. The feature pairs are scored and then merged based on the scores.

First claim

What is claimed is:

1. A computer-implemented method for merging multiple point cloud scans, comprising:
(a) importing a first raw scan file and a second raw scan file, wherein each raw scan file comprises multiple points;
(b) segmenting the first raw scan file and the second raw scan file by extracting first segments from the first raw scan file and second segments from the second raw scan file;
(c) extracting first features from the first segments and second features from the second segments;
(d) coarsely registering one or more of the first features to one or more of the second features to acquire a set of candidate matching feature pairs;
(e) refining the registering based on all of the candidate matching feature pairs;
(f) further refining the registering by:
(1) extracting sample points from the extracted first segments and the extracted second segments based on the registering; and
(2) utilizing the extracted sample points to refine the candidate matching feature pairs;

(g) scoring the candidate matching feature pairs; and
(h) merging the first raw scan file with the second raw scan file based on the scoring.

2. The computer-implemented method of claim 1 , wherein the first raw scan file and the second raw scan file are processed to create a first compressed spherical image file and a second compressed spherical image file respectively.

3. The computer-implemented method of claim 1 , wherein the extracted first segments and extracted second segments comprise homogeneous planar regions.

4. The computer-implemented method of claim 1 , wherein the extracting the first segments comprises:
calculating a surface normal for each of the one or more points in the first raw scan file; and
grouping, based on the calculated surface normal and a spatial distance between each of the one or more points, the one or more points into one or more regions.

5. The computer-implemented method of claim 4 , wherein the grouping comprises:
clustering the one or more points using a region growing method; and
grouping the one or more points within a cluster based on a measure of similarity that is defined using an angle between the surface normal for each of the one or more points and the spatial distance that is defined as a plane-to-point distance between the one or more points.

6. The computer-implemented method of claim 1 , wherein the extracting the first features and the second features comprises:
creating an orthographic binary image by projecting the one or more points from the first segments and the second segments onto an orthographic image plane;
fitting, on the orthographic image plane, a first bounding box around pixels corresponding to one or more of the first segments and a second bounding box around pixels corresponding to one or more of the second segments;
determining two-dimensional (2D) dimensions of the one or more first segments and the one or more second segments based on corresponding bounding boxes;
sorting the one or more first segments and the one or more second segments based on sizes of corresponding bounding boxes; and
filtering the sorted one or more first segments and the one or more second segments.

7. The computer-implemented method of claim 6 , wherein the filtering comprises:
filtering out floor and ceiling segments based on segment size, segment normal, and z-coordinates.

8. The computer-implemented method of claim 6 , wherein:
the filtering comprises classifying each of the sorted one or more first segments and the one or more second segments as a vertical segment or a horizontal segment; and
selecting a set of the vertical segments that are largest as features for registration.

9. The computer-implemented method of claim 1 , wherein the coarsely registering comprises:
(a) estimating a rotation comprising:
(i) determining a common floor in the first raw scan file and the second raw scan file, thereby reducing a search space from a three-dimensional (3D) rotation space into a one-dimensional (1D) rotation space comprising a rotation around a z-axis;
(ii) creating a histogram comprising histogram bins that correspond to rotation candidate angles, wherein each rotation candidate angle is based on a single pair of features, wherein the pair of features comprises one of the extracted first features paired with one of the extracted second features; and
(ii) considering a predefined number of the histogram bins; and

(b) estimating a translation of the considered predefined number of histogram bins comprising:
(i) determining a difference between z-coordinates of centers of the common floor from the first raw scan file and the second raw scan file.

10. The computer-implemented method of claim 9 , wherein the creating the histogram comprises:
creating the histogram bins for angles from 0 to 2π, wherein the histogram bins are of a predefined bin size based on a number of degrees;
for each single pair of features having corresponding angles with the z-axis, computing a rotation angle around the z-axis and increasing a value of the histogram bin corresponding to the computed rotation angle; and
wherein the histogram bins considered are selected from the bins having the highest values.

11. The computer-implemented method of claim 9 , wherein the estimating the translation further comprises:
for each rotation candidate angle in the considered predefined number of histogram bins:
(i) selecting two pairs of features;
(ii) calculating an estimated translation by minimizing a plane-to-point distance between a center point of the first feature and a center point of the second feature in each of the two pairs of features;
(iii) evaluating the estimated translation by:
(1) projecting all of the first features onto the second raw scan file; and
(2) counting a number of the first features that have a match on the second raw scan file.

12. The computer-implemented method of claim 1 , wherein the further matching the first segments to the second segments based on the extracted sample points, is based on iterative closest point (ICP) processing.

13. The computer-implemented method of claim 1 , wherein the scoring comprises:
computing an amount of overlap between the first feature and the second feature of each candidate matching feature pair.

14. The computer-implemented method of claim 1 , wherein the scoring comprises a cycle-based scoring to select locally consistent scan cycles.

15. A non-transitory computer readable storage medium encoded with computer program instructions which when accessed by a computer cause the computer to load the program instructions to a memory therein creating a special purpose data structure causing the computer to operate as a specially programmed computer, executing a method of merging multiple point cloud scans, comprising:
(a) importing, in the specially programmed computer, a first raw scan file and a second raw scan file, wherein each raw scan file comprises multiple points;
(b) segmenting, in the specially programmed computer, the first raw scan file and the second raw scan file by extracting first segments from the first raw scan file and second segments from the second raw scan file;
(c) extracting, in the specially programmed computer, first features from the first segments and second features from the second segments;
(d) coarsely registering, in the specially programmed computer, one or more of the first features to one or more of the second features to acquire a set of candidate matching feature pairs;
(e) refining, in the specially programmed computer, the registering based on all of the candidate matching featu

Assignees

• Autodesk Inc

Inventors

• Akman Oytun
• Poelman Ronald
• Koterba Seth

Classifications

• G06V10/44

  Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components · CPC title

• G06V10/24

  Aligning, centring, orientation detection or correction of the image · CPC title

• G06V10/752

  Contour matching · CPC title

• G06T17/20

  Finite element generation, e.g. wire-frame surface description, {tesselation} · CPC title

• G06F17/3053

  Physics · mapped topic