Vector-Valued Image Processing by Parallel Level Sets

Vector-valued images such as RGB color images or multimodal medical images show a strong interchannel correlation, which is not exploited by most image processing tools. We propose a new notion of treating vector-valued images which is based on the angle between the spatial gradients of their channels. Through minimizing a cost functional that penalizes large angles, images with parallel level sets can be obtained. After formally introducing this idea and the corresponding cost functionals, we discuss their Gâteaux derivatives that lead to a diffusion-like gradient descent scheme. We illustrate the properties of this cost functional by several examples in denoising and demosaicking of RGB color images. They show that parallel level sets are a suitable concept for color image enhancement. Demosaicking with parallel level sets gives visually perfect results for low noise levels. Furthermore, the proposed functional yields sharper images than the other approaches in comparison.

SECTION I. Introduction

There are many imaging applications where more than one piece of information is given at one single point in space. A well known example is an RGB color image where at any point three numbers are given which encode the amount of red, green and blue color. On the one hand you can think of an RGB image as three scalar-valued images or you can think of it as a single vector-valued image. Another example is given in medical imaging where different scanners measure different properties for the same spatial point—for instance a computed tomography (CT) scanner measures the absorption of X-rays by the body or a magnetic resonance tomography (MR) scanner can measure the response of water molecules to a magnetic field. Beside these a positron emission tomography (PET) or a single photon emission computed tomography (SPECT) scanner can obtain functional properties like blood flow or metabolic activity. Modern scanners, like SPECT/CT or PET/MR, combine these in one device and can obtain so a vector-valued image where the different channels of the vector correspond to different properties of the tissue [1], [2].

In such cases the channels can be but do not have to be correlated. Fig. 1 shows the color channels of the test image “pyramid.” It is clearly visible that the objects in this figure are encoded in all three colors. The correlation of the color channels especially for the edges in natural images was also observed by [3]. “All three channels are very likely to have the same texture and edge locations.” Likewise, in medical imaging the channels of a PET/MR scanner are likely to be correlated as different tissue types have properties that are interdependent. This dependency is what we want to exploit in this paper.

Fig. 1. The image “pyramid” and its color channels. The main structures of the image are visible on all channels.

Most image processing tools are designed for scalar-valued images or when applied to vector-valued images they process these independently channel by channel, which fails to exploit the information expressed in the correlation between channels. One prominent example of using information between channels is color total variation [4]. This extension of the scalar-valued version [5] leads to a non-linear diffusion scheme where the diffusivity depends on all channels. This approach is extended by [6] where several variational methods in image processing of vector-valued images are combined using the concept of Polyakov action which yields the so called Nambu functional. An approach to vector-valued diffusion based on statistical correlation, but still channel-wise was developed in [7]. In this paper we propose a new approach emphasising the geometric correlation between channels by considering the degree of parallelism between the level sets of each channel.

In our approach we assume that the components of the vector-valued image are not independent. Therefore, we try to align their gradients which leads to parallel level sets and hence to similar structures. We will see that this approach of enhancing common structures can be used in image processing applications like denoising or demosaicking of color images [3], [8].

We distinguish this usage of the term “level sets” from its usage in applications that evolve a $(N+1)$ dimensional function such that its zero-level-set describes the evolution and topological change in the boundary between two or more objects in an image, for example for segmentation [9], [10].

The rest of this paper is organized as follows. First of all, we give a brief overview about variational approaches in image processing and discuss diffusion equations which naturally arise from gradient based cost functionals. In Section II we introduce the basic concepts how to handle parallel level sets and propose a variational approach to obtain these. Its Gâteaux derivative is then computed in Section III. Finally, in Section IV we present a simple example which illustrates the behaviour of the levels sets and their trend towards parallelism. Moreover, we present results of denoising and demosaicking of color images and compare it to other approaches used for image enhancement. Conclusions and discussions are presented in Section V.

A. Overview

As in the case of scalar-valued images, problems such as denoising, inpainting, demosaicking, or deblurring for vector-valued images can be cast into the form of an inverse problem by seeking a minimum of the functional

$$\Phi (z)\buildrel{\rm def}\over{=}{{1}\over{2}}\left\Vert Az-g\right\Vert^{2}+\alpha{\cal R}(z)\eqno{\hbox{(1)}}$$ where $g$ is the observed data, $z=(z_{k})_{k=1,\ldots, K}:\Omega\subset\BBR^{N}\rightarrow\BBR^{K}$ the vector-valued image, ${\cal R}$ a cost functional and $\alpha$ the trade-off parameter between fidelity of the data fit and a-priori information of the solution.

As we will show in Section III, for some choices of ${\cal R}$, a solution of (1) is the stationary point (in time) of the partial differential equation (PDE)

$$\partial_{t}\Phi=-D\Phi_{z}=-A^{\ast}(Az-g)+\alpha\mathop{\rm div}[{\cal K}\nabla z]\eqno{\hbox{(2)}}$$ where the diffusivity ${\cal K}$ is in general a spatially varying $N\cdot K\times N\cdot K$ matrix depending on the image $z$, i.e., $${\cal K}=\left(\matrix{{\cal K}_{1}&{\cal T}_{1,2}&\ldots&{\cal T}_{1,K}\cr{\cal T}_{2,1}&\ddots &\ddots &\vdots\cr\vdots &\ddots &\ddots &{\cal T}_{K-1,K}\cr{\cal T}_{K,1}&\ldots &{\cal T}_{K,K-1}&{\cal K}_{K}}\right),$$ and the divergence and gradient are defined component-wise. Furthermore, we call the $N\times N$ sub-matrices ${\cal K}_{i}$ within-channel diffusivities and the ${\cal T}_{i,j}$ are called cross-diffusivities. If any of the sub-matrices is of the form $c\cdot I$ where $c$ is a scalar and $I$ the identity matrix we denote the whole matrix $c$ as well. The special case when all sub-matrices are multiples of the identity matrix is called isotropic, otherwise anisotropic. In this paper all diffusion equations will be isotropic. We need to distinguish two other special cases. If the sub-matrices ${\cal K}_{i}$, ${\cal T}_{i,j}$ depend on the image itself, i.e., ${\cal K}_{i}={\cal K}_{i}(z)$, ${\cal T}_{i,j}={\cal T}_{i,j}(z)$, we call this non-linear diffusion, otherwise linear. Again, all diffusion equations considered in this paper will be non-linear. Finally, if any cross-diffusivity ${\cal T}_{i,j}$ is non-zero we call it cross-channel diffusion, otherwise channel-wise diffusion. This will be a key point later on. Important to note is, that even when the diffusion is just channel-wise, the system of PDEs can be coupled if the diffusivities ${\cal K}_{i}$ depend on other channels $j\ne i$.

As mentioned above, the idea in this paper is to consider a particular form of isotropic, non-linear, cross-channel diffusion, in which the penalty term ${\cal R}(z)$ is designed to align the components of $z$ such that their level sets are parallel. We make precise our meaning of parallelism for level sets in Section II.

SECTION II. Modelling a Variational Approach to Enforce Parallel Level Sets

A. Parallel Level Sets

Consider vector-valued images $z=(z_{k})_{k=1,\ldots, K}$ which are defined without loss of generality on the unit cube $\Omega\buildrel{\rm def}\over{=}[{0, 1}]^{N}\subset\BBR^{N}$, that is we have $z:\Omega\rightarrow\BBR^{K}$ and $z_{k}:\Omega\rightarrow\BBR$. Moreover, we have to assume that the channels $z_{k}$ are continuously differentiable, i.e., $z_{k}\in C^{1}(\Omega)$. It is well known that the gradient $\nabla z_{k}$ is orthogonal in each point to the level sets $\left\{x\in\Omega: z_{k}(x)={\rm const}\right\}$.

We now restrict ourselves to the case of two channels, i.e., $K=2$. To simplify the notation we denote the two channels of $z$ by $u$ and $v$. We say that the level sets of $u$ and $v$ are parallel if the gradients $\nabla u(x)$ and $\nabla v(x)$ are parallel at each point $x\in\Omega$, i.e., $\nabla u(x)=s(x)\nabla v(x)$ or $\nabla v(x)=s(x)\nabla u(x)$ for some scalar $s(x)\in\BBR$.

It is common knowledge that

$$\eqalignno{\vert\left\langle\nabla u(x),\nabla v(x)\right\rangle\vert=&\,\vert\cos (\theta(x))\vert\left\Vert\nabla u(x)\right\Vert\left\Vert\nabla v(x)\right\Vert\cr\leq &\,\left\Vert\nabla u(x)\right\Vert\left\Vert\nabla v(x)\right\Vert,}$$ and equality if and only if $\nabla u(x)$ and $\nabla v(x)$ are parallel. The brackets $\left\langle\cdot,\cdot\right\rangle$ denote the Euclidean scalar product and $\left\Vert\cdot\right\Vert$ the Euclidean norm in $\BBR^{N}$. Hence the measure $$\left\Vert\nabla u(x)\right\Vert\left\Vert\nabla v(x)\right\Vert-\vert\left\langle\nabla u(x),\nabla v(x)\right\rangle\vert\eqno{\hbox{(3)}}$$ is non-negative and measures locally how far from parallelism we are. The same holds true if strictly increasing functions $\varphi$, $\psi$ are used and we define a general local measure $f(\nabla u(x),\nabla v(x))$ by $$\varphi (\psi [\left\Vert\nabla u(x)\right\Vert\left\Vert\nabla v(x)\right\Vert]-\psi [\vert\left\langle\nabla u(x),\nabla v(x)\right\rangle\vert]).\eqno{\hbox{(4)}}$$ Valid choices for $\varphi$ and $\psi$ are for instance $s\mapsto s$, $s^{2}$, $\sqrt s$, $\log (s)$, $\exp (s)$.

To obtain a global measure we integrate over the whole domain, i.e.,

$${\cal R}(u, v)\buildrel{\rm def}\over{=}\int_{\Omega}f(\nabla u(x),\nabla v(x))\;{\rm d}x.\eqno{\hbox{(5)}}$$ In the special case $\varphi (s)=\sqrt{s}$ and $\psi [s]=s^{2}$ (4) is equivalent to the magnitude of the vector product $\vert\nabla u(x)\times\nabla v(x)\vert=\vert\sin (\theta (x))\vert$. Then (5) corresponds to the Nambu functional [6] with the tensor of [11]. It is also used for joint reconstruction of multi-physics [12], [13].

The proposed model is minimized when the gradients are parallel or zero. Therefore we implicitly penalize non-zero gradients as well. Another choice to measure parallelism of level sets would be to normalize (4) by the norm of the gradients. This measure is more natural as the level sets do not depend on the magnitudes of the gradients but bears two disadvantages. First, we would need to assume that the gradients do not vanish or need to find a solution in this case. Second, our numerical experiments have shown that a normalized version leads to instabilities as gradients of arbitrary magnitude are equally likely solutions. The normalized version with the choices $\varphi (s)=\sqrt{s}$ and $\psi [s]=s^{2}$ is known as normalized gradient field and serves as a distance measure in registration of medical images from different modalities [14].

B. Arbitrary Vector-Valued Images

As we have seen the stated approach is made for just two channels. One way to extend this approach to arbitrary dimensional vector-valued images is to define the functional pairwise, i.e., for any image $z:\Omega\rightarrow\BBR^{K}$ we define

$${\cal R}(z)\buildrel{\rm def}\over{=}\sum_{k<l}{\cal R}(z_{k}, z_{l}).\eqno{\hbox{(6)}}$$ where the summation is only required for $k<l$ due to the symmetry of the arguments of ${\cal R}(z_{k}, z_{l})$.

SECTION III. Gâteaux Derivatives

This section is dedicated to the Gâteaux derivatives [15, p. 135] of the functional ${\cal R}$ which is the key for derivation of a suitable minimization scheme. We will derive those from a very general Proposition.

If we fix $v$ our proposed functional (and many others) can be written as ${\cal R}(u)\buildrel{\rm def}\over{=}\int_{\Omega}f(\nabla u(x))\,{\rm d}x=\int_{\Omega}f(\nabla u)\,{\rm d}x$. From here onwards we skip the argument $x$ to simplify the notation.

Proposition 3.1:

Let $f:\BBR^{N}\rightarrow\BBR$ be a twice continuously differentiable function. Then the Gâteaux derivative of ${\cal R}: C^{1}(\Omega)\rightarrow\BBR$, ${\cal R}(u)=\int_{\Omega}f(\nabla u)\,{\rm d}x$ at $u\in C^{1}(\Omega)$ is given by $D{\cal R}_{u}: C^{1}(\Omega)\rightarrow\BBR$ with

$$D{\cal R}_{u}(h)=-\int_{\Omega}h\mathop{\rm div}[\nabla f(\nabla u)]\;{\rm d}x+\int_{\partial\Omega}h\left\langle\nabla f(\nabla u), n\right\rangle{\rm d}x$$ where $n$ is the outer normal vector of $\Omega$.

Proof:

Let $h\in C^{1}(\Omega)$ be any function and $\varepsilon>0$. If we treat $f(u+\varepsilon h)$ as a function in $\varepsilon$ we derive

$$\eqalignno{{\cal R}(u+\varepsilon h)=&\,\int_{\Omega}f(\nabla u+\varepsilon\nabla h){\rm d}x\cr=&\,\int_{\Omega}f(\nabla u)+\varepsilon\left\langle\nabla f(\nabla u),\nabla h\right\rangle{\rm d}x+{\cal O}(\varepsilon^{2})}$$ by exploiting the Taylor expansion around zero [16, p. 67]. Using the definition of the Gâteaux derivative [15, p. 135] and Green's first identity [17, p. 534] we finally get $$\eqalignno{D{\cal R}_{u}(h)\buildrel{\rm def}\over{=}&\lim_{\varepsilon\rightarrow0}{{1}\over{\varepsilon}}\left\{{\cal R}(u+\varepsilon h)-{\cal R}(u)\right\}\cr=&\,\lim_{\varepsilon\rightarrow 0}{{1}\over{\varepsilon}}\Biggl\{\int_{\Omega}f(\nabla u)+\varepsilon\left\langle\nabla f(\nabla u),\nabla h\right\rangle\cr\noalign{\vskip -3pt}&\qquad\qquad-f(\nabla u){\rm d}x+{\cal O}(\varepsilon^{2})\Biggr\}\cr\noalign{\vskip-3pt}=&\,\int_{\Omega}\left\langle\nabla f(\nabla u),\nabla h\right\rangle{\rm d}x\cr\noalign{\vskip -3pt}=&\,-\int_{\Omega}h\mathop{\rm div}[\nabla f(\nabla u)]{\rm d}x+\int_{\partial\Omega}h\left\langle\nabla f(\nabla u), n\right\rangle{\rm d}x.}$$ $\blackboxfill$

We note that the assumption that $f$ is twice continuously differentiable is sufficient but may not be necessary.

To obtain the Gâteaux derivative of the proposed method we have to approximate the Euclidean norm smoothly. For a parameter $\beta>0$ we define a smooth approximation of the Euclidean norm of a vector $x$ as $\Vert x\Vert_{\beta}\buildrel{\rm def}\over{=}\sqrt{\left\Vert x\right\Vert^{2}+\beta^{2}}$. This also makes the method more robust as small gradients, i.e., $\left\Vert\nabla u\right\Vert\ll\beta$, are treated like zero gradients. Then the function $f$ given by (4) becomes

$$f(\nabla u,\nabla v)\buildrel{\rm def}\over{=}\varphi(\psi [\Vert\nabla u\Vert_{\beta}\Vert\nabla v\Vert_{\beta}]-\psi [\vert\left\langle\nabla u,\nabla v\right\rangle\vert_{\beta^{2}}]).\eqno{\hbox{(7)}}$$

Lemma 3.2:

Let $\varphi$, $\psi$ be continuously differentiable functions. For fixed $\nabla v$ the gradient of $f:\BBR^{N}\rightarrow\BBR$ defined by (7) at $\nabla u$ is given by

$$\nabla f(\nabla u)=\kappa (u,v)\nabla u+\tau (u,v)\nabla v$$ with coefficients $$\eqalignno{\kappa (u,v)\buildrel{\rm def}\over{=}&{{\psi^{\prime}\left[\Vert\nabla u\Vert_{\beta}\Vert\nabla v\Vert_{\beta}\right]\Vert\nabla v\Vert_{\beta}}\over{\Vert\nabla u\Vert_{\beta}}}\rho (u, v)\cr\tau (u,v)\buildrel{\rm def}\over{=}&-{{\psi^{\prime}\left[\vert\left\langle\nabla u,\nabla v\right\rangle\vert_{\beta^{2}}\right]\left\langle\nabla u,\nabla v\right\rangle}\over{\vert\left\langle\nabla u,\nabla v\right\rangle\vert_{\beta^{2}}}}\rho (u, v)\cr\rho(u,v)\buildrel{\rm def}\over{=}&\varphi^{\prime}\left(\psi\left[\Vert\nabla u\Vert_{\beta}\Vert\nabla v\Vert_{\beta}\right]-\psi\left[\vert\left\langle\nabla u,\nabla v\right\rangle\vert_{\beta^{2}}\right]\right).&{\hbox{(8)}}}$$

Proof:

These results can be easily obtained by using the multi-dimensional chain rule [16, p. 51]. $\blackboxfill$

As the functional ${\cal R}$ is symmetric in its arguments we can extend these results to obtain the Gâteaux derivative in the joint argument $(u,v)$. From here onwards (also in the numerical experiments) we will assume that our images have vanishing normal derivatives at the boundary and denote this by $C^{1}_{\ast}(\Omega)$, i.e., $u\in C^{1}_{\ast}(\Omega)$ if and only if it is continuously differentiable with vanishing normal derivative at the boundary of $\Omega$.

Theorem 3.3:

The Gâteaux derivative of ${\cal R}: C^{1}_{\ast}(\Omega)\times C^{1}_{\ast}(\Omega)\rightarrow\BBR$ given by (5) at $(u,v)$ is given by

$$D{\cal R}_{(u,v)}=-\mathop{\rm div}\left[\left(\matrix{\kappa (u,v) &\tau (u,v)\cr\tau (u,v) &\kappa (v,u)}\right)\nabla\left(\matrix{u\cr v}\right)\right]\eqno{\hbox{(9)}}$$ where the diffusivities $\kappa$ and cross-diffusivities $\tau$ are defined in (9).

It is important to note that taking the divergence, gradient and matrix-vector product are defined channel-wise.

Proof:

As the functional ${\cal R}$ is symmetric in its arguments Lemma 3.2 is valid for $v$ as well. The stated result is then obtained by using Proposition 3.1 and writing those equations in a vector format. The boundary term is zero because of the vanishing normal derivatives. $\blackboxfill$

It is straightforward to extend Theorem 3.3 for the three (or even arbitrary) channel case, e.g., RGB images.

Corollary 3.4:

The Gâteaux derivative of ${\cal R}:[C^{1}_{\ast}(\Omega)]^{3}\rightarrow\BBR$ defined as (6) at $z=(z_{1},z_{2},z_{3})$ is given by

$$D{\cal R}_{z}=-\mathop{\rm div}\left[\left(\matrix{\kappa_{1}&\tau_{1,2}&\tau_{1,3}\cr\tau_{1,2}&\kappa_{2}&\tau_{2,3}\cr\tau_{1,3}&\tau_{2,3}&\kappa_{3}}\right)\nabla\left(\matrix{z_{1}\cr z_{2}\cr z_{3}}\right)\right]\eqno{\hbox{(10)}}$$ where $\kappa_{i}\buildrel{\rm def}\over{=}\sum_{j\ne i}\kappa (z_{i},z_{j})$ and $\tau_{i,j}\buildrel{\rm def}\over{=}\tau (z_{i},z_{j})$. For the definition of $\kappa$ and $\tau$ see (9).

Asymptotics of the Diffusivities

We now turn to the asymptotics of the diffusivities. Without loss of generality we will just discuss the diffusivities for $u$. In the limit when the information in $v$ vanishes, i.e., $\nabla v\rightarrow 0$, we would like that this complex diffusion simplifies to an edge preserving denoising scheme, e.g., total variation denoising. Therefore, the cross diffusivity $\tau (u,v)$ needs to converge to zero. In case that both channels $u$ and $v$ are flat we want to have isotropic diffusion as there are no edges to be preserved or enhanced, i.e., $\kappa (u,v)\rightarrow 1$. This is in general not true but holds in a special case.

Proposition 3.5:

Let $\varphi$, $\psi$ be continuously differentiable with $\varphi^{\prime}=1$ and $\psi^{\prime}=1$. Then the diffusivities of the Gâteaux derivative (9) fulfil the following properties. If $\nabla v\rightarrow 0$, then

$$\kappa (u,v)\rightarrow{{\beta}\over{\Vert\nabla u\Vert_{\beta}}}\qquad\tau (u,v)\rightarrow 0$$ and $\kappa (u,v)\rightarrow 1$, if $\nabla u$, $\nabla v\rightarrow 0$.

Proof:

With the assumptions on the derivatives of $\varphi$ and $\psi$ the diffusivities simplify to

$$\kappa (u,v)={{\Vert\nabla v\Vert_{\beta}}\over{\Vert\nabla u\Vert_{\beta}}}\quad{\rm and}\quad\tau (u,v)=-{{\left\langle\nabla u,\nabla v\right\rangle}\over{\vert\left\langle\nabla u,\nabla v\right\rangle\vert_{\beta^{2}}}}.$$ The stated properties are now obvious. $\blackboxfill$

Due to the desired asymptotics we only considered the case $\varphi (s)$, $\psi[s]=s$ in our numerical experiments. It is likely that there are other pairs of functions $\varphi (s)$, $\psi[s]$ so that these asymptotics hold true but it is out of the scope of this paper to characterize them all.

B. Color Total Variation and Nambu Functional

As we will compare our method with color total variation and the Nambu functional we will state them and their Gâteaux derivatives here.

