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.
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.
posted by Jordan at 6:19 PM
