Sign in to follow this  
Followers 0
BoltBait

Floyd-Steinberg Dithering (Including Source)

6 posts in this topic

I was playing around with the Steganography plugin in order to improve the quality of the hidden images. I ended up adding in Floyd-Steinberg dithering to the hidden image which greatly improved the quality of the hidden image. Dithering reduces the number of colors of an image by choosing the closest color in the palette for a pixel, then taking the difference between that chosen color and the original color and spreads that difference out to the nearby pixels that haven't been processed yet.

More info on dithering here: http://en.wikipedia.org/wiki/Error_diffusion

Normally, paint.net breaks up your effect into multiple threads to complete the job faster. But, because of the way dithering works, the entire process needs to be done in a single thread. CodeLab could not handle making effects work this way. So, I modified CodeLab to add the option to the build screen.

Then, I got to thinking, this might make a good example of the new CodeLab option for forcing the effect to run in a single thread. So, here ya go...

Download here (Paint.NET 4.0+):

http://forums.getpaint.net/index.php?/topic/32048-v

Once installed, you can find it in your Effects > Stylize menu.

Floyd-Steinberg Dithering Examples:

Me.png

Dithering Matrix (2 Options)

Floyd-Steinberg uses the following dithering matrix:

  

- # 7    where #=pixel being processed, -=previously processed pixel
3 5 1    and pixel difference is distributed to neighbor pixels
         Note: 7+3+5+1 = 16

  

Custom uses the following dithering matrix:

  

- # 8 4    where #=pixel being processed, -=previously processed pixel
4 8 4 1    and pixel difference is distributed to neighbor pixels
0 2 1 0    by the weights shown. Note: 8+4+4+8+4+1+2+1 = 32

  

The Floyd-Steinberg matrix is not the only dithering matrix out there. The Jarvis, Judice, and Ninke matrix uses a total of 48. I designed the custom matrix because I wanted to only use factors of 2 in the math. By using only factors of 2, the math is simplified to bit shifts... so it runs really fast. I was actually surprised that no one had defined such a matrix. (Or, if they have, I could not find a reference to it on the Internet.)

Palettes (6 Options)

Several palettes are available including:

  • Black & White
  • 4 shades of gray
  • 8 shades of gray
  • 4 Colors CMYK :arrow-left:  This is surprisingly good.
  • 16 Color Original Windows Palette
  • 16 Color custom palette that I designed myself

I designed my own 16 color palette because I felt that the 16 color Window's palette didn't do a very good job dithering people. That palette lacks any brown colors. I also didn't like the blues that were chosen. So, I adjusted the blues and removed one blue and one green color to add in some browns.

Of course, there are pictures where the Windows palette will render a better picture than my custom palette. But, for most pictures, I've found that my palette does a better job.

  

 

 


Programmer's Section


CodeLab Options

CodeLab contains an option on the "save as dll" screen to force the effect to run as a single thread. Normally this is not a good idea because it slows down your effect. But, you can see here that it is necessary to process each row in order because values are being added to future pixels.

This option can be added to your CodeLab script by using the following comment:

 

// Force Single Threaded

  

If you want to see this "comment" in action, here is the complete example...

  

  

Complete Source Code

Here is the complete CodeLab script for the dithering effect you can download above.

// Title: BoltBait's Floyd-Steinberg Dithering Effect v1.0
// Author: BoltBait
// Name: Floyd-Steinberg Dithering
// Submenu: Stylize
// Force Single Threaded
// Keywords: Floyd|Steinberg|Dithering|Dither|Error|Diffusion
// Desc: Dither selected pixels
// URL: http://www.BoltBait.com/pdn
#region UICode
byte Amount1 = 0; // Palette type|Black & White|4 shades of gray|8 shades of gray|4 Colors CMYK|16 Color Original Windows Palette|16 Color Custom Palette
byte Amount2 = 0; // Dithering method|Floyd-Steinberg (1/16)|Custom (1/32)
#endregion

byte PlusTruncate(byte a, int B)
{
    int c = a + b;
    if (c < 0) return 0;
    if (c > 255) return 255;
    return (byte)c;
}

