Mathematical Morphology and Its Applications to Signal and Image Processing

In the framework of structural representations for applications in image understanding, we establish links between similarities, hypergraph theory and mathematical morphology. We propose new similarity measures and pseudo-metrics on lattices of hypergraphs based on morphological operators. New forms of these operators on hypergraphs are introduced as well. Some examples based on various dilations and openings on hypergraphs illustrate the relevance of our approach.

Ascending and descending Morse complexes are defined by the critical points and integral lines of a scalar field

f

defined on a manifold

M

. They induce a subdivision of

M

into regions of uniform gradient flow, thus providing a compact description of the topology of

M

and of the behavior of

f

over

M

. We represent the ascending and descending Morse complexes of

f

as a graph, that we call the

Morse incidence graph (MIG)

. We have defined a simplification operator on the graph-based representation, which is atomic and dimension-independent, and we compare this operator with a previous approach to the simplification of 3D Morse complexes based on the cancellation operator. We have developed a simplification algorithm based on a simplification operator, which operates on the MIG, and we show results from this implementation as well as comparisons with the cancellation operator in 3D.

Generalizations of various random tessellation models generated by Poisson point processes are proposed and their functional probability

P

(

K

) is given. They are interpreted as characteristics of Boolean random functions models, which provide a generic way of simulation of general random tessellations.

The main question of this paper is to retrieve some continuity properties on (discrete) T0-Alexandroff spaces. One possible application, which will guide us, is the construction of the so-called “tree of shapes” (intuitively, the tree of level lines). This tree, which should allow to process maxima and minima in the same way, faces quite a number of theoretical difficulties that we propose to solve using set-valued analysis in a purely discrete setting. We also propose a way to interpret any function defined on a grid as a “continuous” function thanks to an interpolation scheme. The continuity properties are essential to obtain a quasi-linear algorithm for computing the tree of shapes in any dimension, which is exposed in a companion paper [10].

The U-curve problem is an optimization problem that consists in, given a finite set

S

, a Boolean lattice

$(\mathcal{P}(S), \subseteq)$

and a chain

$\mathcal{L}$

, minimize a function

$c:\mathcal{P}(S) \rightarrow \mathcal{L}$

that satisfies an extension of Matheron’s increasing-decreasing decomposition (i.e., a function that is decomposable in U-shaped curves). This problem may be used to model problems in the domain of Mathematical Morphology, for instance, morphological operator design and some types of combinatorial optimization problems. Recently, we introduced the U-Curve-Search (UCS) algorithm, which is a solver to the U-curve problem. In this paper, we recall the principles of the UCS algorithm, present a constrained version of Serra’s formulation of the Tailor problem, prove that this problem is a U-curve problem, apply the UCS algorithm to solve it and compare the performance of UCS with another optimization algorithm. Besides, we present applications of UCS in the context of W-operator design.

This paper presents the formulation of a discrete equation whose solutions have a strong combinatory nature. More formally, given two subsets

Y

and

C

, we are interested in finding all subsets

X

that satisfy the equation (called

Minkowski Addition Equation

)

X

 ⊕ 

C

 = 

Y

. One direct application of the solutions of this equation is that they can be used to find best representations for fast computation of erosions and dilations. The main (and original) result presented in this paper (which is a theoretical result) is an analytical solution formula for this equation. One important characteristic of this analytical formula is that all solutions (which can be in worst case exponential) are expressed in a compact representation.

With the development of connected filters in the last decade, many algorithms have been proposed to compute the max-tree. Max-tree allows computation of the most advanced connected operators in a simple way. 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 five algorithms and some variations of them in a unique framework. Finally, a decision tree will be proposed to help the user choose the most appropriate algorithm according to their requirements.

In edge-weighted graphs, we provide a unified presentation of a family of popular morphological hierarchies such as component trees, quasi flat zones, binary partition trees, and hierarchical watersheds. For any hierarchy of this family, we show if (and how) it can be obtained from any other element of the family. In this sense, the main contribution of this paper is the study of all constructive links between these hierarchies.

