Lab 1. Image Manipulation & Fractals.

M. Stone and A. Pshenichkin. 9.08.04.

Basics

Before we could begin the assigned tasks, we had to have some basic image manipulation tools. Experimentation with Python yielded underwhelming performance, so we switched to C++, which we deemed the right mixture of speed and versatility.

Some of the libraries we found useful were:

All of our programs were compiled with GCC (2.96.4 or 3.3.4) using the SCons construction tool.

The core of our programs is a versatile Pixel class, which allows for the manipulation of a particular point in the image. Through the magic of templating, we can work in RGB space, RGBA space, HSV space, and specific channels thereof. Most of its functionality is done using the inline tag, which keeps it fast by integrating minor function calls into the code.

Basic Image Manipulation: Background Replacement

Our first task was to alter the background on photographs taken in front of a blue screen with a digital camera. This involved isolating the blue background from the image foreground and replacing it, using very simple alpha blending, with a background image.

Our bluescreen photos have a resolution of 2560x1920. This fact can be easily discovered with any image viewer, or by using DevIL's ilGetInteger to find IL_IMAGE_WIDTH and IL_IMAGE_HEIGHT, which return size information about the current image. DevIL also includes an option for detecting the origin: calling ilGetInteger(IL_ORIGIN_MODE) yields a value that is equal to either IL_ORIGIN_LOWER_LEFT or IL_ORIGIN_UPPER_LEFT. Finding the origin simply involved #define-ing the two to be different values and then comparing those to the output of ilGetInteger(IL_ORIGIN_MODE).

We used an algorithm based on the HSV palette to detect the blue areas of an image. Our algorithm searched for a Hue in the blue range with a non-high Value, and set any pixels that fit our criterion to be totally transparent. Pixels that were not in the blue range or were blue but overly bright were left 100% opaque. Simply searching for blue of any Value caused issues because a lot of the colors that were perceptually white or near-white in the image were part of the blue range of hues, most notably glare. This method successfully isolated all of the bright blue in an image, yielding nice lines around edges. We then used alpha blending, albeit only with values of 0 and 255, to composite the two images.

For a pixel in a composite image, the equation for alpha blending would look something like this:

resultant_pixel_color = top_pixel_alpha/255 * top_pixel_color + (1 - top_pixel_alpha/255) * bottom_pixel_color

Thus, a pixel's resultant color is a weighted average of the top and bottom layer pixels' values.

There were still a few issues that such simple algorithms couldn't get around, such as a wisps of hair that acquired a blue coloration from the background layer, and a blue watch which matched the background color almost perfectly. Both images had an errant corner of wall in them, which we removed using Photoshop. One easily-implemented alternative approach would be checking saturation, but we found that it was unnecessary in this instance.

Here are two images that we created by superimposing ourselves onto pictures from Astronomy Picture of the Day:

Mandelbrot and Julia Sets

Calculating Mandelbrot and Julia sets required complex number and matrix operations. After experimenting with the standard complex number implementation, we came to the conclusion that it was just too slow ("First rule of graphics: Speed! Second rule of graphics: Speed!") and switched to our own implementation, a simple struct with a few inline operators, which only did what we needed it to do (multiplication, addition, finding the norm, squaring itself), but did so in a more expedient manner.

A matrix can be used to transform screen coordinates into values on the complex plane. To this end, we implemented our own (psycho-templated) Matrix class, and used the following matrix: 

[ Sx  0   Tx ]
[ 0   Sy  Ty ]
[ 0   0   1  ]
Where Sx & Sy are scale factors and Tx & Ty are translations. Applying this linear transformation to a vector [x, y, 1] maps our pixel to a coordinate on the complex plane, which we then analyze to determine whether it is in the set.

All points in a set go towards either the zero or infinity attractors. Determining which one is accomplished by iterating until we reach a threshold value. If the treshold is not surprassed after a given number of iterations, that point is relegated to the 0 set. Otherwise, the point is colored according to how many iterations it took to cross the threshold, using a lookup table to speed the calculation. After trying a variety of color schemes, we settled on a cosine-based function for a nicer look.

To avoid aliasing (the jaggies), every pixel is actually the average of several different values. We applied the jittering technique, randomizing which points within the area that the pixel corresponds to were sampled to determine the color. A variable set at compile time determines the number of supersample points for each pixel. Randomization is accomplished using a table or psuedo-random values which gets regenerated after every column pass-through (to actually compute all of the tens of millions of random numbers required using rand() would just be amazingly impractical).

Ultimately, our tests took quite a while, especially given the numerous alterations that we made to the jittering algorithm. We have a large collection of images that differ greatly simply because of different antialiasing techniques. Two of our favorites:

M. Stone and A. Pshenichkin.