Ability to cache using rgba8888 in applyPalette?

[davepagurek]

Hi! Firstly, thanks for this library, it's really useful!

I've noticed some flickering that can happen in outputted gifs. Given images generated from this p5 sketch, I get output gifs like this:

I've narrowed this down to the applyPalette function. What I believe is happening is this:

• applyPalette caches palette indices based on a hash of the color, which depends on the format you pass in
• Multiple input colors map to the same cache index because the format reduces the number of bits. These colors might not map to the same palette index.
• The output palette index depends on which of the set of colors resulting in the same cache index is encountered first
• The first encountered color for one cache index might change from frame to frame, which is causing flickering

I'm dealing with the flickering by effectively writing my own version of applyPalette which caches based on the full 8-bit-per-channel color:

const getIndexedFrame = frame => {
  const paletteCache = {};
  const length = frame.length / 4;
  const index = new Uint8Array(length);
  for (let i = 0; i < length; i++) {
    const key =
      (frame[i * 4] << 24) |
      (frame[i * 4 + 1] << 16) |
      (frame[i * 4 + 2] << 8) |
      frame[i * 4 + 3];
    if (paletteCache[key] === undefined) {
      paletteCache[key] = nearestColorIndex(
        globalPalette,
        frame.slice(i * 4, (i + 1) * 4)
      );
    }
    index[i] = paletteCache[key];
  }
  return index;
};

This results in an output like this:

Anyway, just putting my discovery here in case something like this would be helpful to include in the library! An alternate way of dealing with the flickering might be to find the nearest palette index based on the bit-truncated color as opposed to the source color.

[cdaein]

I had a similar issue, and here is what I've tried.

When using the library's functions, I get a flicker:

const palette = quantize(data, 256);
const index = applyPalette(data, palette);

I tried @davepagurek 's solution, but it only showed a single color (on github, it looks black, but when i open the same file on my machine, it is the gray background color):

const palette = quantize(data, 256);
const index = getIndexedFrame(data, palette);

What worked for me was to reduce maxColors down:

const palette = quantize(data, 4);
const index = applyPalette(data, palette);

[mattdesl]

So, I'm looking into this a bit today.

The reason I didn't use full uint32 as keys is that it's very slow (500ms to 5seconds type of slow). I think it would be worth keeping it as an option, although part of the reason for the modularity of this library is to allow users to choose their own quantization functions (which might be more accurate but much slower).

Another approach that is worth exploring, aside from reducing color counts, is to use dithering. In the latest dev branch you can see a p5 test (serve the root dir, then open /test/p5) with dithering. I might add this dither function in the next version.

I also wonder if there is any other better way of searching/indexing colors that do not reduce bit depth or that are able to maintain some choices across frames. I think gifenc is due for a litttle overhaul at some point, cleaning up some of the code and maybe introducing perceptual color difference functions that are already present in the source code but not exposed to the library.

[davepagurek]

The reason I didn't use full uint32 as keys is that it's very slow

This makes sense! And like you mentioned, using our own function instead of applyPalette was pretty quick to implement, so that's a testament to the design of this library 🙂

Another approach that is worth exploring, aside from reducing color counts, is to use dithering.

Your output image looks great! I suppose this might still potentially have flickering, but due to the dithering breaking up large bands of color, it would be less likely to occur in large areas like in my original gif? That seems like a good compromise between speed and output quality.

I also wonder if there is any other better way of searching/indexing colors that do not reduce bit depth or that are able to maintain some choices across frames.

A potentially quick fix might be to let users pass a cache into applyPalette as a parameter rather than always creating a new one. The cache is already the size of the full spectrum of representable colors, so it wouldn't keep growing like the full-size color cache I added to p5's main branch, which I worry about a bit.

[otizis]

I had a similar issue, and here is what I've tried.

When using the library's functions, I get a flicker:

const palette = quantize(data, 256);
const index = applyPalette(data, palette);

I tried @davepagurek 's solution, but it only showed a single color (on github, it looks black, but when i open the same file on my machine, it is the gray background color):

const palette = quantize(data, 256);
const index = getIndexedFrame(data, palette);

What worked for me was to reduce maxColors down:

const palette = quantize(data, 4);
const index = applyPalette(data, palette);

you might quantize data use foramt not transparent, like default 'rgb565'. so when use nearestColorIndex fun the 2nd params is 3 length array. modify davepagurek's code like this:

paletteCache[key] = nearestColorIndex(
        globalPalette,
        frame.slice(i *4 , ((i + 1) * 4) - 1)
      );

with all i*4 tmp in s, will like this

const getIndexedFrame = frame => {
  const paletteCache = {};
  const length = frame.length / 4;
  const index = new Uint8Array(length);
  for (let i = 0; i < length; i++) {
    const s = i*4
    const key =
      (frame[s] << 24) |
      (frame[s + 1] << 16) |
      (frame[s + 2] << 8) |
      frame[s + 3];
    if (paletteCache[key] === undefined) {
      paletteCache[key] = nearestColorIndex(
        globalPalette,
        frame.slice(s, s+3)
      );
    }
    index[i] = paletteCache[key];
  }
  return index;
};

transparent format is frame.slice(s, s+4)

[otizis]

In my scenario, adding a byte on the end of 4 bytes in the cache key base on @davepagurek code. result image no longer flickering and the generation speed was acceptable .

            const length = imageData.data.length / 4;
            const index = new Uint8Array(length);
            for (let i = 0; i < length; i++) 
            {
                const s = i*4;
                const key =
                    ((imageData.data[s] >>3)<<20) |
                    ((imageData.data[s + 1] >>3)<<15)|
                    ((imageData.data[s + 2] >>3)<<10) |
                    (imageData.data[s + 3] >>3);
                if (paletteCache[key] === undefined) {
                    paletteCache[key] = nearestColorIndex(firstPalette,imageData.data.slice(s, s+ (transparent?4:3)));
                }
              index[i] = paletteCache[key];
            }

before

after