Diffuser modifies quantized image with same palette

Prerequisites

[x] I have written a descriptive issue title
[x] I have verified that I am running the latest version of ImageSharp
[x] I have verified if the problem exist in both DEBUG and RELEASE mode
[x] I have searched open and closed issues to ensure it has not already been reported

Description

Running the ErrorDiffusionPaletteProcessor on a quantized image with the same palette that was used for quantization modifies the image. This is not desirable since the point of dithering is to improve visual fidelity with the limited palette, while in this case a perfectly faithful quantized image is modified and image quality is degraded.

Of course a dithering algorithm can't work well for 100% of cases, but bad quality on perfectly quantized images can prove an issue in practice. With a two-pass quantization algorithm on an image with few distinct colors this results in bad image quality.

The code responsible is here:

pair = this.GetClosestPixelPair(ref sourcePixel, this.Palette);
sourcePixel.ToRgba32(ref rgba);
luminance = isAlphaOnly ? rgba.A : (.2126F * rgba.R) + (.7152F * rgba.G) + (.0722F * rgba.B);
TPixel transformedPixel = luminance >= threshold ? pair.Second : pair.First;

Since all references I found just got the closest color in the palette, I tried changing the implementation to get only the closest color. I didn't see worse visual quality in the test images I ran the diffusion on, though I must say I don't have a trained eye (and I guess this might be subjective too).

The single-pixel implementation also provides a major performance benefit compared to the current implementation. When dithering we can check if there is no error and skip the dither for the pixel. For images that have few colors or all colors in the palette this provides a major speed boost. I added some tests to the benchmark project with 3 images; the lake image from the test set (lots of colors), the lake image quantized with 256 colors and processed with a palette of 128 colors, and the lake image quantized and processed with the full quantization palette.

BenchmarkDotNet=v0.10.14, OS=Windows 10.0.17134
Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical and 4 physical cores
Frequency=2531252 Hz, Resolution=395.0614 ns, Timer=TSC
.NET Core SDK=2.1.300
  [Host]     : .NET Core 2.0.7 (CoreCLR 4.6.26328.01, CoreFX 4.6.26403.03), 64bit RyuJIT
  DefaultJob : .NET Core 2.0.7 (CoreCLR 4.6.26328.01, CoreFX 4.6.26403.03), 64bit RyuJIT

Results before:

Method	Mean	Error	StdDev
'Diffuse Floyd-Steinberg'	855.4 ms	13.092 ms	11.605 ms
'Diffuse Floyd-Steinberg Half Palette'	505.2 ms	9.932 ms	13.258 ms
'Diffuse Floyd-Steinberg Full Palette'	432.3 ms	7.358 ms	6.883 ms

Results after:

Method	Mean	Error	StdDev
'Diffuse Floyd-Steinberg'	781.52 ms	14.6853 ms	15.081 ms
'Diffuse Floyd-Steinberg Half Palette'	444.98 ms	8.5997 ms	10.876 ms
'Diffuse Floyd-Steinberg Full Palette'	34.39 ms	0.6747 ms	1.089 ms

My branch with the benchmark added (under Processing/Dither.cs) can be found at Jjagg/ImageSharp/diffuse-palette.

Steps to Reproduce

In the sample code below I used the jpeg444.jpg that's included in the test folder. It looks like this: jpeg444

The sample uses the web palette quantizer. It can be run in the Sandbox project.

var path = Path.Combine(TestEnvironment.InputImagesDirectoryFullPath, TestImages.Jpeg.Baseline.Jpeg444);

var image = Image.Load<Rgba32>(path);

var frameQuantizer = new PaletteQuantizer(false).CreateFrameQuantizer<Rgba32>();

var quantizedFrame = frameQuantizer.QuantizeFrame(image.Frames[0]);
var quantized = QuantizedFrameToImage(quantizedFrame);

var diffused = quantized.Clone(c => c.Diffuse(KnownDiffusers.FloydSteinberg, .5f, quantizedFrame.Palette));
ImageComparer.Exact.VerifySimilarity(quantized, diffused); // I expected this to hold

After quantization: quantized

After diffusion: diffused

System Configuration

ImageSharp version: 0d179d624201d37d5b32d592eeda831bc12f01f3

SixLabors / ImageSharp