next up previous contents index
Next: cfdiffuse Up: Reference Previous: fzrt   Contents   Index

amss

$ \bigcirc$Name


amss Affine Morphological Scale Space (or Mean Curvature Motion) - by anisotropic diffusion




$ \bigcirc$Command Synopsis


amss [-i] [-p] [-S Step] [-m MinGrad] [-s outputStep] [-f firstScale] [-l lastScale] [-n] [-d cimageD] [-g cimageG] [-c cimageC] [-D cmovieD] [-G cmovieG] [-C cmovieC] image



-i : flag to cancel isotropic diffusion in smooth area

-p : flag to compute AMSS model (power 1/3) instead of MCM (power 1)

-S Step : scale step for each iteration (default 0.1)

-m MinGrad : Minimum of the gradient norm to compute the curvature (default 0.5)

-s outputStep : scale interval between two images (for movie outputs) (default 0.1)

-f firstScale : first scale of diffusion (default 0.0)

-l lastScale : last scale of diffusion (default 2.0)

-n : flag to prevent curvature normalization

-d cimageD : output fimage of the last diffusion

-g cimageG : output fimage of the last gradient

-c cimageC : output fimage of the last curvature

-D cmovieD : output cmovie of successive diffusions

-G cmovieG : output cmovie of successive gradients

-C cmovieC : output cmovie of successive curvatures

image : original picture (input fimage)




$ \bigcirc$Function Summary


void amss (isotrop , power , Step , MinGrad , outputStep , firstScale , lastScale , image , imageD , imageG , imageC , cmovieD , cmovieG , cmovieC , no_norm )

char *isotrop ;

char *power ;

float *Step ;

float *MinGrad ;

float *outputStep ;

float *firstScale ;

float *lastScale ;

Fimage image ;

Fimage *imageD ;

Fimage *imageG ;

Fimage *imageC ;

Cmovie cmovieD ;

Cmovie cmovieG ;

Cmovie cmovieC ;

char *no_norm ;




$ \bigcirc$Description


Multiscale Analysis of image.

The fundamental equation of image processing

AMSS        $\displaystyle {\frac{{\partial u}}{{\partial t}}}$ =|Du|(curv(u))$\scriptstyle {\frac{{1}}{{3}}}$ (1)

u(0,.) = u0(.)

has been discovered recently with existence proofs in the sense of viscosity solutions [AGLM93]. This is the unique model of multiscale analysis of image, affine invariant and morphological invariant.

Another useful, less invariant (not affine invariant), but more easy for a numerical viewpoint, is the same equation without the power 1/3 : ``the mean curvature motion".

MCM        $\displaystyle {\frac{{\partial u}}{{\partial t}}}$ =|Du|(curv(u)) (2)

The function amss will process the model AMSS or the mean curvature motion, from t = tbegin to t = tend.



INPUTS of amss.

image
= u is the original picture (type : fimage).

- p

By default, the module process the mean curvature motion (MCM). By selecting this option, the module process the AMSS model.

- l
lastScale =LS
amss will process the equation (1) or (2) until the normalised scale equals LS.

The normalised scale is defined such that a circle of radius LS in the original image, disapears when the normalised scale = LS. Then the rescaling depends of the power of the curvature :

If MCM (equation(2)), then tend = LS2/2.

If AMSS (equation(1)), then tend = LS $\scriptstyle {\frac{}{}}$43×3/4.

If this option is not used LS= 2.0.

- f
firstScale = FS
This option allows to fix tbegin non equal to zero. Suppose that, for example, we have already calculated the image u at scale 2: u2, and we want to have it at scale 4: u4. We can apply amss to u2. But, we must precise to amss that u2 is already at scale 2, by using option -f 2. Then, the instruction : amss -f 2 -t 4 u2 will process u4.

As for LS, FS is a normalized scale.

If this option is not used, FS is 0.

-s
OutPutStep

OutPutStep is the scale interval between two diffusions (default is 0.1): the module will process the image at each normalised scale : k × OutPutScale + FS, until LS (k $ \in$ IN).

-S
Step
Step is the interval of scale for the discretization of the equations.

$\displaystyle {\frac{{\partial u}}{{\partial t}}}$ = $\displaystyle {\frac{{u(.,t+step) - u(.,t)}}{{step}}}$

It must be a float number and nonnegative (default value is 0.1).

For AMSS model Step must be lower than 0.1, for the mean curvature motion Step must be lower than 0.5. Then,

If MCM, then Step must be $ \leq$ 0.1.

If AMSS, then Step must be $ \leq$ 0.5.

The number of iterations needed by amss is calculated as following : If MCM

Numberofiterations = $\displaystyle {\frac{{LS^2 - FS^2}}{{2*Step}}}$

If AMSS

Numberofiterations = $\displaystyle {\frac{{3}}{{4}}}$$\displaystyle {\frac{{ LS^\frac{4}{3} - FS^\frac{4}{3}}}{{Step}}}$

-i

By default, the module will process an isotropic diffusion when the estimated gradient is less than MinGrad. This can be useful to avoid a problem of our discretization : suppose the image is a black point on white background, then our estimated gradient by centered finite differences is equal to zero at this point. Then, it never disappears.

The -i flag cancels this isotropic diffusion : nothing will be done at points with gradient norm less than MinGrad.

OUTPUTS of amss.

Several outputs can be selected among diffusion image, gradient and curvature, in the Fimage type (for last scale) or Cmovie type (for all intermediate scales). Notice that for Cmovie type, precision may be lost since a conversion from floating point values to char values is necessary. For the curvature, a normalization k $ \mapsto$ 100k + 128 is performed, but it can be cancelled using the -n option.

Numerical scheme.

Equations (1) and (2) verify the following properties

