Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!usc!jarthur!elroy.jpl.nasa.gov!ames!sgi!karsh@trifolium.esd.sgi.com
From: karsh@trifolium.esd.sgi.com (Bruce Karsh)
Newsgroups: comp.sys.sgi
Subject: Re: Fast Fourier Transforms and the GVX
Message-ID: <52686@sgi.sgi.com>
Date: 5 Mar 90 10:16:18 GMT
References: <1990Mar2.160357.10094@hellgate.utah.edu>
Sender: news@sgi.sgi.com
Reply-To: karsh@trifolium.sgi.com (Bruce Karsh)
Organization: Silicon Graphics, Inc., Mountain View, CA
Lines: 50

In article <1990Mar2.160357.10094@hellgate.utah.edu> twolf%ug.utah.edu@cs.utah.edu (Tom Wolf) writes:

>Several of us have been trying to figure out what Fourier Transforms are used
>for in graphics processing? Any ideas?

Fourier transforms are used in image processing for a variety of reasons:

    1)   Fast convolution.

         "Convolution" is a big fancy word for "weighted moving average".
         In other words, each pixel value is replaced by the sum of the
         nearby pixels multiplied by a weighting factor.  I.e.,

		   --
	 P'[i,j] = \	W[m,n] * P[i-m,j-n]
		   /
		   --
		   m,n

	Convolutions are used to blur images, sharpen images, enhance edges,
	and lots of other things.  The image processing literature is full
        of info about this.

	The calculation of a convolution as a sum of products is
        computationally costly.  Using the FFT method, described in almost
        any book on signal processing is often much more efficient.

    2)  Digital filtering.

	Digital filters are used for anti-aliasing images.  The Fourier
	Transform is sometimes used to design these filters.

    3)  Image compression.

	Various schemes have been tried to reduce the number of bits required
	to store an image by Fourier transforming an image and not storing all
	of the coefficients.  For instance, low frequency components and
	small components may be discarded.  Of course, this degrades the image
	quality, but in some instances, it may be worth it.

    4)  Shift invariant representation.

	The magnitude of the Fourier components of an image does not change
	when the image is translated.  (The phase of the components do,
	however).  For this reason, Fourier transforms are sometimes used to
	match a possibly shifted image against a pattern image.  If the
	magnitude of the coefficients aren't approximately equal then the
	image doesn't match the pattern.

Any others?