Floyd–Steinberg dithering alternatives for pixel shader

Question

I know that Floyd–Steinberg dithering algorithm can't be implemented with pixel shader, because that algorithm is strictly sequential. But maybe there exist some higly parallel dithering algorithm which by it's visual output is similar to Floyd-Steinberg algorithm ?

So the question is - What are dithering algorithms which are suitable to implement on pixel shader (preferably GLSL) and with output quality (very) similar to Floyd-Steinberg dithering ?

BTW. Multi-pass algorithms are allowed until there are not more than 2 passes and CPU overhead between those passes is small.

Any ideas ?

EDIT:
I need dithering from 24-bit color to 21-bit color.
(That is - i need to convert from 8 bits/channel to 7 bits/channel.)

EDIT 2 Maybe I've not explained problem very well. So i'll try to expand a bit on exact problem. Problem is this - consider we have this picture:

And we have above picture, but processed with dithering algorithm:

Now this is procedure which will test your dithering is good for me or not:
1. Load these pictures in Photoshop as one picture with 2 layers.
2. Choose Layers blending mode to "Difference".
3. Perform "Merge Visible" operation on layers, to get just one layer.
4. Perform operation => Image/Adjustments/Equalize

After that you must get such image:

As you see - middle pixels which was in monotone red color was not dithered at all. Also dithering of left and right image zones is a bit different. Try to reconstruct dithering algorithm with such behavior.

Answer 1

You could use an ordered dither. It's more coarse looking than Floyd-Steinberg but there's no dependency between pixels.

Edit: Since you're only removing a single bit, this becomes almost trivial. The principle behind ordered dither is to create a pattern that biases the transition threshold; in this case the bias will be 0 or 1 and the pattern will be 2x2 pixels. These two changes together will make the pattern much less obnoxious than the one in the Wikipedia article - you might even like it better than Floyd-Steinberg.

Here's some pseudo-code:

bias = (X xor Y) and 0x01
value = pixel + bias
if value > 255: value = 255
pixel = value and 0x7e

Edit 2: Here's my difference result, as best as I can do. Without knowing how you map your 7-bit values back to 8 bits I'm unable to do better.

Answer 2

If you are reducing from 8 bits to 7, you are throwing away almost no information. Are you sure you even need to dither?

If you need to dither, add random noise and then clip, it will be plenty good for your application.