Extensive partition operators, gray-level connected operators, and region merging/classification segmentation algorithms: Theoretical links

The relation between morphological gray-level connected operators and segmentation algorithms based on region merging/classification strategies has been pointed out several times in the recent literature. However, to the best of our knowledge, the formal relation between them has not been established. This paper presents the link between the two domains based on the observation that both connected operators and segmentation algorithms share a key mechanism: they simultaneously operate on images and on partitions, and therefore they can be described as operations on a joint image-partition model. As a result, we analyze both segmentation algorithms and connected operators by defining operators on complete product lattices, that explicitly model gray-level and partition attributes. In the first place, starting with a complete lattice of partitions, we initially define the concept of segmentation model as a mapping in a product lattice, whose elements are three-tuples consisting of a partition, an image that models the partition attributes, and an image that represents the gray-level model associated to the segmentation. Then, assuming a conditional ordering relation, we show that any region merging/classification segmentation algorithm can be defined as an extensive operator in such a complete product lattice. In the second place, we proposed a very similar lattice-based extended representation of gray-level functions in the context of connected operators, that highlights the mathematical analogy with segmentation algorithms, but in which the ordering relation is different. We use this framework to show that every region merging/classification segmentation algorithm indeed corresponds to a connected operator. While this result provides an explanation to previous work in the area, it also opens possibilities for further analysis in the two domains. From this perspective, we additionally study some theoretical properties of a general region merging segmentation algorithm.