CRITICAL ANALYSIS OF REGISTRATION ALGORITHMS: ON THE POTENTIAL OF SURFACE BASED REGISTRATION FOR AUTOMATIC DEFORMATION MONITORING

By best align is meant the transformation that brings the maximum number of points from one point set to within some distance of points in the corresponding point set . The 4-points congruent sets algorithm (4PCS) by Aiger et.al. (2008) is a solution for a stable alignment of two partially overlapping point cloud datasets, which are randomly orientated to each other. This approach is implemented within a registration tool and a good way to match two point clouds into one coordinate system. The Iterative closest point algorithm (ICP) by Besl and McKay (1992) finds the closest point on a geometric entity to a given point and can be applied within the Registration Tool for further refinement. Using the software Cloudcompare the ICP method can be directly applied with the help of user settings as well as the software 4PCS Demo supports the easy usage of the 4PCS algorithm for surface registration. Both approaches lead to fair results for deformation monitoring.

1.1 The algorithm

Given are the point set P with Np number of points pi from the data shape and the model shape X (with Nx the number of points, lines, segments or triangles involved in the shape model). The iteration is initialized by setting P0=P, q0=1,0,0,0,0,0,0t and k=0 , where q0 a translation vector, in order to avoid local minima. The registration vectors are defined relative to the initial data set P0 so that the final registration represents the complete transformation. The following steps are applied until convergence within a tolerance τ is reached.

Step 1: Computation of the closest points Yk=CPk,X , where C the closest point operator.

Step 2: Computation of the registration qk,dk=QP0,Yk where dk the mean square error, qk the registration vector and Q the least squares registration.

Step 3: Application of the registration via Pk+1=qkP0 which updates the positions of the data shape point set.

Step 4: Termination of the iteration when the change in mean square error falls below a preset threshold τ=0 specifying the desired precision of the registration: dk-dk+1<τ . If τ is dimensionless it is replaced by τtr(Σx) which indicates the rough size of the model shape, where Σx the covariance of the model shape.

1.2 Registration of point clouds with the ICP (Cloud Compare)

For the analysis of registration algorithm, first the ICP (Cloud Compare) was used. Two approaches were used to perform this method with the help of ICP on the given dataset of point clouds of “Buddha”.

The two methods are as follow;

1. Match barycentres (centroid matching)

2. Point pairs picking

Using the first method performed the algorithm on given dataset of “Buddha” to register the clouds to each other and performing the fine registration with tools of ICP. The result can be seen in following figure.

Figure SEQ Figure \* ARABIC 1 - Centroid matching

The above figure was obtained with matching of centres bounding box and we get the transformation matrix.

Figure SEQ Figure \* ARABIC 2 - Fine registration after matching centres

After aligning and partially registering the clouds we perform the fine registration with help of ICP. Figure 2 shows the result of fine registration. As both clouds are of same object so we try to do maximum overlapping manually which is somewhat tricky part and can play role in non-precised result of registration. Second method for point cloud registration was performed by picking up point pairs for the registration of two clouds. As shown in figure 3 below, it can see from the RMS error is very low which is only 0.14.

Figure SEQ Figure \* ARABIC 3 - Point pairs picking

We pick up the points in both cloud dataset. But we make sure that the order of picking point is same in both clouds. So we picked up 4 points in dataset of “Buddha” and in the same order in the reference dataset. The order of picking points should be same and on similar locations so we can reduce the error to minimum. After picking up the points we perform the fine registration for the final outcome and final outcome is shown below in figure 4.

Figure SEQ Figure \* ARABIC 4 - Fine registration after picking point pairs

After the whole process and trying two different methods we conclude that; that ICP can perform efficient registration with minimum errors. But mostly tricky part in performing the method for registration is to align and overlap the maximum volume of clouds to reduce error and RMS. As it provides the opportunity of high degree of freedom and translation in any angle so we can choose the best equivalent remarkable points for performing the registration. This is also time consuming part.

ICP provides number of parameter to consider for maximum quality. It includes the maxim rotation and translation in x, y and z directions. Different parameters like Iteration, threshold value can be set to reduce the RMS error to minimum. One can increase of decrease the number of iterations to find out the best result of registration and minimum RMS error.

As we had played with the iteration in point pair picking method for fine registration and with increasing iteration it gives better result.

2. 4-POINTS CONGRUENT SETS ALGORITHM

