Wednesday, April 27, 2011

Lossy Image Compression

Last night I wrote a lossy image compression algorithm. It is based on an idea from this paper. First I trained a set of 256 6x6 color filters on the CIFAR-10 image dataset. To train the filters, I used the k-means algorithm on 400,000 randomly selected image patches. Here are the resulting filters:

I then used the filters to compress the following image:

Using the maximum compression level, JPEG compresses the image to 7.1KiB:

My compression algorithm compresses the image to 5.6KiB:

Try clicking on the above images to see the high resolution versions. My compressed version of the image is smaller and looks better than JPEG.

I did the compression by doing a raster scan of the image and for each image patch I select the best filter. I then losslessly compress the filter selections using paq8l. The obvious improvement to this algorithm would be to use a combination of several filters for each image patch instead of selecting the best filter. Using several filters would take more space to encode but would result in a much better image approximation. Another idea I plan to try is to use this same algorithm for lossy video compression.

No comments: