1 Introduction

Noise and blur are the most common degradations introduced by an image acquisition system. Formation of a blurred and noisy image is typically modeled as

$$ u_0 = K[u_i] + n $$
(1)

where K denotes a linear blur operator, u i is the ideal undistorted image, u 0 is the observed image and n is a white Gaussian noise. The blur operator K can be described by a Fredholm first kind integral operator

$$\begin{aligned} &{K\bigl[u_i(x,y)\bigr] = \int_\varOmega{k \bigl(x,x',y,y'\bigr)u_i \bigl(x',y'\bigr)\,dx'\,dy'} } \\&{\quad (x,y) \in \varOmega} \end{aligned}$$
(2)

where Ω denotes an open and bounded domain in R 2 and (x,y) denotes the spacial location in Ω. Among all linear blurring operators, many are shift-invariant and can be expressed in the form of convolution:

$$\begin{aligned} K\bigl[u_i(x,y)\bigr] =& \int_\varOmega{k\bigl(x-x',y-y' \bigr)u_i\bigl(x',y'\bigr)\,dx'\,dy'} \\=& (k*u_i) (x,y) \end{aligned}$$
(3)

where k is the so-called point spread function (PSF) associated with K. With an added noise n, the observed image u 0 is

$$ u_0(x,y) = (k*u_i) (x,y) + n(x,y) $$
(4)

Model (4) is applicable to a large variety of image degradation processes that are encountered in practice. Throughout this paper, we consider (4) as the model of degradation where the PSF k is assumed to be known. Typically, k has the following properties, k(x,y)≥0, k→0 as (x 2+y 2)→+∞ , and \(\int_{R^{2}}{k(x,y) dxdy} = 1 \). A typical example of convolution kernel, which we will use throughout this paper, is the Gaussian PSF defined as

$$ k_\sigma(x,y)= \mu \,{e^{-(x^2+y^2)/2{\sigma}^2}} $$
(5)

where σ 2 is the variance that determines the severity of the blur and μ is a normalizing constant ensuring that the blur is of unit mass. The purpose of image restoration is to reconstruct u i , from our knowledge of the blurring kernel k, the statistics of noise n and the observed image u 0.

The image restoration problem is ill-posed; either the linear operator K does not admit inverse or it is near singular, yielding highly noise sensitive solutions. There are many approaches for image restoration based on statistics [7, 11, 12, 14], Fourier and/or wavelet transforms [30], or variational/PDE [15, 24, 29, 33, 40, 41] analysis. Among them, the nonlinear PDE methods have become very popular because of their ability to preserve sharp discontinuities. While linear image restoration techniques such as Wiener filtering and Tikhonov regularization [38] are fast, they are often inappropriate for image processing applications in which the desired solution is not smooth. Use of these methods yield reconstructions in which discontinuities are smoothed out or which suffer from spurious oscillations, known as Gibbs phenomenon. This shortcoming led to the development of Total Variation (TV) image restoration [33, 34]. The TV model preserves edges very well, but the computational cost is very high and parameter dependent. Furthermore, these methods also suffer from the undesirable “staircase” effect, namely the transformation of smooth regions (ramps) into piecewise constant regions (stairs). Marquina and Osher have proposed an improved TV model [29] for deblurring and noise removal based on level set ideas. Unlike TV, the steady state is quickly reached by the Marquina–Osher (MO) model using a simple explicit scheme. The filter in [19] tries to reduce the staircase effect in homogeneous areas of the image by switching between isotropic and anisotropic regularization terms depending on the local image features. A TV restoration, where the image acquisition model is incorporated as a set of local constraints has been proposed in [3]. The inclusion of the local constraints, one for each pixel of the image, provides better reconstruction of textured areas in the image. Welk et al. [41] investigated nonconvex regularization in the image deblurring problem. This model uses the famous Perona–Malik anisotropic diffusion as the regularizer in the image deconvolution PDE. There is another class of image reconstruction methods, namely blind deconvolution models, which does not assume a prior knowledge of the blurring kernel. Examples can be found in [10, 42].

In this paper, we present a new nonlinear level set based PDE model for image restoration, which combines an image deconvolution and a curve evolution based regularization processes. While the deconvolution term tries to invert the convolution operation and deblur the image, the regularization terms in the proposed PDE stabilize the deconvolution operation and also provide effective noise removal and edge preservation. The regularization term in the proposed PDE is a combination of an image smoothing term and an image enhancement term. A mean curvature motion (MCM) based diffusion [4, 29] is used in the image smoothing term to eliminate the noise very effectively and quickly. A time varying edge stopping function is attached with the diffusion term in order to reduce the amount of smoothing performed at the edges. The image enhancement term in the model is a reactive term, which drives the image level sets towards the object boundaries and force them to stop there. This term is used for effective edge preservation and image enhancement. Our model is in the form of a reaction-diffusion PDE rather than a variational regularization. Reaction-diffusion models have been proposed for different applications in the literature, such as shape recovery [23, 36] and image segmentation [21, 37]. The performance and robustness of the method are tested in various experiments, with synthetic and real-life degradations. The quality of the results is evaluated both visually and in terms of Improvement in Signal-to-Noise-Ratio (ISNR) and the Pratt’s Figure Of Merit (FOM). Detailed comparisons with 2 other PDE based deblurring and denoising methods [29, 41] are performed, and show that the proposed method yields significantly better results than these other methods.

