Quality loss when quantizing an image that already has (fewer than) 256 colors

[pwitvoet]

Prerequisites

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

ImageSharp version

3.1.6

Other ImageSharp packages and versions

n/a

Environment (Operating system, version and so on)

Windows 10

.NET Framework version

.NET 8

Description

I've been saving 256-color images as 8-bit indexed pngs, gifs and bmps, using a PaletteQuantizer. In theory, they should not be negatively affected by quantization, because the images already contain 256 or fewer colors. In practice, I'm occasionally seeing quality loss, with output images not making use of the full palette.

This appears to be caused by the EuclideanPixelMap (specifically its ColorDistanceCache) that PaletteQuantizer is using. The color distance cache is lopping off the lowest 3 bits of the RGB values, which is quite troublesome for gradients. From the discussion in #1350 I understand that this is a memory usage optimization, but in my case a simple dictionary would work just fine, because all colors are already present in the palette anyway. If a trade-off has to be made, perhaps it should be configurable?

I also know that it's possible to create a custom IQuantizer implementation, but there are two problems with that:

• IndexedImageFrame<TPixel> doesn't have a public constructor. It's possible to create an instance using reflection, but that's brittle.
• For images with multiple frames, PngEncoderCore and GifEncoderCore only use the given quantizer for the first frame. For subsequent frames, they use a PaletteQuantizer, which re-introduces the quality loss problem.

---

What I actually want to achieve is a bit more strict: I want to preserve the exact index data of the original image, even when a palette contains duplicate colors. I don't expect a standard quantizer to handle such a niche scenario, but it would be very useful if encoders would use the given quantizer for all frames, not just the first frame.

Steps to Reproduce

// Create a grayscale palette (or any other palette with colors that are very close to each other):
var palette = Enumerable.Range(0, 256).Select(i => new Rgba32((byte)i, (byte)i, (byte)i)).ToArray();

// Create an image with a smooth black-white gradient:
using var image = new Image<Rgba32>(254, 4);
for (int y = 0; y < image.Height; y++)
    for (int x = 0; x < image.Width; x++)
        image[x, y] = palette[x];

// Correct result, for comparison:
image.Save(@"C:\Documents\temp\test_images\gradient.png");

// Banded gradient, uses only 32 colors instead of the full palette:
image.Save(@"C:\Documents\temp\test_images\gradient_8bit.png", new PngEncoder {
    ColorType = PngColorType.Palette,
    BitDepth = PngBitDepth.Bit8,
    Quantizer = new PaletteQuantizer(palette.Select(Color.FromPixel).ToArray())
});

// The same problem occurs when saving as an 8-bit bmp or gif file.

Images

Expected output:

Actual output (zoom in to see the banding):

[JimBobSquarePants]

Hi @pwitvoet I've converted this into a discussion because the library is working as designed. Thanks for providing such an excellent summary. It's actually something I've been thinking about recently.

Just a few notes on your comments:

• IndexedImageFrame<TPixel> doesn't have a public constructor. It's possible to create an instance using reflection, but that's brittle.

You shouldn't need to use this constructor. If you look at other quantizer implementations they defer the creation of the type to QuantizerUtilities.

• For images with multiple frames, PngEncoderCore and GifEncoderCore only use the given quantizer for the first frame. For subsequent frames, they use a PaletteQuantizer, which re-introduces the quality loss problem.

Yes, that's not great at the moment but I don't think I can make that configurable.

I have plans to improve the bit preservation in the pixel map by replacing the current cache with a hybrid cache that stores the first 65536 unique colors in the image using full fidelity and falls back to the current implementation if not found. That would fix your issue, but I need to benchmark this to make sure it's usable.

Proposed implementation

using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using SixLabors.ImageSharp.PixelFormats;
using SixLabors.Memory;

public unsafe struct HybridColorDistanceCacheRGBA : IDisposable
{
    private const int IndexRBits = 5;
    private const int IndexGBits = 5;
    private const int IndexBBits = 5;
    private const int IndexABits = 6;
    private const int IndexRCount = 1 << IndexRBits; // 32 bins for red
    private const int IndexGCount = 1 << IndexGBits; // 32 bins for green
    private const int IndexBCount = 1 << IndexBBits; // 32 bins for blue
    private const int IndexACount = 1 << IndexABits; // 64 bins for alpha
    private const int TotalBins = IndexRCount * IndexGCount * IndexBCount * IndexACount; // 1,048,576 bins

    private readonly IMemoryOwner<short> fallbackTable;
    private readonly short* fallbackPointer;
    private MemoryHandle fallbackHandle;

    private readonly Dictionary<int, short> hashTable;
    private readonly int maxHashSize; // Maximum size for the hash table