To compute the morphological self-dual representation of images, namely the tree of shapes, the state-of-the-art algorithms do not have a satisfactory time complexity. Furthermore the proposed algorithms are only effective for 2D images and they are far from being simple to implement. That is really penalizing since a self-dual representation of images is a structure that gives rise to many powerful operators and applications, and that could be very useful for 3D images. In this paper we propose a simple-to-write algorithm to compute the tree of shapes; it works for

n

D images and has a quasi-linear complexity when data quantization is low, typically 12 bits or less. To get that result, this paper introduces a novel representation of images that has some amazing properties of continuity, while remaining discrete.

Hierarchical image representations have been addressed by various models by the past, the max-tree being probably its best representative within the scope of Mathematical Morphology. However, the max-tree model requires to impose an ordering relation between pixels, from the lowest values (root) to the highest (leaves). Recently, the

α

-tree model has been introduced to avoid such an ordering. Indeed, it relies on image quasi-flat zones, and as such focuses on local dissimilarities. It has led to successful attempts in remote sensing and video segmentation. In this paper, we deal with the problem of

α

-tree computation, and propose several efficient schemes which help to ensure real-time (or near-real time) morphological image processing.

In evaluating a hierarchy of segmentations H of an image by ground truth G, which can be partitions of the space or sets, we look for the optimal partition in H that “fits” G best. Two energies on partial partitions express the proximity from H to G, and G to H. They derive from a local version of the Hausdorff distance. Then the problem amounts to finding the cut of the hierarchy which minimizes the said energy. This cuts provide global similarity measures of precision and recall. This allows to contrast two input hierarchies with respect to the G, and also to describe how to compose energies from different ground truths. Results are demonstrated over the Berkeley database.

The goal of this paper is to provide linear or quasi-linear algorithms for producing some of the various trees used in mathemetical morphology, in particular the trees corresponding to hierarchies of watershed cuts and hierarchies of constrained connectivity. A specific binary tree, corresponding to an ordered version of the edges of the minimum spanning tree, is the key structure in this study, and is computed thanks to variations around Kruskal algorithm for minimum spanning tree.

A new approach is proposed for finding optimal cuts in hierarchies of partitions by energy minimization. It rests on the notion of

h

-increasingness, allows to find best(optimal) cuts in one pass, and to obtain nice ”climbing” scale space operators. The ways to construct

h

-increasing energies, and to combine them are studied, and illustrated by two examples on color and on textures.

Connectivity is the basis of several methodological concepts in mathematical morphology. In graph-based approaches, the notion of connectivity can be derived from the notion of adjacency. In this preliminary work, we investigate the effects of relaxing the symmetry property of adjacency. In particular, we observe the consequences on the induced connected components, that are no longer organised as partitions but as covers, and on the hierarchies that are obtained from such components. These hierarchies can extend data structures such as component-trees and partition-trees, and the associated filtering and segmentation paradigms, leading to improved image processing tools.

This paper introduces a probabilistic framework for adaptive morphological dilation and erosion. More precisely our probabilistic formalization is based on using random walk simulations for a stochastic estimation of adaptive and robust morphological operators. Hence, we propose a theoretically sound morphological counterpart of Monte Carlo stochastic filtering. The approach by simulations is inefficient but particularly tailorable for introducing different kinds of adaptability. From a theoretical viewpoint, stochastic morphological operators fit into the framework of Bellman-Maslov chains, the ( max , + )-counterpart of Markov chains, which the basis behind the efficient implementations using sparse matrix products.

It has been shown that the use of the salience map based on the salience distance transform can be useful for the construction of spatially adaptive structuring elements. In this paper, we propose salience-based parabolic structuring functions that are defined for a fixed, predefined spatial support, and have low computational complexity. In addition, we discuss how to properly define adjunct morphological operators using the new spatially adaptive structuring functions. It is also possible to obtain flat adaptive structuring elements by thresholding the salience-based parabolic structuring functions.

