Published

2016-04-01

An algorithm for generation of DEMs from contour lines considering geomorphic features

Keywords:

Digital Elevation Models (DEM), interpolation points, contour lines map, geomorphic features, Modelos de Evaluación Digital, puntos de interpolación, mapas lineales de contorno, características geomórficas. (en)

Downloads

Authors

  • Xiao-Ping Rui
  • Xue-Tao Yu
  • Jin Lu
  • Muhammad Aqeel Ashraf Faculty of Science and Natural Resources, University Malaysia Sabah 88400 Kota Kinabalu Sabah, Malaysia
  • Xian-Feng Song

Geomorphic information is omitted from many existing methods of generating gridded digital elevation models (DEMs) from contour lines, resulting in significant errors during interpolation. Here, we present an advanced schema for improvement of the comprehensive regionalized method of linear interpolation. This approach uses a moving fitting method for an interpolated point and selects elevation points that are representative of geomorphic features as a whole to improve interpolation quality. A total of 16 points are selected, according to certain criteria, in eight directions surrounding the interpolated point; thus, there are two points in each direction, which is sufficient to provide an accurate representation of the geomorphic features of the DEM. Our method introduces virtual control points to prevent sudden changes in the interpolation results, which helps to overcome problems related to the distortion of the local geospatial distribution in areas where feature geomorphic information is inadequate. We construct the spline interpolation function using intersection points and virtual control points, all of which are applied to compute the point elevation. Moreover, we index all elevation values and spatial points of linear features using the R-tree method to ensure that points related to an interpolated position can be retrieved as quickly as possible. Finally, we test our method using a coal mine elevation dataset. The results confirm that our proposed method can generate DEMs smoothly and, in particular, avoid problems related to local distortion. 

 

Resumen

La información geomórfica se omite en muchos de los métodos de generación de Modelos Digitales de Elevación (DEM, en inglés) que se elaboran a partir de líneas de contorno, lo que resulta en errores significativos durante la interpolación. En este trabajo se presenta un esquema avanzado para el mejoramiento del método comprensivo regionalizado de interpolación lineal. Esta aproximación utiliza un método de ajuste móvil para un punto interpolado y selecciona puntos de elevación representativos o características geomórficas como un todo para mejorar la calidad de la interpolación. Se seleccionaron 16 puntos de acuerdo con ciertos criterios, en ocho direcciones alrededor del punto interpolado; por lo tanto, hay dos puntos en cada dirección, lo que es suficiente para proveer una representación precisa de las características geomórficas del DEM. El método propuesto consta de puntos virtuales de control para prevenir cambios repentinos en los resultados de la interpolación, lo que ayuda a vencer los problemas relacionados a la distorsión de la distribución geoespacial local en áreas donde la información de las características geomórficas es inadecuada. Se utilizó una función de interpolación spline con puntos de intersección y puntos de control virtual, que fueron utilizados para calcular el punto de elevación. Además, se indexaron todos los valores de elevación y los puntos espaciales de las características lineales con el método de árbol-R para asegurar que los puntos relacionados a una posición interpolada pueden ser recuperados tan rápido como sea posible. Finalmente, el método fue evaluado con la configuración de elevación de una mina de carbón. Los resultados confirman que el método propuesto puede generar modelos sin problemas y, en particular, evitar complicaciones relacionadas a distorsión local. 

References

Aumann, G., Ebner, H. & Tang, L. (1991). Automatic derivation of skeleton lines from digitized contours. ISPRS Journal of Photogrammetry and Remote Sensing, 46, 259–268. DOI: 10.1016/0924-2716(91)90043-U

Binh, T. Q. and Thuy, N. T. (2008). Assessment of the influence of interpolation techniques on the accuracy of digital elevation model. VNU Journal of Science, Earth Sciences, 24(4), 176–183.

Bonin, O., & Rousseaux, F. (2005). Digital Terrain Model Computation from Contour Lines: How to Derive Quality Information from Artifact Analysis. Geoinformatica, 9(3), 253–268. DOI: 10.1007/s10707-005-1284-2

Bouillon, A., Bernard, M., Gigord, P., Orsoni, A., Rudowski, V., and Baudoin, A. (2006). SPOT 5 HRS geometric performances: Using block adjustment as a key issue to improve quality of DEM generation. ISPRS Journal of Photogrammetry and Remote Sensing, 60(3), 134–146. DOI: 10.1016/j.isprsjprs.2006.03.002

Carley, J. K., Pasternack, G. B., Wyrick, J. R., Barker, J. R., Bratovich, P. M., Massa D. A., ... Johnson T. R. (2012). Significant decadal channel change 58-67 years post-dam accounting for uncertainty in topographic change detection between contour maps and point cloud models. Geomorphology, 179, 71–88. DOI: 10.1016/j.geomorph.2012.08.001

Carrara, A., Bitelli, G., & Carla, R. (1997). Comparison of techniques for generating digital terrain models from contour lines. International Journal of Geographical Information Science, 11(5), 451–473.

