Directed Connected Operators: Asymmetric Hierarchies for Image Filtering and Segmentation

Fast Component Tree Computation for Images of Limited Levels

Component trees have many applications. We introduce a new component tree computation algorithm, applicable to 4-/8-connectivity and 6-connectivity. The algorithm consists of two steps: building level line trees using an optimized top-down algorithm, and computing components from level lines by a novel line-by-line approach. As compared with traditional component computation algorithms, the new algorithm is fast for images of limited levels. It represents components by level lines, offering boundary information which traditional algorithms do not provide.

Efficient Algorithms for Hierarchical Graph-Based Segmentation Relying on the Felzenszwalb–Huttenlocher Dissimilarity

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.

Evaluation of Hierarchical Watersheds

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.

Curvilinear Structure Analysis by Ranking the Orientation Responses of Path Operators

The analysis of thin curvilinear objects in 3D images is a complex and challenging task. In this article, we introduce a new, non-linear operator, called RORPO (Ranking the Orientation Responses of Path Operators). Inspired by the multidirectional paradigm currently used in linear filtering for thin structure analysis, RORPO is built upon the notion of path operator from mathematical morphology. This operator, unlike most operators commonly used for 3D curvilinear structure analysis, is discrete, non-linear and non-local. From this new operator, two main curvilinear structure characteristics can be estimated: an intensity feature, that can be assimilated to a quantitative measure of curvilinearity; and a directional feature, providing a quantitative measure of the structure's orientation. We provide a full description of the structural and algorithmic details for computing these two features from RORPO, and we discuss computational issues. We experimentally assess RORPO by comparison with three of the most popular curvilinear structure analysis filters, namely Frangi Vesselness, Optimally Oriented Flux, and Hybrid Diffusion with Continuous Switch. In particular, we show that our method provides up to 8 percent more true positive and 50 percent less false positives than the next best method, on synthetic and real 3D images.

Connected Filtering on Tree-Based Shape-Spaces

Connected filters are well-known for their good contour preservation property. A popular implementation strategy relies on tree-based image representations: for example, one can compute an attribute characterizing the connected component represented by each node of the tree and keep only the nodes for which the attribute is sufficiently high. This operation can be seen as a thresholding of the tree, seen as a graph whose nodes are weighted by the attribute. Rather than being satisfied with a mere thresholding, we propose to expand on this idea, and to apply connected filters on this latest graph. Consequently, the filtering is performed not in the space of the image, but in the space of shapes built from the image. Such a processing of shape-space filtering is a generalization of the existing tree-based connected operators. Indeed, the framework includes the classical existing connected operators by attributes. It also allows us to propose a class of novel connected operators from the leveling family, based on non-increasing attributes. Finally, we also propose a new class of connected operators that we call morphological shapings. Some illustrations and quantitative evaluations demonstrate the usefulness and robustness of the proposed shape-space filters.