In recent years, the use of Bayesian techniques and Markov random field (MRF) models for computer vision problems has been investigated by many researchers. The major disadvantage of discrete-state MRF models is that optimal estimators require excessive and typically random amounts of computation. In this thesis, we have developed and implemented two classes of deterministic and parallelizable approximation techniques for solving Bayesian estimation problems including image restoration and reconstruction and spatial pattern classification all based on MRF models of the underlying image. The first class of approximation technique is a family of approximations, denoted "cluster approximations," for the computation of the mean of a Markov random field. This is a key computation in image processing when applied to the a posteriori MRF. The approximation is to account exactly for only spat'ially local interactions. Application of the approximation requires the solution of a nonlinear multivariablefixed-point' equation for which we have proven several existence, uniqueness, and convergenceof- algorithm results. Among other applications, we have studied deblurring of noisy blurred images with excellent results. In the second approximation technique, denoted "Bethe tree approximations," we are able to compute not only the mean but also the marginal probability mass functions (pmf) for the sites of the a posteriori MRF. The marginal pmf is the key quantity in image classification and segmentation problems. The approximation is made by transforming the regular image lattice into a tree. This approximation also results in fixed-point equations for which we have proven a variety of theorems. The application of these ideas to spatial pattern classification for agricultilral remote sensing is very successful. We have compared our results with optimal estimators, specifically the thresholded posterior mean (TPM) estimators and maximizer of the posterior marginals (NIPM) estimators. We found that our approximations perform well both in terms of accuracy and speed for a wide variety of examples in image restoration, spatial pattern classification, and remote sensing. Further potential applications include edge detection, boundary detection, phase retrieval, inverse halftoning, medical imaging and color image processing.

Date of this Version

May 1994