Image Motion Deblurring Based on Salient Structure Selection and L0-2 Norm Kernel Estimation

Show more

1. Introduction

Motion blur is caused by the relative displacement between the camera and the target due to the camera or a hand shake. With the popularity of the camera in recent years, the blur is very common in life, so it’s important for the image motion deblurring. However, motion deblurring is a completely challenging problem since it’s an ill-posed problem. Ordinarily, if the motion blur is shift-inva- riant, the image blur process can be modeled as:

where is the known blur image, is the latent image, is a motion blur kernelor a point spread function(PSF), is noise produced during image acquisition, is the convolution operator. In general, the image deblurring could be divided into two types-non-blind: deconvolution and blind deconvolution. In non-blind image deblurring method, the blur kernel and blurred image are known, and the major problem is the deconvolution. In the blind image method, the kernel is usually unknown when the blurred image is acquired in life. In this paper, we are more concerned about the blind image. One of the most difficult problem of the blind image deblurring method is the available information is too little, only one blurred image, we need to estimate the blur kernel from the blurred image, and then restore the latent image by the deconvolution operation of the kernel and the blurred image.

The kernel estimation is an important step in the deblurring process, since the kernel will impact directly on the restoration of latent image. The awful or inaccurate kernel will produce ringing artifact in the latent image. At the beginning, the researchers used some regularization to estimate the accurate kernel [5] [9], but this approach is very costly. Cho [2] used bilateral filtering and shock filtering to predict the image edges for the kernel estimation, but this method is too simple.

Now, we use a more effective image structure extraction algorithm. It avoids the negative effect of the details on the kernel estimation. Meanwhile, we propose a novel method of kernel estimation, it can not only estimate the kernel much faster but also suppress the noise, and guarantee the continuity of kernel. The coarse-to-fine iterative process is taken. The image structure is selected from the blurred image. Then, the kernel can be obtained from the image structure. The latent image, which be got from the estimated kernel and the given blurred image, is prepared for the next finer level.

2. Related Work

Image motion deblurring began to be studied in the last century 60’s, in 1967, Helstron et al. proposed the classical Wiener filter. In 70’s, Richardson and Lucy proposed the RL algorithm based on Bayesian theory, but this method couldn't get the satisfying result since they didn’t take into account the effects of noise and the algorithm model was too simple. Since twenty-first Century, researchers have made great progress in the field of image motion deblurring, they utilized the priors of the image and kernel to restore the latent image. Fergus et al. [3] proposed the image gradient probability distribution has a heavy-tailed distribution, and used this prior of image as the basis for the restoration of the latent image with the RL algorithm. Shan et al. [8] utilized subsection to model the heavy-tailed distribution, and used the image intensity, first and second derivative to restored the image, but it cost a lot of time by reason of too much data to be used. Cho and Lee [2] proposed an algorithm based on edge prediction, employing a bilateral filter and shock filter to denoise and preserve edge. Then they used the edge to estimate the kernel and updated the intermediate latent image. Finally, they alternately iterated this process to get the final clear image. Comparing with Shan et al. [8], as it turned out, this method obviously improved the deblurring speed, and had a wonderful result. Xu & Jia [9] discovered that these details had a negative impact on the kernel estimation, so they used a model based on image gradient to eliminate the details, and ISD was employed to refine the kernel. Pan et al. [7] proposed an algorithm which utilized the salient structure to estimate the kernel, it could get better results when the kernel size is large and the blurred image had complex structure, but it need a lot of time when the kernel size is large. Long et al. [6] proposed a kernel fusion method which used several state-of-the-art motion deblurring methods to estimate the kernel. They trained a more precise kernel via the several kernel results. However this approach was dependent on these state-of-the-art methods.

3. Our Method

Our method focuses on the salient structure selection and the kernel estimation. An effective salient structure extraction method is critical to the kernel estimation, and the accurate kernel is indispensable to the deconvolution. Figure 1 shows the image structure and the kernel in the reconstruction process. Both image structure selection and kernel estimation are under the multi-scale iteration.

3.1. Effective Salient Structure Selection

We find that the effective image structure facilitates the kernel estimation. In previous researches, bilateral filtering and shock filtering are used to predict the image edges [2]. In this paper, we select an image smoothing algorithm based on norm [10] to extract the outstanding structure. -norm can smooth the region which gradient is small. The structure extraction model is defined as:

(1)

where is the structure image, is the blurred image, is the coordinate of the image pixel, which can be written as

(2)

is the -norm of. It denotes the number of non-zero pixels, and respectively denotes the absolute value of image gradient in the direction of horizontal and vertical coordinates.

In addition, structures which are smaller than the size of kernel will have a negative impact on the kernel estimation. While, inaccurate kernel fail to restore image. So we add ar(x) to the model which showed as model (1).

Figure 1. The image reconstruction process. The first line shows the image structure and the second line shows their corresponding kernel.

(3)

Formula (3) is first used in [9], is the gradient of the blurred image, is the absolute value, is a window centered at the pixel of. We assume that and respectively express Formula (3) in the direction of horizontal and vertical. Then, we solve model (1) by substituting two auxiliary variables of, therefore, model (1) is transformed to minimizing, shown as Formula (4) and we call it model (4) in the following paragraphs,

(4)

The solution of model (4) can be decomposed into two sub problems―and:

The sub problem about:

(5)

We can use the Fast Fourier Transforms (FFT) to compute. Based on Paseval theorem, the solving equation can be expressed as:

(6)

where and represent the Fast Fourier Transforms and its inverse operation respectively, and denote the gradient filter in direction and direction, is the element-wise multiplication operator, is the conjugate operator.

The sub problem about:

(7)

We add and to Formula (7) and use and to replace and respectively. As Formula (8) shows.

(8)

According to [10], we can get the result of Formula (8) as following

(9)

Proof details can be found in [10]. After obtaining the salient structure of image, we use the shock filter to further enhance the structural information. Figure 2 shows the different results between the model with filter and the model without filter. We can see that the kernel and latent image with used are more satisfying than without used.

(a) (b) (c) (d)

Figure 2. Effect of. (a) Blurred image; (b) result of Pan [7]; (c) our result without; (d) our result with.

3.2. The Kernel Estimation

In the last few years, a variety of regularizations were used to estimate the kernel, the most commonly used were norm [1] [2] [9] [11] and norm [4] [8]. Although norm can be solved fast, it always produce noise so that it cannot achieve an accurate kernel. Pan [7] employed and norm in estimating kernel, but it did not combine the two regularization in essence, the model of Pan is shown as Formula (10)

(10)

where the first submodel is data fidelity term, and is the gradient of the blurred image, is the gradient of the structure image, and are the weight value. Formula (10) is a non-convex function, and it is difficult to be minimized. Pan minimized this function by using iterative reweighed least square (IRLS). IRLS requires a lot of time because of the complexity of computation.

Now, we propose a new kernel estimation method based on norm. In fact, the blur kernel is the path of camera movement, so the kernel is sparse. For the sparsity of the kernel, we utilize norm ensure it. But norm can’t preserve the continuity in general. So norm is used to guarantee the continuity. And our model can be written as Formula (11) and we call it model (11) in the following paragraphs.

(11)

In order to solve model (11), we add two auxiliary variables into model (11), model (11) can be rewritten as:

(12)

We call it model (12) and the solving of it is same to Section 3.2.

To remove noise, we set the kernel elements with the value smaller than 0.075 of the biggest one to zero. Then, the remaining non-zero values are normalized so that their sum becomes one. The experimental results will be compared in Section 4.

3.3. The Latent Image Reconstruction

The latent image can be restored via the deconvolution operation of the kernel and blurred image. In order to ensure the details and smoothness of the latent image, as well as suppress ringing artifacts produced in process of deconvolution, we use norm as regularization to restore the latent image, the model can be expressed as Formula (13).

(13)

Formula (13) is a nonconvex function, so IRLS can be used to minimize it.

4. Analysis and Experimental Results

4.1. Analysis

From Section 3, we can see that our method mainly takes advantage of regularization. norm has the excellent effect on ensuring image sparsity on the blur kernel, because kernel is the displacement path generated by the camera shake. This path is sparse in the image. On the blurred image, the degeneration of image details is more serious than the image outline. So it is more effective to using the image structure to estimate the kernel. The image structure is also sparse.

For the image structure extraction and the kernel estimation, we both execute in the gradient image. Because of the pixel value of gradient image are all zero in addition to the outline section. It can improve execution efficiency.

4.2. Experimental Results

There are several parameters in our algorithm. In model (1), we set, in model (12), we set = 0.1 or 0.5 and. We use MATLAB R2015b to write code. Figure 3 shows our results in comparison with Xu & Jia [9], Pan [7]. Because of Pan use the IRLS (iterative reweighed least square) to solve Formula (10) at the stage of kernel estimation, it is very time-consuming. We use the Fast Fourier Transforms to solve our models, so our algorithm is more efficient. Table 1 shows the time contrast results between Pan [7] and our algorithm. Figure 3 shows the pictures we used and comparison results among Xu & Jia [9], Pan [7] and our algorithm.