Color FindNearestColor(Color color, Color[] palette)
{
    int minDistanceSquared = 255 * 255 + 255 * 255 + 255 * 255 + 1;
    byte bestIndex = 0;
    for (byte i = 0; i < palette.Length; i++)
    {
        int Rdiff = color.R - palette[i].R;
        int Gdiff = color.G - palette[i].G;
        int Bdiff = color.B - palette[i].B;
        int distanceSquared = Rdiff * Rdiff + Gdiff * Gdiff + Bdiff * Bdiff;
        if (distanceSquared < minDistanceSquared)
        {
            minDistanceSquared = distanceSquared;
            bestIndex = i;
            if (minDistanceSquared < 1) break;
        }
    }
    return palette[bestIndex];
}

// Setup for using pixel op
private UnaryPixelOps.Desaturate desaturateOp = new UnaryPixelOps.Desaturate();

// Here is the main render loop function
void Render(Surface dst, Surface src, Rectangle rect)
{
    // Call the copy function
    dst.CopySurface(src,rect.Location,rect);

    Color[] DitheringPalette = new Color[] { Color.Black, Color.White };
    
    switch(Amount1)
    {
        case 0:
            // black and white
            DitheringPalette = new Color[] { Color.Black, Color.White };
            break;
        case 1:
            // 4 shades of gray
            DitheringPalette = new Color[] { Color.White, Color.Silver, Color.Gray, Color.Black };
            break;
        case 2:
            // 8 shades of gray
            DitheringPalette = new Color[] { Color.FromArgb(0,0,0), Color.FromArgb(36,36,36), Color.FromArgb(72,72,72), Color.FromArgb(108,108,108), Color.FromArgb(144,144,144), Color.FromArgb(180,180,180), Color.FromArgb(216,216,216), Color.FromArgb(255,255,255) };
            break;
        case 3:
            // 4 color: CMYK 
            DitheringPalette = new Color[] { Color.White, Color.Cyan, Color.Yellow, Color.Magenta, Color.Black };
            break;
        case 4:
            // The original 16 color Windows palette
            DitheringPalette = new Color[] { Color.White, Color.Silver, Color.Gray, Color.Black,
            Color.Red, Color.Maroon, Color.Yellow, Color.Olive, Color.Lime, Color.Green,
            Color.Aqua, Color.Teal, Color.Blue, Color.Navy, Color.Fuchsia, Color.Purple };
            break;
        case 5:
            // Custom 16 color palette
            DitheringPalette = new Color[] { Color.White, Color.LightGray, Color.FromArgb(77,77,77), Color.Black, // grays
            Color.Red, Color.Maroon, Color.Yellow, Color.Chocolate, Color.Brown, Color.LimeGreen, Color.DarkGreen, // red brown green
            Color.LightSkyBlue, Color.Blue, Color.FromArgb(79,79,249), Color.FromArgb(255,192,255), Color.Purple }; // blue purple
            break;
    }
    
    Color BestColor;
    ColorBgra BestColora;
    
    // Now in the main render loop, the dst canvas has a copy of the src canvas
    for (int y = rect.Top; y < rect.Bottom; y++)
    {
        if (IsCancelRequested) return;
        for (int x = rect.Left; x < rect.Right; x++)
        {
            if (Amount2==0) // Floyd-Steinberg Dithering
            {
                ColorBgra CurrentPixel = dst[x,y];
                byte A = CurrentPixel.A;
                if (Amount1 < 3) CurrentPixel = desaturateOp.Apply(CurrentPixel);
                Color currentPixel = CurrentPixel.ToColor();

                BestColor = FindNearestColor(currentPixel, DitheringPalette);
                BestColora = ColorBgra.FromColor(BestColor);
                BestColora.A = A;

                // Floyd-Steinberg Dithering
                
                int errorR = currentPixel.R - BestColor.R;
                int errorG = currentPixel.G - BestColor.G;
                int errorB = currentPixel.B - BestColor.B;

                //  - * 7    where *=pixel being processed, -=previously processed pixel
                //  3 5 1    and pixel difference is distributed to neighbor pixels
                //           Note: 7+3+5+1=16 so we divide by 16 (>>4) before adding.

                if (x + 1 < rect.Right)
                {
                    dst[x + 1, y + 0] = ColorBgra.FromBgra(
                        PlusTruncate(dst[x + 1, y + 0].B, (errorB * 7) >> 4),
                        PlusTruncate(dst[x + 1, y + 0].G, (errorG * 7) >> 4),
                        PlusTruncate(dst[x + 1, y + 0].R, (errorR * 7) >> 4),
                        dst[x+1,y].A
                    );
                }
                if (y + 1 < rect.Bottom)
                {
                    if (x - 1 > rect.Left)
                    {
                        dst[x - 1, y + 1] = ColorBgra.FromBgra(
                            PlusTruncate(dst[x - 1, y + 1].B, (errorB * 3) >> 4),
                            PlusTruncate(dst[x - 1, y + 1].G, (errorG * 3) >> 4),
                            PlusTruncate(dst[x - 1, y + 1].R, (errorR * 3) >> 4),
                            dst[x-1,y+1].A
                        );
                    }
                    dst[x - 0, y + 1] = ColorBgra.FromBgra(
                        PlusTruncate(dst[x - 0, y + 1].B, (errorB * 5) >> 4),
                        PlusTruncate(dst[x - 0, y + 1].G, (errorG * 5) >> 4),
                        PlusTruncate(dst[x - 0, y + 1].R, (errorR * 5) >> 4),
                        dst[x-0,y+1].A
                    );
                    if (x + 1 < rect.Right)
                    {
                        dst[x + 1, y + 1] = ColorBgra.FromBgra(
                            PlusTruncate(dst[x + 1, y + 1].B, (errorB * 1) >> 4),
                            PlusTruncate(dst[x + 1, y + 1].G, (errorG * 1) >> 4),
                            PlusTruncate(dst[x + 1, y + 1].R, (errorR * 1) >> 4),
                            dst[x+1,y+1].A
                        );
                    }
                }
            }
            else // Custom Dithering
            {
                ColorBgra CurrentPixel = dst[x,y];
                byte A = CurrentPixel.A;
                if (Amount1 < 3) CurrentPixel = desaturateOp.Apply(CurrentPixel);
                Color currentPixel = CurrentPixel.ToColor();

                BestColor = FindNearestColor(currentPixel, DitheringPalette);
                BestColora = ColorBgra.FromColor(BestColor);
                BestColora.A = A;

                // Custom 1/32 Dithering
                
                int errorR = currentPixel.R - BestColor.R;
                int errorG = currentPixel.G - BestColor.G;
                int errorB = currentPixel.B - BestColor.B;

                //  - - # 8 4    where *=pixel being processed, -=previously processed pixel
                //  0 4 8 4 1    and pixel difference is distributed to neighbor pixels
                //  0 0 2 1 0 

                if (x + 1 < rect.Right)
                {
                    dst[x + 1, y + 0] = ColorBgra.FromBgra(
                        PlusTruncate(dst[x + 1, y + 0].B, errorB >> 2),
                        PlusTruncate(dst[x + 1, y + 0].G, errorG >> 2),
                        PlusTruncate(dst[x + 1, y + 0].R, errorR >> 2),
                        dst[x+1,y].A
                    );
                }
                if (x + 2 < rect.Right)
                {
                    dst[x + 2, y + 0] = ColorBgra.FromBgra(
                        PlusTruncate(dst[x + 2, y + 0].B, errorB >> 3),
                        PlusTruncate(dst[x + 2, y + 0].G, errorG >> 3),
                        PlusTruncate(dst[x + 2, y + 0].R, errorR >> 3),
                        dst[x+2,y].A
                    );
                }
                if (y + 1 < rect.Bottom)
                {
                    if (x - 1 > rect.Left)
                    {
                        dst[x - 1, y + 1] = ColorBgra.FromBgra(
                            PlusTruncate(dst[x - 1, y + 1].B, errorB >> 3),
                            PlusTruncate(dst[x - 1, y + 1].G, errorG >> 3),
                            PlusTruncate(dst[x - 1, y + 1].R, errorR >> 3),
                            dst[x-1,y+1].A
                        );
                    }
                    dst[x, y + 1] = ColorBgra.FromBgra(
                        PlusTruncate(dst[x, y + 1].B, errorB >> 2),
                        PlusTruncate(dst[x, y + 1].G, errorG >> 2),
                        PlusTruncate(dst[x, y + 1].R, errorR >> 2),
                        dst[x,y+1].A
                    );
                    if (x + 1 < rect.Right)
                    {
                        dst[x + 1, y + 1] = ColorBgra.FromBgra(
                            PlusTruncate(dst[x + 1, y + 1].B, errorB >> 3),
                            PlusTruncate(dst[x + 1, y + 1].G, errorG >> 3),
                            PlusTruncate(dst[x + 1, y + 1].R, errorR >> 3),
                            dst[x+1,y+1].A
                        );
                    }
                    if (x + 2 < rect.Right)
                    {
                        dst[x + 2, y + 1] = ColorBgra.FromBgra(
                            PlusTruncate(dst[x + 2, y + 1].B, errorB >> 5),
                            PlusTruncate(dst[x + 2, y + 1].G, errorG >> 5),
                            PlusTruncate(dst[x + 2, y + 1].R, errorR >> 5),
                            dst[x+2,y+1].A
                        );
                    }
                }
                if (y + 2 < rect.Bottom)
                {
                    dst[x, y + 2] = ColorBgra.FromBgra(
                        PlusTruncate(dst[x, y + 2].B, errorB >> 4),
                        PlusTruncate(dst[x, y + 2].G, errorG >> 4),
                        PlusTruncate(dst[x, y + 2].R, errorR >> 4),
                        dst[x,y+2].A
                    );
                    if (x + 1 < rect.Right)
                    {
                        dst[x + 1, y + 2] = ColorBgra.FromBgra(
                            PlusTruncate(dst[x + 1, y + 2].B, errorB >> 5),
                            PlusTruncate(dst[x + 1, y + 2].G, errorG >> 5),
                            PlusTruncate(dst[x + 1, y + 2].R, errorR >> 5),
                            dst[x+1,y+2].A
                        );
                    }
                }
            }
            dst[x,y] = BestColora;
        }
    }
}

