Digital Morse theory

Last updated

In mathematics, digital Morse theory [1] [2] is a digital adaptation of continuum Morse theory for scalar volume data. The term was first promulgated by DB Karron based on the work of JL Cox and DB Karron.

Contents

The main utility of a digital Morse theory is that it serves to provide a theoretical basis for isosurfaces (a kind of embedded manifold submanifold) and perpendicular streamlines in a digital context. The intended main application of DMT is in the rapid semiautomatic segmentation objects such as organs and anatomic structures from stacks of medical images such as produced by three-dimensional computed tomography by CT or MRI technology.

DMT Tree

A DMT tree is a digital version of a Reeb graph or contour tree graph, showing the relationship and connectivity of one isovalued defined object to another. Typically, these are nested objects, one inside another, giving a parent-child relationship, or two objects standing alone with a peer relationship.

The essential insight of Morse theory can be given in a little parable.

The fish tank thought experiment

The fish tank thought experiment: Counting islands as the water level changes

The essential insight of continuous Morse theory can be intuited by a thought experiment. Consider a rectangular glass fish tank. Into this tank, we pour a small quantity of sand such that we have two smoothly sloping small hills, one taller than the other. Now, we fill this tank to the brim with water. We now start a count of the number of island objects as we very slowly drain the tank.

Our initial observation is that there are no island features in our tank scene. As the water level drops, we observe the water level just coincident with the peak of the tallest sand hill. We next observe the behavior of the water at the critical peak of the hill. We see a degenerate point island contour, with zero area, zero perimeter, and infinite curvature. A vanishing small change in the water level and this point contour expand into a tiny island. We now increment our island object count by +1. We continue to drain water from the tank. We next observe the creation of the second island at the peak of the second little hill. We again increment our island object count by +1 to two objects. Our little sea has two island objects in it. As we continue to slowly lower the water level in our little tank sea. We now observe the two island contours gradually expand and grow toward each other. As the water level reaches the level of the critical saddle point between the two hills the island contours touch at precisely the saddle point. We observe that our object count decrements by –1 to give a total island count of one. The essential feature of this rubric is that we only need to count the peaks and passes to inventory all of the islands in our sea, or objects in our scene. This approach works even as we increase the complexity of the scene.

We can use the same idea of enumerating peak, pits and pass criticalities in a very complex archipelago of island features, at any size scale, or any range of size scales, including noise at any size scale.

The relationship between island features can be

  1. Peers: two islands that at a lower water level 'merge' into a common parent.
  2. Parent: an island that splits into two child islands at a higher water level.
  3. Progeny: An island that has a Parent island feature as related above.

Digital Morse theory relates Peaks, Pits and Passes to Parents, Peers and Progeny. This gives a cute mnemonic: PPP → ppp.

As the topology does not care about geometry or dimensionality (directly), complex optimizations in infinite dimensional Hilbert spaces are amenable to this kind of analysis.

See also

Related Research Articles

<span class="mw-page-title-main">Discrete mathematics</span> Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that can be considered "discrete" rather than "continuous". Objects studied in discrete mathematics include integers, graphs, and statements in logic. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers, calculus or Euclidean geometry. Discrete objects can often be enumerated by integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics".

An illusion is a distortion of the senses, which can reveal how the mind normally organizes and interprets sensory stimulation. Although illusions distort the human perception of reality, they are generally shared by most people.

<span class="mw-page-title-main">Optical illusion</span> Visually perceived images that differ from objective reality

In visual perception, an optical illusion is an illusion caused by the visual system and characterized by a visual percept that arguably appears to differ from reality. Illusions come in a wide variety; their categorization is difficult because the underlying cause is often not clear but a classification proposed by Richard Gregory is useful as an orientation. According to that, there are three main classes: physical, physiological, and cognitive illusions, and in each class there are four kinds: Ambiguities, distortions, paradoxes, and fictions. A classical example for a physical distortion would be the apparent bending of a stick half immerged in water; an example for a physiological paradox is the motion aftereffect. An example for a physiological fiction is an afterimage. Three typical cognitive distortions are the Ponzo, Poggendorff, and Müller-Lyer illusion. Physical illusions are caused by the physical environment, e.g. by the optical properties of water. Physiological illusions arise in the eye or the visual pathway, e.g. from the effects of excessive stimulation of a specific receptor type. Cognitive visual illusions are the result of unconscious inferences and are perhaps those most widely known.

<span class="mw-page-title-main">Topography</span> Study of the forms of land surfaces

Topography is the study of the forms and features of land surfaces. The topography of an area may refer to the land forms and features themselves, or a description or depiction in maps.

Riemannian geometry is the branch of differential geometry that studies Riemannian manifolds, defined as smooth manifolds with a Riemannian metric. This gives, in particular, local notions of angle, length of curves, surface area and volume. From those, some other global quantities can be derived by integrating local contributions.

<span class="mw-page-title-main">Landform</span> Feature of the solid surface of a planetary body

A landform is a natural or anthropogenic land feature on the solid surface of the Earth or other planetary body. Landforms together make up a given terrain, and their arrangement in the landscape is known as topography. Landforms include hills, mountains, canyons, and valleys, as well as shoreline features such as bays, peninsulas, and seas, including submerged features such as mid-ocean ridges, volcanoes, and the great ocean basins.

