Elsevier

Signal Processing

Volume 103, October 2014, Pages 399-414
Signal Processing

A novel gradient attenuation Richardson–Lucy algorithm for image motion deblurring

https://doi.org/10.1016/j.sigpro.2014.01.023Get rights and content

Highlights

  • A novel blind image deconvolution algorithm for motion deblurring from a single blurred image is presented.

  • A novel GARL algorithm is proposed to alleviate the ringing problem in the classical Richardson–Lucy image deconvolution method.

  • A unified framework for blur kernel estimation and image deconvolution based on bilateral filtering and the GARL algorithm is presented.

Abstract

This paper presents a novel blind image deconvolution algorithm for motion deblurring from a single blurred image. We propose a unified framework for both blur kernel estimation and non-blind image deconvolution by using bilateral filtering (BF) and a new image deconvolution algorithm, called the Gradient Attenuation Richardson–Lucy (GARL) algorithm. In the blur kernel estimation stage, we show that an initial blur kernel, which is used for starting an alternating kernel refinement process, can be obtained from the blurred image with a quadratic regularization approach. In the non-blind image deconvolution stage, we exploit the image gradients and develop the GARL algorithm to alleviate the notorious ringing problem in the Richardson–Lucy-based image restoration approach. Furthermore, the loss of image details due to the suppression of the ringing artifacts around the regions with strong edges is recovered with an incremental detail recovery procedure. The proposed framework is simple yet effective compared to previous statistical approaches. Experimental results on various real data sets are given to demonstrate superior performance of the proposed algorithm over the previous methods.

Introduction

Motion blur is caused by relative motion between the camera and the scene within the exposure time period. Restoring motion blurred images is a long-standing research problem in computer vision and image processing. Various algorithms have been proposed to tackle this problem and they can be roughly categorized into three groups: deblurring from a single image [8], [10], [12], [14], [18], [19], [21], [23], [24], [26], deblurring from multiple images [6], [7], [13], [15], [20], [22], [25], and computational photography [9], [27].

The real camera motion is usually too complicated to estimate from a blurred image when it involves camera rotation or large scene depth variations. To simplify the problem formulation, previous researches usually assumed the camera motion is perpendicular to the optical axes and the effect of scene depth variation can be neglected. In other words, the blur kernel, or named point spread function (PSF), is assumed to be spatially invariant. Under this assumption, a blurred image, B, can be modeled as the convolution of the clear image I, which is the goal of the image restoration, and the blur kernel F:B=IF+Nwhere N is an additive noise image, and ⊗ is the convolution operator. This problem is called blind deconvolution if both I and F are unknown, or non-blind deconvolution if only I is unknown [3].

In this paper, we propose a unified framework to resolve the problem of motion deblurring from a single image under the assumption of spatially-invariant kernel. The proposed framework is based on introducing the concept of gradient attenuation [5] into the Richardson–Lucy (RL) algorithm [1], [2] for both blur kernel estimation and non-blind image restoration. For an input blurred image, we first construct a pyramid representation of this image and estimate the blur kernel in a coarse-to-fine manner. The estimated blur kernel is also represented as a pyramid representation and further used for non-blind deconvolution to restore a ringing-suppressed image. For the non-blind deconvolution, we propose a gradient-attenuated Richardson–Lucy (GARL) algorithm that alleviates the ringing artifact in the RL algorithm and the computation is accomplished efficiently. The flowchart of the proposed motion deblurring framework is illustrated in Fig. 1.

The contributions of this paper are listed as follows:

  • We propose an initial blur kernel obtained from the blurred image with a quadratic regularization approach for starting an alternating kernel estimation process (Initial PSF estimation).

  • We exploit the gradient attenuation concept and modify the standard RL algorithm for suppressing ringing artifacts in the RL-based image deconvolution (GARL algorithm).

  • We propose an iterative details recovery procedure that can recover missing details due to ringing suppression (Details recovery).

  • We combine GARL and bilateral filtering (BF) [4] algorithms for both blur kernel estimation and non-blind deconvolution in a unified framework.

The rest of this paper is organized as follows: The remaining of Section 1 describes the related works. Non-blind deconvolution and blur kernel estimation algorithms are proposed in 2 Non-blind deconvolution, 3 Blur kernel estimation, respectively. Experimental results are reported in Section 4. Finally, we conclude in Section 5.

