How to convert a 24 Bit PNG to 3 Bit PNG using Floyd–Steinberg dithering?

Question

How to convert a 24 Bit PNG to 3 Bit PNG using Floyd–Steinberg dithering? java.awt.image.BufferedImage should be used to get and set RGB values.

On wikipedia, an example is given on how to convert a 16 Bit to a 8 Bit image:

find_closest_palette_color(oldpixel) = (oldpixel + 128) / 256

Based on this, are there any ideas on how to fit the example above in order to achieve the goal?

Partridgeberry

Answer 1

Use image.getRGB(x, y) and image.setRGB(x, y, color) and use the pseudocode from the wikipedia article. Note that code on the wiki does not say how to "subtract", "add" and "multiply" colors. (The T3 class below handles "color" manipulation.)

The code below will produce this screenshot:

class Test {
  private static BufferedImage floydSteinbergDithering(BufferedImage img) {

    C3[] palette = new C3[] {
        new C3(  0,   0,   0),
        new C3(  0,   0, 255),
        new C3(  0, 255,   0),
        new C3(  0, 255, 255),
        new C3(255,   0,   0),
        new C3(255,   0, 255),
        new C3(255, 255,   0),
        new C3(255, 255, 255)
    };

    int w = img.getWidth();
    int h = img.getHeight();

    C3[][] d = new C3[h][w];

    for (int y = 0; y < h; y++) 
      for (int x = 0; x < w; x++) 
        d[y][x] = new C3(img.getRGB(x, y));

    for (int y = 0; y < img.getHeight(); y++) {
      for (int x = 0; x < img.getWidth(); x++) {

        C3 oldColor = d[y][x];
        C3 newColor = findClosestPaletteColor(oldColor, palette);
        img.setRGB(x, y, newColor.toColor().getRGB());

        C3 err = oldColor.sub(newColor);

        if (x+1 < w)         d[y  ][x+1] = d[y  ][x+1].add(err.mul(7./16));
        if (x-1>=0 && y+1<h) d[y+1][x-1] = d[y+1][x-1].add(err.mul(3./16));
        if (y+1 < h)         d[y+1][x  ] = d[y+1][x  ].add(err.mul(5./16));
        if (x+1<w && y+1<h)  d[y+1][x+1] = d[y+1][x+1].add(err.mul(1./16));
      }
    }

    return img;
  }

  private static C3 findClosestPaletteColor(C3 c, C3[] palette) {
    C3 closest = palette[0];

    for (C3 n : palette) 
      if (n.diff(c) < closest.diff(c))
        closest = n;

    return closest;
  }

  public static void main(String[] args) throws IOException {

    final BufferedImage normal  = ImageIO.read(new URL("http://upload.wikimedia.org/wikipedia/en/2/24/Lenna.png")).getSubimage(100, 100, 300, 300);
    final BufferedImage dietered = floydSteinbergDithering(ImageIO.read(new URL("http://upload.wikimedia.org/wikipedia/en/2/24/Lenna.png"))).getSubimage(100, 100, 300, 300);

    JFrame frame = new JFrame("Test");
    frame.setLayout(new GridLayout(1, 2));

    frame.add(new JComponent() {
      @Override
      protected void paintComponent(Graphics g) {
         super.paintComponent(g);
         g.drawImage(normal, 0, 0, this);
      }
    });
    frame.add(new JComponent() {
      @Override
      protected void paintComponent(Graphics g) {
         super.paintComponent(g);
         g.drawImage(dietered, 0, 0, this);
      }
    });

    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setSize(400, 400);
    frame.setVisible(true);
  }


  static class C3 {
    int r, g, b;

    public C3(int c) {
      Color color = new Color(c);
      this.r = color.getRed();
      this.g = color.getGreen();
      this.b = color.getBlue();
    }
    public C3(int r, int g, int b) {
      this.r = r;
      this.g = g;
      this.b = b;
    }

    public C3 add(C3 o) {
      return new C3(r + o.r, g + o.g, b + o.b);
    }
    public C3 sub(C3 o) {
      return new C3(r - o.r, g - o.g, b - o.b);
    }
    public C3 mul(double d) {
      return new C3((int) (d * r), (int) (d * g), (int) (d * b));
    }
    public int diff(C3 o) {
      return Math.abs(r - o.r) +  Math.abs(g - o.g) +  Math.abs(b - o.b);
    }

    public int toRGB() {
      return toColor().getRGB();
    }
    public Color toColor() {
      return new Color(clamp(r), clamp(g), clamp(b));
    }
    public int clamp(int c) {
      return Math.max(0, Math.min(255, c));
    }
  }
}

Hubsher

This code is very specific to a 3-bit conversion and wouldn't work for any other bit depth, and it doesn't allow for the use of an optimized palette. Still nice to see working code with an example. – Gaven

Another thing most people don't realize about dithering is that you must take into account the gamma curve. A value of 128 will generate 255 half the time and 0 the other half, but this should properly be the output of an input value of 186. – Gaven

@Mark: added palette.. your probably right, I just implemented the wikipedia version! – Hubsher

One final note, by adding the errors back into the image you risk anomalies when the sum is greater than 255 or less than 0. Lest you think I'm complaining too much, I've already given you a +1. – Gaven

@Mark: Oo, posted the wrong code - updating!! Good catch, I refactored too much when adding the T3 class, thanks! – Hubsher

@dacwe, I think I made a mistake - looking at the code again I see I missed the clamp method. Sorry. – Gaven

@Mark: Hum yes, but should it be clamped before or after the next iteration...? – Hubsher

If you're going to the trouble of keeping your error-corrected pixels at a higher bit depth, there's really no need to clamp at all - findClosestPaletteColor will work regardless. I was more worried about the overflow/underflow problem when working in 8 bits. Errors caused by clamping would be minor in comparison, especially since Floyd-Steinberg tends to self correct. To be honest I liked your original code the best, even with all the caveats. – Gaven

Doh, but thanks anyways! :) These algorithms are fun though! :) – Hubsher

This implementation is missing the diff method I believe. – Lode

This was very useful for me, so I added gamma correction and put it up on github for anyone else that could use it. cheers. gist.github.com/naikrovek/e44f0309012fda3fe8c1 – Lathrop

Answer 2

source code needs the missing method "diff" in the static class C3. otherwise, it doesn't compile or work.

here's the missing diff method:

public int diff(C3 o) {
    int Rdiff = o.r - this.r;
    int Gdiff = o.g - this.g;
    int Bdiff = o.b - this.b;
    int distanceSquared = Rdiff*Rdiff + Gdiff*Gdiff + Bdiff*Bdiff;
    return distanceSquared;
}

Collum

Answer 3

Although this is an old post, it might be increasingly relevant at the time of writing, with the advent of e-ink labels in shops, where colors available are usually only BWR (black, white and red, 3 colors) or maybe in some instances BWRY (4 colors) In automating making images in this regard, I implemented the accepted answer at https://gist.github.com/naikrovek/643a9799171d20820cb9 as my floydSteinbergDithering-algorithm. Although this seems to work fine on eg 8-bit palettes, there seem to be a bug in the algorithm that makes poor results when using palettes with only 3 or 4 colors. This can be spotted easily in the beak of scrooge here (see image)

If testing the same image on eg ditherit.com, the beak is fine. However, I found that this bug does not occur in the java implementation at https://github.com/Regarrzo/Java-Floyd-Steinberg-Dithering/ (se example image for results)

I hope this can improve image quality for other people working with BWR palette on those small e-ink-labels ;-)

Auld

Answer 4

You can use JAI: http://java.sun.com/products/java-media/jai/forDevelopers/jai1_0_1guide-unc/Image-manipulation.doc.html

Resiniferous

Answer 5

By the way, here is the code and live demo of Floyd-Steinberg in video! :)

http://blog.ivank.net/floyd-steinberg-dithering-in-javascript.html

Euphemism