Floyd-Steinberg dithering (Java)

From LiteratePrograms

Other implementations: C | Java

This is an implementation of Floyd-Steinberg dithering in Java for color images. As input we receive an image in 24-bit RGB format and a palette of at most 256 colors, and as output we produce a palettized image where each pixel value is an index into the palette. The images are represented as arrays of arrays where the first index is y and the second index is x.

<<type declarations>>=
class RGBTriple {
    public final byte[] channels;
    public RGBTriple() { channels = new byte[3]; }
    public RGBTriple(int R, int G, int B)
    { channels = new byte[]{(byte)R, (byte)G, (byte)B}; }
}

Note that we reserve a full 8 bits for each pixel in the output even when the palette is small — we leave compacting of bits to the caller.

On some platforms, the RGBTriple structure may be padded with extra bits, resulting in wasted space. On such platforms an alternative implementation is to directly use arrays of unsigned characters for pixel data, indexed using macros.

Next we implement the core algorithm. Floyd-Steinberg is based on the concept of error diffusion, where we choose the nearest palette color that we can to the current pixel, and then compute the difference of that color from the original color in each RGB channel. Pieces of this difference are dispersed throughout several adjacent pixels not yet visited:

<<FloydSteinbergDither definition>>=
public static byte[][] floydSteinbergDither(RGBTriple[][] image, RGBTriple[] palette)
{
    set up result image
    loop over all pixels
        RGBTriple currentPixel = image[y][x];
        find nearest color to current pixel
        compute and disperse error
    close loop over all pixels
    return result;
}

There are many ways to find the nearest palette color with varying levels of efficiency and quality. Here we use a trivial algorithm that finds the color with minimum straight-line distance in the color cube from the given color:

<<find nearest color to current pixel>>=
byte index = findNearestColor(currentPixel, palette);
result[y][x] = index;
<<FindNearestColor definition>>=
private static byte findNearestColor(RGBTriple color, RGBTriple[] palette) {
    int minDistanceSquared = 255*255 + 255*255 + 255*255 + 1;
    byte bestIndex = 0;
    for (byte i = 0; i < palette.length; i++) {
        int Rdiff = (color.channels[0] & 0xff) - (palette[i].channels[0] & 0xff);
        int Gdiff = (color.channels[1] & 0xff) - (palette[i].channels[1] & 0xff);
        int Bdiff = (color.channels[2] & 0xff) - (palette[i].channels[2] & 0xff);
        int distanceSquared = Rdiff*Rdiff + Gdiff*Gdiff + Bdiff*Bdiff;
        if (distanceSquared < minDistanceSquared) {
            minDistanceSquared = distanceSquared;
            bestIndex = i;
        }
    }
    return bestIndex;
}

Note that although the actual straight-line distance is the square root of the quantity measured above, the square of the distance (which is much easier to compute) is minimized by the same color as the distance itself because x² is strictly increasing on the positive real numbers.

Now, we do the actual dithering. The Floyd-Steinberg dithering matrix looks like this:

—	—	—
—	X	7/16
3/16	5/16	1/16

For each channel, we determine the difference between the original and palettized value of the pixel labeled "X". We add 7/16 of this difference to the pixel to its right, 5/16 to the pixel below it, and so on. The following code implements this:

int error = (currentPixel.channels[i] & 0xff) - (palette[index].channels[i] & 0xff);
image[y+0][x+1].channels[i] += (error*7) >> 4;
image[y+1][x-1].channels[i] += (error*3) >> 4;
image[y+1][x+0].channels[i] += (error*5) >> 4;
image[y+1][x+1].channels[i] += (error*1) >> 4;

However, it's possible that enough error could accumulate in a pixel to cause overflow or underflow. Because "wrap around" semantics cause undesirable artifacts, we instead truncate the value to 0 or 255 — this is the most expensive part of the algorithm:

