Abstract
In this paper, we describe, analyze and compare techniques for extracting spatial knowledge from a terrain model. Specifically, we investigate techniques for extracting a morphological representation from a terrain model based on an approximation of a Morse-Smale complex. A Morse-Smale complex defines a decomposition of a topographic surface into regions with vertices at the critical points and bounded by integral lines which connect passes to pits and peaks. This provides a terrain representation which encompasses the knowledge on the salient characteristics of the terrain. We classify the various techniques for computing a Morse-Smale complexe based on the underlying terrain model, a Regular Square Grid (RSG) or a Triangulated Irregular Network (TIN), and based on the algorithmic approach they apply. Finally, we discuss hierarchical terrain representations based on a Morse-Smale decomposition.
Keywords
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Bajaj, C.L., Pascucci, V., Shikore, D.R.: Visualization of scalar topology for structural enhancement. In: Proceedings IEEE Visualization 1998, pp. 51–58. IEEE Computer Society, Los Alamitos (1998)
Bajaj, C.L., Shikore, D.R.: Topology preserving data simplification with error bounds. Computers and Graphics 22(1), 3–12 (1998)
Banchoff, T.: Critical points and curvature for embedded polyhedral surfaces. American Mathematical Monthly 77(5), 475–485 (1970)
Bremer, P., Pascucci, V., Hamann, B.: Maximizing adaptivity in hierarchical topological models. In: Proceedings of International Conference on Shape Modeling and Applications (2005)
Bremer, P.-T., Edelsbrunner, H., Hamann, B., Pascucci, V.: A multi-resolution data structure for two-dimensional Morse functions. In: Turk, G., van Wijk, J., Moorhead, R. (eds.) Proceedings IEEE Visualization 2003, pp. 139–146. IEEE Computer Society, Los Alamitos (2003)
Danovaro, E., De Floriani, L., Mesmoudi, M.M.: Topological analysis and characterization of discrete scalar fields. In: Asano, T., Klette, R., Ronse, C. (eds.) Geometry, Morphology, and Computational Imaging. LNCS, vol. 2616, pp. 386–402. Springer, Heidelberg (2003)
De Floriani, L., Magillo, P., Puppo, E.: Data structures for simplicial multi-complexes. In: Güting, R.H., Papadias, D., Lochovsky, F.H. (eds.) SSD 1999. LNCS, vol. 1651, pp. 33–51. Springer, Heidelberg (1999)
Danovaro, E., De Floriani, L., Magillo, P., Mesmoudi, M.M., Puppo, E.: Morphology-driven simplification and multiresolution modeling of terrains. In: Hoel, E., Rigaux, P. (eds.) Proceedings ACM GIS 2003 - The 11th International Symposium on Advances in Geographic Information Systems, pp. 63–70. ACM Press, New York (2003)
Edelsbrunner, H., Harer, J., Natarajan, V., Pascucci, V.: Morse-Smale complexes for piecewise linear 3-manifolds. In: Proceedings 19th ACM Symposium on Computational Geometry, pp. 361–370 (2003)
Edelsbrunner, H., Harer, J., Zomorodian, A.: Hierarchical Morse complexes for piecewise linear 2-manifolds. In: Proceedings 17th ACM Symposium on Computational Geometry, pp. 70–79. ACM Press, New York (2001)
Mangan, A., Whitaker, R.: Partitioning 3D surface meshes using watershed segmentation. IEEE Transaction on Visualization and Computer Graphics 5(4), 308–321 (1999)
Meyer, F.: Topographic distance and watershed lines. Signal Processing 38, 113–125 (1994)
Milnor, J.: Morse Theory. Princeton University Press, Princeton (1963)
Nackman, L.R.: Two-dimensional critical point configuration graph. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-6(4), 442–450 (1984)
Ni, X., Garland, M., Hart, J.C.: Fair morse functions for extracting the topological structure of a surface mesh. ACM Trans. Graph. 23(3), 613–622 (2004)
Pascucci, V.: Topology diagrams of scalar fields in scientific visualization. In: Rana, S. (ed.) Topological Data Structures for Surfaces, pp. 121–129. John Wiley and Sons Ltd., Chichester (2004)
Peucker, T.K., Douglas, D.H.: Detection of Surface-Specific Points by Local Parallel Processing of Discrete Terrain Elevation Data. Computer Graphics and Image Processing 4, 375–387 (1975)
Pfaltz, J.L.: Surface networks. Geographical Analysis 8, 77–93 (1976)
Press, W., Teukolsky, S., Vetterling, W., Flannery, B.: Numerical recipes in c, 2nd edn. Cambridge University Press, Cambridge (1992)
Roerdink, J., Meijster, A.: The watershed transform: definitions, algorithms, and parallelization strategies. Fundamenta Informaticae 41, 187–228 (2000)
Schneider, B., Wood, J.: Construction of metric surface networks from raster-based DEMs. In: Rana, S. (ed.) Topological Data Structures for Surfaces, pp. 53–70. John Wiley and Sons Ltd, Chichester (2004)
Schneider, B.: Extraction of hierarchical surface networks from bilinear surface patches. Geographical Analysis 37, 244–263 (2005)
Smale, S.: Morse inequalities for a dynamical system. Bulletin of American Mathematical Society 66, 43–49 (1960)
Soille, P.: Morphological Image Analysis: Principles and Applications. Springer, Berlin (2004)
Takahashi, S.: Algorithms for extracting surface topology from digital elevation models. In: Rana, S. (ed.) Topological Data Structures for Surfaces, pp. 31–51. John Wiley and Sons Ltd., Chichester (2004)
Takahashi, S., Ikeda, T., Kunii, T.L., Ueda, M.: Algorithms for extracting correct critical points and constructing topological graphs from discrete geographic elevation data. Computer Graphics Forum 14(3), 181–192 (1995)
Toriwaki, J., Fukumura, T.: Extraction of structural information from gray pictures. Computer Graphics and Image Processing 7, 30–51 (1978)
Vincent, L., Soile, P.: Watershed in digital spaces: an efficient algorithm based on immersion simulation. IEEE Transactions on Pattern Analysis and Machine Intelligence 13(6), 583–598 (1991)
Watson, L.T., Laffey, T.J., Haralick, R.M.: Topographic classification of digital image intensity surfaces using generalized splines and the discrete cosine transformation. Computer Vision, Graphics, and Image Processing 29, 143–167 (1985)
Wolf, G.W.: Topographic surfaces and surface networks. In: Rana, S. (ed.) Topological Data Structures for Surfaces, pp. 15–29. John Wiley and Sons Ltd., Chichester (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Čomić, L., De Floriani, L., Papaleo, L. (2005). Morse-Smale Decompositions for Modeling Terrain Knowledge. In: Cohn, A.G., Mark, D.M. (eds) Spatial Information Theory. COSIT 2005. Lecture Notes in Computer Science, vol 3693. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11556114_27
Download citation
DOI: https://doi.org/10.1007/11556114_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28964-7
Online ISBN: 978-3-540-32020-3
eBook Packages: Computer ScienceComputer Science (R0)