Ordering and Multispectral Morphological Image Processing

as arranging the elements of in a line. Not surprisingly, the task of defining a total order for a given set depends greatly on the prior knowledge provided. To illustrate this point, imagine a scenario where two researchers want to order a set of people. The first one defines minimum as the youngest person and the maximum as the oldest person, the second declares the minimum as the fattest one and the maximum as the thinnest one. Clearly, two persons that are similar according to the first researcher’s setting might be dissimilar according to the second’s. Accordingly, the complete list of ordered people can be totally different from one researcher to another.In the field of image processing, the definition of a total ordering among pixels of the image is the main ingredient of mathematical morphology techniques [20]. In this first part of this chapter, we study the case where “prior” knowledge about the spectral information of the background and the foreground on the image is available. We define a supervised ordering as a particular case of reduced ordering where the minimum (resp. maximum) value should be a pixel in the background (resp. foreground). This restriction can be included in the computation of the supervised ordering by using classical machine learning techniques, for instance, by support vector machines (SVM) [25]. Another possibility for known structure in the total ordering problem is to assume that the image is composed by two main components: background and foreground. Additionally, we include the assumption that the background is larger than the foreground. We uncover an interesting application of randomised approximation schemes in multivariate analysis [26]. To summarise, in this chapter a multispectral image is represented through a total ordering and it is analysed by mathematical morphology transformations. Prior information about the spectral information in the image is incorporated into the workflow of mathematical morphology transformations in two scenarios:

Spectral information about the background and the object of interest are available, i.e., “background/foreground training pixels”.

Image can be considered as objects (foreground) over a majority background.

The remainder of this chapter is organised as follows. In Sect. 2, we present the fundamental definitions of mathematical morphology in a lattice formulation. The approach involving a preordering function is presented in Sect. 3. This section also contain examples specialising the general approach to more specific settings. Section 4 explains, implementation issues for any adjunction based morphological transformation. Finally, Sect. 5 concludes the chapter.

2 Complete Lattices and Mathematical Morphology

2.1 Mathematical Morphology

Basically, there are two points of view about mathematical morphological transformations: (1) connection based and (2) adjunction based. The first strategy deals with simplification of a given image in the partition space induced by its connected components [17, 18, 21]. The second perspective analyses an image by composition of two basic transformations, dilation and erosion, which form a Galois connection [9]. In this section we provide the theoretical background of mathematical morphology in its formulation based on adjunction, i.e. by using dilation/erosion operators. Our approach does not include the “connectivity approach”. We refer keen readers to [21] for a comprehensive review of connective morphology.

Fig. 1

Notation for a $$d$$

-variate image, ${\mathbf {I}}: {\mathtt {E}}\rightarrow {\mathbb {F}}$ . Note that the image ${\mathbf {I}}$ maps each spatial point $$x$$

to a vector ${\mathbf {x}}$ in three dimension for a RGB image or in dimension $$d$$

for the case of a multispectral image

2.2 Fundamental Definitions

Let us introduce the notation for a multidimensional image, as it is illustrated in Fig. 1, where the object of interest is a $$d$$

-dimensional image (denoted by ${\mathbf {I}}$ ) which maps the spatial support ${\mathtt {E}}$ to the vector support ${\mathbb {F}}$ , i.e.,

$\begin{aligned} {\mathbf {I}}: \quad&{\mathtt {E}}\quad \rightarrow \quad {\mathbb {F}}={\mathbb {R}}^{d}\\&x\quad \rightarrow \quad {\mathbf {x}}\end{aligned}$

Given a vector image ${\mathbf {I}}\in {\fancyscript{F}}({\mathtt {E}},{\mathbb {F}})$ , i.e. is a mapping from the spatial support to the vector space of dimensions $$d$$

. Theoretical formulation of mathematical morphology is nowadays phrased in terms of complete lattices and operators defined on them. For a detailed exposition on complete lattice theory in mathematical morphology, we refer to J. Serra and C. Ronse in [16, Chap. 2].

Definition 1

(Complete Lattice) A space ${\fancyscript{L}}$ endowed with a partial order $\le$ is called a complete lattice, denoted $({\fancyscript{L}},\le )$ if every subset ${\fancyscript{M}}\subseteq {\fancyscript{L}}$ has both supremum (join) $\bigvee {\fancyscript{M}}$ and infimum (meet) $\bigwedge {\fancyscript{M}}$ .

A minimum (or least) $\bot \in {\fancyscript{M}}$ is an element which is least than or equal to any other element of ${\fancyscript{M}}$ , that is, $r\in {\fancyscript{M}}\Rightarrow \bot \le r$ . We denote the minimum of ${\fancyscript{L}}$ by ${\mathbf {\bot }}$ . Equivalently, a maximum (largest) $\top$ in ${\fancyscript{M}}$ is the greatest element of ${\fancyscript{M}}$ , that is, $r\in {\fancyscript{M}}\Rightarrow r\le \top$ . We denote the maximum of ${\fancyscript{L}}$ by ${\mathbf {\top }}$ .

Definition 2

(Dilation/Erosion) A mapping $f:{\fancyscript{L}}_1 \rightarrow {\fancyscript{L}}_2$ of a complete lattice ${\fancyscript{L}}_1$ into a complete lattice ${\fancyscript{L}}_2$ is said to be a dilation if $f(\vee _{j\in J} r_{j})= \vee _{j \in J} f(r_j)$ for all families $(r_j)_{j \in J}$ of elements in ${\fancyscript{L}}_1$ . A mapping is said to be an erosion if $f(\wedge _{j \in J} r_j) = \wedge _{j \in J} f(r_j)$ for all families $(r_j)_{j \in J}$ of elements in ${\fancyscript{L}}_1$ .

The important relationship between dilation and erosion is that they are dual concepts from the lattice point of view. [9] showed that for any complete lattice ${\fancyscript{L}}$ , we always have a dual isomorphism between the complete lattice of dilation on ${\fancyscript{L}}$ and the complete lattice of erosions on ${\fancyscript{L}}$ . This dual isomorphism is called by Serra [20, Chap. 1] the morphological duality. In fact it is linked to what one calls Galois connections in lattice theory, as we will see at the end of this section.

Definition 3

(Adjunction) Let $\delta ,\varepsilon \in {\fancyscript{L}}\rightarrow {\fancyscript{L}}$ . Then we say that $(\varepsilon ,\delta )$ is an adjunction of every $r,s\in {\fancyscript{L}}$ , we have

$\begin{aligned} \delta (r) \le s\iff r\le \varepsilon (s) \end{aligned}$

(1)

In an adjunction $(\varepsilon ,\delta )$ , $\varepsilon$ is called the upper adjoint and $\delta$ the lower adjoint.

Proposition 1

[9, p. 264] Let $\delta ,\varepsilon \in {\fancyscript{L}}\rightarrow {\fancyscript{L}}$ . If $(\varepsilon ,\delta )$ is an adjunction, then $\delta$ is a dilation and $\varepsilon$ is an erosion.

Definition 4

(Galois connection) Let ${\fancyscript{L}}_1$ and ${\fancyscript{L}}_2$ be lattices and let $\alpha : {\fancyscript{L}}_1 \rightarrow {\fancyscript{L}}_2$ and $\beta : {\fancyscript{L}}_2 \rightarrow {\fancyscript{L}}1$ satisfy the following conditions.

For $r,s\in {\fancyscript{L}}_1,$ if $r\le s$ , then $\alpha (s) \le \alpha (r)$ .

For $r,s\in {\fancyscript{L}}_1,$ if $r\le s$ , then $\beta (s) \le \beta (r)$ .

For $r\in {\fancyscript{L}}_1$ , $\beta \alpha (r) \le r$ .

For $r\in {\fancyscript{L}}_2$ , $\alpha \beta (r) \le r$ .

Then $(\alpha ,\beta )$ is a Galois connection between ${\fancyscript{L}}_1$ and ${\fancyscript{L}}_2$ .

Proposition 2

Let the lattices ${\fancyscript{L}}_1$ and ${\fancyscript{L}}_2$ , maps $\alpha : {\fancyscript{L}}_1 \rightarrow {\fancyscript{L}}_2$ and $\beta : {\fancyscript{L}}_2 \rightarrow {\fancyscript{L}}_1$ a Galois connection. Then the following condition holds for all $r\in {\fancyscript{L}}_1$ and $s\in {\fancyscript{L}}_2$ :

$\begin{aligned} s\le \alpha (r) \iff r\le \beta (s) \end{aligned}$

(2)

Clearly an adjunction in ${\fancyscript{L}}$ is a Galois connection between the dual $({\fancyscript{L}},\ge )$ and $({\fancyscript{L}},\le )$ (indeed, compare Definition 3 and Proposition 2).

At this point, we can see that definition of erosion/dilation on a image requires a complete lattice structure, i.e., a total ordering¹ among the pixels to be analysed. However, there is not difficult to see that the idea of order is entirely absent from multivariate scene, i.e., there is no unambiguous means of defining the minimum and maximum values between two vectors of more than one dimension. Accordingly, the extension of mathematical morphology to vector spaces, for instance, colour/multi/hyper/ultraspectral images, is neither direct nor trivial because the pixels in the images are vectors. We refer keen readers to [1, 2] for a comprehensive review of vector morphology.

