Martin Smith
3 THE TECHNIQUE OF CURVE MATCHING
The automatic curve matching takes place in two stages; firstly a gross (or bulk/coarse) transformation, followed by an
iterative fine adjustment process to obtain the ‘best’ match. The basic methods for each stage are presented. The first
stage was not always needed if the curve coordinate systems were not too dissimilar. The method is best explained by
considering 2 three dimensional (3D) curves. These 3D curves are defined by a series of points with X, Y and Z
coordinates. There is no attempt to record corresponding points in each curve during the observation or collection of the
curve data. The matching process attempts to match a point on curve 1 to a point on curve 2 that is closest to where the
corresponding point on curve 2 should be. The potential quality of the curve fit will be based on either extremely high
redundancy or the filtering out of match points that are not good corresponding points. This filtering should leave a
relatively small number of points that are ‘reasonably’ (within a tolerance) well matched.
Although a bulk translation can be performed by using the centroid of the coordinates the rotation is not quite so easy to
determine. A method of bitangent pairs was investigated, see figure 1.
Curve 1 Curve 2
Figure 1. Finding bitangent pairs on 3D curves
On curve 1 a point Ol is selected and a normal and tangent are determined (method from Bu-Quing, 1989). A further
point on the curve, point O2, is found with ‘the same’ (within tolerance) normal and tangent. If no ‘O2’ is found a new
Ol is chosen and the process is repeated. An attempt is then made to find the corresponding points on curve 2 by
exhaustive searching to find a similar bitangent pair of points. Once a possible pair of corresponding points are found
(P1, P2) a local curve fit between points a to b and a' to b' and similarly c to d and ¢’ to d’ is performed. If the fit is
within tolerance then a bulk transformation is performed using these points. If not the process is repeated with new Ol
and O2. To ‘fine tune’ the transformation (to get a better match) the method known as the Iterative Closest Point (ICP)
matching algorithm is used, see figure 2, developed by a number of researchers in the early 1990's (e.g. Besl & McKay,
1992; Chen & Medoni, 1992).
O3
Figure 2. Iterative closest point matching
As an example consider point P3 and calculate the distance to points on the *O' curve dl, d2, d3. The shortest is d2
therefore O3 is accepted as the matched point. This is performed for all points on ‘P’ curve. Then the statistical
filtering is performed to check each point to see if the value of d is less than a tolerance value, D. After the first iteration
the value of D is related to the mean and standard deviation of the values of d. Points outside the criteria are temporarily
rejected. The matched points are used to compute a new transformation and the ICP process is repeated. Temporary
rejection becomes permanent if a point is continuously ‘temporarily rejected’. Termination of the whole process occurs
when the rate of change in the choice of matched points between iterations, or the number of matched pairs drops below
a threshold value. The result is a list of coordinates of matched points on each curve.
852 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
mn
CC
