Bayesian Restoration of Digital Images Employing Markov Chain Monte Carlo a Review
---
paper_title: Statistical physics of spin glasses and information processing : an introduction

paper_content:

1. Mean-field theory of phase transitions 2. Mean-field theory of spin glasses 3. Replica symmetry breaking 4. Gauge theory of spin glasses 5. Error-correcting codes 6. Image restoration 7. Associative memory 8. Learning in perceptron 9. Optimization problems A. Eigenvalues of the Hessian B. Parisi equation C. Channel coding theorem D. Distribution and free energy of K-Sat References Index
---
paper_title: Statistical mechanics of image restoration

paper_content:

We develop the statistical mechanics formulation of the image restoration problem, pioneered by Geman and Geman (1984). Using Bayesian methods we establish the posterior probability distribution for restored images, for given data (corrupted image) and prior (assumptions about source and corruption process). In the simplest cases, studied here, the posterior is controlled by a cost function analagous to the configurational energy of an Ising model with local fields whose sense is defined by the data. Through a combination of Monte Carlo simulation and mean-field theory we address three key issues. First, we explore the sensitivity of the posterior distribution to the choice of prior parameters: we find phase transitions separating regions in which the distribution is effective (data-dominated) from regions in which it is ineffective (prior-dominated). Second, we examine the question of how best to use the posterior distribution to prescribe a single "optimal" restored image: we argue that the mean of the posterior is, in general, to be preferred over the mode, both in principle and in practice. Finally, borrowing from Monte Carlo techniques for free-energy calculations, we address the question of prior parameter estimation within the "evidence" framework of Gull (1989) and MacKay (1992): our results suggest that parameters identified by this framework provide effective priors, leading to optimal restoration, only to the extent that the forms of the priors are well matched to the processes they claim to represent.
---
paper_title: Statistical Mechanics of Image Restoration and Error Correcting Codes: Phys

paper_content:

We develop a statistical-mechanical formulation for image restoration and error-correcting codes. These problems are shown to be equivalent to the Ising spin glass with ferromagnetic bias under random external fields. We prove that the quality of restoration/decoding is maximized at a specific set of parameter values determined by the source and channel properties. For image restoration in a mean-field system a line of optimal performance is shown to exist in the parameter space. These results are illustrated by solving exactly the infinite-range model. The solutions enable us to determine how precisely one should estimate unknown parameters. Monte Carlo simulations are carried out to see how far the conclusions from the infinite-range model are applicable to the more realistic two-dimensional case in image restoration.
---
paper_title: Statistical-mechanical approach to image processing

paper_content:

The basic frameworks and techniques of the Bayesian approach to image restoration are reviewed from the statistical-mechanical point of view. First, a few basic notions in digital image processing are explained to convince the reader that statistical mechanics has a close formal similarity to this problem. Second, the basic formulation of the statistical estimation from the observed degraded image by using the Bayes formula is demonstrated. The relationship between Bayesian statistics and statistical mechanics is also listed. Particularly, it is explained that some correlation inequalities on the Nishimori line of the random spin model also play an important role in Bayesian image restoration. Third, the framework of Bayesian image restoration for binary images by means of the Ising model is reviewed. Some practical algorithms for binary image restoration are given by employing the mean-field and the Bethe approximations. Finally, Bayesian image restoration for a grey-level image using the Gaussian model is reviewed, and the Gaussian model is extended to a more practical probabilistic model by introducing the line state to treat the effects of edges. The line state is also extended to quantized values.
---
paper_title: Statistical-mechanical approach to image processing

paper_content:

The basic frameworks and techniques of the Bayesian approach to image restoration are reviewed from the statistical-mechanical point of view. First, a few basic notions in digital image processing are explained to convince the reader that statistical mechanics has a close formal similarity to this problem. Second, the basic formulation of the statistical estimation from the observed degraded image by using the Bayes formula is demonstrated. The relationship between Bayesian statistics and statistical mechanics is also listed. Particularly, it is explained that some correlation inequalities on the Nishimori line of the random spin model also play an important role in Bayesian image restoration. Third, the framework of Bayesian image restoration for binary images by means of the Ising model is reviewed. Some practical algorithms for binary image restoration are given by employing the mean-field and the Bethe approximations. Finally, Bayesian image restoration for a grey-level image using the Gaussian model is reviewed, and the Gaussian model is extended to a more practical probabilistic model by introducing the line state to treat the effects of edges. The line state is also extended to quantized values.
---
paper_title: Statistical Mechanics of Image Restoration and Error Correcting Codes: Phys

paper_content:

We develop a statistical-mechanical formulation for image restoration and error-correcting codes. These problems are shown to be equivalent to the Ising spin glass with ferromagnetic bias under random external fields. We prove that the quality of restoration/decoding is maximized at a specific set of parameter values determined by the source and channel properties. For image restoration in a mean-field system a line of optimal performance is shown to exist in the parameter space. These results are illustrated by solving exactly the infinite-range model. The solutions enable us to determine how precisely one should estimate unknown parameters. Monte Carlo simulations are carried out to see how far the conclusions from the infinite-range model are applicable to the more realistic two-dimensional case in image restoration.
---
paper_title: Statistical mechanics of image restoration

paper_content:

We develop the statistical mechanics formulation of the image restoration problem, pioneered by Geman and Geman (1984). Using Bayesian methods we establish the posterior probability distribution for restored images, for given data (corrupted image) and prior (assumptions about source and corruption process). In the simplest cases, studied here, the posterior is controlled by a cost function analagous to the configurational energy of an Ising model with local fields whose sense is defined by the data. Through a combination of Monte Carlo simulation and mean-field theory we address three key issues. First, we explore the sensitivity of the posterior distribution to the choice of prior parameters: we find phase transitions separating regions in which the distribution is effective (data-dominated) from regions in which it is ineffective (prior-dominated). Second, we examine the question of how best to use the posterior distribution to prescribe a single "optimal" restored image: we argue that the mean of the posterior is, in general, to be preferred over the mode, both in principle and in practice. Finally, borrowing from Monte Carlo techniques for free-energy calculations, we address the question of prior parameter estimation within the "evidence" framework of Gull (1989) and MacKay (1992): our results suggest that parameters identified by this framework provide effective priors, leading to optimal restoration, only to the extent that the forms of the priors are well matched to the processes they claim to represent.
---
paper_title: Equation of state calculations by fast computing machines

paper_content:

A general method, suitable for fast computing machines, for investigating such properties as equations of state for substances consisting of interacting individual molecules is described. The method consists of a modified Monte Carlo integration over configuration space. Results for the two‐dimensional rigid‐sphere system have been obtained on the Los Alamos MANIAC and are presented here. These results are compared to the free volume equation of state and to a four‐term virial coefficient expansion.
---
paper_title: Monte Carlo Simulation in Statistical Physics: An Introduction

paper_content:

The Monte Carlo method is a computer simulation method which uses random numbers to simulate statistical fluctuations. The method is used to model complex systems with many degrees of freedom. Probability distributions for these systems are generated numerically and the method then yields numerically exact information on the models. Such simulations may be used to see how well a model system approximates a real one or to see how valid the assumptions are in an analytical theory. A short and systematic theoretical introduction to the method forms the first part of this book. The second part is a practical guide with plenty of examples and exercises for the student. Problems treated by simple sampling (random and self-avoiding walks, percolation clusters, etc.) and by importance sampling (Ising models etc.) are included, along with such topics as finite-size effects and guidelines for the analysis of Monte Carlo simulations. The two parts together provide an excellent introduction to the theory and practice of Monte Carlo simulations.
---
paper_title: Equation of state calculations by fast computing machines

paper_content:

A general method, suitable for fast computing machines, for investigating such properties as equations of state for substances consisting of interacting individual molecules is described. The method consists of a modified Monte Carlo integration over configuration space. Results for the two‐dimensional rigid‐sphere system have been obtained on the Los Alamos MANIAC and are presented here. These results are compared to the free volume equation of state and to a four‐term virial coefficient expansion.
---
paper_title: The Monte Carlo Method

paper_content:

Polyester materials are treated in such fashion as to impart to the treated surface thereof good bondability toward other materials, such as thin films of copper foil, to provide composite laminated articles useful in the industrial arts such as for printed circuitry and the like. The treatment consists essentially in subjecting the surface of the polyester material to a solution, preferably anhydrous, of an alkali metal hydroxide in a high boiling glycol such as ethylene glycol, propylene glycol, dipropylene glycol, diethylene glycol and tetraethylene glycol.
---
paper_title: Time‐Dependent Statistics of the Ising Model

paper_content:

The individual spins of the Ising model are assumed to interact with an external agency (e.g., a heat reservoir) which causes them to change their states randomly with time. Coupling between the spins is introduced through the assumption that the transition probabilities for any one spin depend on the values of the neighboring spins. This dependence is determined, in part, by the detailed balancing condition obeyed by the equilibrium state of the model. The Markoff process which describes the spin functions is analyzed in detail for the case of a closed N‐member chain. The expectation values of the individual spins and of the products of pairs of spins, each of the pair evaluated at a different time, are found explicitly. The influence of a uniform, time‐varying magnetic field upon the model is discussed, and the frequency‐dependent magnetic susceptibility is found in the weak‐field limit. Some fluctuation‐dissipation theorems are derived which relate the susceptibility to the Fourier transform of the tim...
---
paper_title: Monte Carlo theory and practice

paper_content:

The Monte Carlo method has long been recognised as a powerful technique for performing certain calculations, generally those too complicated for a more classical approach. Since the use of high-speed computers became widespread in the 1950s, a great deal of theoretical investigation has been undertaken and practical experience has been gained in the Monte Carlo approach. The author tries to lay a theoretical basis for both the 'traditional' Monte Carlo and quasi-Monte Carlo methods, and, to present some practical aspects of when and how to use them. An important theme is the comparison of Monte Carlo, quasi-Monte Carlo and numerical quadrature for the integration of functions, especially in many dimensions.
---
paper_title: Auxiliary Variable Methods for Markov Chain Monte Carlo with Applications

paper_content:

Abstract Suppose that one wishes to sample from the density π(x) using Markov chain Monte Carlo (MCMC). An auxiliary variable u and its conditional distribution π(u|x) can be defined, giving the joint distribution π(x, u) = π(x)π(u|x). A MCMC scheme that samples over this joint distribution can lead to substantial gains in efficiency compared to standard approaches. The revolutionary algorithm of Swendsen and Wang is one such example. Besides reviewing the Swendsen-Wang algorithm and its generalizations, this article introduces a new auxiliary variable method called partial decoupling. Two applications in Bayesian image analysis are considered: a binary classification problem in which partial decoupling out performs Swendsen-Wang and single-site Metropolis methods, and a positron emission tomography (PET) reconstruction that uses the gray level prior of Geman and McClure. A generalized Swendsen–Wang algorithm is developed for this problem, which reduces the computing time to the point where MCMC is a viab...
---
paper_title: Bayesian variable selection and the Swendsen-Wang algorithm

paper_content:

The need to explore model uncertainty in linear regression models with many predictors has motivated improvements in Markov chain Monte Carlo sampling algorithms for Bayesian variable selection. Currently used sampling algorithms for Bayesian variable selection may perform poorly when there are severe multicollinearities among the predictors. This article describes a new sampling method based on an analogy with the Swendsen-Wang algorithm for the Ising model, and which can give substantial improvements over alternative sampling schemes in the presence of multicollinearity. In linear regression with a given set of potential predictors we can index possible models by a binary parameter vector that indicates which of the predictors are included or excluded. By thinking of the posterior distribution of this parameter as a binary spatial field, we can use auxiliary variable methods inspired by the Swendsen-Wang algorithm for the Ising model to sample from the posterior where dependence among parameters is redu...
---
paper_title: A version of the Swendsen-Wang algorithm for restoration of images degraded by Poisson noise

paper_content:

Abstract An algorithm for restoration of images degraded by Poisson noise is proposed. The algorithm belongs to the family of Markov chain Monte Carlo methods with auxiliary variables. We explicitly use the fact that medical images consist of finitely many, often relatively few, grey-levels. The continuous scale of grey-levels is discretized in an adaptive way, so that a straightforward application of the Swendsen–Wang (Phys. Rev. Lett. 58 (1987) 86) algorithm becomes possible. Partial decoupling method due to Higdon (J. Am. Statist. Assoc. 93 (1998) 442, 585) is also incorporated into the algorithm. Simulation results suggest that the algorithm is reliable and efficient.
---
paper_title: Rate of convergence of the Swendsen-Wang dynamics in image segmentation problems: a theoretical and experimental study

paper_content:

We study in this paper the convergence rate of the Swendsen-Wang dynamics towards its equilibrium law, when the energy belongs to a large family of energies used in image segmentation problems. We compute the exponential equivalents of the transitions which control the process at low temperature, as well as the critical constant which gives its convergence rate. We give some theoretical tools to compare this dynamics with Metropolis, and develop an experimental study in order to calibrate both dynamics performances in image segmentation problems.
---
paper_title: Collective Monte Carlo Updating for Spin Systems

paper_content:

A Monte Carlo algorithm is presented that updates large clusters of spins simultaneously in systems at and near criticality. We demonstrate its efficiency in the two-dimensional $\mathrm{O}(n)$ $\ensuremath{\sigma}$ models for $n=1$ (Ising) and $n=2$ ($x\ensuremath{-}y$) at their critical temperatures, and for $n=3$ (Heisenberg) with correlation lengths around 10 and 20. On lattices up to ${128}^{2}$ no sign of critical slowing down is visible with autocorrelation times of 1-2 steps per spin for estimators of long-range quantities.
---
paper_title: Probability-changing cluster algorithm for Potts models.

paper_content:

We propose a new effective cluster algorithm of tuning the critical point automatically, which is an extended version of the Swendsen-Wang algorithm. We change the probability of connecting spins of the same type, p = 1-e(-J/k(B)T), in the process of the Monte Carlo spin update. Since we approach the canonical ensemble asymptotically, we can use the finite-size scaling analysis for physical quantities near the critical point. Simulating the two-dimensional Potts models to demonstrate the validity of the algorithm, we have obtained the critical temperatures and critical exponents which are consistent with the exact values; the comparison has been made with the invaded cluster algorithm.
---
paper_title: Invaded cluster algorithm for equilibrium critical points

paper_content:

Cluster algorithms are reviewed and a new approach, the invaded cluster algorithm, is described. Invaded cluster algorithms sample critical points without input of the critical temperature. Instead, the critical temperature is an output of the method. Invaded cluster algorithms have less critical slowing than other cluster methods for the Ising model.
---
paper_title: Probability-Changing Cluster Algorithm: Study of Three-Dimensional Ising Model and Percolation Problem

paper_content:

We present a detailed description of the idea and procedure for the newly proposed Monte Carlo algorithm of tuning the critical point automatically, which is called the probability-changing cluster (PCC) algorithm [Y. Tomita and Y. Okabe: Phys. Rev. Lett. 86 (2001) 572]. Using the PCC algorithm, we investigate the three-dimensional Ising model and the bond percolation problem. We employ a refined finite-size scaling analysis to make estimates of critical point and exponents. With much less efforts, we obtain the results which are consistent with the previous calculations. We argue several directions for the application of the PCC algorithm.
---
paper_title: Statistical mechanics of image restoration

paper_content:

We develop the statistical mechanics formulation of the image restoration problem, pioneered by Geman and Geman (1984). Using Bayesian methods we establish the posterior probability distribution for restored images, for given data (corrupted image) and prior (assumptions about source and corruption process). In the simplest cases, studied here, the posterior is controlled by a cost function analagous to the configurational energy of an Ising model with local fields whose sense is defined by the data. Through a combination of Monte Carlo simulation and mean-field theory we address three key issues. First, we explore the sensitivity of the posterior distribution to the choice of prior parameters: we find phase transitions separating regions in which the distribution is effective (data-dominated) from regions in which it is ineffective (prior-dominated). Second, we examine the question of how best to use the posterior distribution to prescribe a single "optimal" restored image: we argue that the mean of the posterior is, in general, to be preferred over the mode, both in principle and in practice. Finally, borrowing from Monte Carlo techniques for free-energy calculations, we address the question of prior parameter estimation within the "evidence" framework of Gull (1989) and MacKay (1992): our results suggest that parameters identified by this framework provide effective priors, leading to optimal restoration, only to the extent that the forms of the priors are well matched to the processes they claim to represent.
---
paper_title: Multicanonical algorithms for first order phase transitions

paper_content:

Monte Carlo simulations are discussed for systems of volume V = Ld which undergo a first order phase transition in the finite volume limit. Conventional canonical, local Monte Carlo algorithms suffer from exponentially fast slowing down ≈V2 exp (cLd−1). Here we present a class of multicanonical Monte Carlo algorithms which can reduce the slowing down to a quadratic power law ≈V2.
---
paper_title: Invaded cluster algorithm for Potts models, Phys

paper_content:

The invaded cluster algorithm, a method for simulating phase transitions, is described in detail. Theoretical, albeit nonrigorous, justification of the method is presented and the algorithm is applied to Potts models in two and three dimensions. The algorithm is shown to be useful for both first-order and continuous transitions and evidently provides an efficient way to distinguish between these possibilities. The dynamic properties of the invaded cluster algorithm are studied. Numerical evidence suggests that the algorithm has no critical slowing for Ising models. @S1063-651X~96!09208-2#
---
paper_title: Invaded cluster dynamics for frustrated models

paper_content:

