- AUETD Home
- View Item

## Efficient Image Restoration Algorithms for Near-Circulant Systems

##### Date

2007-05-15##### Author

Pan, Ruimin

##### Type of Degree

Dissertation##### Department

Electrical and Computer Engineering##### Metadata

Show full item record##### Abstract

The problem of image restoration has been extensively studied for its practical importance as well as its theoretical interest. Restoration problem arises in almost every branch
of engineering and applied physics. The goal of image restoration is to recover the original
scene from the degraded observations. It seeks to model the degradations, blur and noise,
and apply an inverse procedure to obtain an approximation of the original scene.
Due to the fact that image restoration requires a huge amount of computation and
storage, techniques and algorithms that can improve the speed or quality are desirable. A
great variety of fast restoration methods have been proposed. The most well known fast
restoration algorithms involve the use of fast Fourier transforms (FFT's) to implement shift-
invariant deblurring. However, in the face of unknown boundaries, shift-variant smoothing,
and other conditions, FFT's cannot be used in a straightforward manner in the inversion
process.
A group of effcient image restoration algorithms for circulant or near-circulant systems
are proposed in this dissertation that overcome some of these limitations in the direct
application of fast transforms. We assume that the system is a circulant or near-circulant
system so that the convolution property of the FFT can be used.
The regularization of the least-squares criterion is an effective approach in image
restoration to reduce noise amplification. To avoid the smoothing of edges, edge-preserving
regularization using a Gaussian Markov random field (GMRF) model is often used to allow realistic edge modeling and provide stable maximum a posteriori (MAP) solutions.
However, this approach is computationally demanding because the introduction of a non-
Gaussian image prior makes the restoration problem shift-variant. In this case, a direct
solution using FFT's is not possible even when the blurring is shift-invariant.
We consider a class of edge-preserving GMRF functions that are convex and have non-
quadratic regions that impose less smoothing on edges. We propose a decomposition-enabled
edge-preserving image restoration (DEEPIR) algorithm for maximizing the likelihood function. By decomposing the problem into two sub-problems with one shift-invariant and the
other shift-variant, our algorithm exploits the sparsity of edges to define an FFT-based
iteration that requires few iterations and is guaranteed to converge to the MAP estimate.
The assumption of a circulant system does not always hold under certain circumstances. Many problems in signal and image processing require the solution of systems with
a Toeplitz-block-Toeplitz (TBT) structure in which both the Toeplitz blocks and the block
structure are banded. Some fast algorithms make use of the persymmetry (symmetry about
the main antidiagonal) of the Toeplitz blocks, while the ""bandedness"" remains unexplored.
Other algorithms exploit block bands but not banded blocks (or vice versa).
We present a fast algorithm that exploits both the bandedness of the blocks and the
block-bandedness of the block Toeplitz structure by extending the system to a circulant-
block-circulant (CBC) system and solve for the original image by solving a larger system.
Since a Toeplitz-block-Toeplitz system has a near-circulant structure, the computation involved in the extending and solving is comparatively small. Other published algorithms for
TBT matrices typically involves O(M5) operations or O(6M3) operations with `bandlimited
assumption'. This method requires O(k2M3) operations for an M2* M2 Toeplitz-block-
Toeplitz matrix with bandwidth k without any assumptions about the system.
The edge-preserving regularization method proposed for edge preserving also has applications in deblocking JPEG images where the block discrete cosine transform and quantization cause contouring and blocky artifacts in the compressed image. By integrating
regular