Posterization filter explained?

Processing Beginners
6

Here it is!

I implemented three different palettes:

  • Random palette (with random colors)
  • Standard palette (RGB cube)
  • Adaptive palette (with median cut algorithm)

You can click on the different buttons to switch the palette and press - or + to add/ remove colors from the palette.

Screenshot from 2021-09-01 20-41-24
Screenshot from 2021-09-01 20-41-241200×699 123 KB 

/**
 * Quantize colors interface
 * Topic: https://discourse.processing.org/t/posterization-filter-explained
 * Joseph HENRY
 */

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * Generic class for a palette
 */
abstract class Palette {
  IntList colors;

  Palette() {
    colors = new IntList();
  }

  void addColor(color c) {
    colors.append(c);
  }

  void addRandomColor() {
    colors.append(color(random(255), random(255), random(255)));
  }

  color getClosestColorTo(color c) {
    int minIndex = 0;
    float minDistance = distanceBetweenColorsSq(c, colors.get(0));

    for (int i = 1; i < colors.size(); i++) {
      float distance = distanceBetweenColorsSq(c, colors.get(i));

      if (distance < minDistance) {
        minIndex = i;
        minDistance = distance;
      }
    }

    return colors.get(minIndex);
  }

  abstract String toString();
  abstract void increase();
  abstract void decrease();

  void display(int x, int y, int w, int h) {
    int xSquares = 1;

    while (xSquares * ((h * xSquares) / (float) w) < colors.size()) {
      xSquares++;
    }

    float s = (float) w / xSquares;
    int ySquares = int(h / s);

    stroke(0);

    pushMatrix();
    translate(x, y);
    for (int i = 0; i < xSquares; i++) {
      for (int j = 0; j < ySquares; j++) {
        int loc = i + j * xSquares;
        if (loc >= colors.size()) break;
        fill(colors.get(loc));
        square(i * s, j * s, s);
      }
    }
    popMatrix();
  }
}

/**
 * Palette with random colors
 */
class RandomPalette extends Palette {
  RandomPalette(int n) {
    for (int i = 0; i < n; i++) {
      addRandomColor();
    }
  }

  void increase() {
    addRandomColor();
  }

  void decrease() {
    colors.pop();
  }

  String toString() {
    return "Random palette (" + colors.size() + " colors)";
  }
}

/**
 * Standard palette with RGB cube
 */
class StandardPalette extends Palette {
  int power;

  StandardPalette(int power) {
    this.power = power;
    computeColors();
  }

  void increase() {
    power++;
    computeColors();
  }

  void decrease() {
    power--;
    if (power <= 0) power = 1;
    computeColors();
  }

  /**
   * Compute colors by dividing a 3D RGB cube
   */
  void computeColors() {
    colors.clear();

    float offset = (float) 255 / power;

    for (int x = 0; x <= power; x++) {
      float r = x * offset;
      for (int y = 0; y <= power; y++) {
        float g = y * offset;
        for (int z = 0; z <= power; z++) {
          addColor(color(r, g, z * offset));
        }
      }
    }
  }

  String toString() {
    return str(power * 3) + " bit palette";
  }
}

/**
 * Used to sort a list of colors
 */
class ColorComparator implements Comparator<Integer> {
  int shift;

  ColorComparator(int shift) {
    this.shift = shift;
  }

  int compare(Integer o1, Integer o2) {
    float a = ((o1 >> shift) & 0xFF);
    float b = ((o2 >> shift) & 0xFF);
    if (a < b) return -1;
    else if (a > b) return 1;
    else return 0;
  }
}

/**
 * Palette where the colors are statistically choosen
 */
class AdaptivePalette extends Palette {
  PImage fromImg;
  int n;

  AdaptivePalette(PImage img, int n) {
    this.n = n;
    this.fromImg = img.copy();
    compute();
  }

  void increase() {
    n *= 2;
    compute();
  }

