Low Dimensional Topology

November 14, 2012

Digital spheres and Reeb graphs

Filed under: Data topology — Jesse Johnson @ 1:52 pm

This post is about a slightly different direction in the topology of data sets than what I’ve written about previously, but one that is much more explicitly low-dimensional. When a doctor takes an MRI scan of a patient’s brain, they get a three dimensional lattice of points labeled foreground (brain) and background (not brain). The boundary between these two sets should be a sphere, and this is important for things like mapping regions of the brain to biological functions. However, because the MRI is not 100% accurate, even if your brain is a sphere, the MRI data may not be. Two electrical engineers (David Shattuck and Richard Leahy ) proposed a method to determine if the boundary of a brain scan is a sphere by building a certain graph from the cross sections of the scan. This seems to be one of the rare instances in which a cleanly stated math problem just drops out of science and engineering. Shortly after this, three mathematicians (Lowell Abrams, Donniell Fishkind and Carey Priebe ) picked the conjecture up, proved it, then proved a number of follow-up results. Below the fold, I’ll describe the conjecture and how it’s related to a classical topological tool – the Reeb graph of a Morse function.

First let me outline the original conjecture. We can think of the digital data set as union of closed unit-sided cubes with their corners at unit lattice points in $\mathbf{R}^3$, say with coordinates $x,y,z$.  The union of the cubes is called the foreground and the closure of its complement is called the background. A cross section will be the intersection of the foreground or the background with the $yz$ plane cross an interval $[i,i+1]$. The intersection of two adjacent cross sections is a union of squares in the $yz$ plane along which they meet. Define the R-graph of the foreground (background) to be the graph whose vertices are components of the cross sections of the foreground (background, respectively) and whose edges correspond to components of the intersection of adjacent cross sections, connecting the components that contain the intersection. Note that there may be multiple edges between the same pair of vertices. Shattuck and Leahy conjectured, then Abrams, Fishkind and Priebe proved that (assuming the boundary is a surface) the boundary of the foreground will be a sphere if and only if the R-graphs of both the foreground and the background are trees.

Before I try to explain why one should expect this conjecture to be true, lets talk about Reeb graphs of Morse functions. Recall that a Morse function on a surface $S$ is a function $f : S \rightarrow \mathbf{R}$ with a finite number of non-degenerate critical points (saddles and local minima and maxima) at distinct levels. The pre-image of a generic point in $\mathbf{R}$ is a collection of loops and the Reeb graph of $f$ is the quotient of $S$ that sends each component of the pre-image of each point in $\mathbf{R}$ to a single point. As suggested by the name, the resulting topological space is a graph: Away from critical points, the level loops in $S$ form parallel families whose quotients form edges. At each saddles, three such families come together to form a valence-three vertex and at each local minimum or maximum, a single parallel family collapses, producing a valence-one vertex. The structure of the Reeb graph depends on the Morse function, but only to a degree: The rank of the (fundamental group of) the graph is always precisely the genus of $S$ (half the rank of $S$). In particular, $S$ will be a sphere if and only if the Reeb graph is a tree. If you work out a few examples on the sphere, it should quickly become clear why it is always a tree.

The R-graphs defined by the foreground and background are very similar to the Reeb graph of a Morse function, though there are some important differences. In particular, the foreground is a three-dimensional object, not a surface. So if one of the cross sections is not a disk, it will be bounded by more than one loops, which will be identified together in the R-graph. This is why one needs to look at the R-graphs of both the foreground and the background. However, the R-graphs are still capturing very similar information and as I understand it, we should expect the conjecture to be true for similar reasons to why the Reeb graph for any Morse function on the sphere is a tree.

 Shattuck, D.W.; Leahy, R.M.; , “Automated graph-based analysis and correction of cortical volume topology,” Medical Imaging, IEEE Transactions on , vol.20, no.11, pp.1167-1177, Nov. 2001. (Here, if you have digital access to IEEE journals.)

 Abrams, L.; Fishkind, D.E.; Priebe, C.E.; , “A proof of the spherical homeomorphism conjecture for surfaces,” Medical Imaging, IEEE Transactions on , vol.21, no.12, pp.1564-1566, Dec. 2002.  (Here, if you have digital access to IEEE journals.)