t the 
ution 
milar 
to the choice of the mesh-width which characterizes the 
resolution of a DTM given by a height matrix. The coef- 
ficients c(z) of the functional expansion (3) in connection 
with the functional parameter r represent the DTM in our 
approach. This approximation method is tested on several 
artificial and practical examples in (Brand, 1994) for dif- 
ferent sets of reference points and basis points. It works 
well but has the following drawbacks : 
e A suitable value for the region of influence r is not 
known in advance. Its choice can be very delicate. 
e |f the characteristic scale of the reference points 
varies in space, one has to choose the value of r 
according to the smallest feature of the scale size 
in the region. If not doing so, essential information 
may be lost. A spatially variable value of r would 
be appropriate in this case. 
e The error of the DTM can only be calculated at the 
end of the process. An improvement requires a com- 
pletely new run with modified r and/or modification 
of the given grid. 
These drawbacks can be avoided by a hierarchical algo- 
rithm. 
3 THE NEW ALGORITHM 
The new algorithm can be described as follows 
(1) Choose a relatively small scale parameter ro (large 
spherical caps) and relatively coarse basis grid l'o. 
(ii) Compute an approximation go from (3). 
(i) Compute the error Ei at the given data (reference 
points). 
(iv) Decide wether E; is sufficiently small in all parts of 
the domain. If true stop. 
(v) Increase the scale parameter to r1 (smaller spherical 
caps) and refine the basis grid (grid of coefficients) 
to I4 
(vi) Compute the approximation of the discrete error Fi 
in those parts of the domain where F1 is above the 
threshold in (iv). Add this contribution to the ap- 
proximation obtained in (zz). 
(vii) Iterate steps (121) to (vi) up to the situation where 
(a) The error £j; is sufficiently small in the whole 
domain or 
(b) The refinement of the grid I'; approaches a cell 
size where the number of points from = that 
serve to determine a particular coefficient de- 
creases below a threshold which ensures suffi- 
cient averaging 
Profiles along the equator of the resulting succesive ap- 
proximation (first 3 steps) for an artificial example are 
represented in Figure 4. The height of the reference points 
are plotted as circles, the basis points as crosses. 
This algorithm is characterized by different resolution and 
the adaptive choice of the basis points. First tests have 
been conducted with several basis grids described in (Free- 
den, Schreiner, 1993). In (Brand, et al., 1995) a different 
151 
  
  
  
  
  
  
  
  
  
  
  
Figure 4: Synthetic example, profiles along the equator for 
different levels of approximation 
hierarchical grid with tree structure has been employed 
which considerably speeds up the computation. It can be 
described as follows : each point of a grid I'; has n sons 
located in the neighbourhood of this point. The union 
makes up Ll';j41. With respect to the unit square, which 
can be transformed to the sphere, a sequence of basis grids 
reads To = ((1/2,1/2)) T1 — ((1/4, 1/2); (3/4, 1/2)], 
T» — ((1/4, 1/4); (1/4, 3/4); (8/4, 1/4); (3/4, 3/4)) and so 
on, each of the previous points having two sons alternately 
in horizontal and vertical direction. This organization al- 
lows easy and efficient management of the basis points. 
Similarly, the hierarchical organization of the data points 
in form of a quadtree (see e.g. Samet, Weber, 1988) is 
introduced for very large data sets. By sorting the given 
reference points as well as the above defined basis grids 
according to their latitudes the calculation of the sums (3) 
is simplified. The calculation of the scalar product has 
only be done in a small region around the sampling point, 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996