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