Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

nautil.us

Post reply on HN
Print view View original

61–70 of 105 posts

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#61

Post by nilkn »

jjoonathan wrote: post #53
nilkn wrote: post #24

> You could just tell them a handful of numbers—the sizes of the different circles in the picture above. Maybe I'm crazy and just missing something, but this feels a little too good to be true. This would put the set of smooth curves in 1-1 correspondence with the set of finite sets (since each curve is being specified completely by a finite set of numbers). But the set of finite sets is countably infinite since it's…

First of all, there are four kinds of "Fourier transforms" in common use, so the cardinality problem that you have observed cannot really be discussed until we pick one to talk about. For instance, the FT maps uncountable to uncountable and the DFT maps finite to finite (and can be understood with intro Linear Algebra as a change of basis). The things we are calling countable and uncountable are actually dimensionali…

> Fourier Series only guarantee reproduction (take the transform and then take the inverse to get the reproduced curve) up to the L2 norm

This completely resolved the confusion. Thanks very much for typing this up.

This is one of those details which is probably pretty unimportant for the lay reader, but for someone with some mathematical training (outside of this specific domain) its omission threw a big red flag for me.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#62

Post by michaelochurch »

jjoonathan wrote: post #53
nilkn wrote: post #24

> You could just tell them a handful of numbers—the sizes of the different circles in the picture above. Maybe I'm crazy and just missing something, but this feels a little too good to be true. This would put the set of smooth curves in 1-1 correspondence with the set of finite sets (since each curve is being specified completely by a finite set of numbers). But the set of finite sets is countably infinite since it's…

First of all, there are four kinds of "Fourier transforms" in common use, so the cardinality problem that you have observed cannot really be discussed until we pick one to talk about. For instance, the FT maps uncountable to uncountable and the DFT maps finite to finite (and can be understood with intro Linear Algebra as a change of basis). The things we are calling countable and uncountable are actually dimensionali…

I wish I could give this post 5 upvotes.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#63

Post by sillysaurus2 »

tobr wrote: post #19
sp332 wrote: post #14

Earlier quoted context omitted.

Oh, so your brain can still mostly recreate the shape even with no low frequencies!

Depends on how far away from the image you are, or how big it is. By taking the low frequency from one image, and the high frequency from another, you can get some interesting results. Take a look at this image, first sitting near the screen, then step away a couple of meters. http://cvcl.mit.edu/GroupFaceHybrid.jpg

Holy wow. That's freakin' awesome!

Open that image in a new tab, then hold down CTRL and scroll up/down to zoom in and out. When you zoom out to 25%, each of them switches from smiling to frowning or vice versa. The lady on the right is clearly smiling at 25% zoom. I had no idea that was possible.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#64

Post by ppruitt »

data-cat wrote: post #42

This article was interesting but didn't really tell me anything I don't already know. Does anyone know where I can find a good article that actually explains the mathematics of performing a Fourier transformation? I thought that is what this article was going to be about.

I found the book, "Who Is Fourier?: A Mathematical Adventure" to be an intuitive explanation of the Fourier Series and transform: http://amzn.com/0964350432

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#65

Post by Guillaume86 »

quasque wrote: post #60

ImageMagick has a nice tutorial on the use of Fourier transforms in image processing, if you want to get a more intuitive feel on the subject: http://www.imagemagick.org/Usage/fourier/

Really interesting, thanks!

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#66

Post by zwieback »

dnautics wrote: post #39
zwieback wrote: post #37

It's interesting to note that Fourier wasn't trying to any of the things that the Fourier Transform is commonly used for today, namely signal processing. He was trying to solve heat transfer equations when he came up with the Fourier series. I'm not even sure if he was that interested in the Transform as such, e.g. looking at a signal in frequency space and then efficiently applying filters before transforming back t…

when it first came out most people ridiculed it for being a mere intellectual curiosity. I would characterize the fourier transform (especially the DFT) as the single most important mathematical innovation that enables the interface between the digital and analog world.

I agree although there's a continuum from Fourier to Cooley-Tukey and so on so it's hard to pinpoint which part is the most important.

Also, maybe it's more beloved by engineers (like myself) than mathematicians.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#67

Post by ZoFreX »

aliston wrote: post #4

This 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…

I'm an audiophile, and I can tell you from looking at the FFT which settings you used in LAME to make that MP3* :)

Different presets set different lowpass filter values, opting for the best balance between preserving frequencies, achieving a small file size, and the perceived quality. The latter is often measured with various approximations to human perception of sound - psychoacoustics. This is why you can't compare different encoders using an approximation - the algorithms themselves are made using them. It's the Dunning-Kruger effect, but for computers.

You can actually change those presets, so you can hear for yourself what effects changing it has: http://lame.cvs.sourceforge.net/viewvc/lame/lame/USAGE

* Why would anyone bother to learn this skill? Well, I don't mind MP3s (or AACs or OGGs for that matter), and I certainly can't tell the difference between them and lossless formats, but an MP3 that has been re-encoded several times is really atrocious. It's like when you re-compress a jpg a few times, it gets messy. This helps definitively figure out what an MP3 really is or was. Sometimes the tags on the MP3 lie about which encoder was used or what the compression settings were. Other times, the file used to be something else, such as re-encoding a 128kbps MP3 as a LAME V0 preset MP3. Looking at the frequency plot in a sound editor makes this rather obvious, as the lower presets and crummier encoders have much lower lowpass filters.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#68

Post by arb99 »

I find this kind of stuff fascinating.

Are there any decent books (kindle or proper books) with this kind of content? I've got no background in Maths (other than some (UK) A-level maths at school), but always love reading these sort of posts.

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#69

Post by doctoboggan »

If you are interested in audio fingerprinting using the FFT check out my IPython notebook that explores this idea in more detail. I used a spectrogram and image processing tools to identify what a given audio sample is. You should be able to download the notebook and run all the examples.

http://jack.minardi.org/software/computational-synesthesia/

Re: Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

#70

Post by GrantS »

thearn4 wrote: post #49

Another cool thing is that orthonormal bases are not unique - there are many other basis functions that you can choose beyond just sine and cosine to decompose a function (or digital signal). Though they are a natural choice if you are specifically looking to analyze periodicities. One direction to go in for further study: https://en.wikipedia.org/wiki/Wavelet

Yes! Same goes for pulling eigenvectors out of a data set e.g. for PCA (Principal Components Analysis) -- those form an orthonormal basis. You can even pick a set of random orthogonal vectors of the same number and dimension as your original data and re-represent the data with no loss of information.

I had a lot of fun demonstrating this concept for reconstructing images via a Processing sketch a few years ago and still use it for teaching from time to time. All source code for quick and dirty Haar, Eigen, Random, and Fourier-like methods included here: http://www.cc.gatech.edu/~phlosoft/transforms/

Post reply on HN