Question

1. Consider an image of size 10,000-by-10,000 pixels that needs to be convolved with a filter of size 100-by-100. Comment about the most efficient method for convolving. Would it be convolution in spatial domain or Fourier?

Answer 1

Convolution has applications that include probability, statistics, computer vision, natural language processing, image and signal processing, engineering, and differential equations. The convolution can be defined for functions on Euclidean space, and other groups.Convolution:Convolution in time domain results in multiplication in the frequency domain. You find the Fourier transform of the signals and multiply them,then find the inverse Fourier transform of the result. The final result will be equivalent to convolution of the signals in time domain.

Suppose that you despise convolution. What are you going to do if given an input signal and impulse response, and need to find the resulting output signal? Figure 9-8 provides an answer: transform the two signals into the frequency domain, multiply them, and then transform the result back into the time domain. This replaces one convolution with two DFTs, a multiplication, and an Inverse DFT. Even though the intermediate steps are very different, the output is identical to the standard convolution algorithm.

Does anyone hate convolution enough to go to this trouble? The answer is yes. Convolution is avoided for two reasons. First, convolution is mathematically difficult to deal with. For instance, suppose you are given a system's impulse response, and its output signal. How do you calculate what the input signal is? This is called deconvolution, and is virtually impossible to understand in the time domain. However, deconvolution can be carried out in the frequency domain as a simple division, the inverse operation of multiplication. The frequency domain becomes attractive whenever the complexity of the Fourier Transform is less than the complexity of the convolution. This isn't a matter of which you like better; it is a matter of which you hate less.

The Fourier transform of the convolution is the product of the two Fourier transforms! The correlation of a function with itself is called its autocorrelation.

The Fourier transform is a linear operator – The transform of the sum of two functions is the sum of the transforms h12 = h1 + h2 H12 ( f )= h12e−2πift dt −∞ ∞ ∫ = h1 + h ( 2 )e−2πift dt −∞ ∞ ∫ = h1 e−2πift dt −∞ ∞ ∫ + h2 e−2πift dt −∞ ∞ ∫ = H1 + H Fourier Transforms • h(t) may have some special properties – Real, imaginary – Even: h(t) = h(-t) – Odd: h(t) = -h(-t) • In the frequency domain these symmetries lead to relations between H(f) and H(-f).