Matrix-Valued Levelings for Colour Images

Abstract

Morphological levelings represent a useful tool for the decomposition of an image into cartoon and texture components. Moreover, they can be used to construct a morphological scale space. However, the classic construction of levelings is limited to the use of grey scale images, since an ordering of pixel values is required.

In this paper we propose an extension of morphological levelings to colour images. To this end, we consider the formulation of colour images as matrix fields and explore techniques based on the Loewner order for formulating morphological levelings in this setting. Using the matrix-valued colours we study realisations of levelings relying on both the completely discrete construction and the formulation using a partial differential equation. Experimental results confirm the potential of our matrix-based approaches for analysing texture in colour images and for extending the range of applications of levelings in a convenient way to colour image processing.

1 Introduction and Motivation

The analysis of texture in an image is an important task in image processing. It is for instance fundamental for performing the decomposition of an image into cartoon and texture components, and gives useful information for many potential applications like inpainting or segmentation. Among the interesting tools for filtering textures are the morphological levelings. While the concept behind levelings can be traced back to the works [6] (see also [5]) the notion itself was to our knowledge coined by Meyer in [14]. A distinct feature of the morphological levelings is their ability to preserve object boundaries during the filtering, similar to morphological amoebas cf. [11, 18]. This in particular makes them a potentially useful building block for many basic image processing tasks such as image segmentation. The appearance of the levelings triggered further research expanding the knowledge about their theoretical properties and possible applications. Mentioning some milestones, in [15] the corresponding scale space has been studied, and the potential for performing image decompositions and texture analysis tasks has been explored in [13].

Since levelings rely in their original construction on a lattice structure between scales, they inherently depend on the total order relation of grey scale values. When considering the processing of colour images, this is a significant issue since such vector-valued images do not incorporate a natural ordering of the colour information. We refer to [2] for a comprehensive overview on the efforts to rank colour information for morphological processing purposes. Let us also mention the more recent work [7] where frame-theoretical methods are applied to obtain morphological processes for colours, and the paper of Zanoguera and Meyer [20] where non-separable vector levelings are considered.

In this paper we propose and study the extension of morphological levelings to colour images based on their recent formulation in terms of matrix fields introduced in [4, 10]. In this setting, each pixel bears colour information in terms of a symmetric $2 \times 2$ matrix. For such matrix fields the Loewner order can be used to define an ordering of matrices. This can be explored for defining matrix-valued counterparts of morphological filters. Both the fully discrete formulation of dilation/erosion [4, 10] as well as formulations based on partial differential equations (PDEs) of those processes [3] have been proposed in this framework, whereas the median filter and its extensions have recently been the subject of even more extensive investigations [9, 18, 19].

Our Contributions. Relying on the matrix-valued framework for dilation/erosion as developed in [3, 10] we present colour-valued formulations of the morphological levelings. Thereby we especially rely on the discrete leveling formulation via the triphase operator $\varLambda$ as defined in [12], and the PDE-based formulation used for studying scale-space properties in [15]. Both possible approaches are carried over within our framework to colour image processing and are evaluated experimentally. On the technical side, let us note in this context that the definition of the PDE-based colour levelings involves some intricate choices in the discretisation process. We study here a technically different discretisation of matrix-valued derivatives as in [3] as well as two possible implementations of the mechanism that steers application of dilation/erosion in that formulation. Our experiments demonstrate the potential of our approach for texture-related colour image processing tasks.

2 Levelings for Grey-Valued Images

In this section, we briefly review how to define a leveling for a given grey-valued image f and a marker image M. We describe both the fully discrete, complete lattice based construction as well as the continuous-scale PDE-based formulation, see e.g. [13] for a detailed discussion of both approaches.

2.1 Discrete Construction of Levelings

A leveling $\varLambda (M|f)$ is a fixed point of the operator $\lambda (M|f)$ defined by

$$\begin{aligned} \lambda (M|f)=[f\wedge \delta _B(M)]\vee \epsilon _B(M) \end{aligned}$$

(1)

where we have employed the usual notations $\vee$ for the supremum, $\wedge$ the infimum, $\delta _B$ the dilation, and $\epsilon _B$ for erosion, respectively (see for instance [12]). The fixed point is obtained in the limit of the iteration of $\lambda$, i.e. more precisely, by calculating the iteration

$$\begin{aligned} u_{k+1}=\lambda (u_k|f) \end{aligned}$$

(2)

for $k=0,1,2,\ldots$ with $u_0=M$. Hence, $\varLambda (M|f)$ is given by $u_\infty$.

Recalling the definitions of the fundamental operations used in (1), let us note that one needs to consider a structuring element B. In the discrete setting, this is effectively the shape of a window that slides over the pixels in an image and defines the grey values accumulated in the indicated operation. Making use of the structuring element, one can define dilation and erosion in general as

$$\begin{aligned} \delta _B(f)(x):= & {} (f\oplus B)(x):=\sup _{a\in B} f(x-a)\\ \epsilon _B(f)(x):= & {} (f\ominus B)(x):=\inf _{a\in B} f(x-a) \end{aligned}$$

The supremum $\vee$ and infimum $\wedge$ of two images $f_1$ and $f_2$ are defined in a pointwise sense as

$$\begin{aligned} \left( f_1\vee f_2 \right) (x):= & {} \max \left\{ f_1(x),f_2(x)\right\} \\ \left( f_1\wedge f_2 \right) (x):= & {} \min \left\{ f_1(x),f_2(x)\right\} \end{aligned}$$

2.2 PDE-Based Formulation of Levelings

The PDE-based formulation of levelings in a grey valued setting amounts to the following problem formulation over an image domain $\varOmega$, cf. [12]:

(3)

where $(K_{\sigma } *f)(x)$ represents a Gaussian convolution of f with mean $\mu = 0$ and standard deviation $\sigma$ and where $\partial _{n} u(t,x)$ denotes the derivative in outer normal direction along the boundary of our domain.

Let us note that the time t can be understood as the scale parameter in the corresponding scale space. The leveling is obtained as the steady state of the time evolution i.e. formally for $t \rightarrow \infty$. However, let us already note here that in practice integration over relatively small time intervals is sufficient to obtain reasonable results.

For the suitable interpretation of (3) let us remark that the underlying PDEs

$$\begin{aligned} \partial _{t} u(t,x) \, = \, \pm \Vert \nabla u \Vert \end{aligned}$$

(4)

describe scalar-valued dilation ($+$) respectively erosion (−). Thus one can observe that the PDE in (3) includes in addition to (4) the signum function, working as a switch between the dilation/erosion processes.

3 Processing Colour Images

To define a leveling for a colour image consisting of three channels (r, g, b) is not a trivial task. As indicated beforehand this is due to the non-existing total order of colour values. In order to define suitable operations for colour images, we largely rely on the framework developed in several recent works on matrix-valued colour image processing, for details we refer to [10, 19]. We now give a brief account of its building blocks.

3.1 Colour Images and Matrix Fields

We now briefly recall the conversion of (r, g, b) values to matrices, summarising the presentation in [3]. Via this conversion, a given RGB image is transformed in two steps into a matrix field of equal dimensions in which each pixel is assigned a symmetric $2\times 2$ matrix.

To this end, the RGB colours are first transformed to the HCL colour space, assuming that red, green and blue intensities are normalised to [0, 1]. This is a standard procedure, cf. [1]. For a pixel with intensities r, g, b, we obtain its hue h, chroma c and luminance l via $M=\max \{r,g,b\}$, $m=\min \{r,g,b\}$, $c=M-m$, $l=\frac{1}{2}(M+m)$, and $h=\frac{1}{6}(g-b)/M$ modulo 1 if $M=r$, $h=\frac{1}{6}(b-r)/M+\frac{1}{3}$ if $M=g$, $h=\frac{1}{6}(r-g)/M+\frac{2}{3}$ if $M=b$.

Fig. 1.

Colour bi-cone (Color figure online)

After modifying the luminance l as by $\tilde{l}:=2l-1$, and interpreting c, $2\pi h$, and $\tilde{l}$ as radial, angular and axial coordinates of a cylindrical coordinate system, we have a bijection from the (r, g, b) unit cube mapping onto a solid bi-cone, see Fig. 1.

The bi-cone is then transformed into Cartesian coordinates via $x=c\cos (2\pi h)$, $y=c\sin (2\pi h)$, and $z=\tilde{l}$. In a final step, the coordinates (x, y, z) are put as entries into a symmetric matrix $A\in \mathrm {Sym}(2)$ via

$$\begin{aligned} A \; := \; \frac{\sqrt{2}}{2} \begin{pmatrix}z-y &{} x \\ x &{} z+y \end{pmatrix} \end{aligned}$$

(5)