<<plus truncate macro>>=
private static byte plus_truncate_uchar(byte a, int b) {
    if ((a & 0xff) + b < 0)
        return 0;
    else if ((a & 0xff) + b > 255)
        return (byte)255;
    else
        return (byte)(a + b);
}
<<compute and disperse error macro>>=
int error = (currentPixel.channels[i] & 0xff) - (palette[index].channels[i] & 0xff);
if (x + 1 < image[0].length) {
    image[y+0][x+1].channels[i] =
        plus_truncate_uchar(image[y+0][x+1].channels[i], (error*7) >> 4);
}
if (y + 1 < image.length) {
    if (x - 1 > 0) {
        image[y+1][x-1].channels[i] =
            plus_truncate_uchar(image[y+1][x-1].channels[i], (error*3) >> 4);
    }
    image[y+1][x+0].channels[i] =
        plus_truncate_uchar(image[y+1][x+0].channels[i], (error*5) >> 4);
    if (x + 1 < image[0].length) {
        image[y+1][x+1].channels[i] =
            plus_truncate_uchar(image[y+1][x+1].channels[i], (error*1) >> 4);
    }
}

Additionally, we must ensure that we ignore pixels outside of the image area. This might be made more efficient by placing the image inside a buffer with a border around it, but here we just test for it.

This implementation actually modifies the source image in place for efficiency and simplicity, but we could avoid this by instead computing the value passed to findNearestColor based on the error of adjacent previously visited pixels.

Now we simply invoke the macro once for each channel:

<<compute and disperse error>>=
for (int i = 0; i < 3; i++)
{
    compute and disperse error macro
}

To loop over the pixels, we proceed in reading order, left to right, top to bottom:

<<loop over all pixels>>=
for (int y = 0; y < image.length; y++) {
    for (int x = 0; x < image[y].length; x++) {
<<close loop over all pixels>>=
    }
}

Another common order used in Floyd-Steinberg dithering alternates between traversing rows left-to-right and right-to-left, which helps avoid some kinds of artifacts. The dithering matrix must be reflected when traversing right-to-left. For simplicity we don't do this here.

Finally, we initialize the result image with the metadata from the original image and a sufficiently large buffer to hold all the pixels' indexes:

<<set up result image>>=
byte[][] result = new byte[image.length][image[0].length];

Finally, we put together the implementation in a source file for use:

<<FloydSteinbergDither.java>>=
imports
type declarations
public class FloydSteinbergDither
{
    plus truncate macro
    FindNearestColor definition
    FloydSteinbergDither definition
    main method
}

This completes the implementation.

Sample code

The following sample code reads in an RGB image in a raw image file format, dithers it to a specific optimized 16-color palette found using Photoshop, and writes the output to a raw image file. The original image and dithered result are shown below. The raw input image file for this sample can be downloaded at Image:Amorphophallus titanum USBG small.raw.

<<imports>>=
import java.io.*;
<<main method>>=
public static void main(String[] args) throws IOException {
    RGBTriple[][] image = new RGBTriple[145][100];
    InputStream raw_in = new BufferedInputStream(new FileInputStream(args[0]));
    for (int y = 0; y < image.length; y++) {
        for (int x = 0; x < image[0].length; x++) {
            image[y][x] = new RGBTriple();
            raw_in.read(image[y][x].channels, 0, 3);
        }
    }
    raw_in.close();
    RGBTriple[] palette = {
        new RGBTriple(149, 91, 110),
        new RGBTriple(176, 116, 137),
        new RGBTriple(17, 11, 15),
        new RGBTriple(63, 47, 69),
        new RGBTriple(93, 75, 112),
        new RGBTriple(47, 62, 24),
        new RGBTriple(76, 90, 55),
        new RGBTriple(190, 212, 115),
        new RGBTriple(160, 176, 87),
        new RGBTriple(116, 120, 87),
        new RGBTriple(245, 246, 225),
        new RGBTriple(148, 146, 130),
        new RGBTriple(200, 195, 180),
        new RGBTriple(36, 32, 27),
        new RGBTriple(87, 54, 45),
        new RGBTriple(121, 72, 72)
    };
    byte[][] result = floydSteinbergDither(image, palette);
    OutputStream raw_out = new BufferedOutputStream(new FileOutputStream(args[1]));
    for (int y = 0; y < result.length; y++) {
        for (int x = 0; x < result[y].length; x++) {
            raw_out.write(palette[result[y][x]].channels, 0, 3);
        }
    }
    raw_out.close();
}

Download code