The scheme is based on a diffusive interpretation of the equations. Indeed, if $ \xi$ is a unit vector, such that $ \nabla$u.$ \xi$ = 0, and u$\scriptstyle \xi$$\scriptstyle \xi$ the second derivative of u in the direction $ \xi$, we have :

(2) $\displaystyle \Leftrightarrow$ $\displaystyle {\frac{{\partial u}}{{\partial t}}}$ = u$\scriptstyle \xi$$\scriptstyle \xi$

This formulation yields an anisotropic diffusion equation. Anisotropic, because we diffuse only in one direction $ \xi$, depending on the gradient. (compare with the isotropic diffusion ( $ {\frac{{\partial u}}{{\partial t}}}$ = $ \Delta$u) i.e. the heat equation).

Equation (1) can be rewritten as $ {\frac{{\partial u}}{{\partial t}}}$ = ($ \nabla$u)$\scriptstyle {\frac{{2}}{{3}}}$(u$\scriptstyle \xi$$\scriptstyle \xi$)$\scriptstyle {\frac{{1}}{{3}}}$, where ($ \nabla$u)$\scriptstyle {\frac{{2}}{{3}}}$ is understood as the speed of the diffusion.

The schemes which we wish to discuss compute u$\scriptstyle \xi$$\scriptstyle \xi$ by a quasilinear formula in the sense defined above.



In order to have consistency, we must find $ \lambda_{0}^{}$,$ \lambda_{1}^{}$,$ \lambda_{2}^{}$,$ \lambda_{3}^{}$,$ \lambda_{4}^{}$, such that :

u$\scriptstyle \xi$$\scriptstyle \xi$ = $\displaystyle {\frac{{1}}{{\Delta x^2}}}$(- 4$\displaystyle \lambda_{0}^{}$ui, j + $\displaystyle \lambda_{1}^{}$(ui+1, j + ui-1, j) + $\displaystyle \lambda_{2}^{}$(ui, j+1 + ui, j-1) (3)

         + $\displaystyle \lambda_{3}^{}$(ui-1, j-1 + ui+1, j+1) + $\displaystyle \lambda_{4}^{}$(ui-1, j+1 + ui+1, j-1)) + o(1)

[Consistency] implies

$\displaystyle \lambda_{1}^{}$($\displaystyle \theta$) = 2$\displaystyle \lambda_{0}^{}$($\displaystyle \theta$) - sin2$\displaystyle \theta$
$\displaystyle \lambda_{2}^{}$($\displaystyle \theta$) = 2$\displaystyle \lambda_{0}^{}$($\displaystyle \theta$) - cos2$\displaystyle \theta$
$\displaystyle \lambda_{3}^{}$($\displaystyle \theta$) = - $\displaystyle \lambda_{0}^{}$($\displaystyle \theta$) + 0.5(sin$\displaystyle \theta$cos$\displaystyle \theta$ + 1)
$\displaystyle \lambda_{4}^{}$($\displaystyle \theta$) = - $\displaystyle \lambda_{0}^{}$($\displaystyle \theta$) + 0.5(- sin$\displaystyle \theta$cos$\displaystyle \theta$ + 1)

We choose for several reasons (see [CEGLM]):

$\displaystyle \lambda_{0}^{}$($\displaystyle \theta$) = 0.5 - cos2($\displaystyle \theta$) + cos4($\displaystyle \theta$)

We deduce the others $ \lambda$'s:

$\displaystyle \left\{\vphantom{
\begin{array}{l}
-4 \lambda_0 = -2 + 4 \cos^2(\...
...2(\theta)\sin^2(\theta) - 0.5 \sin(\theta)\cos(\theta) \\
\end{array}}\right.$$\displaystyle \begin{array}{l}
-4 \lambda_0 = -2 + 4 \cos^2(\theta)\sin^2(\thet...
... = \cos^2(\theta)\sin^2(\theta) - 0.5 \sin(\theta)\cos(\theta) \\
\end{array}$

Then our estimation of u$\scriptstyle \xi$$\scriptstyle \xi$, is exact for all the linear combinations of the polynom ials of degree 0,1,2 and 3, plus the polynomial : (x2 + y2)(x sin$ \theta$ - y cos$ \theta$)2. Of course, the calculus can be false for the other polynomials.

algorithm.

Our algorithm is following:

(2):        un+1(x) = un(x) + $\displaystyle \Delta$tun$\scriptstyle \xi$$\scriptstyle \xi$(x)
(1):        un+1(x) = un(x) + $\displaystyle \Delta$t(Du)2/3(un$\scriptstyle \xi$$\scriptstyle \xi$(x))1/3

In the case of (2) i.e. mean curvature motion, we must choose $ \Delta$t $ \leq$ 0.5($ \Delta$x)2 in order to have some stability. Whereas for (1) i.e. AMSS model , the maximum value of $ \Delta$t cannot be imposed theoretically.

This scheme verifies [Consistency] , because it is exact at order 2. All the geometrical properties ([Isom. invariance] , [Scale invariance] , ...) are true for all the polynomials mentionned above. For other functions, we have these properties only for the affine transforms which leave the grid invariant.

But, the scheme is not morphological. And, it does not satisfy [Order Preserving] . However, it is experimentally quite stable. In fact, we do not expect to have [Order Preserving] and [Consistency] in such a quasilinear scheme with a fixed stencil. If you impose both, as noticed in [ALM] and proved by [CrLi], you do not limit the size of the stencil.




$ \bigcirc$See Also


osamss.


$ \bigcirc$Version 1.5


Last Modification date : Thu Nov 29 20:23:56 2001


$ \bigcirc$Author


Jacques Froment, Frederic Guichard, Lionel Moisan






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