Automatic point cloud pre-alignement using orientation histograms

Introduction

Terrestrial laser scanners allow to obtain accurate 3d model of the object as a point cloud. Real objects should be scanned with different instrument positions and then scan data is registered into the single coordinate system. In practice the process of registration is performed using manual or semi-automated registration techniques. First fully automatic methods were introduced about fifteen years ago. Many of the methods based on well-known iterative closest point algorithm (ICP) permit to obtain the exact solution of a problem. Nevertheless, the problem is difficult to solve due to necessity of information regarding the coarse relative orientation parameters of point clouds. We develope the algorithm based on usage of orientation histogram to solve a problem without any information concerning scan positions. Experimental studies of the algorithm have demonstrated its efficiency at any values of point clouds relative orientation.

Short algorithm description

The pre-alignment algorithm for two point clouds consists of an estimation of shift vector T and rotation matrix R between local coordinate systems for each scan. Our algorithm includes two consistent steps: angular orientation and its relational shift.

Point filtering
We reject all points with vertical normal directions. And we also remove all points by surface variation threshold, this action filters the majority of vegetation points.

Estimation of the angular orientation
Estimation of the angular orientation consists of the following steps:

  1. Generate two orientation histograms H1 and H2 for scans P1 and P2 respectively;
  2. Search the maximum of correlation function C(H1, H2_rotated) for all possible values of rotation matrix R.

The value of rotation matrix, corresponded to the maximum of correlation function, is a required angular scans orientation value.

Estimation of the translation vector
Firstly the rotation procedure is applied for cloud P2 using values of rotation matrix, which was found in the previous step. Than the binary voxel presentation for both scans should be calculated using 3D discretization procedure. The element of voxel representation is equal to 1 if at least one scan point is inside this voxel and is equal to 0 otherwise.

Estimation of the shift between scans coordinate systems is defined by maximum of the correlation function G, which is computed using Fourier Transform.

See our paper for more details.

Results

Cat sculpture (without planes!)

     
Fig. 1. Scan data before & after automatic alignment..Initial rotation angle along Z axis is ~78deg. The length of initial translation vector is ~90% of the full data size.

Welfenschloss castle

     
Fig. 2. Scan data before & after automatic alignment..Initial rotation angle along Z axis is ~72deg.The length of initial translation vector is ~70% of the full data size. This data provided by the Institut for Cartography and Geoinformatics, Leibniz Universität Hannover, http://www.ikg.uni-hannover.de

Samarina Church

     
Fig. 3. Scan data before & after automatic alignment..Initial rotation angle along Z axis is ~43 deg. The length of initial translation vector is ~120% of the full data size. This data are provided by ISPRS, Working Group V/3, http://www.commission5.isprs.org/wg3e.

Build

     
Fig. 4. Scan data before & after automatic alignment..Initial rotation angle along Z axis is ~70 deg. The length of initial translation vector is ~150% of the full data size.

Publications

Chibunichev A.G., Velizhev A.B., Automatic Matching of Terrestrial Scan Data Using Orientation Histograms, ISPRS the XXI Congress, Beijing, 2008 [pdf]

References

Dold, C., 2005. Extended Gaussian images for the registration of terrestrial scan data. In: ISPRS WG III/3, III/4, V/3 Workshop "Laser scanning 2005", Enschede, the Netherlands. [pdf]

Makadia, A., Patterson IV A., Daniilidis K., 2006. Fully automatic registration of 3D point clouds. In: Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference, Vol. 1, pp. 1297-1304. [pdf]

Contacts

Alexander Velizhev
avelizhev@graphics.cs.msu.ru