Issue 336 in webp: regression in webp lossless (palette)

[pdk… via monorail]

Status: New
Owner: ----
Labels: Type-Defect Priority-Medium

New issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336

http://cdn.pwmon.org/1900/217b.x1.png

The file has increased about 10% in size recently. It's caused by this. (Later commits don't matter.)

https://chromium.googlesource.com/webm/libwebp/+/75a9c3c45230d995af10daf5ceeff5ddda1f8543

# new
$ cwebp 217b.x1.png -lossless -o 217b.x1.png.webp
Saving file '217b.x1.png.webp'
File: 217b.x1.png
Dimension: 681 x 54
Output: 8270 bytes
Lossless-ARGB compressed size: 8270 bytes
* Header size: 51 bytes, image data size: 8194
* Precision Bits: histogram=5 transform=5 cache=0
* Palette size: 29

# old
$ cwebp 217b.x1.png -lossless -o 217b.x1.png.webp
Saving file '217b.x1.png.webp'
File: 217b.x1.png
Dimension: 681 x 54
Output: 7446 bytes
Lossless-ARGB compressed size: 7446 bytes
* Header size: 56 bytes, image data size: 7364
* Lossless features used: PALETTE
* Precision Bits: histogram=5 transform=5 cache=0
* Palette size: 29

Less at 2x resolution.

http://cdn.pwmon.org/1900/217b.x2.png

# new
$ cwebp 217b.x2.png -lossless -o 217b.x2.png.webp
Saving file '217b.x2.png.webp'
File: 217b.x2.png
Dimension: 1362 x 108
Output: 17056 bytes
Lossless-ARGB compressed size: 17056 bytes
* Header size: 57 bytes, image data size: 16974
* Precision Bits: histogram=5 transform=5 cache=0
* Palette size: 24

# old
$ cwebp 217b.x2.png -lossless -o 217b.x2.png.webp
Saving file '217b.x2.png.webp'
File: 217b.x2.png
Dimension: 1362 x 108
Output: 15950 bytes
Lossless-ARGB compressed size: 15950 bytes
* Header size: 57 bytes, image data size: 15867
* Lossless features used: PALETTE
* Precision Bits: histogram=5 transform=5 cache=0
* Palette size: 24


--
You received this message because:
1. The project was configured to send all issue notifications to this address

You may adjust your notification preferences at:
https://bugs.chromium.org/hosting/settings

[vincent.… via monorail]

Updates:
Labels: -Priority-Medium Priority-Low
Owner: vincent....@gmail.com
Status: Accepted

Comment #1 on issue 336 by vincent....@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c1

Hi, thx for the case.
When making improvements compression-wise, it is hard to improve every single image out there. Yours is indeed a regression.
It's tricky to choose the lossless feature before compression starts and the decision making is being improved.

[pdk… via monorail]

Comment #2 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c2

(I accidentally deleted the images.)

[pascal.m… via monorail]

Comment #3 on issue 336 by pascal.m...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c3

Attaching the test image here, for reference.

