Efficient image restoration algorithms for near-circulant systems

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 efficient 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 regularization into decompression of a compressed JPEG image, this algorithm significantly reduces blocky effects in the image. The proposed edge-preserving regularization scheme can be applied to reduce ringing artifacts on edges and smooth block boundaries in JPEG images. When the image restoration system is a TBT system instead of a CBC system, we can still make use of the FFT by extending and displacing the system to achieve a fast solution. In general, the proposed techniques in this dissertation improve the quality of restored images and improve the computational performance.