Dithering

// Ein Bild, das nur wenige Farben verwenden darf, zerfällt in Flecken: Alles, was
// nah beieinander liegt, landet auf derselben Farbe, und weiche Übergänge werden zu
// harten Stufen. Dithering tauscht diese Flecken gegen ein feines Korn, das das Auge
// wieder zu der Farbe zusammenmischt, die gemeint war.
public static class Dithering
{
    // Floyd und Steinberg, 1976. Jeder Pixel bekommt die nächstgelegene Farbe, die noch
    // erlaubt ist, und der Unterschied zwischen gewünschter und verwendeter Farbe wird
    // an die Nachbarn weitergereicht, die noch an die Reihe kommen.
    public static PngImage FloydSteinberg(PngImage image, int levels)
    {
        var channels = ToChannels(image, levels);

        for (var y = 0; y < image.Height; y++)
        {
            for (var x = 0; x < image.Width; x++)
            {
                for (var channel = 0; channel < 3; channel++)
                {
                    var index = ((y * image.Width + x) * 3) + channel;
                    var wanted = channels[index];
                    var used = Snap(wanted, levels);

                    channels[index] = used;

                    // Der Fehler wird auf vier Nachbarn verteilt. Das meiste geht nach
                    // rechts, der Rest in die nächste Zeile; zusammen ergeben die Teile
                    // genau den ganzen Fehler, es geht also nichts verloren und nichts hinzu.
                    var error = wanted - used;

                    Hand(channels, image, x + 1, y, channel, error * 7f / 16f);
                    Hand(channels, image, x - 1, y + 1, channel, error * 3f / 16f);
                    Hand(channels, image, x, y + 1, channel, error * 5f / 16f);
                    Hand(channels, image, x + 1, y + 1, channel, error * 1f / 16f);
                }
            }
        }

        return ToImage(channels, image);
    }

    // Die andere Schule: Statt den Fehler weiterzureichen, wird jeder Pixel vor dem
    // Runden um einen festen Betrag gestupst. Der Betrag kommt aus einer kleinen
    // Matrix, die sich über das Bild wiederholt, weshalb das Ergebnis gewebt aussieht.
    public static PngImage Ordered(PngImage image, int levels)
    {
        var channels = ToChannels(image, levels);
        var step = 1f / (levels - 1);

        for (var y = 0; y < image.Height; y++)
        {
            for (var x = 0; x < image.Width; x++)
            {
                // Der Matrixwert läuft von 0 bis 15, der Stups von minus einer halben Stufe
                // bis plus einer halben Stufe.
                var nudge = ((Matrix[(y % 4) * 4 + (x % 4)] + 0.5f) / 16f - 0.5f) * step;

                for (var channel = 0; channel < 3; channel++)
                {
                    var index = ((y * image.Width + x) * 3) + channel;
                    channels[index] = Snap(channels[index] + nudge, levels);
                }
            }
        }

        return ToImage(channels, image);
    }

    // Dieselbe Reduktion ohne jedes Dithering: Jeder Pixel nimmt einfach die nächste
    // erlaubte Farbe. Daran werden die beiden oberen gemessen.
    public static PngImage Quantize(PngImage image, int levels)
    {
        var channels = ToChannels(image, levels);

        for (var index = 0; index < channels.Length; index++)
            channels[index] = Snap(channels[index], levels);

        return ToImage(channels, image);
    }

    // Bayers 4-x-4-Matrix. Benachbarte Zahlen liegen so weit auseinander wie möglich,
    // damit das Muster gleichmäßig bleibt und nirgends verklumpt.
    private static readonly int[] Matrix =
    [
        0, 8, 2, 10,
        12, 4, 14, 6,
        3, 11, 1, 9,
        15, 7, 13, 5,
    ];

    // Die erlaubten Werte eines Kanals liegen gleichmäßig zwischen 0 und 1: Bei drei
    // Stufen sind das 0, 0,5 und 1. Snap wählt den nächstgelegenen davon.
    private static float Snap(float value, int levels)
    {
        var steps = levels - 1;

        return Math.Clamp(MathF.Round(value * steps) / steps, 0f, 1f);
    }

    // Gibt einen Teil des Fehlers an einen Nachbarn, sofern es diesen Nachbarn gibt.
    private static void Hand(float[] channels, PngImage image, int x, int y, int channel, float part)
    {
        if (x < 0 || y < 0 || x >= image.Width || y >= image.Height)
            return;

        channels[((y * image.Width + x) * 3) + channel] += part;
    }

    // Rot, Grün und Blau als Werte von 0 bis 1. Die Fehlerdiffusion muss mit Brüchen
    // rechnen, ein Byte je Kanal würde sie sofort wegrunden.
    private static float[] ToChannels(PngImage image, int levels)
    {
        ArgumentOutOfRangeException.ThrowIfLessThan(levels, 2);

        var channels = new float[image.Width * image.Height * 3];

        for (var pixel = 0; pixel < image.Width * image.Height; pixel++)
        {
            for (var channel = 0; channel < 3; channel++)
                channels[pixel * 3 + channel] = image.Pixels[pixel * 4 + channel] / 255f;
        }

        return channels;
    }

    private static PngImage ToImage(float[] channels, PngImage original)
    {
        var pixels = new byte[original.Width * original.Height * 4];

        for (var pixel = 0; pixel < original.Width * original.Height; pixel++)
        {
            for (var channel = 0; channel < 3; channel++)
                pixels[pixel * 4 + channel] = (byte)MathF.Round(channels[pixel * 3 + channel] * 255f);

            pixels[pixel * 4 + 3] = original.Pixels[pixel * 4 + 3];
        }

        return new PngImage { Width = original.Width, Height = original.Height, Pixels = pixels };
    }
}

// file zeigt auf ein Farbfoto, 320 x 240 Pixel.
var photo = PngImage.Load(file);

// Levels ist die Anzahl der Werte, die ein Kanal annehmen darf. Zwei Stufen lassen
// acht Farben übrig, drei Stufen 27 und vier Stufen 64.
foreach (var levels in new[] { 2, 3, 4 })
{
    var dithered = Dithering.FloydSteinberg(photo, levels);
    var target = Path.Combine(folder, $"grand-prismatic-spring-{levels}.png");

    dithered.Save(target);

    Console.WriteLine(
        $"{levels} levels: {levels * levels * levels,3} colours allowed, " +
        $"{dithered.ColourCount(),3} used, {new FileInfo(target).Length / 1024,3} KiB");
}

var photo = PngImage.Load(file);

// Zwei Arten, den Fehler zu messen: Pixel für Pixel und über Quadrate von
// 4 x 4 Pixeln. Die zweite kommt dem Auge näher, denn es mittelt erst über
// eine kleine Fläche, bevor es urteilt.
Console.WriteLine("levels  colours  method      pixel   4 x 4");

foreach (var levels in new[] { 2, 3, 4 })
{
    (string Name, PngImage Result)[] ways =
    [
        ("plain", Dithering.Quantize(photo, levels)),
        ("ordered", Dithering.Ordered(photo, levels)),
        ("diffused", Dithering.FloydSteinberg(photo, levels)),
    ];

    foreach (var (name, result) in ways)
    {
        Console.WriteLine(
            $"{levels,6}  {levels * levels * levels,7}  {name,-8}  " +
            $"{Error(photo, result, 1),6:0.0}  {Error(photo, result, 4),6:0.0}");
    }
}

// Der mittlere Unterschied zum Original, gemessen über Quadrate der angegebenen
// Größe. Größe 1 vergleicht einzelne Pixel, Größe 4 kleine Flächen.
static double Error(PngImage original, PngImage result, int size)
{
    var sum = 0.0;
    var squares = 0;

    for (var y = 0; y + size <= original.Height; y += size)
    {
        for (var x = 0; x + size <= original.Width; x += size)
        {
            for (var channel = 0; channel < 3; channel++)
            {
                var difference = 0;

                for (var offsetY = 0; offsetY < size; offsetY++)
                {
                    for (var offsetX = 0; offsetX < size; offsetX++)
                    {
                        var pixel = (((y + offsetY) * original.Width) + x + offsetX) * 4 + channel;
                        difference += original.Pixels[pixel] - result.Pixels[pixel];
                    }
                }

                sum += Math.Abs(difference) / (double)(size * size);
                squares++;
            }
        }
    }

    return sum / squares;
}