Localized Topological Simplification

This blog post provides more details and examples about the paper [Localized Topological Simplification of Scalar Data]. Disclaimer: This post is still work-in-progress and will receive some updates and extensions in the future.

Critical Points

The local classification of vertices is the basis for many topological data analysis (TDA) algorithms, such as the merge tree and the Morse-Smale complex. Lets assume for now that every vertex of a scalar field f would have a unique value (the next section explains how this can be enforced). Then the type of every vertex can be determined without ambiguity based on the connectivity of its upper and lower link, i.e., its local neighborhood:

Specifically, if the lower link (red) and upper link (orange) of a vertex v are both connected, then v is a regular point (a). If v has no lower or upper link then v is a minimum or maximum, respectively (b-c). If the lower or upper link of v consists of multiple components, then v is called a saddle (d).

Order-Based Scalar Field Representations

Scalar field topology is rooted in discrete Morse theory[1], which requires—among other things—that every vertex has a distinct value from all its neighbors, i.e., neighboring vertices can not have the same scalar value. This criterion guarantees that the critical point classification of the previous section is unambiguous. However, scalar fields that we encounter in real life do in general not meet this criterion. To still apply the concepts of Morse theory, one can break ties deterministically with a method called Simulation of Simplicity (SoS)[2]. In short, if one compares two vertices with the same value, then the tie is broken by comparing an additional property that can not even produce ties, such as the position of the vertices in machine memory.

Resolving ties as described previously requires to perform two comparisons each time one needs to disambiguate two vertex values during topological algorithms. A more elegant way to solve this issue is to sort the vertices once via SoS in ascending order, and then assign to them a new scalar value that corresponds to their index in the sorted vertex list. The resulting scalar field is called AN order field o for the original scalar field f. Note, the order field depends on the used SoS technique and thus it is not unique. One needs to be aware that different order fields for the same scalar field can contain a different number of extrema, and/or they might be located at different positions.

Consider the following example of a line that consists of four vertices with the following scalar values:

So we need to break the tie between vertex B and C via SoS. If we do this based on the positive x-coordinate of the vertices, we get the following order field:

Based on the local point classification described at the beginning of this blog post, the vertices A and C are classified as maxima, and B and D as a minima. Thus, o has two persistence pairs: <A,D> with a persistence value (measured by f) of 2, AND <B,C> with a persistence value of 0! The second persistence pair is called a disambiguation artifact. As a small exercise, you can verify that by breaking ties via the negative x-coordinate this pair would not exist.

So in order to use scalar field topology, we have to pay the price that the order field is not unique, and that it might contain undesired critical points in regions where the original scalar field exhibits neighboring vertices with the same scalar value (so called scalar plateaus). Moreover, it is often not known a prior which SoS technique will result in the least number of disambiguation artifacts. Yet, with the order field we can now employ the whole arsenal of topological abstractions, which can be used for robust, multi-scale feature characterizations. In these characterizations, the disambiguation artifacts are usually identified as undesired features (in addition to the undesired features already present in the original scalar field). This is the place where the concept of topological simplification[3] comes in. This procedure is capable of removing undesired extrema (and therefore their associated features) from the order field.

Localized Topological Simplification (LTS)

For a high level description of LTS I refer the reader to the paper and my VIS2020 presentation. In short, one can imagine the order field as a landscape (at least in 1D and 2D).

Note, the image shows the original scalar field f, not o. I will update this post with illustrations of o in the future, but for now just image that vertices that appear to be on the same y-coordinate to actually have slightly different scalar values (so there is no ambiguity).

If we now want to remove a maximum, then this can be imagined as flattening its corresponding hill. Lets assume we want to remove the left maximum, then we first identify its corresponding hill shown here in orange (the hill can be computed based on the descriptions of my talk and the paper: see superlevel set propagation).

However, creating scalar plateau comes with all problems described earlier. So one needs to define a new unambiguous vertex order on this plateau that will not create additional critical points. In 1D this is trivial and can be imagined as fixing the plateau at the saddle, and then slightly tilting the plateau downwards.

In higher dimensions this is no longer trivial. However, the key insight presented in the LTS paper is that the plateau disambiguation can itself be formulated as a topological simplification problem! Specifically, we want to derive a local order field l that is only defined on the plateau and has the following properties:

• l restricted to the plateau has exactly one maximum that is located at the previous saddle vertex of o.
• All minima of l must have a neighbor outside of the plateau.

Imagine we would have computed such a local order and then embed it in the previous order field. Then the maximum on the plateau becomes a regular vertex on the entire domain since the vertex was previously a saddle and therefore must have a larger neighbor. All minima of the plateau also become regular vertices since they have a neighbor outside the plateau, which by the definition of superlevel set components (which corresponds to the hill) must have a smaller value that the plateau. Details about how to formulate this mathematically and a proof of correctness can be found in the paper (Section 4.2).

Local Order Computation

For the remainder of the post I will show how to compute a local order that satisfies the conditions listed earlier. This is a detailed demonstration of the example shown in Figure 6 of the paper. Consider the following order field which is defined on a 2D-Manifold. It exhibits two maxima (orange), and now we want to remove the maximum that currently has the order 22.

To this end, we first need to compute the superlevel set component of maximum 22. This can be done with a so-called superlevel set propagation. Specifically, we initialize the component with the maximum, and then always add the largest neighbor of the component until we added a saddle. To determine if an added vertex is a saddle, we simply have to check if the vertex has a larger neighbor that has not been added to the current component. If yes, then this neighbor must belong to a different superlevel set component and therefore the current vertex is a saddle. This procedure is animated below, where vertices of the current component are shown in orange, component neighbors (candidates) are shown in gray, and unseen vertices are shown in white. You can advance the procedure by one step by clicking on the image. Note that the last added vertex (currently with value 10) has a larger neighbor (23) that has not been added to the component. So 10 must be a saddle and we computed the complete superlevel set component.

Next we need to compute the local order of the component that satisfies the aforementioned conditions. To this end, we can use the iterative topological simplification procedure of Tierny and Pascucci[4]. In short, we will alternate between superlevel and sublevel set propagations from valid exrema until all invalid extrema are removed. That this procedure converges is prooven in the corresponding paper.

We start by initializing the local order with the global order, but enforce that the previous saddle is a maximum on the plateau by setting its value to infinity.

Now we determine the new local order of the component by initiating a superlevel set propagation from the maximum we just created. While we execute a superlevel set propagation, every vertex that gets added to the component receives a new local order that corresponds to the number of unabsorbed vertices of the plateau.

When we processed the entire plateau, we check if the local order contains minima that do not have a neighbor outside the plateau, i.e., if the local order contains invalid minima. As shown in the next image, the current local order exhibits two invalid minima, so we have to remove them with a sublevel set propagation (the inverse of a superlevel set propagation).

If necessary (as in this case) we initiate a sublevel set propagation from all valid minima located at the boundary (if none exist we can create one). For sublevel set propagations, the new local order corresponds to the order in which vertices are added to the component.

After this procedure, we have to check again if the new order contains invalid extrema. As shown below, the current order contains a new undesired maximum.

So we need to perform another superlevel set propagation starting from the only valid maximum:

This local order finally has no invalid maxima, so it can be embedded in the global order.

References

• [1] J. Milnor, "Morse Theory", Princeton Univ. Press, 1963.
• [2] H. Edelsbrunner et al., "Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms", ACM Transactions on Graphics, 1990.
• [3] H. Edelsbrunner et al., "Persistence-Sensitive Simplification Functions on 2-Manifolds", Proceedings of the twenty-second annual symposium on Computational Geometry, 2006.
• [4] J. Tierny and V. Pascucci, "Generalized Topological Simplification of Scalar Fields on Surfaces", IEEE TVCG, 2012.