Frankenstein's Algorithm

Our abominable creation

Dramatization of Creating a New Image Compression Algorithm

Attempts At Algorithm

As a capstone to our project, our group hoped to create an entirely new image compression algorithm by cobbling together everything we had learned with regards to image compression.

It is far from optimal. As it turns out, when an industry has already been focused on a field for two decades, most of the ideas have already been implemented or tried. Like Dr. Frankenstein, we decided to mess with powers beyond our control anyways.

After researching variations for converting image information stored in RGB format and other algorithms like discrete wavelet transform, we finally stumbled across a novel way to compress image information.

https://static.vecteezy.com/system/resources/previews/003/399/528/original/modern-flat-design-of-jpeg-file-icon-for-web-free-vector.jpg

Building off of JPEG

Understanding how JPEG compresses images, which applies the 8x8 quantization matrix, then rounding to reduce high frequencies, we had the idea to instead just cut out higher frequencies entirely.

DCT coefficient matrix

Here is the DCT applied to an 8x8 block in the image. Just like in JPEG.

After Frankenstein

Here are the coefficients after applying our elimination algorithm, set to 2x2.

Instead of using the quantization matrix and rounding to decide which components to keep, our algorithm directly sets which values are kept. For instance, setting 2x2 only keeps the coefficient from the first two rows and columns in the DCT coefficients matrix. Below are a few examples of the different setting levels, as well as the resulting ratio achieved.

1x1

Ratio: 0.0156

Here, where the algorithm is set to only keep the 0 frequency component (DCT coefficient at 1x1), there is an extremely visible change from the original image. Now, each 8x8 block where the DCT is performed appears as one, large, homogonous pixel. On the upside, however, very little data is need to to store the resultant image

3x3

Ratio: 0.1403

Expanding the DCT coefficients kept results in a noticeable increase in quality, as values other than the zero frequency are kept, allowing more of the original image to be reconstructed. Even with so much of the frequency component eliminated (only 9/64 coefficients remain), the resulting image is still recognizable.

Diagonal

Ratio: 0.2484

Here, a new method of deciding elimination was used. The coefficients kept were the ones with coordinates <= 5. For instance, the coordinates (1,5) and (3,3) were kept, while (4,4) and (1,6) were eliminated (15/64 coefficients were kept). This most closely follows the pattern in JPEG, where the gradient of elimination is along a diagonal instead of square pattern.

In summary, our algorithm successfully performed image processing and compression, being able to drastically reduce the amount of data present in the final image. It is by no means ideal, however. The 1x1 setting, while incredibly small in data size, is terrible in quality, and unacceptable as an image format. Even with a 3x3 setting, while much more recognizable, still performs poorer visually than a JPEG, which comparatively still had a lower compression ratio of 0.05. This is due to the key distinction that JPEG has an adaptability built in, where the values are proportionally removed or scaled with the quantization matrix, instead of brute forced with our algorithm. The one saving grace is that theoretically, the brute force method requires much less algorithmic work, and could save time.

Page updated

Report abuse