Rob Reeves 
  
Original Sequence Periodic extension in 2N Increasing DCT Frequency 
> 
  
| 
| Reflection around end point | 
| 
  
Discontinuituy 
causes ringing 
Increasing DCT Frequency 
DFT 
  
  
  
  
  
  
  
D Figi 
0 N 2N 3N ! AN 
  
  
  
  
  
  
  
  
  
  
  
» à - (left 
: T A st 
Periodic extensions in N 
then 
and 
Figure 1: The symmetric extension inherent in the DCT is contrasted to the periodic extension inherent in the discrete by f 
Fourier transform (left). Ordering the DCT coefficients along the diagonals, or zig-zag order, starting with the DC | 
coefficient, results in an order that approximately corresponds to decreasing energy of the components (right). ever 
( 
Zig-zag order is shown in Figure 1, and results in coefficients being selected roughly in order of increasing frequency and m 
decreasing information content (Wallace, 1991). mor 
texti 
A range of values of n were taken in order to explore the change in behavior as more or less of the DCT coefficients were — | orde 
used in the least squares adjustment. The measures used to compare the performance of the two algorithms were (1) the freq 
proportion of match windows which converged (Figure 3), (2) the mean error in the disparity measurement (Figure 4), 
(3) the standard deviation of the disparity error (Figure 5), and (4) the average time taken to reach convergence in each 
match window (Figure 6). The notation 'PD' in the legend of the figures indicates the pixel domain algorithm, while 
the notation *TD’ indicates the transform domain. The cases where the algorithm failed to converge were not included 
in the calculation of the average number of iterations, mean error, or the standard deviation of the disparity error. The 
comparison was made using three window sizes in the DCT domain, 8 x 8, 16 x 16 and 32 x 32. To make sure that the 
same set of window patches were matched in the pixel domain, the effective window sizes had to be reduced by one pixel | 
at each edge, due to constraints inherent in the experimental software. The algorithms were compared using two fragments 
of aerial images. In each case, a stereo pair was created with known uniform horizontal disparity of 0.5 pixels, by shifting : 
the image by an integral number of pixels, and then low pass filtering and subsampling the shifted and unshifted images. 
The image fragments used are shown in Figure 2, and details of the original imagery are shown in Table 1. 
Redland Willunga 
Height 6503m 7575m | 
Focal length 303.71mm 153.02mm | 
Pixel size 22.5um 22.5um | 
Terrain Forest, isolated trees | Flat agricultural 
Table 1: Details of the image sets used in the comparison. Ry 
The algorithm was programmed in the Java programming language, using JDK 1.1.6, running under Windows NT 4.00 on ima; 
a Pentium Pro PC with 32 Mbytes of RAM and a 100MHz CPU. The least squares system was solved by matrix inversion, 
and DCT's were performed using a fast algorithm. Aside from this, no other attempt was made to optimize the code. 62 
| 
6 EXPERIMENTAL RESULTS | The 
| As I 
6.1 Number of Converging Match Windows coef 
wing 
As can be seen from Figure 3, taking more than 25% of the DCT coefficients resulted in the same or more converging coef 
match windows as for the pixel domain algorithm. For larger windows, the required percentage of DCT coefficients is larg 
  
764 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.