FAQ:What is the state of the art in lossless image compression?

From Data Compression Wiki

Jump to: navigation, search

Contents

Algorithms:

JBIG (bi-level, arithmetic coder):

The JBIG algorithm is one of the best available for lossless image compression. For an introduction to JBIG, see FAQ:Introduction to JBIG.

JBIG works best on bi-level images (like faxes) and also works well on gray-coded grey scale images up to about six or so bits per pixel. You just apply JBIG to the bit planes individually. For more bits/pixel, lossless JPEG provides better performance, sometimes. (For JPEG, see FAQ:Introduction to JPEG.)

You can find the specification of JBIG in International Standard ISO/IEC 11544 or in ITU-T Recommendation T.82. You can order a copy directly from ISO or ITU or from your National Standards Body. In the USA, call ANSI at (212) 642-4900.

FELICS (bi-level + greyscale, Huffman):

See also the MG system containing an implementation of the 'FELICS' algorithm of P.G. Howard and J.S. Vitter. FELICS usually gives better and faster compression than lossless JPEG, at least for 8-bit greyscale images (see FAQ:Where can I get image compression programs?). From the MG README file:

The MG system is a suite of programs for compressing and indexing text and images. Most of the functionality implemented in the suite is as described in the book Managing Gigabytes.[1]

These features include:

  • text compression using a Huffman-coded semi-static word-based scheme
  • two-level context-based compression of bi-level images
  • FELICS lossless compression of gray-scale images
  • combined lossy/lossless compression for textual images
  • indexing algorithms for large volumes of text in limited main memory
  • index compression
  • a retrieval system that processes boolean and ranked queries
  • an X windows interface to the retrieval system

Also Paul Howard's PhD thesis, which among other things describes FELICS.[2]

JPEG-LS (greyscale + colorspace, Golomb-Rice)

JPEG-LS is the emerging ISO standard for lossless/near-lossless compression of continuous-tone images. Marcelo Weinberger says about it:

JPEG-LS is being developed by ISO/IEC JTC1/SC29/WG1 (final committee draft document FCD14495-1 as of July 1997), and it is based on HP's LOCO-I algorithm.[3]

The main feature of JPEG-LS is its superior placement in the compression/complexity trade-off curve. Tested over a wide variety of image types, it was shown to be, on the average, within about 4% of the best available lossless image compression at a fraction of the complexity. In particular, JPEG-LS significantly outperforms FELICS and lossless JPEG Huffman at similar levels of complexity (it also outperforms lossless JPEG arithmetic, which is of significantly higher complexity). [...]

A software implementation of JPEG-LS, is now available at http://www.hpl.hp.com/loco/ There, the DCC'96 paper on LOCO-I is also available. The standard draft is also available through a link to the official JPEG Web site.

CALIC[4] (greyscale, Huffman + arithmetic coder)

BTPC[5], APT[6] and PyramidWorkshop (greyscale + colorspace, Huffman + arithmetic coder)

BMF (greyscale + colorspace)

Glicbawls[7], TMW[8] and TMWLego[9] (greyscale + colorspace, arithmetic coder)

MRP - Adaptive Context Quantization[10] (greyscale, Huffman + arithmetic coder)

SLP (greyscale)

PCIF[11] (colorspace, Huffman)

GraLIC[12] (greyscale)

Benchmarks

Here are three more or less representative benchmarks for each kind of image: bi-level, grey-scale and RGB color-space. The images has been choosen based upon:

  • high entropy
  • high level of detail
  • high resolution
  • representative
  • natural
