| dc.description.abstract | This thesis is concerned with the problem of deconvolution of discrete signals convolved with a discrete Gaussian. It examines the problem for both one? and two?dimensional signals.
The problem of deconvolution arises in the context of restoring a signal (or an image) from a degraded version. It is assumed that an unknown finite sequence x(k)x(k)x(k) is linearly convolved with an infinite sequence g(k)g(k)g(k) (called the kernel) to produce the sequence y(k)y(k)y(k), which is also of infinite extent. However, only a finite portion of y(k)y(k)y(k), of the same length as that of x(k)x(k)x(k), is available. Very frequently, y(k)y(k)y(k) is corrupted by additive noise. Thus, the degradation of the unknown signal x(k)x(k)x(k) is modelled by
y(k)=(g(k)?x(k))+n(k),k=0,…,N?1y(k) = (g(k) * x(k)) + n(k), \quad k = 0, \ldots, N-1y(k)=(g(k)?x(k))+n(k),k=0,…,N?1
where “*” denotes linear convolution, and n(k)n(k)n(k) is the noise sequence. Signal restoration is the process of recovering x(k)x(k)x(k) from y(k)y(k)y(k), given (i) the kernel g(k)g(k)g(k) and (ii) statistical information about the noise n(k)n(k)n(k). Further, it is desirable that the restoration be robust to noise.
Equation (1) can be rewritten as the matrix equation
y=Ax+n(2)y = Ax + n \tag{2}y=Ax+n(2)
where xxx, yyy, and nnn are column vectors formed from the sequences x(k)x(k)x(k), y(k)y(k)y(k), and n(k)n(k)n(k), and AAA is a Toeplitz matrix whose columns and rows are shifted finite subsequences of the kernel g(k)g(k)g(k). In the absence of noise, Eq. (2) reduces to
y=Ax(3)y = Ax \tag{3}y=Ax(3)
If the kernel is Gaussian, then AAA is symmetric, with
A[i,j]=p?a(i?j)2A[i, j] = p \, a^{(i-j)^2}A[i,j]=pa(i?j)2
where p=1/(?2?)p = 1 / (\sigma \sqrt{2\pi})p=1/(?2??) and a=exp?(?1/(2?2))a = \exp(-1/(2\sigma^2))a=exp(?1/(2?2)).
In the case of two?dimensional signals, the column vectors xxx and yyy contain the elements of the image matrices (original and degraded), with the transposed rows stacked one below the other. If the images are of size N×NN \times NN×N, the vectors xxx and yyy have size N2×1N^2 \times 1N2×1. Here, the matrix AAA is block Toeplitz with Toeplitz blocks, and each block is symmetric Toeplitz of size N×NN \times NN×N. This matrix can be expressed as a Kronecker product of two N×NN \times NN×N matrices, each similar to the one?dimensional AAA matrix.
The deconvolution problem with respect to Eq. (3) is to find xxx given yyy. It is known that a small perturbation in yyy results in a very large perturbation in the solution xxx, making the deconvolution problem ill?posed. The degree of ill?posedness varies with the kernel ggg. One measure of ill?posedness is the condition number of the matrix AAA.
In an effort to solve the restoration problem with a Gaussian kernel, this thesis studies the characteristics of the matrix AAA associated with the Gaussian kernel and obtains several interesting properties, such as bounds on the condition number of AAA, an analytical Cholesky decomposition (LL\*LL^\*LL\* decomposition), and a direct analytical formula for A?1A^{-1}A?1. Although a formal proof for the analytical Cholesky decomposition is not provided, the decomposition has been verified analytically for AAA matrices of various dimensions using the REDUCE symbolic computation package. All these results are extended to the two?dimensional case using Kronecker product identities.
The organization of the thesis is as follows:
Chapter 1 introduces the concept of deconvolution and restoration and provides a survey of existing deconvolution and restoration methods.
Chapter 2 deals with one?dimensional deconvolution. All results-including bounds on the condition number, analytical Cholesky decomposition, and the formula for A?1A^{-1}A?1-are derived. Experimental results using the formula for A?1A^{-1}A?1 are presented. | |
