Keywords
|
| Image deconvolution, alternating direction method of multipliers (ADMM), boundary conditions, periodic deconvolution, inpainting, frames. |
INTRODUCTION
|
| Deconvolution is an inverse problem where the observed image is modeled as resulting from the convolution with a blurring filter, possibly followed by noise, and the goal is to estimate both the underlying image and the blurring filter. In deconvolution, the pixels located near the boundary of the observed image depend on pixels (of the unknown image) located outside of its domain. The typical way to formalize this issue is to adopt a so-called boundary condition (BC). |
| • The periodic BC refers to the image repeats in all directions.Its matrix representation can be implemented via the FFT. |
| • The zero BC assumes a black boundary,so that pixels outside the barders of the image have zero value, thus the matrix representing the convolution is block-Toeplitz, with Toeplitz blocks. |
| • Inreflexiveand anti-reflexive BCs, the pixels outside the image domain are a morror image of those near the boundary, using even or odd symmetry, respectively. |
| For the sake of simplicity and computational convenience, most fast deconvolution algorithms assume periodic BC, which has the advantage of allowingconvolutions to be efficiently carried out using the FFT. However, as illustrated in Fig. 1, these BC are notaccurate and are quite unnatural models of most imaging systems. Deconvolution algorithms that ignore this mismatch and wrongly assume periodic BCleadtothewellknownboundaryartifacts. Abetter assumptionaboutthe image boundaries is simply they are unobserved/unknown,which models well a canonical imaging system where an image sensor captures the cental part of the image projected by the lens.The assumptions(unnatural) of periodic boundary conditions as illustrated in Fig 1. |
| In quadratic regularization, image deconvolution with periodic BC corresponds to a linear system,wherethe corresponding matrix can be efficiently inverted in the DFTdomain using the FFT. |
| The technique to deconvolution under frame-based analysisnon-smooth regularization; that work proposes an algorithmbased on variable splitting and quadratic penalization, using the method to solve the linear system at each iteration.That method is related to, but it is not ADMM, thus has noguarantees of converge to a minimizer of the original objective function. Although mentions the possibility of using the method within ADMM, that option was not explored.The image deconvolution under frame based analysis non-smooth regularization using ADMM inherit all the desirable properties of previous ADMM-based deconvolution methods: all the update equations (includingthe matrix inversion) can be computed efficiently without using inner iterations; convergence is formally guaranteed. |
ADMM
|
| The application of ADMM to our particular problem involves solving a linear system with the size of the unknown image or with the size of its representation. Although this seems like an unsurmountable obstacle, we show that it is not the case. In many problems, such as (circular) deconvolution, reproduction of missing samples, or reconstruction from partial Fourier observations, this system can be solved very quickly in closed form (with O(n) or O(n log n) cost). For problems of the form (1), we show how exploiting the fact that W is a tight Parseval frame, this system can still be solved efficiently (typically with O(n log n) cost. |
| We report results on a set of benchmark problems, including image deconvolution, recovery of missing pixels, and reconstruction from partial Fourier transform, using both frame-based regularization. In all the experiments, the resulting algorithm is consistently and considerably faster than the previous state of the art methods FISTA, TwIST, and SpaRSA. |
| Consider a generalization of an unconstrained optimization problem |
 (1) |
Where  are arbitary matrices, and  are convex functions.The instance of ADMM proposed in to so1lve(1) is presented in Algorithm 1, where  denotes the j-th block of ζ in the following partition |
 |
| and a similar notation is used for uk and dk. |
| Lines 4 and 6 of this algorithm are the main steps and those that can pose computational challenges. These steps, however, wereshown to have fast closed-form solutions in several cases of interest. In particular, the matrix inversion in line 4 cansometimes (e.g., in periodic deconvolution problems) be computedcheaply, by exploiting the matrix inversion lemma, the FFT and otherfast transforms (see [1, 13]), while line 6 corresponds to a so-calledMoreau proximity operator (MPO), defined as |
 (2) |
| for several choices of f, proxf has a simple closed form. |
 |
Under the condition that (1) has a solution, Algorithm 1 inherits the convergence guarantees of ADMM given in [11]. For our formulation, sufficient conditions for Algorithm 1 to converge to a solution of 1 are:  ll functions gi are proper, closed, and convex; the matrix  has full column rank (where()* denotes matrix/vector conjugate transpose,and  |
PROPOSED APPROACH
|
A. Image deconvolution with periodic BC:
|
| This section reviews the ADMM-based approach to image deconvolution with periodic BC, using the frame-based formulations, the standard regularizers for this class of imaging inverse problems. |
We begin by considering the usual observation model used in image deconvolution with periodic BC: y = Ax+ w, where  are vectors containing all pixels (lexicographically ordered) of the original and the observed images, respectively, w denotes white Gaussian noise, and  is the matrix representing the (periodic) convolution with some filter. In the frame-based analysis approach, the estimated image,  is obtained as |
 (3) |
Where  is the analysis operator of some frame (e.g., a redundant wavelet frame or a curvelet frame),Ø is a regularizer encouraging the vector of frame analysis coefficients to be sparse, and λ > 0is the regularization parameter. A typical choice for Ø, herein adopted, is |
 |
| Problem (5) can be written in the form (3), with J = 2 and |
 (4) |
 (5) |
 (6) |
 (7) |
| The operators of g1and g2, simple expressions of key components of Algorithm 1 (line 6), |
 (8) |
 (9) |
| where “soft” denotes the well-known soft-threshold function |
 (10) |
where the sign, max, and absolute value functions are componentwise, and  denotes the component-wise product. Line 4 of Algorithm 1 (the other key component) has the form |
 (11) |
| Assuming that P corresponds to a Parseval1 frame (i.e., P*P =I, although possibly PP*≠I the matrix inverse in (11) is simplycomputed in the DFT domain |
 (12) |
| in which U and U* are the unitary matrices representing the DFT and its inverse, and Λ is the diagonal matrix of the DFT coefficients of the convolution kernel (i.e., A = U* ΛU). |
The inversion in (12) has O(n log n) cost, since matrix  is diagonal and the products by U and U* can be computed using the FFT. The leading cost of each application of (11) (line 4 of Algorithm 1) is thus either the O(n log n) cost associated with (12) or the cost of the products by P*. For most tight frames used in image restoration, this product has fast O(n log n) algorithms. |
| We conclude that, under periodic BC and for a large class of frames, each iteration of Algorithm 1 for solving (3) has O(n log n) cost. Finally, this instance of ADMM has convergence guarantees, since: (1)g2 is coercive, so is the objective function in (3), thus its set of minimizers is not empty, (2)g1 and g 2 are proper, closed, convex functions; (3) matrixH(2) = I obviously has full column rank, which implies that G = [A*I*]also has full column rank. |
B. Image deconvolution with unknown boundaries:
|
| To handle images with unknown boundaries, we model the boundary pixels as unobserved, which is achieved |
| y = MAx + n, (13) |
| whereM ∈ {0,1}m×m (with m<n) is a masking matrix, i.e., a matrix whose rows are a subset of the rows of an identity matrix. The role of M is to observe only the subset of the image domain in which the elements of Axdo not depend on the boundary pixels; consequently, the BC assumed for the convolution represented by A is irrelevant, and we may adopt periodic BCs, for computational convenience. |
Assuming that A models the convolution with a blurring filter with a limited support of size  and that x and Axrepresent square images of dimensions √n ×√n, then matrix M ∈ Rmxn with  , represents the removal of a band of width l of the outermost pixels of the full convolved image Ax. Problem be seen as hybrid of deconvolution and inpainting, where the missing pixels constitute the unknown boundary. If M = I, model reduces to a standard periodic deconvolution problem. Conversely, if A=I, problem becomes a pure inpainting problem. Moreover, the formulation problem can be used to model problems where not only the boundary, but also other pixels, are missing, as in standard image inpainting. |
| Under model (13), the frame-based analysis formulation(1) changes to |
 |
| At this point, one could be tempted to map (14) into (1) using (4), (5, and (7), and simply change (6) into |
 (15) |
| The problem with this choice is that the matrix to be inverted in line 4 of Algorithm 1 would become |
 (16) |
| which, unlike (13), is not easily invertible due to the presence of M. To side step this difficulty, we propose to decouple the action of the(DFT diagonal) operator A from the spatial operator M, by keeping (7), (8), and (9), and replacing (4) by |
 (17) |
| With this choice, line 4 of Algorithm 1 is still given by (13) (with its efficient FFT-based implementation (14)), while mask peratorM only affects the Moreau proximity operator of the new g1, |
 (18) |
 (19) |
| Notice that, due to the special structure of M, matrix M*M is diagonal, thus the inversion in (18) has O(n) cost, the same being true about the product M*y , which corresponds to extending the observed image y to the size of x, by creating a boundary of zeros around it. Of course, both (M*M + μ1 I)−1 and M* can be precomputed and then used throughout the algorithm, as long as μ1 is kept constant. Similarly to what was shown for the periodic BC case, the proposed ADMM approach for deblurring with unknown boundaries has a leading cost of O(n log n) per iteration. Considering the similarities of our approach with the one of Section 3.1, it is sufficient to confirm that the new g1in (16) is proper, closed, and convex (which is obviously the case), to guarantee the convergence of the proposed ADMM algorithm. |
EXPERIMENTS
|
In the experiments herein reported, we use the benchmark Lena image(of size 256 × 256), with 2 different blurs (outof- focus and uniform), all of size 19 × 19(i.e., 2l + 1 × (2l + 1), with I= 9), at two different BSNRs (blurred signal to noise ratio): 40dB, 50dB, and 60dB. The reason why we concentrate on large blurs is that the effect of the boundary conditions is very evident in this case.On each degraded image, the algorithm proposed in Section3.2 was run, as well as the periodic version (Section 3.1), withand without pre-processing the observed image with the âÃâ¬Ãâ¢edgetapperâÃâ¬Ãâ MATLAB function. The algorithms are stopped when  and λ was adjusted to yield thehighest SNR of the reconstructed image. |
| The simulation studies involve the output of the proposed method based on the ADMM is shown in the fig3. It includes the original image and the degraded image after performing the ADMM algorithm it will produce the estimated image. The cost function will indicate the number of iterations to obtain the estimated image from the degraded image. The ISNR values of the estimated image is tabulated in the table.2 based on frame analysis is used in ADMM. |
CONCLUSION
|
| Presented a new strategy to extend recent fast image deconvolution algorithms, based on the alternating direction method of multipliers (ADMM), to problems with unknown boundary conditions. Considered frame based analysis formulation, and gave the convergence guarantees for the algorithms proposed. Experiments show the results in terms of restoration quality. Ongoing and future work includes theinstead of adopting a standard BC or a boundary smoothing scheme, a more realistic model of actual imaging systems treats the external boundary pixels as unknown; i.e., the problem is seen as one of simultaneous deconvolution and inpainting, where the unobserved boundary pixels are estimated together with the deconvolved image. |
| |
Tables at a glance
|
 |
|
| Table 1 |
Table 2 |
|
| |
Figures at a glance
|
 |
 |
 |
| Figure 1 |
Figure 2 |
Figure 3 |
|
| |
References
|
- M. Afonso, J. Bioucas-Dias, and M. Figueiredo, “Fast image recovery using variable splitting and constrained optimization,” IEEE Trans. Image Proc., vol. 19, pp. 2345–2356, 2010.
- An augmented Lagrangian approach to the constrainedoptimization formulation of imaging inverse problems,” IEEETrans. Image Proc., vol. 20, pp. 681–695, 2011.
- A. Beck and M. Teboulle, “A fast iterative shrinkagethresholding algorithm for linear inverse problems,” SIAMJour.Imaging Sciences, vol. 2, pp. 183–202, 2009.
- J. Bioucas-Dias and M. Figueiredo, “A new TwIST: two-stepiterative shrinkage/thresholding algorithms for image restoration,” IEEE Trans.
- Image Proc., vol. 16, pp. 2992–3004, 2007.
- S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternatingdirection method of multipliers,” Foundations and Trends inMachine Learning, vol. 3, pp. 1–122, 2011.
- T. Chan, A. Yip, and F. Park, “Simultaneous total variation image inpainting and blind deconvolution,” International Journalof Imaging Systems and Technology, vol. 15, pp. 92–102, 2005.
- P. Combettes and J.-C.Pesquet, “Proximal Splitting Methodsin Signal Processing”, in Fixed-Point Algorithms for InverseProblems in Science and Engineering (H. Bauschke et al, Editors), pp. 185–212, Springer, 2011.
- P. Combettes and V. Wajs, “Signal recovery by proximalforward-backward splitting,” SIAM Journal on MultiscaleModeling& Simulation, vol. 4, 2005.
- I. Daubechies, M. Defrise, C. De Mol, “An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,” Comm. Pure and App. Math., vol. 57, pp. 1413–1457,2004.
- M. Donatelli, C. Estatico, A. Martinelli, and S. SerraCapizzano, “Improved image deblurring with anti-reflectiveboundary conditions and reblurring,” Inverse Problems,vol. 22, pp. 2035–2053, 2006.
|
Menu