LibGfx/AnimationWriter+WebPWriter: Compress identical pixels in consecutive frames

[nico]

AnimationWriter already only stores the smallest rect that contains changing pixels between two frames. For example, when doing a screen recording and only the mouse cursor moves, we already only encode the pixels in the (single) rectangle containing old and new mouse cursor positions.

Within that rectangle, there can still be many pixels that are identical over the two frames. When possible, we now replace all identical pixels with transparent black. This has two advantages:

1. It can reduce the number of colors in the image. In particular, for wow.gif (and likely many other gifs), new frames had more than 256 colors before, and have fewer than 256 colors after this change.

2. Long run of identical pixels compress better.

In some cases, this transform might make things slighly worse, for example if the input image already consists of long runs of a single color. We'll now add another color to it (transparent black), without it helping much. And the decoder now must do some blending, slowing down decoding a bit.

But most of the time this should be a pretty big win. We can tweak the heuristic when to do it later.

This transform is possible when:

• The new frame doesn't already have transparent pixels (which are different from the old frame)

• The encoder/decoder can handle frames with transparent pixels

For the latter reason, encoders currently have to opt in to this.

LibGfx/WebPWriter: Opt in WebPAnimationWriter to inter frame compression

No effect on sunset-retro.png since that's not animated.

    wow.gif (nee giphy.gif) (184k):
        1.4M -> 255K
        74.0 ms ± 1.1 ms -> 86.9 ms ± 3.3 ms

(from 7.6x as big as the gif input to 1.4x as big.
About 82% smaller, for a 16% slowdown.)

    7z7c.gif (11K):
        8.4K -> 8.6K
        12.9 ms ± 0.5 ms -> 12.7 ms ± 0.5 ms

(2.4% bigger, so the transform makes things a bit worse for this
image.)

[nico]

I haven't implemented this for GIFWriter yet since that doesn't have full support for compression. Adding just

diff --git a/Userland/Libraries/LibGfx/ImageFormats/GIFWriter.cpp b/Userland/Libraries/LibGfx/ImageFormats/GIFWriter.cpp
index 6db2ecc1d6..eb5e2179c6 100644
--- a/Userland/Libraries/LibGfx/ImageFormats/GIFWriter.cpp
+++ b/Userland/Libraries/LibGfx/ImageFormats/GIFWriter.cpp
@@ -169,6 +169,7 @@ public:
     }

     virtual ErrorOr<void> add_frame(Bitmap&, int, IntPoint, BlendMode) override;
+    virtual bool can_blend_frames() const override { return true; }

 private:
     SeekableStream& m_stream;

and running Build/lagom/bin/animation -o wow2.gif wow.gif produces this gif, which nicely visualizes what's actually stored in the file now (all the black pixels are fully transparent):

Also adding:

diff --git a/Userland/Libraries/LibGfx/ImageFormats/GIFWriter.cpp b/Userland/Libraries/LibGfx/ImageFormats/GIFWriter.cpp
index 6db2ecc1d6..842a2ab476 100644
--- a/Userland/Libraries/LibGfx/ImageFormats/GIFWriter.cpp
+++ b/Userland/Libraries/LibGfx/ImageFormats/GIFWriter.cpp
@@ -141,7 +141,7 @@ ErrorOr<void> write_graphic_control_extension(BigEndianOutputBitStream& stream,
     // User Input Flag
     TRY(stream.write_bits(false, 1));
     // Transparency Flag
-    TRY(stream.write_bits(false, 1));
+    TRY(stream.write_bits(true, 1));

     // Delay Time
     TRY(stream.write_value<u16>(duration_ms / 10));

produces this gif, which seems to work:

(It even fixes the transparency outside the round rect.)

But it looks like it might work at least partially by coincidence, since GIFWriter doesn't have explicit code for handling transparency. So I'm leaving gif writing support for this technique for the future.

(The gif with the two tweaks above is 228K, compared to 435K produced without them, so this is a good win for gif encoding too – also brings output size at least in the ballpark of the input size.)