5. Introduction

Let us first discuss the centrality of forming objects based on interpolating a sampled function $\delta$ by a function f and determining the points p, where the function f satisfies $f(p) \geq \tau$.

In a variety of applications, one is given function data sampled at discrete semi-regular points in space, sometimes sampled over time, sometimes sampled over color, or some other dimensionality. This can be a real-valued function, i.e., one is given a single real number at each sampling point, or one may be given several numbers at each sample point. Examples include multiple color values collected from points on the earths surface by a multi-spectral orbiting scanner, CT, PET or MRI data, topographic geographic mapping, and electron density data from X-ray crystallography. This data is called volumetric, or density data. In a variety of such application areas, one seeks to reasonably segment the data based on functional values (A comparison of volumetric and surface rendering was done by [1]).

One often seeks to identify objects representing a range of function values, i.e., $\tau_1 \leq f \leq \tau_2$ for the interpolated function f. In this case, regardless of the methodology used, e.g, volume rendering, iso-surfaces from Marching Cubes, or ray tracing, the data is segmented into regions bounded by surfaces all having the same function value (iso-surfaces). Note that while the data may take the threshold value in the interior of the object, if the function is assumed continuous then the boundary (hyper)surfaces will all equal the threshold value and thus we will call them iso-surfaces.

In these applications, our colleagues often search the range of function values for the ``right'' threshold value $\tau$, to segment the image properly and reveal detail of an internal structure under consideration. Thus it would be very useful to develop a set of computational tools that could reveal all possible threshold defined objects up to topological equivalence (number, connectivity, topological complexity and approximate geometry) and use this information to organize and understand the volume data.

We will show that we can adapt the fundamental ideas of Morse Theory to this discrete setting in a sound and computationally useful way. Now since we cannot assume that the underlying function is Morse precisely because there may be large collections of spatially proximate, identically valued readings, we have to understand how we can identify the values at which the topology of level sets change, in this discrete data setting. It is this identification, subject to the rather reasonable set of assumptions about the data that are made in the current state of the art in imaging, that we call Digital Morse Theory. This is intended to distinguish it from traditional Morse Theory which, as mentioned, cannot be directly applied, without making assumptions on the underlying function that may not be consistent with the data readings as given. Nevertheless, we can recover the mechanisms and utility of Morse Theory in this digital setting.

In order to show that our methods are independent of the iso-surface construction, or level set interpolation technique, we discuss and axiomatize the basic assumptions of the majority of volumetric level set data imaging and segmentation methods. These axioms will define both the topology and geometry of the (iso-surface bounded) level sets of the interpolated function f. Then we will demonstrate that, subject to these reasonable assumptions, one can identify all critical function values c_i and associated critical points (and structures). These are the values at which the topology of the boundary iso-surfaces of the level sets changes. In this way we can divide the range of function values into a set of disjoint intervals, in which the level set topology is invariant. Then, using our iso-surface construction techniques, we can classify and render all possible objects, up to topological equivalence, for the entire range of function values. Further, we can identify the zone of influence of each criticality. These zones are similar to the basins of attraction of dynamical systems theory, and will allow us to categorize a criticality by the volume of the zone. In this way, we can cull criticalities that are inessential or caused by noise in the data. Moreover, the identification of these regions can provide a powerful tool for Level of Detail management during rendering, needed when the dataset becomes very large. We show that any iso-surface is completely contained within a zone, and that the iso-surfaces within a zone, for varying iso-value, are topologically equivalent. Thus one can render objects' approximate geometry using less lattice data points in regions given by a criticality's zone of influence. The management of variable data resolution is comparable to wavelet analysis (See [2], [3]).

We define a natural hierarchical relation among criticalities and represent this relation by a criticality graph. This graph is a tree and has a number of uses. The graph represents the evolution of the level sets as the threshold is varied. The algorithm for computing zones also computes this graph. The algorithm is linear in the number of data points, in the sense that each data point need be accessed from disk only once. This is especially critical in large volumetric data sets, where disk access is the primary computational overhead. The graph, together with the zones, will allow us to organize and simplify (compress) the data in a topologically consistent way. We can also use this organization of the data to limit the number of data readings read from disk, for fast iso-surface rendering. Together with the representative level sets and the LOD tools, we believe that DMT can provide powerful visual search tools for apprehending volumetric data.

We give a simple and elegant iso-surface construction algorithm (called SpiderWeb) that, in addition to being provably correct, is highly parallelizable and, unlike many such algorithms in the literature, extends seamlessly to higher dimensions. Our algorithm obeys the axioms and has other very nice properties.

We give an introductory presentation of our ideas for the case of n-dimensional real-valued data. We make some simplifying assumptions, for the sake of a rather formal presentation, but we discuss where assumptions may be relaxed without changing the utility of the ideas. To convince the reader of the basic soundness and utility of our ideas, we will give our explication for the case of volumetric data readings that can be consistently mapped onto the integer lattice, and thus organized as readings on the vertices of hypercubes. We shall suggest how our results can be naturally extended to imaging, segmentation, and level set interpolation of spatially irregular data readings, and thus to other tiling of space, by applying the results of the digital topology literature.