Bayer Ordered Dithering

Question

I'm updating a plugin for Paint.net which i made some months ago, it's called Simulate Color Depth and it reduces the number of colors in the image to the chosen BPP and for a long time it have had dithering included but NEVER ordered dithering and i thought it would be a nice addition to have that in so i started to search on the internet for something useful, i ended up on this wiki page here http://en.wikipedia.org/wiki/Ordered_dithering, and tried to do as written in the pseudo code

for (int y = 0; x < image.Height; y++)
{  
    for (int x = 0; x < image.Width; x++)
    {
        Color color = image.GetPixel(x, y);  
        color.R = color.R + bayer8x8[x % 8, y % 8];  
        color.G = color.G + bayer8x8[x % 8, y % 8];  
        color.B = color.B + bayer8x8[x % 8, y % 8];  
        image.SetPixel(x, y, GetClosestColor(color, bitdepth);  
    }  
}

but the result is way too bright so i decided to check the wiki page again and then i see that there's a "1/65" to the right of the threshold map which got me thinking of both error diffusing (yes i know, weird huh?) and dividing the value i get from bayer8x8[x % 8, y % 8] with 65 and then multiply the value with the color channels, but either the results were messy or else still too bright (as i remember it) but the results were nothing like i have seen elsewhere, either too bright, too high contrast or too messy and i haven't found anything really useful searching through the internet, so do anyone know how i can get this bayer dithering working properly?

Thanks in advance, Cookies

Incubation

woops, forgot it while writing everything else :S – Incubation

this doesn't answer your question, but Digital Halftoning (mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=4433) might be a good resource to consult. This textbook is the parent reference for much of the material contained in the Wikipedia article. – Hammock

As a side note, I wrote up an explanation of 1-bit ordered dithering in Graphics Gems, vol 1, p. 176, with is similar to but more specific than the Bayer algorithm. IMHO, Floyd-Steinberg dithering with appropriate blue noise creates a more visually appealing image. – Cleave

@Greg im not interested in buying a book for this, im mainly programming for the fun and the challenge @Cleave what i need is something that works on many different BPP but else thanks – Incubation

@Incubation I thought thats what libraries were for? The Google Books scans contain a fair amount of the content in the chapters on Ordered Dithering. You'll find a treasure trove of material if you search for papers that cite that book. – Hammock

@Greg Ahh okay, i think i will take a look then and when i read the wiki page today i saw a line i didn't notice before "The values read from the threshold map should scale into the same range as is the minimal difference between distinct colors in the target palette." so im currently trying to do the thing described above, even though the results still look too bright i think i might be doing it wrong – Incubation

Answer 1

I don't think there's anything wrong with your original algorithm (from Wikipedia). The brightness disparity is probably an artifact of monitor gamma. Check Joel Yliluoma's Positional Dithering Algorithm, the appendix about gamma correction from this article about a dithering algorithm invented by Joel Yliluoma (http://bisqwit.iki.fi/story/howto/dither/jy/#Appendix%201GammaCorrection) to see an explanation of the effect (NB: page is quite graphics-heavy).

Incidentally, perhaps the (apparently public-domain) algorithm detailed in that article may be the solution to your problem...

Predominate

Answer 2

Try this:

color.R = color.R + bayer8x8[x % 8, y % 8] * GAP / 65;

Here GAP should be the distance between the two nearest color thresholds. This depends on the bits per pixel.

For example, if you are converting the image to use 4 bits for the red component of each pixel, there are 16 levels of red total. They are: R=0, R=17, R=34, ... R=255. So GAP would be 17.

Navigable

I tried it and the result only gets better on high BPP if it's low BPP the result is way too bright, but if i edit it it might work, ill let you know – Incubation

Answer 3

Found a solution, levels is the amount of colors the destination images should have and d is the divisor (this is normalized from my code (which uses paint.net classes) to simple bitmap editting with GetPixel and SetPixel)

    private void ProcessDither(int levels, int d, Bitmap image)
    {
        levels -= 1;
        double scale = (1.0 / 255d);
        int t, l;

        for ( int y = rect.Top; y < rect.Bottom; y++ )
        {
            for ( int x = rect.Left; x < rect.Right; x++)
            {
                Color cp = image.GetPixel(x, y);

                int threshold = matrix[y % rows][x % cols];

                t = (int)(scale * cp.R * (levels * d + 1));
                l = t / d;
                t = t - l * d;
                cp.R = Clamp(((l + (t >= threshold ? 1 : 0)) * 255 / levels));

                t = (int)(scale * cp.G * (levels * d + 1));
                l = t / d;
                t = t - l * d;
                cp.G = Clamp(((l + (t >= threshold ? 1 : 0)) * 255 / levels));

                t = (int)(scale * cp.B * (levels * d + 1));
                l = t / d;
                t = t - l * d;
                cp.B = Clamp(((l + (t >= threshold ? 1 : 0)) * 255 / levels));

                image.SetPixel(x, y, cp);
            }
        }
    }

    private byte Clamp(int val)
    {
        return (byte)(val < 0 ? 0 : val > 255 ? 255 : val);
    }

Incubation

But, and despite sounding cliche, what IS the Matrix? What's a good algorithm to produce that matrix? – Swan