6.2 Relaxing Morse conditions with combinatorial insight.

We assume the reader is familiar with basic topology.

Definition 1   For simplicity, we assume that our data readings have been mapped onto the n-dimensional integer lattice in Euclidean space, that is, are given by a real-valued function $\delta$ defined on $\bf {Z}^n$. We form unit hypercubes in the natural way, i.e., a line segment (edge) connects points $p,q \in \bf {Z}^n$ iff their Euclidean distance is 1. Thus the data readings are given at the hypercube vertices (or lattice points). We shall assume, without loss of generality, that $\delta$ is non-negative. We further assume that $\delta > 0$ on a finite subset of $\bf {Z}^n$.

Definition 2   We will say that a continuous real-valued function f interpolates $\delta$ if the domain of f is Euclidean n-space, $\bf {E}^n$, f is non-zero on a closed and bounded subset of $\bf {E}^n$, and for all $p \in \bf {Z}^n$, $f(p) = \delta (p)$.

Definition 3   We denote by $\bf {X}_{f}^{\geq \tau}$, the set of $p \in \bf {E}^n$ such that $f(p) \geq \tau$, for f that interpolates $\delta$. Similarly, $\bf {X}_{\delta}^{\geq \tau}$ denotes the set $p \in \bf {Z}^n$ such that $\delta (p) \geq \tau$.

Clearly, if f interpolates $\delta$ then $\bf {X}_{\delta}^{\geq \tau} \subseteq \bf {X}_{f}^{\geq \tau}$.

Definition 4   We denote the topological boundary of a set X by B(X).

A first assumption made by most researchers' interpolation methods is that the underlying function is continuous. We shall reduce questions of the topology of the boundary components of $\bf {X}_{f}^{\geq \tau}$ to basic combinatorial questions. Much will be made of connected sets of data readings in $\bf {Z}^n$. The reason for this is simple. Each component O of $\bf {X}_{f}^{\geq \tau}$ contains a subset of $\bf {X}_{\delta}^{\geq \tau}$. We will regard this set as connected, that is, a set of data readings is connected if and only if the set is contained in the same level set component. As we shall argue, a reasonable set of assumptions on the interpolation method will allow us to reverse this implication. In other words, if we determine the connectivity of $\bf {X}_{\delta}^{\geq \tau}$, this will determine the topology of the components of $\bf {X}_{f}^{\geq \tau}$.

This is the basic idea behind the digital topology program: that objects are defined by discrete data reading connectivity. While we could use a discrete topology on $\bf {X}_{\delta}^{\geq \tau}$ to obtain our results, for generality we prefer to examine the standard point set topology of $\bf {X}_{f}^{\geq \tau}$, for a reasonable class of interpolation functions f.

We will restrict the class of interpolation functions f by axioms on the structure of $B( \bf {X}_{f}^{\geq \tau})$, for each $\tau$. Since, in point of fact, most algorithms in the literature are for interpolating the components of $B ( \bf {X}_{f}^{\geq \tau} )$ for specific $\tau$, without actually specifying f on all of $\bf {E}^n$, this makes sense.

For ease of exposition, we define with respect to each real number $\tau$ :

Definition 5  

A point $p \in \bf {Z}^n$ is High if $p \in \bf {X}_{\delta}^{\geq \tau}$, that is, if $\delta (p) \geq \tau$, and is Low if $\delta (p) < \tau$.

We shall assume that for each $\tau$ not in the (finite) range of $\delta$ ($\tau$ not equal to a data reading), $\bf {X}_{f}^{\geq \tau}$ consists of a finite collection $O_i ( \tau )$, $i = 1, \ldots , k$, of path connected, full-dimensional components, and that the boundary $B ( O_i ( \tau ))$, of each component consists of a finite set of closed, bounded, and oriented manifolds. This is consistent with the literature and goals of the imaging community.

Most methods, in the absence of further information, construct $\bf {X}_{f}^{\geq \tau}$ with the simplest topology consistent with the data, that is, they don't introduce extraneous holes and handles in the objects (see, for example figures 1 and 2), in the sense that every component of the level sets or their complement contains at least 1 data reading (integral point).

We will assume that the manifolds of $B (\bf {X}_{f}^{\geq \tau})$ intersect our hypercubes in simple ways, so that any intersection with a hypercube edge is at a point, with a hypercube face is a one-dimensional set and, in general, the intersection of $B (\bf {X}_{f}^{\geq \tau})$ with a d-dimensional hypercube is a d-1-dimensional set (see axiom 2 below). This is a reasonable assumption as it merely means that at an iso-value $\tau$ not precisely equal to a data reading, the plateau regions of $B (\bf {X}_{f}^{\geq \tau})$ never overlap a cube face. This will allow us to determine adjacency of High vertices by deciding if they are path connected within a face F (see figure 3). Now obviously for diagonally opposite High vertices that are not edge-connected we may need to see if there is a path between the two vertices through the cube interior. But this will not change the character of our results, merely the value of certain critical points.

Most methods interpolate a single boundary surface crossing point on a hypercube edge if and only if the endpoint readings are High and Low. Even if one employs a method, for example, that creates a level set boundary that snakes back and forth across the hypercube edge connecting two Highs, the two Highs will most surely be part of the same component of $\bf {X}_{f}^{\geq \tau}$, and thus no topological generality is lost by assuming that the entire hypercube edge is contained in $\bf {X}_{f}^{\geq \tau}$.

Since edge adjacent Highs are assumed part of the same component, one may be tempted to define connectivity of $\bf {X}_{\delta}^{\geq \tau}$ by the transitive closure of the hypercube edge adjacency. Unfortunately, as observed in the seminal work in digital topology, edge adjacency alone leads to asymmetry in the sense that the complementary components will not be edge-connected (in 3-dimensions they will be 14-connected rather than 6-connected).

We will explain below why we feel that 6-connectivity for Highs is not the right choice. However, for any (local) connectivity one chooses, we can develop the same results: algorithms for identifying criticalities and constructing a criticality graph. This is because our axioms completely specify the topology of the boundary manifolds of the level sets, subject to the connectivity rule that one chooses.