Brute-Force vs. Heuristic Filtering

For images of color type 3 (indexed color), filter type 0 (None) is usually the most effective. Note that color images with 256 or fewer colors should almost always be stored in indexed color format; truecolor format is likely to be much larger.

Filter type 0 is also recommended for images of bit depths less than 8. For low-bit-depth grayscale images, it may be a net win to expand the image to 8-bit representation and apply filtering, but this is rare.

For truecolor and grayscale images, any of the five filters may prove the most effective. If an encoder uses a fixed filter, the Paeth filter is most likely to be the best. For best compression of truecolor and grayscale images, we recommend an adaptive filtering approach in which a filter is chosen for each scanline. The following simple heuristic has performed well in early tests: compute the output scanline using all five filters, and select the filter that gives the smallest sum of absolute values of outputs. (Consider the output bytes as signed differences for this test.) This method usually outperforms any single fixed filter choice. However, it is likely that much better heuristics will be found as more experience is gained with PNG.

These suggested methods work well for photorealistic images and for images with 256 or fewer colors. However, there are a few cases when different approaches are significantly better.

The first two images presented here have peculiar features, and this is why the special parameters produce much smaller datastreams than the default heuristics. These images have more than 256 colors, but when compared to photo-realistic images, these colors are few. Moreover, there are many single-color patches.

It's worth mentioning the pngcrush program which performs a brute-force search of zlib/libpng parameters. The program also performs an educated search, when it selects 10 trial methods.

The table below compares the lengths of the IDAT (combined) chunk produced by using this heuristics vs. the minimum lengths that can be obtained by setting the zlib/libpng parameters. The brute-force search was performed using pngcrush.

frymire.png  1118 x 1105 pixels  3,622 distinct colors  3,706,170 bytes uncompressed  Original source: Bragzone ColorSet	filter method PNG_ALL_FILTERS PNG_FILTER_NONE zlib compression level 9 9 zlib strategy Z_FILTERED Z_DEFAULT_STRATEGY IDAT size 377522 251865 A big image with few colors. Very big compression ratio (14.7 : 1)
serrano.png  629 x 794 pixels  1,313 distinct colors  1,498,278 bytes uncompressed  Original source: Bragzone ColorSet	filter method PNG_ALL_FILTERS PNG_FILTER_NONE zlib compression level 9 9 zlib strategy Z_FILTERED Z_DEFAULT_STRATEGY IDAT size 152546 106765 This image is smaller than the previous one, and it has fewer colors. The compression ratio is also very big (14.0 : 1)
lena.png  512 x 512 pixels  148,279 distinct colors  786,432 bytes uncompressed  Original source: Bragzone ColorSet	filter method PNG_ALL_FILTERS PNG_ALL_FILTERS zlib compression level 9 4 zlib strategy Z_FILTERED Z_FILTERED IDAT size 475442 475430 A photorealistic image with plenty of colors. Unlike the previous images, this is an example where the suggested heuristics work very well, and the difference achieved by brute-force search is marginal.
?	I am looking for an image that has fewer than 256 colors, and it is still compressed better as an RGB image, rather than a paletted image. Business graphics should be in this category.