December 20, 2012
Where to find me

As you probably have noticed, there is not much going on this blog anymore. Most of my activity is now happening on the various social outlets. So if you want to know what I'm up to you find my stuff here:

http://www.rebelmouse.com/quasimondo
http://twitter.com/quasimondo
http://www.flickr.com/photos/quasimondo
http://mario-klingemann.tumblr.com

Sometimes I'm adding new stuff to the Incubator:
http://incubator.quasimondo.com

Posted at 04:13 PM | Comments (0)
January 31, 2011
Fast Radial Blur

Given my track record of last year - a total of 4 blog posts - I do not have very high hopes that I'll do much better in 2011, but since I decided not to speak on any conferences this year I might have a little bit more time to share my experiments here instead of on stages only. I don't want to over-promise, but I hope that over the next weeks I'll find the time to finally explain and release the source codes for several projects that I have exclusively shown in my talks over the last years. Of course some of them have in the time since I've presented them been independently discovered by others, but I think I've still got a few aces in my pockets which are worth sharing.

I'll start with a simple visual effect: Radial Blur, which can give images the 200mph speed zoom look. In a naive approach you could achieve this effect by replacing every pixel with a weighted average of all neighboring pixels within the blur radius that lie on a line that goes through the center of zoom and the pixel itself. The problem with this method is that it is very slow since it would require many calculations to collect each neighbor and since the angle is different at every pixel there is not much room for other optimizations, like reusing already read pixels, which is key for every fast blur algorithm.

But using a neat trick that I remembered from my early Photoshop days allows to speed up this process a lot. Here is a demo:

The way this works is by converting the pixels from cartesian mapping (where the axes are x & y) to polar mapping (with axes angle & distance to the center) which arranges them in a way that all the neighbors that need to be averaged arrange themselves nicely in a straight line. This allows us to use a simple native Blur filter to quickly calculate the average. Depending if the blur is in x direction or y direction the final result will either be a Radial Blur (the well-known zoom effect) or a Circular Blur (which looks like a fast spinning wheel). The final step is to convert the pixels back from polar mapping to cartesian.

Open this link in a new window to see the process in a step by step demo.

By default the mapping uses the center of the image as the center of the polar coordinate system. This will result the center of the zoom to also be in the center of the image. So what if we want the zoom center to be at a different location? There are two ways of going about this - unfortunately I did not manage the faster way to work correctly yet which would be to simply use that center in the mapping algorithm. For some reason I have not found the right equations which work both ways. So for now I am using the slower method which does always work:

The trick here is to first make the image bigger by padding the borders so that the desired center of the zoom is temporarily the center of the image. So if you want the zoom center to be in the upper half of the image you add as many border pixels to the top that the chosen spot becomes the new vertical center. Then follows the cartesian-to-polar transform, the linar blur and the polar-to-cartesian mapping. The final step is to crop the image back to its original size by removing the previously added top pixels.

Another issue are artifacts that show due to the mapping. The problem is that since all the pixels that lie on a circle with a certain radius are mapped to a straight line, once the circumference of that circle gets bigger than the width of the mapped image pixel information gets lost. To fix this it is required to make the bitmap that holds the polar map as wide as the biggest possible circumference. Unfortunately that is not always possible since the temporary bitmaps could get pretty huge this way. The good news is that since we are blurring those artifacts will mostly not become too visible. Only for small blurs it improves the quality when using a bigger resolution for the cartesian image map.

You can find the source code for the RadialBlur class and the required pixel bender kernels as usual inside QuasimondoLibs

Posted at 07:45 PM | Comments (11)
May 24, 2010
Converting RGB to HSL differently

Sometimes when working with bitmaps you might find the need to work in a HSL (Hue, Saturation, Luminance) mode, for example when trying to detect skintones in an image. So what you do is probably to use the classic formula from Wikipedia that uses min/max and a whole lot of ifs: http://en.wikipedia.org/wiki/HSL_and_HSV

Well, here is a little alternative method: whilst working with the YUV colorspace I figured that since Y contains all the luminance information, the U + V channels must thus contain the hue and saturation. And it turns out that indeed when looking at u and v as the coordinates of a vector, its angle will represent the hue and its length will be the saturation.

So a formula that does not need any min/max and ifs to convert rgb to hsl looks like this:

// r,b and b are assumed to be in the range 0...1
luminance =  r * 0.299 + g * 0.587 + b * 0.114;
u = - r * 0.1471376975169300226 - g * 0.2888623024830699774 + b * 0.436;
v =   r * 0.615 - g * 0.514985734664764622 - b * 0.100014265335235378;
hue = atan( v, u );
saturation = Math.sqrt( u*u + v*v );

In this case hue will be between -Pi and Pi and saturation will be between 0 and 1/sqrt(2), so you might want to multiply the saturation by sqrt(2) to get it in a range between 0 and 1.

Of course this also works the other way round - hsl to rgb looks like this:

// hue is an angle in radians (-Pi...Pi)
// for saturation the range 0...1/sqrt(2) equals 0% ... 100%
// luminance is in the range 0...1
u = cos( hue ) * saturation;
v = sin( hue ) * saturation;
r =  luminance  + 1.139837398373983740  * v;
g = luminance  - 0.3946517043589703515  * u - 0.5805986066674976801 * v;
b = luminance + 2.03211091743119266 * u;

And here is a demo of a Pixel Bender kernel that allows you to adjust hue, saturation and brightness of a bitmap using this technique: HSL Adjust Demo, Source: hsladjust.zip

[Edit]As it was correctly noticed in the comments, the values that this method returns are not the HSL values that you get when you are using the classic formula. Nevertheless I think that this method has its uses, for example if you want to quickly create color schemes or if you are using it like in the demo to change the hue/saturation/Luminance of a photo.[/Edit]

[Edit]I updated the factors in the matrix one more time with values I found in the Wikipedia YUV discussion page. Those look better to me at least.[edit]

Posted at 02:21 PM | Comments (13)
January 14, 2010
Pibeca - Pixel Bender for Canvas

Let me say this first - I am not a fan of Canvas and tinkering around with this project I realized why I prefer programming in AS3 so much more to Javascript: my goodness - this language is a dirty mess, how can anyone get anything done with it? But for fairness sake - I guess there must be some pro development tools out there which I don't know about and my using of notepad might not be the true JS developer experience.

So even though I think that compared to the capabilities of the Flash Player Canvas still lacks a lot, it cannot be ignored since it is now available on most major browsers. As a Flasher I find it especially entertaining to watch how history keeps repeating - browsing Canvas community blogs is like time traveling: plasma effects, l-systems, bitmap manipulations, physics engines, vector drawing experiments, emulators - in short everything that we were excited and enthusiastic about years ago is now being rediscovered, ported or reinvented on Canvas, just like we rediscovered, ported or reinvented things that had been done in Java or C years before Flash. But hey, I actually envy these guys - there is nothing more rewarding and creativity boosting than trying to push a limited platform to the maximum.

So since we are not so different after all, here's a little contribution to world platform peace - Pibeca allows you to use pixel shaders on Canvas Bitmaps. It achieves that by using Adobe® Pixel Bender™ filters which can be written with the freely available Pixel Bender™ toolkit. Those kernels are very small programs who's only purpose in life it is to push pixels around very fast.

So here is an proof of concept which should work on any browser that supports canvas:

Under the hood a canvas bitmap and a kernel url is being sent to an invisible SWF which loads the Pixel Bender filter kernel, processes the bitmap and then sends it back to JavaScript which passes it back to a canvas. That's all. Given that I have to encode the bitmap to a string in order to get it to the other side and back the speed is pretty okay I think.

I wanted to get this prototype out quickly, so until I have prepared some docs and more examples those who are adventurous can already have a look at QuasimondoLibs and check out the Actionscript and Javascript source code for this demo. Pibeca is released under MIT License.

