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

$${\frac{{\partial u}}{{\partial t}}} {\frac{{1}}{{3}}}$$ (1)

u(0,.) = u₀(.)

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".

$${\frac{{\partial u}}{{\partial t}}}$$ (2)

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

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 t_end = LS²/2.

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

If this option is not used LS= 2.0.

- f

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

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.

$${\frac{{\partial u}}{{\partial t}}}$$ = $${\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 = $${\frac{{LS^2 - FS^2}}{{2*Step}}}$$

If AMSS

Numberofiterations = $${\frac{{3}}{{4}}}$$$${\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

• [Order Preserving] , because they both are parabolic equations.
• [Morphology] , the analysis commute with a monotonous rescaling of the grey level scale.
• [Scale invariance] , the analysis commute with zoom.
• [Isom. invariance] , the analysis commute with isometry.
• [Affine invariance] , for only the equation (1) AMSS model.

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_$\xi$$\xi$ the second derivative of u in the direction $\xi$, we have :

(2) $$\Leftrightarrow$$ $${\frac{{\partial u}}{{\partial t}}}$$ = u_$\xi$$\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)^{${\frac{{2}}{{3}}}$}(u_$\xi$$\xi$)^{${\frac{{1}}{{3}}}$}, where ($\nabla$u)^{${\frac{{2}}{{3}}}$} is understood as the speed of the diffusion.

The schemes which we wish to discuss compute u_$\xi$$\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 :

$$\xi \xi {\frac{{1}}{{\Delta x^2}}} \lambda_{0}^{} \lambda_{1}^{} \lambda_{2}^{}$$ (3)

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

[Consistency] implies

$$\lambda_{1}^{}$$($$\theta$$) = 2$$\lambda_{0}^{}$$($$\theta$$) - sin²$$\theta$$

$$\lambda_{2}^{}$$($$\theta$$) = 2$$\lambda_{0}^{}$$($$\theta$$) - cos²$$\theta$$

$$\lambda_{3}^{}$$($$\theta$$) = - $$\lambda_{0}^{}$$($$\theta$$) + 0.5(sin$$\theta$$cos$$\theta$$ + 1)

$$\lambda_{4}^{}$$($$\theta$$) = - $$\lambda_{0}^{}$$($$\theta$$) + 0.5(- sin$$\theta$$cos$$\theta$$ + 1)

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

$$\lambda_{0}^{}$$($$\theta$$) = 0.5 - cos²($$\theta$$) + cos⁴($$\theta$$)

We deduce the others $\lambda$'s:

$$\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.$$$$\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_$\xi$$\xi$, is exact for all the linear combinations of the polynom ials of degree 0,1,2 and 3, plus the polynomial : (x² + y²)(x sin$\theta$ - y cos$\theta$)². Of course, the calculus can be false for the other polynomials.

algorithm.

Our algorithm is following:

• We estimate the gradient direction $\theta$, and $\xi$ the orthogonal direction using the 9 points of the stencil 3x3.

• Computation of curv(u) as above.

• We proceed, in case of equation

(2):        uⁿ⁺¹(x) = uⁿ(x) + $$\Delta$$tuⁿ_$\xi$$\xi$(x)

(1):        uⁿ⁺¹(x) = uⁿ(x) + $$\Delta$$t(Du)^2/3(uⁿ_$\xi$$\xi$(x))^1/3

In the case of (2) i.e. mean curvature motion, we must choose $\Delta$t $\leq$ 0.5($\Delta$x)² 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