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.

Stylolite

I'm having trouble understanding your result. The difference image implies your Floyd-Steinberg output contains components with values of 0 and 255, but this doesn't make sense with 7 bits; it should be 0 and 254, or 1 and 255. Unless you're using the even colors from 0-126, and the odd ones from 129-255? – Buttons

Problem is that I don't know too exact mappings of bits, that is why I've created such question - to re-search dithering algorithm of program X. – Stylolite

If you could post the result image we might be able to figure out the mapping of the bits. – Buttons

There also appears to be a problem with your Floyd-Steinberg code. The input image has blue=green everywhere, so the algorithm should produce identical results in the green and blue channels - but it does not. – Buttons

Actually I'm researching Photoshop gradient dithering algorithm, so if you have Photoshop - just make gradient with dithering option on. – Stylolite

Answer 1

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.

Orcinol

This is closest to what I've done and there are no better answers, so I'll mark this as accepted answer. – Stylolite

Answer 2

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.

Buttons

Ordered dithering doesn't fits, because it's visual output is very different than Floyd-Steinberg dithering. (To see big differences try to apply ordered and Steinberg dithering to image with big areas in monotone color and compare results) – Stylolite

@0x69, I admitted in the answer that the output is coarse. Can you tell us what bit depth you're generating, and what palette you're using if any? – Buttons

@0x69, I have an edit too. I think you'll like it, epsecially in the monotone color areas. – Buttons

See my edit number 2 :) - could you produce real GLSL dithering code OR just show what final image you've got using my described testing procedure ? – Stylolite

I'll set +1 for nice try, but i can't give you bounty points, because: 1.Your dithering is somewhat irregular. – Stylolite

but i can't give you bounty points, because: 1. Your ordered dithering is somewhat irregular (pattern is not continuous) 2. Dithering pattern not extends to the edges of image (as it should be - can be seen from testing image). 3. As I've said in original post this question is not about ordered dithering, but rather about Floyd-Steinberg alternatives or at least random noise-like dithering. – Stylolite