---
layout: post
title: "K Pix: Inks/Pixels"
categories: [Hacking]
tags: [Software, _Phase4]
---

<figure class="align-center">
	<canvas width="390" height="266" id="km_sample4" class="align-center">
	</canvas>
  <figcaption id='stats4'>Reduced colors</figcaption>
</figure> 
<button id="reloader" onclick="kmSample4.update_pic_src();" class="btn--primary align-center">Press for a Different Random Photo</button>

<script>
	var kmSample4 = {
		m: null,
		canvas: null,
		ctx: null,
		iter: 0,
		srcImage: null,
		imSize: {x:128,y:128},
		paused: false,
		pinBW: true,
		pxls: null,
		stats: null,
		histo: new Array(256), // how many pixels ahve this value
		member: new Array(256), // for any gra value, what's the "owning" mean (as index into "this.m[]")
		mapped: new Array(256),
		placeHolderURLs: ['https://loremflickr.com/g/128/128/vespa,scooter','https://picsum.photos/g/128/128/?random',"https://www.fillmurray.com/128/128"],
		//
		sat_random_color: function() {
			// returns some strong color. We consider RG&B to be evenly-tempered, no perceptual hijinks
			var c = [Math.random(), Math.random(), Math.random()];
			var v = Math.max.apply(Math,c);
			c = c.map(function(x) { return Math.min(1.0, x/v);});
			var v = 1.0 - Math.min.apply(Math,c);
			c = c.map(function(x) { return Math.max(0.0, (1.0-x)/v);});
			c = c.map(function(x) { return Math.min(255, Math.floor(255*x));});
			return c;
		},
		init_sample_data: function(nMeans) {
			// let's randomly place a few mean candidates
			this.m = [];
			for (var i=0; i<nMeans; i=i+1) {
				var cv = this.sat_random_color(); // for our mean markers
				var fv, pin;
				if (this.pinBW && (i>=(nMeans-2))) {
					fv = (i==(nMeans-1))?255:0;
					pin = true;
				} else {
					fv = 256*Math.random();
					pin = false;
				}
				var iv = Math.floor(fv);
				this.m.push({
					v: fv,
					i: iv,
					cv: cv,
					c: ('rgb('+cv.join(',')+')'),
					active: true,
					pinned: pin
				});
			}
		},
		distance1D: function(v,m) {
			// distance between a pixel value and a mean.
			return Math.abs(v-m.v);
		},
		padz: function(n, width, z) {
		  z = z || '0';
		  n = n + '';
		  return n.length >= width ? n : new Array(width - n.length + 1).join(z) + n;
		},
		draw_pic: function(x,y) {
			if (this.pxls != null) {
				this.ctx.putImageData(this.pxls, x, y);
			} else {
				this.ctx.drawImage(this.srcImage, x,y); // , this.imSize.x,this.imSize.y);
			}
		},
		draw_histo: function(x,y) {
			var i;
			for (i=0; i<this.m.length; i+=1) {
				var m = this.m[i];
				if (!m.active) {
					continue;
				}
				if (!this.m[i].pinned) {
					this.ctx.strokeStyle = m.c;
					var xx = ((255-m.i)+x);
					this.ctx.beginPath();
					this.ctx.moveTo(xx,y);
					this.ctx.lineTo(xx,y+256);
					this.ctx.stroke();
				}
			}
			var g = this.ctx.createLinearGradient(x, y, x+256, y);
			g.addColorStop(1, '#101010ff');
			g.addColorStop(0, '#e0e0e0ff');
			this.ctx.fillStyle='black';
			this.ctx.strokeStyle=g;
			for (i=0; i<256; i+=1) {
				this.ctx.beginPath();
				this.ctx.moveTo((255-i)+x, y+256);
				this.ctx.lineTo((255-i)+x, y+256-this.histo[i]);
				this.ctx.stroke();
			}
		},
		draw_points: function(x0,y0) {
			var i, j, p, x, y;
			for (i=0; i<256; i+=1) {
				this.mapped[i] = this.m[this.member[i]].i;
			}
			for (j=0; j<this.pxls.data.length; j+=4) {
				p = this.pxls.data[j];
				p = this.mapped[p];
				this.result.data[j] = p;
				this.result.data[j+1] = p;
				this.result.data[j+2] = p;
				this.result.data[j+3] = 255;
			}
			this.ctx.putImageData(this.result, x0, y0);
		},
		update_canvas: function() {
			// draw points AND means
			this.ctx.fillStyle = 'white';
			this.ctx.fillRect(0,0,this.canvas.width,this.canvas.height)
			this.draw_pic(0,0);
			this.draw_points(0,128);
			this.draw_histo(128,0);
		},
		update_memberships: function() {
			// update points, to see if any have switched affiliations. Return a count of
			//     how many have changed.
			var ip, im;
			var nChanged = 0;
			for (ip=0; ip<256; ip=ip+1) {
				var dBest = 2000; // some large value beyond our 256-value range
				var mBest = null;
				for (im=0; im<this.m.length; im=im+=1) {
					if (!this.m[im].active)
						continue;
					var dm = Math.abs(ip - this.m[im].v);
					if (dm<dBest) {
						dBest = dm;
						mBest = im;
					}
				}
				if (mBest != this.member[ip]) {
					nChanged += 1;
					this.member[ip] = mBest;
				}
			}
			// console.log(nChanged+' changed');
			return(nChanged);
		},
		update_centroids: function() {
			// update mean locations (ignore inactive ones)
			var ip, im, n, c;
			for (im=0; im<this.m.length; im+=1) {
				if (!this.m[im].active)
					continue;
				n = 0;
				c = 0;
				for (ip=0; ip<256; ip+=1) {
					if (this.member[ip] == im) {
						n += this.histo[ip];
						c += ip*this.histo[ip];
					}
				}
				if (n==0) { // set is EMPTY - can be discarded
					if (!this.m[im].pinned) {
						this.m[im].active = false;
					}
					// console.log("mean "+im+' has no membership, value '+this.m[im].i);
				} else { // move to centroid of member points
					if (!this.m[im].pinned) {
						this.m[im].v = c/n;
						this.m[im].i = Math.floor(this.m[im].v);
					}
				}
			}
			this.update_stats();
		},
		update_stats: function() {
			if (!this.stats) {
				this.stats = document.getElementById('stats4');
			}
			var i, c;
			for (i=0,c=0; i<this.m.length; i+=1) {
				if (this.m[i].active) c += 1;
			}
			text = (this.pinBW) ? ((c-1).toString()+' <b>inks:</b>') : (c.toString()+' colors:');
			var actives = [];
			for (i=0; i<this.m.length; i+=1) {
				if (this.m[i].active) {
					actives.push(this.m[i].i);
				}
			}
			actives.sort(function(a,b){return b-a;});
			for (i=0; i<actives.length; i+=1) {
				if ((!this.pinBW) || (actives[i]!=255)) {
					var ink = (actives[i] == 0) ? '&amp; black' : (Math.floor((100*(255-actives[i])/255)).toString()+'%,');
					text = text+' '+ink;
				}
			}
			this.stats.innerHTML = text;
		},
		update_all: function() {
			// our complete method -- just loop on this until you don't
			var m = this.update_memberships();
			if (m > 0) {
				this.update_centroids();
			}
			return(m);
		},
		remove_one: function() {
			// randomly remove a mean, until we reach some minimum
			var i, ct;
			for (i=0; i<this.m.length; i+=1) {
				if (this.m[i].active) {
					if (!this.m[i].pinned)
						this.m[i].active = false;
					break;
				}
			}
			for (i=0, ct=0; i<this.m.length; i+=1) {
				if (this.m[i].active) {
					ct += 1;
				}
			}
			return (ct > 2);
		},
		looper: function(timestamp) {
			// called by requestAnimationFrame() forever
			if (this.paused) {
				window.requestAnimationFrame(this.looper.bind(this));
				return;
			}
			var ch = this.update_all();
			this.update_canvas();
			if (ch > 0) {
				window.requestAnimationFrame(this.looper.bind(this));
			} else if (this.remove_one()) {
				window.setTimeout(this.looper.bind(this),2000);
			} else {
				window.setTimeout(this.startup.bind(this),4000);
			}
			this.iter += 1;
		},
		startup: function() {
			// also called whenever we re-start
			this.init_sample_data(6+Math.floor(6*Math.random()));
			this.iter = 0;
			window.requestAnimationFrame(this.looper.bind(this));
		},
		collect_gray_pixels: function(context,x0,y0,w,h) {
			var i;
			this.pxls = context.getImageData(x0,y0,w,h);
			this.result = context.createImageData(w, h);
			// but we only care about the gray, so
			var grayscale = function(ctx,rgba) {
				var data = rgba.data;
			    for (var i = 0; i < data.length; i += 4) {
			      var avg = (data[i] + data[i + 1] + data[i + 2]) / 3;
			      data[i]     = avg; // red
			      data[i + 1] = avg; // green
			      data[i + 2] = avg; // blue
			    }
			    ctx.putImageData(rgba, 0, 0);
			  };
			grayscale(context,this.pxls);
			// preparing a histogram will make later calculations faster
			for (i=0; i< 256; i+=1) {
				this.histo[i] = 0;
				this.member[i] = null; // for each gray value, which is the closest mean?
			}
			for (i=0; i<this.pxls.data.length; i+=4) {
				//var v = (this.pxls.data[i] + this.pxls.data[i+1] + this.pxls.data[i+2])/3;
				var v = this.pxls.data[i];
				this.histo[ v ] += 1;
			}
		},
		init_pic_from_image: function() {
			if (!this.srcImage) {
				this.srcImage = document.getElementById('gray4');
			}
			this.imSize.x = this.srcImage.width;
			this.imSize.y = this.srcImage.height;
			var srcCanv = document.createElement('canvas');
			srcCanv.width = this.imSize.x;
			srcCanv.height = this.imSize.y;
			var srcCtx = srcCanv.getContext('2d');
			srcCtx.drawImage(this.srcImage, 0,0);
			this.collect_gray_pixels(srcCtx,0,0,this.srcImage.width,this.srcImage.height);
		},
		toggle_pause: function() {
			// user can click to stop/start the animation
			this.paused = ! this.paused;
		},
		main: function(canvID,srcImg) {
			this.canvas = document.getElementById(canvID);
			var p = this.canvas.parentElement;
			if (p.offsetWidth < (this.canvas.width-4)) {
				this.canvas.width = p.offsetWidth - 4;
			}
			this.ctx = this.canvas.getContext('2d');
			this.canvas.onclick = this.toggle_pause.bind(this);
			this.init_pic_from_image();
			this.startup();
		},
		update_pic_src: function() {
			if (this.srcImage) {
				console.log("reload");
				var env = "{{ jekyll.environment }}";
				this.srcImage.src = (env == 'development') ? "/img/misc/c-scoot.jpg" : ('https://picsum.photos//128/128/?random&junk='+new Date().getTime());
			} else {
				console.log("button pressed too soon?");
			}
		},
		begin: function() {
			// load an interesting pic
			this.srcImage = new Image();
			this.srcImage.setAttribute('id','gray4');
			this.srcImage.setAttribute('crossOrigin','anonymous');
			this.srcImage.onload = function() {
				this.main("km_sample4");
			}.bind(this);
			this.update_pic_src();
		}
	};
	kmSample4.begin();
