In this article, we design an incremental method for computing seeded watershed cuts for interactive image segmentation. We propose an algorithm based on the hierarchical image representation called the binary partition tree to compute a seeded watershed cut. Additionally, we leverage properties of minimum spanning forests to introduce a parallel method for labeling a connected component. We show that those algorithms fits perfectly in an interactive segmentation process by handling user interactions, seed addition or removal, in linear time with respect to the number of affected pixels. Run time comparisons with several state-of-the-art interactive and non-interactive watershed methods show that the proposed method can handle user interactions much faster than previous methods with a significant speedup ranging from 10 to 60 on both 2D and 3D images, thus improving the user experience on large images. • Watershed cut algorithm based on binary partition trees. • Incremental watershed cut algorithm for interactive image segmentation. • Parallel connected component labeling in forests (acyclic graphs).

Component-graphs provide powerful and complex structures for multi-band image processing. We propose a multiband astronomical source detection framework with the component-graphs relying on a new set of component attributes. We propose two modules to differentiate nodes belong to distinct objects and to detect partial object nodes. Experiments demonstrate an improved capacity at detecting faint objects on a multi-band astronomical dataset.

We study the problem of fitting an ultrametric distance to a dissimilarity graph in the context of hierarchical cluster analysis. Standard hierarchical clustering methods are specified procedurally, rather than in terms of the cost function to be optimized. We aim to overcome this limitation by presenting a general optimization framework for ultrametric fitting. Our approach consists of modeling the latter as a constrained optimization problem over the continuous space of ultrametrics. So doing, we can leverage the simple, yet effective, idea of replacing the ultrametric constraint with a min-max operation injected directly into the cost function. The proposed reformulation leads to an unconstrained optimization problem that can be efficiently solved by gradient descent methods. The flexibility of our framework allows us to investigate several cost functions, following the classic paradigm of combining a data fidelity term with a regularization. While we provide no theoretical guarantee to find the global optimum, the numerical results obtained over a number of synthetic and real datasets demonstrate the good performance of our approach with respect to state-of-the-art agglomerative algorithms. This makes us believe that the proposed framework sheds new light on the way to design a new generation of hierarchical clustering methods. Our code is made publicly available at https://github.com/PerretB/ultrametric-fitting.

We propose an efficient algorithm that removes unimportant regions from a hierarchical partition tree, while preserving the hierarchical partition structure. Various experiments demonstrate that applying this algorithm on various classification or segmentation problems does indeed improve the results by a large margin. Code is available online at https://github.com/higra/Higra. B. Perret, G. Chierchia, J. Cousty, S.J. F. Guimarães, Y. Kenmochi, L. Najman, Higra: Hierarchical Graph Analysis, SoftwareX, 10, 1--6, ISSN 2019, 2352-7110, 10.1016/j.softx.2019.100335.

This paper aims to understand the practical features of hierarchies of morphological segmentations, namely the quasi-flat zones hierarchy and watershed hierarchies, and to evaluate their potential in the context of natural image analysis. We propose a novel evaluation framework for the hierarchies of partitions designed to capture various aspects of those representations: precision of their regions and contours, possibility to extract high quality horizontal cuts and optimal non-horizontal cuts for image segmentation, and the ease of finding a set of regions representing a semantic object. This framework is used to assess and to optimize hierarchies with respect to the possible pre- and post-processing steps. We show that, used in conjunction with a state-of-the-art contour detector, watershed hierarchies are competitive with the complex state-of-the-art methods for hierarchy construction. In particular, the proposed framework allows us to identify a watershed hierarchy based on a novel extinction value, the number of parent nodes that outperforms the other hierarchies of morphological segmentations. This coupled with the fact that watershed hierarchies satisfy clear global optimality properties and can be efficiently computed on large data, make them valuable candidates for various computer vision tasks.

Connected operators provide well-established solutions for digital image processing, typically in conjunction with hierarchical schemes. In graph-based frameworks, such operators basically rely on symmetric adjacency relations between pixels. In this article, we introduce a notion of directed connected operators for hierarchical image processing, by also considering non-symmetric adjacency relations. The induced image representation models are no longer partition hierarchies (i.e., trees), but directed acyclic graphs that generalize standard morphological tree structures such as component trees, binary partition trees or hierarchical watersheds. We describe how to efficiently build and handle these richer data structures, and we illustrate the versatility of the proposed framework in image filtering and image segmentation.

Connections in image processing are an important notion that describes how pixels can be grouped together according to their spatial relationships and/or their gray-level values. In recent years, several works were devoted to the development of new theories of connections among which hyperconnection (h-connection) is a very promising notion. This paper addresses two major issues of this theory. First, we propose a new axiomatic that ensures that every h-connection generates decompositions that are consistent for image processing and, more precisely, for the design of h-connected filters. Second, we develop a general framework to represent the decomposition of an image into h-connections as a tree that corresponds to the generalization of the connected component tree. Such trees are indeed an efficient and intuitive way to design attribute filters or to perform detection tasks based on qualitative or quantitative attributes. These theoretical developments are applied to a particular fuzzy h-connection, and we test this new framework on several classical applications in image processing, i.e., segmentation, connected filtering, and document image binarization. The experiments confirm the suitability of the proposed approach: It is robust to noise, and it provides an efficient framework to design selective filters.

In this paper, we investigate the possibilities offered by the extension of the connected component trees (cc-trees) to multivariate images. We propose a general framework for image processing using the cc-tree based on the lattice theory and we discuss the possible applications depending on the properties of the underlying ordered set. This theoretical reflexion is illustrated by two applications in multispectral astronomical imaging: source separation and object detection.