Digital Morse theory

From HandWiki

In mathematics, digital Morse theory[1][2] is a digital adaptation of continuum Morse theory for scalar volume data. This is not about the Samuel Morse's Morse code of long and short clicks or tones used in manual electric telegraphy. The term was first promulgated by DB Karron based on the work of JL Cox and DB Karron. 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

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. 
  2. Cox, J.; Karron, D.B.; Ferdous, N. (2002). "Digital Morse Theory for scalar volume data". DIMACS 2003. http://www.casi.net/DMT.pdf.