# Colourscheme Generation

I’ve always enjoyed having a wide range of desktop backgrounds to choose from, but now that I use a tiling window manager with transparency on non-focused windows, I see my background more than ever. It became clear that the colourscheme I was using (Solarized) wouldn’t match my all of my backgrounds (or many at all). I had to either live with it, or change my colourscheme every time I changed my backround. Naturally I chose the latter.

Unfortunately I don’t have an eye for colour and it would change what should be a single line in my terminal into a tedious process of picking out colours whenever I wanted to change backgrounds. So, I turned to automatically generated colourschemes; while I’m aware of existing scripts for this I wanted to make something that did exactly what I wanted, how I thought it should be done. (If you just want to see the end product, you can check out the script on GitHub.)

I first had to decide on the structure of my colourschemes. Taking after Solarized and Nord, I settled on three background colours, three foreground colours, and the rest (ten) as various accent colours. Going for a dark colourscheme, the following defines what a good colourscheme should fulfill:

- there should be significant separation of the three groups of colours
- the colours within each group should be sufficiently distinct from each other
- all colours should be recognizable as being derived from the background image
- the backgrounds should be the darkest, and the foreground should be the lightest

## Setup

This is clearly the job for a clustering algorithm. Since the number of colours for the colourscheme is fixed, k-means was an easy choice. Rather than performing the clustering on the RGB values in the images, I decided to first convert them to the CIELAB colour space. CIELAB is designed to be perceptually uniform; the distance between two colours in the space is roughly proportional to the visual difference between the colours when they are viewed. There is much to be written about the importance of perceptual uniformity in colour spaces and colour maps, but I will simply say that this is (in my opinion) one of the few logical choices of colour space here.

Another benefit of CIELAB is that one of the components (the ‘L’ in the acronym) is luminosity, which is perfect for separating the dark backgrounds from the lighter foregrounds and accents. The luminosity ranges from 0 to 100, with 0 being black and 100 being white. I chose fixed intervals of luminosity to define the colour groups, but this may fail or produce poor results if the range of luminosities in the image is too narrow.

After choosing how the colours will be represented and which clustering algorithm to use, the rest is fairly simple. I decided to write my own k-means implementation in numpy instead of using something premade (eg scikit-learn) in case I wanted to make tweaks to improve the results.

## Initial Results

I picked out a few pictures I had taken to test this first iteration of the colourscheme generator. You can see one example below, and the rest are here.

Base Image | Generated Colourscheme |
---|---|

The colours are laid out in order of increasing luminosity, with the three background colours at the top and the three foreground colours at the bottom. A couple of the tenents of a good colourscheme are satisfied here; the three groups of colours are all distinct from each other and correspond to the dominant colours of the image.

Where this method fails is the distinction between the colours. Especially in the accents, many of them feel ‘samey’. Even the highlights are just different shades of beige.

## First Solution Attempt: Repulsion

Since the only problem is that the colours aren’t spread out enough, the first thing I tried was artificially spreading them out by a repulsive force scaling with the inverse of the square of the distances between the centroids, like how like electric charges repel. This is applied after every k-means iteration, and its strength is controlled by a parameter \(k\):

\[\vec{d}_{ij} = \frac{k}{r_{ij}^2} \hat{r}_{ij}\]where \(d_ij\) is the change in position of the \(j\)-th centroid due to the force from the \(i\)-th centroid, \(r_{ij}\) is the distance between the two centroids, and \(\hat{r}_{ij}\) is the unit vector pointing from \(i\) to \(j\). The total displacement of the \(j\)-th centroid on each iteration is

\[\vec{d}_j = \sum_{i \neq j} \vec{d}_{ij}\]The result of this are shown below.

Base Image | $$k = 0$$ (No Repulsion) | $$k = 50$$ | $$k = 100$$ | $$k = 200$$ |
---|---|---|---|---|

This is not the same image as before, for reasons that will be explained later. There is definitely improvement in how distinct the colours are going from \(k = 0\) to \(k = 200\), especially noticeable in the foreground colours. The colours are also a little more vivid.

