Forum archive

Algorithm of optimisation PNG

lorents at 2010-08-05 00:37

Good afternoon!
Help to solve the following problem.
On given I have two algorithms of optimisation PNG

for /f "delims=" %%i in ('dir /b /s /a-d Images\*.png') do (
	call :pngopt "%%~fi"
	"%~dp0Docs\advpng.exe" -z -4 "%%~fi"
	"%~dp0Docs\deflopt.exe" "%%~fi"
)

:pngopt
"%~dp0Docs\optipng.exe" -i0 -zw32k -zc1-9 -zm1-9 -zs0-3 -f0-5 -full -force %1 > %temp%\png.log
for /f "delims==,IDAT tokens=5" %%i in (%temp%\png.log) do (
	set f=%%i
)
set f=%f:~1,1%
del %temp%\png.log
"%~dp0Docs\pngout.exe" /k0 /f%f% %1

and

for /f "delims=" %%i in ('dir /b /s /a-d Images\*.png') do (
	"%~dp0Docs\optipng.exe" -i0 -zw32k -zc1-9 -zm1-9 -zs0-3 -f0-5 -force "%%~fi"
	"%~dp0Docs\pngout.exe" /k0 /ks "%%~fi"
	"%~dp0Docs\advpng.exe" -z -4 "%%~fi"
	"%~dp0Docs\deflopt.exe" "%%~fi"
)

Both ways well enough optimise PNG, but there is one problem. I do not know in advance what way will yield the best result if possibility it to define without search of algorithms?

Whether also there are even more strongly algorithms, without considering search of filters?

AcetoliNe at 2010-08-05 15:41
Re: Algorithm of optimisation PNG
Those aren't 'algorithms'; you're just invoking different PNG programs in advance.

The only way to tell which one will compress a specific PNG better, is to try them out. There is no sure-fire shortcut method that I am aware of.
lorents at 2010-08-05 16:01
Clearly, painfully it would not be desirable to touch, but it seems there is no other way out.
lorents at 2010-08-20 16:17
Whether prompt, please, there is a communication -zc-zm-zs OptiPng with-n or-b PngOut?
Awesoken at 2010-08-21 02:41
-zs is similar to the /s# option in PNGOUT, although the assignment of strategy numbers is different.

-zc and -zm do not have a similar option in PNGOUT.

/b# and /n# in PNGOUT control the same thing - the number of Huffman blocks generated. I do not believe OPTIPNG has an option to control the number of Huffman blocks.
lorents at 2010-08-21 03:06
Clearly, that have explained thanks.
Simply at different values of parametres -zw -zc -zm -zs OptiPng, I receive the different size of files PNG through/ks PngOut. Also wanted to learn, how it is possible to receive the least the size PNG without search, or at least to reduce quantity of touched files?
Has noticed that sometimes at/s1 PngOut I receive the size less than at/s0.
counting_pine at 2010-08-21 08:04
-zm is a rough analogue to /b - it tells zlib how many codes it can fit inside a block, which directly controls how many blocks are used. I think the maximum number of codes inside a block (including the end-of-block code) is a relatively modest 32768.

The number of codes per block doubles (and the number of blocks approximately halves) with each increment of -zm.
lorents at 2010-08-21 15:49
Can you meant not -zm, and -zw?
counting_pine at 2010-08-22 07:13
If I understand right, -zw controls the window size - how far back it's prepared to search for matches. In most cases the largest size will probably be best. Anything else would limit the potential for match-finding, which is usually an important component of the compression.
It probably has no effect for -z2 and -z3, since it limits the effective window size to 0 or 1.

You can check how many blocks are emitted for an image using flateinfo if it's still around, or by reading the output of pngout /ks /v.
lorents at 2010-08-22 20:27
Whether correctly I understand, the it is less quantity of blocks, the better?
Where it is possible to download flateinfo?
counting_pine at 2010-08-23 11:11
Fewer blocks aren't always better.

