How to add viscosity in speed function when calculating Fast Marching Method

Sorry, this's more like a question for programming rather than math. On implementing Fast Marching Method, I have a question for adding viscosity to the speed function so the evolved front cannot get into narrow gaps.

My speed function $V$ is a 2D array. Define the speed value on point $(x,y)$ is $V(x,y)$. Bigger the value of $V(x,y)$ faster the fronts propagate, smaller value is otherwise.

From this thread, I get the general idea of slower speed value influence nearby area. To make the evolving front slow down thus cannot go through narrow gaps, I need to obtain new value $\widetilde V(x,y)$ where $\widetilde V(x,y) \le V(x,y)$

To obtain $\widetilde V(x,y)$, I need to use this equation: $$\widetilde V(x,y) = \min_{x',y'}\left\{V(x,y)+L\sqrt{(x-x')^2+(y-y')^2} \right\}$$ In my understanding, I should find max value (the slowest one) within a radius of the center point $(x,y)$ and make it to slow down the original $V(x,y)$, but I'm quite confused how to relate this to the equation and also what's the meaning of variable $L$ (should be a parameter for tuning but I'm not sure)

1 Answer

The approach from the linked thread may or may not do exactly what you want. It does not actually introduce viscous forces into the equation. Instead, it postulates that the speed gradient of a viscous fluid will not exceed some number $L$. The smaller values of $L$ put more restriction on the speed gradient, which corresponds to a more viscous fluid. But $L$ does not directly corresponds to viscosity parameters like Reynolds number; it is purely a computational device, a cheap one at that.

I should find max value (the slowest one) within a radius of the center point $(x,y)$ and make it to slow down the original $V(x,y)$

That would not work very well, I think. If the original $V$ has sharp gradient, like on the illustration in the linked thread, then taking the lowest speed within the certain radius will result in $\tilde V$ that still has a sharp gradient, just at a different place.

The formula $$\widetilde V(x,y) = \min_{x',y'}\left\{V(x',y')+L\sqrt{(x-x')^2+(y-y')^2} \right\}\tag{1}$$ does something similar, but in a more subtle way. (Note that the primes were missing in $V(x',y')$, which is obviously a typo.) You still inspect other points $(x',y')$ for small values of $V$, but their influence does not slow down the fluid at $(x,y)$ to the same extent. Rather, the slow-down effect is mitigated by the term $L\sqrt{(x-x')^2+(y-y')^2}$ which makes the influence of far-away points small or nonexistent. The meaning of (1) is explained in What's behind the function $g(x)=\operatorname{inf}\{f(p)+d(x,p):p\in X\}$?

The actual implementation should be rather simple. Run a loop over all $(x,y)$, and inside of it another look over $(x',y')$. In the inner loop, find the minimum of the right hand side of (1), and record it in the new copy of the array, $\widetilde V$.

After that, use the Fast Marching Method in the usual way, with velocity given by $\widetilde V$.

I have not tested any of this myself. If the result is not satisfactory, perhaps you'll get more help at Computational Science.

• thanks your explanation (especially about the typo). I'm still working on my code. Actually I use FMM for image segmentation. Perhaps the problem is either my calculation to compute per-pixel feature isn't pretty good or the speed function itself. Commented Dec 26, 2013 at 1:16