The tree of shapes of an image (ToS) is a powerful hierarchical representation of image. Being self-dual and contrast invariant, it is well-suited for several image processing tasks such as filtering, segmentation or object detection. It is a must-have tool in the toolbox of image processing practitioners, if only as a pre-or post-processing usage. Nevertheless, the ToS computation is a complex task, so far, limited to CPU. This is a major bottleneck in any deep-learning or real-time image processing pipeline that requires GPUs for speed. This limitation is due to a front propagation algorithm, used in the ToS construction, that is intrinsically sequential and not well-suited for massively parallel architectures. In this paper, we present a new approach to compute, end-to-end, the tree of shapes on massively parallel architectures that outperforms the existing algorithms. The parallelization strategies introduced in this paper can further be used to speed up many propagation-based algorithms such as distance transforms.

The alpha-tree, also known as the quasi-flat zone hierarchy is a widely used representation of images in Mathematical Morphology. This structure organizes the regions according to a similarity criterion into a tree, that eases the multiscale analysis of images. Many alpha-tree algorithms exist and computing this structure efficiently is still an active field of research. Indeed, the alpha-tree is commonly used in remote sensing where there is an urge for fast processing of large terabytes images. In this paper, we propose the first massively parallel alpha-tree algorithm that leverages concurrent union-find data structures to exploit the SIMT (Single Instruction Multiple Threads) programming model of GPUs. Our algorithm outperforms the State-of-the-Art parallel CPU algorithms by a factor of 10 on average on desktop computers and servers. It also opens new perspectives for using Mathematical Morphology methods on GPU pipelines.

Generic programming is a powerful paradigm abstracting data structures and algorithms to improve their reusability, as long as they respect a given interface. Coupled with a performance-driven language, it is a paradigm of choice for scientific libraries where the implementation of manipulated objects may change depending on their use case, or for performance purposes. In those performance-driven languages, genericity is often implemented statically to perform some optimization. This does not fit well with the dynamism needed to handle objects which may only be known at runtime. Thus, in this article, we evaluate a model that couples static genericity with a dynamic model based on type erasure in the context of image processing. Its cost is assessed by comparing the performance of the implementation of some common image processing algorithms in C++ and Rust, two performance-driven languages supporting some form of genericity. Finally, we demonstrate that compile-time knowledge of some specific information is critical for performance, and also that the runtime overhead depends on the algorithmic scheme in use.

C++ is a multi-paradigm language that enables the programmer to set up efficient image processing algorithms easily. This language strength comes from many aspects. C++ is high-level, so this enables developing powerful abstractions and mixing different programming styles to ease the development. At the same time, C++ is low-level and can fully take advantage of the hardware to deliver the best performance. It is also very portable and highly compatible which allows algorithms to be called from high-level, fast-prototyping languages such as Python or Matlab. One fundamental aspects where C++ shines is generic programming. Generic programming makes it possible to develop and reuse bricks of software on objects (images) of different natures (types) without performance loss. Nevertheless, conciliating genericity, efficiency, and simplicity at the same time is not trivial. Modern C++ (post-2011) has brought new features that made it simpler and more powerful. In this paper, we focus on some C++20 aspects of generic programming: ranges, views, and concepts, and see how they extend to images to ease the development of generic image algorithms while lowering the computation time.

Noise level information is crucial for many image processing tasks, such as image denoising. To estimate it, it is necessary to find homegeneous areas within the image which contain only noise. Rank-based methods have proven to be efficient to achieve such a task. In the past, we proposed a method to estimate the noise level function (NLF) of grayscale images using the tree of shapes (ToS). This method, relying on the connected components extracted from the ToS computed on the noisy image, had the advantage of being adapted to the image content, which is not the case when using square blocks, but is still restricted to grayscale images. In this paper, we extend our ToS-based method to color images. Unlike grayscale images, the pixel values in multivariate images do not have a natural order relationship, which is a well-known issue when working with mathematical morphology and rank statistics. We propose to use the multivariate ToS to retrieve homogeneous regions. We derive an order relationship for the multivariate pixel values thanks to a complete lattice learning strategy and use it to compute the rank statistics. The obtained multivariate NLF is composed of one NLF per channel. The performance of the proposed method is compared with the one obtained using square blocks, and validates the soundness of the multivariate ToS structure for this task.

In Mathematical Morphology, the max-tree is a region-based representation that encodes the inclusion relationship of the threshold sets of an image. This tree has proved useful in numerous image processing applications. For the last decade, work has led to improving the construction time of this structure; mixing algorithmic optimizations, parallel and distributed computing. Nevertheless, there is still no algorithm that benefits from the computing power of the massively parallel architectures. In this work, we propose the first GPU algorithm to compute the max-tree. The proposed approach leads to significant speed-ups, and is up to one order of magnitude faster than the current State-of-the-Art parallel CPU algorithms. This work paves the way for a max-tree integration in image processing GPU pipelines and real-time image processing based on Mathematical Morphology. It is also a foundation for porting other image representations from Mathematical Morphology on GPUs.

The Tree of Shapes (ToS) is a morphological, tree-based representation of an image, translating the inclusion of its level lines. It features many invariants to image changes, which make it well-suited for many applications in image processing and pattern recognition. In this paper, we propose a way of turning a ToS computation into a Max-Tree computation. The latter has been widely studied, and many efficient algorithms (including parallel ones) have been developed. Furthermore, we develop a specific optimization to speed-up the common 2D case. It follows a simple and efficient algorithm, running in linear time with a low memory footprint, that outperforms other currently used algorithms. For Reproducible Research purpose, we distribute our code as free software.

