# Posterization filter explained?

**URL:** <https://discourse.processing.org/t/posterization-filter-explained/32001>\
**Category:** Beginners\
**Created:** [August 29, 2021, 9:40pm UTC](https://discourse.processing.org/t/posterization-filter-explained/32001 "2021-08-29T21:40:07Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![CodeMasterX](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/codemasterx/32/2942_2.png) [@CodeMasterX](https://discourse.processing.org/u/CodeMasterX)\
**Post date:** [August 29, 2021, 9:40pm UTC](https://discourse.processing.org/t/posterization-filter-explained/32001/1 "2021-08-29T21:40:07Z")

</div>

Hi!  
I saw an interesting filter recently, its called posterization. In short terms, it sets the maximum number of colors in an image.  
 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/4/422fad9015c2ccf8ca6a7ea9ed1784c12c0fd1cb.jpeg)

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!

---

<div class="post-metadata">

**Author:** ![josephh](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/josephh/32/210_2.png) [@josephh](https://discourse.processing.org/u/josephh)\
**Post date:** [August 30, 2021, 2:04pm UTC](https://discourse.processing.org/t/posterization-filter-explained/32001/3 "2021-08-30T14:04:26Z")

</div>

Hi @CodeMasterX,

Interesting topic! 😋

> [@CodeMasterX](#):
>
> How do you choose the shades used

Choosing the shades is actually determining which [palette](https://en.wikipedia.org/wiki/Palette_(computing)) 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:

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/4/4fffe67653ae6fad47fabf3ab49ed13f83f46ab2.jpeg)

From the Wikipedia page:

> These full RGB palettes employ the same number of [bits](https://en.wikipedia.org/wiki/Bit) to store the relative intensity for the red, green and blue components of every image’s [pixel](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/List_of_software_palettes#Adaptive_palettes) 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](https://en.wikipedia.org/wiki/False_color#True_color) original image. There exist many algorithms to pick the colors through [color quantization](https://en.wikipedia.org/wiki/Color_quantization); one well known is the Heckbert’s median-cut algorithm.

> Adaptive palettes only work well with a [unique image](https://en.wikipedia.org/wiki/Palette_(computing)#Adaptative_vs._master_palettes). 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.

[![](https://upload.wikimedia.org/wikipedia/commons/7/7c/Adaptative_8bits_palette_sample_image.png) ](https://upload.wikimedia.org/wikipedia/commons/7/7c/Adaptative_8bits_palette_sample_image.png)  
[![](https://upload.wikimedia.org/wikipedia/commons/7/72/Adaptative_8bits_palette_color_test_chart.png) ](https://upload.wikimedia.org/wikipedia/commons/7/72/Adaptative_8bits_palette_color_test_chart.png)

* * *

You can see a list of common palettes here:

> **[List of color palettes](https://en.wikipedia.org/wiki/List_of_color_palettes)**
>
> This article is a list of the color palettes for notable computer graphics, terminals and video game console hardware.
> Only a sample and the palette's name are given here. More specific articles are linked from the name of each palette, for the test charts, samples, simulated images, and further technical details (including references).
> In the past, manufacturers have developed many different display systems in a competitive, non-collaborative basis (with a few exceptions, as the VESA consort...

> [@CodeMasterX](#):
>
> How do you pick what shade it shifts to (is it distance in 3D space?)

From the [Color quantization](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Euclidean_distance)

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

> [@CodeMasterX](#):
>
> Is there a way to reverse it?

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:

> <https://dsp.stackexchange.com/questions/41490/how-to-reverse-color-quantization>

---

<div class="post-metadata">

**Author:** ![CodeMasterX](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/codemasterx/32/2942_2.png) [@CodeMasterX](https://discourse.processing.org/u/CodeMasterX)\
**Post date:** [August 30, 2021, 3:24pm UTC](https://discourse.processing.org/t/posterization-filter-explained/32001/4 "2021-08-30T15:24:27Z")

</div>

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

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/b/b08cc4d3793af09f3213d98df982bd77ab02e812.jpeg)

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

---

<div class="post-metadata">

**Author:** ![josephh](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/josephh/32/210_2.png) [@josephh](https://discourse.processing.org/u/josephh)\
**Post date:** [August 30, 2021, 5:48pm UTC](https://discourse.processing.org/t/posterization-filter-explained/32001/5 "2021-08-30T17:48:28Z")

</div>

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

I also found a related topic:

> [@How to apply color quantization to an image](https://discourse.processing.org/t/how-to-apply-color-quantization-to-an-image/4849):
>
> Is there a simple way (preferably a function) to apply [color quantization](https://en.wikipedia.org/wiki/Color_quantization) to an image? Specifically I’d like to pick a PImage and an int of colours, and it’d reduce the number of colours to that int, trying to keep it as close as possible to the original. For reference, imagemagick can do it easily (I’d link to it, but discourse isn’t letting me): magick input.png +dither -colors 6 output.png outputs an image with 6 colours. Not shades, but colours. The +dither is actually not doing dithering b…

---

<div class="post-metadata">

**Author:** ![josephh](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/josephh/32/210_2.png) [@josephh](https://discourse.processing.org/u/josephh)\
**Post date:** [September 1, 2021, 6:52pm UTC](https://discourse.processing.org/t/posterization-filter-explained/32001/6 "2021-09-01T18:52:21Z")

</div>

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](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/9/93b744d4697a05dac753e0c03657f421362137a8.png)

```processing
/**
 * 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();
  }
}

```

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [September 1, 2021, 7:35pm UTC](https://discourse.processing.org/t/posterization-filter-explained/32001/7 "2021-09-01T19:35:14Z")

</div>

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.

> <https://github.com/processing/processing/blob/a6e0e227a948e7e2dc042c04504d6f5b8cf0c1a6/core/src/processing/core/PImage.java#L1153-L1172>

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

> **[Reference](https://processing.org/reference/filter_.html)**
>
> Filters the image as defined by one of the following modes: THRESHOLD Converts the image to black and white pixels depending if they are above or below the threshold defined by the …

![](https://processing.org/static/b598aad31813f9d69197bda4a003d6ac/c1587/filter_3.webp)