2D FFT

Could someone please explain the concept of 2D FFT in more layman terms?
Most if not all the resources i read about 2D FT for image processing are
loaded with lots of mathematical formulaes which I believe are important,
but have problems understanding. I just want a basic conceptual idea about
the technique before using some freeware to compute the 2D FT of a brain
image.

Thanks alot for your help.

On Feb 2, 11:04&#4294967295;am, "cherriegeller" <cherrie.gel...@gmail.com> wrote:
> Could someone please explain the concept of 2D FFT in more layman terms?
> Most if not all the resources i read about 2D FT for image processing are
> loaded with lots of mathematical formulaes which I believe are important,
> but have problems understanding. I just want a basic conceptual idea about
> the technique before using some freeware to compute the 2D FT of a brain
> image.

Why don't you start with the 1D FFT? Do you understand that? Or, to
paraphrase an old joke, first understand the FFT in N dimensions, and
then set N = 2.

illywhacker;

illywhacker wrote:
> On Feb 2, 11:04 am, "cherriegeller" <cherrie.gel...@gmail.com> wrote:
> 
>>Could someone please explain the concept of 2D FFT in more layman terms?
>>Most if not all the resources i read about 2D FT for image processing are
>>loaded with lots of mathematical formulaes which I believe are important,
>>but have problems understanding. I just want a basic conceptual idea about
>>the technique before using some freeware to compute the 2D FT of a brain
>>image.
> 
> 
> Why don't you start with the 1D FFT? Do you understand that? Or, to
> paraphrase an old joke, first understand the FFT in N dimensions, and
> then set N = 2.
> 
> illywhacker;

I'm another that has no feel for a 2D Fourier Transform (discrete OR 
continuous). In the "1D" case we can build on a demonstration of how 
only odd harmonics of a sine wave can be added to approach a square 
wave. Is there a similar demo for the "2D" case?

For example I have a gut feeling that a 2D transform of elevation data 
in the region of the San Andreas Fault or the Great Rift Valley would 
show a prominent feature. But what vector space would it be in?

On 2 Feb, 15:47, Richard Owlett <rowl...@atlascomm.net> wrote:

> For example I have a gut feeling that a 2D transform of elevation data
> in the region of the San Andreas Fault or the Great Rift Valley would
> show a prominent feature. But what vector space would it be in?

The vector space would be the space of MxN arrays, where M and N
are the dimensions of the image. But don't go there. Instead,
try and build some intuition by playing with the 2D FFTs of
binary B&W images that contain simple shapes.

Rune

On 2 Feb, 14:47, Richard Owlett <rowl...@atlascomm.net> wrote:
> illywhacker wrote:
> > On Feb 2, 11:04 am, "cherriegeller" <cherrie.gel...@gmail.com> wrote:
>
> >>Could someone please explain the concept of 2D FFT in more layman terms?
> >>Most if not all the resources i read about 2D FT for image processing are
> >>loaded with lots of mathematical formulaes which I believe are important,
> >>but have problems understanding. I just want a basic conceptual idea about
> >>the technique before using some freeware to compute the 2D FT of a brain
> >>image.

A 2D FFT is a way of making any 2D map by adding together 'egg boxes'
whose egg cells are sine shaped and that have varying widths
(frequencies) in each dimension. Strictly speaking these egg boxes are
formed by making images that have sinsusoidal variations at a single
frequency in each dimension - each basis image has just one horizontal
and one vertical frequency. They look like egg boxes, which is why I
call them egg boxes. You might call them 'textures'.

This is all there is to it.

If you apply a 2D FFT to a brain scan image that was created by MRI, I
think you will end up with the raw RF data from the MRI machine,
because at least when I worked on it 25 years ago..) the image is just
the 2D FFT of the data.

>
> > Why don't you start with the 1D FFT? Do you understand that? Or, to
> > paraphrase an old joke, first understand the FFT in N dimensions, and
> > then set N = 2.
>
> > illywhacker;
>
> I'm another that has no feel for a 2D Fourier Transform (discrete OR
> continuous). In the "1D" case we can build on a demonstration of how
> only odd harmonics of a sine wave can be added to approach a square
> wave. Is there a similar demo for the "2D" case?

