Inversion ranks for lossless compression of color palette images

摘要

Palette images are widely used in World Wide Web (WWW) and game cartridges applications. Many image used in the WWW are stored and transmitted after they are compressed losslessly with the standard graphics interchange format (GIF), or portable network graphic (PNG). Well known two dimensional compression scheme; such as JPEG-LS and CALIC, fails to yield better compression than GIF or PNG, due to the fact that the pixel value represent indices that point to color values in a look-up table. The GIF standard uses Lempel-Ziv compression, which treats the image as a one-dimensional sequence of index values, ignoring two-dimensional nature. Bzip, another universal compressor, yields even better compression gain that the GIF, PNG, JPEG-LS, and CALIC. Variants of block sorting coders, such as Bzip2, utilize Burrows-Wheeler transformation (BWT) by Burrows M. and Wheeler D. J. (1994), followed by move-to-front (MTF) transformation by Bentley J. L. (1986), Elias, P (1987) before using a statistical coder at the final stage. In this paper, we show that the compression performance of block sorting coder can be improved almost 14% on average by utilizing inversion ranks instead of the move-to-front coding.