Improved lossless compression of color-mapped images by an approximate solution of the traveling salesman problem

Author

Spira, A. ; Malah, D.

Author_Institution

Res. Div., Net2Wireless Israel Ltd, Haifa, Israel

Volume

3

fYear

2001

fDate

2001

Firstpage

1797

Abstract

A color-mapped image is composed of a palette and an image of indices. The color of each pixel is the palette color referenced by the pixel´s index. The indices image is usually far from being smooth. This affects its compressibility by lossless image compression methods, due to their reliance on the natural smoothness of images. The indices images can be smoothed by re-ordering the palette, ie, assigning the indices to the colors in a better way. We propose a new method for palette ordering based on an approximate solution of the traveling salesman problem. The proposed method has low complexity, dependent only on the size of the palette. It is found to significantly improve the compression ratios of color-mapped images coded with the JPEG-LS lossless compression standard. The resulting compression ratios are better than those achieved by the popular GIF image file format

Keywords

approximation theory; data compression; image coding; image colour analysis; travelling salesman problems; JPEG-LS standard; approximate solution; color-mapped image; compression ratios; image coding; image compression; indices; lossless compression; palette ordering; pixel index; traveling salesman problem; Code standards; Color; Displays; Heuristic algorithms; Image coding; Laplace equations; Pixel; Self organizing feature maps; Streaming media; Traveling salesman problems;

fLanguage

English

Publisher

ieee

Conference_Titel

Acoustics, Speech, and Signal Processing, 2001. Proceedings. (ICASSP '01). 2001 IEEE International Conference on

Conference_Location

Salt Lake City, UT

ISSN

1520-6149

Print_ISBN

0-7803-7041-4

Type

conf

DOI

10.1109/ICASSP.2001.941290

Filename

941290