It's worth splitting a block if the code frequencies in the first half differ enough from the code frequencies in the second half that it's worth the overhead of an additional block header to give each half its own Huffman tree. The larger the block is, the more likely this is to happen.

I don't know Ken's block split threshold algorithm, but /b256 tends to work pretty well. I find it often beats /n1.

(@Ken: /n1 seems to take the time to calculate block split thresholds, while /b0 doesn't. Not a bug, and certainly not unworkaroundable, but something you might be interested in remedying.)

I'm not sure flateinfo is still available. I'm not even sure if I have a copy of a version that reads PNGs. There's also the method Ken mentions in www.jonof.id.au/forum/index.php?topic=1176.msg6938#msg6938 - some assembly required.
lorents at 2010-08-23 14:49
Thanks a lot that have explained.
lorents at 2010-09-05 01:20
Explain please why, by optimisation of the same picture through parametre /r I receive the different sizes?
counting_pine at 2010-09-19 08:09
Hi,
/R adds a random factor to PNGOUT. Ordinarily it starts compressing each block with a fairly uniform Huffman tree and iteratively improves it. With /R, it starts with random Huffman trees instead. This can result in different local minima, which can result in better compression.

PS. I'd forgotten about PNGOUT's /L feature. That quickly spits out the block count in the '/n' number.
lorents at 2010-09-19 17:10
Thanks, and it is possible to learn all latent functions PngOut?
lorents at 2010-09-19 17:57
Prompt, How it is possible to find, the best approximate value n?
counting_pine at 2010-09-20 23:03
You can find out most of PNGOUT's functionality at http://advsys.net/ken/util/pngout.htm
I think it's complete apart from the /L parameter and the return values, which are explained in www.jonof.id.au/forum/index.php?topic=1515
As for finding the best block count, a binary search (using /s2 for speed) might work well.
Awesoken at 2010-09-21 01:27
I have updated the PNGOUT tutorial with /L and the exit codes. Thanks for pointing it out, counting_pine.

Technically, it would make more sense to use a Golden Section Search to find a minimum. Because the function is noisy, you should use brute force for the final steps.
lorents at 2010-09-22 18:47
Thanks for councils, have very strongly helped.
I wanted to specify still, whether ????? communication to honey in parameters /n and /f?
lorents at 2010-09-22 19:52
How I understand, value of parameter /n on a straight line depends on the size of the picture, I am right?
counting_pine at 2010-09-24 04:00
Thanks for the WP link Ken, looks like it deserves a good read-through at some point.
@lorents:
The /f filter types should be treated as discrete and they have to be brute-forced. But /f0 for simple diagrams and /f5 for everything else are "usually" the best.
I don't know what magic Ken's using in the /b algorithm and I haven't investigated the correlation between image size and the number of blocks created using /b. But larger images, and less compressible images, will usually be given more blocks.

If I had to guess, I'd say it runs through the data with a quick, rough "compression" algorithm, puts the resulting codes in a single block, and then bisects the block recursively, based on the frequency of the codes and how much can be gained from splitting it in two. If the gain is more than the extra overhead of writing two blocks instead of one, then the block is split.
Assuming a constant-size block header, the gain would need to be at least the size of a block header. The /b "block split threshold" would be the assumed block header size. The smaller the value, the more likely the algorithm is to split the block.

The /n algorithm would, I suppose, just keep subdividing blocks, choosing the block with the largest split gain each time, until the desired number of blocks is reached.
lorents at 2010-09-24 04:10
That have explained thanks.
lorents at 2010-10-17 17:45
Good afternoon!
Explain, please, as it is possible to learn, in what parameters will optimize PngOut, but without the process of optimization?
Edited by lorents at 2010-10-18 00:20
lorents at 2011-01-13 08:19
Good afternoon!
I search for the program which deletes defined Chunks, but doesn't optimize PNG and works in a command line?

Forum archive

Algorithm of optimisation PNG

Re: Algorithm of optimisation PNG