Repository navigation
Quality loss when quantizing an image that already has (fewer than) 256 colors #2862
Replies: 1 comment 7 replies
|
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:
You shouldn't need to use this constructor. If you look at other quantizer implementations they defer the creation of the type to
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 implementationusing 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();
}
}
} |
|
Ah yes, I did see There are a few cases where quantization isn't just mapping one color to another:
As for using the same quantizer for all frames that use the same palette, I think there are several benefits:
So I decided to see how difficult it would be to change the png and gif encoders. The main issue I encountered is that Regarding your hybrid color distance cache, that looks useful. Maybe 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 |
|
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 & 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.
}
} |
|
Thanks! I ran some tests and it's looking good. :) Just a few remarks:
|
|
Thanks for the feedback! I've verified that 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. |
|
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: 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. |
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