The complex building images are challenging for all methods, because the building images contain too many edges, the invalid edges will restrict the image restoration. Figure 4 shows that, our method can result the commendable latent images.

Table 1. The contrast to Pan [7] in time (s: seconds).

(a)(b)(c)(d)

Figure 3. The comparison results among Xu & Jia [9], Pan [7]and our algorithm. From left to right respectively are blurrd images, results of Xu & Jia [9], results of Pan [7] and our results. The lower right corner of the image is the estimated kernel.

(a) (b) (c) (d)

Figure 4. Comparisons on complex blurred building image. (a) Input; (b) Krishnan [4]; (c) our; (d) our kernel.

We evaluate our results on the dataset in [5] by comparing the Peak Signal to Noise Ratio (PSNR) and Structural Similarity (SSIM) with Xu & Jia [9] and Pan [7]. In Figure 5, PSNR is employed to compare the reconstruction accuracy for the latent image. And Table 2 shows the SSIM results of Xu & Jia [9], Pan [7] and our algorithm. We can see that our accuracy is higher than other methods in most cases.

5. Conclusion

In this paper, an effective image structure extraction algorithm was used to select the salient structure. It eliminated the details of image to avoid the negative effects for the kernel estimation. Meanwhile, a novel kernel estimation method was proposed. It can not only ensure the sparsity of kernel, but also guarantee

Figure 5. The PSNR contrast of Xu & Jia [9], Pan [7] and our algorithm.

Table 2. The SSIM contrast of Xu & Jia [9], Pan [7] and our algorithm.

the connectivity. This kernel estimation model can be translated into convex function, so it can achieve the optimum solution fast. The experimental results show that our algorithm can provide reliable kernel and image. Next stage, we will extend our method to handle non-uniform deblurring.

Acknowledgements

This work is partially supported by National Natural Science Foundation of China (Grant No. 61472305), Science and technology project of Shaanxi province (Grant No. 2016GY-033).

References

[1] Cao, Z., Wei, Z. and Zhang, G. (2015) Robust Deblurring Based on Prediction of Informative Structure. Iet Image Processing, 9, 827-835.
https://doi.org/10.1049/iet-ipr.2014.0948

[2] Cho, S. and Lee, S. (2009) Fast Motion Deblurring. Acm Transactions on Graphics, 28, 89-97. https://doi.org/10.1145/1618452.1618491

[3] Fergus, R., Singh, B., Hertzmann, A., et al. (2006) Removing Camera Shake from a Single Photograph. Acm Transactions on Graphics, 25, 787-794.
https://doi.org/10.1145/1141911.1141956

[4] Krishnan, D., Tay, T. and Fergus, R. (2011) Blind Deconvolutionusing a Normalized Sparsity Measure. IEEE Conference on Computer Vision & Pattern Recognition. IEEE, 233-240.

[5] Levin, A., Weiss, Y., Durand, F., et al. (2009) Nderstanding and Evaluating Blind Deconvolution Algorithms. 2013 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 1964-1971.

[6] Long, M. and Liu, F. (2015) Kernel Fusion for Better Image Deblurring. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE, 371-380.

[7] Pan, J., Liu, R., Su, Z., et al. (2013) Kernel Estimation from Salient Structure for Robust Motion Deblurring. Signal Processing Image Communication, 28, 1156- 1170. https://doi.org/10.1016/j.image.2013.05.001

[8] Shan, Q., Jia, J. and Agarwala, A. (2008) High-Quality Motion Deblurring from a Single Image. Acm Transactions on Graphics, 27, 15-19.
https://doi.org/10.1145/1360612.1360672

[9] Xu, L. and Jia, J. (2010) Two-Phase Kernel Estimation for Robust Motion Deblurring. European Conference on Computer Vision, Springer-Verlag, 81-84.
https://doi.org/10.1007/978-3-642-15549-9_12

[10] Xu, L., Lu, C., Xu, Y., et al. (2011) Image Smoothing via L0, Gradient Mini-mization. Acm Transactions on Graphics, 30, 61-64. https://doi.org/10.1145/2070781.2024208

[11] Zhang, X., Wang, R., Tian, Y., et al. (2015) Image Deblurring Using Robust Sparsity Priors. IEEE International Conference on Image Processing. IEEE.
https://doi.org/10.1109/icip.2015.7350775