Smoothing

Smoothing

Smoothing is performed with a snake-like technique derived from the AMINI and al. Algorithm [Amini, 1990]. It allows two possibilities:

smoothing of the erratic parts of the path and
smoothing of the whole path.

This second possibility is interesting for choosing the level of detail required to represent the geographic features on a map of a given scale (generality level). The advantage of a snake is to use a more global information, and thus have a more global ``view'' of the shape.

The algorithm uses some control points to compute energy and minimize it; the strategy is a mix of snake technique and dynamic programming technique [Amini, 1990]. Control points are more or less close together; this permits to tune the resolution of the result. It is possible to tune the width of the neighborhood around each point to have a best insensitivity to noise, but a wide neighborhood slows down the process.

The main problem of snake-like technique is the non convexity of the images [L. Alquier, 1996], [M. Kass, 1988b], [G. Nicchiotti, 1991], the way to the optimal solution must be continuously ascending or descending, else, the snake can stop on local hot spots, due to noise, or wrong detection. As we use a dynamic programming at first, the resulting curve gives an initial snake very close to the optimal solution; we can reduce the neighborhood of control points to minimum size (i.e. 3X3 windows), so convergence is very fast.

The energy function integrates three terms to assume the desired behavior. The parametric expression is given by:

$\begin{displaymath}E= \int_0^1[\underbrace{E_{image}(v(s))}_{\mbox{External ener......^2+ \beta\vert v_{ss}(s)\vert^2)}_{\mbox{Internal energy}}].d_s\end{displaymath}$

With:

v(s)= (x(s), y(s))

$\begin{displaymath}E_{image}= w. \int_{-\Delta x}^{+\Delta x} \int_{-\Delta x}^{+\Delta x} I(x, y).dy.dx\end{displaymath}$

\|v_s(s)\|²	:	First derivative, conditions the elasticity of the curve.
\|v_ss(s)\|²	:	Second derivative, conditions the smoothness of the curve.
E_image	:	Attractive force acting on each control point, a sum of radiometry values around control points.
$\alpha, \beta, w$	:	Weights adjusting the influence of each term in the energy function E.

In the early tests we used a ``blurring'' algorithm to fill the holes and to help the convergence of the snake, the experiments have shown that it is not useful in most of cases because the dynamic programming finds a solution close to the optimal one.

IRIT-UPS