6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Do you pad the filter with zeros to make it the same size as the image before you take its FFT? Are you doing the complex division correctly? $\endgroup$ – Dima Oct 30 '11 at 4:33
  • $\begingroup$ Yup, padded the filter with zeros, kernel in upper left. All my Python/numpy code is at the aforementioned stackoverflow.com link. The complex division is probably my problem. $\endgroup$ – David Poole Oct 31 '11 at 23:01
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Deconvolution" was a new word for me. I still have much to learn. Thanks! $\endgroup$ – David Poole Oct 31 '11 at 23:11
  • $\begingroup$ @JasonR wouldnt we have to know a 'trainer' sequence in the image for Wiener deconvolution so that MMSE criterion is minimized with respect to something that is known to be true? $\endgroup$ – Spacey Nov 1 '11 at 1:53
  • 1
    $\begingroup$ In general, you need to know the power spectral density of the signal and the transfer function that has been applied to the signal to design the Wiener filter. However, in the likely event that you do not know all of that information, you can make educated guesses that yield a functional structure that is more robust than the inverse filter. See this section on the Wikipedia page for a discussion. $\endgroup$ – Jason R Nov 1 '11 at 3:18
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.