Monday, August 28, 2006

Real-time Mosaic

This is one of my coolest projects so far.

I have been interested in graphics algorithms for some time, and spent a few weeks writing real-time mosaic code. Basically, this turns an image (generally captured from a web-cam) into a matrix made up of smaller images. These images are matched to the original image pixels, to give the illusion of a single, normal picture. Anyway, doing this was not difficult. I decided to implement this in C++, using OpenGL for high speed blitting. I only had access to a Windows box, so I wrote a frame grabber to capture the data from a standard USB webcam, using the Microsoft directional API. Fun fun fun. (Actually, using DirectX gives me a headache, it is a frustrating, annoying and blotted API that simply takes the fun away from anything!)

I chose C++ because the Mosaic lends itself to OO design, particularly with my picture in a picture in a picture in a picture idea.... Also, I need some speed, so C++ suited nicely. Now, the real challenge was making this work in real-time. Generating a static image is easy, and doesn't require a elegant solution.

I finally produced an algorithm that could create a 1024 x 768 mosaic in real-time (approximately 20 fps). The bottleneck was in the sub-image selection - I use a minimum of 2000 frames, and have to find the closest match to every pixel. I ended up writing an extension of the traditional binary search algorithm, modified to sort based on RGB color and include a tolerance range. Simple put, sorting based on average color is difficult, so the binary search converges on a range of images by comparing the sum of the pictures RGB values. Then a more complex formula is applied to the closest matching set, and the closest image selected. For those Computer Scientists out there, it is O(logn + N), when 0 <= N <= 16 and n is the number of elements to sort. This algorithm results in a good trade-off between running time and the quality of the matches.

The result of all this is RTMosaic. I have included some frames from the file Madagascar as the basis, and a webcam pointed at myself. One of the cool features is the 'infinite complexity' in the final image. These frames were grabbed in real-time from the Mosaic, progressively zooming into my mouth. Remember, everything is in real-time! ;)

Note: These images have not been touched up at all. They are real screen-shots.

Saturday, August 19, 2006

Brownian Motion in Three Dimensions

I saw a Blog a while back talking about Brownian Motion in 3D, so I decided to try it out for myself.
I extended 1D Brownian motion to 3D by applying the equation to each of the X,Y and Z components. I then implemented a radial version (not really Brownian Motion anymore), where the particle direction vector can rotate by a fixed amount each iteration.

The C++/OpenGL code simply using STL lists to keep track of the particles position, and plots its path with a varying HSB colour based on the iteration index.

Below are some screenshots. I added trackball rotation and zoom, so it can be oriented and zoomed in 3D. Pretty cool...

Saturday, August 05, 2006

Visualization of Inter-Related Information

What is the best way to view the relationship between multiple entities? This is a question that I asked myself, specifically I was interested in using the Google SOAP Search API to show the links between websites.

I wanted something that would let entities be represented as shapes, with lines connecting them. I also didn't want them to collide, and I wanted some cool animation effects....

...and believe it or not, the answer lies with first year Physics! I am so glad I didn't sleep through that subject! Actually, I found Physics really interesting, but didn't expected to use my knowledge for this!

I represent each webpage (entity) as a particle. Related particles are connected by a line which models the physics of a spring (remember F=kx and all that?) This lets related nodes stay attached, because of this force. To stop particles colliding, I model them as electro-statically charged particles, each with the same charge. The force repels close particle, so the particles maintain an event spacing, and the particles positions equalizes.

I decided to write this as a Java applet, just for a change. I used the Graphics2D API.

Clicking on an entity triggers a SOAP query, and then the entity 'explodes' with the first 10 related webpages springing out from it. And so on. The entity color is from the HSB colour wheel, and the more similar the colors, the closer related the entities are. Hovering over an entity shows the entities name (webpage title). Entities can also be 'detached' from their children by quickly pulling them away. Moving them close again will 're-link' them together.

Below are some screenshots: