Attributes for
Connected Components

Connected components are fundamental to the fields of image processing and computer vision, providing the basis for segmenting and analyzing images. In my Introduction to Max-Trees I delve into the methods of extracting these components from images in order to construct a Max-Tree — a data structure centered around the concept of connected components. However, the true utility of connected components emerges when we compute attributes that provide meaningful information about the image.

This article compiles a set of attributes that can be computed relatively easily, offering insights into the properties and characteristics of connected components. Additionally, a comprehensive collection of GNU Octave implementations for these attributes is provided, facilitating practical application. Some of these implementations are included in the body of this article as well.

While many of these attributes are particularly relevant for connected components within a max-tree structure, they are also applicable in other contexts. The content of this article is derived from my master’s thesis, “Detecting Astronomical Objects with Machine Learning” and aims to make its insights more accessible to a broader audience.

Area

An attribute that can easily be computed is the area. Berger et al. define this attribute as the number of elements within the component.¹ Tushabe provides the formal mathematical definition of area $A(X)$ of component $X$ as²

Here, ${\mathbf{1}}_X(x)$ is the so-called identicator function, which is $1$ if $x\in X$ or $0$ otherwise. While the term “area” originated from two-dimensional components, it can also apply to higher dimensions, such as indicating the volume of a cube in three dimensions. Berger et al. provide an algorithm for computing the area of a component in the context of a max-tree, which is included below in GNU Octave code.¹

function a = area(f, R, parent)
    a = ones(size(R));

    [_, v] = sort(R(:));

    for x = v'
        if parent(x) == x
            continue
        end

        a(parent(x)) = a(parent(x)) + a(x);
    end
end

Perimeter

The perimeter is closely related to the area attribute. Gonzalez and Woods describe the perimeter as the length of the boundary of a component.³ Interpreting the boundary as the number of elements not exclusively connected to elements within the same component, a novel approach to computing the perimeter is presented in my master’s thesis⁶. The complexity of computing the perimeter arises from the fact that an element on the boundary of its own component can also contribute to the boundary of its parent, its parent’s parent, etc. To address this, a boundary vector $ℬ(X)$ is constructed, indicating the contribution of a component $X$ to each layer in the tree. These contributions apply only to the direct and indirect parents of the component. First, we compute the intermediate contribution set $\Lambda (x)$ for each element $x$, composed of the layers where $x$ is part of the perimeter:

Here, $𝒩(x)$ are the neighbors of $x$ and $\lambda (x)$ its level. With $\Lambda (x)$ computed for every element $x$, the contribution of $X$ to the perimeter of layer $\lambda$ is the number of $\lambda$ inclusions in the contribution set of elements in $X$:

The perimeter $𝔅(X_{\lambda }^{\mu })$ of component $X_{\lambda }^{\mu }$ in branch $\mu$ and layer $\lambda$ is determined by summing the contributions of all components to $\lambda$:

where $N=\nu \in \mathbb{Z}\text{ : }\mu ⪯v$ and $\gamma \ge \lambda$. The set of branches $N$ includes all branches $\nu$ that are either equal to or divarications of branch $\mu$ (written as $\mu ⪯\nu$).

Below is a GNU Octave implementation of the perimeter attribute:

function l = per(f, R, parent)
    b = zeros(size(f));
    l = zeros(size(f));

    for a = unique(f)'
        g = f >= a;
        c = zeros(size(f));

        c = c | g > [zeros(1, size(g, 2)); g(1:end-1, :)]; % n
        c = c | g > [zeros(size(g, 1), 1), g(:, 1:end-1)]; % e
        c = c | g > [g(2:end, :); zeros(1, size(g, 2))];   % s
        c = c | g > [g(:, 2:end), zeros(size(f, 1), 1)];   % w

        b = b + c;
    end

    [_, s] = sort(f(:), "descend");

    for x = s'
        y = x;

        while b(x) > 0
            l(y) = l(y) + 1;
            b(x) = b(x) - 1;
            y = parent(y);
        end
    end
end

Compactness & Circularity Ratio

Using the area $A(X)$ and perimeter $𝔅(X)$ attributes, composite attributes like compactness and the circularity ratio can be computed. Gonzales and Woods provide the following formal definitions of compactnes $C(X)$ and circularity ratio $R_c(X)$:³

These attributes indicate the shape of the components they represent. For example, $R_c(X)$ approaches a value of $1$ as the shape of the component $X$ becomes more circular.

Grayscale, Power & Volume

In addition to positional information, the value or intensity represented by elements can be indicative of a component attribute. Many examples are straightforward, such as the sum of (squared) intensities and grayscale (average value within a component). Tushabe provides the formal definition of the latter:

This can be implemented in GNU Octave code as follows:

function g = grayscale(f, R, parent)
    g = zeros(size(f));
    a = area(f, R, parent);

    [_, s] = sort(f(:), "descend");

    for x = s'
        y = x;

        while true
            g(y) = g(y) + f(x) / a(y);

            if y == parent(y)
                break;

            end

            y = parent(y);
        end
    end
end

More sophisticated measurements based on intensity levels include power

for an image $f$ and parent intensity level $\alpha$, and volume

Entropy

Gonzalez and Woods define the entropy attribute as the average amount of information conveyed by each element in a component.³ Given a discrete set of distinct grayscale values $\{a_1,a_2,\dots ,a_J\}$ in a component of size $M\times N$, the probability of encountering a grayscale value $a_j$ in the component is

This function can be used to compute a histogram of component $X$. Using this definition, Gonzalez and Woods provide the formal definition of entropy:³

Invariant Moments

Westenberg, Roerdink, and Wilkinson provide definition for the four invariant moments: non-compactness, elongation, flatness and sparseness.⁴ These are suitable for usage in two- and three-dimensional components, unlike those presented by Hu, which only apply to two-dimensional components.⁵ Westenberg, Roerdink, and Wilkinson define the non-compactness attribute $𝒩(X)$ as

with the moment of inertia tensor $𝐈(X)$ defined as

for $i,j\in \{x,y,z\}$. Computing eigenvalues ${\lambda }_i(X)$ of $𝐈(X)$ and ordering them such that

allows the computation of the attributes elongation $ℰ(X)$, flatness $ℱ(X)$ and sparseness $𝒮(X)$: