Published on
• Machine Learning
• Max-Trees
• Visual Computing
• Data Science

## Introduction to Max-Trees

In the domain of data-science, it is useful to describe images by other means than simple sequences of pixels in order to analyze its contents. An interesting technique is the max-tree, proposed by Salembier, Oliveras and Garrido.2 In a max-tree, each pixel in an image is assigned to a layer. Pixels that are adjacent within the same layer form a component and are stored in a tree-like structure that allow for computation and analysis.

### Components in the First Dimension Figure 1: An example of the manner in which a one-dimensional image can be considered as a structure of components. The image itself is the row of pixels at the bottom, the components are the “pile” of pixels at the top, separated into layers.

Consider the intuitive demonstration of the concept of components in figure 1: each layer (indicated as λ) contains all pixels that fall within the same range of values. In this case, each layer is a direct mapping of the pixel values. Note that for λ = 3, the pixels with a higher value (closer to white) are considered to be part of the component.

The fact that each component is part of a greater component (up until the point where the component encompasses the whole image) allows it to be stored in a tree-like structure, i.e. a max-tree. The underlying assumption of the max-tree is that “objects of interests” within an image will be clustered both in position within the image as in color. The components themselves can be evaluated by computing certain properties, e.g. the area, perimeter, circularity ratio, etc.

### Constructing a Max-Tree

To be able to make computation based on the components within an image, a max-tree needs to be constructed. This can be done using an algorithm proposed by Berger et al.1 The max-tree is constructed by sorting the image pixels in descending order and defining the parent node of each pixel as one of its neighboring pixels. In figure 2 this method of ordering the pixel in an image is demonstrated, as well as the construction of an auxiliary max-tree. For every component in this tree structure, the “root” is defined as the node of the highest ordering value within a single layer among connected pixels. Figure 2: An example of a two-dimension image and the ordering of its pixels as indicated by the assigned alphabetical labels. An auxiliary max-tree structure is constructed by assigning a neighboring pixel as the parent of each node representing a pixel, based on the ordering. The root of each component has been indicated using a bold label. This example can be found in eg.mat.

As a final step, the construction of a canonical max-tree is achieved by redefining the parent of each node within a component to be the root of that node. This node can now be referred to as the “canonical root”. Any direct subsequent components will also have the canonical root as their parent. The convenience of this step is that each component is represented by a single node and thus a single pixel. Figure 3 shows how the auxiliary max-tree from figure 2 is converted into a canonical max-tree. Figure 3: The conversion of the auxiliary max-tree (left) from figure 2 into a canonical max-tree (right). Note that the parent of each node is always a root node.

This article is a rewriting of my literature study on max-trees as part of my 2021 master’s thesis “Detecting Astronomical Objects with Machine Learning”.3 Attached to this article are GNU Octave implementations of Berger’s max-tree algorithm and example data as it appears in figure 2. A visualisation function for max-trees is also included, allowing the structure of the max-tree to be inspected.

1. Christophe Berger et al. “Effective Component Tree Computation with Application to Pattern Recognition in Astronomical Imaging”. In: Proc. International Conference on Image Processing. Vol. 4. San Antonio, Texas, US: IEEE, Sept. 2007, pp. 41-44. ISBN: 978-1-4244-1436-9. DOI: 10.1109/ICIP.2007.4379949

2. Philippe Salembier, Albert Oliveras, and Luis Garrido. “Antiextensive Connected Operators for Image and Sequence Processing”. In: Trans. on Image Processing 7.4 (Apr. 1998), pp. 555-570. DOI: 10.1109/83.663500

3. Michaël van de Weerd. “Detecting Astronomical Objects with Machine Learning”. Feb. 2021. URL: https://fse.studenttheses.ub.rug.nl/23854/

This website collects statistical data in order to improve your user experience.

Privacy Statement

A reference to the heading "" has been copied to your clipboard.