8.2.1The abstract model

Our image domain will be an open bounded set Ω ⊂ ℝn with Lipschitz boundary. Ourdata f lies in Y = L2(Ω;ℝm). We look for positive parameters λ = (λ1, . . . , λM)and α = (α1, . . . , αN) in abstract parameter sets and They are intended to solve for some convex, proper, weak* lower semicontinuous cost functional F : X → ℝ the problem

for

Our solution u lies in an abstract space X, mapped by the linear operator K to Y. Several further technical assumptions discussed in detail in [39] cover A, K, and ϕi. In Section 8.2.2 of this review we concentrate on specific examples of the framework.

Remark 2.1. In this paper we focus on the particular learning setup as in (P), where the variational model is parameterized in terms of sums of different fidelity terms ϕi and total variation-type regularizers d|Aju|, weighted against each other with scalar-or function-valued parameters λi and αj (respectively). This framework is the basis for the analysis of the learning model, in which convexity of J(⋅; λ, α) and compactness properties in the space of functions of bounded variation will be crucial for proving the existence of an optimal solution. Please note, however, that bilevel learning has been considered in more general scenarios in the literature, beyond what is covered by our model. Let us mention the work by Hintermüller [54] et al. on blind-de-blurring and Pock et al. on learning of nonlinear filter functions and convolution kernels [27, 28]. These works, however, treat the learning model in finite dimensions, i.e., the discretization of a learning model such as ours (P), only. An investigation of these more general bilevel learning models in a function space setting is a matter of future research.

It is also worth mentioning that the model discussed in this paper and in [63] is connected to the sparse optimization model using wavelets, in particular wavelet frames [20].

For the approximation of problem (P) we consider various smoothing steps. For one, we require Huber regularization of the Radon norms. This is required for the singlevalued differentiability of the solution map (λ, α) ↦ uα,λ, required by current numerical methods, irrespective of whether we are in a function space setting or not; for an idea of this differential in the finite-dimensional case, see [87, Theorem 9.56]. Secondly, we take a convex, proper, and weak* lower-semicontinuous smoothing functional H: X → [0, ∞]. The typical choice that we concentrate on is

For parameters μ ≥ 0 and γ ∈ (0, ∞], we then consider the problem

for

Here we denote by |Aju|γ the Huberised total variation measure which is defined as follows.

Definition 2.2. Given γ ∈ (0, ∞], we define for the norm ‖ ⋅ ‖2 on ℝn, the Huber regularization

Then if ν = f ℒn + νs is the Lebesgue decomposition of ν ∈ ℳ(Ω;ℝn) into the absolutely continuous part fℒn and the singular part νs, we set

The measure |ν|γ is the Huber-regularization of the total variation measure |ν|.

In all of these, we interpret the choice γ = ∞to give back the standard unregularized total variation measure or norm.

8.2.2Existence and structure: L2-squared cost and fidelity

We now choose

with M += 1. We also take that is we do not look for the fidelity weights. Our next results state for specific regularizers with discrete parameters α = (α1, . . . , αN) ∈ conditions for the optimal parameters to satisfy α > 0. Observe how we allow infinite parameters, which can in some cases distinguish between different regularizers.

We note that these results are not mere existence results; they are structural results as well. If we had an additional lower bound 0 < c ≤ α in (P), we could without the conditions (2.2) for TV and (2.3) for TGV2 [9] denoising, showthe existence of an optimal parameter α. Also with fixed numerical regularization (γ < ∞and μ > 0), it is not difficult to show the existence of an optimal parameter without the lower bound. What our very natural conditions provide is existence of optimal interior solution α > 0 to (P) without any additional box constraints or the numerical regularization. Moreover, the conditions (2.2) and (2.3) guarantee convergence of optimal parameters of the numerically regularized H1 problems (Pγ,μ) to a solution of the original BV(Ω) problem (P).

Theorem 2.3 (Total variation Gaussian denoising [39]). Suppose f, f0 ∈ BV(Ω)∩L2(Ω), and

Then there exist μ̄ , γ̄ > 0 such that any optimal solution αγ,μ ∈ [0,∞] to the problem

with

satisfies αγ,μ > 0 whenever μ ∈ [0, μ̄], γ ∈ [γ̄,∞].

This says that if the noisy image oscillates more than the noise-free image f0, then the optimal parameter is strictly positive – exactly what we would naturally expect!

First steps of proof: modeling in the abstract framework. The modeling of total variation is based on the choice of K as the embedding of X = BV(Ω)∩L2(Ω) into Y = L2(Ω), and A1 = D. For the smoothing term we take For the rest of the proof we refer to [39].

