Deconvolution of Images - How To?

Question

I'd like to do a deconvolution of image. For example for convolution I'm using a $3\times 3$ mask with all elements $= 1$:

$$\begin{bmatrix}1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1\end{bmatrix}$$

For a pixel $X$ as follows:

$$\begin{bmatrix}X_1 & X_2 & X_3 \\ X_4 & \ \mathbf X & X_5 \\ X_6 & X_7 & X_8\end{bmatrix}$$

which is convolved by a kernel given by:

$$\begin{bmatrix}a & b & c \\ d & e & f \\ g & h & i\end{bmatrix}$$

I believe $X$ should be determined as follows

$$X=\frac{aX_1+bX_2+cX_3+dX_4+eX+fX_5+gX_6+hX_7+iX_8}{a+b+c+d+e+f+g+h+i}$$

This is a basic convolution. Now I'd like to do a deconvolution of an image which was convolved with above mask. Does anybody know how to count that?

Answer 1

Deconvolution is in the general case not possible, so it needs to be approximated with application specific constraints and requirements.

Let's look at a simple 1-dimensional example that illustrates the problem. Assume you have an impulse response like your kernel, i.e. h = [1 1 1]. Then let's look at the output of a signal (which you can think of a line of pixels), x = [2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1]. The result of the convolution is

2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 -2 -1

So except for the overhang at the edges, the result is all zeros. Information is lost and you cannot re-construct the original image from there.

Convolution is equivalent to multiplication in the frequency domain, so de-convolution is basically division in the frequency domain. That's a problem when the thing you divide by is zero or very close to zero.

Answer 2

I will try to address @Hilmar answer and answer the general question.

Hilmar Answer

Deconvolution is in the general case not possible, so it needs to be approximated with application specific constraints and requirements.

Let's look at a simple 1-dimensional example that illustrates the problem. Assume you have an impulse response like your kernel, i.e. h = [1 1 1]. Then let's look at the output of a signal (which you can think of a line of pixels), x = [2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1 2 -1 -1]. The result of the convolution is

2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 -2 -1

The case above is simply wrong. Specifically if one looks on my comment:

The result being zero doesn't mean data is lost. It has the same information as any other number.

Let's do the following example:

% Input Signal
vX = [2; -1; -1; 2; -1; -1; 2; -1; -1; 2; -1; -1; 2; -1; -1];
% Convolution Kernel
vH = [1; 1; 1];

% Convolution Result
vC = conv(vX, vH, 'full');

% Convolution Operator - Matrix Form
mH = CreateConvMtx1D(vH, length(vX), 1);

% Deconvolution
vXR = mH \ vC;

Where CreateConvMtx1D() is given in my GitHub Code.

The result is given by:

vXR.'

ans =

    2.0000   -1.0000   -1.0000    2.0000   -1.0000   -1.0000    2.0000   -1.0000   -1.0000    2.0000   -1.0000   -1.0000    2.0000   -1.0000   -1.0000

Which is a perfect reconstruction of the input signal.

General Case

Indeed the properties of Deconvolution in 1D and 2D are similar.
The ability to reconstruct the signal are basically a function of 2 parameters:

• The SNR of the data (Added noise).
• The Condition Number of the Convolution Operator of the problem.

Let us assume there is no added noise in the problem.
Then we're only limited by the Condition Number.
In theory, for any bounded Condition Number one would be able to perfectly reconstruct the signal. Yet since we use finite and quantized representation of numbers (Let's say Float64) we are limited with the condition number we're able to tackle.

For more details see - 1D Deconvolution with Gaussian Kernel (MATLAB).