Keywords

1 Introduction

Mathematical morphology (MM) is a powerful non-linear theory widely used for image processing and analysis [11, 22]. The first morphological operators have been conceived by Matheron and Serra in the early 1960s for binary images [11]. Although binary MM has been effectively extended to gray-scale images using level-sets, umbra, and fuzzy set theory [24], the extension of MM to multivalued images is not general because there is no natural ordering for vectors [2]. Indeed, much research on multivalued MM focused on finding an appropriate ordering for a given image processing task [2, 7, 9, 15, 25, 28]. A detailed account on multivalued MM can be found in [2, 3, 28].

In this paper, we focus on a distance-based approach which have been investigated and generalized by many researchers including [1, 2, 8, 14, 20, 26,27,28]. Precisely, we focus on the distance-based approach to multivalued MM obtained by first comparing the distance between the value of a pixel and a reference value \(\varvec{r}\) followed by a lexicographical cascade to resolve ambiguities [2]. Although it has been extended using support-vector machines, krigging, and fuzzy set theory [20, 27], we shall focus our attention in the simplest distance-based approach because it depends on a single meaningful parameter – the reference \(\varvec{r}\). Precisely, we first characterize the outcome of an elementary distance-based morphological operator as a function of the reference. Then, we address the case in which we are uncertain about the appropriate reference value \(\varvec{r}\). Using probability theory, we assume that the reference is modeled by a random variable. Furthermore, to obtain relevant information on the distance-based morphological operators, we use descriptive statistics such as the expectation, the mode, or some measures of dispersion. For illustrative purpose, we apply some statistics of distance-based morphological operators for edge detection in color image and, despite the lack of interpretation, we obtain some promising results.

The paper is organized as follows: Next section reviews the distance-based approach and presents a characterization of distance-based erosions, dilations, and gradients. Statistics of the distance-based morphological operators are addressed in Sect. 4 while the computational experiment for edge detection is provided in Sect. 5. The paper finishes with some concluding remarks in Sect. 6.

2 Distance-Based Elementary Morphological Operators

A multivalued image can be modeled as a mapping \(\varvec{f}:\mathcal {D} \rightarrow \mathbb {V}\), from a point set \(\mathcal {D}\) into a vector-valued space \(\mathbb {V}\). In this paper, we assume that the point set is \(\mathcal {D}\subseteq \mathbb {Z}^{2}\). Also, let us assume that the value set \(\mathbb {V} \subset \mathbb {R}^n\). Additional requirements on \(\mathbb {V}\) will be included accordingly throughout the paper.

Although MM can be defined in more general mathematical structures such as sponges [10] and inf-lattices [12], in this paper we focus on a particular but very useful approach to multivalued MM based on complete lattices [11, 19]. Recall that a partially ordered set \((\mathbb {L},\le )\) is a complete lattice if every subset \(X \subseteq \mathbb {L}\) has an infimum and a supremum on \(\mathbb {L}\), denoted respectively by \(\bigwedge X\) and \(\bigvee X\) [4].

Like the classical approaches to MM, erosions and dilations of a lattice-valued image \(\varvec{f}: \mathcal {D} \rightarrow \mathbb {V}\) can be defined in terms of a structuring element B. The structuring element B is used to extract relevant information about the shape and form of objects in the probed image \(\varvec{f}\) [23]. The two elementary non-linear, translation invariant morphological operators for lattice-valued images can defined as follows using a structuring element: Let the value set \(\mathbb {V}\), equipped with a partial order “\(\le \)”, be a complete lattice. The erosion and the dilation of a lattice-valued image \(\varvec{f}: \mathcal {D} \rightarrow \mathbb {V}\) by a structuring element B, denoted respectively by \(\varvec{\varepsilon }_{B}(\varvec{f})\) and \(\varvec{\delta }_{B}(\varvec{f})\), are the lattice-valued images given by

$$\begin{aligned} \varvec{\varepsilon }_{B}(\varvec{f})(x)= \bigwedge \varvec{f}(B_x) \quad \text{ and } \quad \varvec{\delta }_{B}(\varvec{f})(x)= \bigvee \varvec{f}(B_x), \quad \forall x \in \mathcal {D}, \end{aligned}$$
(1)

where

$$\begin{aligned} \varvec{f}(B_x) = \{\varvec{f}(x+b):b \in B,x+b\in \mathcal {D}\},\end{aligned}$$
(2)

is the set of the values of the image \(\varvec{f}\) in the pixels selected by the structuring element B translated by \(x \in \mathcal {D}\). We would like to recall that the elementary morphological operators given by (1) satisfies the following fundamental relationship from algebraic mathematical morphology called adjunction [11]: Given two images \(\varvec{f}\) and \(\varvec{g}\), we have \(\delta _B(\varvec{f}) \le \varvec{g}\) if and only if \(\varvec{f}\le \varvec{\varepsilon }_{\check{B}}(\varvec{g})\), where \(\check{B} = \{-b:b \in B\}\) is the reflected structuring element.

The fundamental requirement in (1) is a partial order with well defined extreme operations. It turns out, however, that there is no natural ordering for vectors. Therefore, much research on multivalued MM have been focused on determining appropriate vector ordering schemes [2, 7, 9, 15, 25, 28]. A detailed account on the various approaches to multivalued MM can be found in [2, 3]. In the following, we focus on the distance-based approach examined by Angulo [2].

Briefly, a distance-based order is a reduced order in which the elements are ranked by comparing the distance to a certain reference value \(\varvec{r} \in \mathbb {V}\). In order to avoid ambiguities, the usual lexicographical cascade is used in the subsequent comparisons. Formally, suppose that \(\mathbb {V} \subseteq \mathbb {R}\) is equipped with a metric \(d:\mathbb {V}\times \mathbb {V} \rightarrow [0,+\infty )\). Given a reference value \(\varvec{r} \in \mathbb {V}\), a distance-based order is defined as follows for any \(\varvec{u}=(u_1,\ldots ,u_n) \in \mathbb {V}\) and \(\varvec{v}=(v_1,\ldots ,v_n) \in \mathbb {V}\):

$$\begin{aligned} \varvec{u} \preccurlyeq _{\varvec{r}} \varvec{v} \ \Leftrightarrow \left\{ \begin{array}{l} d\left( \varvec{v},\varvec{r}\right) <_{\mathbb {R}} d\left( \varvec{u},\varvec{r}\right) , \\ d\left( \varvec{u},\varvec{r}\right) = d\left( \varvec{v},\varvec{r}\right) \quad \text{ and } \quad \varvec{u} \le _\mathtt {lex} \varvec{v}, \end{array} \right. \end{aligned}$$
(3)

where the symbol “\(\le _\mathtt {lex}\)” denotes the usual lexicographical ordering, that is, \(\varvec{u}\le _\mathtt {lex} \varvec{v}\) if and only if there exists \(\ell \in \{1,\ldots ,n\}\) such that \(u_j = v_j\) for all \(j < \ell \) and \(u_\ell \le _{\mathbb {R}} v_\ell \). Note that, using the distance-based order “\(\preccurlyeq _{\varvec{r}}\)”, an element \(\varvec{v}\) is larger than or equal to another element \(\varvec{u}\) if \(\varvec{v}\) is closer to the reference \(\varvec{r}\) than \(\varvec{u}\). Furthermore, for any \(\varvec{u},\varvec{v}\in \mathbb {V}\) either \(\varvec{u}\preccurlyeq _{\varvec{r}}\varvec{v}\) or \(\varvec{v}\preccurlyeq _{\varvec{r}}\varvec{u}\) hold true. Hence, the relation “\(\preccurlyeq _{\varvec{r}}\)” given by (3) is a total order. Although a total order circumvent the false color problem [21], they are usually not regular with respect to a metric [6].

Suppose that \(\mathbb {V} \subseteq \mathbb {R}^n\) is a complete lattice with the distance-based order given by (3). Accordingly, we define the distance-based erosion and dilation of a multivalued image \(\varvec{f}:\mathcal {D} \rightarrow \mathbb {V}\) by a structuring element B, denoted respectively by \(\varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})\) and \(\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})\), using (1) and (3). The dilation \(\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x)\) yields the element of \(\varvec{f}(B_x)\) closest to the reference \(\varvec{r}\). On the downside, the erosion \(\varvec{\varepsilon }_{B}^{\varvec{r}}(f)\) does not have a simple interpretation [28]. Nevertheless, the distance-based morphological operators and their compositions have been effectively applied for image filtering, enhancement, and analysis [2]. In these applications, the reference \(\varvec{r}\in \mathbb {V}\) must be defined a priori by the user.

Apart from the two elementary operators, we define the distance-based gradient as the distance between dilation and erosion. The morphological gradient is given by

$$\begin{aligned} \varvec{\varrho }_{B}^{\varvec{r}}(\varvec{f})(x)= d\big (\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x), \varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})(x)\big ), \quad \forall x \in \mathcal {D}, \end{aligned}$$
(4)

where d denotes a metric on \(\mathbb {V}\). The morphological gradient can be used for image segmentation or edge detection. Since an effective application of the distance-based morphological operators depends on an appropriate choice of the reference \(\varvec{r}\in \mathbb {V}\), let us characterize them as a function of \(\varvec{r}\).

3 Characterization of Distance-Based Morphological Operators

