International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
Figure 6. A skeleton line derived in a critical area
3. DERIVATION OF SKELETON LINES FROM
DIGITAL ELEVATION MODELS USING THE PROFILE
RECOGNITION AND POLYGON-BREAKING
ALGORITHM
Chang et al. (1998) has proposed Profile Recognition and
Polygon Breaking Algorithm (PPA) for derivation of skeleton
lines from DEMs. The algorithm consists of five procedures as
follows:
3.1 Target Recognition
The recognition is done with an algorithm that is termed the
Profile Recognition. All the points that can be recognized as
part of a ridge shape along a profile with limited length are
taken as ridge targets (Figure 7).
Figure 7. Four profiles with the lengths of seven points
The algorithm first takes the current processed point as the
centre of the profile. If it can find at least one point lower than
the central one on both sides of the profile, the central point is
taken as a ridge target. Furthermore, the profile is switched
from N-S, NE-SW- E-W to NW-SE to check whether the point
is a target or not.
This is a relatively loose recognition process compared to
traditional shape recognition because, even if a point is not a
local high along any direction, it still is possible to accept it as a
ridge target. For example, if a profile length equal to 7 points
with elevations of 1, 2, 3, 4, 3, 2 and 1, then not only is the
central point with elevation of 4 recognized, but so are its two
closest neighbors. If, on the other hand, the user takes a profile
length equal to 3, the profile recognition is reduced to a pure
shape recognition. It is suggested that profile length is selected
to be a length just long enough to recognize the possible
ambiguous targets on the map.
3.2 Target Connection
Once target recognition has been accomplished, every two
neighboring target points are connected into a segment. For this
program, in a 9-point girdded cell, the central point has eight
neighbors which are memorized as number 1 for the northern
point through number 8 for the other points in a clockwise
direction. Under this approach, many diagonal connections
cross each other and make many new junction points which are
not located on the gridded nodes. When such a situation occurs,
the process automatically gets rid of the less important
segments; for example, in a ridge search case, the segment with
lower elevation is eliminated (Figure 8).
Figure 8. Target connection
3.3 Segment Check-Out
After the processes of target recognition and connection, it is
guaranteed that all possible axes confirmed within the
connected segment groups. In this process, the unfavored
segments are cautiously eliminated one by one without
breaking the continuity of the lines. Firstly a repeated
procedure called Polygon Breaking is applied in order to check
the closed polygon and eliminate the least important segment
within each polygon until no closed polygon of any size
remains (Figure 9).
Ur == ; — T = Pd
: a ; T
S. mM D oh dis Ar
A Cr, M — ir jf A
— — “iy
Vu - hy 4 3 A Ug?
|I T Tx [ ^1. 1. -]
eth p VAN d
Do € wpe A ^ : i. T 7
ER nee hep
Li 1 CE | 3 TT?
i À + > P 1
CHICO eie pM
TT 1.71 71/1 i
HH HH rm Li i
i TT IIT Wi
[e eM Et rr rS
D
1
Figure 9. Polygon breaking
The relative importance of the segment is determined by the
elevation; for instance, in the case of ridge depicting, the
segment with lower elevation is less important than segments
with higher elevation. After this process, the remaining lines
become pure dendritic patterns all the axes are represented by
continuous segment groups with many branches instead of a
belt of closed polygons. The tracing tour starts from one end of
the weakest segment which has not been checked previously.
620
Intern
When
the tra
segme
execut
After
the ax
the br
(Figur
end-pc
are eli
than tl
34 I
This p
target
11). 7
elevat
valley
elevat
j elevat
averag
distan
351
When
simpl:
proce:
The p
type a
the us
progr:
