Recently at Redbubble we have encountered a very interesting colour matching problem:

Given a “target” colour and a set of colours, we have to determine which colour in the set is the closest one to the target colour.

In order to understand why such a solution is needed, let’s analyse a scenario that actually happens on the website:

- An artist creates a work which he wants to sell on a t-shirt, and chooses the colour white as the default background for his work.
- A user browsing the website sees this work and wants to buy it as a hoodie, so the user chooses ‘Hoodie’ as the clothing style in the work page.
- Unfortunately we cannot print white hoodies, so we display the work on a black hoodie, which is the first background colour available for hoodies.

We would like instead to set the colour of the hoodie to the one that is the nearest to white, amongst those that are available for hoodies.

The simplest way of solving this problem would be to create a static mapping from all colours to all colours, representing what we think are the best matches. Since colour proximity is a subjective thing, any algorithmic approach runs the risk of providing results that differ from what the majority of humans would expect. Therefore, by doing a manual mapping, we would eliminate that risk. The problem with this approach though is that we would have to update this mapping manually every time a new colour became available, or an existing colour became unavailable on the website.

**First attempt – dumb hexadecimal comparison**

We started then to look for alternative solutions. Our very first idea was to map each colour to their hexadecimal value and choose the colour in the set that had the closest hexadecimal value to that of the target colour. This method produced wrong results from the start, mapping for instance the colour turquoise (hexadecimal value 0xA5Efff) to red (hexadecimal value 0xA50120), when we expected something like light blue to be chosen. This taught us that the proximity of the colours’ hexadecimal values said nothing about how close the colours were to one another visually.

**Second attempt – three-dimensional RGB space**

After this, we began to think about situations in which we normally calculate distances. Usually, we calculate distances between points in a cartesian system. Thus, if we could somehow represent colours as points in a cartesian system, we would be able to calculate the distance between them by using simple euclidean distance. An easy way to do this is by using the colour’s RGB values as coordinates in a 3D space.

This method produced results that were still off the mark, but already a little better than the first method. The colour turquoise (rgb value [165, 239, 255]) was now being mapped to silver (rgb value [224, 225, 221], euclidean distance 69.51), with light blue (rgb value [141, 179, 210], euclidean distance 78.74) ranking in the second place. This and other results were not what people would expect were the closest colours, and showed that proximity in the three-dimensional RGB space is not a perfect indication of colours being near one another from a human’s perspective.

**Third attempt – the HSL model**

We felt we were getting closer to the right solution, but we didn’t know how we could tweak this method in order for it to produce the right results. So, we decided we needed the help of a domain expert. We remembered we have an engineer on the team, Amanda Koh, who has a passion for computer graphics and photography who had recently given a talk about digital colours, so we asked for her opinion. She suggested we use the HSL colour space, a cylindrical coordinate system that arranges colours in a more intuitive geometry. In other words, the HSL model groups colours together in a way that makes more sense from the perspective of the human eye:

In the HSL model a colour has three properties: hue, saturation, and luminance. Hue corresponds to the angle around the central vertical axis of the cylinder, saturation is the distance from the central vertical axis of the cylinder, and luminance is the distance along the central vertical axis of the cylinder. In order to convert a colour from the RGB space to the HSL space we can use formulas like these.

Once we have translated all the colours into HSL coordinates, we still have to calculate the distance between them. We cannot use the euclidean distance formula as we did before with the RGB coordinates because euclidean distance can only be used to calculate the distance between two points in cartesian coordinates. A coordinate in the cartesian system is a measure of how far along an axis a point is, but as we have seen above, one of the coordinates in the HSL model, hue, is actually an angle around the vertical axis of the HSL space. Therefore, the euclidean distance formula cannot be used in this case.

In order to solve this problem we need to convert the HSL coordinates into cartesian coordinates, and then calculate the euclidean distance. This conversion became much easier after we realised that the coordinates of a point in any hue-saturation cross-section of the HSL cylinder were actually coordinates in the polar coordinate system, where hue is the angular coordinate and saturation is the radial coordinate:

(remembering that the hue angle has to be converted from degrees to radians).

The conversion from polar coordinates to cartesian coordinates in 2D is done as follows:

`x = r * cos(θ) = saturation * cos(hue)`

y = r * sin(θ) = saturation * sin(hue)

Since luminance is the distance to the origin along the vertical axis, we will take z = luminance as is.

After converting the colour from the HSL space to the cartesian coordinate system and calculating the euclidean distance between the colours, we started to see better results. The colour turquoise, for instance, was finally being mapped to light blue, but it would be mapped to grey if we removed light blue from the available colours, even if royal blue (a darker shade of blue) was present in the set. This didn’t make much sense for us, as we expected a blue color to be chosen instead of a grey one. Many other similar cases like this were being observed as well.

**Fourth attempt – weighted euclidean distance**

We showed those results to our colour expert and she gave us another valuable piece of information: when the human eye judges the proximity of colours, hue is more important than saturation, and much more important then luminance. In other words, two colours that have similar hue values will be deemed closer to one another than two colours that have similar saturation values, and even more so than two colours that have similar luminance values.

With this in mind we decided to add weights to our distance calculation, in such a way that the distance between two colours would vary greatly even if their hue values differed by a small amount, but would not vary that much even if their saturation or hue values differed greatly. After some experimentation, we set these weights as 0.5 for hue, 0.3 for saturation and 0.2 for luminance.

After this change all colours were being mapped to those that most humans in the office expected, except for a special case: greyscale colours. For example, the colour white (#FFFFFF) was being mapped to grey (#b6b6b6), instead of to oatmeal (#f4f0e1), the colour most humans in the office expected it to be mapped to. The reason for this is that these colours have a very similar low hue value (close to 0), and varying levels of luminance. But since luminance was given a very low weight value, it became hard to differentiate between those colours when choosing the closest one to the target colour.

**Fifth attempt – adaptive weighting of distance coordinates**

The solution we found for this is to first detect if the target colour is a greyscale colour. Greyscale colours can be detected by having low saturation values, so we set a low saturation threshold of 0.2. Any colour falling below this threshold is considered to be a greyscale colour. When this is the case, we simply change the weights used in the distance calculation, prioritising luminance and saturation in detriment of hue. After some experimentation we set these weights as 0.2 for hue, 0.3 for saturation and 0.5 for luminance.

**Results**

The following work, “On Top Of Mountains”, by cabinsupplyco looks awesome on a white t-shirt:

But it was shown on a black hoodie when users chose the hoodie product on the dropdown to the right, due to the unavailability of the color white for hoodies:

Now that our color matching algorithm has been implemented, a color that is closer to white is chosen, and the work looks like this on a hoodie:

This feature will also be useful for other parts of the website, like when sending products to external shopping feeds such as Google and Facebook, making sure we always choose the best colours to display our artists’ works in.