Component Tree: Update Rather than Rebuild

Abstract

The component tree is a graph-based structure that represents in a lossless way the spatial / spectral information carried by a grey-level image. The component tree models the inclusion of the connected components over the successive threshold sets of an image, thus leading to two dual variants: the max-tree, obtained by upper-thresholding, and the min-tree, obtained by lower thresholding. Modifying a node of one tree not only modifies the associated image in a controlled way, but also modifies the other tree. In particular, removing nodes from a component tree leads to either extensive or antiextensive connected operators. In this article, we investigate the effects of (partly or fully) removing nodes from a component tree. In particular, we explore the consequences of this operation on its dual tree. In a first time, this study is carried out from a theoretical point of view. In a second time, we provide an efficient algorithmic scheme for updating the dual tree when its primal tree undergoes such transformations. In a third time, we illustrate the relevance of this scheme by designing computationally efficient alternating sequential filters that inherit the properties of connected operators.