The blind image restoration problem in (1) is ill-posed because I and F are highly under-constrained and there are infinitely many possible combinations of I and F such that their convolution is equal to the blurred image B. Previous works typically assumed that the blur kernel has a simple parametric form (e.g., single one-directional motion or a Gaussian model). However, as Fergus et al. showed in [8], the blur kernels are usually too complicated to be represented with simple parametric forms. They hereby proposed to utilize ensemble learning to estimate the blur kernel with a sophisticated variational Bayes inference algorithm, which employs the property of specific distributions of image gradients for natural images to approximate the posterior distribution. Levin [10] also exploited image statistics for estimating blur kernels. Nevertheless, the motion blur is assumed to be unidirectional with constant velocity. Jia [12] estimated the blur kernel by using the transparency information of blurred region. The limitation of this method is the need to find regions that can produce high-quality matting results. Dai and Wu [21] also made use of the matting results and proposed an alpha-motion blur constraint model which provides local linear constraint for the blur parameters. Shan et al. [18] proposed two probabilistic models to improve image restoration. One is to model the spatially random distribution of noise, and the other is a smoothness prior model which can reduce the ringing artifacts. Joshi et al. [19] utilized pairs of predicted sharp edge and blurred edge to estimate the blur kernel based on the assumption of blurred step edges such that the suitable kernel is of a small size and described with a single peak. Cai et al. [23] proposed to maximize the sparsity property of motion blur kernel in a curvelet system, which can provide a good constraint on the curve-like geometrical support of motion blur kernel. However, the real blur kernels are often too complicated for this curvelet representation. Levin et al. [24] discussed the limitation of the maximum a posterior (MAP) approach and suggested to estimate the MAP of F alone (marginalizing over I). However, the computational aspects are challenging. Cho and Lee [26] proposed a latent image prediction step, which applied shock filter to recover the sharp edge information for estimating the blur kernel. This gradient prediction step can remove small details and ringing artifacts; however, it also emphasizes image noises, and sometimes this may affect the accuracy of the estimated blur kernel.

A number of recent image processing methods took advantage of sparse representation to resolve different image processing problems. For example, Yan et al. [29] presented an image denoising algorithm based on learning a nonlocal multiresolution dictionary in each decomposition level of the wavelets. Their algorithm was proved to outperform the state-of-the-art image denoising methods from experiments with high-level noises. Recently, Xu et al. [30] proposed a generalized L0 sparse expression for motion deblurring. Their method provides a unified framework for both uniform and non-uniform motion deblurring from a single image. Furthermore, Zhang et al. [31] presented a robust algorithm for recovering a latent sharp image from multiple blurry images. Their algorithm is based on introducing a novel Bayesian-inspired penalty function that couples latent image, blur kernel and noise level and leads to an adaptive sparse prior for the image and blur kernel.

Even with a known blur kernel, the restored image may contain some undesirable reconstruction artifacts, such as ringing artifacts. To overcome this problem, Levin et al. [16] modeled the sparse image derivative distribution as a heavy-tailed function to alleviate the ringing artifacts. This natural image prior encourages the intensities of most image pixels to be locally smooth. Shan et al. [18] proposed a local smoothness prior which assumes the gradients of smooth regions in a blurred image are similar to those in a clear image. Yuan et al. [15], [17] proposed the concept of residual deconvolution and modified the standard Richardson–Lucy (RL) algorithm [1], [2], by incorporating either a gain-control process [15] or a bilateral-filtering-like process [17] for suppressing the ringing artifacts. Some nice image restoration results from their experiments were reported. However, the gain-controlled RL [15] produces over-smooth restoration results. The method proposed in [17] needs to estimate the edge-regularization term pixel by pixel within a local window at each scale and in each iteration of RL, which requires high computation cost. Since the edge-regularization is defined with a bilaterally weighted filter, the restoration results are sensitive to the parameters in the Gaussian kernels, especially in the residual deconvolution process.

Section snippets

Non-blind deconvolution

As mentioned in the previous section, several algorithms were proposed to suppress the ringing artifacts in the restored image [15], [16], [17], [18]; however, these algorithms usually produce over-smoothed images or require high computation costs. In this section, we propose a modified RL algorithm, called the gradient attenuation RL algorithm (GARL), to alleviate ringing artifacts in image deconvolution. This algorithm suppresses the ringing propagation by introducing a gradient attenuation