Chen, X., Ma, W., Xu, G., & Paul, J. C. (2010). Computing the Hausdorff distance between two B-spline curves. Computer-Aided Design, 42(12), 1197–1206. DOI: 10.1016/j.cad.2010.06.009

Clarke, A. L., Gruen, A., & Loon, J. C. (1982). The application of contour data for generating high fidelity grid digital elevation models. Proceedings Auto-Carto 5, 213–222. Washington DC.

Corral, A., & Almendros-Jiménez, J. M. (2007). A performance comparison of distance-based query algorithms using R-trees in spatial databases. Information Sciences, 177(11), 2207–2237. DOI: 10.1016/j.ins.2006.12.012

Curry, H. B., & Schoenberg, I. J. (1996). On Pólya frequency functions IV: The fundamental spline function and their limits. Journal d’Analyse Mathematique, 17(1), 71–107. DOI: 10.1007/BF02788653

Dinis, L. M. J. S., Natal Jorge, R. M., & Belinha, J. (2007). Analysis of 3D solids using the natural neighbour radial point interpolation method. Computer Methods in Applied Mechanics and Engineering, 196(13– 16), 2009–2028. DOI: 10.1016/j.cma.2006.11.002

Doytsher, Y., & Hall J. K. (1997). Interpolation of DTM using bi- directional third-degree parabolic equations, with FORTRAN subroutines. Computers & Geosciences, 23(9), 1013–1020. DOI: 10.1016/S0098-3004(97)00061-7

Gofuku, S., Tamura, S., & Maekawa, T. (2009). Point-tangent/point-normal B-spline curve interpolation by geometric algorithms. Computer- Aided Design, 41(6), 412–422. DOI: 10.1016/j.cad.2009.02.005

Gousie, M. B., & Franklin W. R. (2003). Constructing a DEM from grid- based data by computing intermediate contours. In GIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems, 71–77. DOI: 10.1145/956676.956686

Hearnshaw, H. M., & Unwin, D. J. (1994). Visualization in Geographical Information Systems. Chichester: Wiley, 168–180.

Heritage, G. L., Milan, D. J., Large, A. R. G., & Fuller, L. C. (2009). Influence of survey strategy and interpolation model on DEM quality. Geomorphology, 112(3–4), 334–344. DOI: 10.1016/j. geomorph.2009.06.024

Hickey, R., Smith A., & Jankowski P. (1994). Slope length calculations from a DEM within ARC/INFO grid. Computers, Environment and Urban Systems, 18(5), 365–380. DOI: 10.1016/0198-9715(94)90017-5

Huang, F., Liu, D., Tan, X., Wang, J., Chen Y., & He, B. (2011). Explorations of the implementation of a parallel IDW interpolation algorithm in a Linux cluster-based parallel GIS. Computers & Geosciences, 37(4), 426–434. DOI: 10.1016/j.cageo.2010.05.024

Huang, P. W., Lin, P. L., & Lin, H. Y. (2001). Optimizing storage utilization in R-tree dynamic index structure for spatial databases. Journal of Systems and Software, 55(3), 291–299. DOI: 10.1016/S0164-1212(00)00078-9.

Hung, W., & Yang, M. (2004). Similarity measures of intuitionistic fuzzy sets based on Hausdorff distance. Pattern Recognition Letters, 25(14), 1603–1611. DOI: 10.1016/j.patrec.2004.06.006

Hutchinson, M. F. (1988). Calculation of hydrologically sound digital elevation models. Third International Symposium on Spatial Data Handling, Sydney, Australia, August 117–133.

Hutchinson, M. F. (1996). A locally adaptive approach to the interpolation of digital elevation models. In Proceedings, Third International Conference/Workshop on Integrating GIS and Environmental Modeling, January 21–25.

Hutchinson, M. F. (2008). Adding the Z-dimension. In Wilson J.P. and Fotheringham, A. S. (Eds.) The Handbook of Geographic Information Science, (pp. 144–168). Blackwell. DOI: 10.1002/9780470690819.ch8

Jones, K. H. (1998). A comparison of algorithms used to compute hill slope as a property of the DEM. Computers & Geosciences, 24(4), 315–323. DOI: 10.1016/S0098-3004(98)00032-6

Kweon, I. S. and Kanade T. (1994). Extracting Topographic Terrain Features from Elevation Maps. CVGIP: Image Understanding, 59(2), 171–182. Li, Z. (1994). A comparative study of the accuracy of digital terrain models (DTMs) based on various data models. ISPRS Journal of Photogrammetry and Remote Sensing, 49(1), 2–11.

Maekawa, T., Matsumoto, Y., & Namiki, K. (2007). Interpolation by geometric algorithm. Computer-Aided Design, 39(4), 313–323. DOI: 10.1016/j.cad.2006.12.008