(please update the bug if you'd prefer the image not to be attached here!)

Attachments:
217b.x1.png 7.6 KB

[pdk… via monorail]

Comment #4 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c4

I have a question. The way I understand vp8l.c the transforms are picked by heuristics primarily based on the entropy of the result. From my experience with DEFLATE in PNG, entropy is a good (but not very good) measurement for compressibility. (Might be different with the more advanced but still DEFLATE-like compression used here.)

As there are only 16 possible combinations of transforms, why not run the full compression for all and then pick the best. Make it a switch.

(That obviously excludes the predictor combinations within the transform itself.) For that transform however, perhaps the few possible square sizes could be added. I think currently only 3 different sizes are picked statically from the method. Which perhaps explains why worse settings sometimes unintuitively produce better results.

[Vincent Rabaud]

You are right that crunching on the different combinations would lead to better results. Not to create too disruptive of a change, we could add that to method 6 only. I am looking into the feasibility, stay tuned.

--
You received this message because you are subscribed to the Google Groups "WebP Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to webp-discuss+unsubscribe@webmproject.org.
To post to this group, send email to webp-d...@webmproject.org.
Visit this group at https://groups.google.com/a/webmproject.org/group/webp-discuss/.
For more options, visit https://groups.google.com/a/webmproject.org/d/optout.

[pdk… via monorail]

Comment #5 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c5

(Reply to your post on the forum.)

I think it doesn't even need to be automatic. Just expose a switch that lets you set the lossless transforms bit-wise. Then users can automate their own combinations. Might be easier than to re-architecture the whole thing.

[vrab… via monorail]

Comment #6 on issue 336 by vra...@google.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c6

Adding yet another switch would complexify the API/command line. Also, this parameter is not very intuitive: exposing it would be useful only if you try all its possible values.
I have a patch ready here: https://chromium-review.googlesource.com/474907
Feel free to comment.

[pdk… via monorail]

Comment #7 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c7

It's a winner I think.

I only tried a few images. For two images size decreased 14-17%. And these are images where WebP already did very well compared to optimized PNGs. (And had not regressed with the new code.)

(PNG)

37054 xyz.x1.png
83385 xyz.x2.png

(WebP)

24750 xyz.x1.webp
48350 xyz.x2.webp

Lossless-ARGB compressed size: 24750 bytes
* Header size: 594 bytes, image data size: 24130
* Lossless features used: SUBTRACT-GREEN
* Precision Bits: histogram=5 transform=5 cache=7

Lossless-ARGB compressed size: 48350 bytes
* Header size: 1468 bytes, image data size: 46856
* Lossless features used: SUBTRACT-GREEN
* Precision Bits: histogram=6 transform=5 cache=7

(WebP+474907)

21162 xyz.x1.webp
39900 xyz.x2.webp

Lossless-ARGB compressed size: 21162 bytes
* Header size: 1202 bytes, image data size: 19935
* Lossless features used: PREDICTION CROSS-COLOR-TRANSFORM SUBTRACT-GREEN
* Precision Bits: histogram=5 transform=4 cache=1

Lossless-ARGB compressed size: 39900 bytes
* Header size: 2176 bytes, image data size: 37699
* Lossless features used: PREDICTION CROSS-COLOR-TRANSFORM SUBTRACT-GREEN
* Precision Bits: histogram=6 transform=4 cache=1

If I could make a suggestion it's to introduce the switch -slow_lossless or similar for this, as the increase in encoding time from 5 to 6 is obviously significant and not expected. (As is the potential benefit!) It also allows using this in combination with 4 (rather than 6), as I've noticed that 4 tends to often do marginally better on smaller (as in compressed bytes) images.

[vrab… via monorail]

Comment #8 on issue 336 by vra...@google.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c8

I updated the patch to simplify/fix a compression regression.

We can't add a parameter:
- cwebp is already cluttered
- mostly: this feature is very useful so it has to be usable from the API (not just from the executable).

That leaves us with:
- having a different behavior for method=6 (which can lead to a 10x slowdown ...)
- have a method 7 (but changing the possible values is also not acceptable)
- try out the five methods for m=6 and q=100 only
- for m=6, try out 1 method for q<25, 2 for 25<q<50, 3 for 50<q<75 and so on.

[pdk… via monorail]

Comment #9 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c9

I think -q is problematic as most users may not even know that it applies to lossless. I don't think it's documented well.

-q <float> ............. quality factor (0:small..100:big), default=75

(For lossless, usually the opposite is true.)

Although they may use -z for the same effect.

[pdk… via monorail]

Comment #10 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c10

I'd like to propose a mini-patch that saves some bytes on images with predictor transform. With the above images 8 and 30 bytes. The idea is to prefer the predictor of the previous tile.



Attachments:
p.diff 2.0 KB

[pdk… via monorail]

Comment #11 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c11

​Well, I noticed an image with an adverse effect of about 100 bytes, so it
may not be a good idea.​

[pdk… via monorail]

Comment #12 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c12

​I think there is a bug in the new code somewhere as it can significantly
increase the size of near lossless images.​

[vrab… via monorail]

Comment #13 on issue 336 by vra...@google.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c13

Hi, I believe the bug is fixed (still testing) and please add an image to this bug report if not.
For your patch, I could not see any noticeable improvement: it is easy to improve images by a few bytes but we want a consistant improvement.
Nonetheless, your patch has the right idea and I am playing with using the entropy codes we learn in patches in a second pass.

[pdk… via monorail]

Comment #14 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c14

The bug is still there.

$ examples/cwebp -near_lossless 20 -m 5 -q 100 98965986.source.x2.webp -o 98965986.source.x2.webp.webp
...
Output: 950578 bytes
Lossless-ARGB compressed size: 950578 bytes
* Header size: 16666 bytes, image data size: 933886

* Lossless features used: PREDICTION CROSS-COLOR-TRANSFORM

* Precision Bits: histogram=5 transform=4 cache=10

$ examples/cwebp -near_lossless 20 -m 6 -q 100 98965986.source.x2.webp -o 98965986.source.x2.webp.webp
...
Output: 1052632 bytes
Lossless-ARGB compressed size: 1052632 bytes
* Header size: 18808 bytes, image data size: 1033798

* Lossless features used: PREDICTION CROSS-COLOR-TRANSFORM SUBTRACT-GREEN

* Precision Bits: histogram=5 transform=4 cache=10

It also adds some artifacts to the image. Well noticeable as horizontal lines above the large tree.

http://cdn.pwmon.org/webp/html/98965986.source.x2.webp

[pdk… via monorail]

Comment #15 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c15

Also I think limiting it to q=100 makes it unnecessarily slow. I've noticed that q=100 is about twice as slow as q=50, with usually negligible size difference. And that slowness is multiplied now. An intermediate solution could be to run the combinations at q=50, which I think is very unlikely to produce a different set of transform, and then compress the best again at q=100. That's still one iteration wasted, and more complex code.

It makes the case for having a dedicated switch again IMO.

[pdk… via monorail]

Comment #16 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c16

The new code reduces this image by 37%. Otherwise it's 39% larger than PNG. (Not a regression.)

http://cdn.pwmon.org/webp/pw.png

(PNG)

170537 pw.png

(WebP)

Output: 236618 bytes
Lossless-ARGB compressed size: 236618 bytes
* Header size: 6569 bytes, image data size: 230024

* Lossless features used: PREDICTION CROSS-COLOR-TRANSFORM

* Precision Bits: histogram=4 transform=4 cache=10

(WebP+474907)

Output: 149312 bytes
Lossless-ARGB compressed size: 149312 bytes
* Header size: 2684 bytes, image data size: 146602
* Precision Bits: histogram=4 transform=4 cache=10

[vrab… via monorail]

Comment #17 on issue 336 by vra...@google.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c17

Nice one for the PNG ! That should drastically reduce the number of images where WebP is bigger.
For your q=50 idea, I think it's better to keep the idea that "-m6 -q 100" is the best we can have that we know of (and by doing your q=50, we know that we could do better by having a q=100 in the first pass).
I updated the code to fix your image btw. Testing is ongoing but if you have non-working image, please attach. Thx!

[vrab… via monorail]

Comment #18 on issue 336 by vra...@google.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c18

The patch is currently on hold until 483824 is in and more testing is done.

[vincent.… via monorail]

Updates:
Status: Fixed

Comment #19 on issue 336 by vincent....@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c19

https://chromium-review.googlesource.com/c/474907/ got in.
The default heuristic to choose the transform could be improved but the cruncher is a safe (but slow) way of getting the best transform.

[pdk… via monorail]

Comment #20 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c20

Regarding slowness, this seems like a prime target for multi-threading.

[bugdro… via monorail]

Comment #21 on issue 336 by bugd...@chromium.org: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c21

The following revision refers to this bug:
https://chromium.googlesource.com/webm/libwebp/+/f8c2ac15af8be582e2bd79d6133b3b4ae11956d5

commit f8c2ac15af8be582e2bd79d6133b3b4ae11956d5
Author: Vincent Rabaud <vra...@google.com>
Date: Wed Jun 14 14:50:36 2017

Multi-thread the lossless cruncher.

BUG=webp:336

Change-Id: I8e861d6a61d51a5cdc4bbd00cd4f17d4ff006d2f

[modify] https://crrev.com/f8c2ac15af8be582e2bd79d6133b3b4ae11956d5/src/utils/bit_writer_utils.c
[modify] https://crrev.com/f8c2ac15af8be582e2bd79d6133b3b4ae11956d5/src/enc/vp8l_enc.c
[modify] https://crrev.com/f8c2ac15af8be582e2bd79d6133b3b4ae11956d5/src/utils/bit_writer_utils.h

[pdk… via monorail]

Comment #22 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c22

​Wow this is great. I think this makes the case to loosen the restrictions
on this feature, or introduce some additional logic to enable it.​

[pdk… via monorail]

Comment #23 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c23

​PS. You may have already noticed this, but the man page is incorrect now.
​
​
Use multi-threading for encoding, if possible. This option is only effective
​
when using lossy compression on a source with a transparency channel.

[bugdro… via monorail]

Comment #24 on issue 336 by bugd...@chromium.org: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c24

The following revision refers to this bug:

https://chromium.googlesource.com/webm/libwebp/+/f1d5a397db3edf9ac38de1e5659c2ff424a4c622

commit f1d5a397db3edf9ac38de1e5659c2ff424a4c622
Author: Pascal Massimino <pascal.m...@gmail.com>
Date: Wed Jun 14 19:49:13 2017

multithread cruncher: only copy stats when picture->stats != NULL

BUG=webp:336

Change-Id: I6dfbbdcf61a6cb455f6cbf3dcd7f4c46578f42aa

[modify] https://crrev.com/f1d5a397db3edf9ac38de1e5659c2ff424a4c622/src/enc/vp8l_enc.c

[vincent.… via monorail]

Comment #25 on issue 336 by vincent....@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c25

Thx pdknsk@, good catch on the man pages !

[bugdro… via monorail]

Comment #26 on issue 336 by bugd...@chromium.org: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c26

The following revision refers to this bug:

https://chromium.googlesource.com/webm/libwebp/+/f0569adb9367eb1392c489864d7a0892bc196fb9

commit f0569adb9367eb1392c489864d7a0892bc196fb9
Author: Vincent Rabaud <vra...@google.com>
Date: Thu Jun 15 08:49:04 2017

Fix man pages for multi-threading.

BUG=webp:336

Change-Id: I70d3dfb8a532c1f2b80bd08cc62e833962cb4b34

[modify] https://crrev.com/f0569adb9367eb1392c489864d7a0892bc196fb9/man/cwebp.1
[modify] https://crrev.com/f0569adb9367eb1392c489864d7a0892bc196fb9/man/gif2webp.1

[pdk… via monorail]

Comment #27 on issue 336 by pdk...@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c27

​Is it planned to scale the side thread(s)?​

[vincent.… via monorail]

Comment #28 on issue 336 by vincent....@gmail.com: regression in webp lossless (palette)
https://bugs.chromium.org/p/webp/issues/detail?id=336#c28

pdknsk@, for now, we'll stick to two threads: yes, more workers would probably be beneficial.
But the ideal solution would be to have the user choose the number of threads, and that would require a proper priority queue, which is not worth the effort implementing in C. In addition, the amount of CPU used is the same, multi-threading only helps the throughput and the cruncher mode is to be used for static assets, not for on the fly encoding.