Recently, a nonstandard cluster Monte Carlo ~MC! dynamics, the invaded cluster ~IC! dynamics, based on invaded percolation has been introduced by Machta et al. for the ferromagnetic Ising model @1#. The IC dynamics is based on the Kastelein-Fortuin‐Coniglio-Klein ~KF-CK! cluster formulation of the Ising model @2# and has been shown to be even more efficient than the Swendsen-Wang~SW! dynamics @3# in equilibrating the system at the critical temperature. The IC dynamics has the advantage that the value of the critical temperature does not need to be known a priori. In fact, the dynamics itself drives the system to the critical region as in self-organized critical ~SOC! systems. The aim of this paper is to extend the IC dynamics to frustrated systems where KF-CK clusters percolate at a temperature T p higher than the critical temperature Tc . In particular, we will consider the fully frustrated ~FF! Ising model on a square lattice where it has been shown numerically @4# that kBT p /J.1.69 (kB is the Boltzmann constant and J is the strength of the interaction! and Tc50. We will use two definitions of clusters. The first definition is based on the KF-CK clusters. In this case the IC dynamics leads to a SOC percolating state at temperature T p corresponding to the percolation of KF-CK clusters. The second definition is more general @5# and reduces to the cluster of Kandel, Ben-Av, and Domany @6# in the FF Ising model. In this case the IC dynamics leads to a SOC state at the thermodynamical critical temperature T c 50. In Sec. II we review the definition and the results of IC dynamics on the ferromagnetic Ising model. Then we extend the IC dynamics to the FF Ising model using the KF-CK cluster in Sec. III and the Kandel‐Ben-Av‐Domany ~KBD! clusters in Sec. IV, where we study also the equilibrium relaxation of the proposed dynamics. We present conclusions in Sec. V.
---
paper_title: New Monte Carlo algorithm: Entropic sampling.

paper_content:

We present a new Monte Carlo sampling algorithm, with which one can obtain any desired distribution of the sampling in one Monte Carlo simulation. The free energy and the entropy of a system can thus be obtained from a simple exercise of this algorithm. The main idea is to sample directly the entropy of a system at infinite temperature. Importance sampling is shown to be a particular case of the new algorithm. The algorithm is tested against the exact partition function of the [ital L]=4 simple cubic Ising model. A comparison with the multicanonical ensemble for the [ital L]=12, [ital q]=10 Potts model shows that the new algorithm is more general and more efficient.
---

Title: Bayesian Restoration of Digital Images Employing Markov Chain Monte Carlo: A Review

Section 1: Introduction
Description 1: Introduce the problem of noise in digital images and the importance of image restoration. Discuss traditional image processing techniques and their limitations, and explain the relevance of statistical mechanics and Bayesian statistics in image processing.

Section 2: Mathematical Description of an Image
Description 2: Provide a mathematical representation of an image, introducing terms like pixels, gray levels, and the concept of a noisy image versus a true image.

Section 3: Stochastic Description of an Image
Description 3: Explain the stochastic approach to describing images, including the concept of an image as a collection of random variables and the introduction of state space and random fields.

Section 4: Poisson Likelihood Distribution
Description 4: Describe the Poisson model for image degradation, explaining why Poisson statistics are used and how the Likelihood distribution is formulated.

Section 5: Kullback-Leibler Entropy Distance
Description 5: Define and explain the Kullback-Leibler entropy distance as a measure of the difference between two images and its relevance in quantifying image degradation.

Section 6: Hamming Distance
Description 6: Introduce the Hamming distance metric for measuring the difference between two images, especially useful for binary and low-gray-level images.

Section 7: Gaussian and Other Channel Likelihood Distributions
Description 7: Discuss other popular models for image degradation, including Gaussian channel and binary symmetric channel models.

Section 8: Three Ingredients of Bayesian Methodology
Description 8: Introduce the essential components of Bayesian methodology in image processing: Likelihood, Prior, and Posterior distributions.

Section 9: Bayesian Priori Distribution
Description 9: Discuss the concept of Bayesian Prior, including energy models, Gibbs distribution, and Markov random fields.

Section 10: Markov Chain Monte Carlo Methods
Description 10: Describe the use of Markov Chain Monte Carlo (MCMC) methods for image restoration, including Metropolis and Gibbs sampler algorithms.

Section 11: Bayesian Maximum Posteriori (MAP) Methods
Description 11: Explain how Maximum à Posteriori estimation is used in Bayesian image restoration and the balance between Prior and Likelihood.

Section 12: Restoration of Toy and Benchmark Images
Description 12: Present case studies and examples of image restoration using Bayesian MCMC methods on toy and benchmark images, describing the process and results.

Section 13: Cluster Algorithms for Image Restoration
Description 13: Detail advanced techniques like Swendsen-Wang and Wolff cluster algorithms for efficient image restoration and their implementation.

Section 14: Conclusion and Future Directions
Description 14: Summarize the key findings of the review, discuss the effectiveness of the Bayesian MCMC approach, and suggest potential areas for future research in image restoration.