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.