Digital Morse theory
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
- Peers: two islands that at a lower water level 'merge' into a common parent.
- Parent: an island that splits into two child islands at a higher water level.
- 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.
- Cox, J., Karron, D. B., and Ferdous, N. (2003). Topological Zone Organization of Scalar Volume Data. Journal of Mathematical Imaging and Vision. March 2003, Volume 18, Issue 2, pp 95-117 http://link.springer.com/article/10.1023%2FA%3A1022113114311
- Digital Morse Theory for Scalar Volume Data . DIMACS 2003.