The elementary distance-based morphological operators depend on the reference \(\varvec{r}\). The effect of the reference on elementary distance-based morphological operators is related to the Voronoi diagram and its variation. Precisely, the distance-based dilation is directly related to the Voronoi diagram while the distance-based erosion is directly related to the farthest neighbor diagram. Using Voronoi’s diagram and its variation, we can characterize the distance-based morphological operators as follows:

Theorem 1

Let \(\mathbb {V} \subseteq \mathbb {R}^n\), equipped with a metric \(d:\mathbb {V} \times \mathbb {V} \rightarrow [0,+\infty )\), be a complete lattice with the distance-based order “\(\preccurlyeq _{\varvec{r}}\)” given by (3). Consider a multivalued image \(\varvec{f}:\mathcal {D} \rightarrow \mathbb {V}\) and a flat and finite structuring element B. Since B is finite, we can write \(\varvec{f}(B_x) = \{\varvec{f}_{1}(x),\ldots ,\varvec{f}_{k(x)}(x)\}\), where \(k(x) \le \text {Card}(B)\), for any \(x \in \mathcal {D}\). Furthermore, let

$$\begin{aligned} RV_\ell (x) = \{ \varvec{v}\in \mathbb {V}: d(\varvec{f}_\ell (x),\varvec{v}) <_\mathbb {R}d(\varvec{f}_i(x),\varvec{v}), \forall i \ne \ell \},\end{aligned}$$
(5)

and

$$\begin{aligned} RF_\ell (x) = \{ \varvec{v}\in \mathbb {V}: d(\varvec{f}_j(x),\varvec{v}) <_\mathbb {R}d(\varvec{f}_\ell (x),\varvec{v}), \forall j \ne \ell \},\end{aligned}$$
(6)

denote respectively the interior of the Voronoi region and the interior of the Voronoi region of the farthest neighbor which contains the value \(\varvec{f}_\ell (x) \in \varvec{f}(B_x)\). The distance-based erosion, dilation, and gradient, given by (1) and (4), as a function of the reference \(\varvec{r}\in \mathbb {V}\), satisfy the following equations for \(x \in \mathcal {D}\):

$$\begin{aligned} \varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})(x)&=\varvec{f}_{i}(x), \quad \text{ if } \quad \varvec{r} \in RF_{i}(x), \end{aligned}$$
(7)
$$\begin{aligned} \varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x)&= \varvec{f}_j(x), \quad \text{ if } \quad \varvec{r} \in RV_{j}(x), \end{aligned}$$
(8)
$$\begin{aligned} \varvec{\varrho }_{B}^{\varvec{r}}(\varvec{f})(x)&= d(\varvec{f}_{i}(x), \varvec{f}_{j}(x)), \quad \text{ if } \quad \varvec{r} \in RF_{i}(x) \cap RV_{j}(x). \end{aligned}$$
(9)

Proof

Due to page constrain, let us only show (7). The identity (8) can be derived in a similar fashion while (9) follows from (7) and (8). Let \(\varvec{f}:\mathcal {D} \rightarrow \mathbb {V}\) be a multivalued image and B a flat and finite structuring element. Given \(x \in \mathcal {D}\), let us assume \(\varvec{r}\in RF_i(x)\). From (6) we have \(d(\varvec{f}_j(x),\varvec{r}) < d(\varvec{f}_i(x),\varvec{r})\) for all \(j \ne i\). Furthermore, from (3), we have \(\varvec{f}_i(x) \preccurlyeq _{\varvec{r}}\varvec{f}_j(x)\) for all j. Thus, from (1), the following identities hold true where “\(\curlywedge _{\varvec{r}}\)” denotes the infimum obtained using the distance-based ordering “\(\preccurlyeq _{\varvec{r}}\)”:

We would like to point out that, for any \(x \in \mathcal {D}\), \(\varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})(x)\) and \(\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x)\) assumes \(k(x) \le \mathtt {Card}\big (\varvec{f}(B_x)\big )\) distinct values. In contrast, the gradient \(\varvec{\varrho }_{B}^{\varvec{r}}(\varvec{f})(x)\) admits at most \(k(x)(k(x) - 1)/2\) values. The following example illustrates the distance-based morphological operators \(\varvec{\varepsilon }_{B}^{\varvec{r}}\), \(\varvec{\delta }_{B}^{\varvec{r}}\), and \(\varvec{\varrho }_{B}^{\varvec{r}}\) as a function of \(\varvec{r}\).

Fig. 1.
figure 1

Voronoi diagram and the diagram of the farthest neighbor of \(\varvec{f}(B_x)\).

Full size image

Example 1

