Thomas Eboli

Jian Sun

Jean Ponce

Neural Embedding of an Iterative Deconvolution Algorithm for Motion Blur Estimation and Removal

This paper introduces a new learning-based approach to motion blur removal. A local linear motion model is first estimated at each pixel using a convolutional neural network (CNN) in a regression setting. These estimates are then used to drive an algorithm that casts non-blind, non-uniform image deblurring as a least-squares problem regularized by natural image priors in the form of sparsity constraints. This problem is solved by combining the alternative direction method of multipliers with an iterative residual compensation algorithm, with a finite number of iterations embedded into a second CNN whose trainable parameters are deconvolution filters. The second network outputs the sharp image, and the two CNNs can be trained together in an end-to-end manner. Our experiments demonstrate that the proposed method is significantly faster than existing ones, and provides competitive results with the state of the art on several synthetic and real datasets.

Introduction

The goal of blind image deconvolution is to recover a sharp image from a picture degraded by camera shake, object motion or defocus given only the blurry picture of the scene as input. It has wide applications in computational photography, astronomy, microscopy and medical image enhancement for example. Classical methods such as Wiener [START_REF] Xu | Inverse kernels for fast spatial deconvolution[END_REF] and Richardson-Lucy [START_REF] Hadley | Bayesian-based iterative method of image restoration[END_REF] filtering apply inverse filters to the corrupted image but they are known to generate artifacts in the restored images. Variational methods rely on a set of constraints to recover sharp pictures by solving an inverse problem with, for instance, sparsity priors [START_REF] Cho | Fast motion deblurring[END_REF][START_REF] Whyte | Non-uniform deblurring for shaken images[END_REF][START_REF] Michael Ohirsch | Fast removal of non-uniform camera shake[END_REF][START_REF] Schmidt | Bayesian deblurring with integrated noise estimation[END_REF][START_REF] Michaeli | Blind deblurring using internal patch recurrence[END_REF][START_REF] Xu | Unnatural L0 sparse representation for natural image deblurring[END_REF]. These priors are handcrafted and may fail to capture all the constraints that lead to visually appealing images. Recently, convolutional neural networks (CNNs) have also been applied to blind deconvolution problems [START_REF] Xu | Deep convolutional neural network for image deconvolution[END_REF][START_REF] Chakrabarti | A neural approach to blind motion deblurring[END_REF][START_REF] Nah | Deep multi-scale convolutional neural network for dynamic scene deblurring[END_REF][START_REF] Noroozi | Motion deblurring in the wild[END_REF][START_REF] Orest Kupyn | Deblurgan: Blind motion deblurring using conditional adversarial networks[END_REF], case as supervised regression. These methods essentially ignore the underlying "physics" of the image corruption process, but exploit various tricks such as skip connections [START_REF] He | Deep residual learning for image recognition[END_REF], batch normalization [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] or generative adversarial networks [START_REF] Goodfellow | Generative adversarial nets[END_REF] to directly output a sharp image.

The aim of this paper is to combine the classical image processing approach with the modern neural one, embedding an iterative deconvolution algorithm in a CNN, thus obtaining a relatively shallow architecture that can be trained end to end, and yields competitive accuracy and significantly improved speed. We focus on motion blur removal and decompose this task into motion estimation and nonblind deconvolution. Like others, we assume that each image patch is corrupted by a local linear motion [START_REF] Tae | Segmentation-free dynamic scene deblurring[END_REF]. In [START_REF] Sun | Learning a convolutional neural network for non-uniform motion blur removal[END_REF], the authors design a CNN to predict a linear motion kernel per patch in the blurry image for every overlapping patch and they enforce smoothness of the global blur kernel by applying a Markov Random Field algorithm. In [START_REF] Gong | From motion blur to motion flow: A deep learning solution for removing heterogeneous motion blur[END_REF], the authors propose a fully convolutional network (FCN) to predict the non-uniform blur kernel directly for the whole image. The motion estimates can then be fed to a non-blind deblurring algorithm (e.g., [START_REF] Zoran | From learning models of natural image patches to whole image restoration[END_REF]), but this pipeline is not trainable end to end, and it is computationally expensive. The main contributions of this paper can be summarized as follows. [START_REF] Bahat | Non-uniform blind deblurring by reblurring[END_REF] We propose an iterative algorithm that casts non-blind, non-uniform image deblurring as a least-squares problem regularized by natural image priors in the form of sparsity constraints. This problem is solved by combining the alternative direction method of multipliers with an iterative residual compensation algorithm with theoretical convergence guarantees. A finite number of iterations of this algorithm are embedded in a CNN whose trainable parameters are deconvolution filters (see [START_REF] Zhang | Learning fully convolutional networks for iterative non-blind deconvolution[END_REF][START_REF] Gregor | Learning fast approximations of sparse coding[END_REF] for similar ideas in the context of uniform image deblurring or sparse coding). This approach combines high accuracy with faster convergence than other solvers for the same task. [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF] We propose a CNN-based regressor for local linear motion estimation and demonstrate that it is both more accurate and faster than [START_REF] Gong | From motion blur to motion flow: A deep learning solution for removing heterogeneous motion blur[END_REF][START_REF] Sun | Learning a convolutional neural network for non-uniform motion blur removal[END_REF]. By stacking the two networks, we obtain a simple and relatively shallow architecture for blind motion blur removal that can be trained end to end, and is competitive in terms of accuracy with the state of the art [START_REF] Bahat | Non-uniform blind deblurring by reblurring[END_REF][START_REF] Nah | Deep multi-scale convolutional neural network for dynamic scene deblurring[END_REF] on the dataset of [START_REF] Bahat | Non-uniform blind deblurring by reblurring[END_REF], as well as significantly faster.

2 Iterative Non-Blind Deconvolution

Uniform Blur

Let us first consider the case of uniform blur. We use the classical model y = k x + , where x is the (unknown) sharp image, k is the (known) uniform blur kernel, y is the (observed) blurry image, and ∼ N (0, σ 2 ) is an additive noise term. Regularized non-blind deconvolution amounts to solving min x ||k x -y|| 2 2 + λR(x), where R is some regularizer associated with natural images priors. A common prior is to impose sparsity constraints on filtered versions of x. More specifically, we consider here n filters k i , and solve the problem:

min x 1 2 ||k x -y|| 2 2 + λ n i=1 ||k i x|| l with 0 ≤ l ≤ 1. (1)
We use the alternating direction method of multipliers (ADMM) [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF] algorithm to solve Eq. ( 1): We introduce n auxiliary variables z 1 , . . . , z n and expand Eq. (1) as follows:

min x,z 1 2 ||k x -y|| 2 2 + λ n i=1 ||z i || l s.t z i = k i x, ∀i ∈ [1, 2, . . . , n] . (2)
The corresponding augmented Lagrangian is:

L(x, z, α) = 1 2 ||k x -y|| 2 2 + λ n i=1 ||z i || l - n i=1 α i , k i x -z i + ρ 2 n i=1 ||k i x -z i || 2 2 , (3)
where the coefficients α i are Lagrange multipliers and ρ is a penalty parameter. We solve Eq. ( 2) by alternatively updating the variables z i , x, and β i = α i /ρ (scaled Lagrange multipliers).

• z i update : Each one of the n independent optimization problems

min zi λ||z i || l + ρ 2 ||k i x + β i -z i || 2 2 (4)
can be solved in closed-form when l = 0 or l = 1 using hard-or soft-thresholding [START_REF] Elad | Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing[END_REF].

• x update : The related optimization problem is, with z 0 = 1 √ ρ y and k 0 = 1 √ ρ k:

min x n i=0 ||k i x + β i -z i || 2 2 . (5)
This sum of least-squares problems is itself a linear least-squares problem which can be solved by conjugate gradient descent for example, but its special form affords the much more efficient iterated residual compensation (or IRC method presented now). Imagine for the moment that we have a single least-squares problem of the form min x ||k x -y|| 2 . We propose to repeatedly apply an inverse deconvolution filter d (obtained by Wiener filtering for example, more details on this below) to blurry residuals until convergence. We initialize the algorithm with x 0 = d y and repeat the following two steps T times.

1. We compute the blurry residual: r t+1 = y -k x t ;

2. We remove the deblurred residual from x t : x t+1 = x t + d r t+1 .

Proposition : Let δ denote the unit impulse, and H denote the square matrix version of the filter δ -d k. When the spectral radius ρ of H is smaller than 1, the sequence x t converges linearly to x with convergence rate ρ.

Proof. By denoting by x the vectorized version of x, we have, by definition, for t ≥ 1,

x t+1 = x t + d k (x -x t ) = h x t + d k x. (6)
Thus,

x t+1 -x = h (x t -x) ⇐⇒ xt+1 -x = H(x t -x), (7)
and

||x t+1 -x|| 2 F = ||H(x t -x)|| 2 F ≤ ρ 2 ||x -x|| 2 F . (8)
Finally,

||x t+1 -x|| 2 F ≤ ρ 2 ||x t -x|| 2 F . (9)
Empirically, as also shown there, this algorithm limits the artifacts obtained by common deconvolution methods such as Wiener filtering, with accuracy comparable to FFT and conjugate-gradient methods for a fraction of the computational cost of the latter. It is also easily adapted to the sum of least-squares problems of Eq [START_REF] Cho | Fast motion deblurring[END_REF], resulting in Algorithm 2.1. We use finite-support deconvolution filters d i instead of a classical FFT-based approach because they have proven fast and accurate. They are also easily adapted to the non-uniform case, and can be efficiently implemented by local operations. One detail not discussed yet is how we explicitly compute the inverse filters d i . Let us assume that we can compute local deconvolution kernels

d 0 , d 1 , • • • , d n in R w f ×w f for the k i in R w k ×w k such that n i=0 d i k i = δ. (10)
We have in this case

||x - n i=0 d i z i || 2 F = || n i=0 d i (k i x -z i )|| 2 F ≤ n i=0 ||d i || 2 F ||z i -k i x|| 2 F . (11)
As

||z i -k i x|| 2
F is supposed to be close to 0, it is therefore reasonable to take x = n i=0 d i z i as an approximate solution to [START_REF] Cho | Fast motion deblurring[END_REF]. This approximation will of course need to be refined iteratively.

The local deconvolution kernels d 0 , • • • , d n can be computed by solving the linear equations: where matrix K i is the linear operator associated with k i , and di is the vectorized version of d i . This is a under-determined linear system. Writing

n i=0 K T i di = K T 0 , • • • , K T n     d0 . . . dn     = δ, (12)
Q = K T 0 , • • • , K T n , d = [ dT 0 , • • • , dT n ]
T , we can find its minimal-norm solution as

d = Q † δ = Q T (QQ T ) -1 δ, (13)
where

Q † is the right pseudo-inverse of Q. Therefore each di is given by di = K i (QQ T ) -1 δ, for i = 0, • • • , n. (14)
Given the local approximate deconvolution filters, we run the iterative residual compensation algorithm (Alg. 2.1) to minimize the correct residual

n i=1 z i -k i x i . • β i update : The closed-form solution to min βi β i , k i x -z i , ∀i ∈ [1, 2, . . . , n] . ( 15
)
with update rate η i is

β * i = β i + η i (k i x -z i ).

Experimental Evaluation for the Regularized Model

We compare the extension of the IRC algorithm, i.e. Alg. 2.1, with the case of a penalized leastsquares problem. We build a test set made of 20 images taken PASCAL VOC dataset blurred with the 8 kernels from [START_REF] Levin | Understanding and evaluating blind deconvolution algorithms[END_REF]. Overall, we get 160 test images. We compare the IRC algorithm with the fast Fourier transform (FFT)-based algorithm (boundaries are carefully treated), FFT-nopad (no care for the boundaries) and a conjugate gradient descent-based method by solving:

min x ||k x -y|| 2 2 + λ||k 1 x|| 1 + λ||k 2 x|| 1 , (16)
where

k 1 = [-1, 1] and k 2 = [-1, 1] T ).
We set λ = 0.003, 10 iterations of the ADMM algorithm and ρ = 2.43 × 10 -5 , ∀i ∈ [1, . . . , 10] to balance the different terms of Eq. ( 5). Figure 2: For a given patch taken from y, we assume that the corresponding blur kernel can be interpolated by four of the linear motions we have selected beforehand. We apply the corresponding inverse filters, computed ahead of time, to that patch and average the results. Repeating this operation to every overlapping patch of y enables fast non-uniform deconvolution.

Non-Uniform Blur

The motion blur is globally non-uniform but locally uniform. We can thus restore individual, overlapping patches of y with Alg. 2.1. However, this potentially requires computing as many inverse filters as there are pixels in y, which would dramatically slow down our approach in practice. To skirt this issue, we follow [START_REF] Tae | Segmentation-free dynamic scene deblurring[END_REF] and [START_REF] Sun | Learning a convolutional neural network for non-uniform motion blur removal[END_REF], and assume that a wide range of non-uniform motion blurs, including those due to camera rotation, can be locally approximated by linear motions. We select a relatively small set of linear motions to represent a wide range of globally non-uniform blurs.

Following [START_REF] Sun | Learning a convolutional neural network for non-uniform motion blur removal[END_REF], we select the linear motions of magnitude l = 1, 3, ..., 35 pixels and orientations θ = 0, 6, . . . , 174 degrees. Overall, we consider 511 different filters (l = 1 is counted only once as it is the same filter for each possible value of θ). We compute offline an inverse kernel for each of those 511 filters.

During inference, a (continuous) linear motion parametrized by a couple (l, θ) in R + × [0, 180) is associated with each patch from y. We propose to use interpolation to switch from this representation to our discrete predefined filters while limiting quantization errors. For a patch p with predicted motion m = (l p , θ p ), we fetch from the 511 predefined linear motions the closest couples

m 1 = (l -, θ -), m 2 = (l -, θ+), m 3 = (l + , θ -) and m 4 = (l + , θ+) such that l -≤ l p ≤ l + and θ -≤ θ p ≤ θ + .
We then compute the Euclidean distances between m p and the m i and we make then sum to 1 by applying the softmax function S. The m i correspond to four kernels linear motions kernels. If the d i are the corresponding inverse filters, we have:

x = 4 i=1 w i (m p )d i p with w i (m p ) = S(||m p -m i || 2 2 ). ( 17
)
This method is easily adaptable to an entire image. That is, we can remove any linear blur parametrized by continuous coordinates with a finite set of linear motions in a non-uniform setting. Figure 2 illustrates this non-uniform deconvolution step.

Non-Uniform Motion Blur Estimation and Removal

In this section, we design two models. The first one is a CNN taking as input y and outputing k, an estimate of the locally linear non-uniform blur kernel k. The second one is a CNN formulation of the IRC algorithm to tackle non-blind deblurring when provided y and k or k, and outputing x, an estimate of the sharp image. Finally, we show how to combine both architectures to get an end-to-end learning framework that directly outputs x given only y.

Motion-Net for Non-Uniform Motion Estimation

We want to compute an estimate of the motion corresponding to y. Previous approaches select a small set of linear motions, as in the previous section, and assign to each pixel of y one of those motions. For example, Gong et al. [START_REF] Gong | From motion blur to motion flow: A deep learning solution for removing heterogeneous motion blur[END_REF] adapt a fully connected network (FCN) initially designed for semantic segmentation [START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF] to this classification problem. We take instead Deeplab [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF], a CNN-based approach that has been shown to be faster and more accurate for semantic segmentation than [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF], and adapt it to the regression problem of assigning a continuous linear motion to every pixel of y by replacing the final classification layer by a 2-channel (magnitude and direction) convolutional layer.

IRC-Net for Non-Uniform and Non-Blind Blur Removal

Figure 3 illustrates how we embed a few iterations of the ADMM algorithm within a CNN, dubbed IRC-Net. At each one of the N stages of the ADMM algorithm, we first proceed to the z i update by mapping them onto the convolution ("Conv") and shrinkage ("Shrink") layers in the red part. Second, we sequentially solve Eq. ( 5) by mapping it onto a first non-uniform convolution layer ("NU-Conv") applying to each patch of y the corresponding local k i kernels, a subtraction layer ("Sub"), a second non-uniform convolution layer ("NU-Conv") implementing the operations discussed in Section 2.2 and an addition layer ("Sum") in the blue branch. We repeat T times those four operations to execute Alg. 2.1. We finally update the scaled Lagrangian multipliers β in the green part.

The NU-Conv layer performs non-uniform convolution. The trainable parameters are filters initialized with the predefined inverse filters we compute ahead of time in the case of the second "NU-Conv" block of Fig. 3. Thus, we use the backpropagation algorithm to fine-tune the filters just like for a regular convolution layer. The Shrink layer performs the shrinkage operation involved in the z i updates. We turn the soft-shrinkage function into a layer with learnable parameters following [START_REF] Yan Yang | Deep admm-net for compressive sensing mri[END_REF] in order to fit more flexible shrinkage operations.

Embedding Blur Estimation and Removal in a Neural Architecture

We can tackle blind deblurring problems by concatenating Motion-Net and IRC-Net in a single pipeline and fine-tune them in an end-to-end framework. To connect both models while ensuring the gradient can flow from IRC-Net to Motion-Net, we use the interpolation technique introduced in Section 2.2. Let us consider a patch p of corresponding linear motion mp predicted by Motion-Net. If Motion-Net of parameters Θ M is denoted by f and IRC-Net of parameters Θ D , e.g., the precomputed inverse filters d i , is denoted by g, we have:

x = g(p, {k i } 4 i=1 , {w i } 4 i=1 ; Θ D ) with w i = S(||f (p ; Θ M ) -m i || 2 2 ). ( 18
)
This method is easily adaptable to an entire image and is illustrated in Fig. 4. Thus, we can update Θ D and Θ M without any supervision on k. The proposed trainable pipeline to address blind deblurring problems. First, we predict the local linear motions responsible for the blur (1). We then look for the reference motions on a discrete grid corresponding to the predicted motion to build the estimate of the kernel k and compute matching weights kept in memory for the averaging step (2). We then use IRC-Net for each of the inverse filters selected (3) and finally we average all the restored versions of the blurry image y to build the estimate x (4).

Experiments

In this section, we experimentally validate the proposed models for motion estimation, non-blind and finally blind deblurring on synthetic and real-world images.

Motion Estimation

Real-world non-uniform blur kernels synthesis: A way to get a large dataset with ground-truth kernels is to synthesize camera motions as proposed in [START_REF] Gong | From motion blur to motion flow: A deep learning solution for removing heterogeneous motion blur[END_REF] but real-world motions captured by cameras are not rotations and uniform translations. We create a dataset containing more realistic blurs with pseudo ground-truth kernels by averaging around 10 consecutive frames randomly selected from one of the GOPRO tracks provided by [START_REF] Nah | Deep multi-scale convolutional neural network for dynamic scene deblurring[END_REF]. That is, we get a realistic blurry image. The corresponding kernel is obtained by estimating the optical flow between each pair of consecutive frames using [START_REF] Ilg | Flownet 2.0: Evolution of optical flow estimation with deep networks[END_REF]. Then, we sum all the predicted flows to get an approximate linear motion of each pixel in the image which can be used as a target information to learn to predict realistic non-uniform locally linear kernels.

Training: We build a dataset made of 7,000 images taken from VOC 2012 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2012[END_REF] and synthetically blurred with camera rotations and translations. We add 5,000 images built with the method explained in the previous paragraph. Overall, we gather a pool of 12,000 images containing various types of blurs. We select 10,000 images from that pool to be the train set and 2,000 to be the validation set. The maximum magnitude of the linear motions is 35 pixels. Finally, we build a test set of 600 images: 300 images are corrupted with motions up to 21 pixels and 300 other images up to 35 pixels. We randomly flip and rotate by 90 degrees the samples and add a Gaussian noise of variance 2. The model is trained during 150 epochs with Adam optimizer and starting learning rate of 10 -4 , multiplied by 0.1 every 50 epochs. We use full images with batch size of 1 and replace batch normalization by instance normalization [START_REF] Ulyanov | Improved texture networks: Maximizing quality and diversity in feed-forward stylization and texture synthesis[END_REF] as we use only one image per forward pass during training. Table 2 and Fig. 5 show that our approach achieves slightly better results than the ones of FCN [START_REF] Gong | From motion blur to motion flow: A deep learning solution for removing heterogeneous motion blur[END_REF] with respect to the metric proposed by [START_REF] Sun | Learning a convolutional neural network for non-uniform motion blur removal[END_REF]. Motion-Net produces smoother results while being nearly 50 times faster.

Non-Blind Deblurring

Initialization: The number of stages of the network is set to 5 with 2 iterations for the inner network responsible for IRC. In the formulation of Eq. ( 1), we set l = 1 and we initialize k 1 and k 2 with vertical and horizontal gradient filters.

Training: We train IRC-Net using gradient descent and learning rate set to 10 -7 on a synthetic dataset made of 5,400 synthetically blurred patch pairs of size 121 × 121 with motions corresponding to the selected linear motions presented in Section 2.2 to update a single precomputed inverse filters with the exact corresponding motion. We do not use the pseudo ground-truth kernels used for training Motion-Net as predictions may be incorrect, leading to inexact ground-truth data and thus, wrong updates of the parameters of IRC-Net. At test time, we use continuous linear motions and take advantage of the interpolation technique explained in Section 2.2. We quantitatively evaluate our approach on a synthetic test set with 60 pairs of clean and blurry images from VOC 2012 with synthetic spatially-varying motion blur. The training loss is the l 2 distance. Table 3 shows that our approach, before fine-tuning, gives significantly better results than a widely used FFT-based non-uniform deconvolution method (NU-FFT) [START_REF] Michael Ohirsch | Fast removal of non-uniform camera shake[END_REF][START_REF] Xu | Unnatural L0 sparse representation for natural image deblurring[END_REF] and Gaussian mixture method (GMM) prior-based approach (GMM-Patch) but falls behind the conjugate gradient-based algorithm (NU-CG) with a gap of 0.23dB. When fine-tuned, it achieves slightly better results than NU-CG, i.e. +0.14dB, and is more than 300 times faster.

Blind Deblurring

We select the IRC-Net with two inner iterations and we combine it with the proposed Motion Net to build a blind deblurring approach following the method described in Paragraph 3.3. We fine-tune the pipeline on a dataset made of 3,000 synthetic images and 3,000 images from the dataset provided by [START_REF] Nah | Deep multi-scale convolutional neural network for dynamic scene deblurring[END_REF] with stochastic gradient descent with learning rate set to 10 -9 , momentum set to 0.9, and batch size set to 1. The training loss is the l 2 distance. Fine-tuning Motion-Net and IRC-Net together improves the deblurring results. We report in Table 4 comparison results for the datasets of [START_REF] Bahat | Non-uniform blind deblurring by reblurring[END_REF]. We are significantly above the classical baseline [START_REF] Sun | Learning a convolutional neural network for non-uniform motion blur removal[END_REF] in terms of accuracy and running time. In terms of PSNR, we also compete with recent approaches such as [START_REF] Nah | Deep multi-scale convolutional neural network for dynamic scene deblurring[END_REF][START_REF] Gong | From motion blur to motion flow: A deep learning solution for removing heterogeneous motion blur[END_REF][START_REF] Bahat | Non-uniform blind deblurring by reblurring[END_REF]. We are slightly above the CNN of [START_REF] Nah | Deep multi-scale convolutional neural network for dynamic scene deblurring[END_REF] by 0.12 dB on the moderate dataset and by 0.26 dB on the severe dataset while being 5 times faster. We are more than 400 times faster than [START_REF] Gong | From motion blur to motion flow: A deep learning solution for removing heterogeneous motion blur[END_REF] while achieving similar results on the moderate dataset and better results on the severe benchmark (+0.16 dB). We are behind [START_REF] Bahat | Non-uniform blind deblurring by reblurring[END_REF] by only 0.07 dB. We achieve poorer results in terms of SSIM than the best competitors on both benchmarks but not by far, i.e. -0.06 on the moderate dataset and -0.14 on the severe dataset in comparison with [START_REF] Bahat | Non-uniform blind deblurring by reblurring[END_REF]. Blur estimation and removal on real-world images are illustrated in Fig. 7. More examples are presented in the supplementary material. Table 5: Quantitative comparison for blind deconvolution methods on the dataset of [START_REF] Köhler | Recording and playback of camera shake: Benchmarking blind deconvolution with a real-world database[END_REF]. Mean runtime is for images of size 800 × 800 pixels.

Table 5 summarizes comparison results on the classical benchmark for blind image deblurring proposed by Köhler et al. [START_REF] Köhler | Recording and playback of camera shake: Benchmarking blind deconvolution with a real-world database[END_REF]. We achieve a PSNR score of 25.49 dB, which is better than similar approaches proposing to estimate and then remove blur such as [START_REF] Gong | From motion blur to motion flow: A deep learning solution for removing heterogeneous motion blur[END_REF] and [START_REF] Sun | Learning a convolutional neural network for non-uniform motion blur removal[END_REF]. They respectively score 24.92 dB and 25.22 dB. It is well behind the 26.33 dB claimed by [START_REF] Bahat | Non-uniform blind deblurring by reblurring[END_REF] or the 26.48 dB claimed by [START_REF] Nah | Deep multi-scale convolutional neural network for dynamic scene deblurring[END_REF]. This shows a limitation of our method based on approximating non-uniform blurs with local linear motions. Very complex blurs that cannot be approximated by linear motions, e.g., curve motions, require better models to be estimated and then removed in a two-steps fashion.

Conclusion

We have proposed an iterative deconvolution approach and its embedding in a fine-tuned CNN where each feature map corresponds to a step of an ADMM algorithm, demonstrating its effectiveness on non-uniform deblurring problems. This learning-based method relies on image processing arguments, leading to fewer parameters and less intensive computations than deep CNNs. To extend it to the blind setting, we have designed a new motion regressor and a technique to combine both architectures within a single learning framework that competes with recent approaches while being faster. For future work, we plan to adapt Motion-Net to more complex local kernels than linear motions and enhance IRC-Net with richer priors such as [START_REF] Michael Ohirscohirsch | Fast removal of non-uniform camera shake[END_REF] or [START_REF] Ulyanov | Deep image prior[END_REF].

Figure 1 :

 1 Figure 1: Examples of regularized deconvolution results. "Deconvreg" is Matlab's deconvolution method using Laplacian regularization.