Color total variation [4], i.e., $\vert z\vert_{\rm CTV}\buildrel{\rm def}\over{=}\sqrt{\sum_{i}\vert z_{i}\vert_{\rm TV}^{2}}$ with $\vert z_{i}\vert_{\rm TV}\buildrel{\rm def}\over{=}\int_{\Omega}\Vert\nabla z_{i}\Vert_{\beta}\,{\rm d}x$ can not be expressed directly in our framework of Proposition 3.1. Nevertheless the Gâteaux derivative is of form (10) with diffusivities

$$\kappa_{i}\buildrel{\rm def}\over{=}{{\vert z_{i}\vert_{\rm TV}}\over{\vert z\vert_{\rm CTV}}}{{1}\over{\left\Vert\nabla z_{i}\right\Vert}},\quad\tau_{i,j}\buildrel{\rm def}\over{=}0.\eqno{\hbox{(11)}}$$ The other variational method we want to compare with is the Nambu functional [6] which can be stated as $\int_{\Omega}\eta (z/\beta)\,{\rm d}x$ with $$\eqalignno{&\eta (z)\buildrel{\rm def}\over{=}\cr&\qquad\sqrt{1+\sum_{i}\left\Vert\nabla z_{i}\right\Vert^{2}+\sum_{i<j}\left\Vert\nabla z_{i}\right\Vert^{2}\Vert{\nabla z_{j}}\Vert^{2}-\left\langle\nabla z_{i},\nabla z_{j}\right\rangle^{2}}.}$$ Then the Gâteaux derivative takes again the form of (10) with diffusivities $$\eqalignno{\kappa_{i}\buildrel{\rm def}\over{=}&\,\left(1+\sum_{j\ne i}\left\Vert\nabla z_{j}\right\Vert\right)\eta(z)^{-1}\cr\tau_{i,j}\buildrel{\rm def}\over{=}&\,-\left\langle\nabla z_{i},\nabla z_{j}\right\rangle\eta(z)^{-1}.&{\hbox{(12)}}}$$

SECTION IV. Numerical Experiments

A. Implementation

The task at hand is to minimize (1) for our parallel level set cost functional. As this functional is differentiable we use tools from optimization to solve it [18]. A suitable choice for large scale optimization with information about the first but not the second derivative is the large scale version of BFGS [18, p. 226]. This is a Quasi-Newton method where the Hessian is approximated by a low rank matrix based only on first derivative information. The line search algorithm is also taken from [18, p. 59].

To complete the implementation details we will describe how we discretized our Gâteaux derivative, see (10). We use an image extension so as to satisfy the vanishing normal derivatives as required by the assumptions in Theorem 3.4. It is sufficient to have a look at the discretization of $\mathop{\rm div}(\kappa\nabla u)$ at any point $(i,j)$ as all the terms in (10) are of this form. By using a central differencing scheme on a sub-grid, i.e., $\partial_{1}u_{i,j}\approx u_{i+1/2, j}-u_{i-1/2,j}$, and linear interpolation of any missing values, i.e., $u_{i+1/2, j}=1/2[u_{i+1, j}+u_{i, j}]$, we get

$$\eqalignno{&\mathop{\rm div}(\kappa\nabla u)_{i,j}\approx{{1}\over{2}}\Biggl\{\sum_{(k,l)\in{\cal N}(i,j)}[\kappa_{k,l}+\kappa_{i,j}] u_{k,l}\cr&\qquad\qquad\qquad\quad\quad-[\overline{\kappa}_{i,j}+4\kappa_{i,j}] u_{i,j}\Biggr\}&{\hbox{(13)}}}$$ where the neighbourhood of $(i,j)$ is defined as ${\cal N}(i,j)\buildrel{\rm def}\over{=}\{(i+1, j), (i-1, j), (i, j+1), (i, j-1)\}$ and $\overline{\kappa}_{i,j}\buildrel{\rm def}\over{=}\sum_{(k,l)\in{\cal N}(i,j)}\kappa_{k,l}$. This spatial discretization is a compromise between accurate and local approximation of the derivatives. More accurate approximations would result in less spatial resolution.

It is very important to note that we are not proposing an algorithm but a cost functional which can be used in a variational formulation. This is independent of the actual algorithm which is used to minimize the corresponding objective function.

As we know the ground truth in our numerical simulations the parameters $\alpha$ and $\beta$ were chosen to be optimal. We will discuss the trend with respect to noise of the chosen parameters but further analysis is out of scope of this paper.

The MATLAB implementation of the method can be found on the authors' homepage [19].

B. Measuring Similarities of Images

