Chris Bore wrote:> 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.Here's an example of the DCT basis, halfway down: http://www.cs.cf.ac.uk/Dave/Multimedia/node231.html The DFT basis adds similar combinations with spatial sine waves. Martin -- Quidquid latine scriptum est, altum videtur.
2D FFT
Started by ●February 2, 2009
Reply by ●February 2, 20092009-02-02
Reply by ●February 2, 20092009-02-02
Richard Owlett <rowlett@atlascomm.net> wrote:> Rune Allnor wrote: >> On 2 Feb, 15:47, Richard Owlett <rowl...@atlascomm.net> wrote:(snip)>>>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.The first thing to know is that in rectangular coordinates the FFT is separable. You take the FFT of all the rows, then all the columns, or the other way around, and get the same result: the 2D FFT of the data. In 1D we know that, for example, f(x)=sin(3x) one the solution for the amplitude of vibration for a violin string as a function of position on the string. In equation form, consider f(x,y)=sin(3x)sin(3y), a function with frequency 3 in x and y. Using the sine addition angle identities in reverse, sin(3x)sin(3y)=(cos(3x-3y)-cos(3x+3y))/2 (Consider it over the range 0 to 1 for both x and y, the frequencies being 3 radians/unit length in x and y.) The solution is the sum (difference) of two cosine waves, one going in the (x+y) direction, the other in the (x-y) direction. In electrical terms, they are standing waves in two dimensions. (The frequency in (x+y) and (x-y) directions is 3/sqrt(2)). Among others, sin(Ax)sin(By) are the solutions to the vibrating modes of a square drum head with uniform tension. (Circular drum heads require Bessel functions for the modes.) In electrical terms, they are the solutions for the current in a square plate, going to zero at the boundary.> 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.> 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?"They come up often in optics. One of my favorite optics lab experiments generates 2D fourier transforms using lenses: Start with a uniform monochromatic light source and illuminate a transparent object. (A black and white slide, for example, or a piece of metal with holes cut out of it.) After the light goes through the object place a lens of focal length f. Put an image sensor (TV camera with lens removed) a distance f from the lens. The image will be the 2D fourier transform of the object. If you rotate the object the transform will rotate the same way. In the same way that you need higher frequencies to resolve waveforms with sharp transitions, you need larger lenses to resolve higher spatial frequencies (in addition to collecting more light).> 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?As far as I know, speech signals are 1D. Studying optics might improve your driving, though, if you can't see very well. -- glen
Reply by ●February 2, 20092009-02-02
glen herrmannsfeldt wrote:> Richard Owlett <rowlett@atlascomm.net> wrote: >> Rune Allnor wrote: >>> On 2 Feb, 15:47, Richard Owlett <rowl...@atlascomm.net> wrote: > (snip) > >>>> 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. > > The first thing to know is that in rectangular coordinates > the FFT is separable. You take the FFT of all the rows, then > all the columns, or the other way around, and get the same result: > the 2D FFT of the data. > > In 1D we know that, for example, f(x)=sin(3x) one the solution > for the amplitude of vibration for a violin string as a function > of position on the string. > > In equation form, consider f(x,y)=sin(3x)sin(3y), a function > with frequency 3 in x and y. Using the sine addition angle > identities in reverse, sin(3x)sin(3y)=(cos(3x-3y)-cos(3x+3y))/2 > (Consider it over the range 0 to 1 for both x and y, the > frequencies being 3 radians/unit length in x and y.) > > The solution is the sum (difference) of two cosine waves, one going in > the (x+y) direction, the other in the (x-y) direction. > In electrical terms, they are standing waves in two dimensions. > (The frequency in (x+y) and (x-y) directions is 3/sqrt(2)). > > Among others, sin(Ax)sin(By) are the solutions to the vibrating > modes of a square drum head with uniform tension. (Circular > drum heads require Bessel functions for the modes.) > > In electrical terms, they are the solutions for the current > in a square plate, going to zero at the boundary. > >> 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. > >> 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?" > > They come up often in optics. One of my favorite optics lab > experiments generates 2D fourier transforms using lenses: > > Start with a uniform monochromatic light source and illuminate > a transparent object. (A black and white slide, for example, or > a piece of metal with holes cut out of it.) After the light goes > through the object place a lens of focal length f. Put an image > sensor (TV camera with lens removed) a distance f from the lens. > The image will be the 2D fourier transform of the object. > > If you rotate the object the transform will rotate the same way. > > In the same way that you need higher frequencies to resolve waveforms > with sharp transitions, you need larger lenses to resolve higher > spatial frequencies (in addition to collecting more light).The first side-looking radars created images with transforms produced by lenses, including a conical lens to spread the narrow vertical angle to the broad horizontal image plane.>> 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? > > As far as I know, speech signals are 1D. Studying optics > might improve your driving, though, if you can't see very well.:-) Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●February 2, 20092009-02-02
>On Feb 2, 11:04=A0am, "cherriegeller" <cherrie.gel...@gmail.com> wrote: >> Could someone please explain the concept of 2D FFT in more laymanterms?>> Most if not all the resources i read about 2D FT for image processingare>> loaded with lots of mathematical formulaes which I believe areimportant,>> but have problems understanding. I just want a basic conceptual ideaabou=>t >> the technique before using some freeware to compute the 2D FT of abrain>> 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 =3D 2. > >illywhacker; >The only thing i know about 1D FFT is that I can "express" any time series into a linear combination of sine and cosine components. I roughly know the formulae but mainly uses software like Matlab to do it for me. What i find difficult is to visualise the results of a 2D FT on an image? For example, the site which Chris Bore sent, there are quite a few images showing results of 2D FT, which i just cannot fathom. For 1D FFT, it is very clear if i plot the spectrum i can see spikes appearing at particular frequencies whose component contribute to the timecourse. I can seem to do the same for 2D FT ... is a 2D FT simply 2 1D FTs put together, say 1 in a vertical and 1 in the horizontal direction? Sorry if this is too simple or naive question but i really want to understand this concept. Thanks for all your help.
Reply by ●February 3, 20092009-02-03
cherriegeller <cherrie.geller@gmail.com> wrote:> The only thing i know about 1D FFT is that I can "express" any time series > into a linear combination of sine and cosine components. I roughly know the > formulae but mainly uses software like Matlab to do it for me.> What i find difficult is to visualise the results of a 2D FT on an image?Index a 2D array from 0 to N-1 in each dimension. (It doesn't have to be square, but it is easier to explain that way.) The x and y indecies are the spatial frequency in the x and y direction. The basis functions are then f(x,y)=exp(i*kx*x)*exp(i*ky*y) where kx and ky are the x and y spatial frequencies. f(0,0) is the DC or constant term, f(1,0) the lowest x direction mode, f(0,1) the lowest y mode. (Assuming the discrete case, or the frequency 1 continuous case.) f(x,y)=exp(i*kx*x+i*ky*y) (exponential identity) f11(x,y)=exp(i*1*(x+y)) frequency sqrt(2) in the (x+y) direction. (I think in my previous post I had 1/sqrt(2), but it goes through two cycles over the distance sqrt(2).) So, those are the basis functions, or the corresponding combinations of sin and cosine. Multiply by the amplitude and add them up.> For example, the site which Chris Bore sent, there are quite a few images > showing results of 2D FT, which i just cannot fathom. For 1D FFT, it is > very clear if i plot the spectrum i can see spikes appearing at particular > frequencies whose component contribute to the timecourse. I can seem to do > the same for 2D FT ... is a 2D FT simply 2 1D FTs put together, say 1 in a > vertical and 1 in the horizontal direction?Yes, in rectangular coordinates.> Sorry if this is too simple or naive question but i really want to > understand this concept. Thanks for all your help.-- glen
Reply by ●February 3, 20092009-02-03
On 2 Feb, 18:06, Chris Bore <chris.b...@gmail.com> wrote:> I always teach in a way that > depends on powerful visual or auditory images.'Infotainment.' A very dangerous method. In recent years I have started seeing on TV the movies and visualizations I made in my mind decades ago, when I read the books on geology and astronomy as a kid. As far as I am concerned, the insight lies not in seeing the end visualization, but in interpreting and contemplating the material you read, to get there.> 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.Well, I might not have phrased it quite like that, but I have to agree with your colleagues. Learning to 'see' from an equation is not something that comes for free. It takes hard work over long time to learn. Students need to understand that, and get to work on it. While you personally might have found your preferred way of coping with maths, be aware that you set the stage for your students as well. It is a general rule in teaching that very few students can reach beyond the level of their teacher. Those very few who can, can only reach a limited distance beyond. So the infortainment shows might give a short-term illusion of progress, but it undermines the long- term results one usually strives for. ....> Mind you, many people disagree with me on this approach and call it > dumbing down.Me among them. Most, if not all, of the semantics wars on comp.dsp are based in this general inability to comprehend or discuss abstract concepts. Rune
Reply by ●February 3, 20092009-02-03
On Feb 3, 6:44�am, Rune Allnor <all...@tele.ntnu.no> wrote:> On 2 Feb, 18:06, Chris Bore <chris.b...@gmail.com> wrote: > > > I always teach in a way that > > depends on powerful visual or auditory images. > > 'Infotainment.' A very dangerous method. In recent years I have > started seeing on TV the movies and visualizations I made in my > mind decades ago, when I read the books on geology and astronomy > as a kid.Yeah, that's what they say. :-) But here is a question. Why would you avoid the use of images, analogies, models and visualizations, when so many people do find them helpful? To take your geology example, if I read about volcanoes I can visualize for myself what one looks like and how it works, but why would it be wrong for someone to show me a picture of one, or an animation of the geolgic forces working on it?> As far as I am concerned, the insight lies not in seeing the end > visualization, but in interpreting and contemplating the material > you read, to get there. > > > 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. > > Well, I might not have phrased it quite like that, but I have to > agree with your colleagues. Learning to 'see' from an equation > is not something that comes for free. It takes hard work over > long time to learn. Students need to understand that, and get > to work on it.I'm lucky in that my 'students' are not in academia, but usually practising engineers who did learn the 'right' way but without understanding it. So they tend to be grateful for my dumbed down approach that at least enables them to do their work. :-) So in a way you could say I benefit from all the work that was put into them in the 'right' way even though it never helped them in any practical way. The other problem I do see with understanding through equations is, they fail to see the limitations. For example some visualizations of the basis functions for a 2D FT can help you to see easily how they are poor models for certain types of 2D data, and how limitations imposed by doing discrete math can change what you are seeing. Some of these things may be quite hard to see so readily from the equations, and so the equations may be over-relied upon. that is, the equations can tend to be taken as the 'right' model with the real world coming in a poor second. This is how, for example, we get such lousy digital cameras because nobody seems to realise that a great big blob of light- sensitive silicon is not a Dirac delta function.> While you personally might have found your preferred way of coping > with maths, be aware that you set the stage for your students as > well. > It is a general rule in teaching that very few students can reach > beyond the level of their teacher. Those very few who can, can only > reach a limited distance beyond. So the infortainment shows might > give a short-term illusion of progress, but it undermines the long- > term results one usually strives for.Now here I disagree totally. Not about infotainment but about excelling beyond the teacher. Most of my students go well beyond what I teach them, and that is the whole point. I know so little, what would be the value in teaching them even less? And I am well impressed by the ability of most engineers of all kinds to take what is taught to them, question and internalise it, and then to go way beyond what the teacher may ever have thought.> .... > > > Mind you, many people disagree with me on this approach and call it > > dumbing down. > > Me among them. Most, if not all, of the semantics wars on comp.dsp > are based in this general inability to comprehend or discuss > abstract concepts.Yes, I'd say in fact that MOST people disagree with me. Except for the students. :-) And the people who pay me to teach them. :-)> Rune
Reply by ●February 3, 20092009-02-03
On 3 Feb, 19:00, Chris Bore <chris.b...@gmail.com> wrote:> On Feb 3, 6:44�am, Rune Allnor <all...@tele.ntnu.no> wrote: > > > On 2 Feb, 18:06, Chris Bore <chris.b...@gmail.com> wrote: > > > > I always teach in a way that > > > depends on powerful visual or auditory images. > > > 'Infotainment.' A very dangerous method. In recent years I have > > started seeing on TV the movies and visualizations I made in my > > mind decades ago, when I read the books on geology and astronomy > > as a kid. > > Yeah, that's what they say. :-) > > But here is a question. Why would you avoid the use of images, > analogies, models and visualizations, when so many people do find them > helpful? To take your geology example, if I read about volcanoes I can > visualize for myself what one looks like and how it works, but why > would it be wrong for someone to show me a picture of one, or an > animation of the geolgic forces working on it?They are helpful as long as they don't dominate. The problem occurs if the students are releaved of the work of imagining what goes on.> > As far as I am concerned, the insight lies not in seeing the end > > visualization, but in interpreting and contemplating the material > > you read, to get there. > > > > 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. > > > Well, I might not have phrased it quite like that, but I have to > > agree with your colleagues. Learning to 'see' from an equation > > is not something that comes for free. It takes hard work over > > long time to learn. Students need to understand that, and get > > to work on it. > > I'm lucky in that my 'students' are not in academia, but usually > practising engineers who did learn the 'right' way but without > understanding it. So they tend to be grateful for my dumbed down > approach that at least enables them to do their work. :-) So in a way > you could say I benefit from all the work that was put into them in > the 'right' way even though it never helped them in any practical way.OK. As long as that premise is fully understood by the students. And you are clear with them that what you tell them is an (over) simplification of the maths.> The other problem I do see with understanding through equations is, > they fail to see the limitations. For example some visualizations of > the basis functions for a 2D FT can help you to see easily how they > are poor models for certain types of 2D data, and how limitations > imposed by doing discrete math can change what you are seeing. Some of > these things may be quite hard to see so readily from the equations, > and so the equations may be over-relied upon. that is, the equations > can tend to be taken as the 'right' model with the real world coming > in a poor second. This is how, for example, we get such lousy digital > cameras because nobody seems to realise that a great big blob of light- > sensitive silicon is not a Dirac delta function.That's a direct consequence of the negligence of maths teaching in practical DSP an negligence of practical experience in academia: The practitioners don't understand the maths, and can neither understand nor criticize it, since they lack the training. The academics don't understand the problems caused by idealizations and simplifications of the models.> > While you personally might have found your preferred way of coping > > with maths, be aware that you set the stage for your students as > > well. > > It is a general rule in teaching that very few students can reach > > beyond the level of their teacher. Those very few who can, can only > > reach a limited distance beyond. So the infortainment shows might > > give a short-term illusion of progress, but it undermines the long- > > term results one usually strives for. > > Now here I disagree totally. Not about infotainment but about > excelling beyond the teacher. Most of my students go well beyond what > I teach them, and that is the whole point. I know so little, what > would be the value in teaching them even less? And I am well impressed > by the ability of most engineers of all kinds to take what is taught > to them, question and internalise it, and then to go way beyond what > the teacher may ever have thought.I see the limitations, and have done for years. There aren't many practitioners out there who have the combination of academic and practical experience I have. Few academics have worked with data; few practitioners have studied the maths etc. I hit the wall when people insist on 'physical' or 'intuitive' explanations for the maths. This is caused solely by lack of training, and is *the* main obstacle that prevents DSP from progressing forward and not un around in circles as it is tending to, these days.> > .... > > > > Mind you, many people disagree with me on this approach and call it > > > dumbing down. > > > Me among them. Most, if not all, of the semantics wars on comp.dsp > > are based in this general inability to comprehend or discuss > > abstract concepts. > > Yes, I'd say in fact that MOST people disagree with me. Except for the > students. :-) And the people who pay me to teach them. :-)Maybe you should have a word with the people who pay your students to work for them, after they leave you... Rune
Reply by ●February 3, 20092009-02-03
Rune Allnor <allnor@tele.ntnu.no> wrote: (snip, someone wrote)>> But here is a question. Why would you avoid the use of images, >> analogies, models and visualizations, when so many people do find them >> helpful?(snip)> They are helpful as long as they don't dominate. The problem > occurs if the students are releaved of the work of imagining > what goes on.(snip)> OK. As long as that premise is fully understood by the students. > And you are clear with them that what you tell them is an (over) > simplification of the maths.There is a comment in "The Feynman Lectures on Physics" about being asked what the E field in an EM wave really looks like. He has answers about how we can make diagrams, but we can't really explain what it really looks like. Even worse when trying for visual examples of quantum mechanics. (snip)> That's a direct consequence of the negligence of maths teaching > in practical DSP an negligence of practical experience in academia: > The practitioners don't understand the maths, and can neither > understand nor criticize it, since they lack the training. The > academics don't understand the problems caused by idealizations > and simplifications of the models.Well, there is another problem in that in most colleges math is taught by the math department, EE in the EE department and physics in the physics department. I suppose that makes sense, but it is hard on students when an idea from one is needed in the other. Commonly it is using differential equations in EE and physics. (snip)> I hit the wall when people insist on 'physical' or 'intuitive' > explanations for the maths. This is caused solely by lack of > training, and is *the* main obstacle that prevents DSP from > progressing forward and not un around in circles as it is > tending to, these days.I was watching the TV Game show "Are you smarter than a 5th grader?" (and you would be surprised sometimes), There was a question, with a diagram of a sine function and an arrow, with the question something like: "Which part of a sound wave is shown in the diagram: a) Crest b) Period c) Trough" I believe in this case the 5th grader got it right and the contestant wrong, but I think the question is wrong. Sound waves don't have crests and troughs, but sound wave diagrams do. If that isn't explained to the students then it seems that the visualization is worse than teaching without visualization. Among others, that they might believe sound is a transverse wave. (Not to mention that most 5th grade teachers probably don't understand it any better.) As for 2D Fourier transform, you can visualize the vibrational modes of a drum head. Use a rectangular one to avoid the degenerate modes, vibrate it with a speaker and audio oscillator, and put some powder on the head: you can visualize the nodes of the vibrational modes as you change the frequency. -- glen
Reply by ●February 3, 20092009-02-03
glen herrmannsfeldt wrote: ...> Sound waves don't have crests and troughs, but sound wave > diagrams do. If that isn't explained to the students > then it seems that the visualization is worse than > teaching without visualization. Among others, that > they might believe sound is a transverse wave. > (Not to mention that most 5th grade teachers probably > don't understand it any better.)Sound a transverse wave? Surely not in air! ... Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
