TY - GEN

T1 - Ordering color maps for lossless compression

AU - Memon, Nasir D.

AU - Ray, Sibabrata

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028758044&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028758044&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0028758044

SN - 081941638X

T3 - Proceedings of SPIE - The International Society for Optical Engineering

SP - 1192

EP - 1203

BT - Proceedings of SPIE - The International Society for Optical Engineering

PB - Society of Photo-Optical Instrumentation Engineers

T2 - Visual Communications and Image Processing '94

Y2 - 25 September 1994 through 29 September 1994

ER -