🚀 go-pugleaf

In article <1992Aug6.111336.9896@waikato.ac.nz> singlis@waikato.ac.nz writes:

> How do you calculate the FFT of a 2-D image? I assume you calculate the FFT
> of the row/col of the element (pixel) you are working with.

The equation that describes the 2-D FFT is `separable', which means
that it can be decomposed into a series of 1-D FFTs.  In other words,
you FFT along all the rows, then FFT down all the columns.  (This is
not, however a very efficient way to do it!)  Most image processing
books go into this topic in a little detail.

> BUT how do they display this as an intensity diagram? An FFT creates a freq.
> breakdown, how do you display this as a single intensity???

The result of a FT is complex: for every pixel, there is a real part
and an imaginary part.  To display the FT, it is common (but by no
means universal) to convert the real-imaginary representation to
modulus-phase, and then display the modulus (or maybe modulus-square),
since this is what happens in real life (i.e., optics).  But don't
just discard the phase: the information it contains is at least as
important as that in the modulus!

--
 Dr Adrian F. Clark                                   JANET: alien@uk.ac.essex
 INTERNET: alien%uk.ac.essex@nsfnet-relay.ac.uk          FAX: (+44) 206-872900
 BITNET: alien%uk.ac.essex@ac.uk              PHONE: (+44) 206-872432 (direct)
 Dept ESE, University of Essex, Wivenhoe Park, Colchester, Essex, C04 3SQ, UK.

In article <ALIEN.92Aug6090438@vulcan.essex.ac.uk>, alien@essex.ac.uk
("Adrian F Clark") writes

> that it can be decomposed into a series of 1-D FFTs.  In other words,
> you FFT along all the rows, then FFT down all the columns.  (This is
> not, however a very efficient way to do it!) [...]

Actually, row-column decomposition IS a fairly efficient way to
compute a 2-D DFT.  Slightly faster methods exist (e.g., vector-radix
FFTs), but the speed-up over row-column decomposition is usually
small, and may not be worth the extra difficulty in programming
(considerable).  Row-column decomposition gets you down to the right
order of complexity.

The following is a good introductory reference:

 AUTHOR:  Lim, Jae S.
 TITLE:   Two-dimensional signal and image processing /
 EDITION: c1990.
 IMPRINT: Englewood Cliffs, N.J. : Prentice Hall,

Kris Popat
MIT Rm. E15-355  Cambridge, MA 02139         popat@media-lab.mit.edu

alien@essex.ac.uk ("Adrian F Clark") writes:


>The equation that describes the 2-D FFT is `separable', which means
>that it can be decomposed into a series of 1-D FFTs.  In other words,
>you FFT along all the rows, then FFT down all the columns.  (This is
>not, however a very efficient way to do it!)                 ^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

I don't understand this remark; could you elaborate?



>Most image processing
>books go into this topic in a little detail.

Which is your favorite?


-- 

	Jeff Mulligan (jbm@eos.arc.nasa.gov)
	NASA/Ames Research Ctr., Mail Stop 262-2, Moffett Field CA, 94035
	(415) 604-3745

In article <POPAT.92Aug6115014@image.mit.edu> popat@image.mit.edu (Kris Popat) writes:
>
>In article <ALIEN.92Aug6090438@vulcan.essex.ac.uk>, alien@essex.ac.uk
>("Adrian F Clark") writes
>
>> that it can be decomposed into a series of 1-D FFTs.  In other words,
>> you FFT along all the rows, then FFT down all the columns.  (This is
>> not, however a very efficient way to do it!) [...]
>
>Actually, row-column decomposition IS a fairly efficient way to
>compute a 2-D DFT.  Slightly faster methods exist (e.g., vector-radix
>FFTs), but the speed-up over row-column decomposition is usually
>small, and may not be worth the extra difficulty in programming
>(considerable).  Row-column decomposition gets you down to the right
>order of complexity.
>
>The following is a good introductory reference:
>
> AUTHOR:  Lim, Jae S.
> TITLE:   Two-dimensional signal and image processing /
> EDITION: c1990.
> IMPRINT: Englewood Cliffs, N.J. : Prentice Hall,
>

This is a good reference; however, much of its analysis about algorithms
has not been updated for current computer architecture.  In particular, the
analysis of convolution by using two FFTs together reduces only complex
multiplications.  Computers today are more sensitive to memory accesses.
This is of CRITICAL importance when using a workstation without local
swap space.  

What you have to ask yourself is what takes longer on your machine?
a complex multiplication or cache misses.  Page faults are killers but don't
happen as often.

The point is that just because someone says that their algorithm is better
does not mean that it will be better on your machine.

John Liptak
jliptak@lookout.uswest.com

In article <POPAT.92Aug6115014@image.mit.edu>, popat@image.mit.edu (Kris
Popat) writes:
>
>In article <ALIEN.92Aug6090438@vulcan.essex.ac.uk>, alien@essex.ac.uk
>("Adrian F Clark") writes
>
>> that it can be decomposed into a series of 1-D FFTs.  In other words,
>> you FFT along all the rows, then FFT down all the columns.  (This is
>> not, however a very efficient way to do it!) [...]
>
>Actually, row-column decomposition IS a fairly efficient way to
>compute a 2-D DFT.  Slightly faster methods exist (e.g., vector-radix
>FFTs), but the speed-up over row-column decomposition is usually
>small, and may not be worth the extra difficulty in programming
>(considerable).  Row-column decomposition gets you down to the right
>order of complexity.

Well I have only one data point, but I found that on an RS6000 using IBMs
ESSL library, a large 3D FFT (say 60x60x60) runs about twice as fast as
splitting it along three dimensions and do each ray. Presumably the hit
isn't quite as bad in 2D. I imagine whatever ESSL uses for the 3D FFT
directly is the best known- it's a rather impressive library.

Maynard Handley

In <ALIEN.92Aug6090438@vulcan.essex.ac.uk> alien@essex.ac.uk ("Adrian F Clark") writes:


>In article <1992Aug6.111336.9896@waikato.ac.nz> singlis@waikato.ac.nz writes:

>> How do you calculate the FFT of a 2-D image? I assume you calculate the FFT
>> of the row/col of the element (pixel) you are working with.

>The equation that describes the 2-D FFT is `separable', which means
[stuff deleted]
>since this is what happens in real life (i.e., optics).  But don't
>just discard the phase: the information it contains is at least as
>important as that in the modulus!

Ok. Understood. But exactly what does it contain? I just can't seem to
grasp what the phase information in a 2d FFT actually means. I'm after
an intuitive answer, not a mathematical one. With 1d signals, it's a
little bit easier.

>--
> Dr Adrian F. Clark                                   JANET: alien@uk.ac.essex
> INTERNET: alien%uk.ac.essex@nsfnet-relay.ac.uk          FAX: (+44) 206-872900
> BITNET: alien%uk.ac.essex@ac.uk              PHONE: (+44) 206-872432 (direct)
> Dept ESE, University of Essex, Wivenhoe Park, Colchester, Essex, C04 3SQ, UK.

Shckwish!
(Chris Karadaglis, Iconix)

In article <ck.713491034@iconix.oz.au> ck@iconix.oz.au (Chris Karadaglis) writes:

> Ok. Understood. But exactly what does it contain? I just can't seem to
> grasp what the phase information in a 2d FFT actually means. I'm after
> an intuitive answer, not a mathematical one. With 1d signals, it's a
> little bit easier.

I don't understand your confusion.  The meaning of phase in a 2-D
image is _precisely_ the same as that of phase in a 1-D signal: each
pixel (sample) in the image (signal) has a modulus component and a
phase component.  Think of it in a vector way: the modulus is the
length of an arrow with its blunt end at the origin, and the phase
gives the direction in which the arrowhead points.

This is why it's important not to fiddle with the phase when filtering
(which fiddles with the amplitude).  There are demonstrations of the
relative importance published, such as mixing the phase of one image's
FT with the amplitude of another image's FT and then inverting the
transform: the `phase image' is usually dominant.

--
 Dr Adrian F. Clark                                   JANET: alien@uk.ac.essex
 INTERNET: alien%uk.ac.essex@nsfnet-relay.ac.uk          FAX: (+44) 206-872900
 BITNET: alien%uk.ac.essex@ac.uk              PHONE: (+44) 206-872432 (direct)
 Dept ESE, University of Essex, Wivenhoe Park, Colchester, Essex, C04 3SQ, UK.