Posterization filter explained?

Hi!
I saw an interesting filter recently, its called posterization. In short terms, it sets the maximum number of colors in an image.
image

You set the maximum of n-colors and only use them.

So I have a few questions:

  • How do you choose the shades used
  • How do you pick what shade it shifts to (is it distance in 3D space?)
  • Is there a way to reverse it?

Thank you!

2 Likes

Hi @CodeMasterX,

Interesting topic! :yum:

Choosing the shades is actually determining which palette to use. There are different types of palettes: Standard or Adaptive

Standard palettes are palettes who have a fixed number of colors, like RBG palettes:

From the Wikipedia page:

These full RGB palettes employ the same number of bits to store the relative intensity for the red, green and blue components of every image’s pixel color. Thus, they have the same number of levels per channel and the total number of possible colors is always the cube of a power of two. It should be understood that ‘when developed’ many of these formats were directly related to the size of some host computers ‘natural word length’ in bytes—the amount of memory in bits held by a single memory address such that the CPU can grab or put it in one operation.

If you look at the Color cube, it’s always determined by dividing it into power of two so that’s how colors are chosen.


But if you have an image that is mostly red, then you are missing a lot of red shades so that’s why Adaptive palettes are useful.

If you read the Adaptive palette section on Wikipedia, it’s written:

Those whose whole number of available indexes are filled with RGB combinations selected from the statistical order of appearance (usually balanced) of a concrete full true color original image. There exist many algorithms to pick the colors through color quantization; one well known is the Heckbert’s median-cut algorithm.

Adaptive palettes only work well with a unique image. Trying to display different images with adaptive palettes over an 8-bit display usually results in only one image with correct colors, because the images have different palettes and only one can be displayed at a time.



You can see a list of common palettes here:

From the Color quantization page:

If the palette is fixed, as is often the case in real-time color quantization systems such as those used in operating systems, color quantization is usually done using the “straight-line distance” or “nearest color” algorithm, which simply takes each color in the original image and finds the closest palette entry, where distance is determined by the distance between the two corresponding points in three-dimensional space. In other words, if the colors are ( r 1 , g 1 , b 1 ) and ( r 2 , g 2 , b 2 ) , we want to minimize the Euclidean distance

So yes you can use the Euclidean distance in 3D space to pick the corresponding color!

I don’t think so, since you are loosing color information when you quantize the colors, there is no way you can get back the full spectrum of colors.

Meanwhile there’s ways to minimize this effect with filtering:

3 Likes

Here is the result of what I got! Thank you!

I am just using the default method of using the color cube. I will post the code in my project library #4

2 Likes

Awesome! I am also going to post my code on this thread!

I also found a related topic:

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.

/**
 * 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

Here is the Processing implementation of POSTERIZE.

The input param / levels is used to bin each channel into colors, and levels must be between 2 and 255. Levels is levels per channel – each channel is extracted, multiplied by the desired number of levels to create higher bits for the levels, then shifted right to eliminate differences between groups in the original lower bits, before being divided and written back into each channel.

There is no choosing color / clustering / etc. – the level input to this process always creates a uniform subdivision of each 8bit color channel into however many groups – 2, 8, 32, et cetera.

This can be used in filter(POSTERIZE, mylevels) directly, or called on a PImage / PGraphics object.

2 Likes