Talk:Floyd–Steinberg dithering

Error in pseudocode

Is this pseudo code correct? I think it should be:

     pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error
     pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error

...

otherwise we set all the neighbors to low values —Preceding unsigned comment added by 71.231.1.193 (talk • contribs) 21:51, 17 February 2007

yes, it was corrected a couple days later. Han-Kwang (t) 21:47, 4 September 2007 (UTC)

It's still wrong. Every write of quantization error is later overwritten. matt kane's brain (talk) 15:00, 22 July 2010 (UTC)

It's wrong even if it's right. The 'quantized pixel' is not stored unmodified? that's supposed to be the output, no? This pseudocode is supposed to illustrate the algorithm, so there should be three arrays, one to store the input (and not be written), one to store the output (and never read) and one which is used to hold the quantization errors. Once that change is made it will be much easier to write and much easier to follow. Doing it all in-place is a neat trick but in practice it requires extra fractional bits to accumulate the errors properly (unless you're already using floats, I guess). IMHO that trick should not be in this reference (if so it should at least be done right!). 216.191.144.135 (talk)

FWIW I think the required change is as below, but comment still stands...

           pixel[x][y] := newpixel /* not pixel[x][y] + newpixel */

216.191.144.135 (talk)

216.191.144.135 (talk) 22:10, 4 August 2010 (UTC)

as of 2022, the pseudocode is still incorrect. the outer loop uses y, the inner loop uses x, and yet the pixels are arranged [x][y]. Cloudmadeofcandy (talk) 01:16, 9 November 2022 (UTC)

Rounding?

Ideally, should the FSD algorithm round the quantization errors to the nearest integer, or not? Or doesn't it matter at all? Shinobu 15:57, 4 September 2007 (UTC)

FSD doesn't make an assumption about the representation of the pixel values. It works just as well when the pixels are floating point numbers between 0 and 1. For speed reasons, an implementation might do everything in integer math, but the result won't be as good. Suppose all pixels have value 1, but you have to encode with a palette with either 0 or 2. So the quantization error is 1 each time, but 7/16 and the other distributed errors are all rounded to 0 and the algorithm won't work. Han-Kwang (t) 21:47, 4 September 2007 (UTC)

Yes, I see. That means that as the destination levels get higher and higher, the rounding will matter less and less. In real applications, the levels could be {0, 255} or even {0, 65535}. Of course you could also save 16 times the errors if space allows and do the bit-shift later. Shinobu 23:40, 5 September 2007 (UTC)

Move to error-diffusion dithering?

I propose we move this article to error-diffusion dithering, because I will be adding a few other error-diffusion dithering algorithms here that could not stand on their own as separate articles, but are clearly related to Floyd-Steinberg in the sense that they too use an error-diffusion process. Shinobu 23:44, 5 September 2007 (UTC)

I would be fine with that. I didn't know it was called like that, but the first few google hits are much nicer references than what I could find when I was looking for references for this article. They also explain the artifacts in FSD. Han-Kwang (t) 20:53, 6 September 2007 (UTC)

Sounds like a good idea to me. Certainly all variants of error-diffusion that only differ by the diffusion filter can be on the same page (I don't know why they are typically presented as though they were different algorithms). --DavidHopwood 02:31, 29 October 2007 (UTC)

Isn't it noise shaping instead of just dither?

According to some sources, Floyd-Steinberg dithering is not dithering, but dithering plus noise shaping, being the noise shaping part the important one. The quantization noise is moved to high frequencies where our eye is more sensitive.--80.24.18.223 (talk) 08:05, 27 May 2008 (UTC)

About the quantization method

Using this to reduce color from 16 bits to 8 bits:

find_closest_palette_color(oldpixel) = (oldpixel + 128) / 256

Isn't this going to create 257 colors including 0 and 256, if the old colors are from 0 to 65535? If the '/' is simple truncation, of course. —Preceding unsigned comment added by Rachel2046 (talk • contribs) 00:19, 10 June 2009 (UTC)

I think you are right. Reducing a 16 bit value to a 8 bit value can be thought as a shift of the original value to the right, for eight positions. This is equivalent to a division by 256. I'll modify the location in question. Wrev (talk) 16:40, 28 January 2020 (UTC)

Error calculated from modified pixel value?

Is it normal that the reference value used to determine the error is a value modified by diffusing the previous errors rather than the actual "source" value? I know that would prevent doing the dithering in-place (because you have to keep the original value somehow), but I heard error was always calculated from the theoretical value, not intermediary stuff...

That would make the pseudocode such:

for each y from top to bottom
   for each x from left to right
      pixel[x][y]  := sourcepixel[x][y]
for each y from top to bottom
   for each x from left to right
      oldpixel  := pixel[x][y]
      newpixel  := find_closest_palette_color(oldpixel)
      pixel[x][y]  := newpixel
      quant_error  := sourcepixel[x][y] - newpixel
      pixel[x+1][y  ] := pixel[x+1][y  ] + quant_error * 7/16
      pixel[x-1][y+1] := pixel[x-1][y+1] + quant_error * 3/16
      pixel[x  ][y+1] := pixel[x  ][y+1] + quant_error * 5/16
      pixel[x+1][y+1] := pixel[x+1][y+1] + quant_error * 1/16

Medinoc (talk) 20:18, 26 January 2015 (UTC)

Does anyone have the Floyd–Steinberg paper?

I can't find it anywhere. I'd like to see how they presented this originally. Dicklyon (talk) 22:00, 4 September 2021 (UTC)