next up previous contents index
Next: skeleton Up: Reference Previous: lsnakes_demo   Contents   Index

mac_snakes

$ \bigcirc$Name


mac_snakes Maximizing Average Contrast Snakes for contour detection




$ \bigcirc$Command Synopsis


mac_snakes [-p power] [-n niter] [-s step] [-v] [-V V] u in out



-p power : g(s)= |  s |   $ \hat{{}}$  power (default power=1.0)

-n niter : number of iterations (default 1000)

-s step : evolution step (default 1.0)

-v : verbose mode

-V V : select video mode and specify zoom (e.g. 2)

u : input Fimage

in : input curves (Dlists)

out : output curves (modified input)




$ \bigcirc$Function Summary


Dlists mac_snakes (u , in , niter , step , power , v , V )

Fimage u ;

Dlists in ;

int *niter ;

float *V ;

double *step , *power ;

char *v ;




$ \bigcirc$Description


This module implements the Kimmel and Bruckstein snake model [KB02] for contour detection (or optimization). Its goal is to maximize with respect with $ \gamma$ (an arclength parameterized curve) the average contrast

E($\displaystyle \gamma$) = $\displaystyle {\frac{1}{{L(\gamma)}}}$$\displaystyle \int_{{0}}^{{L(\gamma)}}$g$\displaystyle \left(\vphantom{\frac{}{}\!\!
Du(\gamma(s))\cdot n(s)}\right.$$\displaystyle {\frac{{}}{{}}}$Du($\displaystyle \gamma$(s)) . n(s)$\displaystyle \left.\vphantom{\frac{}{}\!\!
Du(\gamma(s))\cdot n(s)}\right)$ds,

where g is an increasing scalar function, L($ \gamma$) the length of the curve $ \gamma$ and n(s) its normal vector (that is, orthogonal to $ \gamma{^\prime}$(s)). Such a model has several advantages compared to the classical Kass-Witjin-Terzopoulos model [KWT87] and the more elaborate model of geodesic active contours from Caselles, Kimmel and Sapiro [CKS97]. The use of a normal contrast (instead of a gradient norm) is an improvement to the model of Fua and Leclerc [FL90].

This module only implements the case g(s) = | s|power, but it could be easily adapted to more general functions g. The influence of the choice of g is discussed in [DMM03]. The default is g(s) = | s|, but powers smaller than 1 could be preferred in order to reduce even more the sensitivity to the image contrast.

The numerical scheme is based on a gradient descent (with step step) associated to a discrete version of E($ \gamma$) (see the description below, and [DMM03] for a complete discussion and full details). An input Fimage (u) and an initial set in of curves (Dlists) should be provided to the module, which outputs a new (final) set of curves out after niter iterations (-n option). Intermediate states can be monitored by printing the energy evolution (with -v option) or visually with the -V option followed by a zoom factor (try 2 for example). Note that the number of points of each curve is kept constant during the evolution, so that an appropriate (fine enough) sampling of each initial curve is needed: rough polygons will not do in general!

Practical Use

Due to their sensitivity to initial conditions, snakes models should be used for interactive contour optimization rather than for contour detection. To obtain good results, one should

An example is given by the following sequence of commands:

circle -r 20 -n 100 c
fkzrt c c 1 0 115 170
fkview -s -b cimage c &
fsepconvol -g 1 cimage u
mac_snakes -V 2 -s 1 -n 3000 u c out

For an interactive choice of the initial contour, the first two lines may be replaced by

readpoly cimage c
gass -e 2 c c
(type 'q' after drawing manually the initial contour).

Numerical Scheme

For a non-Euclidean parameterization $ \gamma$(p) : [a, b]$ \to$IR2, the energy we want to maximize writes

