53 
;ween two points P 
Lmum length of all 
) within the resel. 
r line, and dotted 
1 the resel. The 
am length of all 
2 line segments are 
it with 45°. 
j-n=0 
s of the (i-m) and 
D 
) and (j-n) are not 
distance. For easy 
o let J=3 and 1=2. 
adjacent points P 
k-). The length of 
^(Pi .P i+1 )- The 
ints P,Q within a 
paths within the 
ig.3). 
e which delineates 
point on Z. The 
Q within the resel 
•(Q.P) 
in to the bordering 
¡ome closed contour 
it. Let denote 
1 elevation values 
or point P of this 
different E's which 
is of the effective 
distance. That is, if 
D(P,Z i)<D(P,Z 2 )^D(P,Z 3 ) 
then Z x and Z 2 are chosen, provided that Ei 35E2 . 
However, if Ej^ =E 2 then Z3 shall be chosen in stead of 
Z 2 , and so forth. The interpolated elevation value 
at P is then 
E.xW(P,Z.¡)+E xW(P,Z 
E(P) ^ (1) 
W(P,Z i )+W(P,Zj) 
where Z^ and Z- are the chosen curves. The 
weighting function W(P,Z) can be any monotonously 
decreseing function of D(P,Z). We use W(P,Z)= 
1/D(P,Z) 
Some of the resels may be surrounded by a single 
closed contour line to represents a local extreme of 
a terrain, or located between an open contour line 
and the edge of the image. In either cases, the 
above equation cannot be applied because two 
different E's can not be found for such a resel. For 
simplicity, we can fill up these resels with the 
same elevation value, thus create some flat plateaus 
or valleys. Or, we may, by adding a "peak point" in 
the resel during the last two steps of the 
prepocessing, creat an artificial peak point for this 
resel. The above interpolation equation can be 
applied again. 
5. A fast algorithm for finding D's and E's 
In a image of size N M, each pixel can be denoted 
by a pair of integers(i,j), with Ki<N and l<j<M. 
With the chosen W(P,Z)=1/D(P,Z)»Equation (1) in the 
last section may be rewritten as: 
e a(ì. j) d b( ì > j)D A (i, J) 
E(i, j)= ? -- (2) 
D A (i, j)+%(i, j) 
Subscript A(or B) indicates that E A (or Eg) and Da(or 
Dg) associate with the contour line Z A (or Zg). 
For fast computation, a "scanning and revising" 
method is derived to determine these two pairs of D's 
and E's. For the sake of simplicity, only the 
essential features are described below. 
(1) Initiation: For each pixel on the contour 
line, let D^=Dg=0 and E A =E B =elevation value of the 
contour line. For each pixel not on the contour 
line, let D.=Dg=some large number, say M+N, and 
E A =E B=° 
Fig. 4. The center square represents the current 
pixel. The squares (1), (2), (3) and (4) are used 
for the "forward" scanning and revising. The squares 
(5), (6), (7) and (8) are used for "backward" 
scanning and revising. 
(2) Forward (left-and-down) scanning and revising: 
Pick up the pixels one by one in the sequence (1,1), 
(2,1), (N,1), (1,2), (2,2) (N,M). For a 
given pixel(i,j), E A , Eg, D A and Dg are revised 
according to following rules: 
Rule(i):If D A (i,j)=Dg(i,j)=0, then the pixel is on 
the contour line, no revision is enacted. 
Rule(ii):If D A (i,j) and Dg(i,j) are nonzero, the 
original pairs, 
D A (i.j), E A (i,j),Dg(i,j),Eg(i,j) 
are to be compared with other 8 pairs of E's and D's. 
They are calculated from 4 
pixels adjacent to (i,j) 
(see Fig.4) 
D A (i-l,j-l)+3; 
E A (i-l,j-1) 
D B (i-l,j-l)+3; 
E B (i-l,j-1) 
D A (i,j-1)+2; 
E A (i,j-l) 
D B (i,j-l)+2; 
E B (i,j-l) 
D A (i+l, j-l)+3; 
E A (i+1,j-1) 
DßCi+l » j~l)+3; 
E B (i+l, j-1) 
D A (i-l, j)+2; 
E A (i-1, j ) 
D B (i-l,j)+2; 
E B (i-l,j) 
However, if any of the indies is outside the range 
(i.e., i-l=0, j—1=0 or j+l>M), the corresponding pair 
does not exist. Also, if both DA(i-l,j)=0 and 
D A (i,j-l)=0, the pairs computed from the pixel (i-1, 
j-1) shall be disregarded, because (i—1,j—1) and 
(i,j) will belong to different resels. 
Rule(iii): Among these pairs, if all the E's are 
equal, select two pairs with least D's to be the new 
D A (i,j), E.(i,j) and Dg(i,j) , Eg(i,j). If the E's 
are not all equal, select the two pairs with least 
D's and different E's to be the new D A (i,j), E A (i,j), 
Dg(i,j), Eg(i,j). 
(3) Backward scanning and revising: This 
is the same as (2), except the scanning sequence is 
exactly the opposite and the 4 comparing pixels are a 
mirror image of above as shown in Fig. 4. 
(4) The forward and backward scanning cycles may be 
repeated until no revision occurs. 
Unless the image contains some resels of unusual 
(whirling or wriggling) shapes, two or three cycles 
are sufficient to terminate the process. 
To examine the feasibility of implementing the 
algorithms discussed in the previous sections, we 
select a 10cm x 10cm section out of a topomap sheet 
with the scale of 1/50,000. The region chosen covers 
Te-chi Reservior and high mountainous terrain with 
local peaks around 3000 meters in altitude. The 
complexity of the topography is particularly suitable 
for demonstration. 
Fig. 1, shown in section 2^, represents the line- 
drawn contour map to be digitized and interpolated. 
Aside from isolated peaks and water surface, typical 
interval between two adjacent contour lines is 100 
meters. 
Following the preprocessing steps described in 
Section II, we obtains a labeled contour-line map 
with different colors representing different 
elevation value as depicted in Fig. 5. The final 
result, followed by the interpolation scheme 
discussed in Section IV, is illustrated in Fig. 6. 
The color scale is shown on the right side of the 
figure, with red (or purple) color for highest (or 
lowest) elevation level. The color contour lines are 
superimposed in the figure for comparisons. In a 
complicated terrain like this example, we are able to 
demonstrate the capability of our algorithms to 
generate a digital elevation model.