Yes. You can generate mutiple images, each of which is modulated by a
sine wave of single frequency in each dimension. Sine waves in the
horizontal direction are 'horizontal' spatial frequencies, in the
vertical direction are 'vertical' spatial frequencies. Each such image
is one function from the basis set - call it (m,n) where m and n are
the horizontal and vertical spatial frequencies (say, expressed as
number of cycles across the whole image). For instance (4,0) would be
like ripples, four of them across the horizontal direction. (4,4) is a
mesh (I call it an egg box). And so on. You can add together many of
these to form any image. I do this with a simple image that is a 2D
square wave - a bright square in top left quadrant, black elsewhere.
You just add the odd harmonics but in two dimensions, to build up the
image. It doesn't work as well as a 1D square wave because we look at
an intensity map but it does well enough.

>
> For example I have a gut feeling that a 2D transform of elevation data
> in the region of the San Andreas Fault or the Great Rift Valley would
> show a prominent feature. But what vector space would it be in?- Hide quoted text -
>

I do something like this in a class I run on image processing. The 2D
FFT of a relief map of Marin County is quite simple. The fault is a
diagonal feature running from top left to bottom right on the map, and
its 2D FFT shows a prominent diagonal line running from bottom left to
top right - which is typical for linear features. The valleys that run
into the fault valley tend also to be doagonals, at an angle to the
main one, and they show up as a weaker diagonal feature in the 2D FFT.
It is not all that informative, to be honest. :-) I use the Marin
County relief map mainly to show the concept of an image as a 2D map
of some value, we just do the 2D FFT for a laugh.

Chris
=======================
Chris Bore
www.bores.com


> - Show quoted text -

Rune Allnor wrote:

> On 2 Feb, 15:47, Richard Owlett <rowl...@atlascomm.net> wrote:
Restoring snipped portion of my post ;)

 >>
 >> I'm another that has no feel for a 2D Fourier Transform (discrete OR
 >> continuous). In the "1D" case we can build on a demonstration of how
 >> only odd harmonics of a sine wave can be added to approach a square
 >> wave. Is there a similar demo for the "2D" case?
  [end restoration]
>> 
>> 
>>For example I have a gut feeling that a 2D transform of elevation data
>>in the region of the San Andreas Fault or the Great Rift Valley would
>>show a prominent feature. But what vector space would it be in?
> 
> 
> The vector space would be the space of MxN arrays, where M and N
> are the dimensions of the image. But don't go there.

Thank you. *THANK YOU* ;)

> Instead,
> try and build some intuition by playing with the 2D FFTs of
> binary B&W images that contain simple shapes.
> 
> Rune

Your suggestion would answer a different "Why" - "why/how does 2D FT work?"
My question is more "why would you want to do a 2D transform?"

I don't have any application, _that I *know* of_ , for a 2D transform. 
But I see it regularly discussed by people with a "signals" orientation. 
I have an interest in one class of signals (speech). My question might 
be phrased "what gain would I have for effort invested in studying 2D 
transforms?" I could investigate the Carnot cycle, but would it improve 
my driving?

Chris Bore wrote:

