Understanding Colour Quantization
While our eyes can see a vast array of colours, computer graphics employ limited colour palettes in several use cases to depict the majority of the colours we can see in a reasonable amount of space.
The Median Cut is a technique that minimises the number of distinct colours used in an image, generally to make the new image look as closely like the original as possible.
To put it plainly, images are made up of pixels, each of which may be associated with one of 16,777,216 distinct colours in the context of RGB colour space, which is perhaps the most often used colour space.
The best representative subset of colours is chosen as part of colour quantization so that when an identical image is produced with this limited set of colours, it looks similar to the original image.
In the below example, we can see an image of a sunset with several hundred colours is reduced to 2, 4, 8, 16, and 64 colours.
Real-Time Use Case For Colour Quantization
Due to restrictions such as memory and processing capacity, it was usual in the early days of the PC to show images in fewer colours (specifically 2, 4, 16, and max 256 colours). This was accomplished through the use of colour quantization.
With the rapid growth of technology, this is no longer the case. Colour quantization is nowadays used in many places for video/image encoding.
GIF files only support up to 256 colours, necessitating quantization for many images. On the other hand, though PNG pictures can accommodate up to 16 million colours, colour quantization can typically help to reduce file size without sacrificing visual quality.
Many image/video editing apps use colour quantization to render the posterization effect of the original image.
Median Cut Algorithm
There are several algorithms for colour quantization, one such widely used algorithm is Median Cut Algorithm.
Suppose we have an image with an arbitrary number of pixels associating hundreds/thousands of colours and want to generate a palette of n colours.
We will first put all the pixels of the image (that is, their RGB values) in a bucket.
Determine which colour channel (red, green, or blue) has the largest variation among the pixels in the bucket, and then sort the pixels based on the values in that channel. For example, If the red channel has the greatest range, a pixel with an RGB value of (10, 8, 16) is less than a pixel with an RGB value of (100, 2, 24), since 10 < 100.
After sorting the bucket, move the upper half of the pixels to a new bucket.
Now we have 2 buckets, repeat the same steps from step 2 until we get the desired count of buckets (which is equal to the total number of colours that we want to generate as part of our palette i.e, n)
For example, in the below image, we can see a visual representation of how this works.
Let's assume, we have a bucket of 8 colours and we need to find a palette of 4 best representative colours that can be used to represent these 8 colours
First, the bucket is sorted by the red colour channel since R has the highest range
Range R = 246 - 21 = 225
Range G = 185 - 21 = 164
Range B = 224 - 39 = 185
Max (Range r, Range g, Range b) = Max (225, 164, 185) = 225 <-> Range R
Then the sorted bucket is split into two at the median point
Steps 2 and 3 are further repeated until we have the desired set of buckets matching the number of colours to be derived for the palette
Here in our case, the upper half of the bucket is moved into a separate bucket and sorted by blue colour channel and then further divided into two. Finally, the average of RGB individually is computed from the final resulting buckets.
Similarly, the lower half of the bucket is moved into a separate bucket and sorted by red colour channel and then further divided into two and the average value of RGB individually is computed.
In the end, we have the 4 best representative colours.
Implementing Median Cut Algorithm
We will be implementing the median cut algorithm in node js. We will be using a package called get-pixels which helps us to grab all the pixels in an image and return the result as a ndarray of pixels in raster order having shapes equal to [width, height, channels].
//index.js
const swatch = require('./swatch.js')
const fs = require('fs');
const buildHtml = (colors) => {
return `
<!DOCTYPE html>
<head>
<title>Quantized Color Palette</title>
<style>
html, body {
padding: 0;
margin: 0;
height: 100%;
width: 100%;
}
body {
display: flex;
flex-wrap: wrap;
}
.col {
height: 25%;
width: 25%;
}
</style>
</head>
<body>
${colors.reduce((prev, color) => {
return prev + `
<div class="col" style="background-color: rgb(${color.r}, ${color.g}, ${color.b})"></div>
`
}, '')}
</body>
</html>`
}
swatch.load(process.argv[2])
.then((rgbVals) => {
const colors = swatch.quantize(rgbVals)
fs.writeFile('./output.html', buildHtml(colors), (err) => {
if (err) {
console.log(err);
}
console.log("successfully written to file");
})
})
.catch((err) => {
console.log(err);
})
//swatch.js
const getPixels = require("get-pixels");
class Swatch {
static load = (img) => {
return new Promise((resolve, reject) => {
getPixels(img, (err, pixels) => {
if (err) {
reject(err);
}
resolve(Swatch.pixelsByRGB(pixels))
})
})
}
static pixelsByRGB = (pixels) => {
const rgbVals = [];
/* pixel.data is an array containing individual entry for each colour space of rgba values of each pixels in an continous order.
It would look something like [r, g, b, a, r, g, b, a, ...]
*/
for (let i = 0; i < pixels.data.length; i += 4) {
rgbVals.push({
r: pixels.data[i],
g: pixels.data[i + 1],
b: pixels.data[i + 2],
})
}
return rgbVals;
}
static colorChannelWithGreatestRange = (rgbVals) => {
let rMin = Number.NEGATIVE_INFINITY;
let rMax = Number.POSITIVE_INFINITY;
let gMin = Number.NEGATIVE_INFINITY;
let gMax = Number.POSITIVE_INFINITY;
let bMin = Number.NEGATIVE_INFINITY;
let bMax = Number.POSITIVE_INFINITY;
for (let i = 0; i < rgbVals; i++) {
rMin = Math.min(rgbVals[i].r, rMin);
rMax = Math.max(rgbVals[i].r, rMax);
gMin = Math.min(rgbVals[i].g, gMin);
gMax = Math.max(rgbVals[i].g, gMax);
bMin = Math.min(rgbVals[i].b, bMin);
bMax = Math.max(rgbVals[i].b, bMax);
}
const rangeRed = rMax - rMin;
const rangeGreen = gMax - gMin;
const rangeBlue = bMax - bMin;
const rangeMax = Math.max(rangeRed, rangeBlue, rangeGreen);
if (rangeMax === rangeRed) {
return "r";
} else if (rangeMax === rangeGreen) {
return "g";
} else if (rangeMax === rangeBlue) {
return "b";
}
}
static quantize = (rgbVals, initialDepth = 0, maxDepth = 4) => {
if (initialDepth === maxDepth) {
const color = rgbVals.reduce((prev, current) => {
prev.r += current.r;
prev.g += current.g;
prev.b += current.b;
return prev;
}, {
r: 0,
g: 0,
b: 0
})
return [{
r: Math.round(color.r / rgbVals.length),
g: Math.round(color.g / rgbVals.length),
b: Math.round(color.b / rgbVals.length)
}]
}
const colorChannelWithBiggestRange = this.colorChannelWithGreatestRange(rgbVals);
rgbVals.sort((prev, current) => {
return prev[colorChannelWithBiggestRange] - current[colorChannelWithBiggestRange]
});
const mid = rgbVals.length / 2;
return [
...this.quantize(rgbVals.slice(0, mid), initialDepth + 1, maxDepth),
...this.quantize(rgbVals.slice(mid), initialDepth + 1, maxDepth)
]
}
}
module.exports = Swatch
sunset.jpeg
when we run the above program using
node index.js sunset.jpeg
we would get a palette of 16 colours (since we had our max depth as 4, 2 ^ 4 is 16) which best represents the overall colours used in the image. we can increase the depth to get a palette with more colours.
I hope this would have been helpful for you to understand the median cut algorithm for colour quantization. I welcome you to drop a comment if you have any questions or suggestions. Thank you!!!