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


$ \bigcirc$Name

segct Region-Growing method using the energy model of Mumford and Shah with piecewise constant approximation function

$ \bigcirc$Command Synopsis

segct [-S size_of_grid] [-N nb_of_regions] [-L lambda] [-c curves] [-r reconstruction] . . fimage boundary

-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

. (screen output) : final number of regions

. (screen output) : final lambda value

fimage : original image

boundary : b/w image of boundary set

$ \bigcirc$Function Summary

Cimage segct (sgrid , nb_of_regions , lambda , curves , u , f_nb_of_regions , f_lambda , image_org )

int *sgrid , *nb_of_regions , *f_nb_of_regions ;

float *lambda , *f_lambda ;

Fimage image_org , u ;

Curves curves ;

$ \bigcirc$Description

The command segct generates, starting from fimage, a 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 [MS95]. Call g the picture defined on an open rectangle R, u a piecewise constant function, which aim is to approximate g, and let B be the boundaries between the regions, i.e. the set of jump points of u. 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 $ \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 ui = $\displaystyle {\frac{{1}}{{\vert O_{i}\vert}}}$$\displaystyle \int_{{O_{i}}}^{}$g.

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, 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. 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 visualized on the original fimage for example.

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

$ \bigcirc$Version 1.21

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

$ \bigcirc$Author

Georges Koepfler

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