Multivalued component tree: New results and a bridge between partial and total partition trees

Overview & Synopsis

Tree-based structures constitute an efficient way of representing images for manipulation, processing and analysis purposes. In this context, a wide range of such trees has been proposed in the framework of mathematical morphology. These so-called morphological trees are partition trees, i.e. trees where each cut corresponds to a (partial or total) partition of the support of the image. Some of these trees belong to the subfamily of the component tree, that models an image via its successive threshold sets. The component tree and its variants were natively designed for handling grey-level images, i.e. images with values organized as a totally ordered set. Ten years ago, the notion of a multivalued component tree was introduced to extend the component tree beyond this total order hypothesis. In particular, it was shown that a component tree could be built on images with values structured by a (partial) hierarchical order. In this article, we continue and complete the study of the multivalued component tree. We observe that this tree has the unusual property of possibly being a total partition tree or a partial partition tree. Based on this fact, the first part of this article is dedicated to establish a common framework to describe the partial partition trees (e.g. the component tree and related trees) and the total partition trees (e.g. the binary partition tree and related trees). In this framework, the multivalued component tree belongs to a family that bridges both kinds of (total / partial) partition trees. Regarding the notion of multivalued component tree itself, our contributions are twofold: (1) we propose a new algorithm for the construction of the multivalued component tree; and (2) we describe two strategies for building hierarchical orders from sets of values not natively endowed with an order relation.