Regularization is an well-known technique for obtaining stable solution of ill-posed inverse problems. In this paper we establish a key relationship among the regularization methods with edge-preserving noise filtering method which leads to an efficient adaptive regularization methods. We show experimentally the efficiency and superiority of the proposed regularization methods for some inverse problems, e.g. deblurring and super-resolution (SR) image reconstruction.

In this paper we present a reconstruction method controlled by the evolution of attributes. The process begins from a marker, propagated over increasing quasi–flat zones. The evolution of several increasing and non–increasing attributes is studied in order to select the appropriate region. Additionally, the combination of attributes can be used in a straightforward way.

To demonstrate the performance of our method, three applications are presented. Firstly, our method successfully segments connected objects in range images. Secondly, input–adaptive structuring elements (SE) are defined computing the controlled propagation for each pixel on a pilot image. Finally, input–adaptive SE are used to assess shape features on the image.

Our approach is multi–scale and auto–dual. Compared with other methods, it is based on a given attribute but does not require a size parameter in order to determine appropriate regions. It is useful to extract objects of a given shape. Additionally, our reconstruction is a connected operator since quasi–flat zones do not create new contours on the image.

In this paper, nonlocal mathematical morphology operators are introduced as a natural extension of nonlocal-means in the max-plus algebra. Firstly, we show that nonlocal morphology is a particular case of adaptive morphology. Secondly, we present the necessary properties to have algebraic properties on the associated pair of transformations. Finally, we recommend a sparse version to introduce an efficient algorithm that computes these operators in reasonable computational time.

Quasi-flat zones enable the computation of homogeneous image regions with respect to one or more arbitrary criteria, such as pixel intensity. They are most often employed in simplification and segmentation, while multiple strategies exist for their application to color data as well. In this paper we explore a vector ordering based alternative method for computing color quasi-flat zones, which enables the use of vectorial

α

and

ω

parameters. The interest of this vectorial strategy w.r.t marginal quasi-flat zones is illustrated both qualitatively and quantitatively by means of color simplification and segmentation experiments.

Mathematical morphology is a very successful branch of image processing with a history of more than four decades. Its fundamental operations are dilation and erosion, which are based on the notion of a maximum and a minimum with respect to an order. Many operators constructed from dilation and erosion are available for grey value images, and recently useful analogs of these processes for matrix-valued images have been introduced by taking advantage of the so-called Loewner order. There has been a number of approaches to morphology for vector-valued images, that is, colour images based on various orders, however, each with its merits and shortcomings. In this article we propose an approach to (elementary) morphology for colour images that relies on the existing order based morphology for matrix fields of symmetric 2×2-matrices. An RGB-image is embedded into a field of those 2×2-matrices by exploiting the geometrical properties of the order cone associated with the Loewner order. To this end a modification of the HSL-colour model and a relativistic addition of matrices is introduced.

The experiments performed with various morphological elementary operators on synthetic and real images demonstrate the capabilities and restrictions of the novel approach.

Mathematical morphology (MM) is a very popular image processing framework, which offers widely-used non-linear tools. It was introduced for binary and greylevel images, but recently, numerous approaches have been proposed for color or multivariate images. Many of these approaches are based on the lexicographical ordering, which respects the total ordering properties, thus making this approach a very robust solution. However, it also has disadvantages like the subjective prioritization of the components and the perceptual nonlinearities introduced due to color component prioritization. Within this paper, we introduce a new multivariate MM approach, derived from a probabilistic approach, through the optimization of the distance between the estimated pseudo-extrema and vectors within the initial data set. We compare the results generated using the two approaches and a generic lexicographic approach based on Principal Component Analysis as the axis prioritization criteria.

In theory, there is no problem generalizing morphological operators to colour images. In practice, it has proved quite tricky to define a generalization that “makes sense”. This could be because many generalizations violate our implicit assumptions about what kind of transformations should not matter. Or in other words, to what transformations operators should be invariant. As a possible solution, we propose using frames to explicitly construct operators invariant to a given group of transformations. We show how to create saturation- and rotation-invariant frames, and demonstrate how group-invariant frames can improve results.

This paper introduces mathematical morphology for real-valued images whose support space is a Riemannian manifold. The starting point consists in replacing the Euclidean distance in the canonic quadratic structuring function by the Riemannian distance. Besides the definition of Riemannian dilation/erosion and Riemannian opening/closing, their properties are explored. We generalize also some theoretical results on Lasry–Lions regularization for Cartan–Hadamard manifolds. Theoretical connections with previous works on adaptive morphology and on manifold shape are considered. Various useful image manifolds are formalized, with an example using real-valued 3D surfaces.

In this paper, a family of weighted neighborhood sequence distance functions defined on the square grid is presented. With this distance function, the allowed weight between any two adjacent pixels along a path is given by a weight sequence. We build on our previous results, where only two or three unique weights are considered, and present a framework that allows any number of weights. We show that the rotational dependency can be very low when as few as three or four unique weights are used. An algorithm for computing the distance transform (DT) that can be used for image processing applications is also presented.

The ubiquity of the Laplace-Beltrami operator in shape analysis can be seen by observing the wide variety of applications where it has been found to be useful. Here we demonstrate a small subset of such uses with their latest developments including a scale invariant transform for general triangulated meshes, an effective and efficient method for denoising meshes using Beltrami flows via high dimensional embeddings of 2D manifolds and finally the possibility of viewing the framework of geodesic active contours as a surface minimization having the Laplace-Beltrami operator as its main ingredient.

The introduction of nonlinear filters which approximate flat dilation and erosion is an issue that has been studied during the past years. In the literature, we can find works which involve the definition of robust morphological-like filters from well-known operators such as the Counter-Harmonic Mean (CHM). The main goal of this paper is to provide the reader with a morphological CHM-based regularization which simultaneously preserve both the structural information in areas of the image with high gradient and the morphological effect in the areas with low gradient. With this purpose, we introduce a suitable mathematical framework and then deal with the variational formulation which is derived from it. Practical aspects of the implementation are discussed and some results are provided to illustrate the behaviour of our approach.

We present a novel framework for learning morphological operators using counter-harmonic mean. It combines concepts from morphology and convolutional neural networks. A thorough experimental validation analyzes basic morphological operators dilation and erosion, opening and closing, as well as the much more complex top-hat transform, for which we report a real-world application from the steel industry. Using online learning and stochastic gradient descent, our system learns both the structuring element and the composition of operators. It scales well to large datasets and online settings.

This paper defines floodings on edge weighted and on node weighted graphs. Of particular interest are the highest floodings of a graph below a ceiling function defined on the nodes. It is shown that each flooding on a node weighted graph may be interpreted as a flooding on an edge weighted graphs with appropriate weights on the edges. The highest flooding of a graph under a ceiling function is then interpreted as a shortest distance on an augmented graph, using the ultrametric distance function. Thanks to this remark, the classical shortest distance algorithms may be used for constructing floodings.

In recent works, a new notion of component-graph has been introduced to extend the data structure of component-tree –and the induced antiextensive filtering methodologies– from grey-level images to multivalued ones. In this article, we briefly recall the main structural key-points of component-graphs, and we present the initial algorithmic results that open the way to the actual development of component-graph-based antiextensive filtering procedures.

This paper introduces a generalization of self-dual marked flattenings defined in the lattice of mappings. This definition provides a way to associate a self-dual operator to every mapping that decomposes an element into sub-elements (i.e. gives a cover). Contrary to classical flattenings whose definition relies on the complemented structure of the powerset lattices, our approach uses the pseudo relative complement and supplement of the bi-Heyting algebra and a new notion of

inf-structuring functions

that provides a very general way to structure the space. We show that using an inf-structuring function based on connections allows to recover the original definition of marked flattenings and we provide, as an example, a simple inf-structuring function whose derived self-dual operator better preserves contrasts and does not introduce new pixel values.

