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.² 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

Consider the intuitive demonstration of the concept of components in figure 1: each layer (indicated as $\lambda$) 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 $\lambda =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.¹ The following is an implementation of this algorithm in GNU Octave code, defining three functions that can be used to construct a canonized max-tree:

function [r, zpar] = root(x, zpar)
    if zpar(x) == x
        r = x;
    else
        zpar(x) = root(zpar(x), zpar);
        r = zpar(x);
    end
end

function [R, parent] = tree(f)
    parent = zpar = nan(size(f));

    [_, s] = sort(f(:), "descend");
    [_, R] = intersect(s, [1:numel(f)]);

    for p = s'
        parent(p) = p;
        zpar(p) = p;

        for n = N(p, f)
            if isnan(zpar(n))
                continue;
            end

            [r, zpar] = root(n, zpar);

            if r != p
                parent(r) = p;
                zpar(r) = p;
            end
        end
    end

    R = reshape(R, size(f));
end

function parent = canonize(parent, f)
    [_, s] = sort(f(:), "descend");
    [_, R] = intersect(s, [1:numel(f)]);

    for p = fliplr(s')
        q = parent(p);

        if f(parent(q)) == f(q)
            parent(p) = parent(q);
        end
    end

    parent = reshape(parent, size(f));
end

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.

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.

Further Reading

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”.³ 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.