Posted at 12:59 PM | Comments (7)
January 10, 2010
Galactose - Emergent Behavior of Particles

I have added a new experiment called Galactose to my Incubator.

galactose.jpg

The motion of a particle field is controlled by the shape of the random clusters they form among each other. The orientation of the clusters control each particle's further motion which leads to all kind of interesting feedback effects and emergent patterns. The core algorithm which calculates the overall alignment and orientation of the clusters is written in Pixel Bender.

Posted at 08:04 PM | Comments (6)
December 02, 2009
Bloom

Bloom

Posted at 09:22 AM | Comments (2)
October 20, 2009
Flash Median Filter

As you might have read in Eugene's blog, he, Nicoptere and me were having a little competition who could come up with the fastest implementation of a median filter. Median filters have the unpleasant property that they can not be as easily optimized as for example blur filters. The median filter is also one of those types of filters that are not very well suited for an implementation in Pixel Bender due to the way Pixel Bender processes images (except maybe for a trivial 3x3 median).

What a median filter does is to take all the pixels within a certain radius around a pixel, sort them numerically ( channel by channel) and then return the color that ends up in the middle of the sorted list. You can imagine that doing this for every pixel in an image is quite a processing effort. Fortunately people much smarter than me have found ways to speed this up considerably. The paper I had stumbled across sometimes in the past was this one by Simon Perreault and Patrick Hebert. And whilst the authors even provided the C source for this filter I did not bother to look at it since I thought that things that are fast in C are not necessarily fast in Flash and decided to roll my own version of the algorithm based on maintaining the histograms and the kernel in the form of sorted linked lists. I figured that this would speed up the process of joining and separating the histograms since I could use a kind of "zipper" technique to do that. To my astonishment the first tests were extremely slow - even though I tested the speed with a release version (testing this with the debug version is about 10 times slower).

The breakthrough came with a tip Ralph Hauwert gave me: whenever you create a linked list class in Actionscript make sure that you use the "final" keyword for it. Until then I had thought that this keyword acted more as a decorative element without real impact. Well, I'm happy that I was wrong since the speedup in this case was extraordinary.

When you compare my implementation with Eugene's note that a kernel size of 7x7 in his example is the equivalent of a radius of 3 in mine (3+3+1=7), 17x17 is a radius of 8 (8+8+1=17). As far as I can see my version is faster until a radius of 7 but after that his version surpasses mine. I have to study his code now to see how he has solved it.

Since the median filter still takes considerable rendering time I added a "asynchronous" switch which allows to render the effect in background without stalling the rest of the application. Of course this will slow down the whole rendering process.

Here is my Median example
sourcecode and zipped sources

Posted at 01:05 PM | Comments (19)
September 04, 2009
Flash Player Memory Management

Whilst working with some huge bitmaps for Aviary I had to face the undeniable fact that huge bitmaps are memory hogs and that the memory that is made available to the Flash Player by the browser is not unlimited. Actually it is quite limited - on my Vista machine that has 4GB of RAM I max out the memory at ca 1.5GB in FireFox 3.5.2. - that theoretically allows to keep 25 of the 64MB 4095*4095 bitmaps in memory which are the maximum sized bitmaps that Flash Player 10 allows for.

In practice it turns out though that this value is much smaller, the reason for it I learned from Joa: memory fragmentation does have a big impact on how big the chunks of memory can be that you can allocate at a certain time. So while you might be able to create 4 bitmaps of 10 MB each you might not be able to create a single one of 40MB.

But being limited to "just" 1.5GB is unfortunately not the end of the story. It shows that in most browsers (like FireFox 3.5.2) these ca. 1.5GB are not available to every SWF individually. No, all SWFs in all open tabs or windows of Firefox are sharing that one Pool of 1.5GB. That means the more one SWF requests the less is available for the others.

