How can Floyd-Steinberg-Dithering work?

Question

I'm currently trying to implement the Floyd-Steinberg-Dithering algorithm in Java. After a few failed attempts I came across a question after reading the pseudocode listed on Wikipedia.

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  := oldpixel - newpixel
  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
  pixel[x  ][y+1] := pixel[x  ][y+1] + 5/16 * quant_error
  pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error

What I'm trying to achieve is squishing the image into a 16 color palette. After adding the error the pixels however, don't I create completely new colors that don't even exist in the palette?

But would forcing the entire image back into the color palette at the end suffice to make this work?

Thanks in advance!

Answer 1

Note that the quantized error is added only to pixels that have not yet been mapped to the palette (quantized)!

This means that after the error has been added in, these pixels will also be mapped, and their error propagated forwards onto other unprocessed pixels.

At the end of the algorithm, every pixel will have been mapped, and the final remaining error will be discarded.

As a result, you should not have any pixels outside of the palette at the end of the quantization operation.

Answer 2

I have used a modified algorithm:

 for each y from 0 to ImageHeight-1
    for each x from 1 to ImageWidth-1
        oldpixel  := pixel[x][y]
        newpixel  := find_closest_palette_color(oldpixel)
        pixel[x][y]  := newpixel
        quant_error  := oldpixel - newpixel
        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
        pixel[x  ][y+1] := pixel[x  ][y+1] + 5/16 * quant_error
        pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error

and i have used this 16 colors palette:
               **B    G    R**
 black:          0,   0,   0
 blue:         127,   0,   0
 green:          0, 127,   0
 cyan:         127, 127,   0
 red:            0,   0, 127
 magenta:      127,   0,   0
 brown:        127,   0, 127
 gray:         191, 191, 191
 dark gray:     63,  63,  63
 light blue:   255,   0,   0
 light green:    0, 255,   0
 light cyan:   255, 255,   0
 light red:      0,   0, 255
 pink:         255,   0, 255
 yellow:         0, 255, 255
 white:        255, 255, 255

The result was better with this palette, without serpentine scanning as recommended in Wikipedia.