    public HybridColorDistanceCacheRGBA(MemoryAllocator allocator, int maxHashSize = 65536)
    {
        this.fallbackTable = allocator.Allocate<short>(TotalBins);
        this.fallbackTable.GetSpan().Fill(-1);
        this.fallbackHandle = this.fallbackTable.Memory.Pin();
        this.fallbackPointer = (short*)this.fallbackHandle.Pointer;

        this.hashTable = new Dictionary<int, short>(maxHashSize);
        this.maxHashSize = maxHashSize;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Add(Rgba32 color, short index)
    {
        int hash = GetHash(color);
        if (this.hashTable.Count < this.maxHashSize)
        {
            this.hashTable.TryAdd(hash, index);
        }

        int coarseIndex = GetCoarseIndex(color);
        this.fallbackPointer[coarseIndex] = index;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool TryGetValue(Rgba32 color, out short match)
    {
        if (this.hashTable.TryGetValue(GetHash(color), out match))
        {
            return true; // Exact match found
        }

        match = this.fallbackPointer[GetCoarseIndex(color)];
        return match > -1; // Coarse match found
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int GetHash(Rgba32 color)
    {
        /*
         * Improved hash function for better distribution:
         * The constants used here (73856093, 19349663, 83492791, 113429371) are prime numbers.
         * Multiplying the color channels by these primes helps in achieving a uniform distribution
         * of hash values by reducing collisions when colors differ slightly.
         * This approach ensures that similar colors produce different hash values, improving hash table performance.
         */
        return (color.R * 73856093) ^ (color.G * 19349663) ^ (color.B * 83492791) ^ (color.A * 113429371);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int GetCoarseIndex(Rgba32 color)
    {
        int rIndex = color.R >> (8 - IndexRBits);
        int gIndex = color.G >> (8 - IndexGBits);
        int bIndex = color.B >> (8 - IndexBBits);
        int aIndex = color.A >> (8 - IndexABits);

        return (aIndex * IndexRCount * IndexGCount * IndexBCount) +
               (rIndex * IndexGCount * IndexBCount) +
               (gIndex * IndexBCount) +
               bIndex;
    }

    public void Clear()
    {
        this.hashTable.Clear();
        this.fallbackTable.GetSpan().Fill(-1);
    }

    public void Dispose()
    {
        if (this.fallbackTable != null)
        {
            this.fallbackHandle.Dispose();
            this.fallbackTable.Dispose();
        }
    }
}

[pwitvoet]

Ah yes, I did see QuantizerUtilities.QuantizeFrame. I must've forgotten about it because it's doing a lot more than just creating an indexed frame instance, and the way it's doing quantization doesn't fit my use case.

There are a few cases where quantization isn't just mapping one color to another:

• If you already have index data and a palette, it's more efficient and accurate to use that index data directly. I've been saving dummy images with a custom 'quantizer' that contains the actual index data: https://github.com/pwitvoet/wadmaker/blob/master/Shared/FileFormats/Indexed/IndexedImageSavingQuantizer.cs This solves the quality/accuracy problem I was running into, but I do consider it to be a bit of a hack, and it doesn't work for multi-frame images.
• In some applications, specifically some older games, palette indices can have a special meaning, such as being transparent, or always being rendered at full brightness, or being remapped to a team-specific color, and so on. The color of a pixel may not always provide enough information to determine the palette index.

---

As for using the same quantizer for all frames that use the same palette, I think there are several benefits:

• It allows the above special cases to be handled correctly.
• It's potentially more efficient, because any caching done by the quantizer when building the palette can be reused for subsequent frames. Using a new PaletteQuantizer<TPixel> for subsequent frames means building a new pixel map cache.
• I think it matches how one would expect a quantizer to be used - to quantize all frames, not just to build a palette.

So I decided to see how difficult it would be to change the png and gif encoders. The main issue I encountered is that GifEncoderCore needs a quantizer with a SetTransparentIndex method, which is currently only offered by PaletteQuantizer<TPixel>. So that method would need to be added to IQuantizer<TPixel> and to all quantizers that implement that interface, which might complicate them somewhat. Other than that, it seemed fairly straightforward to reuse the same quantizer instance. But I took some shortcuts and I'm not familiar with all the decisions behind this code, so I might be overlooking something important.

---

Regarding your hybrid color distance cache, that looks useful. Maybe PaletteQuantizer could have a max hash size setting so users can make their own trade-offs between accuracy and memory usage?

Oh, you shouldn't use hashes as keys, because hash collisions will cause incorrect matches (for example, try adding RGB(254, 253, 224) and then looking up RGB(70, 61, 120)). You'll have to construct the dictionary with a custom IEqualityComparer if you want a custom hash function.