Separate formats from dithering?

[Artoria2e5]

I am a bit interested in getting a somewhat simple description of the cool new "scatter" algorithm, but the way it's duplicated in AnimatedGif and PNG8 is... not nice, I guess. Would it make more sense to make a shared function with a signature somewhat like the following to do all the dither instead?

public byte[] dither(int[] image, int width, PaletteReducer pr, DitherAlgorithm da) {
  // ...
  return indexedPixels;
}

[Artoria2e5]

Hmmm, they are actually in PaletteReducer already. I guess it's a case of inlining? Okay.

[tommyettinger]

Yeah, it's mostly like inlining, except in a few key places where it didn't make sense to duplicate almost all of the method but make a few parts specific to PNG8 or GIF. The animation code in particular has to track the current frame for some, but not all, dithering algorithms, and PaletteReducer doesn't have any concept of the current frame.

Also, I think I can explain Scatter a little better than how it currently is in DitherAlgorithm, let's see... Broadly, it's Floyd-Steinberg error diffusion, but it adjusts that error up or down using blue noise, so it breaks up patterns in Floyd-Steinberg in a visually-preferable way. Specifically, it uses triangular-mapped blue noise, which produces more noise results in the center of the range (causing less adjustment of error) than noise at either extreme. At the end, there's an interesting step that exaggerates the diffusion of error but not the current pixel's color; this uses a method that can be thought of as an extremely rough approximation of cube root, and it only needs to be approximate because only the general shape of the function matters, not its precise values. The number 0x2.Ep-8f is used there; it's the same as 2.875f / 256.0f, and it's multiplied by a current error value between -255 and 255. That number is something I adjusted so it tends to push the diffused error to at most maybe 1.5 (depending on how imprecise the cbrtShape() method is), and is less often in the center of the range. Keeping diffused error relatively high helps make the dithering a little more pixel-art-like, with lots of balancing light and dark pixels nearby each other.

Scatter has some artifact issues when the palette is small and dither strength is high; there are probably some ways to resolve this, but I'm not sure what they are yet. These artifacts appear as horizontal lines of contrasting color, and I think they're caused by over-correcting for one very high or low value at the start of the row.

If you want to experiment with changing Scatter, good places to start might be adjusting various constants, simplifying TRI_BLUE_NOISE_MULTIPLIERS, or changing how diffused error starts on each new row.

Constants like 0x2Ep-8f could be changed to whatever looks good to you, and that could vary based on the style of image you're dithering or its palette size. The dither strength value is adjusted differently for each dithering algorithm, and you may find you prefer some particular strength more.

The TRI_BLUE_NOISE_MULTIPLIERS values are calculated with... uh... (float) Math.exp(OtherMath.probit((PaletteReducer.TRI_BLUE_NOISE[i] + 128.5) * 0x1p-8) * 0.5). So splitting that up, (PaletteReducer.TRI_BLUE_NOISE[i] + 128.5) * 0x1p-8 gets a standard triangular blue noise value from a large precalculated array (it's a byte), adds 128.5 to put it in the 0.5 to 255.5 range, and multiplies by 0x1p-8 (which is 1.0/256.0) to give a value between 1.0/512.0. and 511.0/512.0. That value is triangular-mapped, so it is most often in the center, near 0.5. That is given to probit(), which is an uncommon but useful approximation. The probit function is like a remapping from the 0-1 range (both exclusive) to the range of a normal-distributed variable (that is, a bell curve, centered on 0.0). The one we have here can go (in this case) between -2.885634913355785 and 2.885634913355785, and won't ever produce exactly 0. Using probit makes the already-triangular-mapped noise even more centrally-biased. We then multiply the result of probit() by 0.5 to bring it closer to 0 on both sides, and give that to Math.exp(). We use Math.exp() to get a multiplier (instead of just adding to 1.0) because the results of probit() on blue noise are perfectly balanced on either side of 0.0, with as many positive as negative and by an equal amount. If you multiply by Math.exp(0.1), or 1.1051709180756477, then balance that out by multiplying by Math.exp(-0.1), you get exactly 1.0. This makes using these numbers as multipliers essentially balanced in how they affect error.

Changing how error gets diffused could be the most promising angle, but it's also the one I understand the least. I think something is wrong with all of the error-diffusion-based dithers when the dither strength is too high, but I don't really know why the linear "streak" artifacts occur.

I hope that helps!