Image simplification plays a fundamental role in Image Processing to improve results in complex tasks such as segmentation. The field of Mathematical Morphology (MM) itself has established many ways to perform such improvements. In this paper, we present a new approach for image simplification which takes into account erosion and dilation from MM. The proposed method is not self-dual and only single-band signals under a discrete domain are considered. Our main focus is on the creation of concave structuring functions based on a relation between signal extrema. This relation is given by two extrema according to their degree of separation (distance) and the respective heights (contrast). From these features, a total order relation is produced, thus supplying a way to progressively simplify the signal. Some two-dimensional images are considered here to illustrate in practice this simplification behavior.

Connected filtering is a popular strategy that relies on tree-based image representations: for example, one can compute an attribute on each node of the tree and keep only the nodes for which the attribute is sufficiently strong. 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 done not in the space of the image, but on the space of shapes built from the image. Such a processing, that we called

shape-based morphology

[30], is a generalization of the existing tree-based connected operators. In this paper, two different applications are studied: in the first one, we apply our framework to blood vessels segmentation in retinal images. In the second one, we propose an extension of constrained connectivity. In both cases, quantitative evaluations demonstrate that shape-based filtering, a mere filtering step that we compare to more evolved processings, achieves state-of-the-art results.

In this paper we present a keypoint detector based on the bimodality of the histograms of oriented gradients (HOGs). We compute the bimodality of each HOG, and a bimodality image is constructed from the result of this bimodality test. The maxima with highest dynamics of the image obtained are selected as robust keypoints. The bimodality test of HOGs used is also based on dynamics. We compare the results obtained using this method with a set of well-known keypoint detectors.

The progress in the area of object recognition in the last decade is impressive. The literature reports new descriptors, new strategies, new ways to combine descriptors and classifiers and new problems in a so fast pace that it is hard to follow the whole area. A recent problem in the area is the fine-grained categorization. In this work, to address this problem, we propose a descriptor based on the application of morphological granulometries in the map of edges of an image. This descriptor is used to characterize the distribution of lengths and orientations of edges and to build a model for generic objects. We also propose a new spatial quantization with an arbitrary number of levels and divisions in each level. This quantization is so flexible that adjacent regions may have overlapping areas to avoid breakages in the structures that are near the border of the regions as it happens in the traditional spatial pyramids. Both approaches are used in a challenging and recent object recognition problem, the categorization of very similar classes. The proposed descriptor was used along with other descriptors and the overall performance of our solution to this problem was about 8% better than other work using the bag-of-words approach reported in the literature. Our descriptor showed a result 12% better when compared to the results of other edge-related descriptor in the categorization of very similar classes.

In recent years, many new methods have been proposed for extracting curve skeletons of 3D shapes, using a mesh-contraction principle. However, it is still unclear how these methods perform with respect to each other, and with respect to earlier voxel-based skeletonization methods, from the viewpoint of certain quality criteria known from the literature. In this study, we compare six recent contraction-based curve-skeletonization methods that use a mesh representation against six accepted quality criteria, on a set of complex 3D shapes. Our results reveal previously unknown limitations of the compared methods, and link these limitations to algorithmic aspects of the studied methods.

Recently, we introduced a morphological texture contrast (MTC) operator that allows detection of textural and non-texture regions in images. In this paper we provide comparison of the MTC with other available techniques. We show that, in contrast to other approaches, the MTC discriminates between texture details and isolated features, and does not extend borders of texture regions. Using the ideas underlying the MTC operator, we develop a complementary operator called morphological feature contrast (MFC) that allows extraction of isolated features while not being confused by texture details. We illustrate an application of the MFC operator for extraction of isolated objects such as individual trees or buildings that should be distinguished from forests or urban centers. We furthermore provide an example of how this operator can be used for detection of isolated linear structures. We also derive an extended version of the MFC that works with vector-valued images.