To evaluate our results we define some objective criteria measuring the denoising and demosaicking performance. We decided to use the peak signal-to-noise ratio (PSNR) which is probably the most common measure to evaluate image enhancement performance. It is defined as $\mathop{\rm PSNR}(u, u_{\delta})\buildrel{\rm def}\over{=}10\log_{10}\left(255^{2}/\left\Vert u-u_{\delta}\right\Vert_{L^{2}}^{2}\right)$ for images in the range of $[{0, 255}]$ [20, p. 272]. Next to this measure we also refer to the measure of structural similarity (SSIM) which is often seen to be closer to visual perception [21], [22]. It is extended to color images as the mean of the SSIM of the color channels

C. A Simple Example

Let us start with a simple example which illustrates the properties of our method and is shown in Fig. 2. The top two rows (a), (b) show the evolutions of the start images $u$ and $v$ on the left hand side towards minimization of the proposed parallel level set cost functional with $\varphi (s)$, $\psi[s]=s$. Below in the bottom two rows (c), (d) the corresponding level sets are displayed. It is clearly visible that from the initial shapes, the images evolve to a common shape that is somewhat in between both of the original shapes. Furthermore, we see that the background is almost unchanged and that the gradients are either parallel or zero.

Fig. 2. The figure shows a toy example to illustrate the evolution to minimize the proposed parallel level set cost functional for the choice $\varphi (s)$, $\psi[s]=s$. (a) and (b) show the sequence of the images $u$ and $v$. The initial images were chosen to be for (a) $u(x)=\exp[-(\Vert x\Vert_{\infty}-\mu_{1})^{2}/\nu^{2}]$ and (b) $v(x)=1-\exp[-(\Vert x\Vert_{1}-\mu_{2})^{2}/\nu^{2}]$. Their corresponding level sets (contour lines) are shown in (c) and (d).

We can see in detail how these shapes evolve to the steady state. Looking at the top row, at first the shape evolves at all eight common corners. At its own corners we can clearly see the diffusing nature of this method (fourth image from the left hand side). But after this usual diffusion these “shadows” move back to a sharp image. At first sight it might appear that this diffusion in the “wrong direction” could be explained by shock filtering of Osher and Rudin [23] but as the corresponding diffusivities $\kappa$ are non-negative this can not be the reason. Another plausible reason is that this is cross-channel diffusion as the cross-diffusion coefficients $\tau$ are non-zero.

D. Denoising of Color Images

Next, we want to show that this method can be used very well to denoise color images. As test data we have chosen some color images of the Berkeley Segmentation Database [24], [25]. For better comparison we used publicly available noisy versions of those which are degraded by additive, uncorrelated Gaussian noise of standard deviations of 5, 10, 15, 25 and 35 [26].

For the denoising case we compare our results with non-local means [27], Nambu functional [6] and color total variation (CTV) [4]. For non-local means we used the implementation available at [28]. As the others are variational methods we implemented these for better comparison in the same manner as we implemented the proposed parallel level set method. This means (1) with the operator being the identity is minimized by using a Quasi-Newton method described above with the gradient (10) and diffusivities given by (11) and (12).

The results for one test image are shown in Fig. 3. All methods perform very well for a small noise level. When the noise level increases non-local means shows unpleasant color fluctuations. While the Nambu functional smooths the images a lot to get rid of the noise the proposed method yields sharper images. Fig. 4 shows the PSNR and SSIM with respect to the noise level. Non-local means and color total variation are clearly worse than the Nambu functional and the proposed parallel level sets functional. The performance of these are very similar with the proposed functional most of the time ahead of the Nambu functional.

Fig. 3. Denoising of color images. The results of the proposed parallel level set cost functional (proposed), the Nambu functional (Nambu) and non-local means (NL Means) are shown. Not shown are the results for color total variation due to space limitations. The figure shows the results for increasing noise level, i.e., higher standard deviation (std). While non-local means shows color fluctuations with increasing noise level the images obtained by the Nambu functional are far blurrier than the one of the proposed parallel level sets cost functional. The parameters are chosen to maximize the peak signal-to-noise ratio.

Fig. 4. The figure shows the denoising performance with respect to the noise level of the methods under comparison. The solid line is the mean PSNR and SSIM taken over the five test images. The dotted lines indicates the minimal and maximal values. The results of non-local means and color total variation are clearly worse than the Nambu functional and the proposed parallel level sets functional. These two perform very similar with the proposed functional almost all the time ahead of the Nambu functional.

In Fig. 5 the choices of parameters are plotted against the noise level with the solid line indicating the mean and the dotted lines the minimum and maximum over the five data sets. It can be seen that the optimal parameters vary a lot between different images. As expected there is an overall trend in the regularization parameter $\alpha$ to decrease to zero as the noise level decreases. This trend can also be seen for $\beta$ for the parallel level sets functional and non-local means but not for the Nambu functional and color total variation.

