Map image colors using CSS and linear algebra

studen

21 Jun 2024

Perfect color matching
HSL
feColorMatrix
Enters linear algebra
Solving the matrix equation
Singular Value Decomposition
Nullspace of $A$
Solution to the matrix equation
Implementation
Conclusion

If you don't see this image it makes no sense — Original illustration from xkcd.

In a previous blog post I added an illustration from xkcd for a comedy touch. I love the style and simplicity of the xkcd illustrations but, without any manipulation, the images look alien in my blog. So, I added some CSS filters to the image and hand-tweaked it to try and match the background of the page's style. It was good enough to trick the unwitting eye, but then I wondered how to create a perfect match.

Perfect color matching

HSL

The CSS filter property has some functions to manipulate the colors of the image it is applied to. In particular, the three functions brightness, saturate, and hue-rotate can manipulate the three components of the HSV representation of the colors. So I thought about using them to transform the original HSV values into the target. However, the original color was white whose saturation value is 0, and the saturate function is a multiplier, so it's impossible to map it to any other color with saturation other than 0.

There is another function that can help with this: sepia. This function does a combination of transformations, and among those, it adds some offset to the saturation. With it, we could circumvent the problem of the 0 value in the saturation.

Another 0-value multiplicator problem arises with the brightness function when the original color is black. In that case, we can first use the invert function and then use the multipliers.

I tried to apply this to calculate the filter needed to map the background, but the match was not perfect. Reading through some StackOverflow answers I read that the hue-rotate function does not conserve the brightness and saturation values. I found it odd but did not delve into it because I had found a better approach.

feColorMatrix

There is another CSS filter function url that can use a reference to an SVG filter element. In particular, the feColorMatrix element is of interest:

The SVG filter element changes colors based on a transformation matrix. Every pixel's color value [R,G,B,A] is matrix multiplied by a 5 by 5 color matrix to create new color [R',G',B',A'].

$\begin{pmatrix} R' \\ G' \\ B' \\ A' \\ 1 \end{pmatrix} = \begin{pmatrix} r_1 & r_2 & r_3 & r_4 & r_5 \\ g_1 & g_2 & g_3 & g_4 & g_5 \\ b_1 & b_2 & b_3 & b_4 & b_5 \\ a_1 & a_2 & a_3 & a_4 & a_5 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} R \\ G \\ B \\ A \\ 1 \end{pmatrix}$

So, each channel of the new color will be

$\begin{align*} R' &= r_1 R + r_2 G + r_3 B + r_4 A + r_5 \\ G' &= g_1 R + g_2 G + g_3 B + g_4 A + g_5 \\ B' &= b_1 R + b_2 G + b_3 B + b_4 A + b_5 \\ A' &= a_1 R + a_2 G + a_3 B + a_4 A + a_5 \\ \end{align*}$

This presents us with a great opportunity. The matrix has 20 parameters and does a 4-to-4 mapping. So, with adequate values, we could map up to 5 colors, we only need to calculate those values.

Enters linear algebra

If we want to map the colors $(R_i, G_i, B_i, A_i) \to (R_i', G_i', B_i', A_i')$ for $i \in [1, 5]$ we would end up with a system of equations in the form:

$\begin{align*} R_1' &= r_1 R_1 + r_2 G_1 + r_3 B_1 + r_4 A_1 + r_5 \\ G_1' &= g_1 R_1 + g_2 G_1 + g_3 B_1 + g_4 A_1 + g_5 \\ B_1' &= b_1 R_1 + b_2 G_1 + b_3 B_1 + b_4 A_1 + b_5 \\ A_1' &= a_1 R_1 + a_2 G_1 + a_3 B_1 + a_4 A_1 + a_5 \\ \vdots \\ R_5' &= r_1 R_5 + r_2 G_5 + r_3 B_5 + r_4 A_5 + r_5 \\ G_5' &= g_1 R_5 + g_2 G_5 + g_3 B_5 + g_4 A_5 + g_5 \\ B_5' &= b_1 R_5 + b_2 G_5 + b_3 B_5 + b_4 A_5 + b_5 \\ A_5' &= a_1 R_5 + a_2 G_5 + a_3 B_5 + a_4 A_5 + a_5 \\ \end{align*}$

That we can express in matrix form like:

$\begin{pmatrix} \begin{matrix} R_1 & G_1 & B_1 & A_1 & 1 \\ R_1 & G_1 & B_1 & A_1 & 1 \\ R_1 & G_1 & B_1 & A_1 & 1 \\ R_1 & G_1 & B_1 & A_1 & 1 \\ \end{matrix} & 0 & 0\\ 0 & \ddots & 0\\ 0 & 0 & \begin{matrix} R_5 & G_5 & B_5 & A_5 & 1 \\ R_5 & G_5 & B_5 & A_5 & 1 \\ R_5 & G_5 & B_5 & A_5 & 1 \\ R_5 & G_5 & B_5 & A_5 & 1 \\ \end{matrix} \end{pmatrix} \begin{pmatrix} r_1 \\ \vdots \\ g_1 \\ \vdots \\ b_1 \\ \vdots \\ a_1 \\ \vdots \end{pmatrix} =\begin{pmatrix} R_1' \\ G_1' \\ B_1' \\ A_1' \\ \vdots \\ R_5' \\ G_5' \\ B_5' \\ A_5' \\ \end{pmatrix}$

Solving the matrix equation

The system of equations can be solved in many ways, for example using the simplest substitution algorithm, expressing some variables as a combination of others until the system is solved.

Another method could be Cramer's rule, but it only works for fully determined systems and we would like to be able to solve indeterminate systems (if we only want to map 4 colors or less, leaving some degrees of freedom to the answer).

I found a method to solve indeterminate systems of equations using the singular value decomposition of a matrix. From the form of the decomposition, it is transparent how to obtain all the solutions to the system of equations. Also, using this method is better compared to others regarding numerical stability.

Singular Value Decomposition

The singular value decomposition¹ of a matrix $A$ is

$A = U \Sigma V^T$

where $U$ and $V^T$ are orthogonal matrices and $\Sigma$ is a diagonal value. This decomposition can be obtained for rectangular matrices and its form has some interesting corollaries:

Nullspace of $A$

The nullspace or kernel, of a linear transformation $f$ , is the subspace in the domain that is mapped to the null vector in the image space by $f$ ; i.e.: the vectors $\vec{x}$ that fulfill $f(\vec{x}) = \vec{0}$ , or, in the case where $A$ represents the transformation: $A \vec{x} = \vec{0}$ .

From the form of the SVD, it follows that the columns of $U$ whose index correspond to the indexes of the diagonal matrix $\Sigma$ with a value of 0 form an orthogonal base for the nullspace of $A$ .

Solution to the matrix equation

Given the matrix equation $A \vec{x} = \vec{b}$ , we can solve for $\vec{x}$ using the pseudo-inverse of $A$ given by the SVD:

$\begin{align*} A \vec{x} &= \vec{b} \\ A^T A \vec{x} &= V \Sigma U^T \vec{b} \\ \Sigma^2 \vec{x} &= V \Sigma U^T \vec{b} \\ \vec{x} &= V \Sigma^{-1} U^T \vec{b} \end{align*}$

Where $\Sigma^{-1}_{ii} = 1 / \Sigma_{ii}$ if $\Sigma_{ii} \neq 0$ else 0 ². This formula gives us a solution to the equation (or the closest one if the system has no solution). The complete solution subspace is formed by the solution obtained by the previous formula and a linear combination of the vectors of the nullspace.

Implementation

With all this information, we can create a webapp to calculate the correct values of the matrix filter based on the color mapping we want to create.

Of course, I first searched for implementations in Rust of the SVD and found it in nalgebra. However, the implementation doesn't calculate the full matrix $U$ , so the nullspace cannot be calculated. I found the issue but after some chatting in nalgebra's discord server, and some fighting with the internal API of the library I gave up.

I then proceeded to look for an implementation in javascript and made a demo of the app live here whose code is on my Github.

In the demo, you can choose up to 4 colors to map. Mapping 5 is possible, but I found that with 5 it's too common that the mapping is impossible. We are solving a system of equations and it might not have solutions, for example, you can't map white to both black and red. But the restrictions are more complicated than that, it also cares about linear combinations of the selected colors.

On the other hand, leaving that one color unmapped leaves us with 4 degrees of freedom for the values of the filter matrix, which translates into the possibility of getting different colors for the colors we did not map. Any linear combination of the vectors of the nullspace satisfies the mapping we gave, but for the rest of the colors it might be different. That's why there is a random button (I initially thought about some sliders, but it's not clear what the limits should be (that issue is not solved by that random selection either)).

You can see the result in the first image of this article where I used a filter that maps the black-on-white theme of the original xkcd image to the theme of the blog.

Some more work can be done in the web app, off the top of my head:

Allow to use the image the user wants
Of course, improve the design

Conclusion

I don't know how useful other people will find this tool that I made, but for this blog, it will be plenty. I also refreshed my knowledge of linear algebra and learned a lot about SVD and other topics while researching this.

See a more detailed explanation of SVD theory and implementation in Numerical Recipes 3rd Edition, chapter 2.6.

See what we did? We just made $\infty = 0$ .