Blur kernel estimation

In this section, we describe the proposed blur kernel estimation that combines GARL and BF algorithms. Most previous works formulated blind deconvolution as a MAP estimation problem. From Bayes rule and the assumption that the clear image I and the blur kernel F are independent, we can write the posterior probability as follows:P(I,F|B)P(B|I,F)P(I)P(F)where P(B|I, F) is the likelihood term, P(I) and P(F) are the image prior and the kernel prior, respectively.

Maximizing the posterior, Eq. (20),

Experimental results

To show the effectiveness of our algorithm, we demonstrate the proposed image restoration algorithm on several real images, including the blurred images with spatially invariant blurs and ground truth provided by Levin et al. [24] and indoor and outdoor images taken by off-the-shelf hand-held camera in poor lighting environments. We also show various comparisons with previous state-of-the-art methods. The computing platform for our experiments is a PC running MS Windows XP 32 bit version with

Conclusion

In this paper, we proposed a framework for image deblurring from a single blurred image under the assumption of spatially-invariant blur kernel by using the GARL and BF algorithms. The proposed blur kernel estimation is simple but effective compared to the previous methods. The kernel initialization process was proved to be quite effective through experiments. For the non-blind image deconvolution, we proposed the GARL algorithm, which is a combination of a gradient attenuation function and RL

References (31)

  • A. Rav-Acha et al.

    Two motion-blurred images are better than one

    Pattern Recognit. Lett.

    (2005)
  • W.H. Richardson

    Bayesian-based iterative method of image restoration

    J. Opt. Soc. Am.

    (1972)
  • L.B. Lucy

    An iterative technique for the rectification of observed distributions

    Astron. J.

    (1974)
  • D. Kundur et al.

    Blind image deconvolution

    IEEE Signal Process. Mag.

    (1996)
  • C. Tomasi et al.

    Bilateral filtering for gray and color images

    (1998)
  • R. Fattal et al.

    Gradient domain high dynamic range compression

    ACM Trans. Graph.

    (2002)
  • M. Ben-Ezra et al.

    Motion-based motion deblurring

    IEEE Trans. Pattern Anal. Mach. Intell.

    (2004)
  • R. Fergus et al.

    Removing camera shake from a single photograph

    ACM Trans. Graph.

    (2006)
  • R. Raskar et al.

    Coded exposure photography:motion deblurring using fluttered shutter

    ACM Trans. Graph.

    (2006)
  • A. Levin

    Blind motion deblurring using image statistics

    (2006)
  • S. Paris et al.

    A fast approximation of the bilateral filter using a signal processing approach

    (2006)
  • J. Jia

    Single image motion deblurring using transparency

    (2007)
  • S. Cho et al.

    Removing non-uniform motion blur from images

    (2007)
  • Q. Shan et al.

    Rotational motion deblurring of a rigid object from a single image

    (2007)
  • L. Yuan et al.

    Image deblurring with blurred/noisy image pairs

    ACM Trans. Graph.

    (2007)
  • Cited by (29)

    • Robust motion blur kernel parameter estimation for star image deblurring

      2021, Optik
      Citation Excerpt :

      Mathematically, the process of NBID is to implement a deconvolution with the constraint term. Currently, the NBID algorithm is quite mature and has been successfully applied in many fields of research [9–15]. On the other hand, the BID algorithm needs an automatic estimation of the blur kernel, and there are still many challenges in accurately estimating the blur kernel.

    • Blind image deblurring based on the sparsity of patch minimum information

      2021, Pattern Recognition
      Citation Excerpt :

      The most challenging difficulty in image deconvolution lies in the ill-posedness of the inverse problem, as the associate operator is generally not invertible or nearly singular, which makes the restoration highly sensitive to noise [2,10]. To deal with the ill-posedness, a large number of a priori knowledge [32,37,52,53,56] are employed, especially those through regularization [9,13,16,23,36]. Among the different regularizations, total variation (TV) [8,35,36,39] has received great attention and becomes a popular regularizer for ill-posed inverse problems.

    View all citing articles on Scopus
    View full text