If you would like a rigorous but equally enthusiastic and readable treatment of Fourier transforms, then you can't do better than the (free!) book The Scientist's and Engineer's Guide to Digital Signal Procesing: http://www.dspguide.com/
Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
71–80 of 105 posts
Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
#72If your into software and you don't know a out fourior transform, your not into software. this is something programmers without math will discover, along with Pythagorean theorem and basic trig. Otherwise, you are an over-hyped semantic duck-taper.
This needs to be upvoted rather than downvoted.
Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
#73The newer JPEG algorithm JPEG2000 uses Wavelet Transforms which is kind of similar to the Fourier. The Fourier applies a finite window then decomposes into a sum of infinite waveforms. The Wavelet on the other hand applies no windowing function, and directly decomposes the signal into a sum of _finite_ waveforms.
The Fourier has the disadvantage that you can't arrange the components into a time hierarchy; that is, no component occurs "before" any other.
The Wavelet transform _does_ have a natural time hierarchy. This makes it much better for streaming compression like voice calls.
The Fourier perfectly describes signals of infinite duration (think tone or color) while the Wavelet perfectly describes the position of things within a signal (think rhythm or space).
With the Fourier filtering is really easy. You can do hard, hard cutoffs -- literally no contributions within a certain frequency band -- just by removing components of the decomposition. Similarly, you can accurately apply any arbitrary mathematical filtering function.
The disadvantage of the Wavelet is that, well, the only meaningful transformation you can apply to it is compression -- dropping the shorter timescale components. If you want to filter, it's not enough to trim off timescale components because the wavelet itself can contain any frequency components. There's also nothing like a simple mathematical function you can apply to the coefficients to get a smooth filter.
Neat!
Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
#74This is a great post, but it's a little bit misleading when talking about MP3s and lossy compression and conflates analog fourier analysis with discrete analysis. When you're talking about a digital signal, it is the sample rate that determines the maximum frequency you can represent. It's not MP3s that "throw out the really high notes" -- it's any digital signal. A discrete fourier transform actually is lossless, bu…
Thanks for your feedback. Sure, any digital signal is by definition finite in its resolution (the sample rate or bits). I was trying to address the distinction between wave files of the type stored on audio CDs, and MP3s - both digital signals. I agree that the Fourier transform is in principle lossless, but it's particularly useful to use it in a lossy way, i.e. to throw out the least important (to us) components of…
For what it's worth, mp3s do not store the signal as a DFT. The frequency domain data is produced as a MDCT (modified discrete cosine transform). A DFT is performed during MP3 encoding, but it's used to apply the psychoacoustic model (which is much more complex than just throwing out high frequencies) to figure out how to layout the frequency bands in the MDCT. I don't believe JPEG uses a DFT at any point, just a DCT.
Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
#75There's a bit of a mischaracterization of the way 2 dimensional Fourier transforms operate on images in this post. The 2D DFT (or DCT rather) doesn't deal with anything as complex as tracing shapes on a 2D plane like seen in the video. What it does is treat each 1 dimensional line of the image as a signal/waveform, with the pixel intensity as amplitude. Fourier-family transforms are separable, so the 2D (and ND) case is equivalent to the transform of each line followed by a transform along the resulting columns. So the actual representation that arises from this looks like so, with each image representing the corresponding cosine component: http://0x09.net/img/dct32.png (here grey is 0)
Visually most of the sinusoidal components here are zero or nearly so. However if we scale them logarithmically, we'll see that it's actually not so: http://0x09.net/img/dct32log.png
What transform coders like JPEG do is reduce the precision of these components, causing many of them to become zero. Which is good for the entropy coder, and mostly imperceptible to us. Of course JPEG operates on 8x8 blocks only * rather than a whole image like here.
It's hard to imagine this as an image, so here's a progressive sum starting from the second term, which essentially demonstrates an inverse DCT: http://0x09.net/img/idct32.png
mind that 0 is adjusted to grey in this rendering, and the brightness of the result is not an artifact of the transform.
It's easier to understand what goes on with these transforms if you can visualize things in terms of the basis functions. Which in the case of a 32x32 image like above would be http://0x09.net/img/basis.png (warning: eye strain).
All the examples above pertain to the DCT, partly because of JPEG and partly so I could avoid getting phase involved, but the principles apply equally to the other transforms in the family.
* although recent versions of libjpeg can use other sizes
Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
#76I would love to know more about FT's, along with FFT's and how they help with for example signal processing or finding a signal when looking at a sample or multiple samples of a SDR. Are there any good books/papers/web articles on this topic that are accessible? I often find myself reading papers where some of the math goes over my head. Something with examples/code (code makes me understand math so much easier!) wou…
Richard Lyons - Understanding Digital Signal Processing
Focuses more on explaining the concepts behind the math than presenting a wall of theorems. Given that math is the language of DSP though, there's still a reasonable amount of math.
It assumes the reader has an EE or similar background, but I think it's still fairly approachable regardless. Given that my own background is in EE/embedded systems though, I'm not sure what my opinion counts for there.
Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
#77The Shazam algorithm -- I don't want to be all cynical and dumpy because it's not like I remember exactly how it works either (it's proprietary, after all... and even the explanation I was given was not definitive) but one of my Music Information Retrieval professors once described his anecdotal knowledge of it. It was based on some features derived from FFT for sure but didn't seemed very concerned with note identification, if at all. There are a ton of features that can be post-processed from FFTs that can't be equated to "pitch". Beware misleading analogies... the frequency domain (& quefrency, etc. etc.) is a difficult space to conceptualize.
And when you get into machine learning, some of the operations performed by neural networks and the like don't really represent super linear, human-understandable transformations. It's important to understand feature extraction, but more important in the grand scheme of these things is to understand how to dig data that is useful and how it can be used.
Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
#78If your into software and you don't know a out fourior transform, your not into software. this is something programmers without math will discover, along with Pythagorean theorem and basic trig. Otherwise, you are an over-hyped semantic duck-taper.
This needs to be upvoted rather than downvoted.
I disagree.
It's needlessly inflammatory and misspelt throughout. (Some people just have trouble spelling, and that's fair enough. But writing "a out" instead of "about" and not fixing it is just lazy and disrespectful to readers.
AsymetricCom would probably have got a different response had s/he written something like this instead:
"If you're really into software and want to be more than a semantic duck-taper, you need to know about Fourier transforms. Just like the Pythagorean theorem and basic trig, sooner or later you'll find you need it."
(Note 1. Although I have seen a whole lot of Fourier transforms in my time, I don't agree that you can't be truly "into software" without them. Note 2. It should probably be "duct tape" rather than "duck tape" but (a) the history is really complicated -- see [1] for some details -- and (b) I like the parallel with "duck typing"[2].)
[1] http://www.worldwidewords.org/qa/qa-duc4.htm
[2] If it walks like a duck and quacks like a duck, it is a duck. I think the term "duck typing" originated in the Python community, though Python's by no means the only language to have done a lot of things this way.
Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
#79I would love to know more about FT's, along with FFT's and how they help with for example signal processing or finding a signal when looking at a sample or multiple samples of a SDR. Are there any good books/papers/web articles on this topic that are accessible? I often find myself reading papers where some of the math goes over my head. Something with examples/code (code makes me understand math so much easier!) wou…
Richard Lyons - Understanding Digital Signal Processing Focuses more on explaining the concepts behind the math than presenting a wall of theorems. Given that math is the language of DSP though, there's still a reasonable amount of math. It assumes the reader has an EE or similar background, but I think it's still fairly approachable regardless. Given that my own background is in EE/embedded systems though, I'm not s…
I have taken classes in electrical engineering and embedded systems, so I am fairly familiar with them.
I will take a look at the book, thanks!
Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
#80The Shazam algorithm -- I don't want to be all cynical and dumpy because it's not like I remember exactly how it works either (it's proprietary, after all... and even the explanation I was given was not definitive) but one of my Music Information Retrieval professors once described his anecdotal knowledge of it. It was based on some features derived from FFT for sure but didn't seemed very concerned with note identif…
There is a paper [1] describing the algorithms used by Shazam.
[1] http://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf