Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> In this paper, we present a blind deconvolution algorithm based on the total variational (TV) minimization method proposed. The motivation for regularizing with the TV norm is that it is extremely effective for recovering edges of images as well as some blurring functions, e.g., motion blur and out-of-focus blur. An alternating minimization (AM)implicit iterative scheme is devised to recover the image and simultaneously identify the point spread function (psf). Numerical results indicate that the iterative scheme is quite robust, converges very fast (especially for discontinuous blur), and both the image and the psf can be recovered under the presence of high noise level. Finally, we remark that psf's without sharp edges, e.g., Gaussian blur, can also be identified through the TV approach. <s> BIB001 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> 1 Introduction.- 2 Probabilistic Inference in Signal Processing.- 2.1 Introduction.- 2.2 The likelihood function.- 2.2.1 Maximum likelihood.- 2.3 Bayesian data analysis.- 2.4 Prior probabilities.- 2.4.1 Flat priors.- 2.4.2 Smoothness priors.- 2.4.3 Convenience priors.- 2.5 The removal of nuisance parameters.- 2.6 Model selection using Bayesian evidence.- 2.6.1 Ockham's razor.- 2.7 The general linear model.- 2.8 Interpretations of the general linear model.- 2.8.1 Features.- 2.8.2 Orthogonalization.- 2.9 Example of marginalization.- 2.9.1 Results.- 2.10 Example of model selection.- 2.10.1 Closed form expression for evidence.- 2.10.2 Determining the order of a polynomial.- 2.10.3 Determining the order of an AR process.- 2.11 Concluding remarks.- 3 Numerical Bayesian Inference.- 3.1 The normal approximation.- 3.1.1 Effect of number of data on the likelihood function.- 3.1.2 Taylor approximation.- 3.1.3 Reparameterization.- 3.1.4 Jacobian of transformation.- 3.1.5 Normal approximation to evidence.- 3.1.6 Normal approximation to the marginal density.- 3.1.7 The delta method.- 3.2 Optimization.- 3.2.1 Local algorithms.- 3.2.2 Global algorithms.- 3.2.3 Concluding remarks.- 3.3 Integration.- 3.4 Numerical quadrature.- 3.4.1 Multiple integrals.- 3.5 Asymptotic approximations.- 3.5.1 The saddlepoint approximation and Edgeworth series.- 3.5.2 The Laplace approximation.- 3.5.3 Moments and expectations.- 3.5.4 Marginalization.- 3.6 The Monte Carlo method.- 3.7 The generation of random variates.- 3.7.1 Uniform variates.- 3.7.2 Non-uniform variates.- 3.7.3 Transformation of variables.- 3.7.4 The rejection method.- 3.7.5 Other methods.- 3.8 Evidence using importance sampling.- 3.8.1 Choice of sampling density.- 3.8.2 Orthogonalization using noise colouring.- 3.9 Marginal densities.- 3.9.1 Histograms.- 3.9.2 Jointly distributed variates.- 3.9.3 The dummy variable method.- 3.9.4 Marginalization using jointly distributed variates.- 3.10 Opportunities for variance reduction.- 3.10.1 Quasi-random sequences.- 3.10.2 Antithetic variates.- 3.10.3 Control variates.- 3.10.4 Stratified sampling.- 3.11 Summary.- 4 Markov Chain Monte Carlo Methods.- 4.1 Introduction.- 4.2 Background on Markov chains.- 4.3 The canonical distribution.- 4.3.1 Energy, temperature and probability.- 4.3.2 Random walks.- 4.3.3 Free energy and model selection.- 4.4 The Gibbs sampler.- 4.4.1 Description.- 4.4.2 Discussion.- 4.4.3 Convergence.- 4.5 The Metropolis-Hastings algorithm.- 4.5.1 The general algorithm.- 4.5.2 Convergence.- 4.5.3 Choosing the proposal density.- 4.5.4 Relationship between Gibbs and Metropolis.- 4.6 Dynamical sampling methods.- 4.6.1 Derivation.- 4.6.2 Hamiltonian dynamics.- 4.6.3 Stochastic transitions.- 4.6.4 Simulating the dynamics.- 4.6.5 Hybrid Monte Carlo.- 4.6.6 Convergence to canonical distribution.- 4.7 Implementation of simulated annealing.- 4.7.1 Annealing schedules.- 4.7.2 Annealing with Markov chains.- 4.8 Other issues.- 4.8.1 Assessing convergence of Markov chains.- 4.8.2 Determining the variance of estimates.- 4.9 Free energy estimation.- 4.9.1 Thermodynamic integration.- 4.9.2 Other methods.- 4.10 Summary.- 5 Retrospective Changepoint Detection.- 5.1 Introduction.- 5.2 The simple Bayesian step detector.- 5.2.1 Derivation of the step detector.- 5.2.2 Application of the step detector.- 5.3 The detection of changepoints using the general linear model.- 5.3.1 The general piecewise linear model.- 5.3.2 Simple step detector in generalized matrix form.- 5.3.3 Changepoint detection in AR models.- 5.3.4 Application of AR changepoint detector.- 5.4 Recursive Bayesian estimation.- 5.4.1 Update of position.- 5.4.2 Update given more data.- 5.5 Detection of multiple changepoints.- 5.6 Implementation details.- 5.6.1 Sampling changepoint space.- 5.6.2 Sampling linear parameter space.- 5.6.3 Sampling noise parameter space.- 5.7 Multiple changepoint results.- 5.7.1 Synthetic step data.- 5.7.2 Well log data.- 5.8 Concluding Remarks.- 6 Restoration of Missing Samples in Digital Audio Signals.- 6.1 Introduction.- 6.2 Model formulation.- 6.2.1 The likelihood and the excitation energy.- 6.2.2 Maximum likelihood.- 6.3 The EM algorithm.- 6.3.1 Expectation.- 6.3.2 Maximization.- 6.4 Gibbs sampling.- 6.4.1 Description.- 6.4.2 Derivation of conditional densities.- 6.4.3 Conditional density for the missing data.- 6.4.4 Conditional density for the autoregressive parameters.- 6.4.5 Conditional density for the standard deviation.- 6.5 Implementation issues.- 6.5.1 Estimating AR parameters.- 6.5.2 Implementing the ML algorithm.- 6.5.3 Implementing the EM algorithm.- 6.5.4 Implementation of Gibbs sampler.- 6.6 Relationship between the three restoration methods.- 6.6.1 ML vs Gibbs.- 6.6.2 Gibbs vs EM.- 6.6.3 EM vs ML.- 6.7 Simulations.- 6.7.1 Autoregressive model with poles near unit circle.- 6.7.2 Autoregressive model with poles near origin.- 6.7.3 Sine wave.- 6.7.4 Evolution of sample interpolants.- 6.7.5 Hairy sine wave.- 6.7.6 Real data: Tuba.- 6.7.7 Real data: Sinead O'Connor.- 6.8 Discussion.- 6.8.1 The temperature of an interpolant.- 6.8.2 Data augmentation.- 6.9 Concluding remarks.- 6.9.1 Typical interpolants.- 6.9.2 Computation.- 6.9.3 Modelling issues.- 7 Integration in Bayesian Data Analysis.- 7.1 Polynomial data.- 7.1.1 Polynomial data.- 7.1.2 Sampling the joint density.- 7.1.3 Approximate evidence.- 7.1.4 Approximate marginal densities.- 7.1.5 Conclusion.- 7.2 Decay problem.- 7.2.1 The Lanczos problem.- 7.2.2 Biomedical data.- 7.2.3 Concluding remarks.- 7.3 General model selection.- 7.3.1 Model selection in an impulsive noise environment.- 7.3.2 Model selection in a Gaussian noise environment.- 7.4 Summary.- 8 Conclusion.- 8.1 A review of the work.- 8.2 Further work.- A The General Linear Model.- A.1 Integrating out model amplitudes.- A.1.1 Least squares.- A.1.2 Orthogonalization.- A.2 Integrating out the standard deviation.- A.3 Marginal density for a linear coefficient.- A.4 Marginal density for standard deviation.- A.5 Conditional density for a linear coefficient.- A.6 Conditional density for standard deviation.- B Sampling from a Multivariate Gaussian Density.- C Hybrid Monte Carlo Derivations.- C.1 Full Gaussian likelihood.- C.2 Student-t distribution.- C.3 Remark.- D EM Algorithm Derivations.- D.l Expectation.- D.2 Maximization.- E Issues in Sampling Based Approaches to Integration.- E.1 Marginalizing using the conditional density.- E.2 Approximating the conditional density.- E.3 Gibbs sampling from the joint density.- E.4 Reverse importance sampling.- F Detailed Balance.- F.1 Detailed balance in the Gibbs sampler.- F.2 Detailed balance in the Metropolis Hastings algorithm..- F.3 Detailed balance in the Hybrid Monte Carlo algorithm..- F.4 Remarks.- References. <s> BIB002 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> In this paper, an introduction to Bayesian methods in signal processing will be given. The paper starts by considering the important issues of model selection and parameter estimation. The important class of signal models, known as the General Linear Model, is introduced and the concept of marginal estimation of certain model parameter is developed. The techniques are illustrated for the problem of estimating sinusoidal frequency components in white Gaussian noise and for the general changepoint problem. Numerical integration methods are introduced based on Markov chain Monte Carlo techniques and the Gibbs sampler in particular and applications to audio restoration are presented. <s> BIB003 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> This paper addresses the general problem of estimating parameters in nuclear spectroscopy. We present a unified Bayesian formulation to tackle the various aspects of this problem. This includes deconvolution and modelling of both the peaks and background. The peaks are modelled with Gaussian or Lorentzian type functions and the background with cubic B-splines. The number of peaks and spline knots are treated as unknowns and as such are also estimated together with the model parameters. The Bayesian model allows us to define a posterior probability on the parameter space upon which all subsequent Bayesian inference is based. Direct evaluation of this distribution or its derived features such as the conditional expectation is, unfortunately, not possible on account of the need to evaluate high-dimension integrals. As such we resort to a stochastic numerical Bayesian technique, the reversible-jump Markov-chain Monte Carlo(RJMCMC) method. <s> BIB004 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> Camera shake during exposure leads to objectionable image blur and ruins many photographs. Conventional blind deconvolution methods typically assume frequency-domain constraints on images, or overly simplified parametric forms for the motion path during camera shake. Real camera motions can follow convoluted paths, and a spatial domain prior can better maintain visually salient image characteristics. We introduce a method to remove the effects of camera shake from seriously blurred images. The method assumes a uniform camera blur over the image and negligible in-plane camera rotation. In order to estimate the blur from the camera shake, the user must specify an image region without saturation effects. We show results for a variety of digital photographs taken from personal photo collections. <s> BIB005 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> In this paper we propose a novel blind image deconvolution method developed within the Bayesian framework. A variant of the non-convex l p -norm prior with 0 < p < 1 is used as the image prior and a total variation (TV) based prior is utilized as the blur prior. The proposed method is derived by utilizing bounds for both the image and blur priors using the majorization-minimization principle. Maximum a posteriori Bayesian inference is performed and as a result, the unknown image, blur and model parameters are simultaneously estimated. We also show that as a special case, the developed method provides very competitive non-blind image restoration results when the blurring function is assumed to be known. Experimental results are presented to demonstrate the advantage of the proposed method compared to existing ones. <s> BIB006 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> In blind deconvolution one aims to estimate from an input blurred image y a sharp image x and an unknown blur kernel k. Recent research shows that a key to success is to consider the overall shape of the posterior distribution p(x, k\y) and not only its mode. This leads to a distinction between MAP x, k strategies which estimate the mode pair x, k and often lead to undesired results, and MAP k strategies which select the best k while marginalizing over all possible x images. The MAP k principle is significantly more robust than the MAP x, k one, yet, it involves a challenging marginalization over latent images. As a result, MAP k techniques are considered complicated, and have not been widely exploited. This paper derives a simple approximated MAP k algorithm which involves only a modest modification of common MAP x, k algorithms. We show that MAP k can, in fact, be optimized easily, with no additional computational complexity. <s> BIB007 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> Blind deconvolution is the recovery of a sharp version of a blurred image when the blur kernel is unknown. Recent algorithms have afforded dramatic progress, yet many aspects of the problem remain challenging and hard to understand. The goal of this paper is to analyze and evaluate recent blind deconvolution algorithms both theoretically and experimentally. We explain the previously reported failure of the naive MAP approach by demonstrating that it mostly favors no-blur explanations. We show that, using reasonable image priors, a naive simulations MAP estimation of both latent image and blur kernel is guaranteed to fail even with infinitely large images sampled from the prior. On the other hand, we show that since the kernel size is often smaller than the image size, a MAP estimation of the kernel alone is well constrained and is guaranteed to succeed to recover the true blur. The plethora of recent deconvolution techniques makes an experimental evaluation on ground-truth data important. As a first step toward this experimental evaluation, we have collected blur data with ground truth and compared recent algorithms under equal settings. Additionally, our data demonstrate that the shift-invariant blur assumption made by most algorithms is often violated. <s> BIB008 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> We present a general method for blind image deconvolution using Bayesian inference with super-Gaussian sparse image priors. We consider a large family of priors suitable for modeling natural images, and develop the general procedure for estimating the unknown image and the blur. Our formulation includes a number of existing modeling and inference methods as special cases while providing additional flexibility in image modeling and algorithm design. We also present an analysis of the proposed inference compared to other methods and discuss its advantages. Theoretical and experimental results demonstrate that the proposed formulation is very effective, efficient, and flexible. <s> BIB009 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> Typical blur from camera shake often deviates from the standard uniform convolutional assumption, in part because of problematic rotations which create greater blurring away from some unknown center point. Consequently, successful blind deconvolution for removing shake artifacts requires the estimation of a spatially-varying or non-uniform blur operator. Using ideas from Bayesian inference and convex analysis, this paper derives a simple non-uniform blind deblurring algorithm with a spatially-adaptive image penalty. Through an implicit normalization process, this penalty automatically adjust its shape based on the estimated degree of local blur and image structure such that regions with large blur or few prominent edges are discounted. Remaining regions with modest blur and revealing edges therefore dominate on average without explicitly incorporating structure-selection heuristics. The algorithm can be implemented using an optimization strategy that is virtually tuning-parameter free and simpler than existing methods, and likely can be applied in other settings such as dictionary learning. Detailed theoretical analysis and empirical comparisons on real images serve as validation. <s> BIB010 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> The aim of removing camera shake is to estimate a sharp version x from a shaken image yi¾?when the blur kerneli¾?k is unknown. Recent research on this topic evolved through two paradigms called MAPk and MAPx,k. MAPk only solves for k by marginalizing the image prior, while MAPx,k recovers both x and k by selecting the mode of the posterior distribution. This paper first systematically analyses the latent limitations of these two estimators through Bayesian analysis. We explain the reason why it is so difficult for image statistics to solve the previously reported MAPx,k failure. Then we show that the leading MAPx,k methods, which depend on efficient prediction of large step edges, are not robust to natural images due to the diversity of edges. MAPk, although much more robust to diverse edges, is constrained by two factors: the prior variation over different images, and the ratio between image size and kernel size. To overcome these limitations, we introduce an inter-scale prior prediction scheme and a principled mechanism for integrating the sharpening filter into MAPk. Both qualitative results and extensive quantitative comparisons demonstrate that our algorithm outperforms state-of-the-art methods. <s> BIB011 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> In this paper we study the problem of blind deconvolution. Our analysis is based on the algorithm of Chan and Wong [2] which popularized the use of sparse gradient priors via total variation. We use this algorithm because many methods in the literature are essentially adaptations of this framework. Such algorithm is an iterative alternating energy minimization where at each step either the sharp image or the blur function are reconstructed. Recent work of Levin et al. [14] showed that any algorithm that tries to minimize that same energy would fail, as the desired solution has a higher energy than the no-blur solution, where the sharp image is the blurry input and the blur is a Dirac delta. However, experimentally one can observe that Chan and Wong's algorithm converges to the desired solution even when initialized with the no-blur one. We provide both analysis and experiments to resolve this paradoxical conundrum. We find that both claims are right. The key to understanding how this is possible lies in the details of Chan and Wong's implementation and in how seemingly harmless choices result in dramatic effects. Our analysis reveals that the delayed scaling (normalization) in the iterative step of the blur kernel is fundamental to the convergence of the algorithm. This then results in a procedure that eludes the no-blur solution, despite it being a global minimum of the original energy. We introduce an adaptation of this algorithm and show that, in spite of its extreme simplicity, it is very robust and achieves a performance comparable to the state of the art. <s> BIB012 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> Super Gaussian (SG) distributions have proven to be very powerful prior models to induce sparsity in Bayesian Blind Deconvolution (BD) problems. Their conjugate based representations make them specially attractive when Variational Bayes (VB) inference is used since their variational parameters can be calculated in closed form with the sole knowledge of the energy function of the prior model. In this work we show how the introduction in the SG distribution of a global strength (not necessary scale) parameter can be used to improve the quality of the obtained restorations as well as to introduce additional information on the global weight of the prior. A model to estimate the new unknown parameter within the Bayesian framework is provided. Experimental results, on both synthetic and real images, demonstrate the effectiveness of the proposed approach. <s> BIB013 </s> Variational Bayesian Blind Image Deconvolution: A review <s> III. BAYESIAN INFERENCE <s> In this paper we present an introduction to Variational Bayesian (VB) methods in the context of probabilistic graphical models, and discuss their application in multimedia related problems. VB is a family of deterministic probability distribution approximation procedures that offer distinct advantages over alternative approaches based on stochastic sampling and those providing only point estimates. VB inference is flexible to be applied in different practical problems, yet is broad enough to subsume as its special cases several alternative inference approaches including Maximum A Posteriori (MAP) and the Expectation-Maximization (EM) algorithm. In this paper we also show the connections between VB and other posterior approximation methods such as the marginalization-based Loopy Belief Propagation (LBP) and the Expectation Propagation (EP) algorithms. Specifically, both VB and EP are variational methods that minimize functionals based on the Kullback-Leibler (KL) divergence. LBP, traditionally developed using graphical models, can also be viewed as a VB inference procedure. We present several multimedia related applications illustrating the use and effectiveness of the VB algorithms discussed herein. We hope that by reading this tutorial the readers will obtain a general understanding of Bayesian methods and establish connections among popular algorithms used in practice. <s> BIB014
Once the observation and prior models have been described, in other words, once the elements of the joint probability model in (3) have been specified, the goal now becomes the drawing of inference of the unknown variables Θ = {z, Ω} given the observations. In the Bayesian framework Θ is inferred calculating (or approximating) the posterior distribution p(Θ|y), expressed using the Bayes' rule as Unfortunately, since the integral p(y) = p(Θ, y)dΘ is not tractable, the above posterior cannot be analytically calculated. Different estimation methods have been proposed to address this problem in the BID context and we will now review them. Probably the most widely used method in the literature is Maximum a Posteriori (MAP). Since p(Θ|y) ∝ p(Θ, y) the maximum of the posterior distribution can be obtained by maximizing the joint distribution p(Θ, y) with respect to Θ. However, as pointed out in the landmark papers by Levin et al. BIB007 , BIB008 , MAP is not a suitable estimation procedure in BID problems, because the associated cost function favors flat images for many sparse priors and leads to a delta blur estimate. To avoid the delta blur solution, Perrone and Favaro BIB012 show that a delayed normalization BIB001 are estimated by maximizing the evidence BIB003 . The restored image is finally calculated by maximizing the joint distribution, using the estimate values of h and Ω through the above integration on the image. Variational Bayesian inference has been widely used in BID (see BIB007 - BIB005 , BIB006 , BIB013 , BIB009 , BIB010 , BIB011 ). VB generalizes MAP and MAP h (see BIB014 for a proof) providing approaches for estimation of the posterior distributions of x, h and Ω. Together with the well established use of VB inference in BID, Markov Chain Monte Carlo (MCMC) methods are also gaining popularity. MCMC is the most general method used to approximate a posterior distribution, see BIB002 [44] BIB004 for details. The model in Eq. (3) is used to generate thousands of samples of p(z, Ω|y), which are used to infer the posterior distribution. In theory, sampling methods can find the exact form of the posterior distribution, but in practice they are computationally intensive (especially for multidimensional signals such as images) and their convergence is hard to establish. In computationally cost terms, VB is much more efficient than MCMC, and more expensive than MAP or MAP h . The features of each method are summarized in Table I . We now describe the application of VB and MCMC to BID.