The rest of the paper is organized as follows: Sect. 2 reviews the major PDE based image deblurring and denoising models. Section 3 describes the proposed level set based reconstruction model and its numerical implementation. In Sect. 4, we present the visual and quantitative results on synthetic and real blurred and noisy images. Section 5 concludes the paper.

2 Variational/PDE-based deconvolution models

Considering the degradation model (4), a naive denoising and deconvolution model would be the following:

$$ \hat{u}_0 =\hat{k} \hat{u}_i + \hat{n} $$
(6)

where \(\hat{x}\) denotes the Fourier transform of the function x. Leaving aside the noise, this model has an important drawback: in order to deconvolve, we need to divide by \(\hat{k}(l,m)\) for every frequency (l,m). This procedure is generally ill-posed. If k is smooth, high frequencies tend quickly to zero, implying that those frequencies in \(\hat{u}_{0}\) get amplified, and the model above, in spite of its simplicity, is far from efficient.

A classical way to overcome ill-posed problems is variational regularization. In [38], Tikhonov and Arsenin introduced this idea for image restoration. The Tikhonov regularization is to find an image u, which minimizes the functional

$$ J(u)= \int_\varOmega{|\nabla u|^2\,dx\,dy} + \frac{\lambda}{2}\int_\varOmega{(k*u-u_0)^2\,dx\,dy} $$
(7)

where ∇u denotes the gradient of u. The second term in J(u) is a fidelity term that forces k∗u to be close to the observed image u 0. The first term enforces a smoothness constraint on u and can be seen as a regularizer in the ill-posed deconvolution problem. In other words, we search for a u that best fits the data so that its gradient is low (so that noise will be removed). The parameter λ represents a regularization parameter. The Euler–Lagrange equation associated with the variational problem (7) is

$$ \lambda \bigl(k*(k*u -u_0) \bigr) - \Delta u = 0 $$
(8)

where Δu denotes the Laplacian of u. The solution u(t) depends on λ, which weights both terms of the equation. A small λ approximates the purely denoising term, while a large λ ignores the second term, leaving the deconvolution part of the equation, k∗(k∗u−u 0), with the obvious solution k∗u=u 0. Between the two extreme cases, there is a whole branch of intermediate solutions. This formulation was an important step, but the results were not satisfactory, mainly due to the inability of the previous functional to resolve discontinuities (edges). The regularization functional in (7) assumes u is smooth and information corresponding to high frequencies of u 0 is attenuated by it. These observations motivated the introduction of Total Variation (TV) in image restoration problems.

The formulation of TV models was first given by Rudin, Osher, and Fatemi in [34] for the denoising case and Rudin and Osher in [33] for the denoising and deblurring case. This approach does not require that a solution be continuous but merely that it be of bounded variation. There has been a flurry of recent work, both numerical applications [24, 39, 40] and theoretical analysis [2, 15] that demonstrates the superiority of TV over the linear image reconstruction methods.

On the basis of the BV model, the TV-norm is proposed as a regularization functional for the image restoration problem. The minimization functional presented in [33] is

$$ TV(u) = \int_\varOmega{|\nabla u| \,dx\,dy} + \frac{\lambda}{2} \int_{\varOmega}(k*u-u_0)^2 \, dx\,dy $$
(9)

The Euler–Lagrange equation associated with (9) with homogeneous Neumann boundary condition is given by

$$ \begin{aligned} &\lambda \bigl(k*(k*u-u_0) \bigr) -\nabla. \biggl( \frac{\nabla u}{|\nabla u|} \biggr) = 0, \quad (x,y) \in \varOmega \\&\frac{\partial u}{\partial \mathbf {n}} = 0, \quad \quad(x,y) \in \partial \varOmega \end{aligned} $$
(10)

where ∂Ω is the boundary of Ω and n is the outward normal to ∂Ω. Rudin and Osher [33] applied the artificial time marching method to solve (10)

$$ \frac{\partial u}{\partial t} = -\lambda \bigl(k*(k*u-u_0) \bigr) + \nabla. \biggl(\frac{\nabla u}{|\nabla u|} \biggr) $$
(11)

Since Eq. (11) is not well defined at points where ∇u=0, due to the presence of the term 1/|∇u|, it is common to slightly perturb the TV functional to become

$$ \int_\varOmega{ \sqrt{{|\nabla u|}^2 +\varepsilon } \,dx\,dy} $$
(12)

where ε is a small positive parameter. The TV norm does not penalize discontinuities in u, and thus allows us to recover the edges of the original image. However, there are computational difficulties. The steady state is reached with a very small time step, using (11). Linear semiimplicit fixed-point procedures devised by Vogel and Oman [39] and primal-dual implicit quadratic methods by Chan, Golub, and Mulet [9] were introduced to solve the computational difficulties of TV restoration problem. These methods give good results when treating pure denoising problems, but the methods become highly ill-conditioned for the deblurring and denoising case where the computational cost is very high and parameter dependent. Furthermore, the TV model also suffers from the undesirable staircase effect.

In [29], Marquina and Osher introduced a time dependent model for image deblurring and denoising, which eliminates the computational difficulties associated with the TV restoration problem and also reduces the staircase effect to a certain extend. The model is constructed by evolving the Euler–Lagrange equation of the Rudin–Osher optimization problem, multiplied by the magnitude of the gradient of the solution.

