fractalMapping

Set of libraries and code for running fractal compression and other related code. The fractal compression code is a lossy way of compressing images that keeps track of similarity of bigger blocks within an image to smaller blocks. By storing these similarities as mappings we can recreate an image that is very similar to the original image.

Two core libraries (blockImage.h and compareImages.h) have been created to allow for multiple flavours (letterMapping, regularFractal, regularFractalWithRotation, wavelet) of fractal compression with the help of class inheritance. The blockImage.h library is used to read/write/manipulate images and compareImages.h is the class responsible for generating the 'similarity' mappings as well as recreating an image given a mapping. The inheritance comes into play with compareImages.h. Classes that inherit from this define specific virtual methods that provide ways of determining optimal mappings and ways of generating images given mappings. The purposes of creating the core libraries was to provide an easy way of implementing new methods of fractal compression and image compression.

An image to showcase compression results will be 'Lenna', a common test image used when working with image processing algorithms:

<h2> <a name="lc"> Comments on the code </a> </h2> Each fractal compression code implementation stored in directories (_letterMapping_, _regularFractal_, _regularFractalWithRotation_, _wavelet_) contains a _compress.cc_ file and _decompress.cc_ file. _compress.cc_ is responsible for creating a fractal mapping and _decompress.cc_ is responsible for reading in a mapping and producing an image encrypted in the mapping.

To compile the compress/decompress programs (within directory the program is located) run the following:

g++ -std=c++11 -o (de)compress (de)compress.cc ../blockImage.cc ../compareImages.cc

Some additional requirements and commands may be required for the directories. Those requirements will be described when appropriate.

This library deals with input and output styles of images that are of PNM format with <b>mod 8 height and mod 8 width</b>. Code can be modified to handle images of other dimensions (by filling in non mod 8 dimensions sides with tailing whitespace columns/rows). The PNM format used consists of a text file with .pnm extension where the first line contains: P2 image_width image_height MaxGrey followed by image_width * image_height lines with single integer (0 <= integer <= MaxGrey) representing pixel value. Pixel values in file are recorded to the equivalent way of reading image pixels from left to right and then down one row (like reading a book).

Sample pnm images can be found in sample_images directory.

To convert jpg file to pnm format run the following:

convert lll.jpeg RESULT.pgm
g++ -std=c++11 converter.cc -o convert
./convert RESULT.pgm sample.pnm

converter script is located under other_scripts.

<h2> <a name="lf"> Library Features </a> </h2> Next few sections will discuss features and results of different fractal compression implementations. The algorithms written do not encode the mappings in the most space efficient format, but simple methods to add this and results of such actions is discussed.

The fractal compression algorithms have a very 'slow' nature to them because they require finding optimal mappings between pixel blocks in an image. This requires checking all possible block to block combinations. No additional comments on runtime will be made other than compress and decompress code can take a few seconds to run for a standart 512x512 pixel image such as 'lenna'.

<h2> <a name="rf"> i. regularFractal </a> </h2> <h5> Compression (compress.cc): </h5> Here is a diagram that will be used to explain the algorithm:

<h6> 1. </h6> We start off with the original image (in this example it is 32 by 32 pixels) and split it into two copies. One with 8 by 8 pixels blocks and the other with 16 by 16 pixel blocks. <h6> 2. </h6> We take the 16 by 16 split image and reduce each block to an 8 by 8 pixel approximation by averaging 2 by 2 pixel blocks into one pixel. <h6> 3. </h6> For each possible pairing between an 8 by 8 block from original split and the 16 by 16 reduced split we compute a mapping. The mapping is defined as a scalar multiple <b>a</b> and grayscale shift <b>B</b> computed through simple linear regression (by treating each block as a vector). <h6> 4. </h6> We look at all of the possible mappings between a single 8 by 8 original split block <b>C</b> and all of the reduced blocks computed in part 3. We store the mapping for the <b>C</b> block that produces the smallest error. The error is defined as taking the Euclidean norm of the difference between <b>C</b> and the appropriate mapping(computed in part 3) on a reduced block. We need to store each ideal mapping for each <b>C</b> block. This requires storing the <b>a</b>, <b>B</b> and the position of the 16 by 16 reduced block (in our example the position of the green block in 16 by 16 split is 2). <h5> Compression rate: </h5> Each 8 by 8 block requires to store its approximating 16 by 16 block position, scaling and grayscale shift values. The values of scaling and grayscale are doubles (8 bytes) and approximating block number can be stored as an integer (4 bytes). This means that for each 8 by 8 block you need to store (8+8+4=20) bytes as an upperbound. For lenna, a 512 by 512 pixel image with 4096 - 8 by 8 blocks, that requires 4096*20=81920 bytes for mappings whereas lenna stored in png format requires 264069 bytes. The compression can be optimized even further at the expense of precision. The code can be modified to limit the number of digits stored in scaling/grayscale in order to save space. <h5> Decompression (decompress.cc): </h5> Once you have a mapping, you can then recreate the image approximation using <i>decompress.cc</i> with any starting image such as the following:

The algorithm is very similar to the compression one and we can use the same diagram as in compression section to explain it:

We grab the starting image and split it into two copies. The 8 by 8 split image is what we will be mapping onto and the 16 by 16 split image is where we will be mapping from.

<h6> 2. </h6> We take the 16 by 16 split image and reduce each block to an 8 by 8 pixel approximation by averaging 2 by 2 pixel blocks into one pixel. <h6> 3. </h6> For each 8 by 8 block in original 8 by 8 split we replace the block with the appropriate 16 by 16 reduced block described in mapping, multiplied by scale factor <b>a</b> and adding the grayscale shift <b>b</b>. <h6> 4. </h6> After completing one round of mapping our 8 by 8 block split image will look something like this:

<h6> 5. </h6> To converge to the lenna image we need to set the 8 by 8 block original split as the new 'starting image'. Proceed to step 1. Repeat this about 20 times. After completing this we get the following result:

<h5> Run: </h5> Compress (creates `map_output_extension` file that contains mapping):

cd regularFractal
g++ -std=c++11 -o compress compress.cc ../blockImage.cc ../compareImages.cc
./compress <input_file.pnm> <map_output_extension>

Decompress (creates image_output_name_extension.pnm):

cd regularFractal
g++ -std=c++11 -o decompress decompress.cc ../blockImage.cc ../compareImages.cc
./decompress <map_output_extension> <starting_image_pnm> <image_output_name_extension>

<h2> <a name="rfwr"> ii. regularFractalWithRotation </a> </h2>

This feature is similar to regularFractal, except now the optimal mappings from 16 by 16 reduced blocks to 8 by 8 blocks can include rotation in addition to scaling and grayscale shift. The mappings now also need to store how the 16 by 16 block was rotated. This adds an additional 2 bits per 8 by 8 block. A very negligible cost given that the decompressed image now looks much better than regularFractal(look at the lips and eyes).

Compress (creates map_output_extension file that contains mapping):

cd regularFractalWithRotation
g++ -std=c++11 -o compress compress.cc ../blockImage.cc ../compareImages.cc
./compress <input_file.pnm> <map_output_extension>

Decompress (creates image_output_name_extension.pnm):

cd regularFractalWithRotation
g++ -std=c++11 -o decompress decompress.cc ../blockImage.cc ../compareImages.cc
./decompress <map_output_extension> <starting_image_pnm> <image_output_name_extension>

<h2> <a name="w"> iii. wavelet </a> </h2> The code in this section requires the use of matlab in order to create the Haar-wavelet decomposition. The algorithm breaks an image into its wavelet decomposition. Then it constructs mappings between different levels of the wavelet decomposition by creating mappings between the child and parent levels (child is the smaller image block).

A 2 level wavelet decomposition may look something like this:

Mappings between blocks within a child level and blocks within a parent level are constructed in a similar way to what was done in the fractalMapping section. However, this time we only compute the scaling factor (instead of simple linear regression, we find the line of best fit that c

FractalMapping

Install / Use

README

fractalMapping

Table of Contents: