Implement possible size optimizations from Palette sorting from TruePNG #74

shssoichiro · 2017-07-21T12:08:55Z

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

This adds a new palette sorting algorithm that attempts to minimise entropy by an approximate solution to the Traveling Salesman Problem. The algorithm comes from "An efficient Re-indexing algorithm for color-mapped images" by Battiato et al (https://ieeexplore.ieee.org/document/1344033). It's fast and effective and works in addition to the luma sort (which remains the single most effective sort). In order to keep lower presets fast though, I've only enabled this for o3 and higher. Results on a set of 190 indexed images at `-o5`: 18,932,727 bytes - master 18,578,306 bytes - PR 18,559,863 bytes - PR + #509 (These images may be particularly suited to alternative sorting methods - the gains here are not necessarily what should be expected on average) Note I looked into the 120 different palette sorting methods from TruePNG, as mentioned in #74 (and seen in action in the Zopfli KrzYmod fork). They're... largely ineffective. The combination of all 120 methods are outperformed by just the existing luma sort plus this new one. That's not to say there's nothing further to be gained from them, but trying to brute force all the combinations definitely seems like a bad idea. There are other algorithms I hope to explore in future... @ace-dent Thought this might interest you UPDATE: I realised a quick tweak to alpha values in the luma sort can provide a great improvement on images with transparency. The following numbers were taken with PR #509 as base. `-o2`: 19,065,549 bytes - base (luma sort) 18,949,747 bytes - modified luma sort `-o5`: 18,922,165 bytes - base (luma sort) 18,559,863 bytes - new sorting algorithm + luma sort 18,544,813 bytes - new sorting algorithm + modified luma sort

ace-dent · 2023-09-18T15:45:09Z

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

andrews05 · 2023-09-18T23:48:17Z

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

ace-dent · 2023-09-20T11:30:41Z

@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.

@ace-dent

This adds a new palette sorting algorithm that attempts to minimise entropy by an approximate solution to the Traveling Salesman Problem. The algorithm comes from "An efficient Re-indexing algorithm for color-mapped images" by Battiato et al (https://ieeexplore.ieee.org/document/1344033). It's fast and effective and works in addition to the luma sort (which remains the single most effective sort). In order to keep lower presets fast though, I've only enabled this for o3 and higher. Results on a set of 190 indexed images at `-o5`: 18,932,727 bytes - master 18,578,306 bytes - PR 18,559,863 bytes - PR + shssoichiro#509 (These images may be particularly suited to alternative sorting methods - the gains here are not necessarily what should be expected on average) Note I looked into the 120 different palette sorting methods from TruePNG, as mentioned in shssoichiro#74 (and seen in action in the Zopfli KrzYmod fork). They're... largely ineffective. The combination of all 120 methods are outperformed by just the existing luma sort plus this new one. That's not to say there's nothing further to be gained from them, but trying to brute force all the combinations definitely seems like a bad idea. There are other algorithms I hope to explore in future... @ace-dent Thought this might interest you UPDATE: I realised a quick tweak to alpha values in the luma sort can provide a great improvement on images with transparency. The following numbers were taken with PR shssoichiro#509 as base. `-o2`: 19,065,549 bytes - base (luma sort) 18,949,747 bytes - modified luma sort `-o5`: 18,922,165 bytes - base (luma sort) 18,559,863 bytes - new sorting algorithm + luma sort 18,544,813 bytes - new sorting algorithm + modified luma sort

shssoichiro mentioned this issue Jul 21, 2017

PNG optimizer strategies from TruePNG #71

Open

7 tasks

shssoichiro added T-Needs Tests T-Feature Requests for a new feature to be added labels Jul 21, 2017

shssoichiro added the I-Medium Issues that are breaking core functionality, but have a known workaround label Oct 1, 2017

kornelski mentioned this issue Nov 30, 2018

Framework for trying different color modes #152

Closed

shssoichiro added the T-Compression Relates to improving the compression ratio of images label Dec 12, 2018

andrews05 mentioned this issue May 29, 2023

Additional palette sorting algorithm #514

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implement possible size optimizations from Palette sorting from TruePNG #74

Implement possible size optimizations from Palette sorting from TruePNG #74

shssoichiro commented Jul 21, 2017 •

edited

Loading

ace-dent commented Sep 18, 2023 •

edited

Loading

andrews05 commented Sep 18, 2023

ace-dent commented Sep 20, 2023

Implement possible size optimizations from Palette sorting from TruePNG #74

Implement possible size optimizations from Palette sorting from TruePNG #74

Comments

shssoichiro commented Jul 21, 2017 • edited Loading

ace-dent commented Sep 18, 2023 • edited Loading

andrews05 commented Sep 18, 2023

ace-dent commented Sep 20, 2023

shssoichiro commented Jul 21, 2017 •

edited

Loading

ace-dent commented Sep 18, 2023 •

edited

Loading