• Address: preview zhangyuyan. Cn/example/rep…
  • Source: github.com/RyanProMax/…

Recently I learned machine learning and just learned k-means clustering algorithm, so I wrote a demo as a practice.

The principle is simple:

  1. Read the image data and convert it into a matrix data set, the unit is pixel, and the eigenvalues are: R, G, B, A.
  2. The data set is classified by k-means algorithm.
  3. Get the corresponding classification of background color, convert all pixel colors under this classification into target color, and finally output the image.

1. What is k-means?

Wikipedia: K-average algorithm

[Machine learning] K-means (very detailed)

This is a clustering algorithm based on Euclidean distance.

Suppose we have a set of points on a two-dimensional plane. We now want to divide these points into three classes (k=3).

You might say, well, isn’t that obvious? Just divide the three squares.

However, machines are different from human thinking, we must first give it the rules of division, it is possible to make it achieve automatic classification.

So what are the regular properties of regions?

If each region has a regional center (cluster center), then all points in the region are closest to their corresponding regional center.

In other words, we only need to find the three best regional centers, and then we get the set of points belonging to that region. The whole clustering problem is then transformed into the problem of calculating the optimal solution of regional center.

So when is a regional center optimal?

When the regional center approximates the mean center of the regional point set.

Algorithm steps

  1. Initialize k points at random locations as [cluster center];
  2. For each sample in the dataset, its distance to k cluster centers was calculated, and it was divided into the corresponding class of the cluster center with the smallest distance.
  3. For the data set of each category, its clustering center is recalculated, that is, the centroid of all samples belonging to the category.
  4. Repeat steps 2 and 3 until the clustering center reaches the minimum error.

We first randomly generate 3 regional centers and find the point set (region) with the shortest corresponding distance. You can see that the random classification is very poor.

Then we first calculate the average center of the above regions, and recalculate the regional point set as the new regional center.

Here’s the result, and you can see that we’re pretty close to where we want to be.

And then we loop in and we get our final classification result.

  • Online demo address: ryanpromax. Making. IO/MachineLear…

  • Online demo source: github.com/RyanProMax/…

2. Online background change program

2.1 Read image data and convert it into matrix data set

// Get the width and height of the image and the img tag
const getImageSize = img= > {
  return new Promise((resolve, reject) = > {
    const image = new Image();
    image.src = img;
    image.onload = e= > {
      if (e.path && e.path.length) {
        const { width, height } = e.path[0];
        resolve([width, height, image]);
      } else{ reject(); }}; image.onerror = reject; }); };const transition = imageData= > {
  const ret = [];
  for (let i = 0; i < imageData.length; i += 4) {
    ret.push([imageData[i], imageData[i + 1], imageData[i + 2], imageData[i + 3]]);
  }
  return ret;
};

// Get imageData from canvas and convert it to RGBA pixel matrix
export const getImageData = async img => {
  const [width, height, image] = await getImageSize(img);
  const canvas = document.createElement('canvas');
  [canvas.width, canvas.height] = [width, height];
  const ctx = canvas.getContext('2d');
  ctx.drawImage(image, 0.0);
  return [transition(ctx.getImageData(0.0, width, height).data), width, height];
};
Copy the code

The first result is a two-dimensional matrix (array), row is each pixel, column is the corresponding r, G, B, A value of the pixel, namely the feature vector.

The last two are the width and height of the picture respectively.

2.2 k – means classification

Here I don’t bother to write (dog. JPG), so I use the Node-Kmeans library to divide the pixel set into four categories (in fact, it can also be divided into two categories, but PERSONALLY I think four categories will be more accurate, that is, it may reduce the interference of other colors. However, the calculation time will increase correspondingly, so set it as needed.

const kmeans = require('node-kmeans');

export const useKmeans = vectors= > {
  return new Promise((resolve, reject) = > {
    kmeans.clusterize(vectors, { k: 4 }, (err, res) = > {
      if (err) reject(err);
      resolve(res);
    });
  });
};
Copy the code

The result is returned in the following format:

  • Centroid is an array of eigenvalues at the center of the cluster.
  • A cluster is the set of points corresponding to a class.
  • ClusterInd is the subscript of cluster.

Here, the region to which the 0th pixel belongs is directly taken as the background color region.

const result = await useKmeans(imageData);
const target = result.find(x= > x.clusterInd.includes(0));
Copy the code

(Don’t ask what happens if your PHOTO has a border, it’s lazy.)

2.3 Convert the background color to the color of the pixel

I won’t go into details here, just change the RGBA value of the pixel to the target color value, and then convert the RGBA pixel matrix back to the image output.

Individual is converted through canvas, performance may not be optimal, do not spray HH if you do not like.

export const toBase64 = (imageData, w, h) = > {
  imageData = imageData.flat(1);
  const canvas = document.createElement('canvas');
  [canvas.width, canvas.height] = [w, h];
  const ctx = canvas.getContext('2d');
  const _imageData = ctx.createImageData(w, h);
  if (_imageData.data.set) {
    _imageData.data.set(imageData);
  } else {
    // IE9
    imageData.forEach(function (val, i) {
      _imageData.data[i] = val;
    });
  }
  ctx.putImageData(_imageData, 0.0);
  return canvas.toDataURL();
};
Copy the code

At this point, our transformation is complete.

Don’t ask me if there is interference in the portrait of the id photo (close to the background, noise), this is left to everyone free play (my own idea is to solve through the connected domain algorithm, but mainly I am too lazy to write).

END~