Consider \(\mathbb {V}=[0,1]^2\) and let \(\varvec{f}(B_x)=\left\{ \varvec{f}_1(x), \varvec{f}_2(x), \varvec{f}_3(x)\right\} \), where \(\varvec{f}_1(x)=\left( 0.6,0.9\right) \), \(\varvec{f}_2(x)=\left( 0.9,0.9\right) \), and \(\varvec{f}_3(x)=\left( 0.9,0.4\right) \), be the set of values of a multivalued image \(\varvec{f}:\mathcal {D} \rightarrow \mathbb {V}\) selected by a finite structuring element B centered at \(x \in \mathcal {D}\). The Voronoi regions \(RV_{1}(x)\), \(RV_{2}(x)\), and \(RV_{3}(x)\) as well as the farthest neighbor regions \(RF_{1}(x)\), \(RF_{2}(x)\), and \(RF_{3}(x)\) are shown in Fig. 1. Accordingly, the distance-based dilation and erosion satisfy respectively

$$ \varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x)= {\left\{ \begin{array}{ll} (0.6, 0.9), &{} \varvec{r} \in RV_{1},\\ (0.9, 0.4), &{} \varvec{r} \in RV_{2},\\ (0.9, 0.9), &{} \varvec{r} \in RV_{3}, \end{array}\right. } \quad \text{ and } \quad \varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})(x)= {\left\{ \begin{array}{ll} (0.6, 0.9), &{} \varvec{r} \in RF_{1},\\ (0.9, 0.4), &{} \varvec{r} \in RF_{2}. \\ (0.9, 0.9), &{} \varvec{r} \in RF_{3}, \end{array}\right. } $$

Furthermore, using the Euclidean distance, we obtain

$$ \varvec{\varrho }_{B}^{\varvec{r}}(\varvec{f})(x) = {\left\{ \begin{array}{ll} 0.3,&{} \varvec{r} \in \left( RV_{1}\cap RF_{3}\right) \cup \left( RV_{3}\cap RF_{1}\right) ,\\ 0.5, &{} \varvec{r} \in \left( RV_{2}\cap RF_{3}\right) \cup \left( RV_{3}\cap RF_{2}\right) ,\\ 0.583, &{} \varvec{r} \in \left( RV_{1}\cap RF_{2}\right) \cup \left( RV_{2}\cap RF_{1}\right) . \end{array}\right. } $$

We would like to conclude this section remarking that Theorem 1 do not characterize the distance-based operators in the boundary \(\partial RV_\ell \) of a Voronoi region and the boundary \(\partial RF_\ell \) of a farthest neighbor region. According to (3), the values of \(\varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})(x)\), \(\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x)\), and \(\varvec{\varrho }_{B}^{\varvec{r}}(\varvec{f})(x)\) are determined by the lexicographical ordering if \(\varvec{r}\in \partial RV_\ell \) or \(\varvec{r}\in \partial RF_\ell \). Nevertheless, since the unions \(\cup _{\ell =1}^{k(x)} \partial RV_\ell \) and \(\cup _{\ell =1}^{k(x)} \partial RF_\ell \) of all the boundaries have both Lebesgue measure zero, the values of the reference \(\varvec{r}\) not covered by Theorem 1 are irrelevant in practical situations.

4 Statistics of Distance-Based Morphological Operators

In the last decades, different approaches to distance-based color MM have been proposed by prominent researchers including [1, 2, 8, 14, 20, 26]. Despite successful applications, these approaches often face the difficult task of choosing a suitable reference for sorting vector values. In this section, we assume we are uncertain about the reference value \(\varvec{r}\in \mathbb {V}\). Precisely, using probability theory, the uncertainty about the reference is expressed using a vector-valued random variable \(\varvec{R}\). Most importantly, we can use a descriptive statistic \(\varvec{\mathcal {S}}\), such as a measure of central tendency or dispersion, to obtain relevant information on the distance-based morphological operators \(\varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})(x)\), \(\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x)\), and \(\varvec{\varrho }_{B}^{\varvec{r}}(\varvec{f})(x)\). Let us formalize this reasoning.