Theorem 2.4 (Second-order total generalized variation Gaussian denoising [39]). Suppose that the data f, f0 ∈ L2(Ω) ∩ BV(Ω) satisfies for some α2 > 0 the condition

Then there exists μ̄ , γ̄ > 0 such any optimal solution αγ,μ = ((αγ,μ)1, (αγ,μ)2) to theproblem

with

satisfies (αγ,μ)1, (αγ,μ)2 > 0 whenever μ ∈ [0, μ̄], γ ∈ [γ̄,∞].

Here we recall that BD(Ω) is the space of vector fields of bounded deformation [96]. Again, the noisy data has to oscillate more in terms of TGV2 than the ground-truth does, for the existence of an interior optimal solution to (P). This of course allows us to avoid constraints on α.

Observe that we allow for infinite parameters α.We do not seek to restrict them to be finite, as this will allow us to decide between TGV2, TV, and TV2 regularization.

First steps of proof: modeling in the abstract framework. To present TGV2 in the abstract framework, we take X = (BV(Ω) ∩ L2(Ω)) × BD(Ω), and Y = L2(Ω). We denote u = (υ, w), and set

for E the symmetrized differential. For the smoothing term we take

For more details we again point the reader to [39].

We also have a result on the approximation properties of the numerical models as γ ↗ ∞and μ ↘ 0. Roughly, the outer semicontinuity [87] of the solution map ? in the next theorem means that as the numerical regularization vanishes, any optimal parameters for the regularized models (Pγ,μ) tend to some optimal parameters of the original model (P).

Theorem 2.5 ([39]). In the setting of Theorem 2.3 and Theorem 2.4, there exist γ̄ ∈ (0,∞) and μ̄ ∈ (0,∞) such that the solution map

is outer semicontinuous within [γ̄,∞] × [0, μ̄].

We refer to [39] for further, more general results of the type in this section. These include analogous of the above ones for a novel Huberised total variation cost functional.

8.2.3Optimality conditions

In order to compute optimal solutions to the learning problems, a proper characterization of them is required. Since (Pγ,μ) constitute PDE-constrained optimization problems, suitable techniques from this field may be utilized. For the limit cases, an additional asymptotic analysis needs to be performed in order to get a sharp characterization of the solutions as γ→∞or μ → 0, or both.

Several instances of the abstract problem (Pγ,μ) have been considered in previous contributions. The case with Total Variation regularization was considered in [37] in the presence of several noise models. There the Gâteaux differentiability of the solution operator was proved, which led to the derivation of an optimality system. Thereafter, an asymptotic analysis with respect to γ → ∞was carried out (with μ > 0), obtaining an optimality system for the corresponding problem. In that case the optimization problem corresponds to one with variational inequality constraints and the characterization concerns C-stationary points.

Differentiability properties of higher order regularization solution operators were also investigated in [38]. A stronger Fréchet differentiability result was proved for the TGV2 case, which also holds for TV. These stronger results open the door, in particular, to further necessary and sufficient optimality conditions.

For the general problem (Pγ,μ), using the Lagrangian formalism the following optimality system is obtained:

where V stands for the Sobolev space where the regularized image lives (typically a subspace of H1(Ω;ℝm) with suitable homogeneous boundary conditions), p ∈ V stands for the adjoint state and hγ is a regularized version of the TV subdifferential, for instance,

This optimality system is stated here formally. Its rigorous derivation has to be justified for each specific combination of spaces, regularizers, noise models and cost functionals.

With the help of the adjoint equation (2.5) also gradient formulas for the reduced cost functional ℱ(λ, α) := F(uα,λ , λ, α) are derived:

for i = 1, . . . , M and j = 1, . . . , N, respectively. The gradient information is of numerical importance in the design of solution algorithms. In the case of finite-dimensional parameters, thanks to the structure of the minimizers reviewed in Section 2, the corresponding variational inequalities (2.6) and (2.7) turn into equalities. This has important numerical consequences, since in such cases the gradient formulas (2.9) may be used without additional projection steps. This will be commented on in detail in the next section.

8.3.1Adjoint-based methods

The derivative information provided through the adjoint equation (2.5) may be used in the design of efficient second-order algorithms for solving the bilevel problems under consideration. Two main directions may be considered in this context: Solving the original problem via optimization methods [23, 38, 76], and solving the full optimality system of equations [30, 63]. The main advantage of the first one consists in the reduction of the computational cost when a large image database is considered (this issue will be treated in detail below). When that occurs, the optimality system becomes extremely large, making it difficult to solve it in a manageable amount of time. For a small image database, when the optimality system is of moderate size, the advantage of the second approach consists in the possibility of using efficient (possibly generalized) Newton solvers for nonlinear systems of equations, which have been intensively developed in the last years.

Let us first describe the quasi-Newton methodology considered in [23, 38] and further developed in [38]. For the design of a quasi-Newton algorithm for the bilevel problem with, for example one noise model (λ1 = 1), the cost functional has to be considered in reduced form as ℱ(α) := F (uα, α), where uα is implicitly determined by solving the denoising problem

Using the gradient formula for ℱ,

the BFGS matrix may be updated with the classical scheme

where sk = α(k+1) − α(k), zk = ∇ℱ(α(k+1)) − ∇ℱ(α(k)) and (w ⊗ υ)φ := (υ, φ)w. For the line search strategy, a backtracking rule may be considered, with the classical Armijo criteria

where d(k) stands for the quasi-Newton descent direction and tk the length of the quasi-Newton step. We consider, in addition, a cyclic update based on curvature verification, that is we update the quasi-Newton matrix only if the curvature condition (zk , sk) > 0 is satisfied. The positivity of the parameter values is usually preserved along the iterations, making a projection step superfluous in practice. In more involved problems, like the ones with TGV2 or ICTV denoising, an extra criteria may be added to the Armijo rule, guaranteeing the positivity of the parameters in each iteration. Experiments with other line search rules (like Wolfe) have also been performed. Although these line search strategies automatically guarantee the satisfaction of the curvature condition (see, for example [75]), the interval where the parameter tk has to be chosen appears to be quite small and is typically missing.

The denoising problems (3.1) may be solved either by efficient first- or second-order methods. In previous works we considered primal–dual Newton-type algorithms (either classical or semismooth) for this purpose. Specifically, by introducing the dual variables qi, i = 1, . . . , N, a necessary and sufficient condition for the lower level is given by

where is a regularized version of the TV subdifferential, and the generalized Newton step has the following Jacobi matrix

where L is an elliptic operator, χi(x) is the indicator function of the set {x : γ|Aiu| > 1}and for i = 1, . . . , N. In practice, the convergence neighborhood of the classical method is too small and some sort of globalization is required. Following [53] a modification of the matrix was systematically considered, where the term is replaced by The resulting algorithm exhibits both aglobal and a local superlinear convergent behavior.

For the coupled BFGS algorithm a warm start of the denoising Newton methods was considered, using the image computed in the previous quasi-Newton iteration as initialization for the lower level problem algorithm. The adjoint equations, used for the evaluation of the gradient of the reduced cost functional, are solved by means of sparse linear solvers.

Alternatively, as mentioned previously, the optimality system may be solved at once using nonlinear solvers. In this case the solution is only a stationary point, which has to be verified a posteriori to be a minimum of the cost functional. This approach has been considered in [63] and [30] for the finite- and infinite-dimensional cases, respectively. The solution of the optimality system also presents some challenges due to the nonsmoothness of the regularizers and the positivity constraints.

For simplicity, consider the bilevel learning problem with the TV-seminorm, a single Gaussian noise model and a scalar weight α. The optimality system for the problem reads as follows

where hγ is given by, for example equation (2.8). The Newton iteration matrix for this coupled system has the following form:

The structure of this matrix leads to similar difficulties as for the denoising Newton iterations described above. To fix this and get good convergence properties, Kunisch and Pock [63] proposed an additional feasibility step, where the iterates are projected on the nonlinear constraining manifold. In [30], similarly as for the lower level problem treatment, modified Jacobi matrices are built by replacing the terms in the diagonal, using projections of the dual multipliers. Both approaches lead to a globally convergent algorithm with locally superlinear convergence rates. Also domain decomposition techniques were tested in [30] for the efficient numerical solution of the problem.

By using this optimize-then-discretize framework, resolution-independent solution algorithms may be obtained. Once the iteration steps are well specified, both strategies outlined above use a suitable discretization of the image. Typically a finite differences scheme with mesh size step h > 0 is used for this purpose. The minimum possible value of h is related to the resolution of the image. For the discretization of the Laplace operator the usual five-point stencil is used, while forward and backward finite differences are considered for the discretization of the divergence and gradient operators, respectively. Alternative discretization methods (finite elements, finite volumes, etc) may be considered as well, with the corresponding operators.

8.3.2Dynamic sampling

For a robust and realistic learning of the optimal parameters, ideally, a rich database of K images, K ≫ 1 should be considered (like, for instance, MRI applications, compare Section 8.5.2). Numerically, this consists in solving a large set of nonsmooth PDE-constraints of the form (3.5) and (3.6) in each iteration of the BFGS optimization algorithm (3.3), which renders the computational solution expensive. In order to deal with such large-scale problems various approaches have been presented in the literature. They are based on the common idea of solving not all the nonlinear PDE constraints, but just a sample of them, whose size varies according to the approach one intends to use. Stochastic Approximation (SA) methods ([73, 86]) sample typically a single data point per iteration, thus producing a generally inexpensive but noisy step. In sample or batch average approximation methods (see e.g., [17]) larger samples are used to compute an approximating (batch) gradient: the computation of such steps is normally more reliable, but generally more expensive. The development of parallel computing, however, has improved upon the computational costs of batch methods: independent computation of functions and gradients can now be performed in parallel processors, so that the reliability of the approximation can be supported by more efficient methods.

In [23] we extended to our imaging framework a dynamic sample size stochasticapproximation method proposed by Byrd et al. [18]. The algorithm starts by selecting from the whole dataset a sample S whose size |S| is small compared to the original size K. In the following iterations, if the approximation of the optimal parameters computed produces an improvement in the cost functional, then the sample size is kept unchanged and the optimization process continues selecting in the next iteration a new sample of the same size. Otherwise, if the approximation computed is not a good one, a new, larger, sample size is selected and a new sample S of this new size is used to compute the new step. The key point in this procedure is clearly the rule that checks throughout the progression of the algorithm, whether the approximation we are performing is good enough, that is the sample size is big enough, or has to be increased. Because of this systematic check, such a sampling strategy is called dynamic. In [18,Theorem 4.2] convergence in expectation of the algorithm is shown. Denoting by the solution of (3.5) and (3.6) and by the ground-truth images for every k = 1, . . . , K, we consider now the reduced cost functional ℱ(α) in correspondence of the wholedatabase

and consider, for every sample S ⊂ {1, . . . , K}, the batch objective function:

As in [18], we formulate in [23] a condition on the batch gradient ∇ℱS which imposes in every stage of the optimization that the direction −∇ℱS is a descent direction for ℱ at α if the following condition holds:

The computation of ∇ℱ may be very expensive for applications involving large databases and nonlinear constraints, so we rewrite (3.9) as an estimate of the variance of the batch gradient vector ∇ℱS(α) which reads:

We do not report here the details of the derivation of such an estimate, but we refer the interested reader to [23, Section 2]. In [66] expectation-type descent conditions are used to derive stochastic gradient-descent algorithms for which global convergence in probability or expectation is in general hard to prove.

In order to improve upon the traditional slow convergence drawback of such descent methods, the dynamic sampling algorithm in [18] is extended in [23] by incorporating also second-order information in the form of a BFGS approximation of the Hessian (3.3) by evaluations of the sample gradient in the iterations of the optimization algorithm.

There, condition (3.10) controls in each iteration of the BFGS optimization whether the sampling approximation is accurate enough and, if this is not the case, a new larger sample size may be determined in order to reach the desired level of accuracy, depending on the parameter θ.

Such a strategy can be rephrased in more typical machine-learning terms as a procedure that determines the optimal parameters by validating the robustness of the parameter selection only in correspondence of a training set whose optimal size is computed as above in terms of the quality of batch problem checked by condition (3.10).

8.4.1Total variation-type regularization

The TV is the total variation measure of the distributional derivative of u [3], that is for u defined on Ω

As the seminal work of Rudin, Osher and Fatemi [89] and many more contributions in the image processing community have proven, a nonsmooth first-order regularization procedure such as TV results in a nonlinear smoothing of the image, smoothing more in homogeneous areas of the image domain and preserving characteristic structures such as edges, compare Figure 2. More precisely, when TV is chosen as a regularizer in (1.1) the reconstructed image is a function in BV, the space of functions of bounded variation, allowing the image to be discontinuous as its derivative is defined in the distributional sense only. Since edges are discontinuities in the image function they can be represented by a BV regular image. In particular, the TV regularizer is tunedtowards the preservation of edges and performs very well if the reconstructed image is piecewise constant.

Because one of the main characteristics of images are edges as they define divisions between objects in a scene, the preservation of edges seems like a very good idea and a favorable feature of TV regularization. The drawback of such a regularization procedure becomes apparent as soon as images or signals (in 1D) are considered which do not only consist of constant regions and jumps, but also possess more complicated, higher order structures, for example piecewise linear parts. The artifact introduced by TV regularization in this case is called staircasing [85], compare Figure 3.

One possibility to counteract such artifacts is the introduction of higher order derivatives in the image regularization. Here, we mainly concentrate on two second-order total variation models: the recently proposed Total Generalized Variation (TGV) [9] and the Infimal-Convolution Total Variation (ICTV) model of Chambolle and Lions [25]. We focus on second-order TV regularization only since this is the one that seems to be most relevant in imaging applications [10, 61]. For Ω ⊂ ℝ2 open and bounded, the ICTV regularizer reads

Conversely, second-order TGV [11, 12] reads

Here BD(Ω) := {w ∈ L1(Ω;ℝn) | ‖Ew‖M(Ω;ℝn×n ) < ∞} is the space of vector fields of bounded deformation on Ω, E denotes the symmetrized gradient and Sym2(ℝ2) the space of symmetric tensors of order 2 with arguments in ℝ2. The parameters α, β are fixed positive parameters. The main difference between (4.2) and (4.3) is that we do not generally have that w = ∇υ for any function υ. This results in some qualitative differences of ICTV and TGV regularization, compare for instance [5]. Substituting αR(u) in(1.1) by αTV(u), gives the TV image reconstruction model, TGV image reconstruction model and the ICTV image reconstruction model, respectively. We observe that in (P) a linear combination of regularizers is allowed and, similarly, a linear combination of data fitting terms is admitted (see Section 8.5.3 for more details). As mentioned already in Remark 2.1, more general bilevel optimization models encoding nonlinear modeling in a finite-dimensional setting have been considered, for instance, in [54] for blind deconvolution and recently in [27, 29] for learning the optimal nonlinear filters in several imaging applications.

8.4.2Optimal parameter choice for TV-type regularization

The regularization effect of TV and second-order TV approaches as discussed above heavily depends on the choice of the regularization parameters α (i.e., (α, β) for second-order TV approaches). In Figures 4 and 5 we show the effect of different choices of α and β in TGV2 denoising. In what follows we show some results from [38] applying the learning approach (Pγ,μ) to find optimal parameters in TV-type reconstruction models, as well as a new application of bilevel learning to optimal cartoon-texture decomposition.

Optimal TV, TGV2 and ICTV denoising

We focus on the special case of K = Id and L2-squared cost F and fidelity term Φ as introduced in Section 8.2.2. In [38, 39] we also discuss the analysis and the effect of Huber regularized L1 costs, but this is beyond the scope of this paper and we refer the reader to the respective papers. We consider the problem for finding optimal parameters (α, β) for the variational regularization model

where f is the noisy image, R(α,β) is either TV in (4.1) multiplied by α (then β is obsolete), in (4.3) or ICTV(α,β) in (4.2). We employ the framework of (Pγ,μ) witha training pair (f0, f) of original image f0 and noisy image f, using L2-squared cost As a first example we consider a photograph of a parrot to which we add Gaussian noise such that the PSNR of the parrot image is 24.72. In Figure 6, we plot by the red star the discovered regularization parameter (α∗, β∗) reported in Figure 7. Studying the location of the red star, we may conclude that the algorithm managed to find a nearly optimal parameter in very few BFGS iterations, compare Table 1.

The figure also indicates a nearly quasi-convex structure of the mapping Although no real quasi-convexity can be proven, this is still suggestive that numerical methods can have good performance. Indeed, in all of our experiments, more of which can be found in the original article [38], we have observed commendable convergence behavior of the BFGS-based algorithm.

Generalizing power of the model

To test the generalizing power of the learning model, we took the Berkeley segmentation data set (BSDS300, [69]), resizing each image to a computationally manageable 128 pixels on its shortest edge, and took the 128 × 128 top-left square of the image. To the images, we applied pixelwise Gaussian noise of variance σ = 10. We then split

Table 1: Quantified results for the parrot image (ℓ = 256 = image width/height in pixels).

2

the data set into two halves, each of 100 images. We learned a parameter for each half individually, and then denoised the images of the other half with that parameter. The results for TV regularization with L2 cost and fidelity are in Table 2, and for TGV2 regularization in Table 3. As can be seen, the parameters learned using each half, hardly differ. The average PSNR and SSIM, when denoising using the optimal parameter, learned using the same half, and the parameter learned from the other half, also differ insignificantly. We can therefore conclude that the bilevel learning model has good generalizing power.

Optimizing cartoon-texture decomposition using a sketch

It is not possible to distinguish noise from texture by the G-norm and related approaches [70]. Therefore, learning an optimal cartoon-texture decomposition based on a noise image and a ground-truth image is not feasible. What we did instead, is to make a hand-drawn sketch as our expected “cartoon” f0, and then use the bi-level

Table 2: Cross-validated computations on the BSDS300 data set [69] split into two halves, both of 100 images. Total variation regularization with L2 cost and fidelity. “Learning” and “Validation” indicate the halves used for learning α, and for computing the average PSNR and SSIM, respectively. Noise variance σ = 10.

Table 3: Cross-validated computations on the BSDS300 data set [69] split into two halves, both of 100 images. TGV2 regularization with L2 cost and fidelity. “Learning” and “Validation” indicate the halves used for learning α, and for computing the average PSNR and SSIM, respectively. Noise variance σ = 10.

Table 4: Quantified results for cartoon-texture decomposition of the parrot image (ℓ = 256 = image width/height in pixels).

22

framework to find the true “cartoon” and “texture” as split by the model

for the Kantorovich–Rubinstein norm of [64]. For comparison we also include basic TV regularization results, where we define υ = f − u. The results for two different images are in Figure 8 and Table 4, and Figure 9 and Table 5, respectively.

Table 5: Quantified results for cartoon-texture decomposition of the Barbara image (ℓ = 256 = image width/height in pixels).

8.5.1Variational noise models

From a mathematical point of view, starting from the pioneering work of Rudin, Osherand Fatemi [89], in the case of Gaussian noise a L2-type data fidelity ϕ(u) = (f − u)2 is typically considered. In the case of impulse noise, variational models enforcing the sparse structure of the noise distribution make use of the L1 norm and have been considered, for instance, in [74]. For those models then ϕ(u) = |f −u|. Poisson noise-based models have been considered in several papers by approximating such distribution with a weighted-Gaussian distribution through variance-stabilizing techniques [15, 93]. In [90] a statistically consistent analytical modeling for Poisson noise distributions has been derived: the resulting data fidelity term is the Kullback–Leibler-type functional ϕ(u) = f − u log u.

As a result of different image acquisition and transmission factors, very often in applications the presence of multiple noise distributions has to be considered. Mixed noise distributions can be observed, for instance, when faults in the acquisition of the image are combined with transmission errors to the receiving sensor. In this case a combination of Gaussian and impulse noise is observed. In other applications, specific tools (such as illumination and/or high-energy beams) are used before the signal is actually acquired. This process is typical, for instance, in microscope and Positron Emission Tomography (PET) imaging applications and may result in a combination of a Poisson-type noise and an additive Gaussian noise. In the imaging community, several combinations of the data fidelities above have been considered for this type of problem. In [52], for instance, a combined L1–L2 TV-based model is considered for joint impulse and Gaussian noise removal. A two-phase approach is considered in [19] where two sequential steps with L1 and L2 data fidelity are performed to remove the impulse and the Gaussian component in the noise, respectively. Mixtures of Gaussian and Poisson noise have also been considered. In [57], for instance, the exact log-likelihood estimator of the mixed model is derived and its numerical solution is computed via a primal-dual splitting, while in other works (see, e.g., [44]) the discrete-continuous nature of the model (because of the Poisson–Gaussian component, respectively) is approximated to an additive model by using homomorphic variancestabilizing transformations and weighted-L2 approximations.

We now complement the results presented in Section 8.2.2 and focus on the choice of the optimal noise models ϕi best fitting the acquired data, providing some examples for the single and multiple noise estimation case. In particular, we focus on the estimation of the optimal fidelity weights λi , i = 1, . . . , M appearing in (P) and (Pγ,μ), which measure the strength of the data fitting and stick with the Total-Variation regularization (4.1) applied to denoising problems. Compared to Section 8.2.1, this corresponds to fixing and K = Id. We base our presentation on [23, 37], where a careful analysis in term of well-posedness of the problem and derivation of the optimality system in this framework is carried out.

Shorthand notation

In order not to make the notation too heavy, we warn the reader that we will use a shorthand notation for the quantities appearing in the regularized problem (Pγ,μ), that is we will write ϕi(υ) for the data fidelities ϕi(x, υ), i = 1. . . , M and u for uλ,γ,μ, the minimizer of Jγ,μ(⋅; λ).

8.5.2Single noise estimation

We start considering the one-noise distribution case (M = 1) where we aim to determine the scalar optimal fidelity weight λ by solving the following optimization problem:

subject to (compare (3.1))

where the fidelity term ϕ will change according to the noise assumed in the data and the pair (f0, f) is the training pair composed of a noise-free and noisy version of the same image, respectively.

Previous approaches for the estimation of the optimal parameter λ∗ in the context of image denoising rely on the use of (generalized) cross-validation [103] or on the combination of the SURE estimator with Monte Carlo techniques [83]. In the case when the noise level is known there are classical techniques in inverse problems for choosing an optimal parameter λ∗ in a variational regularization approach, foe example the discrepancy principle or the L-curve approach [42]. In our discussion we do not use any knowledge of the noise level but rather extract this information indirectly from our training set and translate it to the optimal choice of λ. As we will see later such an approach is also naturally extendible to multiple noise models as well as inhomogeneous noise.

Gaussian noise

We start considering (5.1) for determining the regularization parameter λ in the standard TV denoising model assuming that the noise in the image is normally distributed and ϕ(u) = (u − f)2. The optimization problem 5.1 takes the following form:

subject to:

For the numerical solution of the regularized variational inequality we use a primal-dual algorithm presented in [53].

As an example, we compute the optimal parameter λ∗ in (5.2) for a noisy image distorted by Gaussian noise with zero mean and variance 0.02. Results are reported in Figure 10. The optimization result has been obtained for the parameter values μ = 1e − 12, γ = 100 and h = 1/177.

In order to check the optimality of the computed regularization parameter λ∗, we consider the 80 × 80 pixel bottom left corner of the noisy image in Figure 10. InFigure 11 the values of the cost functional and of the Signal-to-Noise Ratio SNR = for parameter values between 150 and 1200, are plotted. Also the cost functional value corresponding to the computed optimal parameter λ∗ = 885.5 is shown with a cross. It can be observed that the computed weight actually corresponds to an optimal solution of the bilevel problem. Here we have used h = 1/80 and the other parameters as above.

The problem presented consists in the optimal choice of the TV regularization parameter, if the original image is known in advance. This is a toy example for proof of concept only. In applications, this image would be replaced by a training set of images.

Robust estimation with training sets

Magnetic Resonance Imaging (MRI) images seem to be a natural choice for our methodology, since a large training set of images is often at hand and used to make the estimation of the optimal λ∗ more robust. Moreover, for this application the noise is often assumed to be Gaussian distributed. Let us consider a training database of clean and noisy images. We modify (5.2) as:

subject to the set of regularized versions of (5.2b), for k = 1, . . . , K.

As explained in [23], dealing with large training sets of images and nonsmooth PDE constraints of the form (5.2b) may result is very high computational costs as, in principle, each constraint needs to be solved in each iteration of the optimization loop. In order to overcome the computational efforts, we estimate λ∗ using the Dynamic Sampling Algorithm 1.

For the following numerical tests, the parameters are chosen as follows: μ = 1e − 12, γ = 100 and h = 1/150. The noise in the images has distribution ?(0, 0.005) and the accuracy parameter θ of Algorithm 1, is chosen to be θ = 0.5.

Table 6 shows the numerical ∗values of the optimal parameter λ∗ and computedvarying N after solving all the PDE constraints and using the Dynamic Sampling algorithm, respectively. We measure the efficiency of the algorithms in terms of the number of the PDEs solved during the whole optimization and we compare the efficiency of solving (5.3) subject to the whole set of constraints (5.2b) with the one where the solution is computed by means of the Dynamic Sampling strategy, observing a clear improvement. Computing also the relative error we also observe a goodlevel of accuracy: the error remains always below 5%. This confirms what was discussed previously in Section 8.3.2, that is the robustness of the estimation of the optimal parameter λ∗ is assessed by selecting a suitable subset of training images whoseoptimal size is validated throughout the algorithm by the check of condition of (3.10)which guarantees an efficient and accurate estimation of the parameter.

Table 6: Optimal λ∗ estimation for large training sets: computational costs are reduced via the Dynamic Sampling Algorithm 1.

Figure 12 shows an example of a database of brain images1together with the optimal denoised version obtained by Algorithm 1 for Gaussian noise estimation.

Poisson noise

As a second example, we consider the case of images corrupted by Poisson noise. The corresponding data fidelity in this case is ϕ(u) = u − f log u [90] and requires the additional condition for u to be strictly positive. We enforce this constraint by using a standard penalty method and solve:

where u is the solution of the minimization problem:

where η ≫ 1 is a penalty parameter enforcing the positivity constraint and δ ≪ 1 ensures strict positivity throughout the optimization. After Huber-regularizing the TV term using (2.2), we write the primal-dual form of the corresponding optimality condition for the optimization problem (5.4) similarly as in (3.5) and (3.6):

where ?δ is the active set ?δ := {x ∈ Ω: u(x) < δ}. We then design a modified SSN iteration solving (5.5) similarly as described in Section 8.3.1, see [37, Section 4] for more details. Figure 13 shows the optimal denoising result for the Poisson noise case in correspondence of the value λ∗ = 1013.76.

Spatially dependent weight

We continue with an example where λ is spatially dependent. Specifically, we choose as parameter space V = {υ ∈ H1(Ω) : ∂nu = 0 on Γ} in combination with a TV regularizer and a single Gaussian noise model. For this example the noisy image is distorted nonuniformly: A Gaussian noise with zero mean and variance 0.04 is present on the whole image and an additional noise with variance 0.06 is added on the area marked by a red line.

Since the spatially dependent parameter does not allow one to get rid of the positivity constraints in an automatic way, we solved the whole optimality system by means of the semismooth Newton method described in Section 3, combined with a Schwarz domain decomposition method. Specifically, we decomposed the domain first and applied the globalized Newton algorithm in each subdomain afterwards. The detailed numerical performance of this approach is reported in [30].

The results are shown in Figure 14 for the parameters μ = 1e − 16, γ = 25 and h = 1/500. The values of λ on the whole domain are between 100.0 to 400.0. From the right image in Figure 14 we can see the dependence of the optimal parameter λ∗ on the distribution of noise. As expected, at the high-level noise area in the input image, values of λ∗ are lower (darker area) than in the rest of the image.

8.5.3Multiple noise estimation

We now deal with the case of multiple noise models and consider the following optimization lower level problem:

where the modeling function Ψ combines the different fidelity terms ϕi and weights λi in order to deal with the multiple noise case. The case when Ψ is a linear combination of fidelities ϕi with coefficients λi is the one presented in the general model (P) and (Pγ,μ) and has been considered in [23, 37]. In the following, we present also the case considered in [21, 22] of Ψ being a nonlinear function modeling data fidelity terms in an infimal convolution fashion.

Impulse and Gaussian noise

Motivated by some previous work in literature on the use of the infimal-convolution operation for image decomposition, cf. [16, 25], we consider in [21, 22] a variational model for mixed noise removal combining classical data fidelities in such fashion with the intent of obtaining an optimal denoised image thanks to the decomposition of the noise into its different components. In the case of combined impulse and Gaussian noise, the optimization model reads:

where u is the solution of the optimization problem:

where w represents the impulse noise component (and is treated using the L1 norm) and the optimization runs over υ and w, see [22]. We use a single training pair (f0, f) and consider a Huber-regularization depending on a parameter γ for both the TV term and the L1 norm appearing in (5.6). The corresponding Euler–Lagrange equations are:

Again, writing the equations above in a primal-dual form, we can write the modified SSN iteration and solve the optimization problem with BFGS as described in Section 8.3.1.

In Figure 15 we present the results of the model considered. The original image f0 has been corrupted with Gaussian noise of zero mean and variance 0.005 and then a percentage of 5% of pixels has been corrupted with impulse noise. The parameters have been chosen to be γ = 1e4, μ = 1e − 15 and the mesh step size h = 1/312. The computed optimal weights are and Together with an optimal denoised image, the results show the decomposition of the noise into its sparse and Gaussian components, see [22] for more details.

Gaussian and Poisson noise

We consider now the optimization problem with ϕ1(u) = (u − f)2 for the Gaussian noise component and ϕ2(u) = (u − f log u) for the Poisson one. We aim to determine the optimal weighting (λ1, λ2) as follows:

subject to u be the solution of:

for one training pair (f0, f), where f corrupted by Gaussian and Poisson noise. After Huber-regularizing the Total Variation term in (5.7), we derive (formally) the following Euler–Lagrange equation

with nonnegative Lagrange multiplier α ∈ L2(Ω). As in [90] we multiply the first equation by u and obtain

where we have used the complementarity condition α ⋅ u = 0. Next, the solution u is computed iteratively by using a semismooth Newton-type method combined with the outer BFGS iteration as above.

In Figure 16 we show the optimization result. The original image f0 has been first corrupted by Poisson noise and then Gaussian noise was added, with zero mean and variance 0.001. Choosing the parameter values to be γ = 100 and μ = 1e − 15, the optimal weights and were computed on a grid with mesh size step h = 1/200.