Ordering color maps for lossless compression

Linear predictive techniques perform poorly when used with color mapped images as there is no linear relationship between neighboring pixels values. Re-ordering the color table, however, can lead to a lower entropy of prediction errors. The problem of ordering the color table such that the absolute weight of the prediction errors is minimized turns out to be intractable. In fact, even for the simplest prediction scheme that uses the value of the previous pixel for the current pixel, the problem of obtaining an optimal ordering turns out to be the optimal linear arrangement problem. The optimal rearrangement problem can be abstracted as a graph problem, and is known to be intractable. We give two heuristics for the problem and use them for ordering the color table of a color mapped image. The first heuristic is based on the famous network flow problem and is computationally expensive. The second heuristic involves successive transposition of color table entries and is simple in terms of implementation and time complexity. Simulation results giving comparison of the two heuristics are presented. Application of the ordering techniques to lossless compression of gray scale image data is also presented. Re-ordering intensity values for images sometimes leads to significant improvements in compression rates. For example, improvements of almost one bit per pixel were obtained with the well known USC-Girl image. Simulation results for a set of standard images are presented.