</script>

_Part of a brief series that started [here.]({{ site.baseurl}}{% post_url 2018-12-05-K-Means %})_
{: .notice--info}

How can we use [_k-Means_]({{ site.baseurl}}{% post_url 2018-12-05-K-Means %}) to understand and/or manipulate photographic images? As a first example, here's a classic from the poster-printing world: choosing a very small number of inks to represent a full-tone photo.

In our example, we grab random photos from the web -- some work great as posters, some... not so much. But the code will do its best given the narrow constraints: all it knows is grayscale values, and we've reduce our calculation to just one dimension: the values along the grayscale histogram from each picture.
<!--more-->
### The Idea

As described in previous posts, _k-Means_ is a [surprisingly simple method]({{ site.baseurl}}{% post_url 2018-12-05-K-Means %})  for discovering "clumps" of information from any source -- even if the clumps are subtle and hard to spot with the naked eye. Basically you just guess, evaluate your guesses, and keep refining them over and over until it's Just Right.

While _not_ mentioned in earlier posts, k-Means is often considered a kind of _machine learning:_ meaning that if you've understood a little of the previous posts, you already have an interesting bit of ML under your belt; an ML flavor rather different from what the media typically describes as "AI."

Most of the big ML successes in recent products like Google's Pixel Lens or Apple's Siri come from what's known as _supervised_ learning: that is, there is a predefined teacher who knows the right answers for some very specific problem, and then supervises the computer until it can solve problems on its own. Computers can learn by repeating lessons over and over again, if the teacher can give them enough quiz questions.

Simple example: If you show a computer 1,000,000 pictures, and every time there are Lego blocks shown in one of those pictures, you label it "Lego," then after a lots of trial and error the computer may learn to label Lego (and non-Lego) pictures all by itself.

The hard part, of course, is that _first_ you need to find a million pictures, carefully and correctly labelled for Legos (and also many that you know are "not Legos," becasue the task isn't "find the Legos in this picture," it's "tell me: is there a Lego in this picture?"), and have all those labelled pictures handy somewhere on your hard drive. That's before you even begin.

ML-savvy readers might point out that if we're seeking only _one_ category, "Legos," maybe only several thousand pictures are needed. Fair enough. Do you have them ready? How much time do you think it will take to find even those? Supervised learning always requires a lot of potentially-laborious supervision up front.

Another different class of methods, and k-Means is on the fringe of this camp, are called <i>UN</i>supervised learning, where we don't need a teacher. Instead, the computer can learn something by itself, based only on the information at hand.

In this case, we want it to figure out what inks to use for printing a poster of a _specific_ picture if our print process only has, say, three or four inks, as in silk-screen or hand-press printing.

---

### The Example Code

As before, you can stop/start the sample by clicking on the sample area.

Also as before, we let the guessed means move around until they're stable, then randomly take one mean away.

One of the color means doesn't move: it's always pinned to K=100%, aka **black.**

A nice characteristic of this method is that it doesn't actually do its calculations directly on the pixels: that would be slow. Instead, we just look at the image histogram, which only has 256 levels to compare, rather than the 16384 pixels of even these little sample pictures.

No matter how large your B&amp;W input image might be, if it's an 8-bit picture it still only has 256 gray levels, and so the ink-finder is just as fast regardless of picture dimensions. The only "slow" parts just need be done once: the histogram collection, and then the final remapping of output display pixels. The "learning" passes are very fast.

This example figures out inks for each single, specific picture. The four inks for a light-toned picture may be inappropriate for a darker picture. But the ones k-Means selects for any individual picture will tend to be exactly the ones that give you great separation of the active tones of the shot.

It's also possible that for very narrow-toned photos, k-Means can even select fewer inks than you might have originally thought you needed. Rare but possible.

All the Javascript code for the sample lives right here in the HTML - no squirrely extra libraries. Hit "View Page Source" in your browser, or look [here on GitHub.](https://raw.githubusercontent.com/joker-b/botzo/master/_posts/2018-12-10-K-Pix.md) All sample code is saved in a single module called `kmSample4`

To experiment on your own, consider making the criteria for ink-reduction "looser" -- currently an ink might persist in the list even if it's only printed for a single pixel. Is there a better criterion?