# Kernel Optimization for Blind Motion Deblurring with Image Edge Prior

Authors: Jing Wang; Ke Lu; Qian Wang; Jie Jia
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Image motion deblurring with unknown blur kernel is an ill-posed problem. This paper proposes a blind motion deblurring approach that solves blur kernel and the latent image robustly. For kernel optimization, an edge mask is used as an image prior to improve kernel update, then an edge selection mask is adopted to improve image update. In addition, an alternative iterative method is introduced to perform kernel optimization under a multiscale scheme. Moreover, for image restoration, a total-variation-(TV-) based algorithm is proposed to recover the latent image via nonblind deconvolution. Experimental results demonstrate that our method obtains accurate blur kernel and achieves better deblurring results than previous works.


---

## Body

## 1. Introduction

Motion deblurring is a type of image restoration problems [1, 2]. Commonly, image motion blur is caused by camera sensor motion, where the track of the sensor motion is represented by a blur kernel [3]. Theoretically, the motion blur process is modeled as the convolution of the latent image and a blur kernel with additive noise (Figure 1). Therefore, motion deblurring not only solves for blur kernel but also recovers latent image. As a blind deconvolution process, motion deblurring is always split into two stages: kernel estimation and nonblind image deconvolution. Note that motion deblurring with single-input image is more complicated than that with two-or-more-input images because multiple blurred images always provide more information in solving the problem [4–6]. In this paper, we mainly focus on the single-image-based motion deblurring.Figure 1
Image motion blur process.To address such challenging problem, various theories and methods have been proposed. In early days, blind deconvolution recovers sharp images by simple motion and Gaussian blur based on frequency-domain constraints or assumptions [7]. Recently, many researchers believe that the more accurate the obtained kernel is, the more clear the recovered image will be. For this reason, kernel estimation becomes a principal task in motion deblurring research. Several novel ideas based on image spatial domain priors are put forward to solve for the blur kernel. For example, Fergus et al. [8] introduced a statistics research of natural image as image gradient prior. Their method uses a Bayesian approach to solve the kernel and then adopts the Richardson-Lucy deconvolution algorithm to reconstruct the image with the estimated kernel. Jia [9] suggested that the blur kernel can be determined by the transparency on the object boundary, and a maximum a posteriori (MAP) model was implemented to estimate the blur kernel. Cai et al. [10] handled a joint optimization problem with the linearized Bregman iteration method, which maximizes the sparsity of the blur kernel and the latent image under curvelet system and framelet system, respectively. Moreover, Joshi et al. [11] solved the simple motion blur and defocus blur kernel by a predicted sharp edge of the blurry image. Xu and Jia [12] proposed a two-phase kernel estimation scheme, which uses a gradient selection process to measure the usefulness of image edges [13].Even with the estimated kernel, the restoration of the latent image is still a tough problem. In the process of motion blur, the latent image loses much high-frequency information. The traditional methods (inverse filter, wiener filter, etc.) always give undesirable restoration results because of the effect of the additive noise [14, 15]. To overcome such difficulty, novel image restoration method with total variation regularization term was proposed recently which removes the image noise and preserves edge details simultaneously [16, 17]. To solve the total variation deconvolution problem, it is common to transform it into a partial difference equation first. Rudin and Osher [16] proposed a time marching scheme to solve the TV model. Vogel and Oman [18] used the fix point iteration method to optimize the TV image deconvolution. According to the variable split method and half quadratic penalty function method, Wang et al. [19] presented a fast total variation deconvolution (FTVd) algorithm to compute TV image deconvolution. Afonso et al. [20] proposed a split augmented Lagrangian shrinkage algorithm (SALSA), where the augmented Lagrangian method is used in computing. Similarly, Chan et al. [21] adopted the alternating direction method (ADM) which considered another variant of the augmented Lagrangian method.In this paper, a complete blind deblurring algorithm is proposed to handle image motion blur with image edge prior. In kernel optimization, an edge mask is used as image prior to improve kernel update and an edge selection mask is adopted to improve image update. Moreover, an alternative iterative method is introduced to implement kernel optimization under a multiscale scheme. For image restoration, a total-variation-based image nonblind deconvolution algorithm is proposed to restore latent image. The rest of the paper is organized as follows. In Section2, the edge character in the blurry image is analyzed and an edge detection process is introduced. In Section 3, given the image edge prior, a complete blind deblurring algorithm is described including a kernel estimation model and an image restoration model. Then, the algorithm is implemented with motion blurred images and the restored results are shown and discussed in Section 4. Finally, Section 5 concludes our work.


## 2. Image Edge Prior

Motion deblurring is an ill-posed problem where the number of unknowns is more than the number of observed measurements. Generally, the motion blur process can be modeled as(2.1)B=K*I+N,
where B is the blurry image, K is the motion blur kernel, I is the latent image, N is the noise effect, and * is the convolution operator. This model suggests that the blurry image is the convolution of a blur kernel and the latent image. Accordingly, our goal is to solve the kernel and the latent image inversely from a single blurred image, which is obviously an ill-posed problem. Therefore, such inverse problem can be solved only with other necessary prior knowledge being provided.In image processing system, an edge is defined as the continuous boundary pixels that connect two separate regions with changing image amplitude attributes [22–24]. It offers information including magnitude and orientation, which has been widely used as image prior knowledge in solving many image processing and computer vision problems, such as image restoration [11, 13] and image superresolution [25, 26]. After edge detection, there always exist some particular edges caused by blur or noise in edge map. Such edges are called false edges, which can be further removed by other image processing techniques.In motion deblurring problem, it can be seen that the edge in the blurry image usually appears fuzzy or unsharp, as shown in Figures2(c) and 2(d), while the latent image has clear edges, as shown in Figures 2(a) and 2(b). If an edge map can be found from the motion blurred image, which is also assumed to be closed enough to the edge map of the latent image, then it might be used to refine the kernel estimation. In this paper, it is assumed that the fuzzy edges in the blurry image are viewed as false edges, which are removed through an edge detection process. In other words, sharp edges can be found through certain edge detection process. This sharp edge map is taken as an edge prior to improve kernel estimation.Edge features analysis in both motion blurred image and latent image. (a) Edge map before motion blur, (b) close-up of (a), (c) edge map after motion blur, (d) close-up of (c), (e) edge map detected from the blurry image by our edge detection process, and (f) close-up of (e).
(a)(b)(c)(d)(e)(f)The edge detection process finds the presence and locations of the intensity transitions. To find an ideal edge map from the blurry image, a modified edge detection process is used and described as follows. First the blurry image is convolved by the derivatives of Gaussian. Then, the magnitude and orientation of its gradient are computed. Thirdly, a nonmaxima suppression method is used to get the thinned gradient magnitudes. Finally, hysteresis is used to get the sharp edge map by doing threshold operation on the gradient magnitude. Especially, two adaptive thresholds are used to suppress the false edges. As shown in Figures2(e) and 2(f), the detected edge map and its close-up are sufficiently clear and sharp in detail. According to this edge map, the edge locations are labeled in a mask, which is used to solve for the blur kernel as described in the Section 3.


## 3. Blind Deblurring Algorithm

### 3.1. Kernel Estimation Model

Before kernel estimation, the blurry image and the initial kernel, which are later used as the inputs of our algorithm, need to be preprocessed. More specifically, the bilateral filter and the shock filter are used to smooth the noise and keep the edge details, respectively [27]. The blur kernel is defined as a smooth convolution mask with nonnegativity values and normalized. So the initial kernel is set as a unit matrix with unit value at its central position.For kernel optimization, an iterative optimization problem model is constructed, and its task is to optimize the blur kernel and the latent image alternately under a multiscale scheme. The edge map mentioned above is introduced as image prior, which adds mask on both latent image and blurry image. On the other hand, theL1 norm of the kernel is used as a regularization term to suppress the noise in the blur kernel. According to the motion blur model, the minimization energy function for motion blur kernel is as follows:(3.1)min⁡K⁡{‖K*ME(∇I)-ME(∇B)‖2+α‖K‖1},
where ∥K*ME(∇I)-ME(∇B)∥2 is the data fitting term and ∥K∥1 is the L1 regularization term of K.ME is the edge location mask mentioned in Section 2, ∇I is the gradient of latent image, ∇B is the gradient of blurry image, and parameter α controls the relative strength of the data fitting and kernel regularization terms. Before adding the edge maskME, lateral filter is used to suppress noise in blurry imageB. Here an unconstrained iterative reweighted least squares (IRLS) system [28, 29] is adopted to solve this minimization problem, and the conjugate gradient (CG) method is used to solve the inner IRLS system.For latent image optimization, an edge selection mask mentioned in [13] is used to recover a coarse latent image. Image edges do not always profit kernel estimation, so we need an edge selection process to choose useful ones. The energy function is then modeled as follows:(3.2)‖K*I-B‖2+β‖∇I-MS(∇I)‖2,
where ∥K*I-B∥2 is the data fitting term, β∥∇I-MS(∇I)∥2 is the regularization term, β is playing the same role as α, and MS is the edge selection mask. According to Parseval’s theorem, this equation has a closed-form solution by using FFTs:(3.3)I=F-1(F(K)¯F(B)+β(F(∂x)¯F(IMsx)+F(∂y)¯F(IMsy))F(K)¯F(K)+β(F(∂x)¯F(∂x)+F(∂y)¯F(∂y))),
where F denotes the FFT and F-1 denotes the inverse FFT.To solve for the kernel accurately, a multiscale scheme is introduced to implement the whole blind deblurring algorithm. Under this scheme, blur kernel and latent image are estimated by using a coarse-to-fine pyramid of image resolutions. The number of scale levels is computed by the size of blur kernel and the scale level step is2. The blurry image is downsampled as the algorithm input. In each scale, the latent image is updated by solving (3.2). Then the updated latent image is used to update the blur kernel by solving (3.1). Finally, the updated kernel is used in the next scale.


### 3.2. Image Restoration Model

Given the estimated blur kernel, the latent image can be restored by using a nonblind image deconvolution algorithm. As mentioned above, a clear image should have sharp edge details. For this reason, an image restoration model with TV regularization term is built to recover the latent image. This model is a minimum optimization problem:(3.4)min⁡I⁡{λ2‖K*I-B‖2+‖DI‖1},
where ∥K*I-B∥2 is the data fitting term, ∥DI∥1 is the TV regularization term, D is the finite difference operator, and λ is weight factor. When (3.4) is used to restore the latent image, the TV regularization term can keep the image edge details satisfyingly.It can be seen that (3.4) is an L1 norm regularization optimization problem. In this paper, the split Bregman method [30, 31] is introduced to solve the problem. The split Bregman method, proposed by Goldstein and Osher, is a fast scheme to solve a type of optimization problem with the form(3.5)min⁡u⁡{‖l(u)‖1+f(u)},
where l(u) and f(u) are both convex functions. According to the variable split method, the split Bregman method transforms (3.5) into an unconstraint optimization problem with an auxiliary variable and quadratic penalty function. Then this unconstraint optimization model is divided into two or three optimization subproblems and solved alternatively with the Bregman iteration.At first, an auxiliary variableG takes the place of DI, and (3.4) is transformed into a unconstrained optimization equation related to I and G as follows:(3.6)min⁡⁡G,I⁡{λ2‖K*I-B‖2+γ2‖G-DI‖2+‖G‖1}.
Then, (3.6) is divided into two subproblems related to I andG, respectively. According to the Bregman iteration, these two optimization subproblems are modeled as(3.7)min⁡I⁡{λ2‖K*I-B‖2+γ2‖G-DI-b‖2},(3.8)min⁡G⁡{λ2‖G-DI-b‖2+‖G‖1},
where b is an iteration parameter and b=b+(G-DI).To solve these two sub-problems, an alternative minimization method (AMD) is used to optimize them. In each iteration, (3.7) is transformed into the equation as follows:(3.9)(DTD+γλKTK)I=γλKTB+DT(G-b),
whereK andD are both block circulant matrices. So (3.9) is computed by FFTs. On the other hand, (3.8) is optimized by the shrinkage technique, and it can be solved by using the following equation:(3.10)G=max⁡⁡{‖g‖2-1λ,0}g‖g‖2,
where g=DI+b. Interested readers can refer to [32] for more details.


## 3.1. Kernel Estimation Model

Before kernel estimation, the blurry image and the initial kernel, which are later used as the inputs of our algorithm, need to be preprocessed. More specifically, the bilateral filter and the shock filter are used to smooth the noise and keep the edge details, respectively [27]. The blur kernel is defined as a smooth convolution mask with nonnegativity values and normalized. So the initial kernel is set as a unit matrix with unit value at its central position.For kernel optimization, an iterative optimization problem model is constructed, and its task is to optimize the blur kernel and the latent image alternately under a multiscale scheme. The edge map mentioned above is introduced as image prior, which adds mask on both latent image and blurry image. On the other hand, theL1 norm of the kernel is used as a regularization term to suppress the noise in the blur kernel. According to the motion blur model, the minimization energy function for motion blur kernel is as follows:(3.1)min⁡K⁡{‖K*ME(∇I)-ME(∇B)‖2+α‖K‖1},
where ∥K*ME(∇I)-ME(∇B)∥2 is the data fitting term and ∥K∥1 is the L1 regularization term of K.ME is the edge location mask mentioned in Section 2, ∇I is the gradient of latent image, ∇B is the gradient of blurry image, and parameter α controls the relative strength of the data fitting and kernel regularization terms. Before adding the edge maskME, lateral filter is used to suppress noise in blurry imageB. Here an unconstrained iterative reweighted least squares (IRLS) system [28, 29] is adopted to solve this minimization problem, and the conjugate gradient (CG) method is used to solve the inner IRLS system.For latent image optimization, an edge selection mask mentioned in [13] is used to recover a coarse latent image. Image edges do not always profit kernel estimation, so we need an edge selection process to choose useful ones. The energy function is then modeled as follows:(3.2)‖K*I-B‖2+β‖∇I-MS(∇I)‖2,
where ∥K*I-B∥2 is the data fitting term, β∥∇I-MS(∇I)∥2 is the regularization term, β is playing the same role as α, and MS is the edge selection mask. According to Parseval’s theorem, this equation has a closed-form solution by using FFTs:(3.3)I=F-1(F(K)¯F(B)+β(F(∂x)¯F(IMsx)+F(∂y)¯F(IMsy))F(K)¯F(K)+β(F(∂x)¯F(∂x)+F(∂y)¯F(∂y))),
where F denotes the FFT and F-1 denotes the inverse FFT.To solve for the kernel accurately, a multiscale scheme is introduced to implement the whole blind deblurring algorithm. Under this scheme, blur kernel and latent image are estimated by using a coarse-to-fine pyramid of image resolutions. The number of scale levels is computed by the size of blur kernel and the scale level step is2. The blurry image is downsampled as the algorithm input. In each scale, the latent image is updated by solving (3.2). Then the updated latent image is used to update the blur kernel by solving (3.1). Finally, the updated kernel is used in the next scale.


## 3.2. Image Restoration Model