F($\displaystyle \gamma$) = $\displaystyle {\frac{{\int_a^b g\left(Du.\frac{\gamma'(p)^\perp}{\vert\gamma'(p...
...rt}\right) \,\vert\gamma'(p)\vert\, dp}}{{\int_a^b \vert\gamma'(p)\vert\, dp}}}$. (11)
Rather than writing the Euler equation for (11) and then discretizing it, we discretize the energy and compute its exact derivative with respect to the discrete curve. Let us suppose that the snake is represented by a polygonal curve M1..Mn (either closed or with fixed endpoints). For the curve length, we can take

L = $\displaystyle \sum_{i}^{}$|$\displaystyle \Delta_{i}^{}$|        with        $\displaystyle \Delta_{i}^{}$ = Mi+1 - Mi.

Now the discrete energy can be written F = $ {\frac{E}{L}}$, with

E = $\displaystyle \sum_{i}^{}$g(ti)|$\displaystyle \Delta_{i}^{}$|,

ti = wi . $\displaystyle {\frac{{\Delta_i}}{{\Vert\Delta_i\Vert}}}$,    wi = Du$\scriptstyle \bot$($\displaystyle \Omega_{i}^{}$),    and    $\displaystyle \Omega_{i}^{}$ = $\displaystyle {\frac{{M_i+M_{i+1}}}{2}}$.

Differentiating E with respect to Mk, we obtain

$\displaystyle \nabla_{{M_k}}^{}$F = $\displaystyle {\frac{1}{L}}$$\displaystyle \left(\vphantom{ \frac{}{}\!\!
\nabla_{M_k} E- F\nabla_{M_k} L}\right.$$\displaystyle {\frac{{}}{{}}}$$\displaystyle \nabla_{{M_k}}^{}$E - F$\displaystyle \nabla_{{M_k}}^{}$L$\displaystyle \left.\vphantom{ \frac{}{}\!\!
\nabla_{M_k} E- F\nabla_{M_k} L}\right)$

with

$\displaystyle \nabla_{{M_k}}^{}$L = $\displaystyle {\frac{{\Delta_{k-1}}}{{\Vert\Delta_{k-1}\Vert}}}$ - $\displaystyle {\frac{{\Delta_k}}{{\Vert\Delta_k\Vert}}}$,

$\displaystyle \nabla_{{M_k}}^{}$E = vk + vk-1 + zk-1 - zk,

vi = $\displaystyle {\textstyle\frac{1}{2}}$g'(ti)D((Du$\scriptstyle \bot$)T)($\displaystyle \Omega_{i}^{}$)$\displaystyle \Delta_{i}^{}$,

zi = g'(ti)wi + h(ti)$\displaystyle {\frac{{\Delta_i}}{{\Vert\Delta_i\Vert}}}$

and h(t) = g(t) - tg'(t). Note that

D((Du$\scriptstyle \bot$)T) = D(- uy    ux) = $\displaystyle \left(\vphantom{\begin{array}{cc}
-u_{xy} & u_{xx} \\
-u_{yy} & u_{xy}
\end{array}}\right.$$\displaystyle \begin{array}{cc}
-u_{xy} & u_{xx} \\
-u_{yy} & u_{xy}
\end{array}$$\displaystyle \left.\vphantom{\begin{array}{cc}
-u_{xy} & u_{xx} \\
-u_{yy} & u_{xy}
\end{array}}\right)$.

Numerically, we compute Du at integer points with a 3×3 finite differences scheme, and D2u with the same scheme applied to the computed components of Du. This introduces a slight smoothing of the derivatives, which counterbalances a little the strong locality of the snake model. These estimations at integer points are then extended to the whole plane using a bilinear interpolation.


To compute the evolution of the snake, we use a two-steps iterative scheme.

  1. The first step consists in a reparameterization of the snake according to arc length. It can be justified in several ways : aside from bringing stability to the scheme, it guarantees a geometric evolution of the curve, it ensures an homogeneous estimate of the energy, and it prevents singularities to appear too easily. However, we do not prevent self-intersections of the curve.
  2. The second step is simply a gradient evolution with a fixed step. If (Min)i represents the (polygonal) snake at iteration n and ($ \tilde{M}_{i}^{n}$)i its renormalized version after step 1, then we set

    Min+1 = $\displaystyle \tilde{M}_{i}^{n}$ + step . $\displaystyle \nabla_{{\tilde M_i^n}}^{}$F.




$ \bigcirc$See Also


czoom, fderiv.




$ \bigcirc$Version 1.0


Last Modification date : Tue Apr 8 04:08:35 2003


$ \bigcirc$Author


Lionel Moisan






next up previous contents index
Next: skeleton Up: Reference Previous: lsnakes_demo   Contents   Index
mw 2004-05-05