Table of Contents

1. Convolution Theorem

2. Filtering

1. Convolution Theorem

Repeat Homework #5, parts A-E, by using the FFT and multiplication instead of convolution.

Compare the execution times for each assignment to the times for Homework #5. Can you explain these in terms of what you know about the run-time complexity of the different approaches?

Here is the code I used to perform the faster convolution in the Fourier domain.

Section	Homework 5 time (seconds)	Homework 8 time (seconds)
Part A	67	2
Part B	66	2
Part C	1	2
Part D	330	37
Part E	340	36

Since the run-time complexity of convolution is N^4 and the run-time complexity of the Fourier transform is only 2*N^2 log N, it is more efficient to take the Fourier transform, multiply, and take the inverse transform for large convolutions.

Return to the Table of Contents

2. Filtering

The image /usr/local/image/450/interfere.pgm has an interference pattern of unknown spatial frequency, orientation, and magnitude. (It is, however, a single frequency.) Write a program to automatically find and eliminate it. Remember that you'll have to eliminate both that frequency and its inverse frequency.

Here is the code I used to accomplish this project.

Original Image (reduced in size by half)	Corrected Image (reduced in size by half)

Return to the Table of Contents

smemoe@byu.edu
Date last modified: 11/12/1999