Given the estimated blur kernel, the latent image can be restored by using a nonblind image deconvolution algorithm. As mentioned above, a clear image should have sharp edge details. For this reason, an image restoration model with TV regularization term is built to recover the latent image. This model is a minimum optimization problem:(3.4)min⁡I⁡{λ2‖K*I-B‖2+‖DI‖1},
where ∥K*I-B∥2 is the data fitting term, ∥DI∥1 is the TV regularization term, D is the finite difference operator, and λ is weight factor. When (3.4) is used to restore the latent image, the TV regularization term can keep the image edge details satisfyingly.It can be seen that (3.4) is an L1 norm regularization optimization problem. In this paper, the split Bregman method [30, 31] is introduced to solve the problem. The split Bregman method, proposed by Goldstein and Osher, is a fast scheme to solve a type of optimization problem with the form(3.5)min⁡u⁡{‖l(u)‖1+f(u)},
where l(u) and f(u) are both convex functions. According to the variable split method, the split Bregman method transforms (3.5) into an unconstraint optimization problem with an auxiliary variable and quadratic penalty function. Then this unconstraint optimization model is divided into two or three optimization subproblems and solved alternatively with the Bregman iteration.At first, an auxiliary variableG takes the place of DI, and (3.4) is transformed into a unconstrained optimization equation related to I and G as follows:(3.6)min⁡⁡G,I⁡{λ2‖K*I-B‖2+γ2‖G-DI‖2+‖G‖1}.
Then, (3.6) is divided into two subproblems related to I andG, respectively. According to the Bregman iteration, these two optimization subproblems are modeled as(3.7)min⁡I⁡{λ2‖K*I-B‖2+γ2‖G-DI-b‖2},(3.8)min⁡G⁡{λ2‖G-DI-b‖2+‖G‖1},
where b is an iteration parameter and b=b+(G-DI).To solve these two sub-problems, an alternative minimization method (AMD) is used to optimize them. In each iteration, (3.7) is transformed into the equation as follows:(3.9)(DTD+γλKTK)I=γλKTB+DT(G-b),
whereK andD are both block circulant matrices. So (3.9) is computed by FFTs. On the other hand, (3.8) is optimized by the shrinkage technique, and it can be solved by using the following equation:(3.10)G=max⁡⁡{‖g‖2-1λ,0}g‖g‖2,
where g=DI+b. Interested readers can refer to [32] for more details.


## 4. Experiments

In this Section, the proposed blind deblurring algorithm was tested with both synthetic motion blurred images and real-life motion blurred images. In the kernel estimation process, the parametersα and β were set as 1e-4,2e-3, the initial minimum kernel size was 3×3, and the initial maximum kernel size was 35×35. According to the multiscale scheme, the outer iteration was controlled by the maximum kernel size and the inner iteration was set as 8 uniformly. In the image recovery process, the parameter λ was set as 2e+3. Our algorithm was implemented on Matlab experimental platform.To verify the validity of our algorithm, the synthetic blurry images were generated by convolving the synthetic images with a15×15 synthetic kernel. The Gaussian white noise was added whose standard deviation was 0.001. Figure 3 shows the experimental results of several synthetic images. The deblurring results are extremely close to the original synthetic images, and they manifest the significance of the proposed algorithm.Testing our algorithm with the synthetic images. (a)–(c) In order from left to right, the images are the original synthetic images, the synthetic images after motion blur, restored results and estimated kernels by using our algorithm, and the close-ups of them (the red rectangle in the blurry image shows the location of close-ups).
(a)(b)(c)On the other hand, the proposed algorithm was compared with the approach described in [28] by deblurring the real-life motion blur images. In Figure 4, the restored results of some real-life images are given. As shown in recovery results, our method is robust to restored sharp images and accurate kernels. In contrast to the approach in [28], the deblurring images and the close-ups show that our algorithm could obtain clearer image detail information.Testing our algorithm with real-life motion blurry images. (a)–(c) In order from left to right, the images are original blurry images, restored results and estimated kernels by our algorithm, restored results and estimated kernels by using the algorithm in [28] and the close-ups of them (the red rectangle in the original blurry image shows the location of close-up).
(a)(b)(c)


## 5. Conclusion

In this paper, a novel blind deblurring algorithm is presented for motion blur occurring in photography. The approach consists of two stages: kernel estimation and image reconstruction. The edge information in blurry images is explored as an image prior for obtaining accurate blur kernel and the use of total variation regularization keeps image details during image recovery. The proposed algorithm was tested with synthetic and really captured motion blur images. The experimental results demonstrated the efficacy of our algorithm in image motion deblurring. On the other hand, there still exist some defects (cartoon effect and unclear texture detail) in the restored images. Our future work is to extend the current research by considering more complex blurs (such as blur with rotation and shift-variant blur) and other image analysis problems [33–35].



---

*Source: 639824-2012-05-09.xml*