The 4PCS algorithm was introduced by Aiger et.al. in 2008. It is an improvement of the randomized alignment approach that was firstly mentioned by Irani and Raghavan in 1996.

The main concept of 4PCS is the following: for different choices of base pairs from P and Q , the computation of the corresponding rigid transformations is performed, their quality is evaluated, and the best transformation is chosen according to the Largest Common Pointset (LCP). The problem becomes easier if the point-bases are defined by four points. The correspondence is performed by approximately congruent bases from Q up to some allowed tolerance δ .

Based on Aiger et al. (2008), a key point of 4PCS is the use of wide-bases because of their stability, resiliency to noise and outliers. It is very important to point out that typical range scanners generate non-additive or non-Gaussian noise, for which any pre-filtering could be harmful. Hence, a resilient technique is needed for the registration of raw noisy data, possibly contaminated with outliers. An important contribution is that of affine transformation leading to the generation of bases invariant under rigid motion. The method also differs from other state-of-the-art techniques in two more points. It takes no assumption about the starting position of the point sets to be aligned. Furthermore, it is not based on the principle generate and test reducing in that way the needed number of trials. Testing all possible corresponding bases Q can be an exhaustive procedure, not to mention infeasible in 3D. To solve this problem the idea of planar congruent sets is introduced. In that way, only a small set of bases from Q is selected as potentially corresponding to P . The algorithm runs in On2 , where n the number of points, however further enhancements using local descriptors reduce the search space to a linear one when the can be computed robustly. Testing over a variety of input data 4PCS proved accurate, fast and robust over noise, outliers and extent of overlap. Limitations of the method include tricky objects, low overlap scans and very large point sets.

Further refinement can subsequently be done with an ICP calculation.

2.1 The algorithm

Given are two point sets P and Q in arbitrary initial positions, an approximation level δ>0 for the position accuracy of the points and an estimation of the overlap fraction f of the points in P that can be matched to Q .

Step 1: Selection of a coplanar base B⊆P , consisting of 4 – approximately – coplanar points. Points should be far from each other to ensure stable alignments. However they should not be too far, so that they all lie in the overlap area (for partial matching). This maximum distance is estimated by f . If f is not provided, then the distance is guessed decreasingly until the desired error tolerance is reached.

Step 2: Given B , its two affine invariants ratios over this plane is computed. Then from the points Q , the set U≡U1,U2,⋯,US that can be related to B up to an approximation level δ by affine transforms is extracted. The best aligning rigid transform Ti that brings B close to Ui in a least square sense is then estimated according to the Largest Common Pointset (LCP).

2.2 Registration Tool

To register points with help of 4PCS algorithm the tool 4PCS Demo is used. The tool provides a 4PCS calculation and an additional ICP refinement.

2.3 Parameters and Error Metric

Within 4PCS Demo several parameters can be set.

Noise is used for adding some systematic errors to the chosen or given model.

Usually a noise of 5% will be applied to the edges of the shape, which could resemble difficult recording conditions in reality.

Delta is a threshold value. For example if a point from dataset A might be congruent to a point from dataset B under this threshold, the transformation parameters will be set according to this threshold and then points from dataset A will be transferred with this threshold to dataset B and the congruent point can be obtained.
Two mayor types of metric errors might occur. One due to threshold value, if delta is too big, the number of possible 4-points datasets will be increased and it causes some conflict for finding right corresponding data.

Another numeric error happens because of low overlap. For example when the fraction overlap is 20% the estimated error is too high, whereas when overlap is 60% the estimated error decreases until 80% overlapping, when the error reaches zero.

Also the noise is a factor for increasing the estimated error. The less noise you have, the less it will influence the result.

2.4 Quality Measures and Usage

The 4PCS is suitable for medium-sized datasets, which are not in an ideal position towards each other, have a fair overlap and have some outliers and noise.
The 4PCS algorithm might have drawbacks if the data is too clean. If the scanned object slips too much, it can lead to ambiguities, which can only be removed if semantic information is available. Other limitations regarding fully automatic registration processes are problems that might occur due to low overlap and very large point sets.

2.5 Results

Results of the processed point clouds are shown below. The task was to determine deformations on a Buddha statue and a Pontiac before and after a crash.

[Anmerkung: Originalpaper enthielt drei Abbildungen, die sich allerdings nicht hochladen ließen]