8 Bits per Pixel in Paletted Images

The default heuristics applied when encoding paletted images is to use as few bits per pixel as possible. However, it is not uncommon for a bigger number of bits per pixels (usually, 8) to be a better choice, even when a smaller number is also possible to be used. The reason relies on the deflate compression, which is designed to encode 8-bit values best.

More precisely, the Lempel-Ziv algorithm encodes sequences of 8-bit values. Further, the Huffman algorithm might compress a certain number of values better than twice as few, but twice as long values which might be perceived as noise. For example, the sequence 1, 2, 3, 2, 2, 1 has more redundancy than the sequence of pairs (1, 2), (3, 2), (2, 1).

The example below (640 x 480, 16-color paletted image) is better compressed at 8bpp than at 4bpp. On the other hand, if interlaced, the same example is better compressed at 4bpp. The example was compressed using the best deflate compression and no filtering.
 

Image type	Length of IDAT	zlib strategy
4bpp, non-interlaced	65501	Z_DEFAULT_STRATEGY
8bpp, non-interlaced	64717	Z_FILTERED
4bpp, interlaced	77691	Z_DEFAULT_STRATEGY
8bpp, interlaced	78134	Z_FILTERED

It can be noticed that Z_FILTERED is better when the higher bit depth is chosen.

The test image is here: