Using the Inverse Filter to Correct a Spatially Convolved Image (Deconvolution)

Question

As part of a homework assignment, we are implementing the Inverse Filter. Degrade an image then recover with an Inverse Filter.

I convolve the image in the spatial domain with a 5x5 box filter. I FFT the filter, FFT the degraded image, then divide the degraded image by the filter. Inverse FFT the result into an image and I get garbage.

If I FFT the image, FFT the filter, multiply the two, divide that result by the FFT'd filter, obviously I get very close to the original image. ((X*Y)/Y ~== X)

I have an inkling the math is not as simple as "spatially convolved == FFT multiplication".

What is is the correct way to use the Inverse Filter? I have the exact kernel used degrade the image. I'm not adding any noise.

Bovik's textbook, The Essential Guide to Image Processing is almost completely dismissive of the Inverse Filter. Gonzalez&Woods is a bit more hopeful but almost immediately skips to the Wiener Filter.

I have a similar question on stackoverflow.com https://stackoverflow.com/questions/7930803/inverse-filter-of-spatially-convolved-versus-frequency-convolved-image

(This questions should also be tagged [homework] but the tag doesn't exist yet and I haven't the rep to create it.)

EDIT. For some of the great suggestions below. @dipan-mehta Before I FFT, I am padding the convolution kernel to the same size as the image. I'm putting the kernel into the upper left. I ifft(ifftshift()) then save to an image and I get a good result. I've done the ifft(ifftshift()) on both the kernel and the image. Good(ish) results. (Images are in my https://stackoverflow.com/questions/7930803/inverse-filter-of-spatially-convolved-versus-frequency-convolved-image question.)

@jason-r is probably correct. I don't understand the mathematics of the underlying convolution + transform. "Deconvolution" was a new word for me. Still have much to learn. Thanks for the help!

My solution for the homework assignment is to do everything in the frequency domain. I spoke with the professor. I was making the assignment harder than necessary. She wanted us to add noise then try the Inverse Filter, Wiener Filter, and Constrained Least Squares Filter. The point of the exercise was to see how the filters handled noise.

Answer 1

There's a couple subquestions that I'll address separately:

• Convolution in the spatial domain (or correspondingly in the time domain for time-sampled signals) is equivalent to multiplication in the frequency domain. In sampled systems, there are some subtleties to boundary cases (i.e. when using the DFT, multiplication in the frequency domain actually gives you circular convolution, not linear convolution), but in general, it really is that simple.

• Pure inverse filtering is almost never the right solution in practice. In most cases, you don't have access to the exact filter that has been applied to your data, so you can't simply invert it anyway. Even if you do know the filter, then it's still problematic. Consider the fact that the filter may have zeros at certain spatial frequencies; if it does, then after applying the filter to your image, all information at those frequencies is lost. If you naively invert that filter, it will have infinite (or at least very high) gain at those nulls. If you then apply the naive inverse to an image that has any additive content at those frequencies (e.g. noise, which is likely to be the case), then that unwatned component will be greatly amplified. This is generally not desirable.

  This inverse-filtering problem is very similar to equalization in communications systems, where this phenomenon is referred to as noise enhancement. In that context, the inverse-filter approach is referred to as a zero-forcing equalizer, which is rarely actually used.

• The area that you're exploring is known more generally as deconvolution. As a general rule, deconvolution is a tricky operation. Even if you know the exact filter that was applied and want to undo it, it's not always that easy. As you noted, the inverse filter approach is usually brushed aside in favor of a Wiener filter or some other structure that aims not to exactly invert the system, but instead to estimate what the input to the system was while minimizing some error criterion (minimizing mean-squared error is a common goal). As you might expect, applying a Wiener filter to this problem is referred to as Wiener deconvolution.

Answer 2

I hope you have not made mistake in the way computation is done for -

I convolve the image in the spatial domain with a 5x5 box filter. I FFT the filter, FFT the degraded image, then divide the degraded image by the filter. Inverse FFT the result into an image and I get garbage.

Suppose your image is 256x256 size, and Filter is 5x5 - in order to apply the Filtering by multiplying the FFTs, you must first convert the filter into equivalent size first. For this, you must keep 5x5 box filter at the "TOP corner" (not center of the image) and pad it rest with zeros to fill 256x256 - you should get an FFT of 256x256 for the filter.

To help diagnose, in programming step #1 - first just take 256x256 FFT of filter alone and check if the IFFT - routine is able to give you back the filter. Same way test if FFT --> IFFT of image itself works backwards properly.

Step #2 - if you only apply filter (and no inverse filter) in the FFT domain by multiplying - check the resultant image after IFFT is fine. It should be basically blurred image.

If all your programming is correct - please ensure that when you do 1/x for FFT co-efficient there are no divide by zero error, and conversely when there is too much peaking the multiplications results in heavy distortions.

In general - for any stable filter, the inverse filter by definition unstable - this could be the primary reason. However, i would always like to cross check implementation before exploring theoretical limits.

If done well, i have seen multiplication in FFT is convolution in sample space both for images as well as audio signals.

Dipan.