Let \(\varvec{f}:\mathcal {D}\rightarrow \mathbb {V}\) be a multivalued image and consider a multivariate random variable \(\varvec{R}\) on \(\mathbb {V} \subset \mathbb {R}^n\). From Theorem 1, for each \(x \in \mathcal {D}\), the distance-based operators \(\varvec{\varepsilon }_{B}^{\varvec{r}}\) and \(\varvec{\delta }_{B}^{\varvec{r}}\) map a sample \(\varvec{r}\in \mathbb {V}\) from \(\varvec{R}\) to an element of \(\varvec{f}(B_x) = \{\varvec{f}_1(x),\ldots ,\varvec{f}_{k(x)}(x)\}\). Hence, given an image \(\varvec{f}:\mathcal {D} \rightarrow \mathbb {V}\), a structuring element B, and \(x \in \mathcal {D}\), we can interpret \(\varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})(x)\) and \(\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x)\) as mappings from \(\mathbb {V}\) to \(\varvec{f}(B_x)\). Precisely, we can define \(\varvec{H}:\mathbb {V}\rightarrow \{\varvec{f}_1(x),\ldots ,\varvec{f}_{k(x)}\}\) by setting either \(\varvec{H}(\varvec{r}) = \varvec{\varepsilon }_{B}^{\varvec{r}}(f)(x)\) or \(\varvec{H}(\varvec{r}) = \varvec{\delta }_{B}^{\varvec{r}}(f)(x)\) for all \(\varvec{r}\in \mathbb {V}\). Furthermore, let \(\varvec{H}(\varvec{R})\) denote the random variable obtained by applying \(\varvec{H}\) on \(\varvec{R}\) and let \(\mathtt {Pr}\left[ \varvec{H}(\varvec{R})=\varvec{f}_{\ell }(x)\right] \) denote the probability of \(\varvec{H}(\varvec{R})=\varvec{f}_{\ell }(x)\), for \(\ell \in \{1,\ldots ,k(x)\}\). Using a descriptive statistic \(\varvec{\mathcal {S}}\), we define new operators as follows in a point-wise manner where \(\varvec{r}\in \mathbb {V}\) is interpreted as a sample from the random variable \(\varvec{R}\):

$$\begin{aligned} \varvec{\mathcal {S}}\varvec{\varepsilon }_{B}(\varvec{f})(x) = \varvec{\mathcal {S}}\left( \varvec{\varepsilon }^{\varvec{r}}_{B}(\varvec{f})(x) \right) \quad \text{ and } \quad \varvec{\mathcal {S}}\varvec{\delta }_{B}(\varvec{f})(x) = \varvec{\mathcal {S}}\left( \varvec{\delta }^{\varvec{r}}_{B}(\varvec{f})(x) \right) , \quad \forall x \in \mathcal {D}. \end{aligned}$$
(10)

In the sequel, we review some vector-valued statistics used as measures of central tendency and dispersion of a (function of a) random variable [13, 17].

The expectation of \(\varvec{H} (\varvec{R})\), which is a measure of central tendency, is given by

$$\begin{aligned} \varvec{E}(\varvec{H}(\varvec{R}))= \displaystyle \sum _{j=1}^{k(x)} \varvec{f}_{j}(x) \mathtt {Pr}\left[ \varvec{H}(\varvec{R})=\varvec{f}_{j}(x)\right] . \end{aligned}$$
(11)

As another measure of central tendency, the mode of \(\varvec{H} (\varvec{R})\) is a value \(\varvec{f}_\ell (x)\) such that \(\mathtt {Pr}[\varvec{H} (\varvec{R}) = \varvec{f}_\ell (x)]\) is maximum.

The scatter matrix of \( \varvec{H} (\varvec{R}) \), denoted by \( \varvec{\varSigma } \), is determined by means of the equation

$$\begin{aligned} \varvec{\varSigma }=\varvec{E}\left( \left( \varvec{H}(\varvec{R}) -\varvec{E}(\varvec{H}(\varvec{R})) \right) \left( \varvec{H}(\varvec{R}) - \varvec{E}(\varvec{H}(\varvec{R})\right) ^{T}\right) , \end{aligned}$$
(12)

where \(\varvec{X}^{T}\) denotes the transpose of the column-vector \(\varvec{X}\). The scatter matrix \(\varvec{\varSigma }\) is used to define two measures of dispersion which generalize the notion of standard deviation. First, since \(\varvec{\varSigma } \) is a symmetric and semidefinite positive matrix, its determinant as well as its trace are non-negative real numbers. The square-root of the determinant of \( \varvec{\varSigma }\), denoted by \(\varvec{\mathtt {std}_{g}}\big (\varvec{H}(\varvec{R})\big )\), is called generalized standard deviation of \( \varvec{H}(\varvec{R})\). The total standard deviation of \(\varvec{H}(\varvec{R})\), denoted by \(\varvec{\mathtt {std}_{t}}(\varvec{H}(\varvec{R}))\), corresponds to the square-root of the trace of the scatter matrix \(\varvec{\varSigma }\). Both generalized and total standard deviation generalize the notion of standard deviation to multivalued random variables. Another measure of dispersion of the random variable \(\varvec{H}(\varvec{R})\) is the Gini’s mean difference, denoted by \(\varvec{\mathtt {gini}}\big (\varvec{H} (\varvec{R})\big )\) and defined by

$$\begin{aligned} \varvec{\mathtt {gini}}\big (\varvec{H}(\varvec{R})\big )= \sum _{i,j=1}^{k} d\big (\varvec{f}_{i}(x), \varvec{f}_{j}(x)\big ) \mathtt {Pr}\left[ \varvec{H}(\varvec{R})=\varvec{f}_{i}(x)\right] \mathtt {Pr}\left[ \varvec{H}(\varvec{R})=\varvec{f}_{j}(x)\right] , \end{aligned}$$
(13)

where d denotes a metric on \(\mathbb {V} \subset \mathbb {R}^n\).

We would like to point out that a measure of central tendency of a distance-based morphological operator yields a vector-valued image. In contrast, a measure of dispersion of a distance-based morphological operator results a gray-scale image. In particular, note that the expectation of either a distance-based dilation or a distance-based erosion corresponds to a weighted average of the elements of \(\varvec{f}(B_x)\). For example, the expectation of \(\varvec{\varepsilon }_{B}^{\varvec{r}}\) is given by the following spatially varying linear filter where \(w(x,y) = \mathtt {Pr}\big [\varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})(x) = \varvec{f}(y)\big ]\) if \(y \in B_x\) and \(w(x,y) = 0\) otherwise:

$$\begin{aligned} \varvec{E}\varvec{\varepsilon }_B(\varvec{f})(x) = \sum _{y \in \mathcal {D}} w(x,y) \varvec{f}(y), \quad \forall x \in \mathcal {D}. \end{aligned}$$

In a similar way, we can compute statistics of the distance-based gradient \(\varvec{\varrho }_{B}^{\varvec{r}}(\varvec{f})(x)\) by interpreting the reference \(\varvec{r}\in \mathbb {V}\) as a sample from the random variable \(\varvec{R}\). In mathematical terms, given a descriptive statistic \(\varvec{\mathcal {S}}\), we define

$$\begin{aligned} \varvec{\mathcal {S}}\varvec{\varrho }_{B}(\varvec{f})(x) = \varvec{\mathcal {S}}\left( \varvec{\varrho }^{\varvec{r}}_{B}(\varvec{f})(x) \right) , \quad \forall x \in \mathcal {D}. \end{aligned}$$
(14)
Fig. 2.
figure 2

Color image \(\varvec{f}\) and the corresponding statistics of distance-based morphological operators. (Color figure online)

Full size image

Example 2

The aim of this example is to illustrate some statistics of distance-based morphological operators. Due to page constraints, let us focus on the distance-based dilation characterized in Example 1. Furthermore, let us assume that the random variable \(\varvec{R}\) is uniformly distributed on \(\mathbb {V} = [0,1]^2\), that is, \(\varvec{R}\sim U(\mathbb {V})\). From the maximum entropy principle, \(\varvec{R}\sim U(\mathbb {V})\) means that we are totally ignorant about the choice of the reference used to define the distance-based morphological operators. Furthermore, when \(\varvec{R}\sim U(\mathbb {V})\), we have \(\mathtt {Pr}[\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x) = \varvec{f}_\ell (x)] = \mu _L(RV_\ell )\), where \(\mu _L(RV_\ell )\) denotes the Lebesgue measure (area, volume or hyper-volume) of the Voronoi region \(RV_\ell \). In this example, \(\mathtt {Pr}[\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x) = \varvec{f}_1(x)] = 0.43\), \(\mathtt {Pr}[\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x) = \varvec{f}_2(x)] = 0.09\), and \(\mathtt {Pr}[\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})(x) = \varvec{f}_3(x)] = 0.48\). Thus, we have

$$ \varvec{E}\varvec{\delta }_{B}(\varvec{f})(x) = 0.43\varvec{f}_1(x) + 0.09\varvec{f}_2(x)+0.48\varvec{f}_3(x) = (0.77,0.66), $$

and

$$\begin{aligned} \varvec{\mathtt {mode}}\varvec{\delta }_{B}(\varvec{f})(x) = \varvec{f}_3(x) = (0.9,0.4). \end{aligned}$$

Note that \(\varvec{E}\varvec{\delta }_{B}(\varvec{f})(x)\) is a weighted average of \(\varvec{f}_1(x)\), \(\varvec{f}_2(x)\), and \(\varvec{f}_3(x)\). Moreover, we have \(\varvec{\mathtt {mode}}\varvec{\delta }_{B}(\varvec{f})(x) = \varvec{f}_3(x)\), which means that \(\varvec{\mathtt {mode}}\varvec{\delta }_{B}(f)\) has no false colors. Similarly, we have