> On 2 Feb, 14:47, Richard Owlett <rowl...@atlascomm.net> wrote:
> 
>>illywhacker wrote:
>>
>>>On Feb 2, 11:04 am, "cherriegeller" <cherrie.gel...@gmail.com> wrote:
>>
>>>>Could someone please explain the concept of 2D FFT in more layman terms?
>>>>Most if not all the resources i read about 2D FT for image processing are
>>>>loaded with lots of mathematical formulaes which I believe are important,
>>>>but have problems understanding. I just want a basic conceptual idea about
>>>>the technique before using some freeware to compute the 2D FT of a brain
>>>>image.
> 
> 
> A 2D FFT is a way of making any 2D map by adding together 'egg boxes'
> whose egg cells are sine shaped and that have varying widths
> (frequencies) in each dimension. Strictly speaking these egg boxes are
> formed by making images that have sinsusoidal variations at a single
> frequency in each dimension - each basis image has just one horizontal
> and one vertical frequency. They look like egg boxes, which is why I
> call them egg boxes. You might call them 'textures'.
> 
> This is all there is to it.
> 
> If you apply a 2D FFT to a brain scan image that was created by MRI, I
> think you will end up with the raw RF data from the MRI machine,
> because at least when I worked on it 25 years ago..) the image is just
> the 2D FFT of the data.
> 
> 
>>>Why don't you start with the 1D FFT? Do you understand that? Or, to
>>>paraphrase an old joke, first understand the FFT in N dimensions, and
>>>then set N = 2.
>>
>>>illywhacker;
>>
>>I'm another that has no feel for a 2D Fourier Transform (discrete OR
>>continuous). In the "1D" case we can build on a demonstration of how
>>only odd harmonics of a sine wave can be added to approach a square
>>wave. Is there a similar demo for the "2D" case?
> 
> 
> Yes. You can generate mutiple images, each of which is modulated by a
> sine wave of single frequency in each dimension. Sine waves in the
> horizontal direction are 'horizontal' spatial frequencies, in the
> vertical direction are 'vertical' spatial frequencies. Each such image
> is one function from the basis set - call it (m,n) where m and n are
> the horizontal and vertical spatial frequencies (say, expressed as
> number of cycles across the whole image). For instance (4,0) would be
> like ripples, four of them across the horizontal direction. (4,4) is a
> mesh (I call it an egg box). And so on. You can add together many of
> these to form any image. I do this with a simple image that is a 2D
> square wave - a bright square in top left quadrant, black elsewhere.
> You just add the odd harmonics but in two dimensions, to build up the
> image. It doesn't work as well as a 1D square wave because we look at
> an intensity map but it does well enough.
> 
> 
>>For example I have a gut feeling that a 2D transform of elevation data
>>in the region of the San Andreas Fault or the Great Rift Valley would
>>show a prominent feature. But what vector space would it be in?- Hide quoted text -
>>
> 
> 
> I do something like this in a class I run on image processing. The 2D
> FFT of a relief map of Marin County is quite simple. The fault is a
> diagonal feature running from top left to bottom right on the map, and
> its 2D FFT shows a prominent diagonal line running from bottom left to
> top right - which is typical for linear features. The valleys that run
> into the fault valley tend also to be doagonals, at an angle to the
> main one, and they show up as a weaker diagonal feature in the 2D FFT.
> It is not all that informative, to be honest. :-) I use the Marin
> County relief map mainly to show the concept of an image as a 2D map
> of some value, we just do the 2D FFT for a laugh.
> 

Are there collections of those, or similar images, on the web?
Bet you show those images as part of first lecture. Why?
1. It's an interest grabber.
2. It provides something for student to hang hat on as he proceeds with 
further study.




> Chris
> =======================
> Chris Bore
> www.bores.com
> 
> 
> 
>>- Show quoted text -
> 
> 

On 2 Feb, 16:34, Richard Owlett <rowl...@atlascomm.net> wrote:
> Rune Allnor wrote:
> > On 2 Feb, 15:47, Richard Owlett <rowl...@atlascomm.net> wrote:
>
> Restoring snipped portion of my post ;)
>
> &#4294967295;>>
> &#4294967295;>> I'm another that has no feel for a 2D Fourier Transform (discrete OR
> &#4294967295;>> continuous). In the "1D" case we can build on a demonstration of how
> &#4294967295;>> only odd harmonics of a sine wave can be added to approach a square
> &#4294967295;>> wave. Is there a similar demo for the "2D" case?
> &#4294967295; [end restoration]
>
>
>
> >>For example I have a gut feeling that a 2D transform of elevation data
> >>in the region of the San Andreas Fault or the Great Rift Valley would
> >>show a prominent feature. But what vector space would it be in?
>
> > The vector space would be the space of MxN arrays, where M and N
> > are the dimensions of the image. But don't go there.
>
> Thank you. *THANK YOU* ;)
>
> > Instead,
> > try and build some intuition by playing with the 2D FFTs of
> > binary B&W images that contain simple shapes.
>
> > Rune
>
> Your suggestion would answer a different "Why" - "why/how does 2D FT work?"
> My question is more "why would you want to do a 2D transform?"

Why would you NOT want to do a 2D FFT? :-)

1) If your data are 2D.
  - The 2D FFT of an image may be used as a basis for compression,
    in a similar way to the use of the 1D FFT for compression of audio
in MPEG.
 - The 2D FFT of an image may be used to analyze or detect features
that are frequency-
   related such as edges, lines, fine and coarse textures, etc
 - the 2D (or 3D) data from an ultrasound scan may yield diagnostic
information
   that is related to spatial frequency, phase etc
2) If your data are the 2D FFT of something you wish to reconstruct
 - the 2D FFT of the RF data from an MRI scanner, is an image of the
tissue water content
 - the image projected by a lens in its focal plane, of an object
illuminated by coherent light
  that is in the other focal plane, is the 2D FFT of the illuminated
object
3) For fun (the real reason..)
 - what does the 2D FFT

>
> I don't have any application, _that I *know* of_ , for a 2D transform.
> But I see it regularly discussed by people with a "signals" orientation.
> I have an interest in one class of signals (speech). My question might
> be phrased "what gain would I have for effort invested in studying 2D
> transforms?" I could investigate the Carnot cycle, but would it improve
> my driving?

4) If your data are speech signals
 - if your data are speech, and you divide these into frames, then you
can apply 2D FFT
   to analyse this as a 2D set of data, which has been used for speech
enhancement as
  well as for analysis and recognition

Chris
==============
Chris Bore
www.bores.com

On 2 Feb, 16:42, Richard Owlett <rowl...@atlascomm.net> wrote:
> Chris Bore wrote:
> > On 2 Feb, 14:47, Richard Owlett <rowl...@atlascomm.net> wrote:
>
> >>illywhacker wrote:
>
> >>>On Feb 2, 11:04 am, "cherriegeller" <cherrie.gel...@gmail.com> wrote:
>
> >>>>Could someone please explain the concept of 2D FFT in more layman terms?
> >>>>Most if not all the resources i read about 2D FT for image processing are
> >>>>loaded with lots of mathematical formulaes which I believe are important,
> >>>>but have problems understanding. I just want a basic conceptual idea about
> >>>>the technique before using some freeware to compute the 2D FT of a brain
> >>>>image.
>
> > A 2D FFT is a way of making any 2D map by adding together 'egg boxes'
> > whose egg cells are sine shaped and that have varying widths
> > (frequencies) in each dimension. Strictly speaking these egg boxes are
> > formed by making images that have sinsusoidal variations at a single
> > frequency in each dimension - each basis image has just one horizontal
> > and one vertical frequency. They look like egg boxes, which is why I
> > call them egg boxes. You might call them 'textures'.
>
> > This is all there is to it.
>
> > If you apply a 2D FFT to a brain scan image that was created by MRI, I
> > think you will end up with the raw RF data from the MRI machine,
> > because at least when I worked on it 25 years ago..) the image is just
> > the 2D FFT of the data.
>
> >>>Why don't you start with the 1D FFT? Do you understand that? Or, to
> >>>paraphrase an old joke, first understand the FFT in N dimensions, and
> >>>then set N = 2.
>
> >>>illywhacker;
>
> >>I'm another that has no feel for a 2D Fourier Transform (discrete OR
> >>continuous). In the "1D" case we can build on a demonstration of how
> >>only odd harmonics of a sine wave can be added to approach a square
> >>wave. Is there a similar demo for the "2D" case?
>
> > Yes. You can generate mutiple images, each of which is modulated by a
> > sine wave of single frequency in each dimension. Sine waves in the
> > horizontal direction are 'horizontal' spatial frequencies, in the
> > vertical direction are 'vertical' spatial frequencies. Each such image
> > is one function from the basis set - call it (m,n) where m and n are
> > the horizontal and vertical spatial frequencies (say, expressed as
> > number of cycles across the whole image). For instance (4,0) would be
> > like ripples, four of them across the horizontal direction. (4,4) is a
> > mesh (I call it an egg box). And so on. You can add together many of
> > these to form any image. I do this with a simple image that is a 2D
> > square wave - a bright square in top left quadrant, black elsewhere.
> > You just add the odd harmonics but in two dimensions, to build up the
> > image. It doesn't work as well as a 1D square wave because we look at
> > an intensity map but it does well enough.
>
> >>For example I have a gut feeling that a 2D transform of elevation data
> >>in the region of the San Andreas Fault or the Great Rift Valley would
> >>show a prominent feature. But what vector space would it be in?- Hide quoted text -
>
> > I do something like this in a class I run on image processing. The 2D
> > FFT of a relief map of Marin County is quite simple. The fault is a
> > diagonal feature running from top left to bottom right on the map, and
> > its 2D FFT shows a prominent diagonal line running from bottom left to
> > top right - which is typical for linear features. The valleys that run
> > into the fault valley tend also to be doagonals, at an angle to the
> > main one, and they show up as a weaker diagonal feature in the 2D FFT.
> > It is not all that informative, to be honest. :-) I use the Marin
> > County relief map mainly to show the concept of an image as a 2D map
> > of some value, we just do the 2D FFT for a laugh.
>
> Are there collections of those, or similar images, on the web?

