Ordering color maps for lossless compression

Nasir D. Memon, Sibabrata Ray

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of SPIE - The International Society for Optical Engineering
PublisherSociety of Photo-Optical Instrumentation Engineers
Number of pages12
Editionp 2
ISBN (Print)081941638X
StatePublished - 1994
EventVisual Communications and Image Processing '94 - Chicago, IL, USA
Duration: Sep 25 1994Sep 29 1994

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
Numberp 2
ISSN (Print)0277-786X


OtherVisual Communications and Image Processing '94
CityChicago, IL, USA

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Ordering color maps for lossless compression'. Together they form a unique fingerprint.

Cite this