2e:null 2f:["$","title",null,{"children":"Finding palettes of dominant colors with the k-means clustering algorithm | Roman Klimenko | Observable"}] 34:T1abb,{ const margin = { top: 20, right: 30, bottom: 30, left: 40 } const radius = 1 const ticks = 3 const padding = 30 const chartHeight = Math.min(200, Math.round((width - margin.left - margin.right - padding - padding) / 3)) const chartWidth = chartHeight const svgHeight = margin.top + (chartHeight + padding + chartHeight + padding + chartHeight) + margin.bottom const svgWidth = margin.left + (chartWidth + padding + chartWidth + padding + chartWidth) + margin.right const svg = d3.select(DOM.svg(svgWidth, svgHeight)) const data = seed.slice(0) /* RGB x0 x1 x2 y0 R RR00 GR01 BR02 y1 G RG10 GG11 BG12 y2 B RB20 GB21 BB22 R G B */ const scale = () => d3.scaleLinear().domain([-10, 265]) const x0 = scale() .range([margin.left, margin.left + chartWidth]) const x1 = scale() .range([margin.left + chartWidth + padding, margin.left + chartWidth + padding + chartWidth]) const x2 = scale() .range([ margin.left + (chartWidth + padding) * 2, margin.left + (chartWidth + padding) * 2 + chartWidth]) const y0 = scale() .range([margin.top + chartHeight, margin.top]) const y1 = scale() .range([ margin.top + chartHeight + (padding + chartHeight), margin.top + (padding + chartHeight)]) const y2 = scale() .range([ margin.top + chartHeight + (padding + chartHeight) * 2, margin.top + (padding + chartHeight) * 2]) svg.append('text') .text('R') .attr('fill', 'red') .attr('font-family', 'sans-serif') .attr('x', x0(255 / 2)) .attr('y', y2(0) + margin.bottom) svg.append('text') .text('G') .attr('fill', 'green') .attr('font-family', 'sans-serif') .attr('x', x1(255 / 2)) .attr('y', y2(0) + margin.bottom) svg.append('text') .text('B') .attr('fill', 'blue') .attr('font-family', 'sans-serif') .attr('x', x2(255 / 2)) .attr('y', y2(0) + margin.bottom) svg.append('text') .text('R') .attr('fill', 'red') .attr('font-family', 'sans-serif') .attr('x', x0(0) - margin.left) .attr('y', y0(255 / 2)) svg.append('text') .text('G') .attr('fill', 'green') .attr('font-family', 'sans-serif') .attr('x', x0(0) - margin.left) .attr('y', y1(255 / 2)) svg.append('text') .text('B') .attr('fill', 'blue') .attr('font-family', 'sans-serif') .attr('x', x0(0) - margin.left) .attr('y', y2(255 / 2)) const transform = (x, y) => (g) => g.attr('transform', `translate(${x},${y})`) svg.append('g').call(transform(0, margin.top + chartHeight)).call(d3.axisBottom(x0).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight)).call(d3.axisBottom(x1).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight)).call(d3.axisBottom(x2).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + padding + chartHeight)).call(d3.axisBottom(x0).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + padding + chartHeight)).call(d3.axisBottom(x1).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + padding + chartHeight)).call(d3.axisBottom(x2).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + (padding + chartHeight) * 2)) .call(d3.axisBottom(x0).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + (padding + chartHeight) * 2)) .call(d3.axisBottom(x1).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + (padding + chartHeight) * 2)) .call(d3.axisBottom(x2).ticks(ticks)) svg.append('g').call(transform(margin.left,0)).call(d3.axisLeft(y0).ticks(ticks)) svg.append('g').call(transform(margin.left,0)).call(d3.axisLeft(y1).ticks(ticks)) svg.append('g').call(transform(margin.left,0)).call(d3.axisLeft(y2).ticks(ticks)) svg.append('g').call(transform(margin.left + chartWidth + padding,0)).call(d3.axisLeft(y0).ticks(ticks)) svg.append('g').call(transform(margin.left + chartWidth + padding,0)).call(d3.axisLeft(y1).ticks(ticks)) svg.append('g').call(transform(margin.left + chartWidth + padding,0)).call(d3.axisLeft(y2).ticks(ticks)) svg.append('g').call(transform(margin.left + (chartWidth + padding) * 2,0)).call(d3.axisLeft(y0).ticks(ticks)) svg.append('g').call(transform(margin.left + (chartWidth + padding) * 2,0)).call(d3.axisLeft(y1).ticks(ticks)) svg.append('g').call(transform(margin.left + (chartWidth + padding) * 2,0)).call(d3.axisLeft(y2).ticks(ticks)) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x0(d.rgba.r)) .attr('cy', d => y0(d.rgba.r)) .attr('fill', d => d3.rgb(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x1(d.rgba.g)) .attr('cy', d => y0(d.rgba.r)) .attr('fill', d => d3.rgb(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x2(d.rgba.b)) .attr('cy', d => y0(d.rgba.r)) .attr('fill', d => d3.rgb(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x0(d.rgba.r)) .attr('cy', d => y1(d.rgba.g)) .attr('fill', d => d3.rgb(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x1(d.rgba.g)) .attr('cy', d => y1(d.rgba.g)) .attr('fill', d => d3.rgb(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x2(d.rgba.b)) .attr('cy', d => y1(d.rgba.g)) .attr('fill', d => d3.rgb(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x0(d.rgba.r)) .attr('cy', d => y2(d.rgba.b)) .attr('fill', d => d3.rgb(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x1(d.rgba.g)) .attr('cy', d => y2(d.rgba.b)) .attr('fill', d => d3.rgb(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x2(d.rgba.b)) .attr('cy', d => y2(d.rgba.b)) .attr('fill', d => d3.rgb(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) return svg.node() }35:T4d4,md`## K is for cluster > *k-means clustering* is a method of vector quantization, originally from signal processing, that is popular for cluster analysis in data mining. k-means clustering aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster. [Wikipedia](https://en.wikipedia.org/wiki/K-means_clustering) The _classical_ k-means algorithm consists of the following steps: 1. Take random **k** points (called _centroids_) from a space formed by our _data_ _points_ (i.e. vectors). 2. Assign every data point to the closest centroid. Each centroid with assigned data point we call a _cluster_. 3. For each cluster, find a new centroid by calculating a center between all the data points in the cluster. 4. Repeat steps 2. and 3. while the coordinates of centroids change. Simple as a pie, isn't it? Well, yes, but there are some nuances. ### Performance Say, **k** is a number of clusters (as well as centroids) and **n** is a number of data points, **d** is a number of dimensions (vector length) and **i** is a number of iterations (how many times 2. and 3. have to run). Roughly speaking, the complexity of this will be:`36:T63f,md`This can be pretty slow, and here are some simple ways to speed it up: 1. Find the final centroids on the sample data and then run the last iteration on the full set. Usually, this significantly reduces the number of iterations on the full set. 2. Set the top limit for the iterations number, so the method will not freeze forever. 3. Set the minimal distance when centroids are considered to be the same. On my code, this saved 3-5 iterations when the distance is less than one but still slightly greater than zero. 4. If you use Euclidean distance, don't calculate the root, the squared distance is ok. ### Distance and scale 1. Squared [Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance) is the simplest one, however, it may not be good to calculate the [color difference](https://en.wikipedia.org/wiki/Color_difference). 2. RGB color space is very simple, but again, if you really need to calculate the color difference precisely, use Lab and CIEDE2000. ### The optimal number of k To find an optimal k, I find the average [variance](https://en.wikipedia.org/wiki/Variance) for each cluster on the sample data. Simply put, a cluster's variance is an average distance between its centroid and each point of the cluster. Therefore, the average variance of for a given k is the average variance of all its clusters. If we draw a chart where the variance is on the y-axis and k is the x-axis, we will see that the variance drops down, but at some point, the slope is decreasing significantly and after this value of k we can observe even some increasing of the variance: `37:T414,{ const margin = { top: 20, right: 30, bottom: 30, left: 40 } const height = Math.min(400, width) const data = samples.map((s) => { return { k: s.k, variance: s.variance } }) const x = d3.scaleLinear() .domain(d3.extent(data, d => d.k)) .range([margin.left, width - margin.right]) .nice() const y = d3.scaleLinear() .domain(d3.extent(data, d => d.variance)) .range([height - margin.bottom, margin.top]) .nice() const svg = d3.select(DOM.svg(width, height)) svg.append('g') .attr('transform', `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(x)) svg.append('g') .attr('transform', `translate(${margin.left},0)`) .call(d3.axisLeft(y)) svg.append('path') .datum(data) .attr('fill', 'none') .attr('stroke', 'steelblue') .attr('stroke-width', 1.5) .attr('stroke-linejoin', 'round') .attr('stroke-linecap', 'round') .attr('d', d3.line().x(d => x(d.k)).y(d => y(d.variance))) return svg.node() }38:T28ae,{ const margin = { top: 20, right: 30, bottom: 30, left: 40 } const radius = 1 const centroidRadiusCorrection = 30 const ticks = 3 const padding = 30 const chartHeight = Math.min(200, Math.round((width - margin.left - margin.right - padding - padding) / 3)) const chartWidth = chartHeight const svgHeight = margin.top + (chartHeight + padding + chartHeight + padding + chartHeight) + margin.bottom const svgWidth = margin.left + (chartWidth + padding + chartWidth + padding + chartWidth) + margin.right const svg = d3.select(DOM.svg(svgWidth, svgHeight)) const data = seed.slice(0) /* RGB x0 x1 x2 y0 R RR00 GR01 BR02 y1 G RG10 GG11 BG12 y2 B RB20 GB21 BB22 R G B */ const scale = () => d3.scaleLinear().domain([-10, 265]) const x0 = scale() .range([margin.left, margin.left + chartWidth]) const x1 = scale() .range([margin.left + chartWidth + padding, margin.left + chartWidth + padding + chartWidth]) const x2 = scale() .range([ margin.left + (chartWidth + padding) * 2, margin.left + (chartWidth + padding) * 2 + chartWidth]) const y0 = scale() .range([margin.top + chartHeight, margin.top]) const y1 = scale() .range([ margin.top + chartHeight + (padding + chartHeight), margin.top + (padding + chartHeight)]) const y2 = scale() .range([ margin.top + chartHeight + (padding + chartHeight) * 2, margin.top + (padding + chartHeight) * 2]) svg.append('text') .text('R') .attr('fill', 'red') .attr('font-family', 'sans-serif') .attr('x', x0(255 / 2)) .attr('y', y2(0) + margin.bottom) svg.append('text') .text('G') .attr('fill', 'green') .attr('font-family', 'sans-serif') .attr('x', x1(255 / 2)) .attr('y', y2(0) + margin.bottom) svg.append('text') .text('B') .attr('fill', 'blue') .attr('font-family', 'sans-serif') .attr('x', x2(255 / 2)) .attr('y', y2(0) + margin.bottom) svg.append('text') .text('R') .attr('fill', 'red') .attr('font-family', 'sans-serif') .attr('x', x0(0) - margin.left) .attr('y', y0(255 / 2)) svg.append('text') .text('G') .attr('fill', 'green') .attr('font-family', 'sans-serif') .attr('x', x0(0) - margin.left) .attr('y', y1(255 / 2)) svg.append('text') .text('B') .attr('fill', 'blue') .attr('font-family', 'sans-serif') .attr('x', x0(0) - margin.left) .attr('y', y2(255 / 2)) const transform = (x, y) => (g) => g.attr('transform', `translate(${x},${y})`) svg.append('g').call(transform(0, margin.top + chartHeight)).call(d3.axisBottom(x0).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight)).call(d3.axisBottom(x1).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight)).call(d3.axisBottom(x2).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + padding + chartHeight)).call(d3.axisBottom(x0).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + padding + chartHeight)).call(d3.axisBottom(x1).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + padding + chartHeight)).call(d3.axisBottom(x2).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + (padding + chartHeight) * 2)) .call(d3.axisBottom(x0).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + (padding + chartHeight) * 2)) .call(d3.axisBottom(x1).ticks(ticks)) svg.append('g').call(transform(0, margin.top + chartHeight + (padding + chartHeight) * 2)) .call(d3.axisBottom(x2).ticks(ticks)) svg.append('g').call(transform(margin.left,0)).call(d3.axisLeft(y0).ticks(ticks)) svg.append('g').call(transform(margin.left,0)).call(d3.axisLeft(y1).ticks(ticks)) svg.append('g').call(transform(margin.left,0)).call(d3.axisLeft(y2).ticks(ticks)) svg.append('g').call(transform(margin.left + chartWidth + padding,0)).call(d3.axisLeft(y0).ticks(ticks)) svg.append('g').call(transform(margin.left + chartWidth + padding,0)).call(d3.axisLeft(y1).ticks(ticks)) svg.append('g').call(transform(margin.left + chartWidth + padding,0)).call(d3.axisLeft(y2).ticks(ticks)) svg.append('g').call(transform(margin.left + (chartWidth + padding) * 2,0)).call(d3.axisLeft(y0).ticks(ticks)) svg.append('g').call(transform(margin.left + (chartWidth + padding) * 2,0)).call(d3.axisLeft(y1).ticks(ticks)) svg.append('g').call(transform(margin.left + (chartWidth + padding) * 2,0)).call(d3.axisLeft(y2).ticks(ticks)) const color = (r, g, b) => { const closest = { centroid: result.centroids[0], distance: distance([r, g, b], result.centroids[0]) } for (let i = 1; i < result.centroids.length; i++) { const _distance = distance([r, g, b], result.centroids[i]) if (_distance < closest.distance) { closest.centroid = result.centroids[i] closest.distance = _distance } } return d3.rgb(closest.centroid[0], closest.centroid[1], closest.centroid[2]) } svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x0(d.rgba.r)) .attr('cy', d => y0(d.rgba.r)) .attr('fill', d => color(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(result.centroids) .enter() .append('circle') .attr('cx', c => x0(c[0])) .attr('cy', c => y0(c[0])) .attr('stroke', 'black') .attr('fill', c => color(c[0], c[1], c[2])) .attr('r', c => radius * c.points.length / matrix.length * centroidRadiusCorrection) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x1(d.rgba.g)) .attr('cy', d => y0(d.rgba.r)) .attr('fill', d => color(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(result.centroids) .enter() .append('circle') .attr('cx', c => x1(c[1])) .attr('cy', c => y0(c[0])) .attr('stroke', 'black') .attr('fill', c => color(c[0], c[1], c[2])) .attr('r', c => radius * c.points.length / matrix.length * centroidRadiusCorrection) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x2(d.rgba.b)) .attr('cy', d => y0(d.rgba.r)) .attr('fill', d => color(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(result.centroids) .enter() .append('circle') .attr('cx', c => x2(c[2])) .attr('cy', c => y0(c[0])) .attr('stroke', 'black') .attr('fill', c => color(c[0], c[1], c[2])) .attr('r', c => radius * c.points.length / matrix.length * centroidRadiusCorrection) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x0(d.rgba.r)) .attr('cy', d => y1(d.rgba.g)) .attr('fill', d => color(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(result.centroids) .enter() .append('circle') .attr('cx', c => x0(c[0])) .attr('cy', c => y1(c[1])) .attr('stroke', 'black') .attr('fill', c => color(c[0], c[1], c[2])) .attr('r', c => radius * c.points.length / matrix.length * centroidRadiusCorrection) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x1(d.rgba.g)) .attr('cy', d => y1(d.rgba.g)) .attr('fill', d => color(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(result.centroids) .enter() .append('circle') .attr('cx', c => x1(c[1])) .attr('cy', c => y1(c[1])) .attr('stroke', 'black') .attr('fill', c => color(c[0], c[1], c[2])) .attr('r', c => radius * c.points.length / matrix.length * centroidRadiusCorrection) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x2(d.rgba.b)) .attr('cy', d => y1(d.rgba.g)) .attr('fill', d => color(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(result.centroids) .enter() .append('circle') .attr('cx', c => x2(c[2])) .attr('cy', c => y1(c[1])) .attr('stroke', 'black') .attr('fill', c => color(c[0], c[1], c[2])) .attr('r', c => radius * c.points.length / matrix.length * centroidRadiusCorrection) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x0(d.rgba.r)) .attr('cy', d => y2(d.rgba.b)) .attr('fill', d => color(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(result.centroids) .enter() .append('circle') .attr('cx', c => x0(c[0])) .attr('cy', c => y2(c[2])) .attr('stroke', 'black') .attr('fill', c => color(c[0], c[1], c[2])) .attr('r', c => radius * c.points.length / matrix.length * centroidRadiusCorrection) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x1(d.rgba.g)) .attr('cy', d => y2(d.rgba.b)) .attr('fill', d => color(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(result.centroids) .enter() .append('circle') .attr('cx', c => x1(c[1])) .attr('cy', c => y2(c[2])) .attr('stroke', 'black') .attr('fill', c => color(c[0], c[1], c[2])) .attr('r', c => radius * c.points.length / matrix.length * centroidRadiusCorrection) svg.append('g') .selectAll('circle') .data(data) .enter() .append('circle') .attr('cx', d => x2(d.rgba.b)) .attr('cy', d => y2(d.rgba.b)) .attr('fill', d => color(d.rgba.r, d.rgba.g, d.rgba.b)) .attr('r', radius) svg.append('g') .selectAll('circle') .data(result.centroids) .enter() .append('circle') .attr('cx', c => x2(c[2])) .attr('cy', c => y2(c[2])) .attr('stroke', 'black') .attr('fill', c => color(c[0], c[1], c[2])) .attr('r', c => radius * c.points.length / matrix.length * centroidRadiusCorrection) return svg.node() }39:[] 32:{"id":"78d894babaef4084","slug":"finding-palettes-of-dominant-colors-with-the-k-means-cluste","title":"Finding palettes of dominant colors with the k-means clustering algorithm","thumbnail":"8b35f7a8fdbbd34cbc31ba3a08826cce13673e0ec64c098c2080caf4393bf119","access_level":"public","create_time":"$D2018-05-01T16:03:09.207Z","update_time":"$D2018-05-15T19:13:58.387Z","view_time":null,"first_public_time":"$D2018-05-15T19:16:15.591Z","has_unpublished_edits":null,"fork":false,"stars":23,"starred":false,"owner":{"type":"team","id":"fe4aac1446538067","login":"romaklimenko","name":"Roman Klimenko","avatar_url":"https://avatars-next.observableusercontent.com/43ab6d186d90e198c84c69775b1b42aefc76727c72b8f482ac7a3c111107ef4d","tier":"starter_2024"},"version":1820,"publish_version":1820,"role":null,"authored":false,"authors":[{"type":"individual","id":"c5af103943962de2","login":"romaklimenko","name":"Roman Klimenko","avatar_url":"https://avatars-next.observableusercontent.com/43ab6d186d90e198c84c69775b1b42aefc76727c72b8f482ac7a3c111107ef4d","tier":null}],"members":[{"type":"individual","id":"c5af103943962de2","login":"romaklimenko","name":"Roman Klimenko","avatar_url":"https://avatars-next.observableusercontent.com/43ab6d186d90e198c84c69775b1b42aefc76727c72b8f482ac7a3c111107ef4d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":11,"collection":{"id":"645ac6ac048e2a55","slug":"experiments","title":"Experiments","owner":{"id":"fe4aac1446538067","login":"romaklimenko","name":"Roman Klimenko"}},"type":"notebook","body":{"title":"Finding palettes of dominant colors with the k-means clustering algorithm","cells":[{"id":0,"value":"md`# Finding palettes of dominant colors with the k-means clustering algorithm\n\nHere is a quick and dirty implementation of the [k-means clustering](https://en.wikipedia.org/wiki/K-means_clustering) used to find a palette of dominant colors for an image.\n\nThe code is hosted on the [Observable](https://beta.observablehq.com/d/78d894babaef4084) notebook.\n\n\n## Let's take a picture\n\nFor example, let's take this nice colorful photo taken by [Jacek Dylag](https://unsplash.com/@dylu) on [Unsplash](https://unsplash.com/):\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"image = {\n yield new Promise((resolve, reject) => {\n const image = new Image\n image.onload = () => resolve(image)\n image.onerror = reject;\n image.crossOrigin = 'anonymous'\n image.src = 'https://images.unsplash.com/photo-1520364136177-0ed423c02b4a?ixlib=rb-0.3.5&ixid=eyJhcHBfaWQiOjEyMDd9&s=4fbce2b238045d65b14e53f885e8514e&auto=format&fit=crop&w=1506&q=80'\n image.style = `max-width: ${Math.min(width, 600)}px; max-height:600px;`\n })\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1729,"value":"imageData = {\n const width = image.width, height = image.height\n const context = this ? this.context : DOM.context2d(width, height, 1)\n context.drawImage(image, 0, 0, width, height)\n const data = context.getImageData(0, 0, width, height)\n data.context = context\n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1732,"value":"matrix = {\n const result = []\n let x = 0\n let y = 0\n let maxLab = 0\n let minLab = 0\n \n result.height = imageData.height\n result.width = imageData.width\n\n for(let i = 0; i < imageData.data.length; i += 4) {\n const pixel = {\n rgba: {\n r: imageData.data[i],\n g: imageData.data[i + 1],\n b: imageData.data[i + 2],\n a: imageData.data[i + 3],\n },\n position: {\n x: x,\n y: y\n }\n }\n result.push(pixel)\n if(x >= result.width - 1) {\n x = 0\n y++\n }\n else {\n x++\n }\n }\n result.maxLab = maxLab\n result.minLab = minLab\n return result\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1735,"value":"points = matrix.map(p => {\n const result = [p.rgba.r, p.rgba.g, p.rgba.b]\n result.point = p\n return result\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1547,"value":"md`To save the performance (remember, we run this code in the browser), let's take a sample of ${seedSize} random pixels of the image:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1726,"value":"seedSize = 1000","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1739,"value":"seed = {\n const result = []\n const step = Math.floor(matrix.length / seedSize)\n for(let i = 0; i < matrix.length; i += step) {\n result.push(matrix[Math.max(0, i - Math.floor(Math.random() * step))])\n }\n return result\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1566,"value":"{\n const context = DOM.context2d(imageData.width, imageData.height, 1)\n const canvas = context.canvas\n\n const imageData2 = context.getImageData(0, 0, imageData.width, imageData.height)\n\n for (let i = 0; i < seed.length; i++) {\n const start = seed[i].position.y * (imageData2.width * 4) + seed[i].position.x * 4\n imageData2.data[start] = seed[i].rgba.r\n imageData2.data[start + 1] = seed[i].rgba.g\n imageData2.data[start + 2] = seed[i].rgba.b\n imageData2.data[start + 3] = seed[i].rgba.a\n }\n \n context.putImageData(imageData2, 0, 0)\n \n return canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1569,"value":"md`It's nearly impossible to guess the original image from these dots, but because they are randomly taken, we can use them as a sample data.\n\nThe photo's size is ${imageData.width}*${imageData.height}, which gives us ${imageData.width * imageData.height} pixels. Each pixel has 3 dimensions: red, green and blue ([RGB](https://en.wikipedia.org/wiki/RGB_color_model)) and can be represented as a vector:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1624,"value":"tex.block`\n\\begin{aligned}\npx = [R, G, B]\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1621,"value":"md`Let's visualize the sample dots by drawing 2D projections of the 3D RGB color space:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1819,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1572,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1627,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1658,"value":"tex.block`\n\\begin{aligned}\nO(k*n*d*i)\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1661,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1798,"value":"zip = (a, b) => a.map((j, i) => [j, b[i]])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1801,"value":"distance = (a, b) => zip(a, b).map(j => Math.pow(j[1] - j[0], 2)).reduce((a, b) => a + b)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1804,"value":"assign = (centroids, points) => {\n centroids.forEach(c => {\n c.points = []\n c.variance = 0\n })\n\n points.forEach((p, i) => {\n let min = {}\n centroids.forEach((c, j) => {\n if(j === 0) {\n min.centroid = c\n min.distance = distance(c, p)\n }\n const newDistance = distance(c, p)\n if (min.distance > newDistance) {\n min.centroid = c\n min.distance = newDistance\n }\n })\n \n min.centroid.variance += min.distance\n min.centroid.points.push(p)\n })\n \n centroids.forEach(c => c.variance /= c.points.length)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1808,"value":"random = (points, k) => {\n if(k < 0 || k > points.length) return\n const set = new Set()\n do {\n set.add(Math.floor(Math.random() * points.length))\n } while(set.size < k)\n return Array.from(set).map(i => points[i])\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1811,"value":"centroid = (points) => points.length === 0 ? [] :\n points\n .reduce((a, b) => b.map((p, i) => a[i] + p)) // summs up each dimention\n .map(p => Math.floor(p / points.length)) // divides each dimention sum by the vector length","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1816,"value":"kmeans = (points, k, centroids, maxIterations = 25, tolerance = 3) => {\n if (!centroids) centroids = random(points, k)\n\n assign(centroids, points)\n \n let moved = true\n let iterations = 0\n \n while(moved && iterations < maxIterations) {\n iterations++\n moved = false\n \n for (let i = 0; i < centroids.length; i++) {\n const newCentroid = centroid(centroids[i].points)\n if (distance(centroids[i], newCentroid) > Math.pow(tolerance, 2)) {\n moved = true\n centroids[i] = newCentroid\n }\n }\n\n if (moved) assign(centroids, points)\n }\n \n return {\n centroids: centroids,\n iterations: iterations\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1775,"value":"samples = {\n const step = Math.floor(matrix.length / seedSize)\n const seed = []\n \n const points = matrix.map(p => {\n const result = [p.rgba.r, p.rgba.g, p.rgba.b]\n result.point = p\n return result\n })\n \n for (let i = 0; i < points.length; i += step) {\n seed.push(points[i])\n }\n \n const results = []\n \n for (let k = 1; k <= 20; k++) {\n const centroids = kmeans(seed, k).centroids\n results.push({\n k: k,\n centroids: centroids,\n variance: centroids.map(c => c.variance).reduce((a, b) => a + b, 0) / k\n })\n }\n\n return results\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1591,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1701,"value":"md`Now put this all together:\n1. Take a sample data set.\n2. Find centroids for different k on the sample data set.\n3. Find from which k the variance slows down its decrease.\n4. Run the k-means clustering with given initial centroids on the full data set.\n\nVoilà:`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1778,"value":"result = {\n let minimum = samples[0]\n \n for (let i = 1; i < samples.length; i++) {\n if (minimum.variance - samples[i].variance < 256) {\n i = samples.length\n }\n else {\n minimum = samples[i]\n }\n }\n \n return kmeans(points, minimum.k, minimum.centroids)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1594,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1703,"value":"md`The big circles represent centroids. The bigger a circle, the more data points are assigned to this centroid.\n\nAnd the posterized image:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1597,"value":"{\n const context = DOM.context2d(imageData.width, imageData.height, 1)\n const canvas = context.canvas\n\n const imageData2 = context.getImageData(0, 0, imageData.width, imageData.height)\n \n const centroids = result.centroids\n \n for(let i = 0; i < imageData.data.length; i += 4) {\n const rgb = [imageData.data[i], imageData.data[i + 1], imageData.data[i + 2]]\n \n const closest = {\n centroid: centroids[0],\n distance: distance(rgb, centroids[0])\n }\n \n for (let i = 1; i < centroids.length; i++) {\n const _distance = distance(rgb, centroids[i])\n if (_distance < closest.distance) {\n closest.centroid = centroids[i]\n closest.distance = _distance\n }\n }\n\n imageData2.data[i] = closest.centroid[0]\n imageData2.data[i + 1] = closest.centroid[1]\n imageData2.data[i + 2] = closest.centroid[2]\n imageData2.data[i + 3] = 255\n }\n \n context.putImageData(imageData2, 0, 0)\n \n return canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1600,"value":"md`## P.S:\nYou may also like these articles, which I found before publishing this notebook:\n\n- [Dominant colors in an image using k-means clustering](https://buzzrobot.com/dominant-colors-in-an-image-using-k-means-clustering-3c7af4622036)\n\n- [Building a way to search photos by colour](https://medium.com/unsplash/building-a-way-to-search-photos-by-colour-d0531bd5a49b)\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 33:"$32:body"