Warning: include_once(../article_type.php): failed to open stream: No such file or directory in /home/suxhorbncfos/public_html/cerj/CERJ.MS.ID.555709.php on line 199
Warning: include_once(): Failed opening '../article_type.php' for inclusion (include_path='.:/opt/alt/php56/usr/share/pear:/opt/alt/php56/usr/share/php') in /home/suxhorbncfos/public_html/cerj/CERJ.MS.ID.555709.php on line 199
Extraction of Topographic Structure Lines from Digital Elevation Model Data
Victor JD Tsai1* and Chin-Ting Lin2
1Department of Civil Engineering, National Chung Hsing University, Taiwan
2Yu Zhan Surveying and Mapping Co., Ltd, Taiwan
Submission: January 28, 2019; Published: February 07, 2019
*Corresponding Author:Victor JD Tsai, Department of Civil Engineering, National Chung Hsing University, Taiwan
How to cite this article:Victor JD Tsai, Chin-Ting Lin. Extraction of Topographic Structure Lines from Digital Elevation Model Data. Civil Eng Res J.
2019; 7(2): 555709. DOI: 10.19080/CERJ.2019.07.555709
Topographic structure lines, including valley lines and ridge lines, represent the skeletons of topographic variation and play important roles in both hydrological analysis and terrain analysis. This research examined two major traditional algorithms, i.e., the running water simulation method and the profile analysis algorithm and developed an iterative filtering -segmentation approach based on image processing techniques for deriving topographic structure lines from Digital Elevation Model (DEM) data. Experimental results from different methods were compared with respect to the accuracy of feature extraction and computational efficiency. It is shown that the proposed iterative filtering-segmentation approach is the most efficient method among these methods.
Topographic structure lines, including ridge lines and valley lines, delineate the most prominent skeleton structures of the land forms. Extraction of topographic structure lines plays an important role in various fields where topographic features are used in spatial analysis such as hydrological applications, military applications, hazard prediction, hiking and mountain climbing, relief representation and delineation. Traditionally, these structure lines were manually interpreted from hardcopy topographic maps which indicate continuous topographic surface by contours. With the aid of digitizing devices, topographic features on the topographic maps were digitized and converted into a digital terrain model (DTM) that contains elevation information and some explicit coding of surface characteristics such as peaks, pits, break lines, boundaries, etc. Many forms of DTM have been used to describe the terrain surface digitally, including digital contour model (DCM) with form lines of equal elevation, digital elevation model (DEM) in a two-dimensional regular-spaced grid of sampled elevations, or triangulated irregular network (TIN) of irregularly distributed topographic features. Among them, DEMs in gridded matrix form can be easily acquired by different approaches and are ubiquitous in various applications, including gradient/slope/aspect analysis in geographical information systems (GIS), terrain synthesis,
detection of drainage networks, extraction of skeleton lines or ridge and valley lines [1-9].
The mainstream methods for terrain skeleton line extraction from DEMs can be divided into two categories: physical water flow simulation-based methods and geometrical morphological analysis-based methods . The former conduct water flow or running water simulation on terrain surface, on which course pits were removed first and flow direction matrix and flow accumulation matrix are constructed . Valley lines are then formed by labeling feature points whose flow accumulation amount is greater than a predefined threshold, and ridge lines are obtained by extracting watershed boundaries (divides). Variations of the water flow simulation approaches include single flow direction or D8 (Deterministic eight-node) approach , Multiple flow direction approach, D-Infinity approach and were implemented in various GIS software, e.g., ArcGIS (D8), IDRISI (D8), and TauDEM (D8 & D-Infinity) [10,11]. However, these methods always suffer from inefficiency, drawbacks in pits removal, flow direction judgement on flat areas, and closed loop of ridge lines .
The geometric approaches identify feature candidates by analyzing terrain profile with a roving window for extracting terrain feature lines. For examples, a 2×2 window was used to scan the DEM data in which the highest point was labeled as
ridge candidate and the lowest as valley candidate . Chang et
al.  proposed a profile-analysis based approach named Profile
recognition and Polygon breaking Algorithm (PPA) to extract
feature lines by lowering the criteria for ridge candidates,
feature connection, polygon breaking, pruning and smoothing.
Zhang et al  proposed Morphological Profile recognition and
Polygon breaking Algorithm (MPPA) to improve PPA’s efficiency
and accuracy. Zou &Weng  proposed an improved gradientbased
profile analysis algorithm by adopting improved Sobel
filters in calculating the gradient-based water flow direction,
followed by a global profile analysis to identify both strong
and weak feature points, feature extension, polygon breaking,
pruning and smoothing.
This paper presents an iterative filtering-segmentation
approach based on image processing techniques to derive
topographic structure lines from DEM data. Procedures of the
proposed approach is introduced in the following section.
Experimental results from the proposed approach, running
water simulation-based method, and profile analysis algorithm
were compared with respect to the accuracy of valley line and
ridge line extraction and computational efficiency.
As shown in Figure 1a, a 362×336 subset of 40-m grid DEM
data of the mountainous Alisan area, Chiayi County, Taiwan
was used as test example. The DEM data were produced using
traditional photogrammetric profiling approach by Aerial
Survey Office, Forestry Bureau, Council of Agriculture, Taiwan.
As shown in Figure 1b, the ground truth of valley lines was
obtained by on-screen manual digitization of digital copy of
1/25,000 topographic maps using Adobe Photoshop CS software.
The ground truth of ridge lines was not digitized for comparison
due to lack of such information in the topographic maps.
The main idea in the proposed iterative filteringsegmentation
approach is to treat the gridded DEM data as a
digital image, i.e., DEM image in the form of Z = f (x, y) . Iterative
process of high-pass filtering, segmentation by thresholding,
and masking was employed to extract topographic structure
lines from the DEM image. The high-pass filtering is a spatial
convolution operation as shown in Eq. (1) and Figure 2a. For
ridge line extraction, a high-pass filter w N×N is a N×N kernel
window as shown in Eq. (2) for N=5 as examples. For valley line
extraction, on the other hand, a negative high-pass filter, e.g.,
w' w × × = − N N N N , is used instead of w N×N in the filtering process.
In the segmentation process, the filtered result g(x, y) was
segmented as a binary mask by setting a threshold value of
zero to distinguish pixels higher (ridge lines using w N×N filter)
or lower (valley lines using w' N×N , filter) than most of their
surrounding neighbors as shown in Figure 2b . For the masking
process, the binary mask applies to the DEM image to preserve
the elevations of pixels within the areas of interest, e.g., ridge
lines or valley lines, while suppress the elevation of other
pixels to zero for the next iteration. These steps repeat until the
ridge/valley lines were converged to 1-pixel width through line
thinning  and pruning to remove noise as shown in Figure
2c,d. Note that the high-pass filter w N×N and negative high-pass
filter w' N×N may become smaller in the size of kernel window and
both apply only to the pixels with non-zero value in the second
and after iterations as shown in Figure 2c.
The D8 running water simulation method, profile analysis
algorithm, and the proposed iterative filtering -segmentation
approach was implemented in MATLAB programs under
Microsoft Windows with Core2 Due T7300 CPU and 2MB RAM
for extracting ridge lines and valley lines from the DEM. A
digital copy of 1/25,000 topographic map of the test area was
downloaded from the Ministry of the Interior, Taiwan for onscreen
manual digitization of the valley lines as ground truth for
the accuracy assessment of the three methods.
For the running water simulation method, the original DEM
was pre-processed to remove pits and the threshold of flow
accumulation was set as 500 in extracting valley lines .
Figure 3 shows the intermediate results in flow direction matrix,
flow accumulation matrix, and extracted streams with different
thresholds in flow accumulation. For the profile analysis
algorithm, the four-direction (horizontal, vertical, and two
diagonal) profiles were employed to detect candidate features
and the original DEM was filtered with a 31×31 high-pass filter
to generate a mask for overlapping with the detected candidate
features, followed by noise removal and pruning for the final
results as shown in Figure 4. For is used by employing the same procedures in the running water simulation method and
profile analysis algorithm. For the proposed iterative filteringsegmentation
approach 31 31 w × , and '
31 31 w × filters were applied
to the DEM image, followed by segmentation to abinary mask
in the first iteration. Further, 21 21 w × and '
21 21 w × filters and 5 5 w ×
5 5 w × filters were employed during the second and third
iterations, respectively. Figure 5 shows the intermediate results
of the proposed approach.
As a summary, Figure 6 shows the final results of extracted
valley lines and ridge lines overlapping on the original DEM
image, respectively. It illustrates that the running water
simulation method is not suitable for extracting ridge lines
because ridge lines do not have the physical characteristics of
continuous downhill slope on conjugate topographic surface. On
the contrary, both profile analysis algorithm and the proposed
iterative filtering-segmentation approach are not limited by
this constraint by applying filtering techniques. Table 1 shows
the accuracy assessment on valley line extraction according
to the concept in classification error matrix . The results
demonstrate that the proposed iterative filtering-segmentation
approach is the most efficient in extracting valley lines with the
same level of overall accuracy as the other two methods. Most
of the errors in the proposed approach are caused by the short
and small structure lines that were eliminated in the high-pass
filtering process. Meanwhile, conjugate topographic surface is
not required in the proposed terative filtering-segmentation
approach by applying a high-pass filter, i.e., wN×N , and its
negative, i.e., w' N×N , over the original DEM data to extract ridge
lines and valley lines, respectively.
Topographic structure lines, including valley lines and ridge
lines, represent the skeletons of topographic variation and
play important roles in both hydrological analysis and terrain
analysis. This research examined the running water simulation
method and the profile analysis algorithm and developed an
iterative filtering-segmentation approach based on image
processing techniques for deriving topographic structure lines
from Digital Elevation Model (DEM) data. Experimental results
from the three methods illustrate that the proposed iterative
filtering-segmentation approach is the most efficient method
among these methods with the same level of overall accuracy.
The running water simulation approach is not suitable for ridge
line extraction because ridge lines do not have the physical
characteristics of continuous downhill slope in conjugate
topographic surface. Both profile analysis algorithm and the
proposed iterative filtering-segmentation approach are not
limited by this constraint. Meanwhile, conjugate topographic
surface is not required in the proposed iterative filteringsegmentation
approach by applying a high-pass filter, i.e., wN×N ,
and its negative, i.e., w' N×N , over the original DEM data to extract
ridge lines and valley lines, respectively.