A.1 ABM and FBM
A.1.1 Area based matching
Area based matching (ABM) is the most straightforward type of correlation, as the images are used with-out previous processing and interpretation. This correlation method has a high degree of accuracy in ar-eas with a good structure [Ackermann, 1984], where there are grey level gaps, for instance, boundaries in the images. Areas with poor structure and subsequent poor contrast present a higher risk of errors, and subsequent poorer accuracy. Boundaries may, for instance, be differences between road and ditch, culti-vation boundaries, or rooves and surroundings etc. On the other hand, the method is sensitive to changes in the grey level value between the images.
The accuracy of ABM can be divided into an accuracy at pixel level and one at sub pixel level. The first-mentioned will find the best whole pixel position for a correlation.
A.1.1.1 Correlation at pixel level
Correlation at pixel level is done by means of correlation calculations, and in the following, different algo-rithms will be discussed. The difference between these algoalgo-rithms lies mainly in the reliability of the corre-lation value and the speed. Speed is often an important factor in the choice of which correcorre-lation function should be used [Kraus, 1990].
Here, two will be mentioned: correlation coefficient and mean square of the grey level differences, as it is these which have acquired the greatest importance.
A.1.1.1.1 Correlation coefficient
The correlation coefficient is an expression of the quality of the concordance between two images or im-age segments. The correlation coefficient (c) is determined on the basis of the standard deviation for the grey level values in the two images, or image segments, and the mutual co-variance matrix.
(
T T)
2T
g µ
σ = ∑ −
A(1.1)(
S S)
2S
g µ
σ = ∑ −
A(1.2)) µ -)(g µ -(g
σ
TS= ∑
T T S S A(1.3)where:
σT = the standard deviation in the target area σS = the standard deviation in the search area gT = the individual grey level values in the target area gS = the individual grey level values in the search area µT = the mean of the grey level values in the target area µS = the mean of the grey level values in the search area
calculated for the same position as the target segment.
A.1 ABM and FBM
The correlation coefficient may then be described as [Kraus, 1993]:
∑
∑ − ⋅ −
⋅ =
=
2 S S 2
T T
S S T T S
T TS
) µ (g )
µ (g
) µ -)(g µ Σ(g
σ σ
c σ
A(1.4)The correlation coefficient is often used as a criterion for confirmation of a correlation. The correlation co-efficient can vary between –1 and 1. The correlation is best when the coco-efficient is 1. For example, the programme package Match-T uses a minimum value for the coefficient, which as point of departure is 0.85 [Inpho GmbH, 1994]. The correlation coefficient is a measure of the quality of the correlation at pixel level. Calculation of the correlation coefficient for a series of search areas may form the basis of the se-lection of the best correlation at pixel level.
A.1.1.1.2 Mean square
Another measure of the quality of the correlation is the mean square which is calculated in the following way:
( )
n g g
T S 2∑ −
A(1.5) where: gT = the grey level value in the target area
gS = the grey level value in the search area n = the number of pixels used
By an optimal correlation, the mean square is 0.
The correlation coefficient has, as its most important advantage, its reliability, but it still results in a longer calculation time. On the other hand, the mean square of the grey level differences is easy to calculate and implement, but cannot handle differences in image scale.
Correlation with a greater accuracy than at pixel level can be achieved by means of other methods which indicate positions at sub pixel level.
Often a better determination of the position than at whole pixel level is desirable. Therefore, sub pixel level is used as well, and here two of the most important types of ABM at sub pixel level, polynomial cor-relation [Schenk et al., 1991; Kraus, 1997] and least squares matching [Ackermann, 1984] are treated.
A.1.1.2 Correlation at sub pixel level
Correlation at sub pixel level can be done by means of 1) fitting in a polynomial, or 2) least squares matching. Both methods presuppose temporary co-ordinates at pixel level which can be produced by it-erative use of correlation calculations, as, for instance, a calculation of the correlation coefficient or the mean square which is repeated for each pixel in a given area.
A.1.1.2.1 Fitting in of a polynomial
As it is wished to find the best fitting in at sub pixel level, the surrounding pixel co-ordinates are also re-garded, for instance, in a segment of 3 x 3 pixels. The segment is placed so that the pixel position with the optimal correlation value is in the centre of the segment. The nine correlation values are used as ob-servations for a better determination of a polynomial. A second degree polynomial is suitable for this pur-pose [Schenk et al., 1991; Kraus, 1997].
v s) ρ(r, a
s a r rsa sa ra
a
0+
1+
2+
3+
2 4+
2 5= +
A(1.6)where: r and s are the integer pixel co-ordinates
a0...a5 are the parameters which are determined by the adjustment pi(r,s) = the individual correlation coefficients within the window v = the residuals
If this equation is used as an observation equation, the coefficients ai for the polynomial can be found by an adjustment. The following equation system is set up:
l + v = A · x A(1.7)
which means:
v = A · x - l
where: l = the observations
v = random values (the residuals) A = the design matrix
x = unknown quantities If l = gT(x,y), x = r0 it follows that:
y) (x, g a r
a y a x a
y a x r a
g y) x, (
v
1 M6 3 5
4 2 1 0
S
+ −
+
+
⋅ +
⋅
=
A(1.8)where: a1, a2, a3, a4, a5, a6, r0 og r1 = temporary values v(x,y) = the residuals
The turning point of the polynomial (the sub pixel position) can then be found by differentiating. A sub pixel position can then be achieved by:
2 3 5 4
5 1 3 2
sub
4a a a
a 2a a r a
−
= −
A(1.9)2 3 5 4
3 1 4 2
sub
4a a a
a a a s 2a
− +
= −
A(1.10)[Schenk et al., 1991]. This method offers a sub pixel accuracy of 1/4 pixel [Kraus, 1997].
A.1.1.2.2 Least squares matching
To find the best correlation at sub pixel level, the least squares matching, which consists of two mations, is often used. The best correlation between two images can be regarded as an affine transfor-mation between the images. By affine transfortransfor-mation, we have 6 geometric unknown quantities: 2 moves, 2 twists and 2 scalings. Furthermore, we have 2 unknown corrections for the contrast in grey level strength. Altogether, 8 unknown quantities.
Therefore, the transformation parameters are calculated during the process, but it is only the co-ordinates of the corresponding point in the search image which are of interest.
A.1 ABM and FBM
If the correlation is done by means of least squares matching, there is, as mentioned, 8 unknown quanti-ties, 6 corrections for the approximated value of the move, and 2 corrections for the contrast in grey level strength:
-
The move in grey level values-
The change in scale-
The x-co-ordinate for the target area (gT)-
The y-co-ordinate for the target area (gT)-
The x-co-ordinate for the search area (gS)-
The y-co-ordinate for the search area (gS)-
The grey level values in the target area (gT)-
The grey level values in the search area (gS) Least squares matching in two dimensions consists of:1)
The radiometric transformation:gT(x,y) = r0 · gS(u,v) + r1 A(1.11)
↑ ↑ Target area Search area
where: gT = the grey level values for the target area x = x-position for the target area
y = y-position for the target area
r0 = estimated correction for the scaling factor in the grey levels gS = the grey level values for the search area
u = the x-position in the search area v = the y-position in the search area
r1 = estimated correction for the shift of the grey level values 2) The geometric transformation:
+
=
6 3 5
4 2 1
a a y
x a a
a a v
u
A(1.12)where: a1, a2, a4, a5 = the affinity divided into 2 scalings and 2 twists a3, a6 = the shift in the x- and y-direction
If the radiometric and the geometric transformation are put together, the following applies:
1 2y 3
1x S 0
T
a x a a r
g r y) (x,
g +
+
+
⋅ +
=
A(1.13)By assigning the target random errors (v), there will be:
1 6 3 5
4 2 1 S 0
T
r
a a y a x a
y a x g a r v y) (x,
g +
+
+
⋅ +
=
+
A(1.14)To solve this problem, an adjustment is used again by means of the least squares principle. The equation system seen in A(1.7) and A(1.8) is set up, and repeated here for clarity:
l + v = A · x which means:
v = A · x - l
where: l = the observations
v = random values (the residuals) A = the design matrix
x = unknown quantities If l = gT(x,y), x = r0 it follows that:
y) (x, g r a r
a y a x a
y a x g a
y)
v(x,
0 1 T6 3 5
4 2 1
S
⋅ + −
+
+
= +
A(1.15)where: a1, a2, a3, a4, a5, a6, r0 og r1 = estimated values v(x,y) = the residuals