An Efficient Color Re-indexing Scheme for Palette-based Compression

This paper presents a fast and efficient way for color re-indexing that tends to maximize the compression performance of a palette-based compression system. The proposed scheme relates the index difference of neighboring pixels to the potential cost of bits. It optimizes the assignment of index values to colors in a one-step look-ahead greedy fashion. Experimental results suggest that the proposed re-indexing scheme can reduce the bit rate by up to 43%, when compared to a previously proposed intensity-based color-indexing scheme. Furthermore, we show that with the proposed color re-indexing scheme, the palette-based JPEG-LS and palette-based JPEG-2000 can often outperform GIF significantly.