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.

[JimBobSquarePants]

Man... Oh man... Have I spent some time on this. It turns out implementing such a thing but keeping it fast is hard!

Here's what I've come up with. It 1.4x - 2x slower than the current approach depending on the number of collisions but will give you your accuracy for the first 256 colors.

Proposed implementation

    /// <summary>
    /// A hybrid cache for color distance lookups that combines an exact-match dictionary with
    /// a fallback coarse lookup table.
    /// </summary>
    /// <remarks>
    /// This cache uses a fallback table with 1,048,576 bins, each storing a 2-byte value
    /// (approximately 2 MB total), while the exact-match dictionary is limited to 256 entries
    /// and occupies roughly 4 KB. Overall, the worst-case memory usage is about 2 MB.
    /// Lookups and insertions are performed in constant time (O(1)) because the fallback table
    /// is accessed via direct indexing and the dictionary employs a simple hash-based bucket mechanism.
    /// The design achieves extremely fast color distance lookups with a predictable, fixed memory footprint.
    /// </remarks>
    // https://github.com/dotnet/roslyn-analyzers/issues/6151
#pragma warning disable CA1001 // Types that own disposable fields should be disposable
    public unsafe struct HybridColorDistanceCache : IDisposable
#pragma warning restore CA1001 // Types that own disposable fields should be disposable
    {
        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 FixedDictionary256 hashTable;
        private readonly int maxHashSize; // Maximum size for the hash table

        public HybridColorDistanceCache(MemoryAllocator allocator, int maxHashSize = 256)
        {
            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 FixedDictionary256(allocator);
            this.maxHashSize = maxHashSize;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public readonly void Add(Rgba32 color, short index)
        {
            if (this.hashTable.TryAdd(color.PackedValue, index))
            {
                return;
            }

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

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

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

        [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 readonly void Clear()
        {
            this.hashTable.Clear();
            this.fallbackTable.GetSpan().Fill(-1);
        }

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

            this.hashTable.Dispose();
        }
    }

    /// <summary>
    /// A fixed-capacity dictionary with exactly 256 entries mapping a <see cref="uint"/> key
    /// to a <see cref="short"/> value.
    /// </summary>
    /// <remarks>
    /// The dictionary is implemented using a fixed array of 256 buckets and an entries array
    /// of the same size. The bucket for a key is computed as (key &amp; 0xFF), and collisions are
    /// resolved through a linked chain stored in the <see cref="Entry.Next"/> field.
    /// The overall memory usage is approximately 3–4 KB. Both lookup and insertion operations are,
    /// on average, O(1) since the bucket is determined via a simple bitmask and collision chains are
    /// typically very short; in the worst-case, the number of iterations is bounded by 256.
    /// This guarantees highly efficient and predictable performance for small, fixed-size color palettes.
    /// </remarks>
    internal sealed unsafe class FixedDictionary256 : IDisposable
    {
        // Buckets array: each bucket holds the index (0-based) into the entries array
        // of the first entry in the chain, or -1 if empty.
        private readonly IMemoryOwner<int> bucketsOwner;
        private MemoryHandle bucketsHandle;
        private int* buckets;

        // Entries array: stores up to 256 entries.
        private readonly IMemoryOwner<Entry> entriesOwner;
        private MemoryHandle entriesHandle;
        private Entry* entries;

        public const int Capacity = 256;

        public FixedDictionary256(MemoryAllocator allocator)
        {
            this.Count = 0;

            // Allocate exactly 256 ints for buckets.
            this.bucketsOwner = allocator.Allocate<int>(Capacity, AllocationOptions.Clean);
            Span<int> bucketSpan = this.bucketsOwner.GetSpan();
            bucketSpan.Fill(-1);
            this.bucketsHandle = this.bucketsOwner.Memory.Pin();
            this.buckets = (int*)this.bucketsHandle.Pointer;

            // Allocate exactly 256 entries.
            this.entriesOwner = allocator.Allocate<Entry>(Capacity, AllocationOptions.Clean);
            this.entriesHandle = this.entriesOwner.Memory.Pin();
            this.entries = (Entry*)this.entriesHandle.Pointer;
        }

        public int Count { get; private set; }

        /// <summary>
        /// Adds a key/value pair to the dictionary.
        /// If the key already exists, the dictionary is left unchanged.
        /// </summary>
        /// <param name="key">The key to add.</param>
        /// <param name="value">The value to add.</param>
        /// <returns><see langword="true"/> if the key was added; otherwise, <see langword="false"/>.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool TryAdd(uint key, short value)
        {
            if (this.Count == Capacity)
            {
                return false; // Dictionary is full.
            }

            int bucket = (int)(key & 0xFF);
            int i = this.buckets[bucket];

            // Traverse the collision chain.
            Entry* entries = this.entries;
            while (i != -1)
            {
                Entry e = entries[i];
                if (e.Key == key)
                {
                    // Key already exists; do not overwrite.
                    return false;
                }

                i = e.Next;
            }

            int index = this.Count;
            this.Count++;

            // Insert the new entry:
            entries[index].Key = key;
            entries[index].Value = value;

            // Link this new entry into the bucket chain.
            entries[index].Next = this.buckets[bucket];
            this.buckets[bucket] = index;
            return true;
        }

        /// <summary>
        /// Tries to retrieve the value associated with the specified key.
        /// Returns true if the key is found; otherwise, returns false.
        /// </summary>
        /// <param name="key">The key to search for.</param>
        /// <param name="value">The value associated with the key, if found.</param>
        /// <returns><see langword="true"/> if the key is found; otherwise, <see langword="false"/>.</returns>

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool TryGetValue(uint key, out short value)
        {
            int bucket = (int)(key & 0xFF);
            int i = this.buckets[bucket];

            // If the bucket is empty, return immediately.
            if (i == -1)
            {
                value = -1;
                return false;
            }

            // Traverse the chain.
            Entry* entries = this.entries;
            do
            {
                Entry e = entries[i];
                if (e.Key == key)
                {
                    value = e.Value;
                    return true;
                }

                i = e.Next;
            }
            while (i != -1);

            value = -1;
            return false;
        }

        /// <summary>
        /// Clears the dictionary.
        /// </summary>
        public void Clear()
        {
            Span<int> bucketSpan = this.bucketsOwner.GetSpan();
            bucketSpan.Fill(-1);
            this.Count = 0;
        }

        public void Dispose()
        {
            this.bucketsHandle.Dispose();
            this.bucketsOwner.Dispose();
            this.entriesHandle.Dispose();
            this.entriesOwner.Dispose();
            this.buckets = null;
            this.entries = null;
        }

        private struct Entry
        {
            public uint Key;     // The key (packed RGBA)
            public short Value;  // The value; -1 means unused.
            public int Next;     // Index of the next entry in the chain, or -1 if none.
        }
    }

[pwitvoet]

Thanks! I ran some tests and it's looking good. :)

Just a few remarks:

• It might be beneficial to increase the number of buckets (not entries), to reduce the chance of hash collisions.
• If I understand correctly, (int)(key & 0xFF) is taking the red channel value. What's the performance for images with little or no variety in the red channel? Wouldn't it be better to use a hash function with a better distribution, or if that is too slow,
  to take some bits from each channel?

[JimBobSquarePants]

Thanks for the feedback!

I've verified that FixedDictionary256 stores up to 256 unique RGBA colors correctly using separate chaining. Even though our bucket index is computed as (int)(key & 0xFF), which effectively uses the lower 8 bits of the packed value (often the red channel), this is not an issue even in cases where there's little or no variance in that channel.

Here's why:

Each bucket is a linked list that holds all entries mapping to that bucket. The first 256 distinct colors encountered are stored, regardless of how many share the same lower 8 bits. In other words, even if many colors have the same red component, every unique color is saved independently in the collision chain. This guarantees that a lack of variance in one channel does not prevent any of the first 256 distinct colors from being captured.

[pwitvoet]

Sorry, I should have clarified that I'm taking about performance, not correctness. As far as I can see your implementation is indeed correct.

I inspected a number of test images (game textures) and found that most of them had around 50 to 100 distinct red values. That gives an average chain length of about 2.5 to 5, so for every color beyond the first 256 that's 2.5 to 5 comparisons on average before it will fall back to the coarse cache. A hash algorithm with a uniform distribution would give an average chain length of 1, so 1 comparison on average. Unfortunately hashing isn't free, but perhaps there's a decent middle-ground that can improve distribution while still being cheap to compute.

The first thing I'd think of would be to xor the RGB channels: int bucket = (int)(((key >> 16) ^ (key >> 8) ^ key) & 0xFF);. I think that by taking more bits into account, it also becomes less likely to hit a worst-case scenario in practice (worst-case being that all colors somehow map to a single bucket and almost every color not being in the dictionary, thus devolving to a linear search for every color lookup).

Increasing the number of buckets should also reduce the average chain length. With 512 buckets and a uniform distribution, you'd get 0.5 comparisons on average.

[JimBobSquarePants]

YES! That's a great idea; some benchmarking indicates a 33% improvement for some larger images. Very nice.