Image de-blurring: in frequency domain or in spatial domain ? 

Very often image deblurring, i.e. reconstruction ("sharpening")  of blurred images is performed in discrete frequency domain instead of spatial domain. Despite having many positive aspects,  deblurring in frequency domain has a negative feature of critical importance: the blurring matrix in the frequency domain is very ill-conditioned.

But what exactly “ill-conditioned” means, and what effect does it have on image restoration?

Consider in more detail the matrix condition ratio. It is defined as the ratio between the matrix' maximum and minimum singular values:

cond(A) = s_max/s_min

where s_max and s_min are the maximum and the minimum diagonal values of the matrix S in the singular value decomposition of our matrix A:

A = U S V^T

The meaning of the condition ratio should be considered in more detail. Consider a system of linear algebraic equations (or SLAE for short):  Ax=b.

Suppose we know the elements of the matrix A exactly, but elements of the right-hand side vector b are known with some degree of uncertainty b+db. The uncertainty in the elements of the right-hand side vector b leads to an uncertainty in the solution x. Then we have

A(x+dx)= b+db

Then, following Forsythe and Moler, we have

which means that  “uncertainty” in the solution of SLAE is limited by cond(A) multiplied by the “uncertainty” in the right-hand side vector b.

Similarly,

which means that  “uncertainty” in the solution of SLAE is limited by cond(A) multiplied by the “uncertainty” in the elements of the matrix A.

In practice, the above expressions mean that if cond(A) = 10⁶ then any “uncertainties” (or numerical discrepancies, to be more precise) in the elements of the right-hand side vector b or of the matrix A are multiplied in the solution by a value of the magnitude of about one million. 

The larger the condition ratio of the matrix is, the less accurate is the solution, and vice versa.

For some filters in the frequency domain, a threshold value is introduced. All elements of the blurring matrix, which are less or equal to that threshold values, are set to zero. This procedure effectively reduces the rank of the blurring matrix and improves its condition number. However, because small singular values of the blurring matrix correspond to high frequencies, which represent the details of the image, the fine details if the image are irreparably lost.

As an example, we consider the condition ratio of a simple blurring matrix in both spatial and frequency domains.

Consider an LSI degradation system with a one-dimensional motion blur in horizontal direction spread over 9 pixels and normalized.

The following MATLAB code reads an original RGB image of a rose from a .jpeg file, converts it to grey scale, and introduces blurring in frequency domain:

original = im2double(rgb2gray((imread('input_tiny.jpg'))));

% 1-D motion blur

motion_kernel = ones(1, 9) / 9;

% frequency response

motion_freq = fft2(motion_kernel, 64, 64);

cond = cond(motion_freq);

As expected, the condition ratio of the blurring matrix is very large:  8.9*10⁺¹⁸, which MATLAB sets to infinity, thus indicating that the matrix is singular and, therefore, no reliable solution could be obtained.

The condition ratio of the blurring matrix in the spatial domain (constructed when rows of the blurred image are ordered lexicographically) equals 36.686, which means that the matrix is very well-conditioned, and the solution will have sufficient (in fact, 13 or 14) significant digits. 

The  blurred and restored images are shown below:

The general conclusion is the image de-blurring in spatial domain is the only reliable approach to the problem. Working in frequency domain should be avoided at all costs. 

It should be noted that it does not matter what mathematical method is used to solve the SLAE with ill-conditioned matrix, since all the errors (uncertainties) in the input data as well as the round-off errors would be magnified in the solution.