I took fundamentals of Data Mining this semester. To hand in a big assignment, just because I learn the front end, want to use JavaScript to achieve Kmeans to get picture tone.
Realize the function
Select the image through the browser and use JavaScript and Kmeans locally to get the image tone.
Implementation approach
A computer image is composed of multiple pixels, which are mixed with red, green and blue colors. The range of red, green and blue channels is [0,255]. Because of this, if the pixel of a picture is a point in three-dimensional space, then a computer image is a bunch of points in three-dimensional space. Kmeans algorithm can be used to cluster these points, and the final result is the hue of the image color.
Theoretical basis -Kmeans
Birds of a feather flock together
- First enter the value of K, that is, we want to cluster the data set to get k groups.
- K data points were randomly selected from the dataset as the centroid and added into the independent initial cluster.
- Add each point in the set to the nearest cluster.
- Then each cluster has a bunch of points under it. Calculate the center of mass of each cluster.
- If the distance between the new centroid and the original centroid is less than a set threshold, the clustering has reached the desired value. The algorithm terminates, otherwise repeat 3-5.
steps
Image upload
Read the image to the browser side through FileReader.
let file = null;
let image = new Image();
let reader = new FileReader();
reader.onload = function (e) {
image.src = e.target.result;
};
document.querySelector("#uploadFile").onchange = function (e) {
file = event.target.files[0];
if (file.type.indexOf("image") = =0) { reader.readAsDataURL(file); }};Copy the codeImage compression
If the image is too large, or if there are too many pixels, the computation becomes too heavy, causing the browser to fake death. Here you need to compress the selected image. In JS, images can be compressed using canvas’s drawImage method. The main code is as follows
let canvas = document.querySelector("canvas");
let image = new Image();
let targetHeight, targetWidth;
image.onload = function () {
let context = canvas.getContext("2d");
let maxWidth = 500,
maxHeight = 500;
targetWidth = image.width;
targetHeight = image.height;
let originWidth = image.width,
originHeight = image.height;
if (originWidth / originHeight > maxWidth / maxHeight) {
targetWidth = maxWidth;
targetHeight = Math.round(maxWidth * (originHeight / originWidth));
} else {
targetHeight = maxHeight;
targetWidth = Math.round(maxHeight * (originWidth / originHeight));
}
canvas.width = targetWidth;
canvas.height = targetHeight;
context.drawImage(image, 0.0, targetWidth, targetHeight);
};
Copy the codeKmeans algorithm
Next, use JavaScript to implement Kmeans. For convenience, several helper classes are defined, and some member functions are implemented in them, which are easy to call.
/** * Pixel helper class **@class Pixel* /
class Pixel {
constructor(r, g, b) {
this._r = r;
this._g = g;
this._b = b;
}
get rgb() {
return {
r: this._r,
g: this._g,
b: this._b, }; }}/** * The corresponding set of points ** in the RGB color space of the image@class RGBSpace* /
class RGBSpace {
constructor(canvasContext, img) {
// Get the RGB data of the image
let data = canvasContext.getImageData(0.0, img.width, img.height).data;
let rgbSpace = [];
for (let row = 0; row < img.height; row++) {
for (let col = 0; col < img.width; col++) {
// Since getImageData returns the alpha of points in order, add four
let r = data[(img.width * row + col) * 4];
let g = data[(img.width * row + col) * 4 + 1];
let b = data[(img.width * row + col) * 4 + 2];
rgbSpace.push(newPixel(r, g, b)); }}this._rgbSpace = rgbSpace;
this._length = img.height * img.width;
}
// Get the Pixel at the specified location
getPixel(idx) {
if (idx > this._length) return;
return this._rgbSpace[idx];
}
// Get a random Pixel in an image
getRandomPixel() {
return this.getPixel(Math.floor(Math.random() * this._length));
}
// Get the number of points
get size() {
return this._length; }}/ * * * *@class Cluster* /
class Cluster {
// Center RGB and the points contained in the cluster
constructor(pixel) {
this._centerR = pixel._r;
this._centerG = pixel._g;
this._centerB = pixel._b;
this._cluster = [pixel];
}
// Add to cluster
addToCluster(pixel) {
this._cluster.push(pixel);
}
// recalculate centroid
recalculateCenter() {
let oldCenter = new Pixel(this._centerR, this._centerG, this._centerB);
let length = this._cluster.length;
let reduced = this._cluster.reduce(
(pre, cur) = > {
let { r: rPre, g: gPre, b: bPre } = pre;
let { r: rCur, g: gCur, b: bCur } = cur.rgb;
return {
r: rPre + rCur,
g: gPre + gCur,
b: bPre + bCur,
};
},
{ r: 0.g: 0.b: 0});let r = reduced.r / length;
let g = reduced.g / length;
let b = reduced.b / length;
this.cluster = [new Pixel(r, g, b)];
this._centerR = r;
this._centerG = g;
this._centerB = b;
// Return the original centroid (the old centroid is "close enough" to end the algorithm)
return new Cluster(oldCenter);
}
// Get the distance of a pixel relative to the centroid of the cluster, or the distance between centroids of two clusters
getDistance(pixel) {
let { _centerR, _centerG, _centerB } = this;
if (pixel instanceof Pixel) {
let { r, g, b } = pixel.rgb;
return (r - _centerR) ** 2 + (g - _centerG) ** 2 + (b - _centerB) ** 2;
}
if (pixel instanceof Cluster) {
let { _centerR: r, _centerG: g, _centerB: b } = pixel;
return (r - _centerR) ** 2 + (g - _centerG) ** 2 + (b - _centerB) ** 2; }}}/** * is used to classify **@param {*} ClusterList
* @param {*} space
* @return {*}* /
function classify(ClusterList, space) {
space._rgbSpace.forEach((pixel) = > {
// Each pixel computes the distance to the centroid of the current cluster
let distanceArray = ClusterList.map((Cluster) = > {
return Cluster.getDistance(pixel);
});
// Add the pixel to the nearest cluster
let min = Math.min(... distanceArray);let minIndex = distanceArray.indexOf(min);
ClusterList[minIndex].addToCluster(pixel);
});
// Recalculate the centroID of each cluster and return the original clusterList
return ClusterList.map((Cluster) = > {
return Cluster.recalculateCenter();
});
}
/** * Determine whether the new and old points are close enough **@param {*} old
* @param {*} now
* @param {*} threshold
* @return {*}* /
function isCloseEnough(old, now, threshold) {
let index = 0;
for (let oldCenter of old) {
// If the centroID of any cluster and the centroID of the old cluster are greater than a certain threshold, it is not close enough
if (oldCenter.getDistance(now[index++]) > threshold) return false;
}
return true;
}
/** * use Kmeans to find the corresponding color **@param {*} context
* @param {*} image
* @param {*} colorPanel
* @param {*} K
* @param {*} threshold* /
function main(context, image, colorPanel, K, threshold) {
// Get an instance of RGBSpace
let space = new RGBSpace(context, image);
// Randomly select K pixels as centroids of K clusters
let ClusterList = Array(K)
.fill(1)
.map(() = > new Cluster(space.getRandomPixel()));
let i = 0;
// This is related to the DOM, if the color plate, create the corresponding container
if (colorPanel) {
ClusterList.forEach((el, idx) = > {
let div = document.createElement("div");
div.className = `panel-${idx}`;
colorPanel.appendChild(div);
});
}
// Loop until each cluster centroID is "close enough" to the last centroID
while (true) {
console.log(i++);
let oldClusterList = classify(ClusterList, space);
console.log(oldClusterList);
if (isCloseEnough(oldClusterList, ClusterList, threshold)) {
break;
}
// Display the result on the corresponding palette
if (colorPanel) {
ClusterList.forEach((cc, index) = > {
let div = document.createElement("span");
div.style.backgroundColor = `rgb(${cc._centerR}.${cc._centerG}.${cc._centerB}) `; colorPanel.children[index].appendChild(div); }); }}}Copy the codeAll the code
index.html
<! DOCTYPEhtml>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="Width = device - width, initial - scale = 1.0" />
<title>Kmeans gets the main color of the picture</title>
<style>
body {
display: flex;
flex-direction: column;
align-items: center;
}
main {
display: flex;
flex-direction: column;
align-items: center;
}
.colorPanel div {
height: 20px;
display: flex;
}
.colorPanel div span {
height: 20px;
width: 20px;
display: block;
}
canvas {
box-shadow: 0 0 10px rgba(0.0.0.0.1);
margin: 20px;
}
section {
padding: 10px;
}
</style>
</head>
<body>
<h2>Kmeans gets the main color of the graph</h2>
<main>
<canvas></canvas>
<section>
<input id="uploadFile" type="file" />
<input class="k" type="number" placeholder="How many colors do I need to output?" />
<button class="start">Start</button>
</section>
<div class="colorPanel"></div>
</main>
</body>
<script src="./index.js"></script>
<script>
let file = null;
let canvas = document.querySelector("canvas");
let colorPanel = document.querySelector(".colorPanel");
let image = new Image();
let reader = new FileReader();
let targetHeight, targetWidth;
image.onload = function () {
let context = canvas.getContext("2d");
let maxWidth = 500,
maxHeight = 500;
targetWidth = image.width;
targetHeight = image.height;
let originWidth = image.width,
originHeight = image.height;
if (originWidth / originHeight > maxWidth / maxHeight) {
targetWidth = maxWidth;
targetHeight = Math.round(maxWidth * (originHeight / originWidth));
} else {
targetHeight = maxHeight;
targetWidth = Math.round(maxHeight * (originWidth / originHeight));
}
canvas.width = targetWidth;
canvas.height = targetHeight;
context.drawImage(image, 0.0, targetWidth, targetHeight);
};
reader.onload = function (e) {
image.src = e.target.result;
};
document.querySelector("#uploadFile").onchange = function (e) {
file = event.target.files[0];
if (file.type.indexOf("image") = =0) { reader.readAsDataURL(file); }};document.querySelector("button.start").onclick = function () {
let context = canvas.getContext("2d");
let K = parseInt(document.querySelector("input.k").value);
if (K <= 0) {
alert("Please enter correct parameters");
return;
}
document.querySelector(".colorPanel").innerHTML = "";
main(
context,
{ height: targetHeight, width: targetWidth },
colorPanel,
K,
1
);
};
</script>
</html>
Copy the codeindex.js
See Kmeans algorithm code for detailsCopy the codeconclusion
In fact, there are still some areas that need to be improved. For example, the color may be too similar. In fact, when randomly selecting the centroid of the cluster, we can check whether it is too similar to the existing cluster, and then select again as appropriate.
In fact, while doing it, I was also wondering whether I could “normalize” the picture. Later, I thought that if I normalized the picture, I would change the color. The selected color may not be the color of the original image. Then you can associate each normalized Pixel instance with the original Pixel instance using a Proxy, only using the normalized Pixel for statistical significance, and then you can think, HMM. Forget it. I’m tired.