Ordering color maps for lossless compression

Nasir D. Memon; Sibabrata Ray

doi:10.1117/12.185878

16 September 1994 Ordering color maps for lossless compression

Nasir D. Memon, Sibabrata Ray

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

Abstract

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.

Citation Download Citation

Nasir D. Memon and Sibabrata Ray "Ordering color maps for lossless compression", Proc. SPIE 2308, Visual Communications and Image Processing '94, (16 September 1994); https://doi.org/10.1117/12.185878

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available