Here is the palette file used for dithering:

; paint.net Palette File
; Lines that start with a semicolon are comments
; Colors are written as 8-digit hexadecimal numbers: aarrggbb
; For example, this would specify green: FF00FF00
; The alpha ('aa') value specifies how transparent a color is. FF is fully opaque, 00 is fully transparent.
; A palette must consist of ninety six (96) colors. If there are less than this, the remaining color
; slots will be set to white (FFFFFFFF). If there are more, then the remaining colors will be ignored.
FFFFFFFF
FF000000
00FFFFFF
FFFFFFFF
FFC0C0C0
FF808080
FF000000
00FFFFFF
FFFFFFFF
FFD8D8D8
FFB4B4B4
FF909090
FF6C6C6C
FF484848
FF242424
FF000000
FFFFFFFF
FFC0C0C0
FF808080
FF000000
FFFF0000
FF800000
FFFFFF00
FF808000
FF00FF00
FF008000
FF00FFFF
FF008080
FF0000FF
FF000080
FFFF00FF
FF800080
FFFFFFFF
FFD3D3D3
FF4D4D4D
FF000000
FFFF0000
FF800000
FFFFFF00
FFD2691E
FFA52A2A
FF32CD32
FF006400
FF87CEFA
FF4F4FF9
FF0000FF
FFFFC0FF
FF800080
FFFFFFFF
FF00FFFF
FFFF00FF
FFFFFF00
FF000000
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF

Enjoy! :D:beer:

__________________________

5

Share this post


Link to post
Share on other sites

Nice Job, BB. Brings back BBS memories.

0

Share this post


Link to post
Share on other sites

So if I Build my CodeLab dll with this version, and Force Single Threaded is checked, then it won't break the execution into several different chunks, instead running this all at once? I kindof need this as well, since what I'm doing is across the full image and selection shape won't really matter at all. I'll try this one out.

0

Share this post


Link to post
Share on other sites

I recently got a pebble watch, and came across this amazing plugin when trying to make a custom watchface. I needed to dither an image, and this seemed to almost be able to do it.

 

I edited the plugin with the Pebble Time palette, and figured it would be worth posting here.

I've included the edited source, the icon, the palette text file I made, and the compiled plugin.

 

Download Here

 

Hopefully this is useful for someone!

1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0