A Color Reindexing Algorithm for Lossless Compression of Digital Images

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.