@Dave was the first to post an answer to this (with working code), and his answer has been an invaluable source of shameless copy and pasting inspiration to me. This post began as an attempt to explain and refine @Dave's
answer, but it has since evolved into an answer of its own.
My method is significantly faster. According to a jsPerf benchmark on randomly generated RGB colors, @Dave's algorithm runs in 600 ms, while mine runs in 30 ms. This can definitely matter, for instance in load time, where speed is critical.
Furthermore, for some colors, my algorithm performs better:
- For
rgb(0,255,0), @Dave's produces rgb(29,218,34) and mine produces rgb(1,255,0)
- For
rgb(0,0,255), @Dave's produces rgb(37,39,255) and mine produces rgb(5,6,255)
- For
rgb(19,11,118), @Dave's produces rgb(36,27,102) and mine produces rgb(20,11,112)
Demo
"use strict";
class Color {
constructor(r, g, b) { this.set(r, g, b); }
toString() { return `rgb(${Math.round(this.r)}, ${Math.round(this.g)}, ${Math.round(this.b)})`; }
set(r, g, b) {
this.r = this.clamp(r);
this.g = this.clamp(g);
this.b = this.clamp(b);
}
hueRotate(angle = 0) {
angle = angle / 180 * Math.PI;
let sin = Math.sin(angle);
let cos = Math.cos(angle);
this.multiply([
0.213 + cos * 0.787 - sin * 0.213, 0.715 - cos * 0.715 - sin * 0.715, 0.072 - cos * 0.072 + sin * 0.928,
0.213 - cos * 0.213 + sin * 0.143, 0.715 + cos * 0.285 + sin * 0.140, 0.072 - cos * 0.072 - sin * 0.283,
0.213 - cos * 0.213 - sin * 0.787, 0.715 - cos * 0.715 + sin * 0.715, 0.072 + cos * 0.928 + sin * 0.072
]);
}
grayscale(value = 1) {
this.multiply([
0.2126 + 0.7874 * (1 - value), 0.7152 - 0.7152 * (1 - value), 0.0722 - 0.0722 * (1 - value),
0.2126 - 0.2126 * (1 - value), 0.7152 + 0.2848 * (1 - value), 0.0722 - 0.0722 * (1 - value),
0.2126 - 0.2126 * (1 - value), 0.7152 - 0.7152 * (1 - value), 0.0722 + 0.9278 * (1 - value)
]);
}
sepia(value = 1) {
this.multiply([
0.393 + 0.607 * (1 - value), 0.769 - 0.769 * (1 - value), 0.189 - 0.189 * (1 - value),
0.349 - 0.349 * (1 - value), 0.686 + 0.314 * (1 - value), 0.168 - 0.168 * (1 - value),
0.272 - 0.272 * (1 - value), 0.534 - 0.534 * (1 - value), 0.131 + 0.869 * (1 - value)
]);
}
saturate(value = 1) {
this.multiply([
0.213 + 0.787 * value, 0.715 - 0.715 * value, 0.072 - 0.072 * value,
0.213 - 0.213 * value, 0.715 + 0.285 * value, 0.072 - 0.072 * value,
0.213 - 0.213 * value, 0.715 - 0.715 * value, 0.072 + 0.928 * value
]);
}
multiply(matrix) {
let newR = this.clamp(this.r * matrix[0] + this.g * matrix[1] + this.b * matrix[2]);
let newG = this.clamp(this.r * matrix[3] + this.g * matrix[4] + this.b * matrix[5]);
let newB = this.clamp(this.r * matrix[6] + this.g * matrix[7] + this.b * matrix[8]);
this.r = newR; this.g = newG; this.b = newB;
}
brightness(value = 1) { this.linear(value); }
contrast(value = 1) { this.linear(value, -(0.5 * value) + 0.5); }
linear(slope = 1, intercept = 0) {
this.r = this.clamp(this.r * slope + intercept * 255);
this.g = this.clamp(this.g * slope + intercept * 255);
this.b = this.clamp(this.b * slope + intercept * 255);
}
invert(value = 1) {
this.r = this.clamp((value + (this.r / 255) * (1 - 2 * value)) * 255);
this.g = this.clamp((value + (this.g / 255) * (1 - 2 * value)) * 255);
this.b = this.clamp((value + (this.b / 255) * (1 - 2 * value)) * 255);
}
hsl() { // Code taken from https://stackoverflow.com/a/9493060/2688027, licensed under CC BY-SA.
let r = this.r / 255;
let g = this.g / 255;
let b = this.b / 255;
let max = Math.max(r, g, b);
let min = Math.min(r, g, b);
let h, s, l = (max + min) / 2;
if(max === min) {
h = s = 0;
} else {
let d = max - min;
s = l > 0.5 ? d / (2 - max - min) : d / (max + min);
switch(max) {
case r: h = (g - b) / d + (g < b ? 6 : 0); break;
case g: h = (b - r) / d + 2; break;
case b: h = (r - g) / d + 4; break;
} h /= 6;
}
return {
h: h * 100,
s: s * 100,
l: l * 100
};
}
clamp(value) {
if(value > 255) { value = 255; }
else if(value < 0) { value = 0; }
return value;
}
}
class Solver {
constructor(target) {
this.target = target;
this.targetHSL = target.hsl();
this.reusedColor = new Color(0, 0, 0); // Object pool
}
solve() {
let result = this.solveNarrow(this.solveWide());
return {
values: result.values,
loss: result.loss,
filter: this.css(result.values)
};
}
solveWide() {
const A = 5;
const c = 15;
const a = [60, 180, 18000, 600, 1.2, 1.2];
let best = { loss: Infinity };
for(let i = 0; best.loss > 25 && i < 3; i++) {
let initial = [50, 20, 3750, 50, 100, 100];
let result = this.spsa(A, a, c, initial, 1000);
if(result.loss < best.loss) { best = result; }
} return best;
}
solveNarrow(wide) {
const A = wide.loss;
const c = 2;
const A1 = A + 1;
const a = [0.25 * A1, 0.25 * A1, A1, 0.25 * A1, 0.2 * A1, 0.2 * A1];
return this.spsa(A, a, c, wide.values, 500);
}
spsa(A, a, c, values, iters) {
const alpha = 1;
const gamma = 0.16666666666666666;
let best = null;
let bestLoss = Infinity;
let deltas = new Array(6);
let highArgs = new Array(6);
let lowArgs = new Array(6);
for(let k = 0; k < iters; k++) {
let ck = c / Math.pow(k + 1, gamma);
for(let i = 0; i < 6; i++) {
deltas[i] = Math.random() > 0.5 ? 1 : -1;
highArgs[i] = values[i] + ck * deltas[i];
lowArgs[i] = values[i] - ck * deltas[i];
}
let lossDiff = this.loss(highArgs) - this.loss(lowArgs);
for(let i = 0; i < 6; i++) {
let g = lossDiff / (2 * ck) * deltas[i];
let ak = a[i] / Math.pow(A + k + 1, alpha);
values[i] = fix(values[i] - ak * g, i);
}
let loss = this.loss(values);
if(loss < bestLoss) { best = values.slice(0); bestLoss = loss; }
} return { values: best, loss: bestLoss };
function fix(value, idx) {
let max = 100;
if(idx === 2 /* saturate */) { max = 7500; }
else if(idx === 4 /* brightness */ || idx === 5 /* contrast */) { max = 200; }
if(idx === 3 /* hue-rotate */) {
if(value > max) { value = value % max; }
else if(value < 0) { value = max + value % max; }
} else if(value < 0) { value = 0; }
else if(value > max) { value = max; }
return value;
}
}
loss(filters) { // Argument is array of percentages.
let color = this.reusedColor;
color.set(0, 0, 0);
color.invert(filters[0] / 100);
color.sepia(filters[1] / 100);
color.saturate(filters[2] / 100);
color.hueRotate(filters[3] * 3.6);
color.brightness(filters[4] / 100);
color.contrast(filters[5] / 100);
let colorHSL = color.hsl();
return Math.abs(color.r - this.target.r)
+ Math.abs(color.g - this.target.g)
+ Math.abs(color.b - this.target.b)
+ Math.abs(colorHSL.h - this.targetHSL.h)
+ Math.abs(colorHSL.s - this.targetHSL.s)
+ Math.abs(colorHSL.l - this.targetHSL.l);
}
css(filters) {
function fmt(idx, multiplier = 1) { return Math.round(filters[idx] * multiplier); }
return `filter: invert(${fmt(0)}%) sepia(${fmt(1)}%) saturate(${fmt(2)}%) hue-rotate(${fmt(3, 3.6)}deg) brightness(${fmt(4)}%) contrast(${fmt(5)}%);`;
}
}
$("button.execute").click(() => {
let rgb = $("input.target").val().split(",");
if (rgb.length !== 3) { alert("Invalid format!"); return; }
let color = new Color(rgb[0], rgb[1], rgb[2]);
let solver = new Solver(color);
let result = solver.solve();
let lossMsg;
if (result.loss < 1) {
lossMsg = "This is a perfect result.";
} else if (result.loss < 5) {
lossMsg = "The is close enough.";
} else if(result.loss < 15) {
lossMsg = "The color is somewhat off. Consider running it again.";
} else {
lossMsg = "The color is extremely off. Run it again!";
}
$(".realPixel").css("background-color", color.toString());
$(".filterPixel").attr("style", result.filter);
$(".filterDetail").text(result.filter);
$(".lossDetail").html(`Loss: ${result.loss.toFixed(1)}. <b>${lossMsg}</b>`);
});
.pixel {
display: inline-block;
background-color: #000;
width: 50px;
height: 50px;
}
.filterDetail {
font-family: "Consolas", "Menlo", "Ubuntu Mono", monospace;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<input class="target" type="text" placeholder="r, g, b" value="250, 150, 50" />
<button class="execute">Compute Filters</button>
<p>Real pixel, color applied through CSS <code>background-color</code>:</p>
<div class="pixel realPixel"></div>
<p>Filtered pixel, color applied through CSS <code>filter</code>:</p>
<div class="pixel filterPixel"></div>
<p class="filterDetail"></p>
<p class="lossDetail"></p>
Usage
let color = new Color(0, 255, 0);
let solver = new Solver(color);
let result = solver.solve();
let filterCSS = result.filter;
Explanation
We'll begin with some Javascript.
"use strict";
class Color {
constructor(r, g, b) {
this.r = this.clamp(r);
this.g = this.clamp(g);
this.b = this.clamp(b);
} toString() { return `rgb(${Math.round(this.r)}, ${Math.round(this.g)}, ${Math.round(this.b)})`; }
hsl() { // Code taken from https://stackoverflow.com/a/9493060/2688027, licensed under CC BY-SA.
let r = this.r / 255;
let g = this.g / 255;
let b = this.b / 255;
let max = Math.max(r, g, b);
let min = Math.min(r, g, b);
let h, s, l = (max + min) / 2;
if(max === min) {
h = s = 0;
} else {
let d = max - min;
s = l > 0.5 ? d / (2 - max - min) : d / (max + min);
switch(max) {
case r: h = (g - b) / d + (g < b ? 6 : 0); break;
case g: h = (b - r) / d + 2; break;
case b: h = (r - g) / d + 4; break;
} h /= 6;
}
return {
h: h * 100,
s: s * 100,
l: l * 100
};
}
clamp(value) {
if(value > 255) { value = 255; }
else if(value < 0) { value = 0; }
return value;
}
}
class Solver {
constructor(target) {
this.target = target;
this.targetHSL = target.hsl();
}
css(filters) {
function fmt(idx, multiplier = 1) { return Math.round(filters[idx] * multiplier); }
return `filter: invert(${fmt(0)}%) sepia(${fmt(1)}%) saturate(${fmt(2)}%) hue-rotate(${fmt(3, 3.6)}deg) brightness(${fmt(4)}%) contrast(${fmt(5)}%);`;
}
}
Explanation:
- The
Color class represents a RGB color.
- Its
toString() function returns the color in a CSS rgb(...) color string.
- Its
hsl() function returns the color, converted to HSL.
- Its
clamp() function ensures that a given color value is within bounds (0-255).
- The
Solver class will attempt to solve for a target color.
- Its
css() function returns a given filter in a CSS filter string.
Implementing grayscale(), sepia(), and saturate()
The heart of CSS/SVG filters are filter primitives, which represent low-level modifications to an image.
The filters grayscale(), sepia(), and saturate() are implemented by the filter primative <feColorMatrix>, which performs matrix multiplication between a matrix specified by the filter (often dynamically generated), and a matrix created from the color. Diagram:
There are some optimizations we can make here:
- The last element of the color matrix is and will always be
1. There is no point of calculating or storing it.
- There is no point of calculating or storing the alpha/transparency value (
A) either, since we are dealing with RGB, not RGBA.
- Therefore, we can trim the filter matrices from 5x5 to 3x5, and the color matrix from 1x5 to 1x3. This saves a bit of work.
- All
<feColorMatrix> filters leave columns 4 and 5 as zeroes. Therefore, we can further reduce the filter matrix to 3x3.
- Since the multiplication is relatively simple, there is no need to drag in complex math libraries for this. We can implement the matrix multiplication algorithm ourselves.
Implementation:
function multiply(matrix) {
let newR = this.clamp(this.r * matrix[0] + this.g * matrix[1] + this.b * matrix[2]);
let newG = this.clamp(this.r * matrix[3] + this.g * matrix[4] + this.b * matrix[5]);
let newB = this.clamp(this.r * matrix[6] + this.g * matrix[7] + this.b * matrix[8]);
this.r = newR; this.g = newG; this.b = newB;
}
(We use temporary variables to hold the results of each row multiplication, because we do not want changes to this.r, etc. affecting subsequent calculations.)
Now that we have implemented <feColorMatrix>, we can implement grayscale(), sepia(), and saturate(), which simply invoke it with a given filter matrix:
function grayscale(value = 1) {
this.multiply([
0.2126 + 0.7874 * (1 - value), 0.7152 - 0.7152 * (1 - value), 0.0722 - 0.0722 * (1 - value),
0.2126 - 0.2126 * (1 - value), 0.7152 + 0.2848 * (1 - value), 0.0722 - 0.0722 * (1 - value),
0.2126 - 0.2126 * (1 - value), 0.7152 - 0.7152 * (1 - value), 0.0722 + 0.9278 * (1 - value)
]);
}
function sepia(value = 1) {
this.multiply([
0.393 + 0.607 * (1 - value), 0.769 - 0.769 * (1 - value), 0.189 - 0.189 * (1 - value),
0.349 - 0.349 * (1 - value), 0.686 + 0.314 * (1 - value), 0.168 - 0.168 * (1 - value),
0.272 - 0.272 * (1 - value), 0.534 - 0.534 * (1 - value), 0.131 + 0.869 * (1 - value)
]);
}
function saturate(value = 1) {
this.multiply([
0.213 + 0.787 * value, 0.715 - 0.715 * value, 0.072 - 0.072 * value,
0.213 - 0.213 * value, 0.715 + 0.285 * value, 0.072 - 0.072 * value,
0.213 - 0.213 * value, 0.715 - 0.715 * value, 0.072 + 0.928 * value
]);
}
Implementing hue-rotate()
The hue-rotate() filter is implemented by <feColorMatrix type="hueRotate" />.
The filter matrix is calculated as shown below:
For instance, element a00 would be calculated like so:
Notes:
- The angle of rotation is given in degrees, which must be converted to radians before passed to
Math.sin() or Math.cos().
Math.sin(angle) and Math.cos(angle) should be computed once and then cached.
Implementation:
function hueRotate(angle = 0) {
angle = angle / 180 * Math.PI;
let sin = Math.sin(angle);
let cos = Math.cos(angle);
this.multiply([
0.213 + cos * 0.787 - sin * 0.213, 0.715 - cos * 0.715 - sin * 0.715, 0.072 - cos * 0.072 + sin * 0.928,
0.213 - cos * 0.213 + sin * 0.143, 0.715 + cos * 0.285 + sin * 0.140, 0.072 - cos * 0.072 - sin * 0.283,
0.213 - cos * 0.213 - sin * 0.787, 0.715 - cos * 0.715 + sin * 0.715, 0.072 + cos * 0.928 + sin * 0.072
]);
}
Implementing brightness() and contrast()
The brightness() and contrast() filters are implemented by <feComponentTransfer> with <feFuncX type="linear" />.
Each <feFuncX type="linear" /> element accepts a slope and intercept attribute. It then calculates each new color value through a simple formula:
value = slope * value + intercept
This is easy to implement:
function linear(slope = 1, intercept = 0) {
this.r = this.clamp(this.r * slope + intercept * 255);
this.g = this.clamp(this.g * slope + intercept * 255);
this.b = this.clamp(this.b * slope + intercept * 255);
}
Once this is implemented, brightness() and contrast() can be implemented as well:
function brightness(value = 1) { this.linear(value); }
function contrast(value = 1) { this.linear(value, -(0.5 * value) + 0.5); }
Implementing invert()
The invert() filter is implemented by <feComponentTransfer> with <feFuncX type="table" />.
The spec states:
In the following, C is the initial component and C' is the remapped component; both in the closed interval [0,1].
For "table", the function is defined by linear interpolation between values given in the attribute tableValues. The table has n + 1 values (i.e., v0 to vn) specifying the start and end values for n evenly sized interpolation regions. Interpolations use the following formula:
For a value C find k such that:
k / n ≤ C < (k + 1) / n
The result C' is given by:
C' = vk + (C - k / n) * n * (vk+1 - vk)
An explanation of this formula:
- The
invert() filter defines this table: [value, 1 - value]. This is tableValues or v.
- The formula defines n, such that n + 1 is the table's length. Since the table's length is 2, n = 1.
- The formula defines k, with k and k + 1 being indexes of the table. Since the table has 2 elements, k = 0.
Thus, we can simplify the formula to:
C' = v0 + C * (v1 - v0)
Inlining the table's values, we are left with:
C' = value + C * (1 - value - value)
One more simplification:
C' = value + C * (1 - 2 * value)
The spec defines C and C' to be RGB values, within the bounds 0-1 (as opposed to 0-255). As a result, we must scale down the values before computation, and scale them back up after.
Thus we arrive at our implementation:
function invert(value = 1) {
this.r = this.clamp((value + (this.r / 255) * (1 - 2 * value)) * 255);
this.g = this.clamp((value + (this.g / 255) * (1 - 2 * value)) * 255);
this.b = this.clamp((value + (this.b / 255) * (1 - 2 * value)) * 255);
}
Interlude: @Dave's brute-force algorithm
@Dave's code generates 176,660 filter combinations, including:
- 11
invert() filters (0%, 10%, 20%, ..., 100%)
- 11
sepia() filters (0%, 10%, 20%, ..., 100%)
- 20
saturate() filters (5%, 10%, 15%, ..., 100%)
- 73
hue-rotate() filters (0deg, 5deg, 10deg, ..., 360deg)
It calculates filters in the following order:
filter: invert(a%) sepia(b%) saturate(c%) hue-rotate(θdeg);
It then iterates through all computed colors. It stops once it has found a generated color within tolerance (all RGB values are within 5 units from the target color).
However, this is slow and inefficient. Thus, I present my own answer.
Implementing SPSA
First, we must define a loss function, that returns the difference between the color produced by a filter combination, and the target color. If the filters are perfect, the loss function should return 0.
We will measure color difference as the sum of two metrics:
- RGB difference, because the goal is to produce the closest RGB value.
- HSL difference, because many HSL values correspond to filters (e.g. hue roughly correlates with
hue-rotate(), saturation correlates with saturate(), etc.) This guides the algorithm.
The loss function will take one argument – an array of filter percentages.
We will use the following filter order:
filter: invert(a%) sepia(b%) saturate(c%) hue-rotate(θdeg) brightness(e%) contrast(f%);
Implementation:
function loss(filters) {
let color = new Color(0, 0, 0);
color.invert(filters[0] / 100);
color.sepia(filters[1] / 100);
color.saturate(filters[2] / 100);
color.hueRotate(filters[3] * 3.6);
color.brightness(filters[4] / 100);
color.contrast(filters[5] / 100);
let colorHSL = color.hsl();
return Math.abs(color.r - this.target.r)
+ Math.abs(color.g - this.target.g)
+ Math.abs(color.b - this.target.b)
+ Math.abs(colorHSL.h - this.targetHSL.h)
+ Math.abs(colorHSL.s - this.targetHSL.s)
+ Math.abs(colorHSL.l - this.targetHSL.l);
}
We will try to minimize the loss function, such that:
loss([a, b, c, d, e, f]) = 0
The SPSA algorithm (website, more info, paper, implementation paper, reference code) is very good at this. It was designed to optimize complex systems with local minima, noisy/nonlinear/ multivariate loss functions, etc. It has been used to tune chess engines. And unlike many other algorithms, the papers describing it are actually comprehensible (albeit with great effort).
Implementation:
function spsa(A, a, c, values, iters) {
const alpha = 1;
const gamma = 0.16666666666666666;
let best = null;
let bestLoss = Infinity;
let deltas = new Array(6);
let highArgs = new Array(6);
let lowArgs = new Array(6);
for(let k = 0; k < iters; k++) {
let ck = c / Math.pow(k + 1, gamma);
for(let i = 0; i < 6; i++) {
deltas[i] = Math.random() > 0.5 ? 1 : -1;
highArgs[i] = values[i] + ck * deltas[i];
lowArgs[i] = values[i] - ck * deltas[i];
}
let lossDiff = this.loss(highArgs) - this.loss(lowArgs);
for(let i = 0; i < 6; i++) {
let g = lossDiff / (2 * ck) * deltas[i];
let ak = a[i] / Math.pow(A + k + 1, alpha);
values[i] = fix(values[i] - ak * g, i);
}
let loss = this.loss(values);
if(loss < bestLoss) { best = values.slice(0); bestLoss = loss; }
} return { values: best, loss: bestLoss };
function fix(value, idx) {
let max = 100;
if(idx === 2 /* saturate */) { max = 7500; }
else if(idx === 4 /* brightness */ || idx === 5 /* contrast */) { max = 200; }
if(idx === 3 /* hue-rotate */) {
if(value > max) { value = value % max; }
else if(value < 0) { value = max + value % max; }
} else if(value < 0) { value = 0; }
else if(value > max) { value = max; }
return value;
}
}
I made some modifications/optimizations to SPSA:
- Using the best result produced, instead of the last.
- Reusing all arrays (
deltas, highArgs, lowArgs), instead of recreating them with each iteration.
- Using an array of values for a, instead of a single value. This is because all of the filters are different, and thus they should move/converge at different speeds.
- Running a
fix function after each iteration. It clamps all values to between 0% and 100%, except saturate (where the maximum is 7500%), brightness and contrast (where the maximum is 200%), and hueRotate (where the values are wrapped around instead of clamped).
I use SPSA in a two-stage process:
- The "wide" stage, that tries to "explore" the search space. It will make limited retries of SPSA if the results are not satisfactory.
- The "narrow" stage, that takes the best result from the wide stage and attempts to "refine" it. It uses dynamic values for A and a.
Implementation:
function solve() {
let result = this.solveNarrow(this.solveWide());
return {
values: result.values,
loss: result.loss,
filter: this.css(result.values)
};
}
function solveWide() {
const A = 5;
const c = 15;
const a = [60, 180, 18000, 600, 1.2, 1.2];
let best = { loss: Infinity };
for(let i = 0; best.loss > 25 && i < 3; i++) {
let initial = [50, 20, 3750, 50, 100, 100];
let result = this.spsa(A, a, c, initial, 1000);
if(result.loss < best.loss) { best = result; }
} return best;
}
function solveNarrow(wide) {
const A = wide.loss;
const c = 2;
const A1 = A + 1;
const a = [0.25 * A1, 0.25 * A1, A1, 0.25 * A1, 0.2 * A1, 0.2 * A1];
return this.spsa(A, a, c, wide.values, 500);
}
Tuning SPSA
Warning: Do not mess with the SPSA code, especially with its constants, unless you are sure you know what you are doing.
The important constants are A, a, c, the initial values, the retry thresholds, the values of max in fix(), and the number of iterations of each stage. All of these values were carefully tuned to produce good results, and randomly screwing with them will almost definitely reduce the usefulness of the algorithm.
If you insist on altering it, you must measure before you "optimize".
First, apply this patch.
Then run the code in Node.js. After quite some time, the result should be something like this:
Average loss: 3.4768521401985275
Average time: 11.4915ms
Now tune the constants to your heart's content.
Some tips:
- The average loss should be around 4. If it is greater than 4, it is producing results that are too far off, and you should tune for accuracy. If it is less than 4, it is wasting time, and you should reduce the number of iterations.
- If you increase/decrease the number of iterations, adjust A appropriately.
- If you increase/decrease A, adjust a appropriately.
- Use the
--debug flag if you want to see the result of each iteration.
TL;DR
