Implementing Floyd-Steinberg Dithering in C# with specific Palette
I am making a program where I want to take an image and reduce its color palette to a preset palette of 60 colors, and then add a dithering effect. This seems to involve two things:
- A color distance algorithm that goes through each pixel, gets its color, and then changes it to the color closest to it in the palette so that that image doesn't have colors that are not contained in the palette.
- A dithering algorithm that goes through the color of each pixel and diffuses the difference between the original color and the new palette color chosen across the surrounding pixels.
After reading about color difference, I figured I would use either the CIE94 or CIEDE2000 algorithm for finding the closest color from my list. I also decided to use the fairly common Floyd–Steinberg dithering algorithm for the dithering effect.
Over the past 2 days I have written my own versions of these algorithms, pulled other versions of them from examples on the internet, tried them both first in Java and now C#, and pretty much every single time the output image has the same issue. Some parts of it look perfectly fine, have the correct colors, and are dithered properly, but then other parts (and sometimes the entire image) end up way too bright, are completely white, or all blur together. Usually darker images or darker parts of images turn out fine, but any part that is bright or has lighter colors at all gets turned up way brighter. Here is an example of an input and output image with these issues:
Input:
]3
Output:
I do have one idea for what may be causing this. When a pixel is sent through the "nearest color" function, I have it output its RGB values and it seems like some of them have their R value (and potentially other values??) pushed way higher than they should be, and even sometimes over 255 as shown in the screenshot. This does NOT happen for the earliest pixels in the image, only for ones that are multiple pixels in already and are already somewhat bright. This leads me to believe it is the dithering/error algorithm doing this, and not the color conversion or color difference algorithms. If that is the issue, then how would I go about fixing that?
Here's the relevant code and functions I'm using. At this point it's a mix of stuff I wrote and stuff I've found in libraries or other StackOverflow posts. I believe the main dithering algorithm and C3 class are copied basically directly from this Github page (and changed to work with C#, obviously)
class Program
{
public static C3[] palette = new C3[]{
new C3(196, 76, 86),
new C3(186, 11, 39),
new C3(113, 0, 32),
new C3(120, 41, 56),
new C3(203, 125, 84),
new C3(205, 90, 40),
new C3(175, 50, 33),
new C3(121, 61, 54),
// etc... palette is 60 colors total
// each object contains an r, g, and b value
};
static void Main(string[] args)
{
// paths for original image and output path for dithered image
string path = @"C:\Users\BillehBawb\Desktop\";
string imgPath = path + "amy.jpg";
string createPath = path + "amydithered.jpg";
// pulls the original image, runs the dithering function, then saves the new image
Bitmap img = new Bitmap(imgPath);
Bitmap dithered = floydSteinbergDithering(img);
dithered.Save(createPath, ImageFormat.Jpeg);
}
// loops through every pixel in the image, populates a 2d array with the pixel colors, then loops through again to change the color to one in the palette and do the dithering algorithm
private static Bitmap floydSteinbergDithering(Bitmap img)
{
int w = img.Width;
int h = img.Height;
C3[,] d = new C3[h, w];
for (int y = 0; y < h; y++)
{
for (int x = 0; x < w; x++)
{
d[y, x] = new C3(img.GetPixel(x, y).ToArgb());
}
}
for (int y = 0; y < img.Height; y++)
{
for (int x = 0; x < img.Width; x++)
{
C3 oldColor = d[y, x];
C3 newColor = findClosestPaletteColor(oldColor, palette);
img.SetPixel(x, y, newColor.toColor());
C3 err = oldColor.sub(newColor);
if (x + 1 < w)
{
d[y, x + 1] = d[y, x + 1].add(err.mul(7.0 / 16));
}
if (x - 1 >= 0 && y + 1 < h)
{
d[y + 1, x - 1] = d[y + 1, x - 1].add(err.mul(3.0 / 16));
}
if (y + 1 < h)
{
d[y + 1, x] = d[y + 1, x].add(err.mul(5.0 / 16));
}
if (x + 1 < w && y + 1 < h)
{
d[y + 1, x + 1] = d[y + 1, x + 1].add(err.mul(1.0 / 16));
}
}
}
return img;
}
// loops through the palette, converts the input pixel and palette colors to the LAB format, finds the difference between all of them, and selects the palette color with the lowest difference
private static C3 findClosestPaletteColor(C3 c, C3[] palette)
{
double[] pixelLab = rgbToLab(c.toColor().R, c.toColor().G, c.toColor().B);
double minDist = Double.MaxValue;
int colorIndex = 0;
for (int i = 0; i < palette.Length; i++)
{
double[] colors = rgbToLab(palette[i].toColor().R, palette[i].toColor().G, palette[i].toColor().B);
double dist = labDist(pixelLab[0], pixelLab[1], pixelLab[2], colors[0], colors[1], colors[2]);
if (dist < minDist)
{
colorIndex = i;
minDist = dist;
}
}
return palette[colorIndex];
}
// finds the deltaE/difference between two sets of LAB colors with the CIE94 algorithm
public static double labDist(double l1, double a1, double b1, double l2, double a2, double b2)
{
var deltaL = l1 - l2;
var deltaA = a1 - a2;
var deltaB = b1 - b2;
var c1 = Math.Sqrt(Math.Pow(a1, 2) + Math.Pow(b1, 2));
var c2 = Math.Sqrt(Math.Pow(a2, 2) + Math.Pow(b2, 2));
var deltaC = c1 - c2;
var deltaH = Math.Pow(deltaA, 2) + Math.Pow(deltaB, 2) - Math.Pow(deltaC, 2);
deltaH = deltaH < 0 ? 0 : Math.Sqrt(deltaH);
double sl = 1.0;
double kc = 1.0;
double kh = 1.0;
double Kl = 1.0;
double K1 = .045;
double K2 = .015;
var sc = 1.0 + K1 * c1;
var sh = 1.0 + K2 * c1;
var i = Math.Pow(deltaL / (Kl * sl), 2) +
Math.Pow(deltaC / (kc * sc), 2) +
Math.Pow(deltaH / (kh * sh), 2);
var finalResult = i < 0 ? 0 : Math.Sqrt(i);
return finalResult;
}
// converts RGB colors to the XYZ and then LAB format so the color difference algorithm can be done
public static double[] rgbToLab(int R, int G, int B)
{
float[] xyz = new float[3];
float[] lab = new float[3];
float[] rgb = new float[3];
rgb[0] = R / 255.0f;
rgb[1] = G / 255.0f;
rgb[2] = B / 255.0f;
if (rgb[0] > .04045f)
{
rgb[0] = (float)Math.Pow((rgb[0] + .055) / 1.055, 2.4);
}
else
{
rgb[0] = rgb[0] / 12.92f;
}
if (rgb[1] > .04045f)
{
rgb[1] = (float)Math.Pow((rgb[1] + .055) / 1.055, 2.4);
}
else
{
rgb[1] = rgb[1] / 12.92f;
}
if (rgb[2] > .04045f)
{
rgb[2] = (float)Math.Pow((rgb[2] + .055) / 1.055, 2.4);
}
else
{
rgb[2] = rgb[2] / 12.92f;
}
rgb[0] = rgb[0] * 100.0f;
rgb[1] = rgb[1] * 100.0f;
rgb[2] = rgb[2] * 100.0f;
xyz[0] = ((rgb[0] * .412453f) + (rgb[1] * .357580f) + (rgb[2] * .180423f));
xyz[1] = ((rgb[0] * .212671f) + (rgb[1] * .715160f) + (rgb[2] * .072169f));
xyz[2] = ((rgb[0] * .019334f) + (rgb[1] * .119193f) + (rgb[2] * .950227f));
xyz[0] = xyz[0] / 95.047f;
xyz[1] = xyz[1] / 100.0f;
xyz[2] = xyz[2] / 108.883f;
if (xyz[0] > .008856f)
{
xyz[0] = (float)Math.Pow(xyz[0], (1.0 / 3.0));
}
else
{
xyz[0] = (xyz[0] * 7.787f) + (16.0f / 116.0f);
}
if (xyz[1] > .008856f)
{
xyz[1] = (float)Math.Pow(xyz[1], 1.0 / 3.0);
}
else
{
xyz[1] = (xyz[1] * 7.787f) + (16.0f / 116.0f);
}
if (xyz[2] > .008856f)
{
xyz[2] = (float)Math.Pow(xyz[2], 1.0 / 3.0);
}
else
{
xyz[2] = (xyz[2] * 7.787f) + (16.0f / 116.0f);
}
lab[0] = (116.0f * xyz[1]) - 16.0f;
lab[1] = 500.0f * (xyz[0] - xyz[1]);
lab[2] = 200.0f * (xyz[1] - xyz[2]);
return new double[] { lab[0], lab[1], lab[2] };
}
}
And here is the C3 class, its basically just the Color class with some math functions to make it cleaner to do the dithering on
class C3
{
int r, g, b;
public C3(int c)
{
Color color = Color.FromArgb(c);
r = color.R;
g = color.G;
b = color.B;
}
public C3(int r, int g, int b)
{
this.r = r;
this.g = g;
this.b = b;
}
public C3 add(C3 o)
{
return new C3(r + o.r, g + o.g, b + o.b);
}
public int clamp(int c)
{
return Math.Max(0, Math.Min(255, c));
}
public int diff(C3 o)
{
int Rdiff = o.r - r;
int Gdiff = o.g - g;
int Bdiff = o.b - b;
int distanceSquared = Rdiff * Rdiff + Gdiff * Gdiff + Bdiff * Bdiff;
return distanceSquared;
}
public C3 mul(double d)
{
return new C3((int)(d * r), (int)(d * g), (int)(d * b));
}
public C3 sub(C3 o)
{
return new C3(r - o.r, g - o.g, b - o.b);
}
public Color toColor()
{
return Color.FromArgb(clamp(r), clamp(g), clamp(b));
}
public int toRGB()
{
return toColor().ToArgb();
}
}
Sorry for the massive code dump, the functions are just pretty large and I want to provide everything I can. If anyone has any suggestions on a simpler or different way to do this, or if you know how to fix the issue I'm running into, please let me know. I have tried quite a few different algorithms for my desired result but I haven't been able to get any of them to do what I want them to. Any help or ideas are greatly appreciated, thank you!
It appears that when you shift the error to the neighbors in floydSteinbergDithering() the r,g,b values never get clamped until you cast them back to Color.
Since you're using int and not byte there is no prevention of overflows to negative or large values greater than 255 for r, g, and b.
You should consider implementing r,g, and b as properties that clamp to 0-255 when they're set.
This will ensure their values will never be outside your expected range (0 - 255).
class C3
{
private int r;
public int R
{
get => r;
set
{
r = clamp(value);
}
}
private int g;
public int G
{
get => g;
set
{
g = clamp(value);
}
}
private int b;
public int B
{
get => b;
set
{
b = clamp(value);
}
}
// rest of class
}