You are not logged in.

Minimum spanning trees for valley and ridge characterization in digital elevation maps

Bangay, Shaun, de Bruyn, David and Glass, Kevin 2010, Minimum spanning trees for valley and ridge characterization in digital elevation maps, in Afrigraph 2010 : proceedings of the 7th international conference on computer graphics, virtual reality, visualisation and interaction in Africa, Association for Computing Machinery, New York, N.Y., pp. 73-82, doi: 10.1145/1811158.1811171.

Attached Files
Name Description MIMEType Size Downloads

Title Minimum spanning trees for valley and ridge characterization in digital elevation maps
Author(s) Bangay, Shaun
de Bruyn, David
Glass, Kevin
Conference name International conference on computer graphics, virtual reality, visualisation and interaction in Africa (7th : 2010 : Franschhoek, South Africa)
Conference location Franschhoek, South Africa
Conference dates 21-23 Jun. 2010
Title of proceedings Afrigraph 2010 : proceedings of the 7th international conference on computer graphics, virtual reality, visualisation and interaction in Africa
Editor(s) Spencer, Stephen N.
Publication date 2010
Series ACM conference proceedings series
Conference series International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa
Start page 73
End page 82
Total pages 153 p.
Publisher Association for Computing Machinery
Place of publication New York, N.Y.
Keyword(s) line
ridge
graph
minimum spanning tree
DEM
Summary Texture synthesis employs neighbourhood matching to generate appropriate new content. Terrain synthesis has the added constraint that new content must be geographically plausible. The profile recognition and polygon breaking algorithm (PPA) [Chang et al. 1998] provides a robust mechanism for characterizing terrain as systems of valley and ridge lines in digital elevation maps. We exploit this to create a terrain characterization metric that is robust, efficient to compute and is sensitive to terrain properties.

Terrain regions are characterized as a minimum spanning tree derived from a graph created from the sample points of the elevation map which are encoded as weights in the edges of the graph. This formulation allows us to provide a single consistent feature definition that is sensitive to the pattern of ridges and valleys in the terrain Alternative formulations of these weights provide richer characteristicmeasures and we provide examples of alternate definitions based on curvature and contour measures.

We show that the measure is robust, with a significant portion derived directly from information local to the terrain sample. Global terrain characteristics introduce the issue of over- and underconnected valley/ridge lines when working with sub-regions. This is addressed by providing two graph construction strategies, which respectively provide an upper bound on connectivity as a single spanning tree, and a lower bound as a forest of trees.

Efficient minimum spanning tree algorithms are adapted to the context of terrain data and are shown to provide substantially better performance than previous PPA implementations. In particular, these are able to characterize valley and ridge behaviour at every point even in large elevation maps, providing a measure sensitive to terrain features at all scales.

The resulting graph based formulation provides an efficient and elegant algorithm for characterizing terrain features. The measure can be calculated efficiently, is robust under changes of neighbourhood position, size and resolution and the hybrid measure is sensitive to terrain features both locally and globally.
ISBN 9781450301183
1450301185
Language eng
DOI 10.1145/1811158.1811171
Field of Research 080103 Computer Graphics
Socio Economic Objective 890299 Computer Software and Services not elsewhere classified
HERDC Research category E1.1 Full written paper - refereed
Copyright notice ©2010, Association for Computing Machinery
Persistent URL http://hdl.handle.net/10536/DRO/DU:30039213

Document type: Conference Paper
Collection: School of Information Technology
Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 0 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 251 Abstract Views, 2 File Downloads  -  Detailed Statistics
Created: Mon, 24 Oct 2011, 11:43:24 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.