Forums

2D FFT

Started by cherriegeller February 2, 2009
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&#2013266080;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 ;) > > &#2013266080;>> > &#2013266080;>> I'm another that has no feel for a 2D Fourier Transform (discrete OR > &#2013266080;>> continuous). In the "1D" case we can build on a demonstration of how > &#2013266080;>> only odd harmonics of a sine wave can be added to approach a square > &#2013266080;>> wave. Is there a similar demo for the "2D" case? > &#2013266080; [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