We have thus obtained by (5) a bijection between the RGB colour space and the set of all matrices that correspond to points of the defined solid bi-cone.

3.2 Functions of Matrix-Valued Arguments

For constructing the levelings we need to give a meaning to matrix-valued counterparts of scalar-valued functions $\varphi : \mathbb {R} \rightarrow \mathbb {R}$, such as the signum function. The question arises how such functions operating in a scalar setting can be applied in the matrix-valued framework.

To tackle the issue, let us recall that any matrix $A \in \mathrm {Sym}(2)$ can be written using the decomposition $A=V \text {diag}\left( \lambda _1,\lambda _2 \right) V^\top$, where $V:=(v_1, v_2)$ accumulates the eigenvectors $v_1,v_2$ of A as column vectors and $\lambda _{1,2}$ are the corresponding eigenvalues. Making use of this decomposition, one may define a function $\varphi$ of a matrix A via

$$\begin{aligned} \varphi (A) \; := \; V \text {diag}\left( \varphi (\lambda _1), \varphi (\lambda _2)\right) V^\top \end{aligned}$$

(6)

in terms of its standard scalar representation. For instance with $\varphi (\cdot ):= \mathrm {sgn} (\cdot )$ we thus obtain the signum function of a symmetric matrix.

Let us note that this construction is in accordance to the extension of exponential and logarithm functions to matrices available in the literature. There the extension is based on the Taylor series expansion and boils down to applying the scalar functions at the eigenvalues. For details on the existing techniques see [8].

3.3 The Loewner Order Approach to Mathematical Morphology

As indicated we propose to use the concept developed for morphological colour processing in [4] that relies on the Loewner order. This is a half-order $\preccurlyeq$ for symmetric matrices in which, for two symmetric matrices A and B, it holds $A \preccurlyeq B$ iff $B-A$ is positive semidefinite.

As discussed for instance in [18] in detail, this concept of comparing two matrices can be extended to tuples of matrices. For any such tuple $\mathcal {A}:= \left( A_1, A_2, \ldots , A_k \right)$, all matrices that are upper bounds for $\mathcal {A}$ with respect to the Loewner order form a convex set, which we denote here as $\mathcal {U}$. To distinguish within this set for instance a unique supremum as needed for defining a matrix-valued dilation, an additional ordering relation needs to be applied.

To this end one may compare matrices by their trace $\mathrm {tr}$, so that the supremum of $\mathcal {A}$ can be obtained as the minimal element C of $\mathcal {U}$ such that $\mathrm {tr}(C) \le \mathrm {tr}(X)$ for all matrices $X \in \mathcal {U}$. Note that this is in analogy to the standard definition in calculus that the supremum is the smallest upper bound of a set.

Therefore, the analogon of discrete lattice-based dilation or erosion can be achieved by combining the selection of pixels using a structuring element with the aggregation by the supremum or respective infimum operation as discussed above. At the end, the resulting matrix field is transformed back to a colour image.

4 Levelings for Colour Images

We now describe the setups for colour levelings that we study in this paper. In doing this there is a certain emphasis on the scheme construction for PDE-based levelings as this is technically the most challenging task.

4.1 Component-Wise Approach

The by far easiest approach to realise colour levelings is to apply the previous explanations of grey-valued dilation/erosion and the leveling filtering for each channel separately, and to combine the resulting three filtered channels at the end to obtain a new colour image. We also discuss this possibility for clarifying the advantages of our constructions.

4.2 Construction Based on Discrete Colour Morphology

An important point of this work is to investigate if the approach from [10] can be carried over to work for levelings by applying the matrix-valued colour framework described above within the construction given in (1) and (2).

To this end, for one filtering step with dilation/erosion, the agglomeration is performed in this paper pixelwise either over cross- or block-shaped structuring elements of size $3 \times 3$ as indicated, so that the corresponding supremum/infimum of matrices is computed as mentioned in Sect. 3.3. Let us also note that, as written in (2), the marker image is updated during the iterative procedure.

4.3 Construction of Levelings Based on Colour-Valued PDEs

For our numerical solution strategy to solve the PDE from (3) we need to discretise matrix-valued differential expressions in time and space, and we also need to take care of numerical boundary conditions.

For approximating the temporal derivative we make use of a standard forward difference scheme. In addition we use an adapted Rouy-Tourin discretisation for the spatial gradient. Rouy and Tourin [17] suggested to approximate the derivative $u_{z}$ in a direction z by

