A new approach for a topographic feature-based characterization of digital elevation data

ABSTRACT

Triangular Irregular Network (TIN) and Regular Square Grid (RSG) are widely used for representing 2.5 dimensional spatial data. However, these models are not defined from the topographic properties of the terrain (i.e., ridge lines, valley lines, saddle points, etc.). This paper introduces a three-step feature-based approach for topographic properties extraction on scattered elevation data modeled by a TIN. Firstly, a segmentation process extracts homogeneous morphological areas bounded by critical lines and points. Secondly, these lines and points are displaced using a deformable process in order to derive the terrain feature points, lines and areas. Thirdly, a classification process labels any topographic feature. This three-step approach relies on the definition of an adapted model of representation (SPIN) and data structure (DCFL2). The proposed approach is validated on a real case study (Seolak mountain in South Korea). Consistent results with the morphology of terrain are displayed.

REFERENCES

• 1: S. Arono. Geographic Information Systems: A Management Perspective. WDL Publications, Ottawa, 1989.
• 2: Chanderjit L. Bajaj , Tamal K. Dey, Convex decomposition of polyhedra and robustness, SIAM Journal on Computing, v.21 n.2, p.339-364, April 1992 [doi>10.1137/0221025]
• 3: C. L. Bajaj , V. Pascucci , D. R. Schikore, Visualization of scalar topology for structural enhancement, Proceedings of the conference on Visualization '98, p.51-58, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 4: B. Baumgart. A polyhedral representation for computer vision. In Proceedings of the AFIPS National Computer Conference, pages 589--596, 1975.
• 5: Jean-Daniel Boissonnat , Olivier Devillers , Monique Teillaud , Mariette Yvinec, Triangulations in CGAL (extended abstract), Proceedings of the sixteenth annual symposium on Computational geometry, p.11-18, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336165]
• 6: E. Brisson. Representing geometric structures in d-dimensions: topology and order. Discrete and Computational Geometry, 9(4):387--426, 1993.
• 7: D. Burghardt and S. Meier. Cartographic Displacement using the Snakes Concept, pages 59--71. In: Semantic modeling for the acquisition of topographic information from images and maps, W. Förstner and L. Plümer editors, Birkhaeuser-Verlag, 1997.
• 8: P. A. Burrough. Principles of Geographical Information Systems for Land Resources Assessment. Clarendon Press, Oxford, 1986.
• 9: Emanuele Danovaro , Leila De Floriani , Paola Magillo , Mohammed Mostefa Mesmoudi , Enrico Puppo, Morphology-driven simplification and multiresolution modeling of terrains, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.63-70, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956685]
• 10: E. Danovaro, L. De Floriani, and M. M. Mesmoudi. Topological analysis and characterization of discrete scalar field. Theoretical Foundations of Computer Vision, Geometry, Morphology, and Computational Imaging, Dagstuhl, April 7-12, 2002, T. Asano, R. Klette, C. Ronse editors, LNCS 2616, Springer-Verlag, pages 386--402, 2003.
• 11: L. De Floriani, E. Puppo, and P. Magillo. Applications of computational geometry to geographic information systems. Chapter 7 in Handbook of Computational Geometry, J.R. Sack, J. Urrutia (Editors), Elsevier Science, pages 333--388, 1999.
• 12: Herbert Edelsbrunner , John Harer , Afra Zomorodian, Hierarchical morse complexes for piecewise linear 2-manifolds, Proceedings of the seventeenth annual symposium on Computational geometry, p.70-79, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378626]
• 13: I. S. Evans. Spatial analysis in geomorphologie, chapter General geomorphometry, derivatives of altitude and descriptive statistics, pages 17--90. Harper and Row, 1972.
• 14: B. Falcidieno and M. Spagnuolo. A new method for the characterization of topographic surfaces. In International Journal of Geographical Information Systems, volume 5, pages 397--412. 1991.
• 15: D. Faugeras and M. Hebert. A 3D recognition and positioning algorithm using geometric matching between primitive surface. In Proceedings of 8 International Joint Conf. Artificial Intelligence, pages 996--1002, 1983.
• 16: Rafael C. Gonzales , Paul Wintz, Digital image processing (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 17: M. Kass, A. Witkin, and D. Terzopoulos. Snakes: active contour models. International Journal of Computer Vision, 1(4):321--331, 1987.
• 18: Y. Kerbrat and J. M. Braemer. Géométrie des courbes et des surfaces. Hermann, Paris, 1976.
• 19: H. Le Men. Généralisation cartographique pour l'occupation du sol: application au passage v1 ô v2 pour la BD carto. Revue international de géomatique, 6(2-3):227--248, 1996.
• 20: Pascal Lienhardt, Topological models for boundary representation: a comparison with n-dimensional generalized maps, Computer-Aided Design, v.23 n.1, p.59-82, Jan./Feb. 1991 [doi>10.1016/0010-4485(91)90082-8]
• 21: C. Lin and M. J. Perry. Shape description using surface triangulation. In Proceedings of the IEEE Worshop on Computer Vision: Representation and Control, Rindge, NH, pages 38--43, 1982.
• 22: Alan P. Mangan , Ross T. Whitaker, Partitioning 3D Surface Meshes Using Watershed Segmentation, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.308-321, October 1999 [doi>10.1109/2945.817348]
• 23: M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., New York, NY, 1988
• 24: D. M. Marks. geomorphomertic parameters; a review and evaluation. geografiska Annaler, 57a(3-4):165--177, 1975.
• 25: P. Monier. Caractérisation du terrain en vue de son traitement numerique. Application la généralisation de l'orographie. Phd thesis in GIS, Université Louis Pasteur, Strasbourg, 1997.
• 26: Mark H. Overmars, Designing the Computational Geometry Algorithms Library CGAL, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.53-58, May 27-28, 1996
• 27: G. Petrie. Modelling, interpolation and contouring procedures. in: Terrain Modelling in Survey and Civil Engineering, G. Petrie and T.J.M. Petrie editors, Whittles Publishing, London, pages 112--127, 1990.
• 28: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 29: S. Rana and J. Morley. Surface networks. Working paper series, Center for Advanced Spatial Analysis, University College London, 2002.
• 30: G. Reeb. Sur les points singuliers d'une forme de pfa. complètement intégrable ou d'une fonction numérique. Compte Rendus de l'Académie des Sciences, Paris, 222:847--849, 1946.
• 31: Ch. Rössl , L. Kobbelt , H.-P. Seidel, Recovering structural information from triangulated surfaces, Mathematical Methods for Curves and Surfaces: Oslo 2000, Vanderbilt University, Nashville, TN, 2001
• 32: L. Schylberg. Computatioal methods for generalization of cartographic data in a raster environnement. Phd thesis in philosophy, Royal Institute of thechnology, Stockholm, Sweden, 1993.
• 33: B. Smith and D. M. Mark. Do moutains exist? Toward an ontology of landforms. Environment and Planning B: Planning and Design, 30(3):411--427, 2003.
• 34: Ernest M. Stokely , Shang You Wu, Surface Parametrization and Curvature Measurement of Arbitrary 3-D Objects: Five Practical Methods, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.8, p.833-840, August 1992 [doi>10.1109/34.149594]
• 35: S. Takahashi, T. Ikeda, Y. Shinagawa, T. L. Kunii, and M. Ueda. Algorithms for extracting correct critical points and constructing topological graphs from discrete geographical elevation data. Computer Graphics Forum, 14(3):181--192, 1995.
• 36: Marc J. van Kreveld, Digital Elevation Models and TIN Algorithms, Algorithmic Foundations of Geographic Information Systems, this book originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, p.37-78, September 16-20, 1996
• 37: R. Weibel and J. S. DeLotto. Automated terrain classification for GIS modeling. In Proceedings of GIS/LIS'88, ASPRS/ACSM, Falls chrurch, Virginia, pages 618--627, November 1988.
• 38: K. Weiler. Edge-based data structures for solid modeling in a curved-surface environment. IEEE Computer Graphics and Applications, 5(1):21--40, January 1985.
• 39: J. Wood. The geomorphological characterisation of digital elevation models. Phd thesis in geography, University of Leicester, 1996.
• 40: J. Wood and S. Rana. Construction of weighted surface networks for the representation and analysis of surface topology. In Proceedings GeoComputation, University of GreenWich, 2000.
• 41: S. Yu, M. Van, and J. Snoeyink. Drainage queries in TINs: from local to global and back again. In Proceedings 7th Drainage Queries in TINs Symposium on Spatial Data Handling (SDH'96), 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Algorithms

Keywords:
DCFL2 data structure, SPIN model, digital elevation data, feature extraction