Fig. 5. The parameters used for denoising are shown. The solid line represents the mean and the dotted lines the maximum and minimum of the parameters. They were optimized to maximize the PSNR (blue) and the SSIM (green). The parameters used for non-local means are half the kernel size $(\alpha)$ and the variance of the gaussian weights $(\beta)$.

E. Demosaicking of Color Images

Demosaicking is the reconstruction of a color image which is obtained by acquiring image data only at positions described by the Bayer filter shown in Fig. 6. This means that at each position either the intensity for red, green or blue is acquired. This technique enables either to acquire a lot less data for a given resolution or to enhance the resolution by using the same amount of data. A detailed discussion of demosaicking is given in [3] and [8]. A typical data set for demosaicking is given in Fig. 6.

Fig. 6. Left: The Bayer filter is used for demosaicking. At each pixel just one detector aquires either red, green or blue. Therefore post-processing is needed to get the full image at the desired resolution. Right: The Bayer filter applied to a part of the test image “bugs.” It is clearly visible that at each pixel location only information about one color is present.

The same data sets for demosaicking as for denoising is used. These data sets are then degraded by the Bayer filter. To compare our results we used only the variational methods as it is straightforward to state the demosaicking problem as an optimization problem (1) with the operator $A$ performing the Bayer filter.

Some results are given in Figs. 7 and 10. Fig. 7 shows that the proposed parallel level set cost functional can be used to fully recover Bayer filtered images with low noise levels. The difference between the reconstructed images and the original images are hardly visible. A comparison with the Nambu functional and color total variation can be obtained from Fig. 10. While color total variation gives blurry results with many color artefacts the Nambu functional is capable of eliminating most of these. It is clear that the proposed method gives the sharpest images with only a few color artefacts in high noise levels.

Overall, we can see from Fig. 8 that color total variation performs much worse than the proposed parallel level set functional and the Nambu functional. While the PSNR indicates that the Nambu functional is slightly better the SSIM states the opposite. For high noise levels they show that the proposed method performs clearly better than the Nambu functional.

Fig. 7. The figure shows the demosaicking results of the proposed parallel level set cost functional (proposed) for noise with low standard deviation $({\rm std}={5})$. It can be see that the proposed method is capable to reconstruct the missing values without any color artefacts. The difference of the reconstructed image to the original one are hardly visible. The parameters are chosen to maximize the peak signal-to-noise ratio.

Fig. 8. The figure shows the demosaicking performance with respect to the noise level of the methods under comparison. The solid line is the mean PSNR and SSIM taken over the five test images. The dotted lines indicates the minimal and maximal values. The results of color total variation are clearly worse than the Nambu functional and the proposed parallel level sets functional. These two perform very similar with the proposed functional almost all the time ahead of the Nambu functional. Especially for very high noise the proposed method performs clearly better.

Fig. 9. The parameters used for demosaicking are shown. The solid line represents the mean and the dotted lines the maximum and minimum. The parameters were either optimized to maximize the PSNR (blue) or the SSIM (green).

Fig. 10. The figure shows the demosaicking results of the proposed parallel level sets cost functional (proposed), color total variation (CTV) and the Nambu functional (Nambu) for increasing noise level. The images obtained by CTV and Nambu functional are blurrier at noise with higher standard deviation (std). CTV shows a lot color artefacts due to the missing information of the Bayer filter for all noise levels. The parameters are chosen to maximize the peak signal-to-noise ratio.

The parameters are plotted against the noise level in Fig. 9 where in all cases and for both parameters a trend towards zero for decreasing noise level is visible. While the variation of $\alpha$ with respect to the noise level seems to be almost constant the variation of $\beta$ is increasing with increasing noise level.

SECTION V. Conclusion

We propose a new framework based on parallel level sets which can be used for image enhancement of vector-valued images. In this approach we exploit the interchannel correlation which is inherent in many vector-valued images such as RGB images. The examples presented in this paper indicate that exploiting this correlation leads to better, sharper reconstructions with less artefacts. The results show that the notion of parallel level sets is a promising tool for vector-valued image processing tasks.

While we showed the usage for denoising and demosaicking it is easily extendible to other applications where more complicated operators are involved. This includes for instance simultaneous reconstruction of multi-modal medical imaging. Such applications will be the subject of future research.

ACKNOWLEDGEMENT

The authors would like to thank the two anonymous reviewers for their comments. M. J. Ehrhardt would like to acknowledge support from an Individual Framework Collaboration Agreement with Siemens Ltd.