website articles
fourier series

Motivation


I was introduced to the Fourier transform and series at the age of 19, and the first thing I thought was, "hey, this can be used for the 3d camera movements in my demos". Originally I was more into regular demomaking instead of procedural generation and compression, so at that time I wanted to use the new toy of Fourier for key frame interpolation. My teacher didn't show much interest about the topic of interpolation, but anyway I did some experiments at home. In fact I programmed it, but never used it in the end cause splines were the wave at the time... Well, now that data compression is an interesting challenge, I though on revisiting the concept, just to have a second contact with it so I can better estimate if it is worth the effort to develop something around this technique in the context of demo coding.



The maths


You might remember from algebra courses the folowing idea: take a vector (or function or signal) f, and a set of axes (or "coordinate system" or "basis"), and rewrite f as a linear combinartion of those axes such that



where the values are called the "coordinates" of the vector f in the new system.

We could choose any coordinate system (Legendre polynomials or simple powers like in Taylor series, you name it). Instead, we take care to choose our axes such that they are orthogonal to each other. Also, we seek for a coordinate system where axes have more and more detail as n increases. There is in fact a very popular coordinate system that fulfills these requirements: the trigonometric family of functions (ie, sinus and cosinus series, that I will write as complex exponentials for a more compact representation) given by



These are the Fourier series (that you probably now already, like many of their cousins - DFT, DCT, Spherical Harmonics, Laplace, etc). Every axis is perpendicular to each other as can be manually checked by dot producting any two of the axes:

Now, to get the coordinates (called "Fourier Coefficients" when using the basis), we just have to do:

, and since we our axes are perpendicular to each other, then we can say

So, computing the coordintes of f is as simple as doing a dot product between the vector and the axes of the new coordinate system (well, their conjugate if they are complex). Just as in regular geometric vector spaces (ie, we are just aplying a rotation matrix to our vector f).



The concept


Memory refreshed? Ok, let's go on.

Now, by rotating the vector f by the matrix we have transformed it's representation, ie, now it's what we have to store in our demo, not f anymore. As we said, the higher order axes represent the detail structure of f, while the global structure of f gets mostly projected into the lower order axes. Assuming f will represent real world data, like camera movements or shapes, it will probably be quite ok if we only pay attention to its global shape, and we discard the rest of the information (for efficient storage and compression purposes). That means we only need to store few of the coordinates . That's what Jpeg images or Mp3 music do, so it should work for our camera paths too.


The experiments


So I quickly coded a proof of concept. I generated a random two dimensional set of 50 points. Then I computed two Fourier series, one for the x coordinate and another for the y. Each of the Fourier series gives 50 coefficients of course. When using all of them to reconstruct a signal the resulting path exactly passes thru the 50 points. Perfect! that's a good way to do camera interpolation (think of the 50 points as key frames).

Next the experiment was to start removing coefficients and see what happens. This in an image using 80% of the coefficients (40):



and this is what happens when you use 20% of the data (10 coefficients):




Results are not as bad as you could expect, because even the full set of 50 coefficients is very easily compressible, much more than the original description of f. For example, since we know that the last coordinates are going to be smaller than the first, you can actually use less bits for those. Well, there many such tricks, just have a look to the JPEG specification for more inspiration.