cgifsave: palette change POC #2824

DarthSim · 2022-05-27T07:25:01Z

Hey!

This is the POC of my approach to generating palettes for cgifsave. How it works:

We compute a palette for each frame. The first frame's palette we use as a global one.
For each frame except the first we compare the palette computed in step 1 with the global palette and the local palette of the previous frame (if any).
If there's a local palette in the previous frame, and the diff between it and the current frame palette is small enough, we use the palette from the previous frame as local for the current frame.
Otherwise, if the diff between the global palette and the current frame palette is small enough, we don't use a local palette.
Otherwise, we use the palette computed in step 1 as a local palette for the current frame.

With this approach, we mitigate the difference between neighbor frame colors which helps transparency and frame optimizers do their jobs.

Some numbers:

Master speeed:

$ /usr/bin/time -f %M:%e vips copy /images/animated_gif12.gif[n=-1] /images/animated_gif12_vips_out_master.gif[reoptimise=1]
40344:5.21

$ /usr/bin/time -f %M:%e vips copy /images/animated_gif13.gif[n=-1] /images/animated_gif13_vips_out_master.gif[reoptimise=1]
32552:5.33

$ /usr/bin/time -f %M:%e vips copy /images/animated_gif15.gif[n=-1] /images/animated_gif15_vips_out_master.gif[reoptimise=1]
27096:3.36

$ /usr/bin/time -f %M:%e vips copy /images/animated_gif16.gif[n=-1] /images/animated_gif16_vips_out_master.gif[reoptimise=1]
41744:2.18

New speeed:

$ /usr/bin/time -f %M:%e vips copy /images/animated_gif12.gif[n=-1] /images/animated_gif12_vips_out_new.gif[reoptimise=1]
40340:4.98

$ /usr/bin/time -f %M:%e vips copy /images/animated_gif13.gif[n=-1] /images/animated_gif13_vips_out_new.gif[reoptimise=1]
32972:5.11

$ /usr/bin/time -f %M:%e vips copy /images/animated_gif15.gif[n=-1] /images/animated_gif15_vips_out_new.gif[reoptimise=1]
26884:3.28

$ /usr/bin/time -f %M:%e vips copy /images/animated_gif16.gif[n=-1] /images/animated_gif16_vips_out_new.gif[reoptimise=1]
41592:2.06

Result sizes

Here I resized the images a bit to increase the color number.

$ ls -l /images/animated_gif*_vips_out_*
-rw-r--r-- 1 *** ***   687545 May 27 06:34 /images/animated_gif12_vips_out_master.gif
-rw-r--r-- 1 *** ***   631936 May 27 06:50 /images/animated_gif12_vips_out_new.gif
-rw-r--r-- 1 *** ***  1051173 May 27 06:34 /images/animated_gif13_vips_out_master.gif
-rw-r--r-- 1 *** ***   997631 May 27 06:50 /images/animated_gif13_vips_out_new.gif
-rw-r--r-- 1 *** ***  3355198 May 27 06:51 /images/animated_gif15_vips_out_master.gif
-rw-r--r-- 1 *** ***  3320212 May 27 06:50 /images/animated_gif15_vips_out_new.gif
-rw-r--r-- 1 *** *** 14747250 May 27 06:35 /images/animated_gif16_vips_out_master.gif
-rw-r--r-- 1 *** *** 14557252 May 27 06:51 /images/animated_gif16_vips_out_new.gif

Findings

As we see, the memory footprint is more or less the same for both approaches, yet my approach is slightly faster and produces slightly smaller files. Also, this approach doesn't have a frame size limitation.

libvips/foreign/cgifsave.c

jcupitt · 2022-05-27T13:28:34Z

Oh, nice! It seems to work well on the test images I tried. @dloebl, any thoughts?

libvips/foreign/cgifsave.c

dloebl · 2022-05-30T11:50:27Z

libvips/foreign/cgifsave.c

+
+				best_dist = VIPS_MIN(best_dist, dist);
+
+				/* We fond the closest entry


Typo: fond -> found

Thanks, fixed

dloebl · 2022-05-30T12:01:00Z

libvips/foreign/cgifsave.c

-		if( cgif->frame_checksum == 0 ||
-			checksum != cgif->frame_checksum ) { 
-			cgif->frame_checksum = checksum;
+		static double pal_change_threshold = 64.0;


This method seems to be similar to the way the maxerror parameter is handled right now: cgifsave.c#L177
We could make the threshold dynamic (e.g. use maxerror here) and set maxerror to a value > 0 by default.

I don't think maxerror fits well here. For example, 64 is a good value for the inter-palette error while it is too large for the inter-frame error. Yet I agree that this number should be dynamic. Maybe we should rename maxerror to, for example, interframe_maxerror and add a new param for inter-palette max error.

Made it dynamic and renamed maxerror. If everything is ok, I'll squash the commits. /cc @jcupitt

dloebl · 2022-05-30T12:05:58Z

Looks like a nice improvement to me 👍
I've added some comments inline.

jcupitt · 2022-06-01T11:53:50Z

I'm seeing some errors with video clips -- it's tagging pixels as transparent when they should all stay solid. Perhaps dispose isn't always being set correctly?

DarthSim · 2022-06-04T08:51:55Z

Could you give a sample, please? I have like 16 test GIFs, and all of them work fine.

jcupitt · 2022-06-04T09:40:19Z

Sorry, it's not a GIF I can share :( I'm trying to find another example, but no luck so far.

Let's fix this up and merge it, then try to resolve any fails in another PR.

jcupitt · 2022-06-06T11:24:00Z

Hi, shall I fix the merge conflict?

jcupitt · 2022-06-06T19:57:12Z

I made a GIF I can share that fails.

This terrible GIF:

http://www.rollthepotato.net/~john/skate.gif

Converted using this branch:

$ vips copy skate.gif[n=-1] x.gif

Becomes:

http://www.rollthepotato.net/~john/x.gif

It looks like every pixel which is equal to the previous pixel becomes transparent in the output, which causes a lot of artefacts at the start of the clip.

DarthSim · 2022-06-07T07:08:57Z

Rebased and squashed the branch.

I made a GIF I can share that fails.

Oh, thank you! I'll dig it.

DarthSim · 2022-06-07T10:47:26Z

I've tested vips copy built from this branch, and I didn't get any artifacts: http://img.darthsim.me/ufHVruZ3o2.gif. I've tested it with both Quantizr and LIQ from the Debian package.

@jcupitt could you test it again on your end? Maybe it was fixed after the rebase?

jcupitt · 2022-06-07T11:14:14Z

I wiped everything and rebuilt, and I see still bad artefacts.

Could it be the cgif version? I'm using git master.

dloebl · 2022-06-07T13:39:04Z

Maybe it's similar to the issue mentioned here?
I can reproduce the artefact with libimagequant 2.17 - but only if dithering is enabled. With Quantizr/libimagequant 4.0 the issue is gone on my side.

DarthSim · 2022-06-07T14:04:13Z

@dloebl That's it, thank you! I'll try to fix it.

DarthSim · 2022-06-07T14:24:12Z

Also I noticed that these pixels are not transparent but just grey. And, as Daniel said, artifacts appear only when dithering is enabled. So I believe it's a bug in LIQ 2.17 itself, and we can do nothing with it.

jcupitt · 2022-06-07T14:34:21Z

Ah good spot.

But these artefacts only appear with this branch -- master seems to work fine. I think something in this PR has triggered this behaviour.

DarthSim · 2022-06-07T15:58:38Z

But these artefacts only appear with this branch -- master seems to work fine. I think something in this PR has triggered this behaviour.

Master uses local palette for basically every frame while this branch doesn't use a local palette when reusing a global one. I noticed that LIQ 2.17 changes palette a lot during remapping, which is not good for us. AFAIK the only way to bypass this is using the histogram API, which is basically what liq_image_quantize does. But fork by @lovell doesn't have such API :(

DarthSim · 2022-06-07T16:14:22Z

BTW it seems like the same problem may occur when we reuse the global palette from the source image, too.

jcupitt · 2022-06-08T09:08:00Z

Perhaps we should merge, and then try to find a workaround for this in another PR. What do you think?

DarthSim · 2022-06-08T10:32:36Z

It seems like I fixed it! I added the vips__quantise_image_quantize_fixed method that does the following:

Quantizes the image and gets the palette.
Creates a fake 1-pixel image and adds all the colors from the palette to it as fixed colors. Fixed colors won't be changed during the remapping.
Quantizes the fake image and returns the result.

Somehow code with this hack works even faster than without it. Probably because LIQ doesn't change the palette.

jcupitt · 2022-06-08T14:27:04Z

That's great! All my tests pass too, well done.

I see some small leaks in valgrind, but maybe that's just libimagequant. Let's merge and maybe try to patch them in another PR.

jcupitt · 2022-06-08T15:28:53Z

I did a quick benchmark against imagemagick:

$ /usr/bin/time -f %M:%e vipsthumbnail 3198.gif[n=-1] -o vips-13.gif --size 224
57344:0.62
$ /usr/bin/time -f %M:%e convert 3198.gif -resize 75% im.gif
200796:6.44
$ ls -l im.gif vips-13.gif 
-rw-rw-r-- 1 john john 3176859 Jun  8 16:26 im.gif
-rw-r--r-- 1 john john 2487189 Jun  8 16:25 vips-13.gif

So for this GIF at least (a short video clip) libvips is now 10x faster, needs 4x less memory, and makes GIFs which are 20% smaller!

Nice work everyone.

jcupitt · 2022-06-08T15:31:17Z

.... and the dithering of the libvips one is better too, so they look nicer.

jcupitt · 2022-06-08T15:35:52Z

Against libvips 8.12:

$ /usr/bin/time -f %M:%e vipsthumbnail 3198.gif[n=-1] -o vips-12.gif --size 224
57764:3.96
$ ls -l vips-12.gif
-rw-r--r-- 1 john john 3441032 Jun  8 16:34 vips-12.gif

DarthSim force-pushed the feature/gif-palette-change-poc branch 2 times, most recently from e1bb183 to 712f057 Compare May 27, 2022 13:26

jcupitt reviewed May 27, 2022

View reviewed changes

libvips/foreign/cgifsave.c Outdated Show resolved Hide resolved

DarthSim force-pushed the feature/gif-palette-change-poc branch 2 times, most recently from 26929fa to 420bcd4 Compare May 27, 2022 14:00

DarthSim marked this pull request as ready for review May 27, 2022 14:39

DarthSim force-pushed the feature/gif-palette-change-poc branch 2 times, most recently from 0ea45c8 to e97850e Compare May 27, 2022 17:11

kleisauke reviewed May 30, 2022

View reviewed changes

libvips/foreign/cgifsave.c Show resolved Hide resolved

DarthSim force-pushed the feature/gif-palette-change-poc branch from e97850e to c7a24b8 Compare May 30, 2022 11:43

dloebl reviewed May 30, 2022

View reviewed changes

DarthSim force-pushed the feature/gif-palette-change-poc branch 2 times, most recently from 5bb685e to a819f16 Compare May 30, 2022 13:52

cgifsave: compare palettes instead of frame sum

62000a9

DarthSim force-pushed the feature/gif-palette-change-poc branch from a819f16 to 62000a9 Compare June 7, 2022 07:07

Add vips__quantise_image_quantize_fixed function

915ab49

jcupitt merged commit 19bef95 into libvips:master Jun 8, 2022

kleisauke mentioned this pull request Jun 13, 2022

cgifsave: number of colours in palette is one less than it could/should be #2852

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cgifsave: palette change POC #2824

cgifsave: palette change POC #2824

DarthSim commented May 27, 2022

jcupitt commented May 27, 2022

dloebl May 30, 2022

DarthSim May 30, 2022

dloebl May 30, 2022

DarthSim May 30, 2022 •

edited

Loading

DarthSim May 30, 2022

dloebl commented May 30, 2022

jcupitt commented Jun 1, 2022

DarthSim commented Jun 4, 2022

jcupitt commented Jun 4, 2022

jcupitt commented Jun 6, 2022

jcupitt commented Jun 6, 2022 •

edited

Loading

DarthSim commented Jun 7, 2022

DarthSim commented Jun 7, 2022

jcupitt commented Jun 7, 2022

dloebl commented Jun 7, 2022

DarthSim commented Jun 7, 2022

DarthSim commented Jun 7, 2022

jcupitt commented Jun 7, 2022

DarthSim commented Jun 7, 2022

DarthSim commented Jun 7, 2022

jcupitt commented Jun 8, 2022

DarthSim commented Jun 8, 2022

jcupitt commented Jun 8, 2022 •

edited

Loading

jcupitt commented Jun 8, 2022

jcupitt commented Jun 8, 2022

jcupitt commented Jun 8, 2022


		best_dist = VIPS_MIN(best_dist, dist);

		/* We fond the closest entry

cgifsave: palette change POC #2824

cgifsave: palette change POC #2824

Conversation

DarthSim commented May 27, 2022

Some numbers:

Master speeed:

New speeed:

Result sizes

Findings

jcupitt commented May 27, 2022

dloebl May 30, 2022

Choose a reason for hiding this comment

DarthSim May 30, 2022

Choose a reason for hiding this comment

dloebl May 30, 2022

Choose a reason for hiding this comment

DarthSim May 30, 2022 • edited Loading

Choose a reason for hiding this comment

DarthSim May 30, 2022

Choose a reason for hiding this comment

dloebl commented May 30, 2022

jcupitt commented Jun 1, 2022

DarthSim commented Jun 4, 2022

jcupitt commented Jun 4, 2022

jcupitt commented Jun 6, 2022

jcupitt commented Jun 6, 2022 • edited Loading

DarthSim commented Jun 7, 2022

DarthSim commented Jun 7, 2022

jcupitt commented Jun 7, 2022

dloebl commented Jun 7, 2022

DarthSim commented Jun 7, 2022

DarthSim commented Jun 7, 2022

jcupitt commented Jun 7, 2022

DarthSim commented Jun 7, 2022

DarthSim commented Jun 7, 2022

jcupitt commented Jun 8, 2022

DarthSim commented Jun 8, 2022

jcupitt commented Jun 8, 2022 • edited Loading

jcupitt commented Jun 8, 2022

jcupitt commented Jun 8, 2022

jcupitt commented Jun 8, 2022

DarthSim May 30, 2022 •

edited

Loading

jcupitt commented Jun 6, 2022 •

edited

Loading

jcupitt commented Jun 8, 2022 •

edited

Loading