Max-tree

MainPage

The max-tree can be seen as a compact structure for the component tree representation. Every operation that can be done in the component tree can be done in the max-tree and vice-versa.

Max-tree Representation

The max-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 :

is defined by:

it represents a set of flat zones. For each non-empty , there is a max-tree node with and . The pixels represented by and their level are the minimum set of attributes that a node has to store in order to be able to recover the image from the max-tree. Note that storing is much more memory efficient than storing , there is no redundancy in the pixels stored. The connected component can be recovered by:

where is the set containing all the descendants of . Node is a parent of node if is the smallest connected component that contains .

The number of connected components that a max-tree node represents is given by:

If , this node is a composite node, i.e. a node that represents a connected component that remained unchanged for a sequence of threshold values. This notion of composite node is useful to implement the max-tree based algorithms.

The restitution of the image corresponding to a given max-tree, is an inverse mapping of the pixels stored in the nodes to the image coordinates system, and is expressed by the following equation:

The construction of the max-tree corresponding to the 1D image is illustrated in Figure 1. The pixels stored in each node is obtained by the set difference between the pixels obtained at level minus the pixels at level , and the empty nodes are removed from the final representation. The corresponding leaves of the max-tree and the component tree store the same set of pixels. This illustration is meant just to explain the max-tree structure and construction, it does not correspond to the most efficient form to build it, for that, there are algorithms that run in quasi-linear time. The composite nodes are represented by double circles. The filled pixels in each connected component represent the pixels each max-tree node stores ( ), and its union with the dashed pixels in the same connected component ( ).

I

h = 0

h = 1

h = 2

h = 3

h = 4

h = 5

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

Max-tree Filtering

Filtering the max-tree consists on contracting its nodes. The most usual rule used to perform this contraction is the direct rule. There are two possible cases: a full node contraction and a composite node partial contraction. The full contraction of a sequence of nodes that constitute a sub-tree rooted in a given node is called pruning. These operations are explained in the next subsections.

Node Contraction by Direct Rule

In the full node contraction by direct rule, the node selected contracts with its parent, and its pixels are also merged with it. The children of the node being contracted become children of its parent. The full contraction by direct rule procedure of a node with its parent is given by:

where is the set containing all the children of node . The full node contraction decreases the number of max-tree nodes by .

In the partial node contraction by direct rule, the composite node is contracted by decreasing its attribute. The composite node partial contraction by direct rule of a node by is given by:

The parameter defines how many levels the composite node will contract. The partial node contraction does not alter the number of max-tree nodes.

Note that by contracting a node in the max-tree, the attribute of its children is being increased. In the full contraction, it is increased by , and in the partial contraction it is increased by .

It is important to mention that contracting a node of the max-tree is a connected filter, and after choosing which nodes will be fully contracted, partially contracted and the parameter , the order of the contractions is irrelevant, the result will always be the same.

The max-tree node being contracted may be a leaf, a ramification, or a node with one child, and depending on the node it has a different effect on the equivalent component tree. These three cases are analyzed.

The max-tree of the image , and its corresponding component tree are illustrated in Figure 2. The result of a full contraction and a partial contraction with of the ramification node in Figure 2(a), which is a composite node with , and its meaning on the component tree is illustrated in Figure 2. The full contraction operation reduced the number of max-tree nodes by , and increased the number of nodes in the component tree from to . The full contraction of the ramification node in the max-tree is equivalent to replacing the Component Tree connected components at levels and , by the two connected components of their descendants at level . The partial contraction did not change the number of max-tree nodes as expected. The effect on the component tree was replacing the connected component at level by the two connected components of their descendants at level , therefore the number of component tree nodes increased from to . The conclusion is that contracting max-tree ramification nodes increases the number of nodes of its equivalent component tree.

(a) Max-tree

(a) Component tree

Figure 2. Max-tree (a) and component tree (b) corresponding to the image .

Figure 3. Max-tree (a) and component tree (b) after full contraction, and max-tree (c) and component tree (d) after partial contraction by direct rule with of the ramification node in Figure 2(a).

The result of a full contraction and a partial contraction with of the leaf on the top left of the max-tree in Figure 2(a), which is a composite node with , and its meaning on the component tree is illustrated in Figure 4. The full contraction operation reduced the number of max-tree nodes by , and decreased the number of nodes in the component tree by . The partial contraction did not change the number of max-tree nodes, and reduced the number of component tree nodes by . The conclusion is that contracting max-tree leaves reduces the number of nodes of its equivalent component tree.

Figure 4. Max-tree (a) and component tree (b) after full contraction, and max-tree (c) and component tree (d) after partial contraction by direct rule with of the leaf on the top left of the max-tree in Figure 2(a).

The result of a full contraction and a partial contraction with of the node with one child on the top right of the max-tree in Figure 4(a), which is a composite node with , and its meaning on the component tree is illustrated in Figure 5. The full contraction operation reduced the number of max-tree nodes by , and did not alter the number of nodes in the component tree. The partial contraction did not change neither the number of max-tree nodes, neither the number of component tree nodes. The conclusion is that contracting max-tree nodes with one child does not alter the number of nodes of its equivalent component tree.

Figure 5. Max-tree (a) and component tree (b) after full contraction, and max-tree (c) and component tree (d) after partial contraction by direct rule with of the node with one child on the top right of the max-tree in Figure 2(a).

Pruning

The pruning consists on performing full contractions of the nodes of a sub-tree. It is useful to implement attribute filters with increasing criteria, such as the area opening. For instance, the max-tree, and its corresponding component tree of the image are illustrated in Figure 6. If we decide to apply an area opening filter that removes all the components with area less than or equal to , it is necessary to prune the sub-tree rooted in the ramification node of the max-tree. The result of the pruning is also illustrated in Figure 6. Note that the number of max-tree nodes reduced from to , and the number of component tree nodes reduced from to , therefore the pruning reduces the number of nodes in both the component tree and the max-tree. The max-tree filtering operations and their effect on the component tree are summarized in Table 1.

Figure 6. Max-tree (a) and component tree (b) corresponding to the image . Max-tree (c) and its corresponding component tree (d) after the pruning of the sub-tree rooted in the ramification node.

Max-tree Operation Effect on the component tree
Contraction of a leaf reduces the number of nodes
Contraction of a ramification increases the number of nodes
Contraction of a node with one child does not alter the number of nodes
Pruning reduces the number of nodes

Table 1. Summary of max-tree filtering operations and their effects on the component tree.