2.3 Preorder by -Function

Let ${\mathtt {E}}$ be a nonempty set and assume that ${\fancyscript{L}}$ is a complete lattice. Let $h: {\mathtt {E}}\rightarrow {\fancyscript{L}}$ be a surjective mapping. Define an equivalence relation $=_{h}$ on ${\mathtt {E}}$ as follows: $x=_{h} y\Leftrightarrow$ $h(x) = h(y) \quad \forall x,y\in {\mathtt {E}}$ . As it was defined in [8], we refer by $\le _h$ the $$h-$$

ordering given by the following relation on ${\mathtt {E}}$

$\begin{aligned} \forall x,y\in {\mathtt {E}}, \quad x\le _h y\Leftrightarrow h(x) \le h(y) \end{aligned}$

Note that $\le _h$ preserves reflexivity ( $x\le _h x$ ) and transitivity ( $x_1 \le _h x_2$ and $x_2 \le _h x_3 \Rightarrow x_1 \le _h x_3$ ). However, $\le _h$ is not a partial ordering because $x\le _h y$ and $y\le _h x$ implies only that $$x=_h y$$

but not

. Note that $$h$$

-ordering is a preorder in ${\mathtt {E}}$ .

An operator $\psi : {\mathtt {E}}\rightarrow {\mathtt {E}}$ is $$h-$$

increasing if $x\le _h y$ implies that $\psi (x) \le _h \psi (y)$ . Additionally, since $$h$$

is surjective, an equivalence class is defined by ${\fancyscript{L}}[r]=\{y\in {\mathtt {E}}| h(y) = r\}$ . The Axiom of Choice [8] implies that there exist mappings $h^{\leftarrow }: {\fancyscript{L}}\rightarrow {\mathtt {E}}$ such that $h h^{\leftarrow }(r)= r$ , for $r\in {\fancyscript{L}}$ . Unless $$h$$

is injective, there exist more than one such $h^{\leftarrow }$ mappings: $h^{\leftarrow }$ is called the semi-inverse of $$h$$

. Note that $h^{\leftarrow } h$ is not the identity mapping in general (but $h^{\leftarrow } h =_{h} \text {id}$ ). However, we have that for any $$h-$$

increasing $\psi : {\mathtt {E}}\rightarrow {\mathtt {E}}$ the result $\psi h^{\leftarrow } h =_{h} \psi$ and hence $h \psi h^{\leftarrow } h = h \psi$ . Let us introduce $\widetilde{\psi }$ the operator associated to $\psi$ in the lattice ${\fancyscript{L}}$ . A mapping $\psi : {\mathtt {E}}\rightarrow {\mathtt {E}}$ is $$h-$$

increasing if and only if there exists an increasing mapping $\widetilde{\psi }: {\fancyscript{L}}\rightarrow {\fancyscript{L}}$ such that $\widetilde{\psi }h = h \psi$ . The mapping $\widetilde{\psi }$ is uniquely determined by $\psi$ and can be computed from

$\begin{aligned} \widetilde{\psi } = h \psi h^{\leftarrow } \end{aligned}$

We can now define the $$h-$$

erosion and $$h-$$

dilation. Let $\varepsilon , \delta : {\mathtt {E}}\rightarrow {\mathtt {E}}$ be two mappings with the property

$\begin{aligned} \delta (x) \le _h y\Leftrightarrow x\le _h \varepsilon (y), \quad \forall x,y\in {\mathtt {E}}\end{aligned}$

then the pair $(\varepsilon , \delta )$ is called an $$h-$$

adjunction. Moreover, let $(\varepsilon ,\delta )$ be $$h-$$

increasing mappings on ${\mathtt {E}}$ , and let $\varepsilon \mapsto ^{h} \widetilde{\varepsilon }$ , $\delta \mapsto ^{h} \widetilde{\delta }$ . Then $(\varepsilon ,\delta )$ is an $$h-$$

adjunction on ${\mathtt {E}}$ if and only if $(\widetilde{\varepsilon }, \widetilde{\delta })$ is an adjunction on the lattice ${\fancyscript{L}}$ . Therefore a mapping $\delta$ (resp. $\varepsilon$ ) on ${\mathtt {E}}$ is called $$h-$$

dilation (resp. $$h-$$

erosion) if $\widetilde{\delta }$ (resp. $\widetilde{\varepsilon }$ ) is a dilation (resp. erosion) on ${\fancyscript{L}}$ . $$h-$$

adjunctions inherit a large number of properties from ordinary adjunctions between complete lattices. Assume that $(\varepsilon , \delta )$ is an $$h-$$