Quantization based lossy data compression

This is implementation of VQ algorithm as in http://www.data-compression.com/vq.shtml.

Here is another nice link explaining the concept http://www.gamasutra.com/view/feature/131499/image_compression_with_vector_.php

Before compression	After compression
488K, PNG	92K, Quant, 2,9 bits per pixel
388K, PNG	92K, Quant, 2,9 bits per pixel
108K, PNG	32K, Quant, 4 bits per pixel
84K, PNG	32K, Quant, 4 bits per pixel

All of the above images have compression ratio between 15% and 20% compared to 24-bit per pixel image, and 1:2,5 to 1:5 ratio compared to PNG. Above images are being run with 2x2 block and 1024 codevectors, since experimental results showed that these give reasonable compression ratio, time and image quality.

In order to get yourself familiarized with this algorithm description I recommend reading articles: http://www.data-compression.com/vq.shtml, http://www.gamasutra.com/view/feature/131499/image_compression_with_vector_.php.

Algorithm splits image into blocks of given size (default is 2x2) and then converts the blocks to vectors. Every pixel is considered to be 3x1 vector, and blocks are based on pixels, so 2x2 block (4 pixels) is transformed to 12 dimensional vector. Pixel values range from [0, 255], and this is scaled to [0, 1] range (this gives slightly better results), so in the end we receive 12-dimensional vector.

Splitting method is used to find codevector. I start with one codevector being average of all vectors and in each iteration I run LBG algorithm to improve the codevector base, after LBG run number of codevectors is doubled with first half being multiplied by (1+eps) and the other by (1-eps), and then again LBG is being executed on these. We repeat splitting phase until desired number of codevectors is achieved.

The problem of empty codevector region is solved by assigning random vector from area of the biggest distortion.

There are numerous possible improvements I haven't been able to solve reasonably due to lack of time, experiments etc.

• Images contain a lot of artifacts. I saw improvements in artifacts reduction by modifying eps parameter, adding more codevectors, reducing block size, extending number of iterations in LBG algorithm, different approach to empty regions problem.
• Algorithm is slow. This one will be very hard to achieve since LBG is normally time consuming. Parallelization is highly non-obvious. Here are references which might help in parallelizing: https://arxiv.org/abs/0910.4711, http://ieeexplore.ieee.org/document/1402243/.
• Change color space from RGB to https://en.wikipedia.org/wiki/Lab_color_space
• Use lossless compression methods after quantization run: Huffman encoding, LZ family, possibly others.
• Change algorithm completely. NeuQuant seems to be far more interesting than LBG: https://scientificgems.wordpress.com/stuff/neuquant-fast-high-quality-image-quantization/ and has far better results.

Make sure you have cmake, gcc and boost libraries installed:

sudo apt-get install cmake gcc libboost-all-dev

Pick a directory and clone into it using:

git clone https://github.com/coodie/quant
cd quant

Time to build and install the project:

mkdir build
cd build
cmake ..
make -j
make install

In order to override compiler used by cmake

export CXX=/path/to/compiler
mkdir build
cd build
cmake ..
make -j

Currently only .ppm file compression is supported. Best way to get .ppm out of your favourite format is to use Netpbm package, it is usualy installed on most of linux distros. Here are examples how to get .ppm file from .png and .jpg.

pngtopnm file.png > file.ppm
jpegtopnm file.jpg > file.ppm

Quant performs operations on files based on their extension:

Compression:

quant input.ppm -o output.quant

Decompression:

quant input.quant -o output.ppm

Showcase (how file looks like after compression):

quant input.ppm -o output.ppm

For more options (playing with parameters) use:

quant --help