next up previous contents index
Next: flst_pixels Up: Reference Previous: flstb_tv   Contents   Index


$ \bigcirc$Name

flst Fast Level Sets Transform of an image

$ \bigcirc$Command Synopsis

flst [-a min_area] image tree

-a min_area : argument of the grain filter

image : Input fimage

tree : The tree of shapes

$ \bigcirc$Function Summary

void flst (pMinArea , pImageInput , pTree )

int *pMinArea ;

Fimage pImageInput ;

Shapes pTree ;

$ \bigcirc$Description

The Fast Level Sets Transform is a decomposition of an image (an Fimage or a Cimage) into ``shapes'', based on connected components of level sets and on level lines (see [MG00][MG99][BCM01]). As the name indicates, it is a fast algorithm, of complexity O(N log N) where N is the number of pixels, but the complexity depends also on the content of the image: a highly textured image would take more time to decompose than an image with many flat zones. A shape is based on a connected component of superior level set ( $ \cal {X}$$\scriptstyle \geq$ $\scriptstyle \lambda$ = [u $ \geq$ $ \lambda$]) or of inferior level set ( $ \cal {X}$$\scriptstyle \leq$ $\scriptstyle \lambda$ = [u $ \leq$ $ \lambda$]). More precisely, it is such a component in which we have filled the holes, where the definition of a hole is as follows:

In all cases, it is easily seen that a shape contains all the connected components of the complementary, except possibly one, called its exterior. The reason for considering such things is that in the physical world, most objects are full, without holes, so that if an object appears in the image with a hole, it means that it is partially occluded by another object. The definition of a hole for a connected component of the complementary not meeting the frame of the image is natural, but much more ambiguous otherwise. Actually, such holes are defined so as to make the shape as small as possible leaving a connected exterior. All these considerations are justified mainly by technical reasons: it allows to have a convenient structure for the family of shapes. In the same manner that superior level sets are decreasing and inferior level sets are increasing when $ \lambda$ increases, it is not hard to see that connected components of upper level sets have a structure of tree, so as connected components of lower level sets: indeed, a node is associated to a connected component of level set and a link (an ``edge'' in graph theory) is put between two nodes if and only if one is included into the other and no third shape is nested between both. The entire image is a connected component of level set ( [u $ \geq$ min u] = [u $ \leq$ max u] and it is the only one that is simultaneously an upper and a lower level set). In that sense, it seems that we have two trees to represent the image. Both are interesting, because one contains light objects on a dark background and the other dark objects on a light background. But it seems better to have both kinds of objects in the same structure. That is the role of the shapes; of course, that means that some connected components of level sets must have been ignored in the resulting structure: they are the ones whose associated shapes are the image itself, that is the ones containing all the frame of the image or containing only a part of the frame but where each component of the complementary has an area smaller than half the image. Shapes also have a tree structure, and two shapes are whether disjoint or nested. The tree is encoded in the following manner in the structure Shape: In this way, we can follow each direction in the tree (going toward the root or toward the leaves) with few pointers. A leaf in the tree has a child field of value NULL. The other fields of the Shape structure have the meaning: The number of shapes in the tree is not more than the number of pixels (plus 1). But the number of holes cannot be bounded so easily. Removing a shape from the tree means connecting its children directly to its father. In fact no connection is changed, but the functions mw_get_parent_shape, mw_get_first_child_shape and mw_get_next_sibling_shape take this field into account, so they should be used instead of the fields directly. Of course, when the tree is the output of flst, no shape is removed initially. The fields of the tree structure, Shapes, are: Of course, the flst is called a ``transform'', that means that we can reconstruct the image when we know the tree of shapes. This is the role of the module flst_reconstruct. The arguments of the function are: Before decomposing the image, it is possible to apply an extrema killer to the image. This reduces the number of shapes, and so the memory requirement of the output structure is also reduced, so as computation time. An extrema killer is applied only in the case where pMinArea is a non NULL pointer and the pointed value is strictly greater than 1. In this case, only shapes of area at least *pMinArea are put in the tree. Some very simple manipulations of the tree structure are made in the modules fgrain and ll_sharp. The field boundary of each shape is left to NULL. To compute it, use the module flst_boundary. The field pixels of the shapes is left to NULL. To compute it, use the module flst_pixels. A similar algorithm, interpreting the image as a bilinear interpolation of data points, is the module flst_bilinear.

$ \bigcirc$See Also

fgrain, ll_boundaries, ll_edges, ll_extract, ll_sharp.

$ \bigcirc$Version 2.0

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

$ \bigcirc$Author

Pascal Monasse

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