Find the closest named color

Question

I have a .json file with name (string) and RGB (r, g, b: numbers) with 30.000 key-value pairs. I am looping the json multiple times per second to find the closest name to a given RGB color. Any idea how I can optimize the code or the json data to make it faster? Currently it works fine for the few calls per seconds, but after 30-50 calls per seconds there is noticeable lag.

[
 { "name": "Aare River", "rgb": { "r": 0, "g": 184, "b": 159 } },
 { "name": "Aare River Brienz", "rgb": { "r": 5, "g": 163, "b": 173 } },
 { "name": "Aarhusian Sky", "rgb": { "r": 17, "g": 80, "b": 175 } },
 { "name": "Abaddon Black", "rgb": { "r": 35, "g": 31, "b": 32 } },
]

fetch("/data/colorsNames.json")
  .then((res) => res.json())
  .then((data) => {
    colorsNames = data;
  });

function setColorName(color: string): void {
  let closestColor = findClosestColorName(hexToRgb(color, false) as ColorRGB);
  colorNameText.textContent = colorsNames[closestColor[0]].name;
}


function findClosestColorName(
  color: ColorRGB
): [index: number, distance: number] {
  let closestIndex = -1;
  let closestDistance = Number.MAX_VALUE;
  let distance = Number.MAX_VALUE;

  for (let i = 0; i < colorsNames.length; i++) {
    distance = getColorsDistance(color, colorsNames[i].rgb);

    if (distance < closestDistance) {
      closestIndex = i;
      closestDistance = distance;
    }

    if (closestDistance === 0) return [closestIndex, closestDistance];
  }

  return [closestIndex, closestDistance];

  function getColorsDistance(color: ColorRGB, match: ColorRGB): number {
    return (
      Math.abs(color.r - match.r) +
      Math.abs(color.g - match.g) +
      Math.abs(color.b - match.b)
    );
  }
}

Answer 1

Incorrect calculation of color distance

sRGB is a logarithmic scale

RGB (AKA sRGB) as used by the browser is a logarithmic scale (apart from the very darker values which are linear)

Your calculation of color distance does not take this into account and results in a bias towards darker colors.

A quick and good approximation for color values is to raise each channels' value to 2.2 and then calculate the distance.

Use pythagoras for distance

The distance between colors is not the sum of the differences between channels, it is the square root of the sum of the square differences (ie pythagoras).

Thus and example of calculating the color distance.

Example

  function getColorsDistance(color: ColorRGB, match: ColorRGB): number {
    var r = (color.r ** 2.2) - (match.r ** 2.2);
    var g = (color.g ** 2.2) - (match.g ** 2.2);
    var b = (color.b ** 2.2) - (match.b ** 2.2);
    return ((r * r + g * g + b * b) ** 0.5) ** (1 / 2.2);
  }

As you are interested in the relative distance (not the sRGB distance) one can skip the square root and the conversion to linear to get

  function getColorsNearness(color: ColorRGB, match: ColorRGB): number {
    var r = (color.r ** 2.2) - (match.r ** 2.2);
    var g = (color.g ** 2.2) - (match.g ** 2.2);
    var b = (color.b ** 2.2) - (match.b ** 2.2);
    return r * r + g * g + b * b;
  }

In terms of performance you can also store the colors in converted values saving the need to raise each channel to the power of 2.2 each time you test the distance.

For example a named color

{ name: "Aare River", rgb: { r: 0 ** 2.2, g: 184 ** 2.2, b: 159 ** 2.2 } },

Exponentiation (**) operator

Incase you are not familiar with the ** operator. It is the same as Math.pow.

For example Math.pow(10, 2.2) === 10 ** 2.2;

To get the root use the inverse power.

For example Math.sqrt(10) === 10 ** (1 / 2) === 10 ** 0.5

Search

The loop you use to find the closest color can be improved.

Use a for of loop

There is no need to use a counter i if you use a for of loop.

Early exit

Move the early exit into the block that that sets closestDistance to a new value, this will save you many cycles.

The improved search would look like.

Note I changed the return type (assume you use an array lookup outside the function which is not needed if you have the color object) and function name to more closely match the functions behavior.

function findClosestColor(color: ColorRGB): [namedColor: ColorRGB, distance: number] {
  var closestColor: ColorRGB;
  var closestDistance = Infinity;
  for (const namedColor of colorsNames) {
    const distance = getColorsDistance(color, namedColor.rgb);
    if (distance < closestDistance) {   
      closestColor = namedColor;
      closestDistance = distance;
      if (closestDistance === 0) { break; }
    }
  }
  return [closestColor, closestDistance];
}

Performance

You say

"Currently it works fine for the few calls per seconds, but after 30-50 calls per seconds there is noticeable lag"

Unless you have a huge list of colors (There are 147 named HTML colors) or very slow device, the lag at 30 searches per second (One search > 16ms to create noticeable lag????) hints at another source of performance loss.

On an mid range PC (And using the sRGB logarithmic distance) I can search well over 10,000 colors from a list of 256 colors in under 16ms (Maintaining smooth 60FPS animation).

Your slowdown begins 4 orders of magnitude sooner using a simpler calculation, something else is going on as JavaScript is not that slow.