Keywords

1 Introduction

An important problem in image analysis is to separate different features in images. However, when the image is noisy, the decomposition process becomes challenging, especially in the separation of the textural component.

In the last two decades many papers were published on image decomposition, addressing modelling and algorithmic aspects and presenting the use of image decomposition in cartooning, texture separation, denoising, soft shadow/spot light removal and structure retrieval - see, e.g., the recent works [7,8,9] and the references therein. Given the desired properties of the image components all the valuable contributions to this problem rely on a variational-based formulation which minimizes the sum of different energy norms: total variation (TV) semi-norm, [14], L\(^1\)-norm, G-norm [1, 12], approximation of the G-norm by the \(div(\textrm{L}^p )\)-norm [15] and by the H\(^{-1}\)-norm [13], homogeneous Besov spaces [5], to model the oscillatory component of an image. A balanced combination of TV semi-norm and L\(^2\)-norm for separating the piecewise constant and smooth components is proposed in [6]. The intrinsic difficulty with these minimization problems comes from the numerical intractability of the considered norms [3, 16], from the tuning of the numerous model parameters, and, overall, from the complexity of extracting noise from a textured image, given the strong similarity between these two components. This paper aims to give robust and efficient answers to these problems by exploiting statistical image characterizations and advanced numerical optimization algorithms.

We present a two-stage variational approach for the decomposition of a given (vectorized) image \(f\in \mathbb {R}^{N}\) into the sum of four characteristic components:

$$\begin{aligned} f = c + s + t+ n\,,\;\,\text {with:}\;\, \;\,o := t + n,\;\, u := c +s + t\, , \end{aligned}$$
(1)

where c, s, t and n represent the cartoon or geometric (piecewise constant), the smooth, the texture and the noise components, respectively, whereas the introduced composite components o and u indicate the oscillatory and noise-free parts of f, respectively. The cartoon, smooth, and oscillatory components c, s, o are separated in the proposed first stage, with the three parts well-captured by using a non-convex TV-like term for c, a quadratic Tikhonov term for s and Meyer’s G-norm for o. The estimated oscillatory component is then separated into texture and white noise parts t, n in the second stage by exploiting the noise whiteness property. This allows to deal effectively with a large class of important noises such as, e.g., those characterized by Gaussian, Laplacian and uniform distributions, which can be found in many applications. In the first stage, the two free regularization parameters are selected based on a novel multi-parameter cross-correlation principle which extends the single-parameter criterion recently proposed in [7]. The first and second stage optimization problems are efficiently solved by means of the alternating directions method of multipliers (ADMM).

In Sect. 2, we begin by recalling some preliminary definitions. The proposed quaternary two-stage variational decomposition model is introduced and motivated in Sect. 3. The cartoon-smooth-oscillating components separation approach (Stage I) is analysed in Sect. 4.1 - modelling insights - and in Sect. 4.2 - resolvability conditions. The multi-parameter selection is discussed in Sect. 5, while in Sect. 6 the computational ADMM framework is detailed. In Sect. 7 we demonstrate the ability of the proposed decomposition model to separate the desired image features and conclusions are drawn in Sect. 8.

2 Preliminaries and Notations

We recall some notions and definitions which will be useful in the rest of the paper. Let us consider two non-zero images in matrix form \(x,y \in \mathbb {R}^{h \times w}\),

$$\begin{aligned} x \,\;{=}\;\, \left\{ x_{i,j} \right\} _{(i,j) \in \mathrm {\Omega }}, \; y \,\;{=}\;\, \left\{ y_{i,j} \right\} _{(i,j) \in \mathrm {\Omega }}, \; \mathrm {\Omega } \;{:=}\; \{ 0 , \,\ldots \, , h-1 \} \times \{ 0 , \,\ldots \, , w-1 \} \, . \end{aligned}$$
(2)

Upon the assumption of suitable boundary conditions for x, y, the sample normalized cross-correlation of the two images x and y and the sample normalized auto-correlation of image x are the two matrix-valued functions \(\rho : \mathbb {R}^{h \times w} \times \mathbb {R}^{h \times w} \rightarrow \mathbb {R}^{h \times w}\) and \(\varphi : \mathbb {R}^{h \times w} \rightarrow \mathbb {R}^{h \times w}\) defined by

$$\begin{aligned} \rho (x,y) \;{=}\; \left\{ \rho _{l,m}(x,y) \right\} _{(l,m) \in \mathrm {\Omega }} \, , \quad \; \varphi (x) \;{=}\; \left\{ \varphi _{l,m}(x) \right\} _{(l,m) \in \mathrm {\Omega }} \, , \end{aligned}$$
(3)

with scalar components \(\rho _{l,m}(x,y)\) and \(\varphi _{l,m}(x)\) given by

$$\begin{aligned} \rho _{l,m}(x,y) \;\;{=}\,{} & {} \!\!\! \frac{1}{\Vert x\Vert _2 \Vert y\Vert _2} \!\! \sum _{\;(i,j)\in \,\mathrm {\Omega }} \! x_{i,j} \, y_{i+l,j+m} \, , \quad \; (l,m) \in \mathrm {\Omega } \, , \end{aligned}$$
(4)
$$\begin{aligned} \varphi _{l,m}(x) \,\;{=}\;\, \rho _{l,m}(x,x) \;\;{=}\,{} & {} \!\!\! \quad \frac{1}{\Vert x\Vert _2^2} \;\;\, \sum _{\;(i,j)\in \,\mathrm {\Omega }} \! x_{i,j} \, x_{i+l,j+m} \, , \quad \; (l,m) \in \mathrm {\Omega } \, , \end{aligned}$$
(5)

respectively, where \(\Vert \cdot \Vert _2\) in (4)–(5) denotes the Frobenius matrix norm and index pairs (l, m) are commonly called lags. It is well known that the sample normalized cross- and auto-correlations satisfy \(\,\rho _{l,m}(x,y), \, \varphi _{l,m}(x,y) \,\;{\in }\;\, [-1,1] \;\; \forall \, (l,m) \in \overline{\mathrm {\Theta }}\).

We introduce the following non-negative scale-independent scalar measure of correlation \(\mathcal {C}: \mathbb {R}^{h \times w} \times \mathbb {R}^{h \times w} \rightarrow \mathbb {R}_+\) between the images x and y:

$$\begin{aligned} \mathcal {C}(x,y) \,\;{:=}\;\, \frac{1}{N} \, \left\| \rho (x,y) \right\| _2^2 \,. \end{aligned}$$
(6)

Finally, we recall the Meyer’s characterization of highly oscillating images - the component o in (1) - in the G-space, dual of \(\textrm{BV}\)-space [12], endowed with the G-norm defined in the discrete setting by

$$\begin{aligned} \Vert o\Vert _{\textrm{G}} = \inf \left\{ \Vert g\Vert _\infty \bigm \vert o = \textrm{div}(g),\;\, g=(g^{(1)},g^{(2)})\in \mathbb {R}^{h\times w}\times \mathbb {R}^{h\times w} \right\} , \end{aligned}$$
(7)

where \(\Vert g\Vert _\infty := \max _{i,j} |g_{i,j}|\), with \(|g_{i,j}|=\sqrt{(g_{i,j}^{(1)})^2+(g_{i,j}^{(2)})^2}\). The G-space is very good to model oscillating patterns such as texture and noise, characterized by zero-mean functions of small G-norm [2].

3 Proposed Two-Stage Variational Decomposition Model

An observed image \(\,f\), composed as in (1), is separated into cartoon, smooth, texture and noise components by solving the following two-stage model:

  • Stage I: Given the observation f, compute estimates \(\widehat{c}\), \(\widehat{s}\), \(\widehat{o}\) of the cartoon, smooth and oscillatory components c, s, o in (1) by solving

    $$\begin{aligned}&\{\widehat{c},\widehat{s},\widehat{o}\} \; {\in } \; \underset{ \tiny \begin{array}{c} c,s,o \,{\in }\,\mathbb {R}^N \\ c+s+o = f \end{array}}{{\text {arg}}\,{\text {min}}}\; \mathcal {J}_1(c,s,o;\gamma _1,\gamma _2,a_1),&\end{aligned}$$
    (8)
    $$\begin{aligned}&\mathcal {J}_1(c,s,o;\gamma _1,\gamma _2,a_1) = \displaystyle {\gamma _1 \sum _{i=1}^{N} \phi \left( \left\| (\textrm{D}c)_i\right\| _2;a_1\right) + \frac{\gamma _2}{2} \left\| \textrm{H}s \right\| _2^2 + \Vert o\Vert _G} ,&\end{aligned}$$
    (9)

    with penalty function \(\phi \) defined in (13) and G-norm defined in (7).

  • Stage II: Given the estimate \(\widehat{o}\) from Stage I, compute estimates \(\widehat{t}\), \(\widehat{n}\) of the texture and white noise components t, n in (1) by solving

    $$\begin{aligned} \{\widehat{t},\widehat{n}\} \,&{\in }&\underset{\tiny \begin{array}{c} t,n \in \mathbb {R}^{N} \\ t+n = \widehat{o}\\ \end{array}}{{\text {arg}}\,{\text {min}}}\; \left\{ \mathcal {J}_2(t,n;a_2,\alpha ) = \displaystyle { \sum _{i=1}^{N} \phi \left( \left\| (\textrm{D}t)_i\right\| _2;a_2\right) } + \imath _{\mathcal {W}_{\alpha }}( n) \right\} , \quad \end{aligned}$$
    (10)

where \(\gamma _1,\gamma _2\) in (8) are positive parameters, \(\textrm{D}:= (\textrm{D}_h;\textrm{D}_v) \in \mathbb {R}^{2N \times N}\), with \(\textrm{D}_h,\textrm{D}_v \in \mathbb {R}^{N \times N}\) finite difference operators discretizing the first-order horizontal and vertical partial derivatives of an image, respectively, and where the discrete gradient of image x at pixel i is denoted by \(\,(\textrm{D}x)_i \;{:=}\; ( (\textrm{D}_h \, x)_i \,;\, (\textrm{D}_v \, x)_i ) \in \mathbb {R}^2\). The matrix \(\textrm{H}\) discretizes the second-order horizontal, vertical and mixed partial derivatives, with \(\,(\textrm{H} x)_i \;{:=}\; ( (\textrm{H}_{hh} \, x)_i \,;\, (\textrm{H}_{hv} \, x)_i \,;(\textrm{H}_{vh} \, x)_i \,; \,(\textrm{H}_{vv} \, x)_i) \in \mathbb {R}^4\) denoting the vectorized Hessian at pixel i. The function \(\,\imath _{\mathcal {W}_{\alpha }}: \mathbb {R}^N \rightarrow \overline{\mathbb {R}} := \mathbb {R}\cup \{+\infty \}\) in (10) is the indicator function of the set \(\mathcal {W}_{\alpha } \subset \mathbb {R}^N\), namely \(\,\imath _{\mathcal {W}_{\alpha }} = 0\) for \(x \in \mathcal {W}_{\alpha }\), \(\,\imath _{\mathcal {W}_{\alpha }} = +\infty \) for \(x \notin \mathcal {W}_{\alpha }\). Therefore, the target white noise component n or, equivalently, the residue image \(\widehat{o} - t\) of Stage II model (10), must belong to the parametric set \(\mathcal {W}_{\alpha }\), referred to as the normalized whiteness set with \(\alpha \in \mathbb {R}_{++}\) called the whiteness parameter, and defined as follows:

$$\begin{aligned} \mathcal {W}_{\alpha }&{:=}&\big \{ \, n \in \mathbb {R}^{h \times w} : \; -w_{\alpha } \le \, \varphi _{l,m}(n) \le w_{\alpha } \quad \!\! \forall \, (l,m) \in \overline{\mathrm {\Theta }}_0:= \overline{\mathrm {\Theta }}\;\,{\setminus }\, \{(0,0)\} \, \big \} \nonumber \\&{=}&\big \{ \, n \in \mathbb {R}^{h \times w} : \; -w_{\alpha } \, n^T n \le \, \big (n \,{\star }\, n \big )(l,m) \le w_{\alpha } \, n^T n \quad \!\! \forall \, (l,m) \in \overline{\mathrm {\Theta }}_0 \, \big \} . \end{aligned}$$
(11)

Motivated by the asymptotic distribution of the sample normalised auto- correlation \(\varphi (n)\) (see [7]), a natural choice for the non-negative scalar \(w_{\alpha }\) is

$$\begin{aligned} w_{\alpha } = \frac{\alpha }{\sqrt{N}} \,, \end{aligned}$$
(12)

where the whiteness parameter \(\alpha \) allows to directly set the probability that the sample normalized auto-correlation of a white noise realization at any given non-zero lag falls inside the whiteness set.

The parametric function \(\phi (\,\cdot \,;a): \mathbb {R}_+ \rightarrow \mathbb {R}_+\) in (8) is a re-parameterized and re-scaled version of the minimax concave (MC) penalty, namely a simple piecewise quadratic function defined by:

$$\begin{aligned} \phi (t;a) \,\;{=}\; \left\{ \begin{array}{ll} \displaystyle {- \frac{a}{2} \, t^2 + \sqrt{2a} \, t} &{}\;\textrm{for}\;\; t \;{\in }\; \big [ \, 0 , \sqrt{2/a} \, \big ) \, , \\ 1 &{}\;\textrm{for}\;\; t \;{\in }\; \big [ \, \sqrt{2/a} , +\infty \, \big ) \, , \end{array} \right. \end{aligned}$$
(13)

with \(a \in \mathbb {R}_+\) called the concavity parameter of penalty \(\phi \). In fact, since \(a = - \min _{t\ne 0} \phi ''(t;a)\), it represents a measure of the degree of non-convexity of \(\phi \).

4 On the Decomposition Stage I

4.1 Insights on the Effect of Different Norms

Given the desired properties of components c, s, t and n, an ideal decomposition model is characterized by the minimization of energies expressed in terms of norms: \(\sum _i \phi (\Vert (\textrm{D}u_1)_i\Vert ;a)=\) is minimal for \(x=c\), \(\Vert \textrm{H}x \Vert _2\) is minimal for \(x=s\), \(\Vert x\Vert _G\) is minimal for \(x=t\), \(\Vert \varphi (x) \Vert _{\infty }:=\max _{(l,m) \ne (0,0) }\, | \varphi _{(l,m)} (x) | \,\) is minimal for \(x=n\).

In Table 1, we provide an insight on this conjecture, for synthetic images with different features illustrated in Fig. 1: piecewise constant scalar fields with sharp edges (\(u_1\)); smooth-gradient scalar fields with varying frequency of oscillations according to parameter z, (\(u_2\)); realization of Gaussian noise with increasing standard deviations \(\sigma \), (\(u_3\)).

The noise component n is perfectly captured by \(\Vert \varphi (u_3)\Vert _{\infty }\) making it minimal and constant for any values of standard deviation \(\sigma \), while \(\textrm{H}^{-1}\)-norm and G-norm values increase as the noise level increases. If the term \(\Vert \varphi (u_3)\Vert _{\infty }\) is not present in the model, then the noise component n is absorbed by the G-norm.

The cartoon component c is well detected by minimal values of \(\sum _i \phi (\Vert (\textrm{D}u_1)_i\Vert ;a)=\) in the first block of Table 1 for all z values but the last column where the image no longer looks like a piecewise constant image, but it looks more like a texture.

Similarly the smooth component s is separated by a minimal \(\Vert \textrm{H}s\Vert _2\) in the second block of Table 1, for all z but the last column where the image has a pronounced textural component.

For what concern the texture component t, both the \(\textrm{H}^{-1}\)-norm and G-norm capture oscillations and they decrease for increasing frequency z, which is good, they both increase for increasing oscillation amplitude, which is not so good. However, G-norm is independent from image dimension, while \(\textrm{H}^{-1}\)-norm increases proportionally with dimension. Moreover, \(\textrm{H}^{-1}\)-norm recognizes as texture only the fine oscillatory patterns (see last column), while G-norm remains limited and small for different scale repeated patterns.

Fig. 1.
figure 1

Sample images used to evaluate model norms.

Full size image
Table 1. Model norms evaluated for images \(u_1, u_2\) and \(u_3\) in Fig. 1
Full size table

4.2 Analysis of the Model

The goal of this section is to shortly analyze the Stage I optimization problem (8)–(9). To facilitate the analysis, first we note that, after replacing in (8)–(9) the explicit definition of the G-norm of the oscillating component \(o=\textrm{D}^Tg\), and exploiting the additive image formation model (1) (from which \(s = f - c - o\)), problem (8)–(9) is equivalent to the following one:

$$\begin{aligned}&\{\widehat{c},\widehat{g}\} \;{\in }\; \underset{ \tiny c \,{\in }\,\mathbb {R}^N\!, \,g \,{\in }\, \mathbb {R}^{2N}}{{\text {arg}}\,{\text {min}}}\; \widetilde{\mathcal {J}}_1(c,g;\gamma _1,\gamma _2,a_1)\,,&\end{aligned}$$
(14)
$$\begin{aligned}&\displaystyle {\widetilde{\mathcal {J}}_1(c,g;\gamma _1,\gamma _2,a_1) \;{=}\; \gamma _1 \!\sum _{i=1}^{N} \phi \left( \left\| (\textrm{D}c)_i\right\| _2;a_1\right) \,{+}\, \frac{\gamma _2}{2} \!\left\| \textrm{H}( f - c - \textrm{D}^T g) \right\| _2^2 \,{+}\,\Vert g\Vert _{\infty }}&\quad \end{aligned}$$
(15)
$$\begin{aligned}&\widehat{o} \;{=}\; \textrm{D}^T \widehat{g}\,, \quad \; \widehat{s} \;{=}\; f - \widehat{c} - \widehat{o} \, .&\end{aligned}$$
(16)

In the following Propositions 1, 2 (see proofs in the Supplementary Material) we analyze the optimization problem (14)–(15), with focus on convexity and coerciveness of the cost function \(\widehat{\mathcal {J}}_1\), and afterward, on existence of solutions to the problem. To simplify notations, we introduce the total optimization variable \(x:=\big (c;g\big ) \in \mathbb {R}^{3N}\).

Proposition 1

For any \(f \in \mathbb {R}^N\) and any \(\gamma _1,\gamma _2,a_1 \in \mathbb {R}_{++}\), the function \(\widetilde{\mathcal {J}}_1\) in (15) is proper, continuous, bounded from below by zero, convex and coercive in g, non-convex and non-coercive in c, hence non-convex and non-coercive in x. However, the function \(\widetilde{\mathcal {J}}_1\) admits global minimizers.

Proposition 2

For any \(f \in \mathbb {R}^N\) and any \(\gamma _1,\gamma _2,a_1 \in \mathbb {R}_{++}\), the function \(\widetilde{\mathcal {J}}_1\) in (15) is constant along straight lines in its domain \(\mathbb {R}^{3N}\) of direction defined by the vector \(d \,\;{:=}\;\, \big ( \, 1_N;0_{2N} \big )\). Hence, any constrained model of the form

$$\begin{aligned} \{\widehat{c},\widehat{g}\} \;{\in }\; \underset{(c;g) \,{\in }\, \mathcal {A}_{q_1,q_2}}{{\text {arg}}\,{\text {min}}}\; \widetilde{\mathcal {J}}_1(c,g;\gamma _1,\gamma _2,a_1) \, , \end{aligned}$$
(17)

with \(\,\mathcal {A}_{q_1,q_2} \subset \mathbb {R}^{3N}\) one among the infinity of \(\,(3N-1)\)-d affine feasible sets

$$\begin{aligned} \mathcal {A}_{q_1,q_2} \,{=}\, \left\{ x \in \mathbb {R}^{3N}\!: \;\, q_1^T x \,\;{=}\;\, q_2 \,\;\textrm{with}\;\;\, q_1^T d \;{\ne }\; 0 \, \right\} , \quad q_1 \in \mathbb {R}^{3N} \,, \;\, q_2 \in \mathbb {R}\, , \end{aligned}$$
(18)

admits solutions and the solutions are equivalent to those of the unconstrained model (14)–(15) in terms of (minimum) cost function value.

5 Multi-parameter Selection via Cross-Correlation

Selecting the regularization parameter of a two-terms (two-components) variational decomposition model based on the cross-correlation between the two estimated components has been proposed in the recent work [7], and referred to as the Cross-Correlation Principle (CCP). However, in the proposed Stage I decomposition model (8) we have three terms/components and two free regularization parameters. Hence, we propose an extension of the CCP in [7] to this more complicated case and refer the extended principle as Multi-Parameter CCP (MPCCP). The MPCCP for Stage I model is formulated as follows:

$$\begin{aligned} \text {Select}\;\;(\gamma _1,\gamma _2) = (\widehat{\gamma }_1,\widehat{\gamma }_2)\;\;\text {such that}\;\;\{\widehat{\gamma }_1,\widehat{\gamma }_2 \}\in \underset{\gamma _1,\gamma _2 \,{\in }\,\mathbb {R}_{++}}{{\text {arg}}\,{\text {min}}}\; C(\gamma _1,\gamma _2)\,, \end{aligned}$$
(19)

where the multi-parameter cross-correlation scalar measure \(C: \mathbb {R}_{++}^2 \rightarrow \mathbb {R}_+\) reads

$$\begin{aligned} \begin{array}{rcl} C(\gamma _1,\gamma _2) &{}\,{=}\,&{} \alpha _{c,o} \, \mathcal {C}\left( \widehat{c}(\gamma _1,\gamma _2),\widehat{o}(\gamma _1,\gamma _2)\right) \;{+}\; \alpha _{s,o} \, \mathcal {C}\left( \widehat{s}(\gamma _1,\gamma _2),\widehat{o}(\gamma _1,\gamma _2)\right) \\ &{}\,{+}\,&{} \alpha _{c,s} \, \mathcal {C}\left( \widehat{c}(\gamma _1,\gamma _2),\widehat{s}(\gamma _1,\gamma _2)\right) \, , \end{array} \end{aligned}$$
(20)

with \(\widehat{c}(\gamma _1,\gamma _2)\), \(\widehat{s}(\gamma _1,\gamma _2)\) and \(\widehat{o}(\gamma _1,\gamma _2)\) the \((\gamma _1,\gamma _2)\)-dependent solution components of Stage I model (8), with the cross-correlation scalar measure \(\mathcal {C}(\cdot ,\cdot )\) defined in (6) and with the cross-correlation weights \(\alpha _{c,o}, \alpha _{s,o}, \alpha _{c,s} \in [0,1]\) allowing to tune the contributions of the three cross-correlations between c and o, s and o, c and s, respectively, to the introduced ternary cross-correlation among c, s, o. In particular, in the first example of the numerical section we will provide evidence that a good choice for the weights is \(\alpha _{c,o} = \alpha _{s,o} = 0.5\), \(\alpha _{c,s} = 0\). The idea encoded by the MPCCP in (19)–(20) is to select the pair \((\gamma _1,\gamma _2)\) in Stage I model (8) which leads to ”as separate as possible” solution components \(\widehat{c}(\gamma _1,\gamma _2)\), \(\widehat{s}(\gamma _1,\gamma _2)\), \(\widehat{o}(\gamma _1,\gamma _2)\), with separability measured by cross-correlation.

The cost function \(C(\gamma _1,\gamma _2)\) we aim to minimize in the MPCCP in (19)–(20) can be evaluated for any given pair \((\gamma _1,\gamma _2)\) (by first solving numerically the associated Stage I model and then directly applying the function C by computing the three cross-correlations) but does not have an explicit form and, hence, the derivatives can not be calculated. A theoretical analysis of the properties of function C is therefore a very hard task and is out of the scope of this paper. However, the numerical tests that we will present seem to indicate that C is continuous (if not differentiable) and unimodal with a unique global minimizer. Hence, by applying some convergent zero-order minimization algorithm - i.e., relying on evaluations of the cost function C but not of its derivatives - for unimodal functions of two variables, MPCCP could be made fully automatic.

6 An ADMM-Based Numerical Solution for Stage I

In this section we consider the solution of the minimization problem (14)–(15) by using ADMM. We introduce two auxiliary variables \(h \in \mathbb {R}^{2N}, \, z \in \mathbb {R}^{2N}\) and solve the following equivalent constrained problem:

$$\begin{aligned} \begin{aligned} \{ \widehat{c}, \widehat{g}, \widehat{h}, \widehat{z}\} \, {\in }&\underset{\begin{array}{c} c \in \mathbb {R}^N,\\ g,h,z \in \mathbb {R}^{2N}, \end{array}}{{\text {arg}}\,{\text {min}}}\; \left\{ \, \gamma _1 \sum _{i=1}^{N} \phi \left( \left\| h_i\right\| _2;a_1\right) + \frac{\gamma _2}{2} \left\| \textrm{H}(f-c-\textrm{D}^Tg)\right\| _2^2 + \left\| z\right\| _{\infty } \right\} \\ \text {s. t.}&\qquad h = \textrm{D}c, \;\, z=g. \end{aligned} \end{aligned}$$
(21)

To solve (21), we define the augmented Lagrangian function

$$\begin{aligned}{} & {} \mathcal {L}(c,g,h,z,\lambda _1,\lambda _2;\gamma _1,\gamma _2) \,{=}\, \gamma _1 \sum _{i=1}^{N} \phi \left( \Vert h_i \Vert _2;a_1\right) + \frac{\gamma _2}{2} \Vert \textrm{H}(f - c - \textrm{D}^T g) \Vert _2^2 + \left\| z\right\| _{\infty } \nonumber \\{} & {} \quad \quad \qquad - \langle \lambda _1 , h - \textrm{D}c \rangle + \frac{\beta _1}{2} \Vert h - \textrm{D}c \Vert _2^2 - \langle \lambda _2 , z - g \rangle + \frac{\beta _2}{2} \Vert z - g \Vert _2^2, \end{aligned}$$
(22)

where \(\lambda _1 \in \mathbb {R}^{2N}\) is the vector of Lagrange multipliers associated with the linear constraints \(h = \textrm{D}c\), \(\lambda _2 \in \mathbb {R}^{2N}\) is the vector of Lagrange multipliers associated with the linear constraints \(z = g\), and \(\beta _1, \beta _2 \in \mathbb {R}_{++}\) are the ADMM penalty parameters. Given the previously computed (or initialized for \(k = 0\)) vectors \(c^{(k)}\), \(g^{(k)}\), \(h^{(k)}\), \(z^{(k)}\), \(\lambda _1^{(k)}\), \(\lambda _2^{(k)}\) and the regularization parameters, the k-th iteration of the proposed ADMM-based iterative scheme reads as follows:

$$\begin{aligned}{} & {} \left( c^{(k+1)},g^{(k+1)}\right) \;{\in }\;\;\,\, \underset{c \in \mathbb {R}^N, g \in \mathbb {R}^{2N}}{{\text {arg}}\,{\text {min}}}\; \; \left\{ \frac{\gamma _2}{2} \Vert \textrm{H}(f - c - \textrm{D}^T g ) \Vert _2^2 - \left\langle \lambda _1^{(k)} , h^{(k)} - \textrm{D}c \right\rangle \right. \nonumber \\{} & {} \left. + \frac{\beta _1}{2} \Vert h^{(k)} - \textrm{D}c \Vert _2^2 - \left\langle \lambda _2^{(k)} , z^{(k)} - g \right\rangle + \frac{\beta _2}{2} \Vert z^{(k)} - g \Vert _2^2 \right\} , \end{aligned}$$
(23)
$$\begin{aligned}{} & {} h^{(k+1)} \;{\in }\;\;\,\, \underset{h \in \mathbb {R}^{2N}}{{\text {arg}}\,{\text {min}}}\; \; \sum _{i=1}^{N} \phi \left( \Vert h_i \Vert _2;a_1\right) + \frac{\beta _1}{2\gamma _1}\left\| h - \left( \textrm{D}c^{(k+1)} + \frac{1}{\beta _1}\lambda _1^{(k)} \right) \right\| _2^2, \end{aligned}$$
(24)
$$\begin{aligned}&z^{(k+1)}&\;{\in }\;\;\,\, \underset{z \in \mathbb {R}^{2N}}{{\text {arg}}\,{\text {min}}}\; \; \frac{1}{\beta _2} \Vert z\Vert _{\infty } + \frac{1}{2}\left\| z - \left( g^{(k+1)} + \frac{1}{\beta _2}\lambda _2^{(k)} \right) \right\| _2^2, \end{aligned}$$
(25)
$$\begin{aligned}&\left( \begin{array}{c} \lambda _1^{(k+1)} \\ \lambda _2^{(k+1)} \\ \end{array} \right)&\;{=}\;\; \left( \, \begin{array}{l} \lambda _1^{(k)} \,\!\,\;{-}\;\,\!\,\! \beta _1 \big ( \, h^{(k+1)} \,\;\;{-}\;\, \textrm{D}c^{(k+1)} \, \big ) \\ \lambda _2^{(k)} \,\!\,\;{-}\;\, \beta _{2} \big ( \, z^{(k+1)} \;\;{-}\;\, g^{(k+1)}\, \big ) \\ \end{array} \right) \, . \end{aligned}$$
(26)

To solve (23), we apply the first-order optimality conditions which lead to solve the following linear system:

$$\begin{aligned} \textrm{A}\left( \begin{array}{c} c \\ g \end{array} \right) = \left( \begin{array}{c} \gamma _2 \textrm{H}^T\textrm{H}f + \beta _1 \textrm{D}^T \left( h^{(k)}- \frac{1}{\beta _1} \lambda _1^{(k)}\right) \\ \gamma _2 \textrm{D}\textrm{H}^T \textrm{H}f + \beta _2 z^{(k)} -\lambda _2^{(k)} \end{array} \right) , \end{aligned}$$
(27)

where

$$\begin{aligned} \textrm{A}= \left[ \begin{array}{cc} \gamma _2 \textrm{H}^T \textrm{H}+ \beta _1 \textrm{D}^T \textrm{D}&{} \gamma _2 \textrm{H}^T \textrm{H}\textrm{D}^T \\ \gamma _2 \textrm{D}\textrm{H}^T \textrm{H}&{} \gamma _2 \textrm{D}\textrm{H}^T \textrm{H}\textrm{D}^T + \beta _2 \textrm{I}\end{array} \right] \,, \end{aligned}$$
(28)

which can be solved via a sparse Cholesky solver. Problem (24) is equivalent to N two-dimensional problems which can be efficiently solved in closed form [8]. In particular, rewriting (24) for each \(h_i\in \mathbb {R}^2\), \(i=1,\ldots ,N\)

$$\begin{aligned} h_i^{(k+1)} \in \underset{h \in \mathbb {R}^2}{{\text {arg}}\,{\text {min}}}\; \phi \left( \Vert h \Vert _2;a_1\right) + \frac{\beta _1}{2\gamma _1}\left\| h - \left( \left( \textrm{D}c^{(k+1)}\right) _i + \frac{1}{\beta _1}\lambda _{1,i}^{(k)} \right) \right\| _2^2 , \end{aligned}$$
(29)

and satisfying the convexity condition \(\beta _1 > a\gamma _1\) (see, e.g., [11]), the closed form in [8] can be applied directly. Problem (25) is not separable but it is equivalent to the proximity operator of the mixed \(\ell _{\infty ,2}\) norm, which also admits a closed form efficient solution [4]. Finally, the ADMM solution of Stage II in (10) is similar to that in [10] and is described in the Supplementary Material.

7 Numerical Examples

In this section we present some preliminary results on the performance of the proposed two-stage decomposition model when applied to images synthetically corrupted by additive white noise of different types among uniform (AWUN), Gaussian (AWGN) and Laplacian (AWLN). We consider three test images of size 200 \(\times \) 200 and 256 \(\times \) 256 pixels - geometric, coast and skyscrapers - which contain flat regions, neat edges and textures.

Example 1

In this example, we evaluate the performance of Stage I of our decomposition framework on the geometric image to showcase the decomposition performance together with the cross-correlation parameter selection. The parameter \(a_1\) (and similarly \(a_2\) for Stage II) can be estimated by directly imposing the abscissa of the transient point \(\bar{a}_1=\sqrt{2/a_1}\) in (13) as \(a_1=2/\bar{a}_1^2\). The rationale is to penalize equally every salient discontinuity in c, therefore the value \(\bar{a}\) should aim to estimate the minimal nonzero salient gradient of c. According to this strategy, for this example we used \(\bar{a}_1=0.4\). Moreover, the ADMM algorithm was initialized by \(h^{(0)}=D f\), \(z^{(0)} = \lambda _1^{(0)} = \lambda _2^{(0)} = 0\). The first row of Fig. 2 reports the input image f, and the resulting components \(\widehat{c}\), \(\widehat{s}\), \(\widehat{o}\), respectively. Each component is visualized in range [0.05,0.95] to demonstrate better both the characteristics as well as reconstruction for each component. In the second row of Fig. 2 we report the cross-correlation surfaces, namely \(C(\gamma _1, \gamma _2)\) in (20) with weights \(\alpha _{c,o} = \alpha _{s,o} = 0.5\), \(\alpha _{c,s} = 0\) - used to select \(\widehat{\gamma }_1\), \(\widehat{\gamma }_2\), \(\mathcal {C}(\widehat{c}(\cdot ),\widehat{s}(\cdot ))\), \(\mathcal {C}(\widehat{s}(\cdot ),\widehat{o}(\cdot ))\) and \(\mathcal {C}(\widehat{c}(\cdot ),\widehat{o}(\cdot ))\) for varying \(\gamma _1\) and \(\gamma _2\). In the latter three surfaces the minimum cross-correlation is represented by a solid dot, while the minimum \(\min (C(\gamma _1,\gamma _2))=C(\widehat{\gamma }_1,\widehat{\gamma }_2)=5.31\times 10^{-8}\) by a diamond marker. In the third row of Fig. 2, from second to last column, we report the associated Signal-to-Noise Ratio (SNR) surfaces for each component for varying \(\gamma _1\), \(\gamma _2\) and the mean SNR surface

$$SNR_{mean}=(SNR(\widehat{c}(\gamma _1,\gamma _2)) + SNR(\widehat{s}(\gamma _1,\gamma _2)) + SNR(\widehat{o}(\gamma _1,\gamma _2))) / 3.$$

Black dot indicates the maximum SNR attained, while the asterisk marks the maximum \(\max (SNR_{mean})\). It can be noticed that the parameter pair \((\widehat{\gamma }_1,\widehat{\gamma }_2)\) selected by the proposed MPCCP is close to the pair \((\gamma _1,\gamma _2)\) yielding a SNR equal to the maximum \(\max (SNR_{mean})\). This indicates that our MPCCP works well for this example. In particular, the SNR values attained by each reconstructed component \(\widehat{c}\), \(\widehat{s}\), \(\widehat{o}\) are \(SNR(\widehat{c}(\widehat{\gamma }_1,\widehat{\gamma }_2))=47.16\), \(SNR(\widehat{s}(\widehat{\gamma }_1,\widehat{\gamma }_2))=52.44\) and \(SNR(\widehat{o}(\widehat{\gamma }_1,\widehat{\gamma }_2))=36.26\).

Fig. 2.
figure 2

Decomposition results of geometric image based on cross-correlation parameter selection for Stage I.

Full size image
Fig. 3.
figure 3

Decomposition results of test images corrupted by AWLN, \(\sigma =6\), AWUN, \(\sigma =10\), and AWGN, \(\sigma =25\), from left to right respectively.

Full size image

Example 2

In this example we present the results of applying Stage I + Stage II to geometric - where we changed the smooth component to a spotlight effect - coast and skyscraper images, corrupted with a realization of AWLN with standard deviation \({\sigma } =6\), AWUN with \({\sigma } =10\), AWGN with \({\sigma } =25\), respectively. Stage I used \(\bar{a}_1=0.4\) with \(h^{(0)}=D f\), \(z^{(0)} = \lambda _1^{(0)} = \lambda _2^{(0)} = 0\) initialization for geometric image, while \(\bar{a}_1=0.1\) with zero initialization of the above variables for the two photographic images. For Stage II, we used \(\bar{a}_2=20\), for geometric, \(\bar{a}_2=0.3\) for coast and \(\bar{a}_2=0.7\) for skyscraper. In the first row of Fig. 3 we report the observed images f used as input for Stage I. The oscillatory component \(\widehat{o}\) was then used as input for Stage II. From second to fifth row of Fig. 3 we report the resulting components \(\widehat{c}\), \(\widehat{s}\), \(\widehat{t}\) and \(\widehat{n}\), where \(\widehat{s}\), \(\widehat{t}\) and \(\widehat{n}\) have been set its mean to 0.5 for visualization purposes. In the last row of Fig. 3 we report images \(\widehat{u}=\widehat{c}+\widehat{s}+\widehat{t}\) which represents the denoised version of the degraded image f.

Remark 1

Due to the nature of G-space, it may seem more natural to model the texture component t by the G-norm, i.e. to use the following model for Stage II:

$$\begin{aligned} \{\widehat{t}_2,\widehat{n}_2\} \;{\in }\; \underset{\tiny t,n \,{\in }\, \mathbb {R}^{N}}{{\text {arg}}\,{\text {min}}}\; \left\{ \Vert t\Vert _G + \imath _{\mathcal {W}_{\alpha }}(n) \right\} \;\, \text {s.t.:}\;\, t+n = \widehat{o}\,. \end{aligned}$$
(30)

In Fig. 4, the decomposition results \(\widehat{t}_2\), \(\widehat{n}_2\), obtained by solving problem (30) for \(\widehat{o}\) of geometric test image, are reported. In the second column of Fig. 4, the horizontal cross-sections are shown: the ground truth (dashed black), and the solutions of Stage II models (10) and (30) (solid red and blue, respectively). From these results, it is clear that the G-norm is not suitable to separate texture from noise. In particular, for localized textures, like the one in Fig. 4, some noise can be included in the texture component without changing its G-norm value.

Fig. 4.
figure 4

Stage II model (30): decomposition results (left) and central horizontal cross-sections (right) of texture and noise with \(\widehat{t}\) and \(\widehat{n}\) from the first column of Fig. 3.

Full size image

8 Conclusions

In this paper we presented a two-stage variational model for the additive decomposition of images corrupted by additive white noise into cartoon, smooth, texture and noise components. We also proposed a novel multi-parameter selection criterion based on cross-correlation which, together with the usage of a whiteness constraint for the noise component, makes the model context- and noise-unaware. Some numerical examples are presented which indicate the good quality decomposition results achievable by the proposed approach.