Results for Black & White Images.

The usual lossy compression algorithms do not handle 1-bit per pixel images. We compare the performances of the VCF algorithm for these images with common lossless algorithms, such as PNG (at maximum compression) and GIF. We also compare the VCF to JBIG, which is less known, but seems to outperform PNG to 1-bit images.

The test implementation only handles 8-bits pixels: 0 for black pixels and 255 for white pixels. The pertinence is not a parameter with this kind of images, and the transitions will always occur. The VCF algorithm is lossless for black & white images.

Lenna.

The test is done with the image "lenna", transformed to a 1-bit per pixel. The ratio white-pixels/black-pixels is very close to 1.

This VCF image has a transition table weighting 1009 bytes and there is 12856 1-bit pixels values, weighting 1607 bytes. The test implementation only handles 8-bits pixel values, hence the size of the resulting image: 13885 bytes. But since the pixel values are either 0 or 255, the resulting file is only 3399 bytes once gziped, which is 23 bytes smaller than the same file compressed with PNG.

It would be much more efficient to encode each pixel on one bit. If we had such an implementation, the resulting file weight would be:
1009 + 12856/8 = 1009 + 1607 = 2616.
If we add the 20 bytes header, and if we expect gzip to perform as before (95%), we can estimate the weight of the compressed image at 2505 bytes, which is 27% smaller than PNG, and only 5% bigger than JBIG.

Files size (in bytes) for Lenna:

vcf.gz	vcf.gz 1-bit	PNG	GIF	JBIG
3399	2505	3422	4229	2395

Text.

We try the same experiment with a 704x512 screenshot of a text window. The image is mostly constituted of white pixels (92%) and very few black pixels (8%). This is a worst case scenario for the VCF algorithm, because, as VCF expects large areas to be uniform, most of the transitions are very likely to occur down to pixel level, using a lot of resources for that.

However, the VCF algorithm (with the 1-bit encoding estimation explained above) performs very well when compared to GIF (2 to 7% smaller), only 48% bigger than PNG, and 72% bigger than JBIG.

We tried several top-level cell sizes, and the best results are for 2x2 pixels cells for vcf.gz, and 128x128 pixels cells for estimated 1-bit vcf.gz.

Files size (in bytes) for Text:

vcf.gz	vcf.gz 1-bit	PNG	GIF	JBIG
14520	13696	9248	14740	7977

Results Interpretation.

GIF and PNG are famous for being amongst the most efficient lossless compression of image algorithms. They have been especially designed for this kind of images. The PNG library binary weights 174kB, and 27k for GIF decompression. Both use 2 to 3 times the size of the uncompressed image in memory for compression or decompression.

The VCF algorithm, even with its test sub-optimal implementation, always outperforms GIF, and compares very favorably against PNG at maximum compression rate. The unoptimized VCF compression program weights only 11kB, and 7.2kB for the decompression (on the same computer), and the memory usage is about then 1kB. The size of both programs could probably by optimized down to less than 1KB by using assembly language.
VCF also compares favorably to JBIG, which have been especially designed for 1-bit images, and weights 54KB and 52KB. It should be remembered that VCF has never been designed for such images!

Since the pertinence is ignored for this test, this is the demonstration of the excellent performances of the "Tree of Cells" encoding for images.

prev toc next

last modification: March 2002
(C) Eric GAUDET, 2002