Component Tree

MainPage

The component tree was proposed as a structure for image representation that represents all connected components resulting of all possible thresholds of the image, and that provides an attribute signature as means of discriminating features in the image. It is efficient to implement connected anti-extensive filters, and by duality extensive filters.

Component Tree Representation

The component tree, , is a rooted tree in which each node stores a set of attributes. It is completely defined by its set of nodes :

and parents :

where is the set minus operand, and is the parent of node . Our convention is that node is the root.

Suppose that the grey-levels of an image are bounded between and . The upper threshold sets resulting of every upper threshold for varying between and can be computed, and we know that threshold sets have the following property:

This hierarchy property allows a tree representation. For each connected component resulting of all threshold sets, there is a component tree node with attributes and . and are the basic attributes stored in the component tree nodes necessary to recover the image from the tree. Other attributes, such as height, area and volume can be computed and stored in the nodes during the tree construction or they can be computed just when required.

Node is a parent of node if contains , and . Note that the component tree may represent a pixel in more than one node, therefore it has some redundancy. The leaves of the component tree correspond to regional maxima in the image and the root represents the whole domain of the image.

The restitution of the image corresponding to a given component tree, is given by the following equation

The construction of the component tree corresponding to the 1D image is illustrated in Figure 1. This illustration is meant just to explain the component tree structure and construction, it does not correspond to the most efficient way to build it, for that, there are algorithms that run in quasi-linear time.

I

h = 0

h = 1

h = 2

h = 3

h = 4

h = 5

Figure 1. component tree construction of the 1D image (a). Bottom-up construction (b)-(g). Resulting component tree (g)

Component Tree Attribute Signature

The notion of attribute signature in the component tree is very important, it conveys information concerning the variation in shape or size of a connected component. The attribute signature uses the linking information between connected components at sequential grey-levels in the image to help the decision making process. The attribute signature of any two nodes and connected by a path in the component tree is simply the sequence of node attributes in this path.

For instance, the attribute signature may be used to choose a threshold value to segment an object in an image. The Mona Lisa painting is depicted in Figure 2(a). The red dot in the image corresponds to a regional maxima, i.e. a component tree leaf. The area signature, and its gradient starting at this leaf and ending at the root of the tree are shown in Figure 2(b) and Figure 2(c), respectively. The area signature presents some discontinuities, i.e. spikes in the gradient curve. The highest spike happens in the transition between to . At , the area of the connected component is of , in the following grey-level, , the area drops to . The reconstruction of the connected components at levels and are depicted in Figure 2(d) and 2(e), respectively. It is clear that the connected component at level merges Mona Lisa's face with a considerable part of the background, while the connected component at level provides a better segmentation of Mona Lisa's face.

(a) Mona Lisa Painting

(b) Area signature

(c) Gradient of the area signature

(d) Reconstruction at h = 75

(e) Reconstruction at h = 76

Figure 2. Mona Lisa painting, the red dot corresponds to a regional maxima (a). Area signature (b), and its gradient (c). Reconstruction of the connected component at level (d) and (e).