Relations Between Regularization and Diffusion Filtering.
Regularization may be regarded as diffusion filtering with an discretization where one single step is used. Thus, iterated regularization with small regularization parameters approximates a diffusion process. The goal of this paper is to analyse relations between noniterated and iterated regularization and diffusion filtering in image processing. In the linear regularization framework, we show that with iterated Tikhonov regularization noise can be better handled than with noniterated. In the nonlinear framework, two filtering strategies are considered: the total variation regularization technique and the diffusion filter technique of Perona and Malik. It is shown that the Perona-Malik equation decreases the total variation during its evolution. While noniterated and iterated total variation regularization is well-posed, one cannot expect to find a minimizing sequence which converges to a minimizer of the corresponding energy functional for the PeronaMalik filter. To overcome this shortcoming, a novel regularization technique of the PeronaMalik process is presented that allows to construct a weakly lower semi-continuous energy functional. In analogy to recently derived results for a well-posed class of regularized PeronaMalik filters, we introduce Lyapunov functionals and convergence results for regularization methods. Experiments on real-world images illustrate that iterated linear regularization performs better than noniterated, while no significant differences between noniterated and iterated total variation regularization have been observed.
Introduction
Image restoration is among other topics such as optic flow, stereo, and shape-from-
shading one of the classical inverse problems in image processing and computer vision
[4]. The inverse problem of image restoration consists in recovering information about
the original image from incomplete or degraded data. Diffusion filtering has become a
popular and well-founded tool for restoration in the image processing community [25, 50],
while mathematicians have unified most techniques to treat inverse problems under the
theory of regularization methods [14, 19, 30, 44]. Therefore it is natural to investigate
relations between both approaches, as this may lead to a deeper understanding and a
synthesis of these techniques. This is the goal of the present paper.
We can base our research on several previous results. In the linear setting, Torre
and Poggio [45] emphasized that differentiation is ill-posed in the sense of Hadamard,
and applying suitable regularization strategies approximates linear diffusion filtering or -
equivalently - Gaussian convolution. Much of the linear scale-space literature is based on
the regularization properties of convolutions with Gaussians. In particular, differential
geometric image analysis is performed by replacing derivatives by Gaussian-smoothed
derivatives; see e.g. [16, 29, 42] and the references therein. In a very nice work, Nielsen
et al. [31] derived linear diffusion filtering axiomatically from Tikhonov regularization,
where the stabilizer consists of a sum of squared derivatives up to infinite order.
In the nonlinear diffusion framework, natural relations between biased diffusion and
regularization theory exist via the Euler equation for the regularization functional. This
Euler equation can be regarded as the steady-state of a suitable nonlinear diffusion
process with a bias term [34, 41, 9]. The regularization parameter and the diffusion
time can be identified if one regards regularization as time-discrete diffusion filtering
with a single implicit time step [43, 39]. A popular specific energy functional arises
from unconstrained total variation denoising [1, 8, 6]. Constrained total variation also
leads to a nonlinear diffusion process with a bias term using a time-dependent Lagrange
multiplier [38].
In spite of these numerous relations, several topics have not been addressed so far in
the literature:
ffl A comparison of the restoration properties of both approaches: Since regularization
corresponds to time-discrete diffusion filtering with a single time step, it follows
that iterated regularization with a small regularization parameter gives a better
approximation to diffusion filtering. An investigation whether iterated regularization
is better than noniterated leads therefore to a comparison between regularization
and diffusion filtering.
ffl Energy formulations for stabilized Perona-Malik processes: The Perona-Malik
filter is the oldest nonlinear diffusion filter [36]. Its ill-posedness has triggered
many researchers to introduce regularizations which have shown their use for image
restoration. However, no regularization has been found which can be linked to the
minimization of an appropriate energy functional.
ffl Lyapunov functionals for regularization: The smoothing and information-reducing
properties of diffusion filters can be described by Lyapunov functionals such as
decreasing L p norms, decreasing even central moments, or increasing entropy [50].
They constitute important properties for regarding diffusion filters as scale-spaces.
A corresponding scale-space interpretation of regularization methods where the
regularization parameter serves as scale parameter has been missing so far.
These topics will be discussed in the present paper. It is organized as follows. Section
2 explains the relations between variational formulations of diffusion processes and regularization
strategies. In Section 3 we first discuss the noise propagation for noniterated
and iterated Tikhonov regularization for linear problems. In the nonlinear framework,
well-posedness results for total variation regularization are reviewed and it is explained
why one cannot expect to establish well-posedness for the Perona-Malik filter. We will
argue that, if the Perona-Malik filter admits a smooth solution, however, then it will
be total variation reducing. A novel regularization will be introduced which allows to
construct a corresponding energy functional. Section 4 establishes Lyapunov functionals
for regularization methods which are in accordance with those for diffusion filtering. This
leads to a scale-space interpretation for linear and nonlinear regularization. In Section
5 we shall present some experiments with noisy real-world images, which compare the
restoration properties of noniterated and iterated regularization in the linear setting and
in the nonlinear total variation framework. Moreover, the novel Perona-Malik regularization
is juxtaposed to the regularization by Catt'e et al. [5]. The paper will be
concluded with a summary in Section 6.
Variational formulations of diffusion processes and
the connection to regularization methods
We consider a general diffusion process of the
on\Omega \Theta (0; 1[
Here g is a smooth function satisfying certain properties which will be explained in the
course of the
paper;\Omega ' R d is a bounded domain with piecewise Lipschitzian boundary
with unit normal vector n, and f ffi is a degraded version of the original image f := f
For the numerical solution of (2.1) one can use explicit or implicit or semi-implicit difference
schemes with respect to t.
The implicit scheme reads as
Here h ? 0 denotes the step-size in t-direction of the implicit difference scheme.
In the following we assume that g is measurable on [0; 1[ and there exists a differentiable
function - g on [0; 1) which satisfies -
g. Then the minimizer of the functional (for
given u(x; t))
Z
\Omega
satisfies (2.2) at time t + h. If the functional T is convex, then a minimizer of T is
uniquely characterized by the solution of the equation (2.2) with homogeneous Neumann
boundary conditions.
T (u) is a typical regularization functional consisting of the approximation functional
and the stabilizing functional
The weight h is called regularization
parameter. The case -
called regularization.
In the next section we summarize some results on regularization and diffusion filtering
and compare the theoretical results developed in both theories.
3 A survey on diffusion filtering and regularization
We have seen that each time step for the solution of the diffusion process (2.1) with
an implicit, t-discrete scheme is equivalent to the calculation of the minimizer of the
regularization functional (2.3). The numerical solution of the diffusion process with
an implicit, t-discrete iteration scheme is therefore equivalent to iterated regularization
where on has to minimize iteratively the set of functionals
Z
\Omega
Here u n is a minimizer of the functional T . If the functionals
T n are convex, then the minimizer of (3.1) denoted by u n is the approximation of the
solution of the diffusion process with an implicit, t-discrete method at time t
In the following we refer to iterated regularization if h That corresponds
to the solution of the diffusion process with an implicit, t-discrete method using a fixed
time step size
If the regularization parameters h n are adaptively chosen (this corresponds to the situation
that the time discretization in the diffusion process is changed adaptively), then the
method is called nonstationary regularization. For some recent results on nonstationary
Tikhonov regularization we refer to Hanke and Groetsch [24]; however, their results do
not fit directly into the framework of this paper. They deal with regularization methods
for the stable solution of operator equations
where I is a linear bounded operator from a Hilbert space X into a Hilbert space Y , and
they use nonstationary Tikhonov regularization
for the stable solution of the operator equation (3.2).
3.1 propagation of Tikhonov regularization with linear
unbounded operators
In this subsection we consider the problem of computing values of an unbounded operator
L. We will always denote by densely defined unbounded
linear operator between two Hilbert spaces H 1 and H 2 . A typical example is
The problem of computing values ill-posed in the sense
that small perturbations in f 0 may lead to data f ffi satisfying
but f
2 D(L), or even if f may happen that Lf ffi 6! Lf 0 as
the operator L is unbounded. Morozov has studied a stable method for approximating
the value Lf 0 when only approximate data f ffi is available [30]. This method takes as an
approximation to the vector y ffi
h minimizes the functional
over D(L).
The functional is strictly convex and therefore if D(L) is nonempty and convex there
exists a unique minimizer of the functional T TIK (u). Thus the method is well-defined.
For more background on the stable evaluation of unbounded operators we refer to [20].
Let then the sequence fu n g n-1 of minimizers of the family of
optimization problems
are identical to the semi-discrete approximations of the differential equation (2.1) at time
This shows
Methods for evaluating unbounded operators can be used for diffusion filtering
and vice versa. However the motivations differ: For evaluating unbounded
operators we solve the optimization and evaluate in a further step the unbounded
operator. In diffusion filtering we "only" have to solve the optimization
problem.
In the following we compare the error propagation in Tikhonov regularization with regularization
parameter h and the error propagation in iterated Tikhonov regularization of
order N with regularization parameter h=N . This corresponds to making an implicit,
t-discrete ansatz for a diffusion process with one step h and an implicit, t-discrete ansatz
with N steps of step h=N , respectively.
Tikhonov regularization with regularization parameter h reads as follows
where L   is the adjoint operator to L (see e.g. [47] for more details). Tikhonov regularization
of order N with regularization parameter h=N reads as follows
I
Let L   L be an unbounded operator with spectral values
such that - n !1 as n !1. Then
I
I
I
I
denotes the propagated error of the initial data f ffi , which remains
in uN - this corresponds to the error propagation in diffusion filtering with an implicit,
t-discrete method.
be the spectral family according to the operator L   L. Then it follows that [47]
I
Z 1/
Using /
N!/
we get that
I
In noniterated Tikhonov regularization the error propagation is
For large values of - (i.e., for highly oscillating noise) the term (1 in (3.7) is
significantly larger than the term
in (3.6).
This shows that noise propagation is handled more efficiently by iterated Tikhonov regularization
than by Tikhonov regularization.
Above we analyzed the error of the (iterated) Tikhonov regularized solutions and not the
error in evaluating L at the Tikhonov regularized solutions. We emphasize that the less
noise is contained in a data set the better the operator L can be evaluated. Therefore
we conclude that the operator L can be evaluated more accurately with the method of
iterated Tikhonov regularization than with noniterated Tikhonov regularization. This
will be confirmed by the experiments in Section 5.
3.2 Well-posedness of regularization with nonlinear unbounded
operators
In this subsection we discuss some theoretical results on regularization with nonlinear
unbounded operators.
3.2.1 Well-posedness and convergence for total variation regularization
Total variation regularization goes back to Rudin, Osher and Fatemi [38] and has been
further analysed by many others, e.g. [1, 7, 6, 8, 12, 13, 27, 28, 43, 40, 46]. In the
unconstrained formulation of this method the data f 0 is approximated by the minimizer
of the functional over
the space of all functions with finite total variation norm
where TV(u) :=
R
\Omega jruj and
Z
\Omega
Z
\Omega
This expression extends the usual definition of the total variation for smooth functions
to functions with jumps [22].
It is easy to see that a smooth minimizer of the functional T
Acar and Vogel [1] proved the following results concerning existence of a minimizer of
(3.8) and concerning stability and convergence of the minimizers:
Theorem 3.1 (Existence of a minimizer) Let f
minimizer u h 2 TV(\Omega\Gamma of (3.8) exists and is unique.
Theorem 3.2 (Stability) Let f
with respect to the L p -norm (1 -
is the minimizer of (3.8) and
is the minimizer of (3.8) where f ffi is replaced by f 0 .
Theorem 3.3 (Convergence) Let f
Then for h := h(ffi) satisfying
with respect to the L p -norm (1 -
It is evident that analogous results to Theorem 3.1, Theorem 3.2 and 3.3 also hold for
the minimizers of the iterated total variation regularization which consists of minimizing
a sequence of functionals
Z
\Omega
denotes the minimizer of the functional
This regularization technique corresponds to the implicit, t-discrete approximation of
the diffusion process (2.1) with -
x.
3.2.2 The Perona-Malik filter
In the Perona-Malik filter [36] we have
1+s and -
Perona-Malik regularization minimizes the family of functionals
Z
\Omega
The functionals T n
PM are not convex and therefore we cannot conclude that the minimizer
of (3.11) (it it exists) satisfies the first order optimality conditionh
with homogeneous Neumann boundary data.
In the following we comment on some aspects of the Perona-Malik regularization tech-
nique. For the definitions of the Sobolev spaces W l;p and the notion of weak lower
semi-continuity we refer to [2].
1. Neumann boundary conditions:
Let\Omega be a domain with smooth boundary @
Using trace theorems (see e.g. [2]) it follows that the Neumann boundary data are
well-defined in L 2 (@
\Omega\Gamma for any function in W 3;2(\Omega\Gamma4 Suppose we could prove that
there exists a minimizer of the functional T n
PM , then this minimizer must satisfy
Z
\Omega
Elementary calculations show that any function u
(3.13). Therefore we cannot deduce from (3.13) that the minimizer is in any
Sobolev space W 1;p
1). Consequently, there exists no theoretical result
that the Neumann boundary conditions are well-defined.
2. Existence of a minimizer of the functional T n
convex, and therefore the functional T n
PM (u) is not weakly lower semi-continuous
on W 1;p
Therefore, there exists a sequence u k 2 W 1;p
(\Omega\Gamma with u k * u in W
1;p(\Omega\Gamma4 but
Consequently, we cannot expect that a minimizing sequence converges (in W
to a minimizer of the functional T n
PM . Thus the solution of the Perona-Malik
regularization technique is ill-posed on W
The diffusion process associated with the Perona-Malik regularization technique is
The Perona-Malik diffusion filtering technique can be split up in a natural way into a
forward and a backward diffusion process:
Here
Both functions a and b are non-negative. In general the solution of a backward diffusion
equation is severely ill-posed (see e.g. [14]). We argue below that this nonlinear backward
diffusion is well-posed with respect to appropriate norms. In fact we argue that the
backward diffusion equation
satisfies
The intuitive reason for the validity of this is the following: Let v 2 C
2(\Omega \Theta [0; T ]) then
Using (3.17), (3.15), and integration by parts it follows that
R
R\Omega rv
R\Omega r:
\Deltav
2(\Omega \Theta [0; T ]) then the right hand side tends to zero as fi ! 0. These arguments
indicate that
Z
\Omega
Consequently the total variation of v(:; t) does not change in the course of the evolutionary
process (3.17). Indeed, (3.15) may be regarded as a total variation preserving
shock filter in the sense of Osher and Rudin [35].
The diffusion process
is a forward diffusion process which decreases the total variation during the evolution.
In summary we have argued that the Perona-Malik diffusion equation decreases the total
variation during the evolutionary process.
3.2.3 A regularized Perona-Malik filter
Although the ill-posedness of the Perona-Malik filter can be handled by applying regularizing
finite difference discretizations [51], it would be desirable to have a regularization
which does not depend on discretization effects. In this subsection we study a regularized
Perona-Malik filter
Z
\Omega
where L fl is linear and compact from L
(\Omega ). The applications which we have
in mind include the case that L fl is a convolution operator with a smooth kernel.
In the following we prove that the functional T n
R-PM attains a minimium:
Theorem 3.4 The functional T n
R-PM is weakly lower semi continuous on L
.
Proof: Let fu s : s 2 Ng be a sequence in L
which satisfies
Then fu s g has a weakly convergent subsequence (which is again denoted by fu s g) with
limit u. Since L fl is compact from L
(\Omega ) the sequence
converges uniformly to In particular, we have
Z
\Omega
Z
\Omega
Using the weak lower semi-continuity of the norm k:k L
it follows that the functional
R-PM is weakly lower semi-continuous. q.e.d.
The minimizer of the regularized Perona-Malik functional satisfies
The corresponding nonlinear diffusion process associated with this regularization technique
is
Regularized Perona-Malik filters have been considered in the literature before [3, 5, 32,
48, 50]. Catt'e et al. [5] for instance investigated the nonlinear diffusion process
This technique (as well as other previous regularizations) does not have a corresponding
formulation as an optimization problem. The differences between (3.20) and (3.21) will
be explained in Section 5.
4 Lyapunov functionals for regularization methods
play an important role in continuous diffusion filtering (see [49,
50]). In order to introduce Lyapunov functionals of regularization methods, we first give
a survey on Lyapunov functionals in diffusion filtering. We consider the diffusion process
(here and in the
will be a domain with piecewise smooth boundary)
on\Omega \Theta (0; T )
We assume that the following assumptions hold:
(\Omega\Gamma3 with a := ess inf
x2\Omega f and b := ess sup
x2\Omega f .
2. L fl is a compact operator from L
into C p (\Omega\Gamma for any p 2 N .
3. T ? 0:
4. For all w 2 L
on\Omega , there exists a positive lower bound
-(K) for g.
The regularizing operator L fl may be skipped in (4.1), if one assumes that -
convex from R d to R. Moreover, it is also possible to generalize (4.1) to the anisotropic
case where the diffusivity g is replaced by a diffusion tensor [50].
Under the preceding assumptions it can be shown that (4.1) is well-posed (see [5, 50]):
Theorem 4.1 The equation (4.1) has a unique solution u(x; t) which satisfies
Moreover,
(\Omega \Theta [0; T
The solution fulfills the extremum principle
a - u(x;
on\Omega \Theta (0; T ]:
For fixed t the solution depends continuously on f with respect to k:k L 2
.
This diffusion process leads to the following class of Lyapunov functionals [50]:
Theorem 4.2 Suppose that u is a solution of (4.1) and that assumptions 1 - 4 are
satisfied. Then the following properties hold
(a) (Lyapunov functionals) For all r 2 C 2 [a; b] with r 00 - 0 on [a; b], the function
Z
\Omega
is a Lyapunov functional:
1.
Z
\Omega
2.
Moreover, if r 00 ? 0 on [a; b], then V is a strict Lyapunov functional:
3. only if
a.e.
4. If t ? 0, then V 0 only if
on\Omega .
5.
on\Omega and
on\Omega \Theta (0; T ].
(b) (Convergence)
1. lim t!1
2.
If\Omega ' R, then the convergence lim t!1 u(x;
In the sequel we introduce Lyapunov functionals of regularization methods.
In the beginning of this section we discuss existence and uniqueness of the minimizer of
the regularization functional in H
Z
\Omega
Lemma 4.3
Let\Omega ' R d , d - 1. Moreover, let - g satisfy:
g(:) is in C 0 (K) for any compact K ' [0; 1[
is convex from R d to R :
Moreover, we assume that there exists a constant c ? 0 such that
Then the minimizer of (4.6) exists and is unique in H
.
Proof: By virtue of (4.9) it follows that
Z
\Omega
Z
\Omega
Suppose now that u n is a sequence such that I(u n ) converges to the minimum of the
functional I(:) in H 1
(\Omega\Gamma7 From (4.10) it follows that u n has a weakly convergent subsequence
in H 1
(\Omega\Gamma3 which we also denote by u n ; the weak limit will be denoted by u   . Since
the functional
lower semi continuous in H
(see
[11, 10]), and thus Z
\Omega
Z
\Omega
Thanks to the the Sobolev embedding theorem (see [2]) it follows that the functional
is weakly lower semi continuous on H
Consequently
and thus u   is a minimizer of I in H
1(\Omega\Gamma5 Suppose now that u 1 and u 2 are two minimizers
of the functional I. Then, from the optimality condition it follows that
(4.
And thus the minimizer of I is unique. q.e.d
The minimizer of (4.6) will be denoted by u h in the remaining of this paper.
In the following we establish the average grey level invariance of regularization methods.
Theorem 4.4 Let (4.7), (4.8), (4.9) hold. Then for different values of h the minimizers
of (4.6) are grey-level invariant, i.e., for h ? 0
Z
\Omega
Z
\Omega
Proof: Elementary calculations show that the minimizer of (4.6) satisfies for all v 2
Taking the second term vanishes and the assertion follows. q.e.d.
In the following we establish some basic results on regularization techniques. As we will
show the proofs of the following results can be carried out following the ideas of the
corresponding results in the book of Morozov [30]. However Morozov's results can not
be applied directly since they are only applicable in the case that - g(jxj 2 which is
not sufficient for the presentation of this paper. Later these results are used to establish
a family of Lyapunov functionals for regularization methods.
Lemma 4.5 Let (4.7), (4.8), (4.9) hold. Then for any h ? 0
and for
Proof: If - g(j:j 2 ) is convex, then g(jsj 2 )s is monotone (see e.g. [11]), i.e., for all s; t 2 R d
1. First we consider the case h ? 0: from (4.13) it follows by using the notation
that
Thus using the Cauchy-Schwarz inequality and the identity (4.14) it follows that
which shows the continuity of u h .
2. If There exists a sequence f n 2 H
Consequently
for any h ? 0 it follows from the definition of a minimum of the Tikhonov-like
functional it follows that
Z
\Omega
Consequently by taking the limit h ! 0 it follows that for any n 2 N
lim
which shows the assertion.
q.e.d.
In the following we present some monotonicity results for the regularized solutions.
Lemma 4.5 implies that we can set u causing any confusion.
Lemma 4.6 Let (4.7), (4.8), (4.9) hold. Then
monotonically decreasing
in h and ku monotonically increasing in h.
Proof: Using the definition of the regularized solution it follows
Z
\Omega
Z
\Omega
Z
\Omega
Z
\Omega
'Z
\Omega
Z
\Omega
and therefore, for t ? 0,
Z
\Omega
Z
\Omega
This shows the monotonicity of the functional
Using very similar arguments
it can be shown that ku
(\Omega\Gamma is monotonically increasing in h. q.e.d.
In the following we analyze the behaviour of the functionals
Lemma 4.7 Let (4.7), (4.8), (4.9) hold. Then, for h ! 1 the regularized solution
converges (with respect to the L 2 -norm) to the solution of the optimization problem
under the constraint Z
\Omega
Proof: The proof is similar to the proof in the book of Morozov [30] (p.35) and thus
omitted. q.e.d.
In the following lemma we establish the boundedness of the regularized solution. For
the proof of this result we utilize Stampacchia's Lemma (see [23]).
Lemma 4.8 Let B be an open domain, u a function in H 1 (B) and a a real number.
Then u
Z
Z
We are using this result to prove that each regularized solution lies between the minimal
and maximal value of the data f .
Lemma 4.9 Let (4.7), (4.8), (4.9) hold. Moreover, let
- g be monotone in [0; 1[:
, then for any h ? 0 the regularized solution satisfies
a := ess
Proof: We verify that the maximum of u h is less than b. The corresponding assertion
for the minimum values can be proven analogously. Let u b
g, then from
Lemma 4.8 and the assumption (4.15) it follows that
Z
\Omega
Z
\Omega
Since
it follows from the definition of a regularized solution that u h (x) - b. q.e.d.
Next we establish the announced family of Lyapunov functionals.
Theorem 4.10
be as in (4.16). Morover, let (4.7),
(4.8), (4.9), and (4.15) be satisfied. Suppose that u h is a solution of (4.6). Then the
following properties hold
(a) (Lyapunov functionals for regularization methods) For all r 2 C 2 [a; b] with r 00 - 0,
the function
Z
\Omega
is a Lyapunov functional for a regularization method: Let
Z
\Omega
Then
1.
2.
Moreover, if r 00 ? 0 on [a; b], then V strict Lyapunov functional:
3. OE(u h only if u
on\Omega .
4. if h ? 0, then DV only if u
on\Omega .
5. V
on\Omega and u
\Omega \Theta (0; H]:
(b) (Convergence)
d=1: u h converges uniformly to Mf for h !1
d=2: lim
d=3: lim
Proof:
(a) 1. Since r 2 C 2 [a; b] with r 00 - 0 on [a; b], we know that r is convex on [a; b].
Using the gray level invariance and Jensen's inequality it follows
R\Omega r
R\Omega u h (x) dx
dy
R\Omega u h (x) dx) dy
2. From Lemma 4.5 it follows that V 2 C[0; 1[. Setting
from (4.13) and (4.8) that
The right hand side is negative since r is convex.
We represent in the following way
\Omega
R
\Omega
R
\Omega
From (4.19) and the convexity of r it follows that the last two terms in the
above chain of inequalities are negative. Thus the assertion is proved.
3. Let OE(u h us now show that the estimate (4.18) implies that
const on \Omega\Gamma Suppose that u h 6= c Since u h 2 H
1(\Omega\Gamma2 there exists a
j\Omega
Z
Z
This assertion follows from the Poincare inequality for functions in Sobolev
spaces [15]. From the strict convexity of r it follows that
r
R
\Omega u h dx
If we utilize this result in (4.18) we observe that for h ? 0 OE(u h
implies that u const
on\Omega . Thanks to the average grey value invariance
we finally obtain u
on\Omega .
We turn to the case From (1.) and (2.) it follows that
If
Thus we have that for all ' ? 0 . Using the continuity of u ' with
respect to ' 2 [0; 1[ (cf. Lemma 4.5) the assertion follows.
4. The proof is analogous to the proof of the (iv)-assertion in Theorem 3 in [50].
5. Suppose that V (0), then from (2.) it follows that
const on [0; H] :
it follows from (4.) that u Using
the continuity of u h with respect to h 2 [0; 1[ (cf. Lemma 4.5) the assertion
follows. The converse direction is obvious.
(b) From Lemma 4.7 and assumption 4.9 it follows that
Z
\Omega
This shows that
From the Sobolev embedding theorem it follows in particular that for h !1
d=1: u h converges uniformly to Mf
(note that we assumed
that\Omega is
bounded domain)
(note that we assumed
that\Omega is
bounded domain).
q.e.d.
In Theorem 4.10 we obtained similar results as for Lyapunov functional of diffusion
operators (see [50]). In (2.) of Theorem 4.10 the difference of Lyapunov functionals for
diffusion processes and regularization methods becomes evident. For Lyapunov functionals
in diffusion processes we have V 0 (t) - 0 and in regularization processes we have
is obtained from V 0 (t) by making a time discrete ansatz at time 0.
We note that this is exactly the way we compared diffusion filtering and regularization
techniques in the whole paper. It is therefore natural that the role of the time derivative
in diffusion filtering is replaced by the time discrete approximation around 0.
Example 4.11 In this example we study different regularization techniques which have
been used for denoising of images:
1. Tikhonov regularization: Here we have - g(juj 2 . In this case the assumptions
(4.7), (4.8), (4.9) and (4.15) are satisfied.
2. total variation Regularization: Here we have - g(juj 2
In this case the
assumption (4.9) is not satisfied.
However, for the modified versions, proposed by Ito and Kunisch [27], where the
functional is replaced by
(4.7), (4.8), (4.9), and (4.15) are satisfied.
For the functional [1, 9]
the assumption (4.9) is not satisfied. For the modified version
studied in [33], the assumptions (4.7), (4.8), (4.9), and (4.15) are satisfied.
For the functional
the assumptions (4.7), (4.8), (4.9), and (4.15) are satisfied. This method has been
proposed by Geman and Yang [17] and was studied extensively by Chambolle and
Lions [8] (see also [33]).
3. Convex Nonquadratic Regularizations: The functional used by Schn-orr [41]
l
l )c ae
satisfies (4.7), (4.8), (4.9), and (4.15), whereas the Green functional [18]
violates the assumption (4.9).
5 Experiments
In this section we illustrate some of the previous regularization strategies by applying
them to noisy real-world images.
Regularization was implemented by using central finite differences. In the linear case
this leads to a linear system of equations with a positive definite system matrix. It
was solved iteratively by a Gau-Seidel algorithm. It is not difficult to establish error
bounds for its solution, since the residue can be calculated and the condition number of
the matrix may be estimated using Gerschgorin's theorem. The Gau-Seidel iterations
were stopped when the relative error in the Euclidean norm was smaller than 0:0001.
Discretizing stabilized total variation regularization with
leads to a nonlinear system of equations. It was numerically solved for
combining convergent fixed point iterations as outer iterations [13] with inner iterations
using the Gau-Seidel algorithm for solving the linear system of equations. The fixed
point iteration turned out to converge quite rapidly, such that not more than 20 iterations
were necessary.

Figure

5.1 shows three common test images and a noisy variant of each of them:
an outdoor scene with a camera, a magnetic resonance (MR) image of a human head,
and an indoor scene. Gaussian noise with zero mean has been added. Its variance was
chosen to be a quarter, equal and four times the image variance, respectively, leading to
signal-to-noise (SNR) ratios of 4, 1, and 0.25.
The goal of our evaluation was to find out which regularization leads to restorations
which are closest to the original images. We applied linear and total variation regularization
to the three noisy test images, used 1, 4, and 16 regularization steps and varied
the regularization parameter until the optimal restoration was found. The distance to
the original image was computed using the Euclidean norm. The results are shown in

Table

1, as well as in Figs. 5.2 and 5.3. This gives rise to the following conclusions:
ffl In all cases, total variation regularization performed better than Tikhonov regular-
ization. As expected, total variation regularization leads to visually sharper edges.
The TV-restored images consist of piecewise almost constant patches.
ffl In the linear case, iterated Tikhonov regularization produced better restorations
than noniterated. Visually, noniterated regularization resulted in images with more
high-frequent fluctuations. This is in complete agreement with the theoretical
considerations in our paper. Improvements caused by iterating the regularization
were mainly seen between 1 and 4 iterations. Increasing the iteration number to 16
did hardly lead to further improvements, in one case the results were even slightly
worse.
ffl It appears that the theoretical and experimental results in the linear setting do
not carry over to the nonlinear case with total variation regularization: regularization
was extremely robust: different iteration numbers gave similar results,
and the optimal total regularization parameter did not depend much on the iteration
number. Thus, in practice one should give the preference to the faster
method. In our case iterated regularization was slightly more efficient, since it
led to matrices with smaller condition numbers and the Gau-Seidel algorithm
converged faster. Using for instance multigrid methods, which solve the linear
systems with a constant effort for all condition numbers, would make noniterated
total variation regularization favourable.
In a final experiment we juxtapose the regularizations (3.20) and (3.21) of the Perona-Malik
filter. Both processes have been implemented using an explicit finite difference
scheme. The results using the MR image from Figure 5.1(c) are shown in Figure 5.4,
where different values for fl, the standard deviation of the Gaussian, have been used. For
small values of fl, both filters produce rather similar results, while larger values lead to
a completely different behaviour. For (3.20), the regularization smoothes the diffusive
flux, so that it becomes close to 0 everywhere, and the image remains unaltered. The
regularization in (3.21), however, creates a diffusivity which gets closer to 1 for all image
locations, so that the filter creates blurry results resembling linear diffusion filtering.
6

Summary

The goal of this paper was to investigate connections between regularization theory
and the framework of diffusion filtering. The regularization methods we considered were
Tikhonov regularization, total variation regularization, and we focused on linear diffusion
filters as well as regularizations of the nonlinear diffusion filter of Perona and Malik. We
have established the following results:
ffl We analyzed the restoration properties of iterated and noniterated regularization
both theoretically and experimentally. While linear regularization can be improved
by iteration, there is no clear evidence that this is also the case in the nonlinear
setting.
ffl We introduced an alternative regularization of the Perona-Malik filter. In contrast
to previous regularization, it allows a formulation as a minimizer of a suitable
energy functional.
ffl We have established Lyapunov functionals and convergence results for regularization
methods using a similar theory as for nonlinear diffusion filtering.
These results can be regarded as contributions towards a deeper understanding as well
as a better justification of both paradigms. It appears interesting to investigate the
following topics in the future:

Table

1: Best restoration results for the different
methods and images. The total regularization
parameter for N iterations with parameter h is
denoted Nh, and the distance describes the
average Euclidean distance per pixel between the
restored and the original image without noise.
image regularization t distance
camera linear, 1 iteration 0.82 15.41
camera linear, 4 iterations 0.54 15.06
camera linear, iterations 0.48 15.02
MR linear, 1 iteration 2.05 23.09
MR linear, 4 iterations 1.16 22.62
MR linear, iterations 1.02 22.64
office linear, 1 iteration 5.7 31.76
office linear, 4 iterations 3.3 30.47
office linear, iterations 2.9 30.45
camera TV, 1 iteration 13.2 11.92
camera TV, 4 iterations 12.8 12.10
camera TV, iterations 12.4 12.19
MR TV, 4 iterations 33.5 20.52
MR TV, iterations 33 20.65
office TV, 1 iteration 102 28.66
office TV, 4 iterations 104 27.99
office TV, iterations 106 28.05

Figure

5.1: Test
scene. (b) Top Right: Gaussian noise added, SNR=4. (c) Middle
Left: Magnetic resonance image. (d) Middle Right: Gaussian
noise added, SNR=1. (e) Bottom Left: Office scene. (f)
Bottom Right: Gaussian noise added, SNR=0.25.

Figure

5.2: Optimal restoration results for Tikhonov regularization.

Figure

5.3: Optimal restoration results for total variation regular-
Figure

5.4: Comparison of two regularizations of the Perona-Malik
filter Filter (3.20),
Right: Filter (3.21), 0:5. (c) Middle Left: Filter (3.20),
2. (d) Middle Right: Filter (3.21), 2. (e) Bottom
Left: Filter (3.20), 8. (f) Bottom Right: Filter (3.21),
ffl Regularization scale-spaces. So far, scale-space theory was mainly expressed in
terms of parabolic and hyperbolic partial differential equations. Since scale-space
methods have contributed to various interesting computer vision applications, it
seems promising to investigate similar applications for regularization methods.
Fully implicit methods for nonlinear diffusion filters using a single time step. This is
equivalent to regularization and may be highly useful, if fast numerical techniques
for solving the arising nonlinear systems of equations are applied.



--R

Analysis of bounded variation penalty methods for ill-posed problems

Coll T.
A nonlinear primal-dual method for total-variation based image restoration
Total variation blind deconvolution
Image recovery via total variation minimization and related problems
Two deterministic half-quadratic regularization algorithms for computed imaging
Weak Continuity and Weak Lower Semicontinuity of Non-Linear Functionals
Direct Methods in the Calculus of Variations
Analysis of regularized total variation penalty methods for denoising
Convergence of an iterative method for total variation denoising
Regularization of Inverse Problems
Measure Theory and Fine Properties of Functions
Image Structure
Nonlinear image recovery with half-quadratic regulariza- tion
Bayesian reconstructions from emission tomography data using a modified EM algorithm
The Theory of Tikhonov regularization for Fredholm Equations of the First Kind
Spectral methods for linear inverse problems with unbounded operators
Optimal order of convergence for stable evaluation of differential operators
Minimal Surfaces and Functions of Bounded Variation
Elliptic partial differential equations of second order 2nd
Nonstationary iterated Tikhonov regularization J.

Introduction to Spectral Theory in Hilbert Space
An active set strategy for image restoration based on the augmented Lagrangian formulation
A computational algorithm for minimizing total variation in image enhancement

Methods for Solving Incorrectly Posed Problems

Nonlinear image filtering with edge and corner enhancement
Least squares and bounded variation regularization


Scale space and edge detection using anisotropic diffusion
Functional Analysis
Nonlinear total variation based noise removal algorithms
Stable evaluation of differential operators and linear and nonlinear milti-scale filtering
Denoising with higher order derivatives of bounded variation and an application to parameter estimation

Gaussian Scale-Space Theory
Relation of regularization parameter and scale in total variation based image denoising
Solutions of Ill-Posed Problems
On edge detection

Lineare Operatoren in Hilbertr-aumen
Anisotropic diffusion filters for image processing based quality control
A review of nonlinear diffusion filtering
Anisotropic Diffusion in Image Processing
Partielle Differentialgleichungen
--TR
On edge detection
Direct methods in the calculus of variations
Scale-Space and Edge Detection Using Anisotropic Diffusion
Feature-oriented image enhancement using shock filters
Biased anisotropic diffusion
Spectral methods for linear inverse problems with unbounded operators
Nonlinear Image Filtering with Edge and Corner Enhancement
Nonlinear total variation based noise removal algorithms
A degenerate pseudoparabolic regularization of a nonlinear forward-backward heat equation arising in the theory of heat and mass exchange in stably stratified turbulent shear flow
Variational methods in image segmentation
Convergence of an Iterative Method for Total Variation Denoising
Regularization, Scale-Space, and Edge Detection Filters
Denoising with higher order derivatives of bounded variation and an application to parameter estimation
Nonstationary iterated Tikhonov regularization
Geometry-Driven Diffusion in Computer Vision
Scale-Space Theory in Computer Vision
Gaussian Scale-Space Theory
A Review of Nonlinear Diffusion Filtering
Scale-Space Properties of Regularization Methods

--CTR
Markus Grasmair, The Equivalence of the Taut String Algorithm and BV-Regularization, Journal of Mathematical Imaging and Vision, v.27 n.1, p.59-66, January   2007
Walter Hinterberger , Michael Hintermller , Karl Kunisch , Markus Von Oehsen , Otmar Scherzer, Tube Methods for BV Regularization, Journal of Mathematical Imaging and Vision, v.19 n.3, p.219-235, November
regularization;image restoration;total variation denoising;diffusion filtering;inverse problems