Current trends in image segmentation are to compute a hierarchy of image segmentations from fine to coarse. A classical approach to obtain a single meaningful image partition from a given hierarchy is to cut it in an optimal way, following the seminal approach of the scale-set theory. While interesting in many cases, the resulting segmentation, being a non-horizontal cut, is limited by the structure of the hierarchy. In this paper, we propose a novel approach that acts by transforming an input hierarchy into a new saliency map. It relies on the notion of shape space: a graph representation of a set of regions extracted from the image. Each region is characterized with an attribute describing it. We weigh the boundaries of a subset of meaningful regions (local minima) in the shape space by extinction values based on the attribute. This extinction-based saliency map represents a new hierarchy of segmentations highlighting regions having some specific characteristics. Each threshold of this map represents a segmentation which is generally different from any cut of the original hierarchy. This new approach thus enlarges the set of possible partition results that can be extracted from a given hierarchy. Qualitative and quantitative illustrations demonstrate the usefulness of the proposed method.

Satellite image classification is a key task used in remote sensing for the automatic interpretation of a large amount of information. Today there exist many types of classification algorithms using advanced image processing methods enhancing the classification accuracy rate. One of the best state-of-the-art methods which improves significantly the classification of complex scenes relies on Self-Dual Attribute Profiles (SDAPs). In this approach, the underlying representation of an image is the Tree of Shapes, which encodes the inclusion of connected components of the image. The SDAP computes for each pixel a vector of attributes providing a local multiscale representation of the information and hence leading to a fine description of the local structures of the image. Instead of performing a pixel-wise classification on features extracted from the Tree of Shapes, it is proposed to directly classify its nodes. Extending a specific interactive segmentation algorithm enables it to deal with the multi-class classification problem. The method does not involve any statistical learning and it is based entirely on morphological information related to the tree. Consequently, a very simple and effective region-based classifier relying on basic attributes is presented.

The topographic map of a gray-level image, also called tree of shapes, provides a high-level hierarchical representation of the image contents. This representation, invariant to contrast changes and to contrast inversion, has been proved very useful to achieve many image processing and pattern recognition tasks. Its definition relies on the total ordering of pixel values, so this representation does not exist for color images, or more generally, multivariate images. Common workarounds, such as marginal processing, or imposing a total order on data, are not satisfactory and yield many problems. This paper presents a method to build a tree-based representation of multivariate images, which features marginally the same properties of the gray-level tree of shapes. Briefly put, we do not impose an arbitrary ordering on values, but we only rely on the inclusion relationship between shapes in the image definition domain. The interest of having a contrast invariant and self-dual representation of multivariate image is illustrated through several applications (filtering, segmentation, and object recognition) on different types of data: color natural images, document images, satellite hyperspectral imaging, multimodal medical imaging, and videos.

The tree of shapes is a morphological tree that provides an high-level hierarchical representation of the image suitable for many image processing tasks. This structure has the desirable properties to be self-dual and contrast-invariant and describes the organization of the objects through level lines inclusion. Yet it is defined on gray-level while many images have multivariate data (color images, multispectral images.) where information are split across channels. In this paper, we propose some leads to extend the tree of shapes on colors with classical approaches based on total orders, more recent approaches based on graphs and also a new distance-based method. Eventually, we compare these approaches through denoising to highlight their strengths and weaknesses and show the strong potential of the new methods compared to classical ones.

Many methods based on the morphological notion of shapes (i.e., connected components of level sets) have been proved to be very efficient in shape recognition and shape analysis. The inclusion relationship of the level lines (boundaries of level sets) forms the tree of shapes, a tree-based image representation with a high potential. Numerous applications using this tree representation have been proposed. In this article, we propose an efficient algorithm that extracts a set of disjoint level lines in the image. These selected level lines yield a simplified image with clean contours, which provides an intuitive idea about the main structure of the tree of shapes. Besides, we obtain a saliency map without transition problems around the contours by weighting level lines with their significance. Experimental results demonstrate the efficiency and usefulness of our method.

In mathematical morphology the tree of shapes of a gray level image is a versatile representation that allows for multiple powerful applications. That structure is highly interesting because it is a self-dual representation invariant by contrast changes and since many authors state that object contours are well described by level lines. Such a representation has not yet been defined (thus used) on color images because a priori a total order on colors is required that really make sense on data. In this paper we propose a solution to obtain a tree of shapes on color images without resorting to an ordering of colors. To that aim we relax the definition of shapes and we show that relevant applications follow from our proposal.

Connected operators are morphological tools that have the property of filtering images without creating new contours and without moving the contours that are preserved. Those operators are related to the max-tree and min-tree representations of images, and many algorithms have been proposed to compute those trees. However, no exhaustive comparison of these algorithms has been proposed so far, and the choice of an algorithm over another depends on many parameters. Since the need for fast algorithms is obvious for production code, we present an in-depth comparison of the existing algorithms in a unique framework, as well as variations of some of them that improve their efficiency. This comparison involves both sequential and parallel algorithms, and execution times are given with respect to the number of threads, the input image size, and the pixel value quantization. Eventually, a decision tree is given to help the user choose the most appropriate algorithm with respect to the user requirements. To favor reproducible research, an online demo allows the user to upload an image and bench the different algorithms, and the source code of every algorithms has been made available.