174 
4. Let the distance measure between the two images for a given transformation M: 
£M) — 4 » D^(Mix(rcii), 52i) + m) (2) 
n n 
ci + c2 ici i=1 
Find Mj such that: 
Er = min €x (M) (3) 
k 
Until: convergence test 
e Result: Mj is the estimated transformation bringing E, towards R5. 
The sets of closest compatible points are recomputed at each iteration: this is the most time-consuming operation. 
The process is repeated until the difference between two successive values of £* is less than a predetermined threshold 
Te. An alternate convergence test can be based on the magnitude of the incremental translation and rotation in an 
iteration. In Equation 2, the inverse transformation ME | is applied to the 5;;.4 because the minimization is applied 
from the initial frame of reference, so that M; is the total transformation bringing R; towards Rs. 
4.2. Convergence 
The proof of convergence for the ICCP algorithm follows the same structure as for the simple ICP [2]. At the 
beginning of iteration k, the error between the points in R, and Ra» and their closest compatible points is expressed 
as £p — £x(Mx1). By definition of the minimization process, £; X £9. At the next iteration (k -- 1), £0, (My) is 
obtained by finding a new set of closest points, and evaluating the distance using the current value of transformation 
MM. Each term in the summation of eui is necessarily less or equal to the corresponding term in £z, since the new 
closest point is at least as close as the one found in the previous iteration, since the same point could be found. As 
for the kth iteration, £7,, « £o Vu And since all the £s are greater or equal to zero, there is a convarger-- +=" 
a minimum with k. The convergence property is the same as for the !(P because ihe geometric transío: nation 
does not affect the compatibility measure of a pair of points: at each iteration, the closest compatible point for a 
given point is always chosen from the same subset. The ICCP method has a general behavior similar to the ICP: 
the convergence rate slows down as the minimum is approached. In [2], acceleration techniques were proposed that 
extrapolate the solution along a path in 7-dimensional space. They are directly applicable to the ICCP as well. Other 
acceleration schemes are found in [14, 16]. 
4.3. Robust version 
As in the case of ICP, the ICCP algorithm is influenced by points belonging to regions visible only in one of the two 
images. This is an issue with all point-based registration methods. Some robust registration algorithms have been 
proposed that attempt to avoid the effect of these outlier points [3, 8, 12, 16]. For this paper, it was rather decided 
to experiment with a weighting of the error contribution for each pair of points, in a matter similar to influence 
functions. The weight is a function of the Euclidian distance between the points. For each pair of points r; and r; 
in the cost function (2), a weight, defined as: 
| 1 PC) ifo ri) < Dinar 
Dar A 
0 otherwise 
(4) 
is applied. A major difficulty with this type of approach is to select the value of Dyaz In an objective manner. 
The distance should be large enough to allow the matching of similar points that may be far apart in the initial 
stages, while being small enough to filter out the contributions of outliers when the two sets of points are close to 
one another. One way of obtaining an initial registration that is sufficiently close so that most points on common 
surfaces are within Dymaz is to first run the basic algorithm, for a fixed number of iterations or up to convergence, 
then to switch to the robust method. It should be noted that the guarantee of monotonical convergence for the 
ICCP is lost with the introduction of these weights in the cost functions. 
The distance minimization in the ICCP algorithm is performed using the unit-quaternion formulation of the problem, as 
described in [6, 9]. The robust version with the o-weighted distance also uses this method, since it can accommodate 
weighting of individual error terms. Translation is first found from the distance between (weighted) centroids. The 
rotation quaternion is found as the eigenvector corresponding to the largest eigenvalue of a real symmetric matrix 
formed with terms of cross-covariances of the data. 
IAPRS, Vol. 30, Part 5W1, ISPRS Intercommission Workshop "From Pixels to Sequences", Zurich, March 22-24 1995 
O NN 
— (fh + OO OO 
— — amm — 9 dm PN