Nadler, S. B. (1978). Hyperspaces of sets: A text with research questions.

New York: Marcel Dekker.

Oky, P., Ardiansyah, D., & Yokoyama R. (2002). DEM generation method from contour lines based on the steepest slope segment chain and a monotone interpolation function. ISPRS Journal of Photogrammetry and Remote Sensing, 57(1–2), 86–101. DOI: 10.1016/S0924-2716(02)00117-X

Peralvo, M., and Maidment, D. (2008). Influence of DEM Interpolation Method in Drainage Analysis. Available online at www.crwr.utexas. edu/gis/gishydro04/Introduction/TermProjects/Peralvo.pdf>.

Rvachev, V. L., Sheiko, T. I., Shapiro, V., & Tsukanov, I. (2001). Transfinite interpolation over implicitly de ned sets. Computer Aided Geometric Design, 18(3), 195–220. DOI: 10.1016/S0167-8396(01)00015-2

Taud, H., Parrot, J. F., & Alvarez, R. (1999). DEM generation by contour line dilation. Computers & Geosciences, 25(7), 775–783. DOI: 10.1016/ S0098-3004(99)00019-9

Vieux, B. E. (1993). DEM aggregation and smoothing effects on surface runoff modeling. Journal of Computing in Civil Engineering—ASCE, 7(3), 310–338. DOI: 10.1061/(ASCE)0887-3801(1993)7:3(310)

Wang, D., Tian, Y., Gao Y., & Wu. L. (2005). A New Method of Generating Grid DEM from Contour Lines. IGARSS 2005, 657–660. DOI: 10.1109/ IGARSS.2005.1526261

Watson, D. F. (1992). Contouring: A Guide to the Analysis and Display of Spatial Data. Oxford: Pergamon.

Watson, D. (1999). The natural neighbor series manuals and source codes. Computers & Geosciences, 25(4), 463–466. DOI: 10.1016/ S0098-3004(98)00150-2

Werbrouck, I., Antrop, M., Van Eetvelde, V., Stal, C., De Maeyer, P., Bats, M., ... Zwertvaegher, A. (2011). Digital elevation model generation for historical landscape analysis based on LiDAR data, a case study in Flanders (Belgium). Expert Systems with Applications, 38(7), 8178– 8185. DOI: 10.1016/j.eswa.2010.12.162

Wise, S. (2011). Cross-validation as a means of investigating DEM interpolation error. Computers & Geosciences, 37(8), 978–991.

Wise, S. (2012). Information entropy as a measure of DEM quality. Computers & Geosciences, 48, 102–110. DOI: 10.1016/j.cageo.2012.05.011

Wood, J. (1994). Visualizing contour interpolation accuracy in digital elevation models. In H. M. Hearnshaw and D. J. Unwin, eds. Visualization in geographical information systems. Chichester: John Wiley and Sons, 168–180.

Wood, J. D., & Fisher P. F. (1993). Assessing interpolation accuracy in elevation models. IEEE Computer Graphics and Applications, 13(2), 48–56. DOI: 10.1109/38.204967

Xiao, L., & Liu, H. (2012). A novel approach for quantitative assessment of DEM accuracy using reconstructed contours. Procedia Environmental Sciences, 12 Part B, 772–776. DOI: 10.1016/j.proenv.2012.01.346

Xie, K., Wu, Y., Ma, X., Liu, Y., Liu, B., & Hessel, R. (2003). Using contour lines to generate digital elevation models for steep slope areas: a case study of the Loess Plateau in North China. Catena, 54(1–2), 161–171. DOI: 10.1016/S0341-8162(03)00063-8

Yu, Z. W. (2001). Surface interpolation from irregularly distributed points using surface splines, with Fortran program. Computers & Geosciences, 27(3), 877–882.

Yu, Z. W., & Tan, H. Q. (2002). Regionalized interpolation: A new approach to surface map reconstruction. Terra Nostra, 3, 513–517.

Zhou, Q., & Chen Y. (2011). Generalization of DEM for terrain analysis using a compound method. ISPRS Journal of Photogrammetry and Remote Sensing, 66(1), 38–45. DOI: 10.1016/j.isprsjprs.2010.08.005.

Zhou, Q., & Liu X., (2004). Analysis of errors of derived slope and aspect related to DEM data properties. Computers & Geosciences, 30(4), 369–378. DOI: 10.1016/j.cageo.2003.07.005

Zhu, Q., Gong, J., & Zhang, Y. (2007). An efficient 3D R-tree spatial index method for virtual geographic environments. ISPRS Journal of Photogrammetry and Remote Sensing, 62(3), 217–224. DOI: 10.1016/j.isprsjprs.2007.05.007

License

Earth Sciences Research Journal holds a Creative Commons Attribution license. 

You are free to:

Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material for any purpose, even commercially.
The licensor cannot revoke these freedoms as long as you follow the license terms.

The Earth Sciences Research Journal is the copyright holder for these license attributes.