ace
the
ject
'ine
id 5
ace
aint
face
geometry. The development of an algorithm for high
accurate measurement of non-targeted but well-defined
image edges was to be achieved. For inspection the
checking of the diameter d between the outer flanges is of
interest. With a diameter of 25 cm an accuracy in
diameter measurement of 10 jum was requested. Because
the method gives 3-D coordinates and the measurement is
done in a plane the standard deviation of a single
coordinate translates to 7.1 jum. A partial report on this
project can be found in El-Hakim, 1990 and Gruen,
Stallmann, 1991.
2. EDGE MATCHING ALGORITHM
The used edge matching method is a modification and
extension of the MPGC matching algorithm. This image
matching algorithm is based on least squares matching
(LSM) and belongs to the class of area based matching
methods. In an iterative least squares adjustment process
the algorithm matches multiple images, finds the edge
and determines 3-D object coordinates simultaneously.
More detailed descriptions of the mathematical concepts
of LSM are published in Gruen 1985, MPGC matching in
Gruen 1985 and Gruen, Baltsavias 1988 and edge
matching in Gruen, Stallmann 1991. Operational details
on MPGC can be found in Baltsavias, 1992.
2.1 Mathematical concept of MPGC matching
The LSM is a method to find similar structures in two
corresponding image windows, the reference patch
(template) and a search image (patch). The patch is
transformed upon the template such that the squared sum
of grey value differences is minimised. The location of
the patch against the template is described by a shift
vector. The template can be an artificial pattern for point
location, or a real window of an image to find
homologous image windows for parallax measurement.
In our case of edge matching it is a synthetic ramp edge.
The systematic differences between the template and the
patch, caused by perspective and sensor effects, can be
modelled by geometric and radiometric transformations.
Since the radiometric parameters are largely orthogonal
to the other system parameters, the radiometric correction
can be applied prior to the adjustment. Due to the small
patches the bundles of rays are very narrow and for the
geometric transformation the strict perspective projection
can be approximated by an affine transformation and
modelled by six linear parameters. The radiometric fit is
done by two parameters to form a linear function. This
leads to equal brightness and contrast of the patches and
the template.
The LSM model uses only the grey value information.
But very often additional information is available, which
can be used to support the model. If the sensor geometry
for each object point is based on perspective projection
the collinearity conditions can be formulated. These
conditions allow us to replace stereo LSM with MPGC
matching, using a theoretically unlimited number of
patches simultaneously for matching. Additionally, the
object coordinates can be determined simultancously.
The geometrical conditions are formulated as observation
equations with usually high weights and integrated into
the adjustment system.
The joint system is solved in a least squares adjustment.
Because of the non-linearity of the functional model the
final solution is obtained iteratively, whereby
approximate values for the parameters are required: the
geometric transformation parameters for each patch and
the object coordinates of the object point. The iterations
are stopped if each element of the solution vector falls
below a threshold.
2.2 Modifications for edge matching
In order to convert the MPGC algorithm into an optimal
and non-biased procedure for the measurement of edges,
the following modifications and extensions had to be
introduced:
e Introduction of a synthetic edge template.
e Reduction of the image shaping parameters to those
which are safely determinable by the given image
edge structure.
e Additional image space constraints for the shifts to
prevent a movement of the template along the edge.
e Creation and pre-rotation of individual templates for
each image.
The used templates are synthetic straight ramp edges
from dark (grey value 30) to light (grey value 226) with
varying linear ramp steepness (Figure 2).
Figure2 Synthetic straight ramp edges with
varying ramp widths (1, 2 and 3 pixels)
The geometrical transformation of the patch has to be
restricted, because the character of the image edges does
not allow the determination of all six parameters. They
allow a rotation of the patches without a scale change. A
scale perpendicular to edge is implicitly included by the
linear radiometric fit.
Since the image edges to be measured are essentially uni-
directional, a linear template edge would slide
continuously along the edge during matching. This effect
is compensated by restricting the shift vector of one patch
approximately perpendicular to the local edge direction.
The restrictions of the number of the reshaping
parameters and the shift vector condition are also
formulated as observation equations and added with a
high weight to the Icast squares equation system (for a
complete algorithmic representation see Gruen,
Stallmann, 1991).
The orientation of the corresponding edge elements in the
frames differ depending on the camera orientation.
Therefore the template must be pre-rotated into the