Implement possible size optimizations from Palette sorting from TruePNG

[shssoichiro]

https://css-ig.net/articles/truepng.php

the real good point is the order of entries in palette. it tries to optimize the sorting, sometimes againts logical way, prefering a heavy tRNS chunk — 256 transparent entries where 10 are really useful, but a smaller iDAT, mainly because of the filtering that is used.

TruePNG does some trials to sort the colors to get the smallest file. It tries to sort the colors by popularity, by colors or by luminance. all those trials are done in memory with fast settings (huffman only for compression, filter 0 and 5) and it picks the smallest output.

the first method that TruePNG can use is the ordering by popularity, also used by another programs. it counts the number of time that a color is used in the picture, then move it to the top of palette, and does the same with the next one. this is an effective way to store most of paletted PNG.

[luma] sorting is done according the following calculation 0,299R + 0,587G + 0,114B. colors which have most brightness are moved to the top of the palette. this method is also used by another programs, like PNGOptimizer or OptiPNG. this could be very effective on images which have a lot of gradients.

the palette can be sorted using another combination using the following transformation, consisting to collect the first bit of each RGB bytes of an entry in palette, and does the same with following bits to the end. this can be good for pictures that contains gradients.

according to the version of TruePNG, it also uses another trials with differents methods, that can be done in RGB, YUV or Lab* colorspace, with a different reference color at start.

Method	Color space	Color reference
Nearest	RGB, YUV, Lab*	most popular, most bright or most dark color
Nearest (W)	RGB, YUV, Lab*	most popular, most bright or most dark color
Nearest (N)	RGB, YUV, Lab*	most popular, most bright or most dark color

Nearest: each subsequent color in the palette is taken as the most similar to the previous one. it is done with Euclidean distance: sqr(R1-R2) + sqr(G1-G2) + sqr(B1-B2) [+sqr(A1-A2)] Nearest (W): « W » means weight, and is the closest color value multiplied by the popularity of color which is indirectly correlated with the context of the image. Nearest (N): « N » means neighbor, and is the value of the color multiplied by a factor of popularity in the immediate environment.

• [ ] Trials to sort colors in palette for optimal filesize, accounting for transparency as below

TruePNG is considering the alpha values in a palette to sort colors. it is usually better to store all transparents colors at the top of the palette, because of unnecessary tRNS values affected for non-transparent colors.

but in some cases, it is better to have colors sorted, even if it makes a big tRNS chunk, because the sorting could reduce the iDAT with more efficiency. TruePNG adds combinations for sorting transparency values and selects the smaller output.

[ace-dent]

@andrews05 - here's a tough paletted image to add to your corpus!

[andrews05]

@ace-dent Nice. What's your analysis so far, how does oxipng fare?

[ace-dent]

@andrews05 - I'm collecting images that compress better with oxipng- but haven't analysed them yet. For palette sorting, there still doesn't seem to be one program that is consistently the best.