# How to Implement the Floyd-Steinberg Algorithm from GIMP in Your Code

I am working on a project where I am trying to display an image as beautifully as possible on an E Ink display. I achieved the best results using the normal Floyd Steinberg algorithm employed in GIMP (indexed mode).
However, all attempts to create an algorithm that produces comparable images have failed.

I am now trying to identify and integrate this specific algorithm into my code, but so far, I have not had much luck. I found one in `dither.c`, but when I tried to apply it, the results were unsuccessful.

dither.c

My e-ink display supports these 8 colors:

``````    [0, 0, 0],          # Black
[255, 255, 255],    # White
[67, 138, 28],      # Dark Green
[100, 64, 255],     # Blue Violet
[191, 0, 0],        # Dark Red
[255, 243, 56],     # Light Yellow
[232, 126, 0],      # Orange
[194, 164, 244]     # Light Violet
``````

When comparing the two dithered images, you can see that the one from GIMP contains significantly less green. The one from GIMP uses much more red, orange, and black for the skin:

[GIMP_algorithm]

[own_algorithm]

my algorithm:

``````def get_nearest_color(r, g, b, palette):
min_diff = float('inf')
nearest_color = palette[0]

for color in palette:
diff = (r - color[0])**2 + (g - color[1])**2 + (b - color[2])**2

# Prioritize orange over green in case of close matches
if (color == [232, 126, 0]) and (color[1] > r):  # Give Orange a slight bias
diff -= 1000  # Adjust this value as needed

if diff < min_diff:
min_diff = diff
nearest_color = color

return nearest_color

def apply_dithering(image, palette, dither_method="floyd_steinberg", intensity=0.1):
pixels = np.array(image, dtype=np.float32)
height, width, _ = pixels.shape
for y in range(height):
for x in range(width):
r, g, b = pixels[y, x][:3]
nearest_color = get_nearest_color(r, g, b, palette)
r_diff = r - nearest_color[0]
g_diff = g - nearest_color[1]
b_diff = b - nearest_color[2]
pixels[y, x][:3] = nearest_color
if dither_method == "floyd_steinberg":
if x + 1 < width:
pixels[y, x + 1][:3] += intensity * np.array([r_diff * 7 / 16, g_diff * 7 / 16, b_diff * 7 / 16])
if y + 1 < height:
if x > 0:
pixels[y + 1, x - 1][:3] += intensity * np.array([r_diff * 3 / 16, g_diff * 3 / 16, b_diff * 3 / 16])
pixels[y + 1, x][:3] += intensity * np.array([r_diff * 5 / 16, g_diff * 5 / 16, b_diff * 5 / 16])
if x + 1 < width:
pixels[y + 1, x + 1][:3] += intensity * np.array([r_diff * 1 / 16, g_diff * 1 / 16, b_diff * 1 / 16])
dithered_image = np.clip(pixels, 0, 255).astype(np.uint8)
return Image.fromarray(dithered_image)
``````

I am grateful for any help!

@Jehan
Thank you very much for your kind offer to help me

Gimp very likely works on the linear values and not on the gamma-corrected one. This is important! For instance, the equivalent color of this pattern (colors are (254, 220, 186) , (69, 103, 137), (212, 69, 111))

Is (199,150,49):

And not what the direct average would tell you (178, 131, 146) (usually too dark):

Some explanations (and the formulas) here.

What you call “GIMP_algorithm” was the result of something done in the GUI, I assume. Is it the filter found in menu `Colors > Dither…`?

If so, I can confirm that you are looking at the right file for the implementation. For starters.

@Ofnuts

Gimp very likely works on the linear values and not on the gamma-corrected one.

In fact, looking at the `prepare()` function, we can see that our algorithm works in the input space’s TRC. It only switches to linear if red, green and blue levels are equal to 2.

@schlaul If you copied exactly the algorithm in our code and it doesn’t show exactly the same thing, I would suggest to work on much smaller samples, not on a big image and to go step by step. You should be able to very quickly find where the difference occurs.

You could even just rebuild GEGL to add traces to it so that you can compare values and find the exact step where they start differing. Compiling GEGL is very easy as you are a developer.

You don’t even need GIMP to test things. You can call GEGL from command line even, which is very useful for quick testing. For instance for this dithering op, just run:

``````gegl input.png -o output.png -- gegl:dither
``````

Change any of the parameters with this syntax:

``````gegl input.png -o output.png -- gegl:dither red-levels=3
``````

(more infos on parameters with `gegl --info gegl:dither`)

Also why don’t you just depend on GEGL in your project? It’s a lib, it’s made to be used in other projects, not only GIMP. GEGL even has a Python binding thanks to GObject Introspection.

Thank you so much, @Ofnuts and @Jehan, for the quick response!

Just to clarify, I didn’t use the Colors > Dither… path to dither the image. Instead, I went with this method:
Image → Mode → Indexed
[6.6. Indexed mode]

Does this method use a different algorithm? And where can I find it?

I’ll definitely give the GEGL library a try and start testing with simpler images. I’ll keep you posted on how it goes!

By the way, I’m not a developer—just a guy with an idea and a tiny bit of experience. Just enough to think I can make it work.

For this, start looking from function `gimp_image_convert_indexed` in `app/core/gimpimage-convert-indexed.c`. From there, look at the specific code path you are taking, depending on the options you were using in the “Convert Image to Indexed Colors” dialog.

There are quite a few different code paths (there are even 2 variants of the Floyd-Steinberg algorithm, I see, a normal and a low-bleed one).

And indeed it doesn’t look like we are using the `gegl:dither` algorithm here (though I haven’t looked extensively at the whole code).