The efficiency of lossless compression algorithms for fixed palette images (also called indexed images) changes if a different indexing scheme is adopted. Indeed, these algorithms adopt a differential-predictive approach of some sort: if the spatial distribution of the indexes over the image is smooth, greater compression ratios may be obtained It becomes hence relevant to find an indexing scheme that realizes such a smooth distribution. This seems to be a hard problem and only approximate answers can be provided if realistic run-time has to be achieved In this paper we propose a new indexing scheme, based on an approximate algorithm that maximizes the cost of a Hamiltonian path in a weighted graph. The proposed technique compares favourably with the algorithm proposed by Zeng et alii in [7]. The computational complexity of the two algorithms is compared and experimental tests that show relative compression rates are reported.

A Color Reindexing Algorithm for Lossless Compression of Digital Images

BATTIATO, SEBASTIANO;GALLO, Giovanni;STANCO, FILIPPO
2001-01-01

Abstract

The efficiency of lossless compression algorithms for fixed palette images (also called indexed images) changes if a different indexing scheme is adopted. Indeed, these algorithms adopt a differential-predictive approach of some sort: if the spatial distribution of the indexes over the image is smooth, greater compression ratios may be obtained It becomes hence relevant to find an indexing scheme that realizes such a smooth distribution. This seems to be a hard problem and only approximate answers can be provided if realistic run-time has to be achieved In this paper we propose a new indexing scheme, based on an approximate algorithm that maximizes the cost of a Hamiltonian path in a weighted graph. The proposed technique compares favourably with the algorithm proposed by Zeng et alii in [7]. The computational complexity of the two algorithms is compared and experimental tests that show relative compression rates are reported.
0-7695-1215-1
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/77236
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact