Entropy constrained color splitting for palette images

This paper proposes two entropy constrained color splitting algorithms through building a binary tree structure for a progressive transmission of palette images. At each step of color splitting, a representative color is split into two new representative colors to minimize the distortion incurred by the reconstructed image subject to an entropy constraint. Among the bit rates of interest, both of the proposed unconditional entropy constrained color splitting algorithms and the conditional entropy constrained color splitting algorithm achieve, on average, 20% more size reduction than the existing distortion-based color splitting algorithm while maintaining the same distortion for our tested images. The superiority of the proposed algorithms is observed for color-quantized nature images and for synthetic images. Furthermore, all the proposed algorithms have a very moderate complexity and can be applied into practical applications like Web browsing through wireless or dialup links.