Two soft-thresholding based iterative algorithms for image deblurring

Abstract

Iterative regularization algorithms, such as the conjugate gradient algorithm for least squares problems (CGLS) and the modified residual norm steepest descent (MRNSD) algorithm, are popular tools for solving large-scale linear systems arising from image deblurring problems. These algorithms, however, are hindered by a semi-convergence behavior, in that the quality of the computed solution first increases and then decreases. In this paper, in order to overcome the semi-convergence behavior, we propose two iterative algorithms based on soft-thresholding for image deblurring problems. One of them combines CGLS with a denoising technique like soft-thresholding at each iteration and another combines MRNSD with soft-thresholding in a similar way. We prove the convergence of MRNSD and soft-thresholding based algorithm. Numerical results show that the proposed algorithms overcome the semi-convergence behavior and the restoration results are slightly better than those of CGLS and MRNSD with their optimal stopping iterations.

Introduction

Image deblurring is a process of reconstructing an approximation of an image from an observed but degraded image, which is often modeled as the solution of the linear operator equation

$$\mathit{Kf}+e=g\text{,}$$

where $f\in {\mathbb{R}}^{n^2}$ is a vector representing the true $n\times n$ image we aim to recover, $e\in {\mathbb{R}}^{n^2}$ represents random noise, $g\in {\mathbb{R}}^{n^2}$ stands for the observed distorted image, and $K\in {\mathbb{R}}^{n^2\times n^2}$ is a blurring matrix with special structures [30], [40]. Such problems arise in applications such as astronomy, medical imaging, geophysical applications and many other areas [18], [19], [20], [23], [28], [32], [39], [48], [54], [55]. Typically Eq. (1) comes from the discretization of an ill-posed continuous model, that is, the matrix K is ill-conditioned and noise in the data may give rise to significant errors in the computed approximate solution. As a result, directly solving the equation $\mathit{Kf}=g$ does not yield an accurate and stable approximate solution and it is necessary to resort to a regularization method. In the literature many regularization techniques can be found, such as Tikhonov regularization [52], truncated singular value decomposition (TSVD), truncated iterative algorithms (e.g. steepest descent and conjugate gradient (CG) iterations) [18], [54] and hybrid approaches [8], [33], [35], [36], [45].

A suitable value of the regularization parameter is important when incorporated with a regularization approach. For Tikhonov regularization, various parameter-choice techniques can be used, such as the discrepancy principle [41], the L-curve [18], [28], generalized cross validation (GCV) [21], the weighted-GCV (W-GCV) [14] and the fixed point algorithm (FP) [3]. These parameter-selection methods have both advantages and disadvantages and it is nontrivial to choose an ‘optimal’ regularization parameter [28], [54].

Iterative regularization algorithms like CG and steepest descent can be favorable alternatives to Tikhonov regularization [10], [18], [42], [49], [50], [54]. They access the coefficient matrix K only via matrix–vector multiplication with K and/or $K^T$. It is known that applying these iterative regularization algorithms to solving the linear system $\mathit{Kf}=g$ is often hindered by a semi-convergence behavior. That is, the first few iterations produce regularization solutions and, after some ‘optimal’ iteration, the approximate solutions converge to some other undesired vector. This undesired vector is contaminated by errors and is therefore a poor approximation. In other words, an imprecise estimate of the termination iteration is likely to result in a poor approximate solution and hence it becomes crucial to decide when to stop the iterations. Parameter-selection methods such as the discrepancy principle and the L-curve can be used to choose such a proper termination, but it is also nontrivial as in the case for Tikhonov regularization.

The difficulty in determining the stopping iteration number of iterative regularization algorithms can be partially alleviated by employing hybrid approaches [4], [9], [12], [14], [26], [27]. Lanczos-hybrid type approaches combine an iterative Lanczos bidiagonalization algorithm with a regularization algorithm such as Tikhonov regularization and TSVD at each iteration. Regularization is therefore achieved by Lanczos bidiagonalization filtering and appropriately selecting a regularization parameter at each iteration. Recently, parameter-selection methods such as W-GCV and FP have been studied for the Lanczos-Tikhonov hybrid approach, see [4], [14]. The W-GCV based Lanczos-Tikhonov hybrid approach makes the solution be less sensitive to iteration number. However, it is characterized by the semi-convergence property as the iteration proceeds. The GKB-FP algorithm in [4] combines a partial Golub-Kahan bidiagonalization (GKB) iteration with Tikhonov regularization in the generated Krylov subspace and the regularization parameter for the projected problem is chosen by FP. In some cases, GKB-FP yields more accurate solutions than W-GCV based Lanczos-Tikhonov. But in some cases the two methods perform comparably.

In this paper, we propose two iterative algorithms based on iterative regularization algorithms and soft-thresholding for image deblurring. Recall that it is the noise in the right-hand side g and its propagation with iterations that are the main reason of the semi-convergence behavior of iterative regularization algorithms like CGLS and MRNSD. Therefore, we propose to combine the iterative regularization algorithms with a noise reduction technique like soft-thresholding at each iteration to suppress the propagation of noise and thus overcome the semi-convergence behavior. One of the proposed algorithms combines CGLS with soft-thresholding at each iteration and another combines MRNSD with soft-thresholding in a similar way. The resulting algorithms are stable and very effective in practical applications. We prove the convergence of MRNSD and soft-thresholding based algorithm. Numerical experiments show that the proposed algorithms overcome the semi-convergence behavior and the restoration results are slightly better than those of CGLS and MRNSD with their optimal iterations.

The outline of the paper is as follows. In Section 2.1 we first review the classical CGLS iteration and then give soft-thresholding and CGLS based iterative algorithm, called CGLS-like. A widely used satellite test problem is considered to demonstrate the utility of CGLS-like compared with CGLS. In Section 2.2 we present an MRNSD-like algorithm and prove its convergence. Several numerical examples are given in Section 3 to illustrate the efficacy of the proposed algorithms. Finally Section 4 gives some conclusions.