In mathematics, specifically in differential topology, Morse theory enables one to analyze the topology of a manifold by studying differentiable functions on that manifold. According to the basic insights of Marston Morse, a typical differentiable function on a manifold will reflect the topology quite directly. Morse theory allows one to find CW structures and handle decompositions on manifolds and to obtain substantial information about their homology.

In gauge theory and mathematical physics, a topological quantum field theory is a quantum field theory which computes topological invariants.

<span class="mw-page-title-main">Scientific visualization</span> Interdisciplinary branch of science concerned with presenting scientific data visually

Scientific visualization is an interdisciplinary branch of science concerned with the visualization of scientific phenomena. It is also considered a subset of computer graphics, a branch of computer science. The purpose of scientific visualization is to graphically illustrate scientific data to enable scientists to understand, illustrate, and glean insight from their data. Research into how people read and misread various types of visualizations is helping to determine what types and features of visualizations are most understandable and effective in conveying information.

<span class="mw-page-title-main">Geometric topology</span> Branch of mathematics studying (smooth) functions of manifolds

In mathematics, geometric topology is the study of manifolds and maps between them, particularly embeddings of one manifold into another.

In algebraic geometry and theoretical physics, mirror symmetry is a relationship between geometric objects called Calabi–Yau manifolds. The term refers to a situation where two Calabi–Yau manifolds look very different geometrically but are nevertheless equivalent when employed as extra dimensions of string theory.

<span class="mw-page-title-main">Topographic prominence</span> Vertical measurement of the independence of a summit

In topography, prominence measures the height of a mountain or hill's summit relative to the lowest contour line encircling it but containing no higher summit within it. It is a measure of the independence of a summit. The key col ("saddle") around the peak is a unique point on this contour line and the parent peak is some higher mountain, selected according to various criteria.

In mathematics, obstruction theory is a name given to two different mathematical theories, both of which yield cohomological invariants.

In mathematics, Tannaka–Krein duality theory concerns the interaction of a compact topological group and its category of linear representations. It is a natural extension of Pontryagin duality, between compact and discrete commutative topological groups, to groups that are compact but noncommutative. The theory is named after Tadao Tannaka and Mark Grigorievich Krein. In contrast to the case of commutative groups considered by Lev Pontryagin, the notion dual to a noncommutative compact group is not a group, but a category of representations Π(G) with some additional structure, formed by the finite-dimensional representations of G.

In computer graphics, marching squares is an algorithm that generates contours for a two-dimensional scalar field. A similar method can be used to contour 2D triangle meshes.

Digital topology deals with properties and features of two-dimensional (2D) or three-dimensional (3D) digital images that correspond to topological properties or topological features of objects.

<span class="mw-page-title-main">Terrain cartography</span> Representation of surface shape on maps

Terrain cartography or relief mapping is the depiction of the shape of the surface of the Earth on a map, using one or more of several techniques that have been developed. Terrain or relief is an essential aspect of physical geography, and as such its portrayal presents a central problem in cartographic design, and more recently geographic information systems and geovisualization.

<span class="mw-page-title-main">Watershed (image processing)</span> Transformation defined on a grayscale image

In the study of image processing, a watershed is a transformation defined on a grayscale image. The name refers metaphorically to a geological watershed, or drainage divide, which separates adjacent drainage basins. The watershed transformation treats the image it operates upon like a topographic map, with the brightness of each point representing its height, and finds the lines that run along the tops of ridges.

<span class="mw-page-title-main">Reeb graph</span>

A Reeb graph is a mathematical object reflecting the evolution of the level sets of a real-valued function on a manifold. According to a similar concept was introduced by G.M. Adelson-Velskii and A.S. Kronrod and applied to analysis of Hilbert's thirteenth problem. Proposed by G. Reeb as a tool in Morse theory, Reeb graphs are the natural tool to study multivalued functional relationships between 2D scalar fields , , and arising from the conditions and , because these relationships are single-valued when restricted to a region associated with an individual edge of the Reeb graph. This general principle was first used to study neutral surfaces in oceanography.

Boundary tracing, also known as contour tracing, of a binary digital region can be thought of as a segmentation technique that identifies the boundary pixels of the digital region. Boundary tracing is an important first step in the analysis of that region. Boundary is a topological notion. However, a digital image is no topological space. Therefore, it is impossible to define the notion of a boundary in a digital image mathematically exactly. Most publications about tracing the boundary of a subset S of a digital image I describe algorithms which find a set of pixels belonging to S and having in their direct neighborhood pixels belonging both to S and to its complement I - S. According to this definition the boundary of a subset S is different from the boundary of the complement I – S which is a topological paradox.

References

  1. Cox, J.; Karron, D. B.; Ferdous, N. (2003). "Topological Zone Organization of Scalar Volume Data". Journal of Mathematical Imaging and Vision. 18 (2): 95–117. doi:10.1023/A:1022113114311. S2CID   24983543.
  2. Cox, J.; Karron, D.B.; Ferdous, N. (2002). "Digital Morse Theory for scalar volume data" (PDF). DIMACS 2003. Archived from the original (PDF) on 2009-01-24.