Getting hex colours from a image

Question

I am trying to get the hex colours from an image. The problem I am having is that for some reason randomly the code causes high CPU usage, which times out the browser and I am not sure how to optimise the code. I am not sure where the high CPU usage is. I've tried adding delays using setTimeout() but with no luck.

The code was original written in Javascript but I am converted it to Typescript,

Here is full code code which returns the hex values

import {Injectable} from '@angular/core';

@Injectable()
export class ExtractColours {

  private euclidean(p1, p2) {
    let s = 0;
    for (let i = 0, l = p1.length; i < l; i++) {
      s += Math.pow(p1[i] - p2[i], 2)
    }
    return Math.sqrt(s);
  }

  private calculateCenter(points, n) {
    let vals = [];
    let plen = 0;

    for (let i = 0; i < n; i++) { vals.push(0); }
    for (let i = 0, l = points.length; i < l; i++) {
      plen++;
      for (let j = 0; j < n; j++) {
        vals[j] += points[i][j];
      }
    }
    for (let i = 0; i < n; i++) {
      vals[i] = vals[i] / plen;
    }
    return vals;
  }


private kmeans(points, k, min_diff) {

        let plen = points.length;
        let clusters = [];
        let seen = [];

        while (clusters.length < k) {
          let idx = parseInt(String(Math.random() * plen));
          let found = false;
          for (let i = 0; i < seen.length; i++ ) {
            if (idx === seen[i]) {
              found = true;
              break;
            }
          }
          if (!found) {
            seen.push(idx);
            clusters.push([points[idx], [points[idx]]]);
          }
        }

        while (true) {
          let  plists = [];
          for (let i = 0; i < k; i++) {
            plists.push([]);
          }

          for (let j = 0; j < plen; j++) {
            let p = points[j];
            let smallest_distance = 10000000;
            let idx = 0;

            for (let i = 0; i < k; i++) {
              let distance = this.euclidean(p, clusters[i][0]);
              if (distance < smallest_distance) {
                smallest_distance = distance;
                idx = i;
              }
            }
            plists[idx].push(p);
          }

          let diff = 0;

          for (let i = 0; i < k; i++) {
            let old = clusters[i];
            let list = plists[i];
            let center = this.calculateCenter(plists[i], 3);
            let dist = this.euclidean(old[0], center);
            clusters[i] = [center, (plists[i])];
            diff = diff > dist ? diff : dist;
          }
          if (diff < min_diff) {
            break;
          }
        }

        return clusters;
      }

here I am converting the rgb to hex but I am also returning the alpha value

private rgbToHex(rgb) {

          function th(i) {
            let h = parseInt(i).toString(16);
            return h.length == 1 ? '0'+h : h;
          }

          let alpha = (parseInt(th(rgb[0]),16) + parseInt(th(rgb[1]),16) + parseInt(th(rgb[2]),16)) / 3;

        return parseInt(String(alpha)).toString(16) +'#' + th(rgb[0]) + th(rgb[1]) + th(rgb[2]) ;
      }


      public process_image(img, ctx) {
        let points = [];

        ctx.drawImage(img, 0, 0, 200, 200);

        let data = ctx.getImageData(0, 0, 200, 200).data;

        for (let i = 0, l = data.length; i < l;  i += 4) {
          let r = data[i];
          let g = data[i+1];
          let b = data[i+2];
          points.push([r, g, b]);
        }
        let results = this.kmeans(points, 3, 1);
        let hex = [];
        for (let i = 0; i < results.length; i++) {
          hex.push(this.rgbToHex(results[i][0]));
        }

        return hex;
      }
    }

Answer 1

General feedback

There are a few ways that some of the loops can be simplified (see below). These may or may not improve the high CPU issue.

The code makes some repeated calls to functions with the same values in close proximity (e.g. calling th() with each value of rgb twice in rgbToHex()). Storing the returned values and re-using the stored values would make the code more efficient.

I'd consider suggesting the use of functional approaches (E.g. with Array.map(), Array.reduce()) but I wouldn't in this case, given that execution time is an issue.

Targeted feedback

There are some places where const could be used for any variable that doesn't get re-assigned - e.g. vals in ExtractColours::calculateCenter(), plen in ExtractColours::kmeans(), etc. This avoid unintentional re-assignment.

---

There are places where parseInt() is called without a radix - e.g.

let idx = parseInt(String(Math.random() * plen));

and

let h = parseInt(i).toString(16);

The radix should always be specified¹ because it doesn't always default to 10.

---

Let's look at that method ExtractColours::calculateCenter(). The variable plen could be assigned to points.length (like it is in ExtractColours::kmeans()), instead of incrementing that in the second for loop. And then the division of each array element by plen could be moved into the previous for loop.

And vals is declared and assigned like this:

let vals = [];
let plen = 0;

for (let i = 0; i < n; i++) { vals.push(0); }

This could be simplified using Array.fill()

const vals = Array(n).fill(0);

¹_{https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/parseInt#Octal_interpretations_with_no_radix}