$$ \varvec{\mathtt {std}_g}\varvec{\delta }_{B}(\varvec{f})(x) = 0, \quad \varvec{\mathtt {std}_t}\varvec{\delta }_{B}(\varvec{f})(x) = 0.29, \quad \text{ and } \quad \varvec{\mathtt {gini}}\varvec{\delta }_{B}(\varvec{f})(x) = 0.15. $$

Accordingly, note that \(\varvec{E}\varvec{\delta }_{B}(\varvec{f})(x)\) and \(\varvec{\mathtt {mode}}\varvec{\delta }_{B}(\varvec{f})(x)\) are vectors while \(\varvec{\mathtt {std}_g}\varvec{\delta }_{B}(\varvec{f})(x)\), \(\varvec{\mathtt {std}_t}\varvec{\delta }_{B}(\varvec{f})(x)\), and \(\varvec{\mathtt {gini}}\varvec{\delta }_{B}(\varvec{f})(x)\) are scalars.

Example 3

In this example, we provide a visual interpretation of some statistics of the distance-based morphological operators \(\varvec{\varepsilon }_{B}^{\varvec{r}}\), \(\varvec{\delta }_{B}^{\varvec{r}}\), and \(\overline{\varvec{\varrho }}_{B}^{\varvec{r}}\). To this end, consider the color image \(\varvec{f}\) depicted in Fig. 2(a). By considering the Euclidean distance and assuming \(\varvec{R}\sim U(\mathbb {V}_\mathtt {RGB})\), which means we have no a priori information about the appropriate reference, we obtain the images shown in Fig. 2 using a \(3 \times 3\) square structuring element. For a better visual interpretation, instead of showing a gradient-like image \(g:\mathcal {D} \rightarrow [0,+\infty )\), we depicted the complement of its re-scaled version given by \( (1-\overline{g})(x)= 1-\frac{g(x)}{ \bigvee \left\{ g(y): y \in \mathcal {D}\right\} }\), \(\forall x \in \mathcal {D}\). Note that the statistics of the gradient as well as the measures of dispersion of \(\varvec{\varepsilon }_{B}^{\varvec{r}}(\varvec{f})\) and \(\varvec{\delta }_{B}^{\varvec{r}}(\varvec{f})\) resemble a gradient image. Like the morphological gradient, we can use these operators for edge detection and image segmentation. The following section confirms this claim.

5 Computational Experiment

Edge detection is an important task in many applications including image segmentation and object recognition. Broadly speaking, an edge is the boundary between two regions whose predominated values are significantly different. A gradient, combined with other techniques, can be used for edge detection [5]. In Example 3, we observed that the measures of dispersion of the distance-based morphological operators as well as the measures of central tendency of the distance-based gradient emphasize variations in intensity of a pixel in a neighborhood determined by the structuring element. Thus, we shall apply them empirically for edge detection.

In order to evaluate the performance of edge detectors based on a statistic of a distance-based operator, we used the Berkeley segmentation dataset and benchmark, University of California, Berkeley [16]. Briefly, this dataset has 300 natural color images and 1633 binary images that were manually segmented by a group of individuals. Like Canny’s edge detector [5], given a natural color image \(\varvec{f}:\mathcal {D}\rightarrow \mathbb {V}_{\mathtt {RGB}}\), we obtained a binary image \(\beta \in \mathcal {D}\) by applying the non-maximum suppression (NMS) method and a hysteresis threshold on the gradient-like image \(\varvec{g}\) obtained from an appropriate statistics of a distance-based morphological operator. In our experiments, both NMS and hysteresis have been computed using the command NonMaxSupHyst from GNU Octave using the threshold parameters \(T_1 = 0.01\) and \(T_2 = 0.2\). Also, the Euclidean distance have been used to define the distance-based operators as well as to compute the Gini’s mean difference. Furthermore, we used a \(3 \times 3\) square structuring element S and we assumed \(\varvec{R}\sim U(\mathbb {V}_{\mathtt {RGB}})\), which means we have no a priori information on the reference.

Fig. 3.
figure 3

Boxplot of the FoM values produced by edge detectors.

Full size image

Apart from the statistics of distance-based morphological operators, we also considered some other edge detectors from the literature. Namely, the gray-scale edge detectors of Sobel and Canny obtained using the GNU Octave commands edge and rgb2gray. We also considered the edge detectors obtained by applying non-maximum suppression and hysteresis on the following gradients: The usual Beucher gradient applied on the gray-scale image obtained using the command rgb2gray, the gradients \(\varvec{\varrho }_B^{\mathtt {Marg}}\) and \(\varvec{\varrho }_B^{\mathtt {Lex}}\) obtained using respectively the marginal and lexicographical RGB orderings [3], and the distance-based gradients \(\varvec{\varrho }_{B}^{\mathtt {black}}\) and \(\varvec{\varrho }_{B}^{\mathtt {white}}\) given by (4) with the reference fixed on black and white, respectively [2]. At this point, we would like to recall that some computational experiments using distance-based operators revealed that an achromatic color, such as black or white, has been recommended for an edge detection task if no information on the reference is available [26].

