How Does a Mountain Know When It’s Peaked?
Locating summits using persistent homology.
August 2, 2020
How Does a Mountain Know When It’s Peaked?
Locating summits using persistent homology.
Published: August 2, 2020.
Motivation
This is a little story of how an abstract mathematical theory like persistent homology can be a practical tool for a usual task in industry.
While summiting a mountain on my bike a few weeks ago, something I hadn't done since getting a cycling computer, my cycling computer notified me that I had reached the peak of a mountain. I hadn't seen such a notification since beginning to use the device, which got me thinking about mountain peaks and how they are defined. At what stage does a local peak in elevation become significant enough to warrant a pin on a map? Fortunately for my curiosity, I had the opportunity to explore this idea at work when I needed to find peaks in data similar to that of geospatial elevation data.
Empirical Peak Identification
Through a qualitative lens this problem seems simple on the surface, though the illusion of simplicity is realised when attempting to make quantitative justifications. For instance, some peaks, such as the overall peak shown in the ngram in Fig. 1 are easily identified empirically, as too are many local peaks. However, quantifying the significance of identified peaks is not immediately obvious.
Can further insight be drawn by analysing the location of actual named peaks? From the geographical data in Fig. 2, named peaks seem to be located along ridgelines, and separated by natural depressions in elevation such as valleys or basins. Thus, these peaks are geographically separated relative to each other. Unfortunately, using these peaks as a truth is fraught with bias, as factors other than the significance of the terrain can influence whether a peak has a name, such as proximity to other significant landmarks or local communities.
Enter Persistent Homology
For those who are not satisfied with empirical means of identifying peaks, Persistent Homology provides a welcome resolution.
[Persistent Homology] casts the multi-scale organisation we frequently observe in nature into a mathematical formalism.
The underlying struggle with attempting to identify peaks empirically lies in the issue of scale. The key is to compare the features over all scales, and to quantify these features by their persistence across these scales. In the context of identifying peaks in geographical elevation data, the features are the peaks, and the significance of the peak is how persistent the peak is across different scales of elevation.
Below, I will explain how we can use ideas from Persistent Homology to quantify the significance of geographical peaks using data from the Shuttle Radar Topography Mission (SRTM) of an area west of Sydney.
Imagine that the terrain in Fig. 3 was completely submerged in water. As the water-level slowly decreases (ignoring local cavities), islands will emerge. The birth-point of an island is at the location where the island emerges from the receding water. As the water continues to recede, new islands will emerge and existing islands will grow. When two (or more) islands grow to the point where they touch, the island which emerged from the water earliest (that is, the island who's peak is highest) persists, while the other island(s) cease to persist, and are merged with the more-persistent island. This marks the death-point of the less-persistent island(s), and the persistence of these deceased islands is calculated as the elevation at it's birth-point, minus the elevation at it's death-point.
Once the water level reaches the overall minimum, all islands which at some point emerged from the water's surface will have merged into another more-significant island, except for the first island to emerge from the water. It is impossible for this island to be merged with another, as it's peak is the highest overall point. Thus, this most-persistent peak has no death-point.
Fig. 4 shows the top-20 most persistent islands from the digital elevation model. Note that while the first island to emerge is the most persistent (as it outlives every other island), the second most persistent island is not necessarily the island which emerges after the first. This shows that the significance (persistence) of a peak is not the same as the sheer height of its peak.
One approach to algorithmically formalising this is to first transform the raster digital elevation model into a network. To do this, each pixel becomes a node in the network, and the nodes corresponding to a pixel's eight neighbours are connected via edges in the network. Each node has a value - the value of the pixel in the raster, which in this case is the elevation at that location. Using an efficient data structure, such as a disjoint-set, the nodes can be processed and each islands can quickly be tracked and merged.
The bar chart in Figure Fig. 5 is a useful tool for visualising the significance of various peaks. In this figure, I have filtered out small- to moderate-sized peaks, showing only the most-significant ones. This diagram is an intuitive way to discern signal from noise.
The DEM data used has limitations in that peaks are more-likely to be located near edges of the image, as these peaks are on average more distant from peaks closer to the centre of the raster. The persistence of these peaks is also more questionable given there could be a more significant peak just beyond the image boundaries.
Conclusion
Persistent Homology provides a quantitative means with which to identify and compare the significance of mountains in digital elevation terrain. Specifically, the relative-significance of all peaks are compared at multiple scales in a manner which is robust to noise.
Resources
A Python notebook with an implementation of the described peak-extraction algorithm is provided here. The code is derived from Huber, S. 2017.