ImCom

Introduction

This repository implements lossless image compression using Haar Transform which is categorized under Discrete Wavelet Transforms. It breaks the signal into two components namely, average and difference. The average operation produces the approximation coefficients and the difference operation produces detail coefficients.

The program takes a RGB image as an input and produces a compressed image which looks visually the same.

     

The first image's original size is 2.7 MB. After compression, the second image was obtained whose size was reduced to 418.7 KB !

Working

The core principle can be understood using an example :

Let's imagine we have an array

First, we group adjacent elements to form pairs.

Now, average each pair and produce a new array with the first four entries as the averages. Calculate half the difference of the pairs and these four results would occupy the last four slots in the new array.

Here, the first four elements are the approximation coefficients and the last four are detail coefficients.

In the next step, we form pairs from half the length i.e we form two pairs from the first four elements.

We again average the pairs and find out half the differences and replace the first four entries.

This time, we form one pair from the first two elements and carry out the same operations as we did before.

We observe that our latest array has reduced greatly with almost all elements close to 0 except the first one. We can reverse this process to obtain the original array.

We originally had an array with 8 elements. We carried out the operations 3 times. So, how did we arrive at this number? Is it just hit and trial? No, we can find out the number of the iterations by using the formula:

An image can be assumed to be a matrix of finite such arrays. To compress an image, we carry out these operations for all rows and columns to produce a greatly reduced matrix. We could further achieve more compression by choosing a limit and setting all elements in the array whose absolute value is lower than that limit. In the above example, we could set the limit as 0.5. The newly reduced array would be :

There are two approaches to arrive at the same result. We could either iterate through each element of the image and carry out the averaging and subtraction operations. The alternative is to use linear algebra to make the process faster. We could just multiply the image matrix with the Haar transform matrix to get the reduced matrix. This repository makes use of the second method.

The image quality can be improved by normalizing the transformation. The 8x8 normalized Haar transform matrix is defined as :

A RGB image can be represented as a 3-D matrix. To compress a RGB image, we first need to separate the three colour components, namely red, green and blue and store them in separate matrices. The three new matrices obtained are 2-D. Then, we compress them individually, decompress them and combine the three matrices again to form a 3-D matrix. This matrix represents the compressed image after Haar Transform.

Dependencies

All the dependencies can be found here.

Usage

• Clone this repository using :

  https://github.com/InvincibleJuggernaut/ImCom.git
  

• Next, go inside the repository directory using :

  cd ImCom
  

• Install all the dependencies using:

  pip3 install -r requirements.txt
  

• The program takes the image named as abc.jpg as input stored in this directory. Therefore, either place an image renamed as such inside this same directory or change the name of the image in file.py accordingly. Once this is done, the program can be run using :

  python3 file.py 
  

Comments

Note that the python program is using some user-defined functions wherever possible instead of in-built functions from the libraries. For example, matrix mutliplication has been achieved using raw Python code instead of using the much optimized numpy.dot. Therefore, it shouldn't be a surprise that the program is quite slow. It could be drastically sped up using the in-built functions.

License

MIT License