Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 SMI; site ur-laser.uucp
Path: utzoo!linus!philabs!cmcl2!seismo!rochester!ur-laser!nitin
From: nitin@ur-laser.uucp (Nitin Sampat)
Newsgroups: net.graphics
Subject: convolution vs. FFT's
Message-ID: <355@ur-laser.uucp>
Date: Thu, 1-Aug-85 09:39:17 EDT
Article-I.D.: ur-laser.355
Posted: Thu Aug  1 09:39:17 1985
Date-Received: Sat, 3-Aug-85 06:33:19 EDT
Organization: Lab for Laser Energetics, Univ. of Rochester
Lines: 27

Does anybody know at what point do Fourier operations
become more practical to use than convolution ?

Example : lets say we are dealing with a 512 X 512 , 8 bit image.

Most image processing systems effect a convolution by using a 3 X 3 
kernal (for example in smoothing).  However, we know that by linear 
system theory, we can take  the FFT of the image and multiply 
this by the transfer function, which is nothing more than the FFT of
the impulse response(in our case the convolution kernal).  FFT operations
give us much more control over the individual frequencies. However, being
computationally demanding, they are avoided and most operations are done
in the spatial domain.  Harware and time limitations dictate that 3 X 3
kernals be used most of the time. For increased control over the frequencies
larger kernal sizes are sometimes used.

The question is that there must be a transition point above which it becomes
more practical to use FFT's .  Someone told me that this "magic number"
is 7 X 7.  So, if one were using a kernal size 7 X 7 or larger, it would
be more feasible to multiply the image by its transfer function in the 
frequency domain rather than convolve it with the impulse response.


Has anyone had any experience with this ?  Is this 7 X 7  approx. correct ?


						nitin