$$ \frac{\partial u}{\partial t} = -|\nabla u| \,\lambda \bigl(k*(k*u-u_0)\bigr)+ |\nabla u| \, \nabla. \biggl(\frac{\nabla u}{|\nabla u|} \biggr) $$
(13)

The main features of this formulation are: (a) there are simple explicit schemes such as Roe’s scheme that behave stably with a reasonable CFL restriction for this evolution equation, (b) the level contours of the image move quickly to the steady solution and the presence of the gradient numerically regularizes the mean curvature term in a way that preserves edges and kills noise through the curvature-based evolution acting on small scales.

The use of nonconvex regularization functionals in image restoration has been investigated by Welk et al. [41]. In general, variational deblurring and denoising of an image can be achieved by minimizing the energy functional

$$ J(u)= \int_\varOmega {\varPsi \bigl( |\nabla u| \bigr)\,dx\,dy} + \frac{\lambda}{2}\int_\varOmega{(k*u-u_0)^2\,dx\,dy} $$
(14)

The function Ψ(|∇u|)=|∇u|2 leads to Tikhonov regularization, whereas Ψ(|∇u|)=|∇u| gives the TV regularization. In [41], the nonconvex function

$$ \varPsi \bigl(|\nabla u|\bigr) = \alpha^2 \ln \biggl(1+ \frac{|\nabla u|^2}{\alpha^2} \biggr) $$
(15)

has been considered in model (14). The resulting gradient-descent equation is

$$ \frac{\partial u}{\partial t}= - \lambda \bigl(k*(k*u-u_0)\bigr) + \operatorname {div}\bigl( g\bigl(|\nabla u|\bigr) \nabla u \bigr) $$
(16)

where

$$ g\bigl(|\nabla u|\bigr) =\frac{1}{ (1+ ({|\nabla u|}^2/\alpha^2 ) )} $$
(17)

The term \(\operatorname {div}( g(|\nabla u|) \nabla u ) \) represents the Perona–Malik anisotropic diffusion, where g is the diffusion coefficient and α is a contrast parameter, which determines above which steepness edges are enhanced in the gradient descent process. The nonconvex Ψ functions like (15) allow the reconstruction of sharper images.

3 The nonlinear level set based deconvolution model

In this section, we introduce a new nonlinear level set model for image deblurring and denoising. To this end, we first review some basic concepts of level set methods and a few level set models, which are directly related to the proposed model.

3.1 Level set methods

The level set methods introduced in [32] are efficient numerical techniques for solving curve evolution problems. They have been widely applied in many problems of image processing such as image enhancement and noise removal [4, 13, 26, 35], segmentation [8, 16, 20, 22, 23], and shape recovery [27, 28, 37].

The basic idea behind the level set method is that a closed curve Γ can be represented as the zero level set of an auxiliary function ϕ, called level set function

$$ \varGamma = \bigl\{(x,y)\mid \phi(x,y) = 0\bigr\} $$
(18)

and the level set method manipulates Γ implicitly, through the function ϕ. If the curve Γ moves in the normal direction with a speed V, then the level set function ϕ satisfies the level set equation

$$ \frac{\partial \phi}{\partial t} = V |\nabla \phi| $$
(19)

The motion of a level set characterized by \(V = \operatorname {div}(\nabla \phi/|\nabla \phi|) \), the mean curvature of the level set is called as Mean Curvature Motion (MCM). The MCM

$$ \frac{\partial \phi}{\partial t} = |\nabla \phi| \operatorname {div}\bigl(\nabla \phi/|\nabla \phi|\bigr) $$
(20)

is very well known for its geometric smoothing properties [5]. This property of MCM has been utilized in the Marquina–Osher deblurring and denoising model (13), where the MCM has been combined with a deconvolution term to restore the degraded observations.

Another important level set formulation is the Geodesic Active Contour (GAC) [8] model for image segmentation. To segment an image u into its constituent objects, an auxiliary level set function ϕ (defined over the image domain) is evolved according to

$$ \frac{\partial \phi}{\partial t} = g \bigl(| \nabla u_\sigma| \bigr) |\nabla \phi| \operatorname {div}\biggl(\frac{\nabla \phi}{|\nabla \phi|} \biggr) + \nabla \bigl(g \bigl(| \nabla u_\sigma| \bigr) \bigr). \nabla \varPhi $$
(21)

where g(.) is a decreasing function of the image gradient

$$ g \bigl(|\nabla u_\sigma|\bigr)=\frac{1}{1+ ({|\nabla (G_\sigma* u)|}^2/\alpha^2 )} \quad (\alpha>0) $$
(22)

Here, G σ denotes a Gaussian convolution of standard deviation σ and α is a contrast parameter. The function g(.) helps to stop the evolution of the curve at the image edges.

The properties of geodesic snakes (21) induced Sapiro to use a related technique for image denoising and enhancement [35]. This is done by deforming each of the level sets of the image according to the GAC, i.e., the image itself acts as the level set function (ϕ=u), giving

$$ \frac{\partial u}{\partial t} = g \bigl(| \nabla u_\sigma| \bigr) |\nabla u| \operatorname {div}\biggl(\frac{\nabla u}{|\nabla u|} \biggr) + \nabla \bigl(g \bigl(| \nabla u_\sigma| \bigr) \bigr). \nabla u $$
(23)

This evolution equation is known as a self-snake. The self-snake algorithm is very effective in preserving and enhancing edges while denoising the image.

Chen, Vemuri, and Wang [13] proposed a modified self-snake process for image denoising and enhancement, where a fidelity term is added to the self-snake (23) to enforce the closeness of the smoothed image to the original image. The restored image is given by the steady-state of

$$\begin{aligned} \frac{\partial u}{\partial t} =& g \bigl(| \nabla u_\sigma| \bigr) |\nabla u| \operatorname {div}\biggl(\frac{\nabla u}{|\nabla u|} \biggr) \\& {} + \nabla \bigl(g \bigl(| \nabla u_\sigma| \bigr) \bigr). \nabla u - \lambda |\nabla u| (u-u_0), \quad \lambda > 0 \end{aligned}$$
(24)

where u 0 is the noisy image, u is the denoised image, λ is a weighting parameter and g is as defined in (22). Excellent denoising results are shown by model (24) with sharp restoration of image features. The authors also establish the existence and stability of a unique viscosity solution to this evolution equation.

3.2 The proposed model

PDE based image deblurring and denoising models are generally made up of two terms, a deconvolution term and a regularizing/denoising term (see Eqs. (11), (13), and (16) in Sect. 2). Knowing the blurring PSF k, the deconvolution term tries to invert the convolution operation to deblur the image, whereas the regularization term numerically stabilizes the deconvolution operation and it also acts as a smoothing term to denoise the image. The smoothing and edge preserving characteristics of the regularization term will greatly affect the performance of an image deblurring and denoising model.

While TV regularization and nonlinear diffusion are common choices in the image deblurring and denoising literature, we investigate the use of the level set model (23), known as self-snake as a regularization term in a deblurring and denoising PDE. Even at high levels of noise, the self-snake model leads to effective denoising of the image with strong preservation of edges as demonstrated in [13, 35]. To utilize the edge preserving and enhancing characteristics of self-snake algorithm in the deblurring and denoising problem, we replace the regularization term in MO model (13) by the self-snake process (23) and our time evolution model takes the following form:

$$\begin{aligned} \frac{\partial u}{\partial t} =& -\lambda |\nabla u| \bigl(k*(k*u-u_0) \bigr) \\&{} + g \bigl(| \nabla u_\sigma| \bigr) |\nabla u| \operatorname {div}\biggl(\frac{\nabla u}{|\nabla u|} \biggr) \\& {} + \beta \, \nabla \bigl(g \bigl(| \nabla u_\sigma| \bigr)\bigr). \nabla u \end{aligned}$$
(25)

The initial and boundary conditions are

$$u(x,y,0) = u_0(x,y), \qquad \frac{\partial u}{\partial \mathbf {n}} = 0 \ \mathit{on} \ \partial \varOmega $$

where u 0 is the blurred and noisy image, u is its restored version, k is the blurring PSF, λ and β are regularization parameters, and g(|∇u σ |) defined in (22) is a decreasing real valued function, which tends to zero as |∇u σ |→∞. The proposed PDE can also be viewed as an extension of the denoising model (24) for the more general deblurring and denoising problem by including a deconvolution operation in the fidelity term.

The proposed model (25) contains three terms: the first term is a deconvolution term which arises naturally in the deblurring context. Knowing the blurring PSF k, this term tries to invert the convolution operation and deblur the image. This term also moves the level curves of the image in the direction of zeros of (k∗u−u 0) ( where u is the restored version of the image and u 0 is the distorted image), since |∇u|(k∗(k∗u−u 0)) represents a level set motion with speed (k∗(k∗u−u 0)).

The second term is a diffusion term used for image smoothing, which also acts as a regularizer for the deconvolution operation. In this term, \(|\nabla u| \operatorname {div}(\frac{\nabla u}{|\nabla u|} )\) represents MCM [4, 29], which diffuses u in the direction orthogonal to its gradient ∇u and does not diffuse at all in the direction of ∇u. This makes u smooth on both sides of an edge with a minimal smoothing of the edge itself. The coefficient of the second term, namely, g(|∇u σ |) serves the purpose of selecting the locations in the image for smoothing. For instance, at image locations having large values of gradient, this coefficient takes on a small value since g(s) is a decreasing function of s, thereby reducing the smoothing performed at these locations. In homogeneous areas of the image, the level curves of the image move with a velocity equal to their mean curvature values. Areas of high curvature will diffuse much faster than areas of small curvature. Thus, small jagged noise artifacts in the homogeneous areas of the image will be quickly removed.

The third term ∇g.∇u is a reactive term, and this term is responsible for forcing the evolution-based image smoothing to stop exactly at the edges. This term attracts the evolving level sets toward the middle of the edges acting as an edge enhancing and sharpening term. In fact, using the diffusion term \(g (| \nabla u_{\sigma}| ) |\nabla u| \operatorname {div}(\frac{\nabla u}{|\nabla u|} )\), the level sets will be completely stopped only when g(|∇u σ |)=0. This happens only at an ideal edge (|∇u σ |=∞). In cases in which there are different gradient values along the edge, as often happens in real images, g(.) gets different values at different locations along the edge. Observe in Fig. 1(a) (taken from Caselles et al. [8]) the one-dimensional case of an edge (an object of high intensity value with low intensity background) of an image u. At the center of an edge, the gradient magnitude attains its maximum value and on both sides of an edge it decreases. Figure 1(b) shows g(.) and its gradient vectors. Observe the way the gradient vectors of g(.) are all directed toward the center of the edge. These vectors pull the propagating level curves toward the middle of the edges and eventually force them to stop there. Since the proposed PDE contains both an edge stopping term and an edge attractive term, it is even possible to restore the exact location of the edges with high differences in their gradient values. Furthermore, this term acts as a shock-filter introduced in [31] for image deblurring. Near the image edges, ∇g.∇u moves the level curves of the image in the same direction as the inverse heat equation would do. Since the level curves move closer to one another than they were initially, the edges will be enhanced and sharpened. In homogeneous areas of the image, the effect of this term is negligible. Thus, in the proposed model, the mean curvature motion of the image level sets give effective denoising in homogeneous areas with a strong preservation of edges with the help of edge stopping function g(.) in the diffusion term and the edge attractive force ∇g.∇u. On the other hand, the deconvolution term together with the shock term ∇g.∇u gives effective deblurring and sharpening of the image.

Fig. 1
figure 1

(a) A 1-D edge signal (smoothed version). (b) The corresponding gradient based edge stopping function g and its gradient vectors

Full size image

The edge preserving properties of the proposed model and the deblurring and denoising models in Sect. 2 can be compared by looking at the corresponding PDEs. The regularization term in model (11) moves each level curve of the image u normal to itself with a velocity equal to the curvature of the level surface divided by the magnitude of the gradient of u, whereas in model (13), the movement of level curves of u is pure mean curvature motion. In both cases, the evolution tends to shrink the level lines of the image and the continued application of both of these models results in blurring and deformation of edges (usually the curved edges appear more curvy).

The action of Welk model [41] can be understood by decomposing the PDE (16) as

$$\begin{aligned} \frac{\partial u}{\partial t} =& - \lambda \bigl( k*(k*u-u_0)\bigr) + g\bigl(|\nabla u|\bigr) \, u_{\xi\xi} \\&{} + \frac{ 1-{|\nabla u|}^2/{\alpha}^2 }{{ ( 1+{|\nabla u|}^2/{\alpha}^2 )}^2} \, u_{\eta\eta} \end{aligned}$$
(26)

where η and ξ are local coordinates that are aligned with the gradient and level set directions of the image. The evolution (26) varies as a function of the values of |∇u|. The second term in (26) represents a one dimensional diffusion in the direction orthogonal to the gradient, whereas the third term takes positive or negative values depending on the value of |∇u| relative to α, which respectively corresponds to a forward or inverse heat diffusion. Thus, the edge preservation capability of Welk model depends on the contrast of the edges compared to the diffusion threshold. Edges above this threshold undergo an “inverse diffusion” in the gradient direction and are enhanced, while edges below this threshold are smoothed (blurred) in both directions.

Note that our model is different from MO model [29]. The diffusion term in the proposed PDE is a mean curvature motion (MCM) based diffusion [4, 29] as in model [29]. However, our formulation involves a time varying edge stopping function with the curve evolution based diffusion term, which reduces the amount of smoothing performed at the edges, and our PDE has an additional reactive term that is not present in the MO model. This term is responsible for forcing the evolution based image smoothing to stop exactly at the edges and providing an effective image enhancement. Even though the proposed PDE (25) has the mean curvature motion as the smoothing term, it does not deform the edges even for a larger stopping time because of the presence of the edge stopping term g(|∇u σ |) and the term ∇g.∇u, which helps to stop the evolving level lines exactly at the center of the edges. Thus, the proposed method gives better localization of edges compared to other methods. Further, the term ∇g.∇u acting as a shock filter enhances and sharpens the edges.

3.3 Numerical implementation

The numerical implementation of the proposed deblurring and denoising PDE (25) is based on the upwind finite difference scheme developed by Osher and Sethian [32] for curve evolution via level sets. Let u n(i,j) be the approximation to the value u(iΔx,jΔy,nΔt), where Δx, Δy and Δt are the spatial step sizes and time step size, respectively. Implementing the time derivative is straightforward with

$$ \frac{\partial u}{\partial t} = \frac{u^{n+1}[i,j] -u^n[i,j]}{\Delta t} $$
(27)

and the diffusive term is approximated using the central finite differences, with

$$ |\nabla u| \operatorname {div}\biggl( \frac{\nabla u}{|\nabla u|} \biggr) =\frac{ u^2_y u_{xx} -2 u_x u_y u_{xy} + u^2_x u_{yy}}{u^2_x+u^2_y} $$
(28)

The data term |∇u|(k∗(k∗u−u 0)) and the doublet term (shock term) ∇g.∇u have to be implemented with special care. To implement the shock term, we have to use forward and backward finite differences adaptively so that their directions are always away from discontinuities. For a discrete grid point (i,j), let

(29)

then

$$\begin{aligned} (\nabla g. \nabla u)[i,j] = & \max \bigl(\Delta_x g^n[i,j],0\bigr) \Delta^-_x u^n[i,j] \\&{}+ \min \bigl(\Delta_x g^n[i,j],0\bigr) \Delta^+_x u^n[i,j] \\&{}+ \max \bigl(\Delta_y g^n[i,j],0\bigr) \Delta^-_y u^n[i,j] \\&{} + \min \bigl(\Delta_y g^n[i,j],0\bigr) \Delta^+_y u^n[i,j] \end{aligned}$$
(30)

and the upwind scheme for the data term |∇u|(k∗(k∗u−u 0)) is given by

$$\begin{aligned} &{\bigl(|\nabla u| \bigl( k*(k*u-u_0)\bigr)\bigr)[i,j] } \\&{\quad = \max \bigl(F[i,j],0\bigr) \nabla^+ u^n[i,j]} \\&{\qquad {} + \min \bigl(F[i,j],0\bigr) \nabla^- u^n[i,j]} \end{aligned}$$
(31)

where F[i,j]=(k∗(k∗u−u 0))[i,j],

$$\begin{aligned} \nabla^+ u^n[i,j] = & \bigl\{ \bigl( \max \bigl(\Delta^-_x u^n[i,j],0\bigr) \bigr)^2 \\& {}+ \bigl( \min \bigl(\Delta^+_x u^n[i,j],0\bigr) \bigr)^2 \\& {}+ \bigl( \max \bigl(\Delta^-_y u^n[i,j],0\bigr) \bigr)^2 \\& {}+ \bigl( \min \bigl(\Delta^+_y u^n[i,j],0\bigr) \bigr)^2 \bigr\}^{1/2} \end{aligned}$$
(32)

and

$$\begin{aligned} \nabla^- u^n[i,j] = & \bigl\{ \bigl( \max \bigl(\Delta^+_x u^n[i,j],0\bigr) \bigr)^2 \\&{}+ \bigl( \min \bigl( \Delta^-_x u^n[i,j],0\bigr) \bigr)^2 \\&{}+ \bigl( \max \bigl(\Delta^+_y u^n[i,j],0\bigr) \bigr)^2 \\&{}+ \bigl( \min \bigl(\Delta^-_y u^n[i,j],0\bigr) \bigr)^2 \bigr\}^{1/2} \end{aligned}$$
(33)

For a detailed discussion on this scheme, we refer the reader to [25, 32].

4 Experimental results

We now present a set of deblurring and denoising experiments illustrating the performance of the proposed algorithm. To assess the relative merit of the proposed method, the results of the proposed method are compared with two other PDE based deconvolution methods from the literature: Marquina–Osher (MO) model [29] and Welk model [41]. The discretization of PDEs associated with algorithms [41] and [29] is done as described in these papers. We examine the conventional Signal to Noise Ratio (SNR) and the Improvement in Signal-to-Noise-Ratio (ISNR) to measure the restoration quality of different methods tested. To Compare the edge preservation performance, we use Pratt’s Figure Of Merit (FOM). The SNR is defined in decibels as

$$ \mathrm{SNR} = 10 \log_{10} \frac{\sum_i{ { ({x_0}^i-\mu )}^2 } }{\sum_i{ { (x^i-{x_0}^i )}^2 } }\, dB $$
(34)

where x 0 is the original undistorted image, μ is the mean of x 0 and x is the restored image.

The ISNR is given by

$$ \mathrm{ISNR} =10\log_{10} \frac{\sum_i{ { (y^i-{x_0}^i )}^2 } }{\sum_i{ { (x^i-{x_0}^i )}^2 } }\, dB $$
(35)

where y is the degraded version of the image and the other symbols are as defined above. The FOM is defined as

$$ \mathrm{FOM} = \frac{1}{\max\{\hat{N}, N_\mathrm{ideal} \}} \, \sum_{i=1}^{\hat{N}} \frac{1}{1+d^2_i \gamma} $$
(36)

In (36), \(\hat{N} \) and N ideal are the number of detected and ideal edge pixels, respectively, d i is the Euclidean distance between the ith detected edge pixel and the nearest ideal edge pixel, and γ is a constant, typically set to 1/9. FOM ranges between 0 and 1, with unity for ideal edge detection.

4.1 Synthetic image experiments

We use two gray scale images, Trui (256×256) and Man (1024×1024) shown in Fig. 2 for our deblurring and denoising experiments. We first scale the intensities of the images into the range between 0 and 1 before we begin our experiments. The degraded images are obtained using the image acquisition model (4). For that, we use the Gaussian blur given in (5) with a blurring parameter σ and a Gaussian noise of standard deviation σ n . Note that the severity of the blurring is increased for a larger value of σ and the amount of noise is increased for a larger value of σ n . In the first experiment, the “Trui” image is corrupted with a Gaussian noise of standard deviation σ n =0.02 and two different levels of blur. The top row of Fig. 6: (a) and (b), show the images blurred with a Gaussian kernel of σ=2 and 3, respectively, each with a noise of σ n =0.02.

Fig. 2
figure 2

Original Test Images used for different experiments (a) Trui: 256×256, (b) Man: 1024×1024

Full size image

4.1.1 Selection of filter parameters

The proper selection of different parameters of a filter is crucial for getting the best results from that filter. The output of the proposed filter is affected mainly by the regularization parameters λ and β, the contrast parameter α (in Eq. (22)) and the number of iterations applied. The selection of proper regularization weight λ is important to get a good restoration of the image.

In the proposed model (25), the regularization parameter λ controls the amount of penalty applied to the L 2-distance square between k∗u and u 0. According to (4), the squared L 2-distance between k∗u i and u 0, where u i is the ideal clean image, is equal to the variance of the additive Gaussian noise n. Therefore, an appropriate λ should give a solution u of (25) satisfying ∥k∗u−u 0∥≈∥k∗u i −u 0∥. A large value of λ ignores the diffusion term in (25) and causes the restored images to be noisy; while a very small λ will eliminate small-scale details in the image. The issue of automatically selecting λ is important, but beyond the scope of the present work. In general, the value of λ should be inversely proportional to the noise variance. In our experiments, we used the formula \(\lambda = C / \max(\sigma_{n}^{2} , 10^{-12} )\), for images with intensity scaled to the range [0,1], where σ n is the standard deviation of the Gaussian noise and C is a constant. The value of constant C was determined empirically so that the restored images had maximum possible signal-to-noise ratios (SNRs). The regularization parameter λ is found in the same way for the other two algorithms also which are compared with the proposed algorithm. This is done to ensure that we compare the best possible result from each of the algorithms considered. The constant C is found to take a value of 0.01 to 0.1 for the proposed method in most of the test cases. More sophisticated techniques exist for automatic regularization parameter selection such as L-curve method [17, 18]. However, these methods require intensive computations involving the operator K.

In order to avoid overload computing and achieve optimal results, different stopping rules are available in the literature. In this experiment and all the following experiments, we start the proposed algorithm by employing the degraded (blurred and noisy) image as the initial guess and the process is terminated if the normalized norm of the difference between two successive iterates is within a prescribed tolerance factor of the current iterate, i.e.,

$$ F^n = \frac{\|u_n -u_{n-1}\|}{\| u_n\|} \leq \mathit{tol} $$
(37)

Figure 3 shows variation of F n with number of iterations for the proposed method when applied to the “Trui” image in Fig. 6(b) (Gaussian blur of σ=3 and Gaussian noise of σ n =0.02). In the numerical implementation, a time step of Δt=0.1 is set for the proposed method. Note that, although the proposed method is terminated using the stopping criterion (37) with a tol factor of 10−8 for the degraded image in Fig. 6(b) (which will cause the evolution to stop by around 128 iterations), we let the PDE run until 500 iterations to see the stability of our method. The evolution of algorithms [41] and [29] are also started by employing the degraded image as the initial guess and the process is terminated by the same criterion described above.

Fig. 3
figure 3

The stopping criterion for the proposed method

Full size image

The values of parameters β and α also affect the image restoration quality significantly. As discussed in Sect. 3.2, the term ∇g.∇u increases the speed of level set evolution by attracting the evolving level curves towards the edges and thereby preserves well the location of edges. On the other hand, the contrast parameter α in the edge stopping function g(.) (22) can also be adjusted to preserve the useful features in an image. A low value of contrast parameter will try to preserve the low contrast features in the image. Since both β and α affect the edge preservation capability of the filter, varying one of them affects the performance of the other. Figures 4 and 5 show the variation in performance (in terms of SNR over iterations) with parameter β for two different values of α when applied to the “Trui” image in Fig. 6(b). It can be observed from Figs. 4 and 5 that the SNR of the restored image is improved at a higher rate for a higher value of beta compared to an evolution with a lower value of beta or zero beta. In this particular example, the PDE evolution will be stopped around 128 iterations as per the stopping tolerance. A value of β=1 gives the best SNR at 128 iterations. However, as the number of iterations increases, the SNR value decreases and the rate of deterioration of SNR is higher for a higher value of beta. Also the deterioration starts at an early point for a higher value of beta. This is expected because at the later stages of evolution, a higher value of β causes more and more image sharpening and contrast enhancement. Because of this, a very high value of β will not be able to achieve considerable SNR improvement before it starts to degrade. Thus, the β value should not be made too high. Considering the above facts, we use a continuation strategy for the value of parameter β where the initial β value is reduced successively during the PDE evolution to get a good quality restoration. The higher values of β in the early stages of evolution helps to get a high quality/SNR image and the successively decreased β keeps the high quality of the image without over sharpening the edges. For a higher value of contrast parameter α (see Fig. 5), the deterioration of SNR starts at an even early point when compared to a lower value of α. We tested the method with different values of β and α and the values producing the maximum SNR is chosen in each case. In all our experiments, a β value of 1 or 2 produced the optimum performance and the optimum α is found to vary between 0.001 to 0.03 depending on the image features. For the “Trui” image with a blur of σ=3 and noise of σ n =0.02, the maximum SNR is achieved by β=1 and α=0.005.

Fig. 4
figure 4

SNR versus iterations for different values of β when α=0.005

Full size image
Fig. 5
figure 5

SNR versus iterations for different values of β when α=0.02

Full size image
Fig. 6
figure 6

(Top row) Trui degraded images with noise of standard deviation σ n =0.02 and different levels of blurring (a) σ=2 (b) σ=3; (second row) (c), (d) corresponding reconstructed images by MO; (third row) (e), (f) by Welk model; (bottom row) (g), (h) by the proposed method

Full size image

The optimum set of filter parameters used for the present experiment are given in Table 1. The reconstructed images obtained by methods [29], [41], and the proposed method are shown in the second, third, and fourth rows of Fig. 6, respectively. From Figs. 6(c) and (d), we can see that method [29] eliminates many important details in the image and the restored images are less sharper when compared to the results obtained by other methods. Also, the edges appear more rounded at the sharp corners. The rounding of the sharp corners is more severe for higher levels of blurring. Figures 6(g) and (h) show that the proposed method achieved considerable improvement in the image quality compared to the degraded images and the restored images given by other methods. Even at high levels of blurring, the image is well restored by preserving all important details in the image and minimal rounding of sharp corners. Many low contrast features eliminated by the other two algorithms are retained by the proposed algorithm. However, we notice that the proposed algorithm produces more block effect compared to the other two algorithms. This is because of the shock term present in the proposed PDE, which acts as an inverse heat equation near the object boundaries, and thereby preserving and sharpening edges. This term has characteristics similar to the shock filters introduced by Rudin and Osher [31], which is known to reconstruct piecewise constant (patches) images [6]. The quantitative results are compared in Table 2. High ISNR and FOM values can be seen for the proposed method for both blur levels. However, the computing time of the proposed method is slightly higher when compared to the MO model [29]. It should also be mentioned that the Welk model [41] requires a much higher computing time when compared to the proposed method and [29].

