Path centering

The path found at figure is visibly a good approximation of the shortest path between the two points. It follows the corners of the domain when it bends and it crosses open spaces in straight lines. It does not present the jagged-ness of Lengyel's paths.
On the other hand, it is not the optimal path for our virtual endoscopy application. In colorful terms, the fly through behaves too much like a formula one to be cosy for the passengers. That is, the camera should follow a more centered path through the bowels, while remaining smooth.
This behaviour can be obtained using a variant of the snake model introduced by Kass et al. [89]. In this model, the path is considered as a parameterized curve - or snake - v(s) = ( x(s),y(s))^T with $s \in [0,1]$. The snake evolves in order to minimize an energy defined as

$$E(v) = \int_0^1 w_1 \left\vert{\frac{\partial v}{\partial s}}... ...ert{\frac{\partial^2 v}{\partial s^2}}\right\vert + P(v) ds$$ (9.1)

where w₁ and w₂ are smoothing terms and P(v) is the image term. In segmentation application, P(v) is typically a decreasing function of the image gradient, forcing the snake to move towards the edges in the image.
Typically, equation () is solved by deriving an evolution equation, then solving it numerically using finite differences. Practically, it means iterating

(9.2)

where I is the identity matrix, $\tau$ the chosen time step, A the smoothness matrix corresponding to the w₁ and w₂ terms and F(v) the image force derived from the potential energy P(v).

  

Figure 9.4: Left: Euclidean DT from the walls of the maze Right: Centered path

In order to center and smooth the path in figure , we adapt the snake model as follows. First of all, the image potential energy is used to drive the snake towards the center of the bowel. To achieve this, we use a decreasing function of the Euclidean distance from the edges of the domain, illustrated at figure . Also, the force deriving from this potential only needs to applied perpendicularly to the snake, because the parallel component would only modify the sampling of the curve and not its location. Therefore, the image force is defined as follows

$$\overrightarrow{F(v)} \overrightarrow{G(v)} - \frac{ (\overrightarrow{v}.\overrightarrow{G(v)}) . \overrightarrow{v} }{\vert v\vert^2}$$ = (9.3)

$$\mathrm{with} \; \; \overrightarrow{G(v)} -\nabla(-D(v))$$ = (9.4)

with arrows omitted over v where its vectorial nature is not important.
For the smoothing term, we use a simplified model. w₂ is set to 0 so that only the first derivative is used. Then, $(I + \tau . A)^{-1}$ is approximated by $I - \tau . A$. Although this is potentially less stable than matrix inversion, experiments show that the smoothness of the distance-based image energy is a sufficient guarantee of stability. With this simplified model, the snake iteration can be de-coupled into two sub-iterations

$$v^{\, t'} v^{\, t} + F(v^{\, t})$$ = (9.5)

$$v^{\, t+1}(i) (1-\tau) . v^{\, t'}(i) + \frac{\tau}{2} . ( v^{\, t'}(i-1) + v^{\, t'}(i+1))$$ = (9.6)

where v(i) is the discrete representation of the curve v.
In our experiments, the snake converges in a few iterations and stabilizes itself very robustly. The resulting centered and smoothed path is illustrated at figure .