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).

Hierarchical image segmentation provides a region-oriented scale-space, i.e. a set of image segmentations at different detail levels in which the segmentations at finer levels are nested with respect to those at coarser levels. However, most image segmentation algorithms, among which a graph-based image segmentation method relying on a region merging criterion was proposed by Felzenszwalb–Huttenlocher in 2004, do not lead to a hierarchy. In order to cope with a demand for hierarchical segmentation, Guimarães et al. proposed in 2012 a method for hierarchizing the popular Felzenszwalb–Huttenlocher method, without providing an algorithm to compute the proposed hierarchy. This paper is devoted to providing a series of algorithms to compute the result of this hierarchical graph-based image segmentation method efficiently, based mainly on two ideas: optimal dissimilarity measuring and incremental update of the hierarchical structure. Experiments show that, for an image of size 321 × 481 pixels, the most efficient algorithm produces the result in half a second whereas the most naive one requires more than 4 h.

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.

The non-horizontal cuts of a hierarchy and the floodings of an image are well-established tools for image segmenting and filtering respectively. We present definitions of non-horizontal cuts and of floodings in the same framework of hierarchies of partitions. We show that, given a hierarchy, there is a one-to-one correspondence between the non-horizontal cuts and the floodings. This opens the door to optimal image filtering based on non-horizontal cuts and, conversely, to nonhorizontal cuts obtained by morphological floodings, or more generally by connected filterings.

In this paper, we consider the estimation of a reference shape from a set of different segmentation results using both active contours and information theory. The reference shape is defined as the minimum of a criterion that benefits from both the mutual information and the joint entropy of the input segmentations and is then called a mutual shape. This energy criterion is here justified using similarities between information theory quantities and area measures, and presented in a continuous variational framework. This framework brings out some interesting evaluation measures such as the specificity and sensitivity. In order to solve this shape optimization problem, shape derivatives are computed for each term of the criterion and interpreted as an evolution equation of an active contour. Some synthetical examples allow us to cast the light on the difference between our mutual shape and an average shape. Our framework has been considered for the estimation of a mutual shape for the evaluation of cardiac segmentation methods in MRI.

In this work, we present a hybrid algorithm to automatically delineate the heart volume in 3D cardiac computed tomography (CT) datasets for the visualization of coronary arteries. Our work eliminates the tedious and time consuming step of manually removing obscuring structures around the heart (ribs, sternum, liver...). It quickly provides a clear and well defined view of the coronaries. So far, works related to heart segmentation have mainly focused on heart cavities delineation, which is not suited for coronaries visualization. In contrast, our algorithm extracts the heart cavities, the myocardium and coronaries as a single object. The proposed approach is based on the fitting of a geometric model of the heart to a set of automatically extracted 3D points lying on the heart shell. A novel two-stage fitting scheme is used to improve the robustness to the outliers. The fitting result is further refined using a Random Walker (RW) segmentation approach. Qualitative analysis of results obtained on a 70 exam database shows the efficiency and the accuracy of our approach.

A statistical methodology is proposed to rank several estimation methods of a relevant clinical parameter when no gold standard is available. Based on a regression without truth method, the proposed approach was applied to rank eight methods without using any a priori information regarding the reliability of each method and its degree of automation. It was only based on a prior concerning the statistical distribution of the parameter of interest in the database. The ranking of the methods relies on figures of merit derived from the regression and computed using a bootstrap process. The methodology was applied to the estimation of the left ventricular ejection fraction derived from cardiac magnetic resonance images segmented using eight approaches with different degrees of automation: three segmentations were entirely manually performed and the others were variously automated. The ranking of methods was consistent with the expected performance of the estimation methods: the most accurate estimates of the ejection fraction were obtained using manual segmentations. The robustness of the ranking was demonstrated when at least three methods were compared. These results suggest that the proposed statistical approach might be helpful to assess the performance of estimation methods on clinical data for which no gold standard is available.

In this paper, we propose a new approach for color image simplification in order to improve flame pixel classification. The fire detection performance depends critically on the performance of the flame pixel classifier. Color image simplification is the process of simplifying an image in order to decrease the number of colors while preserving, as much as possible, shapes. In this work, a hierarchical clustering method in a given color space is used to map the original colors into a smaller set of representative ones, allowing the use of a simple heuristic rule for classifying the clusters related to candidate flame colors. Using reverse mapping, we identify possible flame colors in the image. Main contributions of our work are the application of a simple hierarchical clustering method to color simplification, that decreases the number of possible flame colors, and a filtering methodology to reduce the influence of outliers. Several color spaces and distance measures were used to evaluate the proposed method. Experimental results demonstrate that color simplification is essential to successfully employ heuristic classification of flame colors.

We recently introduced watershed cuts, a notion of watershed in edge-weighted graphs. In this paper, our main contribution is a thinning paradigm from which we derive three algorithmic watershed cut strategies: The first one is well suited to parallel implementations, the second one leads to a flexible linear-time sequential implementation, whereas the third one links the watershed cuts and the popular flooding algorithms. We state that watershed cuts preserve a notion of contrast, called connection value, on which several morphological region merging methods are (implicitly) based. We also establish the links and differences between watershed cuts, minimum spanning forests, shortest path forests, and topological watersheds. Finally, we present illustrations of the proposed framework to the segmentation of artwork surfaces and diffusion tensor images.

We study the watersheds in edge-weighted graphs. We define the watershed cuts following the intuitive idea of drops of water flowing on a topographic surface. We first establish the consistency of these watersheds: They can be equivalently defined by their "catchment basins" (through a steepest descent property) or by the "dividing lines" separating these catchment basins (through the drop of water principle). Then, we prove, through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, we introduce a linear-time algorithm to compute them. To the best of our knowledge, similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and in practice. Finally, the defined concepts are illustrated in image segmentation, leading to the conclusion that the proposed approach improves, on the tested images, the quality of watershed-based segmentations.

The watershed segmentation is a popular tool in image processing. Starting from an initial map, the border thinning transformation produces a map whose minima constitute the catchment basins of the watershed of the initial map. An interesting feature of the transformed map (called border kernel) is to convey not only the watershed partition but also numeric information relative to the initial map. In this paper, we provide the space of all border kernels with a semi lattice and propose morphological operations (relative to this lattice) which allow for merging border kernels and building hierarchies of watersheds based in particular on connected filters.