Name: CCITT standard image 8 Size: 513229 bytes Dimension: 1728x2376x1 Sample-Size: 1.00 bits (1.00 bpp) Alphabet-Size: 1.00 bits (1.00 bpp) Entropy: 0.99 bits (0.99 bpp) Color-Entropy: 0.99 bits (0.99 bpp)
Enlarge
Name: CCITT standard image 8
Size: 513229 bytes
Dimension: 1728x2376x1
Sample-Size: 1.00 bits (1.00 bpp)
Alphabet-Size: 1.00 bits (1.00 bpp)
Entropy: 0.99 bits (0.99 bpp)
Color-Entropy: 0.99 bits (0.99 bpp)
Name: Natural Image - Kid Size: 4010371 bytes Dimension: 2474x1621x1 Sample-Size: 8.00 bits (8.00 bpp) Alphabet-Size: 7.99 bits (7.99 bpp) Entropy: 7.05 bits (7.05 bpp) Color-Entropy: 7.05 bits (7.05 bpp)
Enlarge
Name: Natural Image - Kid
Size: 4010371 bytes
Dimension: 2474x1621x1
Sample-Size: 8.00 bits (8.00 bpp)
Alphabet-Size: 7.99 bits (7.99 bpp)
Entropy: 7.05 bits (7.05 bpp)
Color-Entropy: 7.05 bits (7.05 bpp)
Name: Glass-Building Size: 8643844 bytes Dimension: 1742x1654x3 Sample-Size: 8.00 bits (24.00 bpp) Alphabet-Size: 8.00 bits (24.00 bpp) Entropy: 7.78 bits (23.33 bpp) Color-Entropy: 5.46 bits (16.37 bpp)
Enlarge
Name: Glass-Building
Size: 8643844 bytes
Dimension: 1742x1654x3
Sample-Size: 8.00 bits (24.00 bpp)
Alphabet-Size: 8.00 bits (24.00 bpp)
Entropy: 7.78 bits (23.33 bpp)
Color-Entropy: 5.46 bits (16.37 bpp)
B/W: CCITT standard image 8
Compressor Bit per 1bit pixel
order-0 entropy 0.9900
GIF (libGIF v4.1.4) 0.1255
PNG (libPNG v1.2.8) 0.0772
BMF v1.1 0.0557
PyramidWorkshop v0.0.4 0.0438
GraLIC 0.0316
JBIG (libJBIG v1.6) 0.0294
DjVu v2.1 0.0284
BMF v2.0ß (internal) 0.0256
BMF v2.0 0.0255
FELICS (Managing GigaBytes v1.2) 0.0251
Greyscale: Natural Image - Kid
Compressor Below 8bit entropy Bit per 8bit pixel
order-0 entropy 0.000 7.050
GIF (libGIF v4.1.4) 0.753 6.298
Lossless S+P v4.04 1.882 5.169
JPEG (IJG v6.2 + lossless + arithmetic) 3.317 3.734
RKim v1.06 3.509 3.542
PNG (libPNG v1.2.8) 3.560 3.491
FELICS (Managing GigaBytes v1.2) 3.623 3.428
BMF v1.1 3.720 3.330
BTPC v5.0 3.727 3.324
APT v1.0 3.731 3.319
BTPC v4.1 3.776 3.275
JPEG-2000 (Kakadu v5.1) 3.992 3.059
JPEG-2000 (OpenJPEG v1.0) 3.992 3.058
S+P 3.993 3.058
LOCO-I (Columbia University) 4.044 3.007
PyramidWorkshop v0.0.4 4.070 2.980
CALIC 4.132 2.919
SLP 4.136 2.915
BMF v2.0ß (internal) 4.292 2.759
Glicbawls 4.345 2.706
GraLIC 4.347 2.704
BMF v2.0 4.376 2.675
RGB-space: Glass-Building
Compressor Below 8bit entropy Bit per 24bit pixel
order-0 entropy 0.00 23.33
BMF v1.1 3.63 12.42
BMF v2.0ß (internal) 3.89 11.63
PNG (libPNG v1.2.8) 3.92 11.54
BTPC v4.1 4.09 11.03
BTPC v5.0 4.16 10.84
APT v1.0 4.25 10.55
LOCO-I (Columbia University) 4.42 10.04
JPEG-2000 (OpenJPEG v1.0) 4.51 9.78
JPEG-2000 (Kakadu v5.1) 4.51 9.78
PyramidWorkshop v0.0.4 4.57 9.59
Glicbawls 4.82 8.84
RKim v1.06 4.91 8.57
BMF v2.0 5.08 8.05

References

  1. "Managing Gigabytes: Compressing and Indexing Documents and Images", I.H. Witten, A. Moffat, and T.C. Bell; Van Nostrand Reinhold, New York, 1994, ISBN 0-442-01863-0; US $54.95; call 1 (800) 544-0550 to order
  2. "The Design and Analysis of Efficient Lossless Data Compression Systems", Paul Glor Howard, June 1993
  3. "LOCO-I: A Low Complexity, Context-Based, Lossless Image Compression Algorithm", M. Weinberger, G. Seroussi, G. Sapiro - Proc. IEEE Data Compression Conference, Snowbird, Utah, March-April 1996
  4. Wu, Xiaolin and Memon, Nasir,"Context-Based, Adaptive, Lossless Image Coding", IEEE Transactions on Communications, Vol. 45, No. 4, April 1997.
  5. "Efficient General-Purpose Image Compression with Binary Tree Predictive Coding", J. A. Robinson, IEEE Transactions on Image Processing, Vol 6, No 4, April 1997, pp 601-607.
  6. "Adaptive Prediction Trees for Image Compression", J. A. Robinson, IEEE Transactions on Image Processing, Vol 15, No 5, August 2006, pp 2131-2145.
  7. Glicbawls - Grey Level Image Compression By Adaptive Weighted Least Squares, Bernd Meyer & Peter Tischer, School of Computer Science and Software Engineering, Monash University
  8. TMW - a New Method for Lossless Image Compression, Bernd Meyer & Peter Tischer, Department of Computer Science, Monash University
  9. TMWLego - An Object Oriented Image Modelling Framework, Bernd Meyer & Peter E. Tischer, Data Compression Conference 2001: 504
  10. "Lossless Coding of Still Images Using Minimum-Rate Predictors", Ichiro Matsuda, Hirofumi Mori and Susumu Itoh, Proceedings of 2000 IEEE International Conference on Image Processing (ICIP 2000), Vol.I, pp.132-135, Sep. 2000.
  11. The Polyomino Compressed Image Format, Stefano Brocchi
  12. "GraLIC - new lossless image compressor", Alexander Ratushnyak

External links

Personal tools