4.2 Consequences of axioms: critical points, sets, and values.

In volumetric data, not all our critical points will be isolated points. In particular, a connected cluster of lattice points with identical $\delta$ values can form a critical set. For the purposes of dealing with these clusters we define connectivity of such sets in the same manner that we have defined connectivity for sets of High readings. Two lattice points p and q with $\delta (p) = \delta (q)$ are adjacent if they are adjacent for $\tau = \delta (p)$.

Definition 19   We call a connected component of lattice points with identical $\delta$ values, a degenerate set.

When we refer to an object, we are referring to a single component $O_i (\tau )$ of $\bf {X}_{f}^{\geq \tau}$, and when we refer to its topology we mean the topology of the boundary manifolds comprising $B ( O_i (\tau ) )$.

We now enumerate the critical values and corresponding critical points and sets of f. These are the values such that as $\tau$ is decreased through the value, a change in the connectivity of $\bf {X}_{\delta}^{\geq \tau}$ induces a change in the topology of $B (\bf {X}_{f}^{\geq \tau})$. In each case adjacency is defined for $\tau = \delta (p)$, for p in question. See figures 12 through 18 for illustrations.

Digital Morse criticalities

Definition 20  

1) If a vertex p has a maximum value $\delta(p)$ with respect to all his adjacent lattice neighbors, then p is a maximum critical point and $\delta(p)$ a maximum critical value (see figure 12).

2) If a vertex p has a minimum value $\delta(p)$ with respect to all his adjacent lattice neighbors, then p is a minimum critical point and $\delta(p)$ a minimum critical value (see figure 13).

3) If p is a vertex, such that for each coordinate direction $\delta (p)$ is either a maximum or a minimum with respect to the $\delta$ value of the 2 neighbors in that direction, and $\delta (p)$ is maximal in at least one coordinate direction and minimal in at least one, then, p is a vertex saddle critical point and $\delta(p)$ is a saddle critical value (see figure 14).

4) If p is the disambiguation point of a critical 4-hit face F, then p is a saddle critical point and $\delta(p)$ is a saddle critical value (see figure 15). NOTE: The location and precise value of the disambiguation point and hence the critical value is dependent on the interpolation function, but the existence of this criticality in the face is not.

For 5 through 7 let S be a degenerate set with degenerate value $c = \delta (S)$. Let N_H be the set of adjacent vertices (neighbors) of S in $\bf {X}_{\delta}^{\geq \tau}$, that are not in S, and let N_L be the set of adjacent vertices of S in $\bf {X}_{\delta}^{\leq \tau}$. Let $N = N_H \cup N_L$. Compute the connected components of N_H and N_L with respect to N.

5) If N_H is empty, then S is a maximum critical set and c a maximum critical value (see figure 16).

6) If N_H = N, then S is a minimal critical set and c a minimum critical value (see figure 17).

7) If N_H is non-empty and either N_H or N_L consists of more than 1 connected component then S is a saddle critical set, and c is a saddle critical value (see figure 18).

Changes in the number of components or topology of $B(\bf {X}_{f}^{\geq \tau })$ occur only at critical values. More precisely,

Fundamental Theorem of Digital Morse Theory

Theorem 2  

If $\tau$ is a critical value, then for all sufficiently small $\epsilon > 0$, $B(\bf {X}_{f}^{\geq \tau - \epsilon })$ and $B(\bf {X}_{f}^{\geq \tau + \epsilon })$ are not homeomorphic. Conversely, if $[\tau_1 , \tau_2 ]$ is a critical value-free interval then $B(\bf {X}_{f}^{\geq \tau_1 })$ and $B(\bf {X}_{f}^{\geq \tau_2 })$ are homeomorphic.

Proof: See figures 12 through 18 for illustrations. For one direction of the proof let us show that each of the criticalities c above engender a change in topology of $B(\bf {X}_{f}^{\geq \tau })$ as $\tau$ is decreased through $\delta (c)$.

For a maximum criticality c of type 1, it is easy to see that we can find a neighborhood $\nu$ of c, containing no other lattice point save c, so that for all $\epsilon > 0$, $B(\bf {X}_{f}^{\geq \delta(c) + \epsilon })$ is disjoint from $\nu$. But for some range of $\tau < c$, but $\tau >\delta(p)$ for all adjacent lattice points p of c, $\nu$ will completely contain a (new) component of $B(\bf {X}_{f}^{\geq \tau })$, which contains c. This is because c is now High and all its neighbors are still Low.

Similarly, for a type 2 minimum criticality, for sufficiently small $\epsilon$ $\nu$ will contain a boundary component of $B(\bf {X}_{f}^{\geq \delta(c) + \epsilon })$, as c is Low and all its neighbors are High. Below $\delta(c)$ c will become High and thus $\nu$ will contain no boundary surface.

For type 3 and 4 saddle criticalities, we see that in each case at threshold $\delta(c)$, c becomes High and connects two previously (locally) disconnected components of Highs. Thus from the axioms two locally separate portions of boundary components B₁ and B₂ merge in $\nu$ but do not contain all of $\nu$. Thus either portions of the same boundary merge, and a handle is formed (increase in genus) or two separate boundary components merge.

If c is a maximum critical set (type 5), we can again find a neighborhood $\nu$ of c that contains only lattice points of c. When c is Low (above $\delta(c)$) $\nu$ contains no boundary component and for some range of thresholds below $\delta(c)$ but greater than all neighbors of c, $\nu$ completely contains a new boundary manifold.

Similarly, if c is a minimum set, $\nu$ will contain a boundary component at thresholds above $\delta(c)$, when c is Low but all its neighbors are High. Below $\delta(c)$ c becomes High and becomes part of the same component of $\bf {X}_{\delta}^{\geq \tau}$ as its neighbors and the boundary component vanishes in $\nu$.

Finally if c is a saddle critical set, then its neighbors consist of more than one locally connected component of Highs or more than one locally connected component of Lows. Thus in the former case $\nu$ will contain at least two portions of boundary components B₁ and B₂ for some range of values above $\delta(c)$. For some range of values below $\delta(c)$, B₁ and B₂ merge in $\nu$ but do not contain all of $\nu$. Thus, as above, either two boundary components merge or a handle is formed. In the latter case, above $\delta(c)$, $\nu$ will contain the points of c and at least two of the components of Lows, and no boundary components, but below $\delta(c)$ $\nu$ will contain the boundary of the level set component containing c, separating the two sets of Lows.

We prove the other direction by contradiction. That is, suppose that $B(\bf {X}_{f}^{\geq \tau_2 })$ is not homeomorphic to $B(\bf {X}_{f}^{\geq \tau_1 })$. We show that under this assumption,the critical value free interval $[\tau_1 , \tau_2 ]$, must in fact contain a criticality, a contradiction.

Now, by assumption, there must be a change in topology of $B(\bf {X}_{f}^{\geq \tau })$ at a threshold value $\tau = a$, for some $\tau_1 \leq a \leq \tau_2$. Now, as observed above, the volume of $\bf {X}_{f}^{\geq \tau }$ is monotonically nondecreasing as $\tau$ is decreased, as more and more points fall below the threshold.

In case 1, suppose a new boundary component is formed below a in a neighborhood $\nu$ (of an arbitrary point). Thus for thresholds above a, $\nu$ contains no boundary components, and for a range of thresholds below a, $\nu$ completely contains a component M of $B(\bf {X}_{f}^{\geq \tau })$. Then there must be a lattice point or set c in the interior of M that was Low above a and High below a, such that the lattice neighbors of c are all still Low when c becomes High. c must therefor be a maximum criticality and a a critical value.

Similarly, if a component M, completely contained in $\nu$, vanishes at a, then $\nu$ must contain a minimum point or set criticality.

Finally, by similar argument, if two locally separate boundary components merge in a neighborhood $\nu$ at value a, but for some range of thresholds less than a do not comprise all of $\nu$, then $\nu$ must contain a saddle criticality of type 3, of type 4, or a saddle critical set.

Note that our definitions are constructive, so that in each case we have implicitly given an (efficient) algorithm for recognizing such criticalities.

The topological changes at a criticality, as the threshold is decreased through a (non-maximal) critical value, are completely characterized by the number of distinct sets of Highs that become connected. This is important, as a number of researchers have attempted to deal with the ``zoo'' of critical structures (plateaus, ridges, etc.) that one gets with a non-Morse interpolation function for volume data. By using the appropriate combinatorial analysis we have elucidated and simplified these issues.

The point is that we can divide the entire range of possible function values into disjoint, critical value-free intervals, so that no topological change in the level sets can occur as the threshold is varied within one of the intervals. Moreover, we can now choose one sample value for each interval and compute representative level sets. These give all topologically distinct level sets, over all threshold values.

We say more about computing this and related information in the algorithm section.