  void decrease() {
    n /= 2;
    if (n <= 1) n = 1;
    compute();
  }
  
  /**
   * Implementation of the median cut algorithm
   * See: https://en.wikipedia.org/wiki/Median_cut
   */
  void compute() {
    colors.clear();

    fromImg.loadPixels();
    List<List<Integer>> buckets = new ArrayList();

    // Put all the pixels into a bucket
    buckets.add(new ArrayList());
    for (int i = 0; i < fromImg.pixels.length; i++) buckets.get(0).add(fromImg.pixels[i]);

    // Continue dividing buckets until we reach the color number target
    while (buckets.size() != n) {
      List<List<Integer>> newBuckets = new ArrayList();

      for (List<Integer> bucket : buckets) {
        // Compute the greatest range between RGB
        float minR = 256;
        float maxR = -1;
        float minG = 256;
        float maxG = -1;
        float minB = 256;
        float maxB = -1;

        for (int i = 0; i < bucket.size(); i++) {
          color c = bucket.get(i);
          float r = (c >> 16) & 0xFF;
          float g = (c >> 8) & 0xFF;
          float b = (c & 0xFF);

          if (r < minR) minR = r;
          if (r > maxR) maxR = r;

          if (g < minG) minG = g;
          if (g > maxG) maxG = g;

          if (b < minB) minB = b;
          if (b > maxB) maxB = b;
        }

        float rangeR = maxR - minR;
        float rangeG = maxG - minG;
        float rangeB = maxB - minB;

        // Store the shift so we can compare the colors later
        int shift = 0;
        if (rangeR > rangeG && rangeR > rangeB) {
          shift = 16;
        } else if (rangeG > rangeR && rangeG > rangeB) {
          shift = 8;
        }

        // Sort the bucket
        Collections.sort(bucket, new ColorComparator(shift));

        // Cut the bucket in half
        int middle = bucket.size() / 2;
        newBuckets.add(bucket.subList(0, middle));
        newBuckets.add(bucket.subList(middle, bucket.size()));
      }

      // Replace by the new buckets
      buckets = newBuckets;
    }

    // Compute the average colors for each bucket
    for (List<Integer> bucket : buckets) {
      float rSum = 0;
      float gSum = 0;
      float bSum = 0;

      for (Integer c : bucket) {
        rSum += (c >> 16) & 0xFF;
        gSum += (c >> 8) & 0xFF;
        bSum += c & 0xFF;
      }

      colors.append(color(
        (float) rSum / bucket.size(), 
        (float) gSum / bucket.size(), 
        (float) bSum / bucket.size()));
    }
  }

  String toString() {
    return "Adaptive palette (" + n + " colors)";
  }
}

/**
 * Display an image with squares (to remove filtering)
 */
void displayImage(PImage img, String legend, int xPos, int yPos, int scale) {
  noStroke();

  pushMatrix();
  translate(xPos, yPos);

  // Display squares
  for (int x = 0; x < img.width; x++) {
    for (int y = 0; y < img.height; y++) {
      fill(img.pixels[x + y * img.width]);
      square(x * scale, y  * scale, scale);
    }
  }

  // Display legend
  textAlign(CENTER, CENTER);
  fill(255);
  textSize(30);
  text(legend, (img.width * scale) / 2.0, (img.height * scale) - 50);

  popMatrix();
}

/**
 * Computes the distance squared between two colors
 */
float distanceBetweenColorsSq(color c1, color c2) {
  float r2 = (c2 >> 16) & 0xFF;
  float g2 = (c2 >> 8) & 0xFF;
  float b2 = (c2 & 0xFF);

  float r1 = (c1 >> 16) & 0xFF;
  float g1 = (c1 >> 8) & 0xFF;
  float b1 = (c1 & 0xFF);

  return (r2 - r1) * (r2 - r1) + 
    (g2 - g1) * (g2 - g1) + 
    (b2 - b1) * (b2 - b1);
}

/**
 * Color quantize an image with the given palette
 */
PImage quantizeWithPalette(PImage img, Palette palette) {
  PImage copy = img.copy();

  img.loadPixels();
  copy.loadPixels();

  for (int x = 0; x < copy.width; x++) {
    for (int y = 0; y < copy.height; y++) {
      int loc = x + y * copy.width;
      copy.pixels[loc] = palette.getClosestColorTo(img.pixels[loc]);
    }
  }

  return copy;
}

/**
 * Clickable button class
 */
class Button {
  String label;
  int x, y;
  float w, h;
  color bgColor;
  int fontSize = 20;

  Button(String label, int x, int y, color bgColor) {
    this.label = label;
    this.x = x;
    this.y = y;
    this.bgColor = bgColor;
    this.w = textWidth(label) + 10;
    this.h = fontSize * 1.5;
  }

  boolean isMouseHover() {
    return mouseX > x - w / 2 &&
           mouseX < x + w / 2 &&
           mouseY > y - h / 2 &&
           mouseY < y + h / 2;
  }

  void display() {
    display(false);
  }

  void display(boolean active) {
    pushStyle();

    textSize(fontSize);

    rectMode(CENTER);

    if (isMouseHover()) {
      stroke(255);
    } else {
      noStroke();
    }

    if (active) fill(#40805b);
    else fill(bgColor);

    rect(x, y, textWidth(label) + 10, fontSize * 1.7, 5);

    textAlign(CENTER, CENTER);
    fill(255);
    text(label, x, y - 5);

    popStyle();
  }
}

PImage img, quantized;

int currentPaletteIndex = 0;
List<Palette> palettes;

List<Button> buttons;
Button decrease, increase;

Palette currentPalette() {
  return palettes.get(currentPaletteIndex);
}

void quantizeImage() {
  quantized = quantizeWithPalette(img, currentPalette());
}

void setup() {
  size(1200, 700);

  img = loadImage("https://upload.wikimedia.org/wikipedia/commons/d/d7/RGB_24bits_palette_sample_image.jpg");

  palettes = new ArrayList<Palette>() {
    {
      add(new StandardPalette(1));
      add(new RandomPalette(8));
      add(new AdaptivePalette(img, 8));
    }
  };

  quantizeImage();

  // Buttons
  final int buttonYPos = height - 50;
  buttons = new ArrayList<Button>() {
    {
      add(new Button("Standard palette", 100, buttonYPos, color(100)));
      add(new Button("Random palette", 300, buttonYPos, color(100)));
      add(new Button("Adaptive palette", 500, buttonYPos, color(100)));
    }
  };

  decrease = new Button("-", 650, buttonYPos, color(#574fc3));
  increase = new Button("+", 700, buttonYPos, color(#fe3548));
}

void draw() {
  background(50);

  displayImage(img, "24 bit palette", 0, 0, 3);
  displayImage(quantized, currentPalette().toString(), 450, 0, 3);

  currentPalette().display(900, 0, 300, 600);

  for (int i = 0; i < buttons.size(); i++) {
    buttons.get(i).display(i == currentPaletteIndex);
  }

  decrease.display();
  increase.display();
}

void mousePressed() {
  for (int i = 0; i < buttons.size(); i++) {
    Button button = buttons.get(i);

    if (button.isMouseHover()) {
      currentPaletteIndex = i;
      quantizeImage();
      break;
    }
  }
  
  if (decrease.isMouseHover()) {
    currentPalette().decrease();
    quantizeImage();
  }
  
  if (increase.isMouseHover()) {
    currentPalette().increase();
    quantizeImage();
  }
}

void keyPressed() {
  if (keyCode == RIGHT) {
    currentPalette().increase();
    quantizeImage();
  } else if (keyCode == LEFT) {
    currentPalette().decrease();
    quantizeImage();
  }
}
2 Likes