flst Fast Level Sets Transform of an image
flst [-a min_area] image tree
-a min_area : argument of the grain filter
image : Input fimage
tree : The tree of shapes
void flst (pMinArea , pImageInput , pTree )
int *pMinArea ;
Fimage pImageInput ;
Shapes pTree ;
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
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:
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
- 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 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:
- 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.
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:
- 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
- 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.
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
The arguments of the function 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
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.
- pImageInput: the image to decompose
- pTree: the tree of shapes, filled as output.
- pMinArea: arguments to a possible grain filter.
fgrain, ll_boundaries, ll_edges, ll_extract, ll_sharp.
Last Modification date : Thu Nov 29 20:23:56 2001