Not that I know of. I generate my own, it is not hard to do.

There are some examples though - for instance here:

http://www.cs.unm.edu/~brayer/vision/fourier.html

> Bet you show those images as part of first lecture. Why?
> 1. It's an interest grabber.
> 2. It provides something for student to hang hat on as he proceeds with
> further study.

Not quite the first :-). But early on. I always teach in a way that
depends on powerful visual or auditory images. I hate equations and
formulae unless I can show some physically reasonable visualization of
what they mean. It drives some of my colleagues wild, because they can
'see' from the formulae alone, whereas I am just a poor dumb slow
person who has to grope my way towards enlightenment using models and
analogies drawn from the world around me.

Three other reasons to show such images early:

1) It demystifies. The 2D FFT simply asserts that from this collection
of simplified images, I can construct any image I like through simple
addition. Now we can go on to derive formulae to express this.

2) It shows how bad an idea this is. Anything further from a 'real'
image than a 2D FFT basis function is hard to imagine.

3) Progressing from (2), why do we do it? because we dont know any
math to handle real images, so we decompose them into simple but
unrealistic components that we do know how to handle - sine waves.

Mind you, many people disagree with me on this approach and call it
dumbing down.

Chris
====================
Chris Bore
www.bores.com
>
>
>
> > Chris
> > =======================
> > Chris Bore
> >www.bores.com
>
> >>- Show quoted text -- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

On 2 Feb, 17:34, Richard Owlett <rowl...@atlascomm.net> wrote:
> Rune Allnor wrote:

> > Instead,
> > try and build some intuition by playing with the 2D FFTs of
> > binary B&W images that contain simple shapes.
>
> > Rune
>
> Your suggestion would answer a different "Why" - "why/how does 2D FT work?"
> My question is more "why would you want to do a 2D transform?"

The usual stuff: Filtering, compression, processing... but with
images or other 2D signals.

> I don't have any application, _that I *know* of_ , for a 2D transform.
> But I see it regularly discussed by people with a "signals" orientation.
> I have an interest in one class of signals (speech). My question might
> be phrased "what gain would I have for effort invested in studying 2D
> transforms?"

None, that I can see, with the speech processing. But then,
I don't know much about speech processing so I might be wrong.
Chris already mentioned *the* important reason why you would
want to research the 2D DFT: For fun.

Rune