next up previous contents index
Next: one_levelset Up: Reference Previous: mschannel   Contents   Index


$ \bigcirc$Name

msegct Region-Growing method using the energy model of Mumford and Shah with piecewise constant approximation function, any number of channels

$ \bigcirc$Command Synopsis

msegct [-w w_of_channels] [-S size_of_grid] [-N nb_of_regions] [-L lambda] [-c curves] [-r reconstruction] . . fmovie boundary

-w w_of_channels : weights of channels, MW2-fsignal formated, (default weights 1/number_of_channels)

-S size_of_grid : size of initilization grid (int), default 1

-N nb_of_regions : number of desired regions (int)

-L lambda : value of final scale parameter (float) of last 2-normal segmentation

-c curves : output boundary set in curves format

-r reconstruction : output piecewise constant reconstruction of each channel

. (screen output) : final number of regions

. (screen output) : final lambda value

fmovie : original multichannel data in fmovie format

boundary : b/w image of boundary set

$ \bigcirc$Function Summary

Cimage msegct (weight , sgrid , nb_of_regions , lambda , curves , u , f_nb_of_regions , f_lambda , orig_data )

Fsignal weight ;

int *sgrid , *nb_of_regions , *f_nb_of_regions ;

float *lambda , *f_lambda ;

Curves curves ;

Fmovie orig_data , u ;

$ \bigcirc$Description

The command msegct computes a segmentation of multichannel data. Each channel is an fimage which is part of the input fmovie. Thus we consider a picture where to each pixel are associated nb_ch(float-type) numbers. The number of channels, nb_ch, is equal to the number of images of is which made fmovie (see how an fmovie is loaded in MW2).

The algorithm computes 2-normal segmentation of this picture as will be described below.
The initial picture is broken in a grid of elementary cells, composed of D×D-pixel squares (D=size_of_grid). We use a classical region-growing algorithm to achieve the partition of the image in homogeneous regions.

The criterion which measures the resemblance of regions is given by the Mumford and Shah model. Call g the picture defined on an open rectangle R $ \subset$ IR, u a piecewise constant function, which approximates g, and let B be the boundaries between the regions, i.e. the set of jump points of u (remember that g and u are elements of ${\rm I\!\!R}^{\mbox{\small {\tt nb\_ch}}}$). With Mumford and Shah we introduce the following functional which has to be minimized

E(B) = $\displaystyle \int_{{R}}^{}$| u - g|2 + $\displaystyle \lambda$$\displaystyle \ell$(B),

where |.| is the (weighted) norm we put on g-space:

| u - g|2 = $\displaystyle \sum_{{i=1}}^{{\mbox{\small {\tt nb\_ch}}}}$wi . (ui - gi)2,

with $w=(w_1,\ldots,w_{\mbox{{\tt nb\_ch}}})$ the weights the user puts on the channels. Moreover $ \ell$ is the 1-dimensional Hausdorff measure and $ \lambda$ a real scaling coefficient. The parameter $ \lambda$ gives a weight to the length of the boundaries: a small value allows a lot of boundaries whereas a big value tends to reduce the boundary length $ \ell$(B).
The property of being 2-normal for a segmentation of R in regions $\displaystyle \bigcup_{{i}}^{}$Oi has been used by Pavlidis in the seventies. We say that B is 2-normal if, given any two regions Oi, Oj having common boundary $ \partial$(Oi, Oj), the following inequality for the energy holds

E(B) $\displaystyle \leq$ E(B $\displaystyle \setminus$ $\displaystyle \partial$(Oi, Oj)).

Which yields

$\displaystyle \lambda$$\displaystyle \ell$($\displaystyle \partial$(Oi, Oj)) $\displaystyle \leq$ $\displaystyle {\frac{{\vert O_{i}\vert\cdot \vert O_{j}\vert}}{{\vert O_{i}\vert+\vert O_{j}\vert}}}$| ui - uj|2,

where |.| denotes the surface measure and ui, uj are the mean values of g on Oi, Oj, for example $u^{i}={\displaystyle \frac{1}{\vert O_{i}\vert}}{\displaystyle \int_{O_{i}}}g\;...
...u^i_{\mbox{\small {\tt nb\_ch}}}) \in {\rm I\!\!R}^{\mbox{\small {\tt nb\_ch}}}$.

The algorithm proceeds as follows. The initial picture is partitioned in squares of side size_of_grid pixels. Construct a list of the corresponding symbolic regions containing all the information needed: surface, sum of gray-levels in the square (for each channel), length of boundaries. Construct a table in which to each boundary is associated the value of $ \lambda$ for which this boundary will disappear (i.e. E decreases by merging the two adjacent regions). Using and updating this ``merit'' table the algorithm proceeds. The information on the new region, constructed when a merging decision occurred, is taken from the two old one's, so there is no need to return on pixel level.

There are two (incompatible) options : either one wants the segmentation to stop at nb_of_regions regions or the final segmentation is at scale lambda.

If the first option is chosen the program stops when the desired number of regions (nb_of_regions) is reached. To be more precise it stops at the value of $ \lambda$ for which this particular number of regions is reached, there might be less regions remaining if nb_of_regions doesn't correspond to a 2-normal segmentation for any $ \lambda$.

In case the final $ \lambda$ is fixed the program stops at lambda or for the value of $ \lambda$ just lower than lambda. For example if lambda=13.45 and the current $ \lambda_{c}^{}$=13.09, then if the next boundary in the segmentation will vanish for $ \lambda_{n}^{}$=14.67 the program stops. The obtained segmentation is also valid for each $ \lambda$ strictly lower than the next value $ \lambda_{n}^{}$.

If the program is used as module in another program the final values of $ \lambda$ and the number of regions are passed to the corresponding variables. On command line execution this information is anyway displayed.

The program estimates the memory used by the process, this mainly depends on the precision of the initial grid, for example D = 1 is the best possible precision, but it needs a lot of memory for the data structure (1 pixel = 1 region). So the program turns out to be most efficient (i.e. fast) on machines with a big amount of central memory (RAM). Indeed as there is no previous information on the picture available and as regions can grow in any direction, the whole structure should be available in central memory.

The output shows the initial quadratic error, the total boundary length and the number of regions the algorithm starts with, after reaching nb_of_regions the quadratic error, boundary length, number of region and the current value of $ \lambda$.

The output is file boundary which represents the boundary set on a white background and is stored under cimage-format.

An optional output is file curves which contains the boundary set under curve-format (use -c). Using curves_cimage the result can be visulized on the original fimage for example.

To obtain the gray-level reconstruction of the piecewise constant approximation for each channel use -r. This will write an Fmovie in file reconstruction.

$ \bigcirc$See Also


$ \bigcirc$Version 1.31

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

$ \bigcirc$Author

Georges Koepfler

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