on the
dotted
> errors
timate.
and as
nts has
around
ICY Was
t on the
ed lines
he DCT
radually
fficients
ut 75%
average
is Wert
Average Match Time for Converged Match Windows
T T T T
Rob Reeves
Average Match Time for Converged Match Windows
T T
1000r— 777717 T pre à 800 Ra Ene RA T T i 1 ;
e——o 8x8- TD | e— o "$xa- Tp. |
2 |e 6x6 - PD H 700 o O 6x6-PD |
&—— A 16x16. TD 4—— A 16x16 - TD PS !
800r |^ ^ 14x14 - PD E 4 ^ 14x14- PD Tee
[n——ns 82x32 - TD ui = 2 92x32 — TD
700} dà o 30x30-PD |? a 30x30 - PD
ce a vu = 500 - Ts i
$ 600 a p
2 $ |n
d 5000 8 = 400 |
s = |
z z |
© E p m
É 400 d Él I R/ gi |
bly
A
s 200 - |
A A —— 4
AA E remiss A
A ic =
WOR IN a . eran
eo OS
+ 1 1 i 1 a
|
0 10 20 30 40 50 60 70 80 90 100
Percentage of DCT Coefficients Taken in Least Squares Adjustment
Percentage of DCT Coefficients Taken in Least Squares Adjustment
Figure 6: The effect of taking only a fraction of the available DCT coefficients in each least squares adjustment on the
average time taken to converge for each match window. The times for the pixel domain al gorithms are shown as dotted
horizontal lines for comparison. Results are shown for the “Redland” imagery (left) and the “Willunga” imagery (right).
6.5 Optimum Percentage of DCT Coefficients
For the images that we examined, and the larger window sizes, it was possible to select a percentage of DCT coefficients
that resulted in improved speed over the pixel domain algorithm, and comparable or better accuracy, mean error, and
number of converging match windows. For the 32 x 32 window, taking around 10% of the DCT coefficients resulted in a
speedup of more than two times, while maintaining or bettering the other measures of matching quality. For the 16 x 16
window, the speedup was more modest reducing the average match time to 75% or less of its value for the pixel domain
algorithm. This was achieved by taking around 20% of the DCT coefficients. The other measures of matching quality
were all comparable or better than for the pixel domain. For the 8 x 8 window, taking around 50% of the DCT coefficients
resulted in improvements to the number of converging match windows, with comparable accuracy and bias, but at the
expense of in increase in the average match time by up to I. Whether these specific optimums apply generally can only
be answered by further research.
7 DISCUSSION
It was predicted that by matching in the transform domain using only a proportion of the available DCT coefficients,
matching could be achieved more quickly. This has been shown to be true for match windows of 16 x 16 and 32 x
32. However the overhead of the DCT domain algorithm outweighed any speed increase for the 8 x 8 window. The
development of fast algorithms for the transformation of Equation 7 holds the potential for significantly greater reductions
in match time.
Matching quality, as measured by the standard deviation of the disparity errors, tended to improve in the transform
domain. One possible reason is that by discarding high frequency terms, image noise that is detrimental to matching, is
also discarded. Theoretical results by Fórstner (Fórstner, 1982) suggest that matching accuracy is improved by low pass
filtering to exclude such high frequency noise. In this case a slight upward trend in the standard deviation of the disparity
errors would be expected as the percentage of DCT coefficients increases towards 100%. Scrutiny of Figure 5 shows that
such an effect is minor if it can be discerned at all. The explanation must therefore lie in some difference in the way the
two algorithms operate. One difference between the two algorithms is in the size of the match window. The pixel domain
match window is reduced to a side of size N — 2 where N is the side length of the transform domain match window.
This could influence the results, as the smaller match window size would be expected to lead to lower accuracies and
fewer converging match windows in the pixel domain, but faster pixel domain match times. Our results could therefore be
overstating improvements in matching quality, and understating the improvements in matching time. However, the slight
reduction in pixel domain window size cannot, by itself, account for the improvements in matching quality achieved in
the DCT domain. This can be deduced by considering the pixel domain 30 x 30 case for the “Redland” image, in which
the standard deviation of the disparity errors is 0.19 pixels. In the transform domain 16 x 16 case for the same image,
the standard deviation of the disparity errors is for the most part better than this when a reasonable proportion of DCT
coefficients is taken. This is illustrated in Figure 5. Normally a smaller match window would be expected to result in a
greater standard deviation of the disparity errors, due to there being less information available in the window for matching.
All other factors being equal, it must be concluded that there is another factor besides window size operating to improve
the standard deviation of the disparity errors in the transform domain. The only other significant difference between the
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 767
