16 September 1994 Ordering color maps for lossless compression
Author Affiliations +
Proceedings Volume 2308, Visual Communications and Image Processing '94; (1994) https://doi.org/10.1117/12.185878
Event: Visual Communications and Image Processing '94, 1994, Chicago, IL, United States
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.
© (1994) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Nasir D. Memon, Nasir D. Memon, Sibabrata Ray, Sibabrata Ray, } "Ordering color maps for lossless compression", Proc. SPIE 2308, Visual Communications and Image Processing '94, (16 September 1994); doi: 10.1117/12.185878; https://doi.org/10.1117/12.185878


Fast adaptive arithmetic coding
Proceedings of SPIE (May 01 1994)
Vector excitation coding technique for image data
Proceedings of SPIE (March 13 1996)
Two-Dimensional Hybrid Image Coding And Transmission
Proceedings of SPIE (October 13 1987)
Correlation model for a class of medical images
Proceedings of SPIE (June 01 1991)
Adaptive vector quantization for binary images
Proceedings of SPIE (December 28 2000)

Back to Top