The word is 'interpolation'

date: 03 Oct, 2010, actionscript: 3 FP10, complexity: complexity level 4 of 5complexity level 4 of 5complexity level 4 of 5complexity level 4 of 5complexity level 4 of 5, feedback (votes): users score 4.97 of 5 (106 votes)users score 4.97 of 5 (106 votes)users score 4.97 of 5 (106 votes)users score 4.97 of 5 (106 votes)users score 4.97 of 5 (106 votes)

Hi, few days ago I've been digging into an old hard drive I have and, among some old dusty practices and experiments I found something really interesting I did a while ago. It is the whole conclusion of a research I did about Interpolation, algorithms and existing methods used for reconstructing missing data when scaling images, changing audio pitch, re-sampling, etc. And then I thought it could be useful for someone else and it might be worth to share it with the flash community rather than leave it there in my hard drive doing nothing. This hard drive is actually dying, it is about 8 years old and nowadays it is hard to read any data from it, many dead clusters, folders without a human names, files without sense, I don't even know anymore what is in it... but anyway, at least I could recovery all the required files for writing this article, here we are.

Interpolation

Before showing some examples about interpolation, I would like to explain a little bit what it does mean and why it is so important. Interpolation is a mathematic magic process; it consists in construct new data points within a range of known data points. There are some mathematic patterns (algorithms) for generating missing data between points; I've learned some of them when I was working in an application which required scaling, resizing bitmaps. I don't know if you have notice that when you resize an image through Actionscript It doesn't look as good as it looks when you do the same in Photoshop, Why? Because it needs to reconstruct the image missing data when you scale it, especially when you make it bigger than its original size and using interpolation methods could be a bit expensive in terms of CPU time. Flash player works with some different techniques to achieve similar results faster but it won't work as good as photo shop does, Flash player use a technique called mipmap which works fine (quite fast) and give us an acceptable quality especially when we scale an image to double of its size or the other way round, half of its size, middle terms not as good but still acceptable, it means that there are some limitations when we work with images which have odd dimensions. Anyway, carry on with interpolation… as I said, there are many different algorithms, the most common that I know are hermite, bicubic, cosine and linear. If you take a look in photo shop you will be able to see what photo shop uses for scaling images.

Adobe PhotoShop resize window

Bicubic interpolation

Well, as I mention before I was working in a project where my Actionscript module needs to resize images and keep them with the best quality possible after scaling, so I made an experiment using the bicubic algorithm to achieve that and at the end it worked quite good. Take a look on it in the swf below, load an image, change its size by dragging the bottom-right corner, interpolate it and then save it back and compare it with photo shop. Not too bad I think.

So, can you see the difference between the left image (non-interpolated) and the right image interpolated using Bicubic? Somehow, for some people it is the same normal TV and HD TV... :(

Image resized non-interpolated  Image resized Bicubic-interpolated

Yes of course, here is the source code of my Flash experiment. Take a look on it, I tried to make it the most simple possible, if you have any question just send me an email.

Some algorithms

Here is one interesting swf which contains some interpolation methods used in my experiments. I have extracted all of them from my programs and then I put them together in this graph where you can compare and see the differences between each other. It is really interesting, the reason why I did this research was because I was working in an audio application where I had to modify the pitch of a sound wave on the fly, I will explain this later on at the end of this article for now take a look on how it works. Imagine you have some points in a cartesian plane and then you changed the scale of it; say to 700% bigger of what it was before, so finding the new position of these dots is easy but what happen with the dots between? How the empty space (gap) between these points can be populated? Well, only through an interpolation process you can do that. The following swf shows some points already scaled and each pixel of the lines represent the missing data generated by these different interpolation algorithms.

Yes, here is the source code of it, it is quite simple.

Changing the sound wave pitch

Finally, here we are, we are going to see the hermite interpolation in action. This project is about a piano keyboard and in this practice I just load one of the keys (A4) and then I change the pitch of it for generating the rest of the keys on the fly, this is the principle of how synthesizers and samplers work, of course synthesizers are far more complicated than this. Let me tell you a bit more of it, in every musical instrument all the possible notes generated by it are in a specific wave frequency, that's what people call the tune and that's why we have tools such as: guitar tuners, metal sticks that generates noises in A440 frequency, etc. This is the way how you can synchronize multiple musical instruments and generated harmonic sounds. When I said A440, it actually means the key note A of all the notes; Do(C), Re(D), Mi(E), Fa(F), Sol(G),La(A), Si(B) and the 440 means the frequency of it in Hertz, the frequency specifies how many air pulses per second your sound system, speaker or headphones has to generate to reproduce that specific sound.

Now, my biggest question was, how to know the difference between La(A) and Do(C) or any other key note? And then with this I will know how much I need to stretch a sound wave based on A440 for generating the rest of the notes. Well the answer is quite simple; based on the note A (equal to note 0 in my experiment) I just use the following simple equation for generating higher notes. The new wave length is equal to Math.pow(0.5,(A+n)/12) and for notes that are lower the equation is Math.pow(2,(Math.abs(A-n)/12)). You may wonder what that number 12 is. It is actually the amount of notes you can find in a octave, for some crazy reason some notes have another notes in between called Sharps and Bemols. The full amount of notes in a octave is 1 Do(C), 2 Do#(C Sharp), 3 Re(D), 4 Re#(D Sharp), 5 Mi(E), 6 Fa(F), 7 Fa#(F Sharp), 8 Sol(G), 9 Sol#(G Sharp), 10 La(A), 11 La#(A Sharp), 12 Si (B). These sharps are those black keys you see in a piano keyboard. So, here is the .swf showing that everything I said is true, Lol!

The 13KB ActionScript piano keyboard

19 NOV 2010 - I have reduced the files size of the piano.swf from 80KB to 13KB by using MP3 compression.

Yeah, Yeah, here is the source code of it.

Well, I think it is all for now, feel free to contact me if you would like to clarify any doubts you have, see you!

Alex Nino - yoambulante.com

date: 29 Oct 2010 - 01:09:46, published by beneto
Nice!