The problem of separating touching or overlapping objects is classical in imaging. Many solutions have been proposed in 2D. While similar, the problem in 3D has differentiating features: apparent overlap due to projection effects does not exist, but real or apparent interpenetration can occur only due to either physical particle fusion or partial volume effects. Often the ability to separate objects logically is sufficient, however sometimes finding the orientation of tangent separating plane is useful. In this article, we propose a method based on power watershed for separating 3D touching objects and estimate a precise separating plane. Power watershed is used in two steps, first to obtain individual object identification, and in a second step to allow sub-voxel accuracy in the plane fitting procedure. We show that our approach is much more precise than a simple segmentation. We illustrate this in an application involving the shearing of a sample of sand grains imaged in various configurations by micro-CT tomography. Our technique measures the orientation of the contacts between grains, a quantity that is explicitly used in soil mechanics modeling, but which has up until now been difficult to measure from experiments.

Barcode technology is essential in automatic identification, and is used in a wide range of real-time applications. Different code types and applications impose special problems, so there is a continuous need for solutions with improved performance. Several methods exist for code localization, that are well characterized by accuracy and speed. Particularly, high-speed processing places need reliable automatic barcode localization, e.g. conveyor belts and automated production, where missed detections cause loss of profit. Our goal is to detect automatically, rapidly and accurately the barcode location with the help of extracted image features. We propose a new algorithm variant, that outperforms in both accuracy and efficiency other detectors found in the literature using similar ideas, and also improves on the detection performance in detecting 2D codes compared to our previous algorithm.

We propose a method for accelerating the computation of fuzzy connectedness. The method is based on a precomputation step – the construction of a

supervertex

graph whose vertices are clusters of image elements. By constructing this supervertex graph in a specific way, we can perform the bulk of the fuzzy connectedness computations on this graph, rather than on the original image, while guaranteeing exact results. Typically, the number of nodes in the supervertex graph is much smaller than the number of elements in the image, and thus less computation is required. In an experiment, we demonstrate the ability of the proposed method to accelerate the computation of fuzzy connectedness considerably.

Second-generation connectivity opened the path to the use of mask images to freely define connectivity among the image components. In theory, any image could be treated as a mask image that defines a certain connectivity. This creates a new problem in terms of which image to use. In this paper, clustering masks suitable for the analysis of astronomical images are discussed. The connectivity defined by such masks must be capable of preserving faint structures like the filaments that link merging galaxies while separating neighboring stars. In this way, the actual morphology of the objects of interest is kept. This is useful for proper segmentation. We show that viscous mathematical morphology operators have a superior performance and create appropriate connectivity masks that can deal with the characteristic features of astronomical images.

Digital diffusion processes have been introduced to capture information about the neighborhood of points in a digital object. The properties of these processes give information about curvature, about specific symmetries and particular points on the discrete set. The evolution of diffusion is governed by the

Laplace-Beltrami

operator which presides to the diffusion on the manifold, as for example random walks. In this paper, we will study the discrete Laplacian operator defined on pixels in order to understand the symmetries and extract their intersections. This will lead to the identifications of particular points or information about geometry of a digital set.

We apply morphological image processing for quality inspection of microfluidic chips. Based on a comparison of measured topographies with design data, we provide a coherent solution to four central tasks in the quality assessment of injection moulded polymer devices: determination of channel depth, identification of burrs, calculation of transcription accuracy, and detection of defective regions. Experimental comparison to manual quality inspection procedures demonstrates the good performance of the proposed automated method, and reveals its clear advantages in terms of objectivity and reliability.

Mathematical Morphology (MM) has been introduced in geographical sciences during the years 1970-1980. However it did not find the same echo in the geographer community according the areas of research. Unlike remote sensing where MM tools have been used as early as in the eighties and are nowadays widespread, in the research works resorting to spatial analysis and modelling, MM is much rarer. And yet morphological analyses exactly match the purpose of spatial analysis. This talk aims to demonstrate the relevance of MM in geography and more precisely in spatial analysis. The three applications proposed focus on socio-economic issues: urban zones of influence detection, regional differentiations analysis and spatial modelling. Finally, are highlighted and discussed the major shortcomings which hold up the spread of MM in geography, planning and geomatics.