Battiato Sebastiano, Gallo Giovanni, Impoco Gaetano, Stanco Filippo
Dipartimento di Matematica e Informatica, University of Catania, Italy.
IEEE Trans Image Process. 2004 Nov;13(11):1419-23. doi: 10.1109/tip.2004.836183.
The efficiency of lossless compression algorithms for fixed-palette images (indexed images) may change if a different indexing scheme is adopted. Many lossless compression algorithms adopt a differential-predictive approach. Hence, if the spatial distribution of the indexes over the image is smooth, greater compression ratios may be obtained. Because of this, finding an indexing scheme that realizes such a smooth distribution is a relevant issue. Obtaining an optimal re-indexing scheme is suspected to be a hard problem and only approximate solutions have been provided in literature. In this paper, we restate the re-indexing problem as a graph optimization problem: an optimal re-indexing corresponds to the heaviest Hamiltonian path in a weighted graph. It follows that any algorithm which finds a good approximate solution to this graph-theoretical problem also provides a good re-indexing. We propose a simple and easy-to-implement approximation algorithm to find such a path. The proposed technique compares favorably with most of the algorithms proposed in literature, both in terms of computational complexity and of compression ratio.
如果采用不同的索引方案，固定调色板图像（索引图像）的无损压缩算法的效率可能会发生变化。许多无损压缩算法采用差分预测方法。因此，如果索引在图像上的空间分布是平滑的，则可以获得更高的压缩率。因此，找到一种能够实现这种平滑分布的索引方案是一个相关问题。获得最优的重新索引方案被认为是一个难题，文献中仅提供了近似解。在本文中，我们将重新索引问题重新表述为一个图优化问题：最优重新索引对应于加权图中的最重哈密顿路径。由此可见，任何找到该图论问题良好近似解的算法也能提供良好的重新索引。我们提出了一种简单且易于实现的近似算法来找到这样一条路径。所提出的技术在计算复杂度和压缩率方面都优于文献中提出的大多数算法。
