Skip to end of metadata
Go to start of metadata

Abstract

In the following assignment, we researched two main topics - fractals and the problem of chroma keying, known also as blue screen. Implementations of the respective algorithms written in C99 found its way into the larger Image framework and will be elaborated upon. For each of the problems, a series of images was created to support the case or show the evolution of understanding of the algorithms and its possible advantages or disadvantages in the case.
The image represents a Julia Set known as Chinese Dragon (c=-0.835-0.2321i), where the colors are represent by the number of iterations times respective (b=2.55, r=1, g=1).

Description

We used C programming language to generate and alter images. Our first goal was to code the image structure in order to store and manipulate an image's attributes and data. Our second goal was to code an algorithm to render Mandelbrot and Julia sets. These two functions take in floating point values for the maximum x and y values on the complex plane, and the height of the image and then generate and return a graphical representation of the Mandelbrot or Julia Set defined by those parameters. The final goal was to code an algorithm which would take in an image with a blue background, and replace the background with either a black background, or a specified image. To do this, we wrote a flexible function to replace all the blue pixels with a gray background as defined by the GIF specification, then replace this gray background with the specified new background that is generated from input background file.

Solution

Mandelbrot Set
A Mandelbrot Set is a set of points that can be graphed onto an image to form a fractal. The algorithm we used to generate the Mandelbrot set can be found in Image.c as the function "Image_mandelbrot()". This function takes in floats x0 and y0, which correspond to the minimum x and y window values; floats x1 and y1 which correspond to the maximum extent of the window; and int rows, which corresponds to the number of rows in the image. The algorithm then iterates through each of the pixels of the image and calculates its shade based on the Mandelbrot equation. The Mandelbrot equation calculates x and y values based on:
float x = pow(zx,2)-pow(zy,2)-cx;
float y = 2 * zx * zy - cy;
The x and y values correspond to the location on the complex plane. The cx and cy values are dependent on the position in the image. The algorithm iterates through these equations, changing zx and zy with each iteration (these values represent the x and y values calculated by the previous iteration) , until the x and y values enter the infinity attractor, at which point the iteration stops and colors the current pixel based on the number of iterations.

This is the complete Mandelbrot set, with shading based on the escape time algorithm (as can be told by the distinct color bands).

Julia Set
The Julia set follows a similar algorithm as the Mandelbrot set. Mathematically, the Mandelbrot set is the set of all Julia sets, with each point on the plane representing a different Julia set. While the Mandelbrot set is anchored at 0,0, while the Julia set is anchored at the beginning of the plane. The Julia set is rendered using the "Image_julia()" function in Image.c. This function takes in floats x0, y0, x1, y1, cx, and cy, and int rows. x0 and y0 represent again the minimum x and y window values; x1 and y1 respresent the maximum x and y window values; cx and cy, which are constants in the equation for a Julia set. The algorithm iterates through each of the pixels of the image and calculates its shade based on the Julia set equation. This equation calculates the x and y values based on:
float x = pow(zx,2)-pow(zy,2)-cx;
float y = 2 * zx * zy - cy;
The x and y values correspond to the location on the complex plane. The algorithm iterates through these equations, changing zx and zy with each iteration (these values represent the x and y values calculated by the previous iteration) , until the x and y values enter the infinity attractor, at which point the iteration stops and colors the current pixel based on the number of iterations.

The required Julia set c = 0.7454054 + i*0.1130063 in an appropriate rectangle.

Blue Screen
The chroma keying, known also as the blue screen relies on the fact that such vivid background color rarely occurs in the nature. Thus, it is possible to search the image in search for occurrence of distinct color and simply manipulate based on such.
The implementation for the assignment simply searches every single pixel in the image to check whether the level of blue color is significantly higher then the average of the other two colors plus some random, testing value (found in the trial-and-error method), as to not remove too many items containing tints of blue in the image (e.g. random imprints on the t-shirt). If the color of the pixel is found as blue enough, it is replaced by the standard GIF color for transparency, defined as R: 128, G: 128, B: 128.


Simply Bogo, without any changes.


Bogo with transparency (a sprite) and standard transparent GIF background. The lacks of detection algorithms are especially visible in the shadow.


Less strict check for the background. Bogo's loose hair on the top of the head is not removed by algorithm here.


Stricter check for color. Something is visibly eating my trousers, although the shadow is almost perfectly removed.

The shortcoming of the program here is that it does not pre-search for occurrence of the transparency color in the image. It would be possible to move it slightly in the color space without user noticing the change, and thus avoiding e.g. possible removing of my grey T-shirt imprint.
Thus, the image of person with a transparent background is created. For example, a black background can be employed here.


Bogo on the black background.

By simple adjustments, a separate background can be read into a separate Image construct and then the similar transparency detection can be employed.


Background image.


Me, being a very cute ant.

Furthermore, a separate background creation procedure can be employed and the background, once and for all may be stored in a separate Image entity. We do not really care if the background is bigger then the image we are putting it under, but if it is smaller, tries of reading the data from outside the picture (by sequentially copying equal pixels from one picture onto another) would result in the segmentation fault. In this case we mercilessly repeat background reading by doing modulo division on coordinates, so the number of cols and rows returns and wraps, creating tiling effect.


With said effect, multiplied seals of the College in the background.

Trying to push the framework further, we coded in the support for resizing the sprites and changing their orientation. Orientation change is based on the simple mathematics.

Image_set(rotated, Image_get(src, i, j), src->cols-1-j, i);

i and j are iterating coordinates for respectively rows and columns in the changed orientation.

Resizing (more accurately, downsizing) is based on the principles employed in fractals - the scale factors for both x and y. While this works very well on square images, in case of rectangular images it causes a slight blowing up of the picture, which was not yet resolved very well.
An anti-aliasing was employed to create nicer downsized pictures. A matrix of pixels that are supposed to be represented has all its values averaged for the new pixel, yielding much more aesthetically valued picture (example to follow).


Sampled image of a resized circle (from 1000x1000 to 400x400) has visibly much cleaner edges than unsampled one (below):

Pictures

Aside the images posted over this section, some others follow:


Extension 1 - The values of Mandelbrot set on the plane are colored based on whether the number of iterations was even or not. Interesting ring patterns emerge.


Extension 2 - the higher the values of c, the lower area is occupied by fractal (here c=i)


Extension 3 - aforementioned Chinese Dragon.


Re: Extension 3 - relatively creepy contour of c=1-phi


Different background size vs. multiple Bogos. I am actually on the real photographs from Mazury Lakes, but editing myself in is also relative fun...

Conclusions

In this assignment we learnt a lot about fractals and ways to manage and analyze simple images and how to put simple effects in graphics. It also challenged us to think in the manner that will be the most optimal while executing. Also, we focused on the ways to not multiply beings if the effect can be achieved simpler. Greg also gained relative fluency in C, while I continued to practice writing in my favorite language.

Labels
  • No labels