Closest Array in Array of Arrays

Question

I have an array colors:

const colors = [
    [0, 10, 56], 
    [40, 233, 247], 
    [50, 199, 70], 
    [255, 0, 0],
    ...
];

and a function reduceColor:

const reduceColor = pix => {
    let lowdist = Number.MAX_SAFE_INTEGER;
    let closestColor;
    for (let color of colors) {
        const dist = Math.abs(pix[0] - color[0]) + 
                     Math.abs(pix[1] - color[1]) + 
                     Math.abs(pix[2] - color[2]) ;
        if (dist<lowdist) {
            lowdist = dist;
            closestColor = color;
        }
    }
    return closestColor;
}

console.log(reduceColor([240, 10, 30]));
// [255, 0, 0]

Which works fine, but is slow in the context of a whole image.

Is there a way to, when supplied an array, check another array (made up of subarrays) for the closest subarray, without having to iterate and check over every subarray?

score 0 · Answer 1 · answered Jan 31 '21 at 03:33

I don't think there is a better solution, you have to check that every row, but you could use Typed Arrays that has usually faster implementations, if you make a good use of their built-in methods. Usually browsers use these typed arrays in audio processing or canvas rendering.

Surely avoid JS Arrays because they are not contiguos in the memory, huge operations on them can be very slow. Typed arrays are contiguos instead.

Also avoid to use Math methods because they are implemented with the abstraction of JS interpreter objects, so Math.abs could be quite slow (it should handle big number, floating points, string, null, NaN, etc.). Numerical operations can be faster in these cases.

For the solution, you could use a Uint32Array (MDN), by reinterpreting the colors as a 32-bit number. In hexadecimal we represent a byte with 2 hex digits, so 32-bit is 8 digits. We will store them in the array as:

   -- RR GG BB
0x 00 00 00 00

function makeColor(r, g, b) {
  // the 32-bit color will be "0x00RRGGBB" in hex
  return (r << 16) + (g << 8) + b;
}

function parseColor(color) {
  // isolating the corrispondent bit of the colors
  return [ (color & 0xff0000) >> 16, (color & 0xff00) >> 8, color & 0xff ];
}

function makeColorArray(colors) {
  // creating the Uint32Array from the colors array
  return new Uint32Array(colors.map(c => makeColor(...c)));
}

function distanceRGB(p1, p2) {
  let r1 = (p1 & 0xff0000) >> 16,  // extract red p1
      g1 = (p1 &   0xff00) >> 8,   // extract green p1
      b1 =  p1 &     0xff,         // extract blue p1
      r2 = (p2 & 0xff0000) >> 16,  // extract red p2
      g2 = (p2 &   0xff00) >> 8,   // extract green p2
      b2 =  p2 &     0xff,         // extract blue p2
      rd = r1 > r2 ? (r1 - r2) : (r2 - r1), // compute dist r
      gd = g1 > g2 ? (g1 - g2) : (g2 - g1), // compute dist g
      bd = b1 > b2 ? (b1 - b2) : (b2 - b1); // compute dist b
  return rd + gd + bd; // sum them up
}

// rising the threshold can speed up the process
function findNearest(colors, distance, threshold) {
  return function(pixel) {
    let bestDist = 765, best = 0, curr; // 765 is the max distance
    for (c of colors) {
      curr = distance(pixel, c);
      if (curr <= threshold) { return c; }
      else if (curr < bestDist) {
        best = c;
        bestDist = curr;
      }
    }
    return best;
  };
}

const colors = makeColorArray([
    [0, 10, 56], 
    [40, 233, 247], 
    [50, 199, 70], 
    [255, 0, 0],
    //... other colors
]);

const image = makeColorArray([
   [240, 10, 30]
   //... other pixels
])

const nearest = Array.from(image.map(findNearest(colors, distanceRGB, 0))).map(parseColor)

// ===== TEST  =====
function randomColor() {
  return [ Math.floor(Math.random() * 255), Math.floor(Math.random() * 255), Math.floor(Math.random() * 255) ];
}
testImages = [];
for (let i = 0; i < 1000000; ++i) { testImages.push(randomColor()); }
testImages = makeColorArray(testImages)

testColors = [];
for (let i = 0; i < 1000; ++i) { testColors.push(randomColor()); }
testColors = makeColorArray(testColors);

// START
let testNow = Date.now();
Array.from(testImages.map(findNearest(testColors, distanceRGB, 0))).map(parseColor)
console.log(Date.now() - testNow)

I've tested it over a million random pixels (1000x1000) with 4 colors and takes less then a second (~250-450ms), with a thousand of test colors takes 12-15 seconds. The same experiment with a normal Array took 4-6 seconds just with 4 colors, I did not try the thousand colors test (all on my PC obviously).

Consider to pass heavy work to a Worker (MDN) to avoid UI freezing.

I don't know if it is enough to be runned on a bigger image. I'm sure it can be further optimized (maybe through Gray code hamming distance), but it is a good start point by the way.

You can also be interested to get a way to extract pixels values from images, just check ImageData (MDN) and how to retrive it (Stack Overflow) from a <img> or <canvas> element.

Closest Array in Array of Arrays

1 Answers1