Table 1 Optimal set of filter parameters used for the “Trui” image with noise standard deviation σ n =0.02 and different levels of blur σ=2,3
Full size table
Table 2 Results obtained with different filters applied to the Trui image with noise σ n =0.02 and different levels of blurring with σ=2,3
Full size table

Below we summarize the main steps of our level set based deconvolution algorithm (see Algorithm 1).

Algorithm 1
figure 7

Level set based deconvolution algorithm

Full size image

In the next experiment, we consider the “Trui” image again and the image is corrupted with a Gaussian blur of σ=2 and different levels of Gaussian noise. The top row of Fig. 7: (a)–(c), show the degraded images with Gaussian noise of standard deviation σ n =0.02, 0.05, and 0.07, respectively. The various parameter settings used for this experiment are given in Table 3. The results obtained by different methods for this experiment are shown in Fig. 7 and Table 4. From Table 4, we observe that for all the noise levels, the proposed method obtained the highest ISNR and FOM values.

Fig. 7
figure 8

(Top row) Blurred and noisy Trui images with blurring parameter σ=2 and different levels of Gaussian noise (a)–(c) σ n =0.02,0.05,0.07, respectively; (second row) (d)–(f) corresponding reconstructed images by MO model; (third row) (g)–(i) by Welk model; (bottom row) (j)–(l) by the proposed method

Full size image
Table 3 Optimal set of filter parameters used for the “Trui” experiment with blur parameter σ=2 and different levels of Gaussian noise with σ n =0.02,0.05, and 0.07
Full size table
Table 4 Results obtained with different filters applied to the Trui image with blur parameter σ=2 and different levels of Gaussian noise with σ n =0.02,0.05, and 0.07
Full size table

The numerical results are further supported by qualitative examination. The restored images using MO model [29], Welk model [41], and the proposed method are shown in the second, third, and fourth rows of Fig. 7. From Fig. 7, we can see that the proposed method yielded, in all cases, a significant improvement in image quality. Even at a high level of noise, the proposed method effectively removes noise while preserving important features of the image. More low contrast features are preserved by the proposed method when compared to other two models. The restored images obtained by MO model [29] are less sharper and the edges appear more rounded at the sharp corners. The Welk model [41] gives a much better edge/detail preservation compared to [29]. However, the Welk model did not clearly mark the low contrast edges as the proposed method did. Of course, the contrast parameter α can be reduced to better preserve the low contrast edges in Welk model, but the method fails to satisfactorily eliminate the noise in this case.

As a next example, we show the performance of different models when applied to the “man” image in Fig. 2(b). In this experiment, the “Man” image is corrupted with a Gaussian blur of σ=7 and a Gaussian noise of standard deviation σ n =0.02. Figure 8 shows the degraded and restored images obtained by different filters. For this experiment, we used F n≤10−9 as the stopping tolerance. The ISNR and FOM values obtained by each method are also given with the restored images.

Fig. 8
figure 9

(a) Man blurred with σ=7 and a noise of σ n =0.02; (b) restored image by MO; (c) by Welk model; (d) by the proposed method

Full size image

4.2 Experiments with real blurred images

Besides testing the selected methods with synthetically degraded images, we tested different algorithms using a number of real blurred photographs. Figures 9 and 10 show the results obtained by different filters when applied to two real out of focus blurred images. Figures 9(a) and 10(a) are taken from the Real Blurred Image Database (BID) [1]. The images in this database were taken by consumer cameras and Figs. 9(a) and 10(a) are two of the 142 out-of-focus images in this database. These two images contain different levels of blur with a significant amount of noise in both. The “Nemo” image contains a higher level of blur compared to the “building” image. We can see that the recovered images obtained by the proposed method are more sharper and have more visible details than the blurred ones and the other reconstructed results. The restoration quality of the proposed method seems to be better than other methods by visual comparison. The blurring PSF is assumed to have a width of σ=7 for the “Nemo” image and σ=3 for the “building” image. The other parameters are given values as follows: λ=125, α=0.005, β=2, and tol=10−8 for the “building” image and λ=250, α=0.005, β=1, and tol=10−8 for the “Nemo” image.

Fig. 9
figure 10

(a) Nemo image with real out-of-focus blur; (b) restored image by MO; (c) by Welk model; (d) by the proposed method

Full size image
Fig. 10
figure 11

(a) Building image with real out-of-focus blur; (b) restored image by MO; (c) by Welk model; (d) by the proposed method

Full size image

5 Conclusion

We have presented a new nonlinear PDE model for image deblurring and denoising based on evolution of image level sets. The proposed method is capable of effectively deblurring and denoising the image while preserving and enhancing the important features of the image. The numerical implementation of the method is based on the upwind finite difference scheme proposed by Osher and Sethian. The performance of the method is analyzed using different synthetic and real degraded images having different levels of blur and noise. The favorable performance of our algorithm has been demonstrated visually and quantitatively.