Critical Features Tracking on Triangulated Irregular Networks by a Scale-Space Method

University of Maryland, College Park
32nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2024)

Abstract

The scale-space method is a well-established framework that constructs a hierarchical representation of an input signal and facilitates coarse-to-fine visual reasoning. Considering the terrain elevation function as the input signal, the scale-space method can identify and track significant topographic features across different scales. The number of scales a feature persists, called its life span, indicates the importance of that feature. In this way, important topographic features of a landscape can be selected, which are useful for many applications, including cartography, nautical charting, and land-use planning. The scale-space methods developed for terrain data use gridded Digital Elevation Models (DEMs) to represent the terrain. However, gridded DEMs lack the flexibility to adapt to the irregular distribution of input data and the varied topological complexity of different regions. Instead, Triangulated Irregular Networks (TINs) can be directly generated from irregularly distributed point clouds and accurately preserve important features. In this work, we introduce a novel scale-space analysis pipeline for TINs, addressing the multiple challenges in extending grid-based scale-space methods to TINs. Our pipeline can efficiently identify and track topologically important features on TINs. Moreover, it is capable of analyzing terrains with irregular boundaries, which poses challenges for grid-based methods. Comprehensive experiments show that, compared to grid-based methods, our TIN-based pipeline is more efficient, accurate, and has better resolution robustness.

Overview

This project explores a novel pipeline for tracking critical topological features on Triangulated Irregular Networks (TINs) using a scale-space method. By leveraging adaptive triangular meshes, this approach enhances the precision and efficiency of terrain analysis, overcoming limitations of traditional grid-based models.

High-resolution terrain analysis is essential for fields like cartography, remote sensing, and land-use planning. Traditional Digital Elevation Models (DEMs) suffer from the trade-off between accuracy and quadratically increasing computational cost. Besides, point cloud becomes widely available and provides better accuracy and flexibility than raster format datasets. Thus, TINs have the capability of adapting to varying data density and topographical complexity and preserve critical details.

Regular Grid

TIN

Comparison between a TIN and a regular grid representation of a terrain with the same number of vertices.

Scale space is an analytical framework widely used for image process and analysis. It processes input data from different scales. Using a scale-space method, critical points can be identified and attracked through the scale changes from fine to rough. As illustrated in the following animation, more proninent critical features survive more scales:

Tracking the transition of critical features in a scale space. The homological persistent maximum survives across more scales than the other maximum, who is Collapsed with its neighboring saddle point during when the scale changes from fine to coarse.

Our main contributions are three folds:

Efficient Critical Point Tracking: The project introduces a scale-space method that accurately identifies and tracks critical features, such as peaks, saddles, and pits, across varying scales.
Robustness to Variable Terrain Complexity: Utilizing TINs allows for optimized vertex allocation, focusing resources on complex areas while minimizing redundancy in flatter regions.
Scale space on TINs: developed the Gaussain smoothing operation over a scalar function defiend on the discrete TIN. With the angle-based re-weighting and virtual neighbors, the scale space can be constructed in parallel on modern GPUs.

More details can be found in our paper and the recorded presentation at Youtube.

BibTeX

@inproceedings{feng2024critical, author = {Feng, Haoan and Song, Yunting and De Floriani, Leila}, title = {Predicate Path Expressions}, booktitle = {Proceedings of the 32nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL '24),}, year = {2024}, location = {Atlanta, Georgia}, numpages = {13}, url = {https://doi.org/10.1145/3678717.3691218}, doi = {10.1145/3678717.3691218}, publisher = {ACM}, address = {New York, NY, USA}, }