next up previous contents
Next: The importance of priors Up: Literature review Previous: The Wiener filter

Global iterative approaches

Local filters use information from a local neighborhood to restore pixels one at a time. In contrast, global filters use information from the entire image to restore each pixel. To achieve this, there must be a mechanism for information to travel between every pair of pixels. Wiener filters achieve this by using the frequency domain representation of the image, in which each Fourier coefficient is affected by the value of almost every pixel. Most global filtering approaches achieve it through iteration: at each step, information propagates locally. Many iterations allow information to propagate globally.

A shortcoming of global iterative approaches is that they tend to be quite slow. Some of the algorithms which generate impressive results require hours to filter a single image. For this reason, parallel implementations of these algorithms have been explored.

Most of the algorithms are quite complicated, which makes comparison with them difficult. Implementing some of the newer approaches would be a worthy thesis on its own. For this reason, the most successful global iterative approaches are briefly described here and not mentioned again.

Adaptive filters extend the notion of linear filters by allowing for coefficients which change according to local image properties. The most popular of these are adaptive recursive filters [12, 13, 14, 15, 16] which are based on difference equations with adaptive coefficients. Such filters are able to smooth over very large regions, but can adapt quickly to local signal characteristics. These approaches require many iterations to converge to a solution of the difference equations. Some attempts have been made to adapt multigrid techniques [17, 18] for image restoration. Multigrid methods hold the promise of global algorithms which have complexity for an NxN image (i.e. linear in the number of pixels). Non-multigrid adaptive recursive approaches generally have complexity with a lower bound of .gif

Another family of image restoration techniques are based on Markov Random Fields and ``annealing'' techniques [19, 20, 21, 22]. Annealing techniques are inspired by physical systems which settle into low-energy states as they cool. Loosely, these techniques make small random changes to an image based on a gradually decreasing ``temperature'' parameter. At initial high temperatures, the changes are very large. As the temperature is lowered, the changes become smaller. These changes are directed toward maximizing an objective function. The objective function is based on the posterior probability and an assumed Markov Random Field (MRF) model for the image. The image tends to settle into a ``low energy state'' which corresponds to a mode of the MRF model. Quite astonishingly good results have been achieved using these approaches, but they are extremely slow. Parallel versions of these methods have been implemented in an attempt to reduce filtering time [23, 24].

Regularization methods [4, 25, 26] regard image restoration as an ill-posed inverse problem. Such problems can not be solved by direct inversion, because the solution is highly unstable. To stabilize the inversion, a stabilizing functional is introduced. A typical restoration problem involves blurring and additive noise. This process can be written in matrix form as:

where is the original image, is a matrix representation of the Point Spread Function (PSF), is the noise, and is the observed signal. The matrix is typically ill-conditioned or singular, so that evaluating is problematic. In a regularization approach, one introduces additional constraints based on assumptions about the signal model. Some common approaches are:


next up previous contents
Next: The importance of priors Up: Literature review Previous: The Wiener filter

Todd Veldhuizen
Fri Jan 16 15:16:31 EST 1998