Keywords

1 Introduction

Recovering an image from a noisy and blurry image is an inverse problem which is solved via variational methods, e.g. cf [1, 7]. This requires the minimization of some energy functional.

By the Euler-Lagrange formulation it results into a set of nonlinear partial differential equations which are then solved using say, the gradient-descent iteration, see for instance [12] for the classical model of Rudin, Osher and Fatemi (ROF model), which is based on the total variation (TV) regularization of the intensity (gray level), and [9, 11] for an improved model (TV-Stokes model) which is based on the total variation regularization of the tangential field of the intensity. The drawback of such algorithms is that their convergence is very slow, particularly for large images. There exist now algorithms which are much faster, those based on the dual formulation of the underlying models, see for instance [2, 3, 8]

An iterative regularization algorithm for the ROF model has recently been proposed, cf. [10], giving significant improvement over the classical method in the quality of the restored image. The main purpose of this paper is to propose a similar algorithm for the TV-Stokes model, and its dual formulation for faster convergence. The paper is organized as follows: in Sect. 2 we present the iterative regularization algorithm for the ROF model, and in Sect. 3 we propose a similar algorithm for the TV-Stokes model. In Sect. 4 we describe Chambolle’s iteration for the dual formulation of the TV-Stokes model, which we use for the numerical experiments of Sect. 5.

2 Iterative Regularization for the TV Denoising

Let the noisy image \(d_0\) represented as scalar \(L^2(\varOmega )\) function be given. The classical denoising method is based on the minimization problem:

$$\begin{aligned} \min _{{d}} \int _{\varOmega } \left| \nabla {d} \right| d\mathbf {x} \ + \ \frac{\lambda }{2} \int _{\varOmega } ( {d_0} - {d} )^2 d\mathbf {x}, \end{aligned}$$
(1)

where \(\lambda \) is a constant which is used to balance between the smoothing of the image and the fidelity to the input image. It is difficult to know how to choose \(\lambda \). An equivalent formulation of (1) is the following constrained minimization problem, cf. e.g. [4]:

$$\begin{aligned} \min _{ \Vert {d_0}-{d} \Vert _{L^2}^2=\sigma ^2} \int _{\varOmega } \left| \nabla {d} \right| d\mathbf {x}, \end{aligned}$$
(2)

where \(\sigma \) is the noise level. One often has a reasonable estimate of the noise level. In the original paper [12], a gradient projection method was used to solve (2). The method is known for its good edge preserving capability. It suffers however from its blocky effect on the resulting image. Not just that, it looses quite easily the high frequency part of the image as well. The recently proposed iterative regularization method [10], an algorithm which is based on the original TV denoising algorithm, has proven to give a much better result than the constrained denoising algorithm of ROF.

Given \(d_0, \lambda \), and \(v_0=0\). For \(k=0,1,2,\ldots \), find the minimizer \(d_{k+1}\) of the following minimization problem,

$$\begin{aligned} \min _{{d}} \int _{\varOmega } \left| \nabla {d} \right| d\mathbf {x} \ + \ \frac{\lambda }{2} \int _{\varOmega } ({d_0} + v_k - {d})^2 d\mathbf {x}, \end{aligned}$$
(3)

and update

$$\begin{aligned} v_{k+1} = v_k + d_0 - d_{k+1}. \end{aligned}$$
(4)

For stopping the iterative procedure, a reasonable criterion to use is the discrepancy principle, that is to stop the iteration the first time the residual \(\Vert d_0 - d_k\Vert _{L^2}\) is of the same order as the noise level \(\sigma \), cf. [10]. We know that the problem (3) has a unique solution. It is shown in [10] that \(d_k\) will converge to the original noisy image \(d_0\) as we continue to iterate beyond the discrepancy point.

2.1 Discrete Algorithm

The algorithm consists of two loops. The first one, which will be the outer loop, we call it the k-loop. In each iteration of the k-loop, we need the minimizer of the classical ROF model, which we do by the descent technique, iterating over an artificial time step to steady state.

figure a

2.2 Discretization

For the time discretization we use an explicit scheme, where, in each time step, the nonlinear term is calculated using values from the previous time step and is therefore a known quantity. Each vertex of the rectangular grid corresponds to the position of a pixel or pixel center where the image intensity variable d is defined, cf. Fig. 1 (Right).

Fig. 1.
figure 1

Left: the computational grid with approximating points for the variables \(d, d_x\), and \(d_y\), represented by \(\circ , \triangleright \), and \(\diamond \), respectively. Right: mapping the computational grid onto the pixels.

Full size image

For the space discretization, we approximate the derivatives by finite differences using the standard forward/backward difference operators \(D_x^{\pm }\) and \(D_y^{\pm }\), and the centered difference operators \(C_x^{h}\) and \(C_y^{h}\), respectively in the x and y directions, as \(D_x^{\pm } f = \pm \frac{ f(x \pm h,y) - f(x,y)}{h}\), \(D_y^{\pm } f = \pm \frac{ f(x,y \pm h) - f(x,y)}{h}\), \(C_y^{h} f = \frac{ f(x + h,y) - f(x - h,y)}{2 h}\), and \(C_y^{h} f = \frac{ f(x,y + h) - f(x,y - h)}{2 h}\) for any function f, where h correspond to the \(h-\)spacing. We introduce two average operators \(A_x\) and \(A_y\) as \(A_x f = \left( f(x,y) + f(x+h,y)\right) /2\) and \(A_y f = \left( f(x,y) + f(x,y+h)\right) /2\).

The discrete approximation of (5), thus, takes the following form:

$$\begin{aligned} \nabla \cdot \left( \frac{\nabla u^n}{|\nabla u^n|}\right) + \lambda (u^0 - u^n) \approx D_x^- \left( \frac{D_x^+ u^n}{T_1^n} \right) + D_y^- \left( \frac{D_y^+ u^n}{T_2^n} \right) + \lambda (u^0 - u^n), \end{aligned}$$
(7)

where \(T_1^n\) is defined as \(T_1^n =\sqrt{ \left( D_x^+ u^n\right) ^2 + \left( A_x(C_y^h u^n)\right) ^2 + \epsilon }\), and \(T_2^n\) as \(T_2^n = \sqrt{ \left( D_y^+ u^n\right) ^2 + \left( A_y(C_x^h u^n)\right) ^2 + \epsilon }\). Here \(\epsilon \) is a small number.

3 Iterative Regularization for the TV-Stokes

3.1 The TV-Stokes Denoising

Let the noisy image \(d_0\) represented as scalar \(L^2(\varOmega )\) function be given. We compute \(\tau _0 = \nabla ^{\bot }d_0\). The algorithm is then defined in two steps, see [9, 11]. In the first step, writing the tangent vector as \(\tau = (v,u)\), we solve the following minimization problem:

$$\begin{aligned} \min _{\mathbf {\tau }} \int _{\varOmega } \left( \left| \nabla {v} \right| + \left| \nabla {u} \right| \right) d\mathbf {x} \ + \ \frac{\delta }{2} \int _{\varOmega } |\mathbf {\tau } - \mathbf {\tau _0}|^2 \ d\mathbf {x} \end{aligned}$$
(8)

subject to \(\nabla \cdot {\mathbf {\tau }} = 0,\) where \(\delta \) is a constant which is used to balance between the smoothing of the tangent field and the fidelity to the input tangent field. Once we have the smoothed tangent field, we can get the corresponding normal field \(\mathbf {n} = (u,-v)\). In the second step, we reconstruct our image by fitting it to the normal field through solving the following minimization problem:

$$\begin{aligned} \min _{d} \int _{\varOmega } \left( \left( |\nabla d\right| - \nabla d\frac{\mathbf {n}}{|\mathbf {n}|} \right) d\mathbf {x} + \frac{\lambda }{2} \int _{\varOmega } ( {d_0} - {d} )^2 d\mathbf {x}. \end{aligned}$$
(9)

As before, let \(\Vert d - d_0 \Vert ^2_{L^2} = \sigma ^2\) be the estimated noise variance. This can be estimated using statistical methods. If the exact noise variance cannot be obtained, then an approximate value may be used. In which case, a larger value would result in over-smoothing and a smaller value would result in under-smoothing.

3.2 Iterative Regularization

Given \(d_0, s_0=0, \delta \) and \(\lambda \). For \(k=0,1,2,\ldots \), in the first step, we compute \(\tau _0 = \nabla ^{\bot }(d_0+s_k)\), and we solve the following minimization problem.

$$\begin{aligned} \min _{\mathbf {\tau }} \int _{\varOmega } \left( \left| \nabla {v} \right| + \left| \nabla {u} \right| \right) d\mathbf {x} \ + \ \frac{\delta }{2} \int _{\varOmega } |\mathbf {\tau } - \mathbf {\tau _0}|^2 \ d\mathbf {x}, \end{aligned}$$
(10)

subject to \( \nabla \cdot {\mathbf {\tau }} = 0.\)

Once we have the smoothed tangent field, we get the corresponding normal field \(\mathbf {n} = (u,-v)\). In the second step, we reconstruct our image by fitting it to the normal field through solving the following minimization problem.

$$\begin{aligned} \min _{d} \int _{\varOmega } \left( \left( |\nabla d\right| - \nabla d\frac{\mathbf {n}}{|\mathbf {n}|} \right) d\mathbf {x} \ + \ \frac{\lambda }{2} \int _{\varOmega } ({d_0} + s_k - {d})^2 d\mathbf {x}, \end{aligned}$$
(11)

and update \( s_{k+1} = s_k + d_0 -d_{k+1}. \) For stopping of the iterative procedure, we use the discrepancy principle, that is to stop the iteration the first time the residual \(\Vert d_0 - d_k\Vert _{L^2}\) is of the same order as the noise level \(\sigma \), cf. [10]. It is possible to show that \(d_k\) will converge to the original noisy image\(d_0\) as we continue to iterate beyond the discrepancy point.

3.3 Discrete Algorithm

The algorithm consists of two loops, the outer loop being the k-loop as before. In each iteration of the k-loop, the two minimizing steps of the TV-Stokes algorithms is performed. The discrete algorithm is in Algorithm 2 below.

3.4 Discretization

For the time discretization, we use an explicit scheme, where, in each time step, the nonlinear term is calculated using values from the previous time step and is therefore a known quantity. As before, each vertex of the rectangular grid corresponds to the position of a pixel or pixel center where the image intensity variable d is defined, cf. Fig. 1 (Right).

For the space discretization again we use a staggered grid, cf. Fig. 1 (Left). We approximate the derivatives by finite differences using the standard forward/backward difference operators \(D_x^{\pm }\) and \(D_y^{\pm }\), and the centered difference operators \(C_x^{h}\) and \(C_y^{h}\), respectively in the x and y directions, as described in Sect. 2.

The discrete approximation of (15)–(17) are as follows

$$\begin{aligned} \frac{v^{n+1}-v^n}{\varDelta t}= & {} D_x^- \left( \frac{D_x^+ v^n}{T_1^n(v)} \right) + D_y^- \left( \frac{D_y^+ v^n}{T_2^n(v)} \right) + \delta (v^0 - v^n) + D_x^- q^n \end{aligned}$$
(12)
$$\begin{aligned} \frac{u^{n+1}-u^n}{\varDelta t}= & {} D_x^- \left( \frac{D_x^+ u^n}{T_1^n(u)} \right) + D_y^- \left( \frac{D_y^+ u^n}{T_2^n(u)} \right) + \delta (u^0 - u^n) + D_y^- q^n \end{aligned}$$
(13)
$$\begin{aligned} \frac{q^{n+1}-q^n}{\varDelta t}= & {} D_x^+ v^n + D_y^+ u^n \end{aligned}$$
(14)

where \(T_1^n(u)\) is defined as \(T_1^n(u) = \sqrt{ \left( D_x^+ u^n\right) ^2 + \left( A_x(C_y^h u^n)\right) ^2 + \epsilon }\) and \(T_2^n(u)\) as \(T_2^n(u) = \sqrt{ \left( D_y^+ u^n\right) ^2 + \left( A_y(C_x^h u^n)\right) ^2 + \epsilon }\). Analogously, we define \(T_1^n(v)\) and \(T_2^n(v)\) by replacing u with v.

figure b

The discrete approximation of (18) is defined as follows

$$\begin{aligned} \frac{w^{n+1}-w^n}{\varDelta t}= & {} D_x^- \left( \frac{D_x^+ w^n}{T_3^n} -n_1 \right) + D_y^- \left( \frac{D_y^+ w^n}{T_4^n} -n_2 \right) + \lambda (w^0 - w^n)\qquad \end{aligned}$$
(20)

where \(T_3^n\) is defined as \(T_3^n = \sqrt{ \left( D_x^+ w^n\right) ^2 + \left( A_x(C_y^h w^n)\right) ^2 + \epsilon }\) and \(T_4^n\) as \(T_4^n = \sqrt{ \left( D_y^+ w^n \right) ^2 + \left( A_y(C_x^h w^n\right) ^2 + \epsilon }\). and \(n_k\), for \(k=1\) and 2, respectively as \(n_1=\frac{u}{\sqrt{u^2+(A_x(A_yv))^2)+\epsilon }}\) and \(n_2=\frac{-v}{\sqrt{v^2+(A_y(A_x u))^2)+\epsilon }}\).

4 Chambolle’s Algorithm

In this section we present a dual approach for solving our TV Stokes iterative regularization, cf. [5, 6, 8]. We consider the image in \(L^2(\varOmega )\) be approximated on the regular mesh and be represented as \(d\in \mathbb {R}^{N\times N}\). The derivative matrices, corresponding to the u and v, are then computed naturally from d using appropriate finite differences, which again constitute the pair of matrices corresponding to the tangential vector \(\tau =(v,u)\).

4.1 First Step

In the first step, we consider the minimization problem (10):

$$\begin{aligned} \min _{\nabla \mathbf {\tau }=0} \int _{\varOmega } \left( \left| \nabla {v} \right| + \left| \nabla {u} \right| \right) d\mathbf {x} \ + \ \frac{\delta }{2} \int _{\varOmega } |\mathbf {\tau } - \mathbf {\tau _0}|^2 \ d\mathbf {x}. \end{aligned}$$
(21)

Using a dual formulation of the TV norm we can write

$$ \int _{\varOmega } \left( \left| \nabla {v} \right| + \left| \nabla {u} \right| \right) d\mathbf {x} = \max _{\mathbf {G}}\int _{\varOmega } \langle \tau ,\nabla \cdot \mathbf {G}\rangle \, dx, $$

where \(\langle \mathbf {x},\mathbf {y}\rangle =x_1y_1+x_2y_2\) for \(\mathbf {x},\mathbf {y}\in \mathbb {R}^2\), and \(\mathbf {G}=(\mathbf {g}_1,\mathbf {g}_2)^T\) is the dual variable such that \(\mathbf {g}_i\in C^1_c(\varOmega )^2\) and \(|\mathbf {g}_i|_{\infty }\le 1\). Using this, (10) can be reformulated as

$$\begin{aligned} \min _{\nabla \mathbf {\tau }=0}\max _{\mathbf {G}} \int _{\varOmega } \langle \tau ,\nabla \cdot \mathbf {G}\rangle d\mathbf {x} \ + \ \frac{\delta }{2} \int _{\varOmega } |\mathbf {\tau } - \mathbf {\tau _0}|^2 \ d\mathbf {x}. \end{aligned}$$
(22)

Here \(\nabla \cdot \mathbf {G}=(\nabla \cdot \mathbf {g}_1,\nabla \cdot \mathbf {g}_2)^T\). We define the orthogonal projection \(\varPi _Y\) onto \(Y=\{\tau : \nabla \cdot \tau =0\}\) as

$$\begin{aligned} \varPi _Y \left[ \begin{array}{c} \tau _1\\ \tau _2 \end{array} \right] =\left[ \begin{array}{c} \tau _1\\ \tau _2 \end{array} \right] - \nabla \triangle ^{\dagger } \nabla \cdot \left[ \begin{array}{c} \tau _1\\ \tau _2 \end{array} \right] . \end{aligned}$$
(23)

We note that \(\nabla \cdot \tau =0\) is equivalent to \(\varPi _Y\tau =\tau \); using this, and exchanging min and max, we get

$$\begin{aligned} \max _{\mathbf {G}}\min _\tau \int _{\varOmega } \langle \tau ,\varPi _Y\nabla \cdot \mathbf {G}\rangle d\mathbf {x} \ + \ \frac{\delta }{2} \int _{\varOmega } |\mathbf {\tau } - \mathbf {\tau _0}|^2 \ d\mathbf {x}. \end{aligned}$$
(24)

Minimizing with respect to \(\tau \) we get

$$\begin{aligned} \tau = \tau _0- \frac{1}{\delta }\varPi _Y\nabla \cdot \mathbf {G}. \end{aligned}$$
(25)

Substituting it back, we obtain the dual problem:

$$\begin{aligned} \min _{\mathbf {G}} \int _\varOmega |\varPi _Y \nabla \cdot \mathbf {G} -\delta \tau _0|^2\,d x. \end{aligned}$$
(26)

This problem can be solved using Chambolle’s fixed point iteration (cf. [3]):

$$\begin{aligned} \mathbf {G}^{n+1}= \frac{\mathbf {G}^n + \varDelta t\nabla [\varPi _Y \nabla \cdot \mathbf {G} -\delta \tau _0]}{1 + \varDelta t\nabla [\varPi _Y \nabla \cdot \mathbf {G} -\delta \tau _0]} \end{aligned}$$
(27)
Fig. 2.
figure 2

Denoising of Lena image, with noise level \(\approx \) 8, \(\delta =.16\) and \(\mu =0.20\).

Full size image

In practice we compute an approximation of \(\varPi _Y\) using the following discrete gradient, discrete divergence and discrete Laplace operator. For \(d\in \mathbb {R}^{N\times N}\) representing an image on a 2D grid let

$$\begin{aligned} \nabla ^hd =(dD^T,D d)^T, \quad \nabla ^h\cdot (p_1,p_2)=-p_1D-D^Tp_2, \end{aligned}$$
(28)

where D is differentiation matrix. Then \(\triangle ^h=-dDD^T -D^TDd\) and the discrete projection becomes: \( \varPi _Y^h=I - \nabla ^h(\triangle ^h)^\dagger \nabla ^h. \) Because we know SVD of \(\triangle ^h\), thus the action of \((\triangle ^h)^\dagger \) can be computed using discrete cosine and sine matrices with the aid of the Fast Fourier Transform requiring only \(O(N^2\log _2(N))\) operations.

4.2 Second Step

In the second step, we have an unconstrained minimization problem (11). Using the dual formulation of the TV norm, the problem can be reformulated as

$$\begin{aligned} \min _{{d}} \max _{\mathbf {g} \in C^1_c(\varOmega )^2:|\mathbf {g}|_\infty \le 1} \int _{\varOmega } d \, \nabla \cdot \left( \mathbf {g} + \frac{\mathbf {n}}{|\mathbf {n}|} \right) \, d\mathbf {x} \ + \ \frac{\lambda }{2} \int _{\varOmega } ({d_0} + s_k - {d})^2 d\mathbf {x}. \end{aligned}$$
(29)
Fig. 3.
figure 3

Denoising of fingerprint image, with noise level \(\approx \) 6.4, \(\delta =.16\) and \(\mu =0.20\).

Full size image

Exchanging the min and max, and minimizing with respect to d, we get

$$\begin{aligned} d=d_0+s_k-\frac{1}{\lambda }\nabla \cdot \left( \mathbf {g} + \frac{\mathbf {n}}{|\mathbf {n}|} \right) . \end{aligned}$$
(30)

Substituting it back, we obtain the dual problem:

$$\begin{aligned} \min _{\mathbf {g}} \int _{\varOmega }\left| \lambda (d_0+s_k) -\nabla \cdot \left( \mathbf {g} + \frac{\mathbf {n}}{|\mathbf {n}|} \right) \right| ^2 d\mathbf {x}. \end{aligned}$$
(31)

Using Chambolle’s fixed point iteration we get

$$\begin{aligned} \mathbf {g}^{n+1}= \frac{\mathbf {g}^n + \varDelta t\nabla [\nabla \cdot \left( \mathbf {g}^n + \frac{\mathbf {n}}{|\mathbf {n}|} \right) -\lambda (d_0+s_k)]}{1 + \varDelta t\nabla [\nabla \cdot \left( \mathbf {g}^n + \frac{\mathbf {n}}{|\mathbf {n}|} \right) -\lambda (d_0+s_k)]}. \end{aligned}$$
(32)

5 Numerical Results

The algorithm has been applied to the Lena and the fingerprint image, and the results are shown in Figs. 2 and 3, respectively, showing three iterations of the iterative regularization algorithm, with denoised images in the first row and their corresponding difference images (difference between the noisy image and the denoised image) in the second row. The preliminary results shown in the figures proves that he proposed algorithm works well.