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)
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
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.
