Next: flst_pixels Up: Reference Previous: flstb_tv   Contents   Index

flst

Name

flst Fast Level Sets Transform of an image

Command Synopsis

flst [-a min_area] image tree

-a min_area : argument of the grain filter

image : Input fimage

tree : The tree of shapes

Function Summary

void flst (pMinArea , pImageInput , pTree )

int *pMinArea ;

Fimage pImageInput ;

Shapes pTree ;

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 ( = [u ]) or of inferior level set ( = [u ]). More precisely, it is such a component in which we have filled the holes, where the definition of a hole is as follows:

• for a component not meeting the frame of the image, a hole is any connected component of the complementary that does not meet the frame of the image.
• for a component containing all the frame of the image, a hole is any connected component of the complementary.
• for a component meeting the frame of the image without containing it, it is a connected component of the complementary not meeting the frame or a connected component of the complementary meeting the frame but having an area less than half the image.
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 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 min u] = [u 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:
• parent points to the parent shape. It is a valid pointer, except for the root of the tree, for which it is NULL.
• next_sibling points to another child of its father.
• child is one child of the shape. The other ones can be found by following the links next_sibling of the child until it is the NULL pointer.
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:
• inferior_type is a boolean value indicating if the shape is extracted from an inferior or superior (connected component of) level set. This has no meaning for the root of the tree.
• value is the value of the threshold for the level set whose connected component generated the shape. If it is sufficiently contrasted compared to the background, there are several such thresholds, only the extremal one is kept (shapes are not duplicated in the tree).
• open is a boolean value indicating if the boundary (the level line) is open or closed. That is if the shape meets the frame of the image or not.
• area is the number of pixels in the shape, that is the number of pixels in the connected component of level set plus the areas of the holes.
• removed is a boolean value indicating if the shape should be considered in the tree or removed (see below).
• pixels is an array of points in the plane, the list of pixels in the shapes. The size of the array is the field area.
• boundary is the boundary of the shape (the level line), each point being at the junction of 4 pixels. The point of coordinates (i, j) is considered to be at the upper-left corner of the pixel (i, j).
• data is left free for the user to store what needed.
• data_size is the size (in bytes) of the data. Put it to 0 in case data is not meant to be saved.
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:
• nrow and ncol are the dimensions of the image.
• the_shapes is an array containing all the shapes, in no particular order, except that the one at index zero is always the root.
• nb_shapes is the size of this array.
• smallest_shape is an array of size nrow×ncol where element y×ncol+ x is the smallest shape containing pixel (i, j). This does not take into account that this shape could be removed, so the function mw_get_smallest_shape should be used instead.
• data is left free for the user.
• data_size is the size (in bytes) of data
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:
• pImageInput: the image to decompose
• pTree: the tree of shapes, filled as output.
• pMinArea: arguments to a possible grain filter.
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.

Version 2.0

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

Author

Pascal Monasse

Next: flst_pixels Up: Reference Previous: flstb_tv   Contents   Index
mw 2004-05-05