I have been following some papers on the application of the Merriman-Bence-Osher (MBO) scheme for mean curvature flow and its application to image segmentation. I have some of the citations below by Bertozzi and Flenner, and by Merkurjev et al., and by Van Gennip, et al.
I am having trouble understanding the exact intuition/heuristic behind connecting something like front propagation to object like graphs. It seems like these authors are using graph cuts or spectral clustering to segment the graphs, so I am not clear on what the contribution of the MBO scheme is? Like you could apply spectral clustering to graphs without the MBO scheme and it would work. So I wanted to make sure what the MBO scheme is contributing?
Let me explain the basic ideas for context. Mean curvature flow is a continuous deformation of some set. Given a set and its boundary--imagine something like the map of Italy and its boundary--front propagation will deform that boundary proportional to the curvature at each point on the boundary. So the boot of Italy will gradually become more rounded and convex as the more curved regions deform faster than the flatter regions. Level set methods are a robust and efficient way to numerically solve the front propagation without getting bogged down in the topological changes that can happen to the boundary as it deforms. That all makes sense.
I am having a hard time understanding exactly what these authors are doing when they segment something discrete like a graph using the MBO scheme? They are using graph cuts, which make a lot of sense. Graph cuts tries to minimize the energy of a graph by cutting high energy edges. The energy on each edge is computed usually according to some kernel function or dot product, etc.
So my question is how is the MBO scheme applied to graph cuts? Like are they using some kind of PDE kernel to compute energies on the edges, or is it something that I am not comprehending properly? I can see how computing the energies using a PDE kernel could be attractive because then you could use some non-local operators in the calculation. Is it that simple, or is there some additional nuance that I am missing.
Thanks.
https://epubs.siam.org/doi/abs/10.1137/11083109X
I'm still learning about this myself, but hope this helps.
In image segmentation, we are interested in MCF on a discrete setting. You can think of an image as assigning a value to each pixel on a lattice (or more generally, a graph). We want a partition of the graph into two different parts, e.g. foreground/background. We want the boundary of the partition to be short, which is why this is a min-cut problem.
MCF is a curve-shortening flow. In our application, the curve is the boundary of the graph partition, and if we want to solve a min-cut problem then MCF takes an initial condition and moves it closer to the cut-minimizer.
The MBO scheme is used for approximating mean curvature flow: I posted a question and answered my own question as I was learning about this awhile back: Mean curvature flow vs. diffusion. The point is that MBO is the algorithm that is used in practice to compute MCF on a graph.
Spectral clustering is another way to partition a graph. But it's based on a different principle (projection onto a low-dimensional space) so will have slightly different results. The use of MCF for image-segmentation is directly related to the intuition that we want a segmented image to have smooth boundaries.