The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Voi. XXXVII. Part B4. Beijing 2008
Figure 3 Data Sets
Ql(X[,Y/,Z') is determined as follows:
X\ = {X iA +X,)l2
Y!=Vi-i + y>)li (3)
z;=s(x;,y;)
where , Y { is the planar coordinate, S{X' h Y{) denotes the Z
coordinate of the surface S at X t , Y t . Actually, Y[ = Y t _j = Y t .
Q\ is much closer to P than Q t and Q t _j (See the blank circle).
Specially, if the spatial Euclidean distance between Q t and
is less than a prearrange threshold, Q\ is considered as to
be the anticipated intersection point P .
3 SURFACE MATCHING WITH NDCC
The distance between the point s • R/7' +1 on the transformed
second surface and its corresponding point P i on the first
surface along the normal vector n can described as:
Dist t = (P t -(s-RPj+t))w 0 (4)
where n Q is the unit normal vector of h, • denotes the scalar
product.
Clearly Dist should be zero in ideal case when the match is
reached. Then, an object function that minimizes the sum of
squared Dist can pull the two surfaces close to each other.
min ^ Wf • Distf (5)
where w,, the weight of Dist,, 0 or 1, is used to deal with the
question caused by the partial overlapping(Li, Xu et al. 2001).
According to the principle of least square, the surface can then
be matching with an iterative behavior.
The terminated conditions of the iteration are:
1) The difference of the estimated transformation parameters
between two successive iterations is less than per-arranged
threshold;
2) Or reach the maximum iteration number.
This algorithm is called least normal distance algorithm (LND).
Using LND, the two surfaces are pulled close to each other
along the surface normal vector.
4 EXPERIMENT ANALYSES
In order to provide a better understanding of the performance of
NDCC, we implemented the proposed algorithm, and the
iterative closet point (ICP) algorithm with the desired rotation
angle and translation are respectively less than 0.1" and 0.01m
between two successive iterations and the maximum iteration
number is 70 for a comparative study based on simulated data
set (Figure 3). It is a typical landform surface. It is grided data
set containing 100x120 with an interval distance equal to 10m.
The second surface is derived from the first surface by firstly
applying the per-arranged transformation (rotation angle is 2°
and translate is 50m) to it, and then adding zero-mean Gauss
noise with a standard deviation equal to 0.2m.
Both algorithms are directly applied to the data set without any
pre-processing, feature extraction, and also without knowledge
about the overlapping. Thus, the experimental results based on
such data set are objective and they represent typical surface
conditions.
The performance indices of interest in this paper are
convergence and computational efficiency. Then all
experimental results are given below in turn
4.1 Convergence
To give an in-depth discuss of the convergence of our algorithm,
the method for computing the convergence rate will be given
briefly first. The distance E between two surfaces can be
measured using the mean of the distance between all
corresponding points:
where «(> l) is the number of iteration, ||| is the Euclidean
distance, p i and p'j are corresponding points locating on the
first and second surface, the sub-script i, j are the number of
point, N is the total number of the corresponding pairs, ii(o) is
the surface distance before matching. Note that the
corresponding points are not construct by the matching
algorithm, but the known corresponding points of two surfaces
to be matched. Therefore, E is an objective value and is
independent of the matching algorithm.
During the beginning phase, E is very big owing to the large
error existing in the transformation parameters. With the
increasing of the iterations, E reduces to a small positive
number, not zero.
The convergence indicator (Cl) can then be computed according