$$\begin{aligned} u_{z} \approx \max \left( \max ( D^{-}_{z}u, 0), - \min ( D^{+}_{z}, 0) \right) \end{aligned}$$

(7)

where $D^{+}_{z}$ is the forward difference operator and $D^{-}_{z}$ the backward difference operator in z direction. In our implementation these finite differences are computed component wise on our symmetric matrices.

Let us note that our means to realise the Rouy-Tourin discretisation as in (7) differs from the one given in [3] where a formulation based on computing the supremum/infimum of three matrices is employed. In the scalar setting the formulas are equivalent, but in the matrix-valued setting our approach above is easier to realise than the one from [3].

Similarly the Neumann boundary conditions are enforced by mirroring our data along the boundary in each channel. Following Pizarro et al. [16] we compute these maxima and minima of our matrix-valued data as

$$\begin{aligned} \max (A, B)&= \frac{1}{2} (A + B + \left| A-B\right| )\end{aligned}$$

(8)

$$\begin{aligned} \min (A, B)&= \frac{1}{2} (A + B - \left| A-B\right| ) \end{aligned}$$

(9)

where the absolute value function operates on the eigenvalues of the matrix $A-B$, compare Sect. 3.2. The so obtained spatial derivatives $u_{x}$ and $u_{y}$ will again be symmetric $2\times 2$ matrices. The corresponding computation of the gradient norm is obtained through

$$\begin{aligned} \Vert \nabla u\Vert = \sqrt{ u_{x}^{2} + u_{y}^{2}} \end{aligned}$$

(10)

where the square root applies again to the eigenvalues. Let us remark that $u_{x}^{2}+u_{y}^{2}$ is a symmetric matrix if $u_{x}$ and $u_{y}$ are symmetric matrices.

The sign of $u-f$ can be computed in several possible ways. A straightforward approach would be to apply the signum function to the eigenvalues of the matrices $u-f$ in the style of Sect. 3.2. In that case we must take precautions that the matrix-matrix product between $\mathrm {sgn}(u-f)$ and $\Vert \nabla u\Vert$ remains a symmetric matrix. This could for example be achieved by considering the Jordan matrix product [16]

$$\begin{aligned} A \bullet B = \frac{1}{2} (AB + BA) \end{aligned}$$

(11)

Alternatively, one may consider approaches that yield a scalar value for the sign of a $2\times 2$ matrix. In this latter case the symmetry of the matrices is always preserved. Such an approach could for example be based on the Loewner order. In that case we say that the sign of $u-f$ is 1 if $u\succ f$, $-1$ if $u\prec f$ and 0 else.

5 Experimental Results

In this section, we present several results for constructing levelings for colour images. As a common point of our proceeding, we generally employ test images of relatively low resolution in order to make the effects of the filtering processes obvious.

In what follows, we first demonstrate that the channel-wise approach gives inferior results. After that we aim to clarify differences between the fully discrete and the PDE-based approaches. Furthermore we illustrate the potential of our methods at hand of filtering image patches featuring different types of textures.

5.1 The Channel-Wise Method: False Colours

In this first experiment we apply the component-wise and for comparison the Loewner order approach to the classic test image Peppers, downsampled to resolution $32 \times 32$ which is shown in Fig. 2(a). These two approaches are in some sense comparable directly since they are both different means to realise the iterative leveling construction from (1) and (2).

We employ here a cross-shaped structuring element of size $3\times 3$. The marker images $M_i$ are constructed via 2D Gaussian convolution $G_{\sigma _i}$ of the original image f with standard deviation $\sigma _i=2^{i-1}$, that is $M_i=f*G_{\sigma _i}$ as shown in Fig. 2(b) and (f). The levelings $u_{i}=\varLambda (M_i|u_{i-1})$ with $u_0=f$ are shown in Fig. 2(c) and (g). Additionally we depict the residuals $r_i=f-u_i$ in Fig. 2(d) and (h). For each channel of the colour image $r_i$, we add 0.5 to avoid negative numbers. In Fig. 2(e) we show $u_1-u_2$. Here, we also add 0.5 to each channel.

As we can see, we are easily able to identify levelings by means of the channel-wise approach. One may also observe the desired segmentation-like effect in the output images, and that edges of the original input image stay sharp after leveling construction. This effect is also observable in the (translated) difference image $u_1-u_2$ displayed in Fig. 2(e). Turning to the observable colours, however, we can see even without any comparison to other approaches that the green banana pepper on the left gets an orange-red colour as seen in Fig. 2(c) and (g). This effect is also observable by the relatively prominent green colour in the residual images in Fig. 2(d) and (h). This is an undesirable false colour arising by the missing coupling of channels in this approach.

Let us now evaluate if the Loewner order approach gives in comparison better results. Using the same computational parameters, we obtain the results depicted in Fig. 3. While we obtain qualitatively comparable results, we do not obtain a false colour.

Fig. 2.

Levelings for the component-wise approach. Notice the false colours appearing at the banana pepper in the left half of $u_1$, $u_2$, see especially Fig. 2(g). (Color figure online)

Fig. 3.

Levelings for the discrete Loewner order approach. No false colour appears. (Color figure online)

5.2 Discretisations of the Signum Function

Let us introduce at this point a classic test image that we consider in this paper for the following part of the experimental evaluation, namely the Baboon test image, see Fig. 4.

Fig. 4.

Baboon test image

To be more precise, we focus for better visualisation of filtering effects on small parts of the image featuring different texture characteristics (in a loose sense).

We test at this point the influence of both presented implementations of the signum function. To this end, we denote as Loewner comparison the scalar-valued variant of the sign function where we test at hand of the Loewner order if the argument has uniformly larger or smaller eigenvalues than zero. Consequently, we denote as Jordan product the method following strictly the proceeding of Sect. 3.2 yielding a matrix-valued sign function.

A visualisation of the obtained results for both choices is given in Fig. 5. As computational parameters we employ here a stopping time of $t=1$ as this will turn out to suffice for efficient texture discrimination, and $\sigma =2$. As observable, the Loewner comparison method incorporates a mechanism that tends to sharpen edges at the expense of slight artefacts along them.

Fig. 5.

Results of our PDE implementation for the indicated two different implementations of the sign function. Left: Input image. Middle: Leveling result computed with signum function based on Loewner comparison. Right: Corresponding leveling by Jordan product. As observable, both possible implementations give reasonable results. However, in the Loewner comparison result we observe an enhancement of the strong edges in the image.

Fig. 6.

Zooms into the baboon test image used for the detailed comparison.

Fig. 7.

Comparison of levelings. Left column: Channel-wise approach. Second column: Fully discrete method. Third column: PDE-based with Loewner comparison. Right column: PDE-based with Jordan product.

5.3 Comparison of All Methods

At hand of three distinct parts of the Baboon test image, see Fig. 6, we now give a detailed comparison of all the introduced methods – channel-wise, fully discrete, PDE-based using Loewner comparison and Jordan product – that complements and extends the previous tests.

Let us comment on the leveling results. Here in this first test we stay with our marker images relatively close to the original ones, using $\sigma =1$. For the component-wise approach there are no highly prominent false colours in this test. The fully discrete approach works basically as expected, yet one may notice a slight darkening of some colours. For the PDE-based methods we take here the stopping time $t=1$ as this yields already reasonable results. We observe in the PDE-based levelings a more prominent smoothing effect that might be due to a numerical artefact introduced by the Rouy-Tourin discretisation (which is inherently of first order), but the luminance of colours appears to be preserved (Fig. 7).

5.4 Texture Discrimination

We now turn our attention to the potential for texture filtering of the new leveling methods. To this end we consider difference images, subtracting the RGB valued filtering result from the input image. The so-obtained difference image is shifted pixelwise by 127.5 in each channel.

In Fig. 8 we present the results of this step. The test was performed with the same input images, this time employing Gaussian convolution with $\sigma =2$ in order to complement previous experiments.

We observe that already the channel-wise approach seems to be able to filter the texture. Due to the near absence of false colours in this experiment the result is actually better here than with the fully discrete, Loewner-based method, where the observed change in luminance accounts for areas with large contributions in the difference images. This may be a problem for automatic processing of the results. The, to our impression, most convincing results are delivered by the PDE-based methods, as structures related to texture can clearly be identified.

Fig. 8.

Comparison of levelings. Left column: Channel-wise approach. Second column: Fully discrete method. Third column: PDE-based with Loewner comparison. Right column: PDE-based with Jordan product.

6 Conclusion

Constructing levelings for colour images is not an easy task. The simplest approach to process each channel of the colour image separately may lead to false colours. The discrete approach based on the method in [10] may introduce a change in the luminance of colours which may be an undesirable property in an application. The PDE-based approach based on Jordan product seems to yield the best results among the tested methods and deserves a more detailed analysis in future work.