Mathematical Methods, Algorithms and Implementations

S.Arridge

Exercise 3 

Convolutions and Filtering 

The purpose of these exercises is to gain some experience of the practical
aspects of convolution using time-domain and Fourier-domain.

*** This exercise is formally assessed and counts 15% towards your result  ***

1. One-Dimensional Convolution

Consider some simple functions h(t) such as rectangles, Gaussians, Triangles. 
Sample h(t) and carry out the following different methods of determining the 
convolution of h(t) with a Gaussian width s.

a)	Explicit time-domain convolution, by summing the convolution filter
	weights at each point.
b)	Discrete Multiplication in the Fourier-domain by the Discrete FT of the
	sampled time-domain convolution function.
c)	Analytical Multiplication in the Fourier-domain with the appropriate 
	(sampled) analytic function.
d)	Diffusion in the time-domain using finite differencing. Consider both 
	explicit and implicit time-differencing.
e)	Compare your results with the exact form, got by using the Matlab 
	Signal Processing Toolbox function "conv" to convolve h(t) 
	and the Gaussian.

The important point to demonstrate is that all methods give equivalent
results although some may be much quicker and/or have less errors.

2. Repeat part 1, steps a)-c) for the Deriche smoothing filter exp(-alpha |n|) 
and compare with the recursive filter implementation. Choose the Deriche 
parameter alpha to give the best approximation to a Gaussian of width s. If 
possible find the analytic form as in 1 e).

3. Two-Dimensional Convolution 

Repeat question 1 to perform convolution of a 2D image with a Gaussian. The 
time-domain and Fourier-domain methods are straightforward. 

Notes:
1)In the write up, it is important to discuss the expected errors of numerical
methods with respect to the exact solution.

2) Time domain convolution means :
   i)   create two lists
                {f_k} for the sampled function
                {g_k} for the sampled filter (the Gaussian)
   ii)  use the discrete version of the convolution filter
                h_k = Sum_j f_j g_(k-j)
   iii) Take care at the end points ! 

3) Discrete Multiplication in the Fourier-domain means :
   i)    create two lists
                {f_k} for the sampled function
                {g_k} for the sampled filter (the Gaussian)
   ii)  DFT both lists (f_k -> F_k, g_k ->G_k)
   iii) multiply the lists pointwise (H_k = F_k G_k)
   iv)  inverse DFT the resultant list

4) Analytic Multiplication in the Fourier-domain means :
   i)   create one list
                {f_k} for the sampled function
   ii)  DFT this list (f_k -> F_k)
   iii) Create a list G_k by sampling the analytical Fourier Transform of a
	Gaussian. For this you need to THINK CAREFULLY what frequency points
	are represented in the DFT
   iv)  multiply the lists pointwise (H_k = F_k G_k)
   v)   inverse DFT the resultant list