Figure 3 :

 3 Figure 3: One stage of the ADMM algorithm with IRC for updating x. Concatenating N stages forms a trainable structure implementing the ADMM algorithm. In practice, N = 5 and T = 2 is enough the get good results. The gradient with respect to the loss can flow in the graph to update every trainable parameter like in a usual CNN.

Figure 4 :

 4 Figure 4: The proposed trainable pipeline to address blind deblurring problems. First, we predict the local linear

  (a) Ground-truth motion blur (b) [8], MSE = 23.83 (c) Ours, MSE = 8.59

Figure 5 :

 5 Figure 5: Example of motion field estimation for the severe dataset.

Figure 6 :

 6 Figure 6: Example of non-blind deblurring results. NU-CG achieves a PSNR score of 25.76 dB. Our approach achieves 25.56 dB and after fine-tuning reaches 25.75 dB.

Figure 7 :

 7 Figure 7: Examples of blind deblurring results. The two first rows present synthetically blurred images. The other rows show real-world images.

  Algorithm 2.1: Iterative residual compensation algorithm for updating x. data: zi, di, , Tmax, x0 (current estimate of x).

	result: x.
	initialization: t ← 0 while n i=0 ||r i t || 2 2 > and t < Tmax do
	1. for i = 0, . . . , n do r i t+1 ← zi -ki x ;
	2. xt+1 ← xt + n i=0 di r i t+1 ;
	3. t ← t + 1.
	return Estimated clean image xt+1.

Table 1

 1 FFT 25.95 24.99 26.01 22.44 27.24 26.80 24.58 23.20 25.16 1.3 FFT nopad 20.81 20.18 22.44 17.68 23.34 21.06 19.68 18.29 20.54 1.2 CG 25.93 25.52 25.99 24.02 27.11 26.61 24.96 24.56 25.59 60 IRC 25.91 25.33 25.99 23.74 27.23 26.84 25.37 24.73 25.65 (6, 2.6)

	gathers the evaluation results. It shows that our method competes with the traditional
	conjugate gradient descent method but is significantly faster. Indeed, over the 8 kinds of blur we
	consider, the proposed IRC algorithm achieves 4 times the best average PSNR score and 3 times,
	it is better than conjugate gradient descent, i.e. +0.23 dB for kernel 6, +0.41 dB for kernel 7 and
	+0.21 dB for kernel 8. Over the 160 images of the proposed benchmark, we achieve a better average
	PSNR score over CG (+0.06 dB) and the FFT-based method taking into account boundary effects

(+0.49 dB). We are a slower than the FFT-based method (1.3 seconds for FFT against 8.6 seconds for IRC) because we need first to estimate the inverse kernel of k (with Wiener filtering for example) and then we apply the proposed iterative scheme. However, we are 8 times faster than the most serious competitors in terms of accuracy. This validates the choice of Alg. 2.1 to address non-blind deconvolution in a penalized setting. Figure

1

illustrates this comparison.

Table 1 :

 1 Comparison of regularized deconvolution results. The numbers are average PSNRs over 160 test images. The computational time for IRC is split to the computation of all local deconvolution kernels (first number) and ADMM iterations with these kernels (second number).

Table 2 :

 2 Results for motion estimation over a test set made of 600 blurry images. Mean runtime is for RGB images of size 500 × 375 pixels.

Table 3 :

 3 Quantitative

comparison to other non-blind methods. Mean runtime is for RGB images of size 375 × 500 pixels.

Table 4 :

 4 Quantitative comparison for blind deblurring methods on the datasets of[START_REF] Bahat | Non-uniform blind deblurring by reblurring[END_REF]. The mean runtime is for images of size 375 × 500 pixels. Left column is for moderate blur, right one for severe.

Acknowledgments This work was supported in part by ERC grant VIDEOWORLD, the MSR-Inria joint lab and the Louis Vuitton ENS Chair on Artificial Intelligence.