We quantitatively evaluated the performance of an edge detection technique by computing a normalized version of Pratt’s figure of merit (FoM) as follows [18]: Let \(\beta _i \subseteq \mathcal {D}\) be the binary image produced by the ith edge detector and \(\tau \subseteq \mathcal {D}\) be an human segmented binary image, referred to as the ground truth, both with respect to a given color image \(\varvec{f}\). The FoM value and normalized FoM value are given respectively by

$$\begin{aligned} \mathtt {FoM}(\beta _i,\tau ) = \frac{1}{M} \sum _{x \in \tau } \frac{1}{1+\alpha d^2(x,\beta )} \quad \text{ and } \quad \widehat{\mathtt {FoM}}(\beta _i,\tau ) = \frac{\mathtt {FoM}(\beta _i,\tau )-\mu }{\sigma }, \end{aligned}$$
(15)

where \(M=\max \{\mathtt {Card}(\beta ),\mathtt {Card}(\tau )\}\), \(\alpha \) is a parameter, \(d(x,\beta )\) denotes the distance from \(x \in \tau \) to \(\beta \), and \(\mu \) and \(\sigma \) are the average and standard deviation of the FoM values produced by all edge detectors applied on the same image and its corresponding ground truth. The greater the normalized FoM value, the better the performance of the edge detector. In our experiments, we used \(\alpha =1/9\) and the Euclidean distance. Figure 3 shows the boxplot of the normalized FoM values produced by all the edge detectors on the entire dataset, resulting 1633 values for each method. Note that the edge detectors based on \(\varvec{\mathtt {std}_t}\varvec{\varepsilon }_{B}\), \(\varvec{\mathtt {gini}}\varvec{\varepsilon }_{B}\), \(\varvec{\mathtt {std}}\varvec{\varrho }_{B}\), \(\varvec{\varrho }_B^{\mathtt {Marg}}\), \(\varvec{\varrho }_B^{\mathtt {Lex}}\), \(\varvec{\varrho }_B^{\mathtt {black}}\), and \(\varvec{\varrho }_B^{\mathtt {white}}\) yielded positive average normalized FoM values while the edge detectors of Sobel, Canny, and Beucher resulted negative average normalized FoM values. The largest average normalized FoM values has been produced by the edge detectors based on the standard deviation of the gradient (\(\varvec{\mathtt {std}}\varvec{\varrho }_{B}\)), the total standard deviation and Gini’s mean difference of the erosion (\(\varvec{\mathtt {std}_t}\varvec{\varepsilon }_{B}\) and \(\varvec{\mathtt {gini}}\varvec{\varepsilon }_{B}\)). In fact, paired Student’s hypothesis test with confidence level at 99% confirmed that the edge detector based on the standard deviation of the gradient outperformed all the other edge detectors considered in this computational experiment.

6 Concluding Remarks

In the last decades, several researchers have contributed with new approaches to extend mathematical morphology to multivalued images such as color and hyper-spectral images. In this paper, we focused on the distance-based approach whose ordering scheme depends on a single parameter – the reference \(\varvec{r}\in \mathbb {V}\). Precisely, we characterized the operators of erosion, dilation, and gradient as a function of the reference using the diagrams of Voronoi and farthest neighbor.

In order to address uncertainties in the choice of the reference in the distance-based approach, we assumed that the reference is described by a random variable and used descriptive statistics such as measures of central tendency and dispersion to extract useful information on the distance-based morphological operators. For example, we can compute the expectation of distance-based erosions, the mode of distance-based dilations, or the standard deviation of the distance-based gradient, among others. Furthermore, we evaluated the performance of edge detectors based on some statistics of distance-based morphological operators using the image segmentation dataset of the University of California, Berkeley. Using Pratt’s figure of merit (FoM) as a quantitative measure of the performance, we concluded that the edge detector based on the standard deviation of the gradient outperformed other approaches from the literature including the edge detector of Sobel and Canny.

Despite the promising result obtained in edge detection experiment, the statistics of distance-based morphological operators require further interpretation and theoretical background. Moreover, apart from descriptive statistics, we can use other probabilistic measures such as Shannon entropy to extract features or enhance our understanding of a multivalued image. Finally, we believe that the same reasoning can be extended to more general parametrized reduced ordering. Namely, we can assume that the parameters are samples from a random variable and use descriptive statistics or other probabilistic measures to obtain relevant information on the resulting morphological operators.