Background

Image filtering and inverse filtering

We briefly review least squares solutions of matrix equations.

Let

a = [.1414 .7071 .1414]

and consider its outer product as a (separable) 3x3 filter

H = a'a

We can use MATLAB to construct and apply H to lena.raw. The result will be a slightly blurred output image, since H is approximately a low pass filter.

We want to find the separable filter that recovers the original image as closely as possible (where closeness is measured by mean squared error i.e. we want to find the "inverse" of H). First we find the optimal 1x3 horizontal filter c, then the optimal 3x1 vertical filter d. The outer product d c is the inverse filter we want.

Optimal horizontal filter

Let X denote the original image, and

Z = H X

be the degraded (blurred) image. In this equation we assume that H and X are arranged so that the matrix multiplication produces a convolution.

Given Z, we want to find c such that

X_hat = Z c

is the best approximation of X in the least squares sense. Here, c is our optimal 3x1 vector, Z here refers to the Z in the previous equation that has been rearranged as a (510*512) by 3 matrix, and X_hat is a (510*512) by 1 column vector.

Note that the longer dimension of X_hat and Z is (510*512), not (512*512), because we don't need to compute output values at the left and right one-pixel boundaries.

To solve for the optimal filter vector c, we assume that X is known, and compute:

c = (Z'Z)^(-1) Z' X

where [(Z'Z)^(-1) Z'] is referred to as the pseudo-inverse of the matrix Z. Note that X is the (512x510)x1 vector containing the values of the original image.

After finding c, apply it to Z to get a partially restored image, and repeat the above procedure, but replace Z with the partially restored image, and rearrange terms to account for the vertical filter d (note that 510x512 becomes 510x510).

The optimal 3x3 filter is the outer product d c. Apply this optimal 3x3 filter to the degraded image and compare the resulting image with the original image.

Calculate the MSE between X and Z, X and Z c, and between X and ((Z c) d).