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
Abstract
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.
Keywords: Topographic structure lines; Digital elevation model; High-pass filtering; Segmentation; Feature extraction
Abbrevations: DCM: Digital Contour Model; DEM: Digital Elevation Model; DTM: Digital Terrain Model; GIS: Geographical Information Systems; TIN: Triangulated Irregular Network
Introduction
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 [7]. 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 [5]. 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 [3], 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 [9].
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 [12]. Chang et al. [6] 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 [8] proposed Morphological Profile recognition and Polygon breaking Algorithm (MPPA) to improve PPA’s efficiency and accuracy. Zou &Weng [9] 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.
Material and Methods
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 [13] 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.
Results
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 [14]. 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 × and ' 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 [15]. 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.
Conclusion
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.
References
- De Smith MJ, Goodchild MF, Longley PA (2018) Geospatial Analysis–A Comprehensive Guide‐2018. (6th edn), California, USA.
- Zhou H, Sun J, Turk G (2007) Terrain Synthesis from Digital Elevation Models. IEEE Transactions on Visualization and Computer Graphics 13(4): 834-848.
- O’callaghan JF, Mark D (1984) The Extraction of Drainage Networks from Digital Elevation Data. Computer Vision, Graphics, and Image Processing 28(3): 323-344.
- Band LE (1986) Topographic partition of watersheds with digital elevation models. Water Resources Research 22(1): 15-24.
- Jenson SK, Domingue JO (1988) Extracting Topographic Structure from Digital Elevation Data for Geographic Information System Analysis. Photogrammetric Engineering and Remote Sensing 54(11): 1593- 1600.
- Chang YC, Song GS, Hsu SK (1998) Automatic Extraction of Ridge and Valley Axes Using the Profile Recognition and Polygon-Breaking Algorithm. Computers & Geosciences 24: 83-93.
- Gülgen F, Gökgöz T (2004) Automatic Extraction of Terrain Skeleton Lines from Digital Elevation Models. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 35(3): 372.
- Zhang H, Ma Z, Liu Y, He X, Ma Y (2013) A New Skeleton Feature Extraction Method for Terrain Model Using Profile Recognition and Morphological Simplification. Mathematical Problems in Engineering 2013: 523729.
- Zou K, Weng H (2017) Terrain Feature Line Extraction by Improved Gradient-Based Profile Analysis. International Journal of Signal Processing, Image Processing and Pattern Recognition 10(3): 1-12.
- Quinn P, Beven K, Chevallier P, Planchon O (1991) The prediction of hillslope flow paths for distributed hydrological modelling using digital terrain models. Hydrological Processes 5(1): 59-79.
- Tarboton DG (1997) A new method for determination of flow direction and upslope areas in grid digital elevation models. Water Resources Research 33(2): 309-319.
- Peucker TK, Douglas DH (1975) Detection of Surface-Specific Points by Local Parallel Processing of Discrete Terrain Elevation Data. Computer Graphics and Image Processing 4(4): 375-387.
- Pavlidis T (1980) A Thinning Algorithm for Discrete Binary Images. Computer Graphics and Image Processing 13(2): 142-157.
- Planchon O, Darboux F (2001) A fast, simple and versatile algorithm to fill the depressions of digital elevation models. Catena 46: 159-176.
- Lilles TM, Kiefer RW, Chipman JW (2015) Remote Sensing and Image Interpretation (7th edn), Wiley Publishing, Hoboken, New Jersey, USA.