The reason the image for this example was different, and the main flaw with this approach, is that it does not converge for all values of \(k\). At \(k = 400\) the generation fails for the second image, and at even \(k = 50\) it fails for the first. This is because it’s possible for the repulsion stage to push one of the centroids far enough away from the image’s colours that it is no longer any point’s closest centroid. When the time comes for the centroids to be recalculated, it must average zero points to find the new location for this centroid. This results in a division by zero and the algorithm fails.

There are a few hacky solutions to this, but none of them are satisfying. Skip the next two paragraphs if you aren’t interested in hearing about the stuff that doesn’t work.

Firstly there is the option of ignoring the updating of the centroids if they do not have any points belonging to them. The centroid will then no longer be guaranteed to represent anything about the image’s colours. In fact, as the repulsion continues these orphaned centroids will be pushed farther away from the colours of the image and towards the edge of the Lab colour space - maybe even leaving it! The alternative is to remove these points from the repulsion step as well, which will only encourage other centroids to encroach upon the points of the colour space that it would otherwise have claim over, going back to the same issue of the centroids not being distinct enough.

Secondly, any time that a centroid has no points to average over in the update step, the previously done repulsion could be reversed and then performed again at half the value of \(k\). This would certainly always converge as \(k\) would eventually become infinitesimally small and the algorithm would approach the original k-means one if the repulsion repeatedly failed. However, in addition to ‘saturating’ the parameter \(k\) past a certain point (which would also be different for each image), this would cause irregular behaviour past that point. Suppose that on the first repulsion step, any value past \(k = 200\) would cause the algorithm to fail. If \(k=250\) was given, this step would fail and be redone at half that value. But this would give less repulsion than if a lower value of \(k=150\) was given!

The biggest takeaway I got from these thought experiments is that the algorithm should always be moving the centroids *towards* something. Additionally, the dimensionality of \(k\) manifested by the value at which the algorithm failed depending on the spread of the image’s colours. An image with a narrow range of colours such as the first one on this page couldn’t even run at \(k=50\) without failing, while the second image was able to be run at \(k=200\).

## Second Solution Attempt: Separation

The way forward is clearly to change how the means are recalculated based on the points belonging to them. Instead of becoming the centroid of the points, it should favour points that are farther from the other means, encouraging them to spread out. This can be done with a simple reweighting when averaging the points. Additionally, the new weights should be dimensionless so the updating does not depend on the scale of the data. So, how should a point’s weight during the centroid update be calculated?

An obvious starting point is the distance to the second closest cluster. This is a dimensional quantity, so it should be divided by another dimensional quantity. Without introducing anything new, the only relevant points in the colour space are the point we are calculating the weight of, the centroid that it belongs to, and the second closest centroid. The distance to the second closest centroid is already being used, and the distance from the point to the closest centroid can be arbitrarily close to zero which makes it a bad candidate. This leaves the distance between the closest and second closest centroid.

With this as the scale for the weight, the new centroid update rule becomes \(m_i = \frac{1}{\sum_{x_j \in X_i} (w_j)^s} \sum_{x_j \in X_i} x_j \cdot (w_j)^s\) \(w_j = \frac{r_{j,2}}{r_{j,12}}\) where \(r_{j,2}\) is the distance from \(x_j\) to the second closest centroid, and \(r_{j,12}\) is the distance between the two closest centroids to \(x_j\). The quantity \(s\) is the ‘separation parameter’ determining how strongly the weights affect the updating.

Base Image | $$s = 0$$ (All weights are 1) | $$s = 1$$ | $$s = 2$$ | $$s = 10$$ |
---|---|---|---|---|

As the separation parameter increases, the colours become much more vibrant and distinct. And there’s no risk of the algorithm failing! In fact, this modified algorithm has some neat limiting cases:

- when \(s=0\), it behaves as the normal k-means algorithm
- when \(s \to \infty\), it moves each centroid to the point in the cluster that is farthest from the second closest centroid
- as the clusters become infinitely separated relative to their size, it behaves as the normal k-means algorithm (once each centroid is within its respective cluster)

So far, I have not found anything unsatisfactory with this iteration of the algorithm and it continues to be what I use. With another python script to propagate the colourscheme to my config files and a shell script to tie it all together, my wallpaper changing is back down to one line (with better colourschemes than I could hope to make myself to boot).