So in order that you can figure out what is happening yourself I've built MemoryHog, a tiny tool which will allocate and release memory. When you open multiple instances of it in your browser of choice you can see how memory is managed between all the open SWFs. A warning though: some browsers in some systems do crash when you press the "request maximum" button. Seems like Macs are more susceptible to this than PCs.

One thing you can see very good with MemoryHog is the influence of memory fragmentation. Sometimes whilst you cannot allocate a 100MB block anymore you are still able to get more than 10 10MB blocks.

My resume for Aviary: whilst it it nice to be able to finally use bigger bitmaps in Flash player 10 when it comes to using more than a few of them at the same time we will have to think about a implementing a tile based solution that makes better use of the fragmenting memory.

Posted at 04:35 PM | Comments (16)
July 01, 2009
Automated Threshold & Edge Detection

It's a tiny bit late maybe, but here are two image processing techniques that deal with automated thresholding and edge detection that I showed in my "2d or not 2d" talk in 2007 and in "The Pixel Whisperer" in 2008.

I've had a look at my presentation demos and repackaged their code into a single class called ThresholdBitmap. This is a BitmapData class with a few extras that help you if you plan to extract blobs or edges from a camera stream or some other bitmap.

The general problem when you do camera based experiments is that you have unnown lighting conditions. Using a simple fixed threshold might work at your development machine but might fail completely on a user's computer that has a different camera model or a different backdrop.

In image processing there are several automated thresholding methods, that are supposed to help with this problem, by looking at an image's histogram and adjusting the threshold to a level that separates the foreground from the background in an optimum way: Moment-Preservation, Maximum Entropy, Discriminant and Otsu. Those are quite capable in finding the optimum threshold level if you have relatively uniform lighting over the whole scene.

As an (better) alternative I included an adaptive threshold method which is implemented in PixelBender and which works very well also with uneven lighting, especially if you try to detect QR codes or other markers.

Furthermore the class includes a very fast edge detection (based on the thresholded image) which gives you nice 1 pixel wide edges in most cases.

Here is a demo that allows you to play around (you'll need a webcam)

Sourceview and code can be found here

Credits: the demo uses the super useful Minimal Components by Keith Peters and the Hi.RES! Stats by Mr. Doob.

Posted at 08:27 PM | Comments (14)
May 17, 2009
A fix for createGradientBox()

Whilst playing around with some geometry that involved gradient fills I had to realize that the native implementation of Flash's createGradientBox() is unfortunately entirely useless as soon as you try to introduce rotation and scaling to a gradient. The reason seems to be that internally the order of matrix operations is unsuited for that task.

Maybe I've searched not thoroughly enough, but I didn't find any solution for this out there. So I've written a tiny class that fixes it. Here's a comparison of the difference between matrix.createGradientBox() and my new GradientMatrix.getGradientBox()

To use it you can use the same values that you would use in the native function, the only difference is that you don't have to create a new Matrix first. The syntax is var myGradientMatrix:Matrix = GradientMatrix.getGradientBox( width, height, rotation, tx, ty);

Download GradientMatrix.as here

Posted at 12:58 AM | Comments (7)
Thank you!

Most Visited Entries
Sketches, Works & Source Code
Lectures
Contact
Backlog
In Love with
Powered by
Movable Type 2.661

© Copyright Mario Klingemann

Syndicate this site:
RSS 1.0 - RSS 2.0

Quasimondo @ flickr
Quasimondo @ LinkedIn
Quasimondo @ Twitter
Quasimondo @ Facebook
Quasimondo @ MySpace
Quasimondo is a Bright
Citizen of the TRansnational Republic
My other blog in german
Impressum


My family name is written Klingemann,
not Klingelmann, Klingeman, Klingaman, Kingemann,
Kindermann, Killingaman, Klingman, Klingmann, Klingonman
Klingemman, Cleangerman, Klingerman or Kleangerman

profile for Quasimondo at Stack Overflow, Q&A for professional and enthusiast programmers