After making my new smart fabric, I’m successfully turning leather into a touch panel. So right now I can get the raw data and translate them into my point matrix!

According to unknown confidentiality agreement, I better not put any picture here. I would just talk about real-time k-means algorithm for 2 dimension points.

And here is the problem: every time you touch the fabric, it light up 1 to 9 point in my matrix. For one finger it’s totally fine, but for multi-touch, I need to figure out where exactly my fingers are. To do this, I need to assign every point to it’s finger. Here I need clustering analysis, I choose k-means clustering algorithm (wiki).

Let’s code it in JavaScript! Here is the tutorial I found.

Here is the quick explanation:

- Randomly assign a position of each finger.
- Assign every point to it’s closest finger position.
- Change position of finger to the centroid of each group.
- Repeat step 2 and 3 until the position stop change.

But K-means is not a high efficiency algorithm, there’s a lot of calculating. In the original algorithm, if there’s any group have not point inside, it’ll get a new randomly position. But here we’re trying to detect fingers, the position is predictable. I set default positions into different corners, so in most cases, the calculating loop would stop within 2 times. (Notice: for real time calculating, if your computer is not fast enough or your matrix is too large, this might be a bad solution.)

function kmeans(comingPoints) { data = comingPoints; dataExtremes = getDataExtremes(data); dataRange = getDataRanges(dataExtremes); run(); }

Create a function and call it every time I receive new data;

function makeAssignments() { assignments = []; for (var i in data) { var OnePoint = data[i]; var distances = []; for (var j=0; j<kPoints;j++) { var mean = means[j]; var sum = 0; for (var dimension in OnePoint) { var difference = OnePoint[dimension] - mean[dimension]; difference *= difference; sum += difference; } distances[j] = Math.sqrt(sum); } assignments[i] = distances.indexOf( Math.min.apply(null, distances) );///return closest mean point index } }

In this function, assign every point into a group.

function moveMeans() { makeAssignments(); var sums = []; var counts = []; var moved = false; for (var j=0; j<kPoints; j++) { counts[j] = 0; sums[j] = []; for (var i=0; i<2; i++) { sums[j][i] = 0; } } for (var point_index in assignments) { var mean_index = assignments[point_index]; var OnePoint = data[point_index]; var mean = means[mean_index]; counts[mean_index]++; for (var i=0; i<2; i++){ sums[mean_index][i] += OnePoint[i]; } } for (var i=0; i<kPoints; i++) { if ( 0 === counts[i] ) { sums[i]= defaultMeans[i]; //If it didn't have any points assigned to it, give it a new position in the conner. continue; } for (var dimension=0 ; dimension<2; dimension++) { sums[i][dimension] /= counts[i]; } } if (means.toString() !== sums.toString()) { moved = true; //if centroid stop changing, stop loop } means = sums; return moved; }

Here we calculating centroid of each group and loop until stop changing.

function run() { var moved = moveMeans(); if (moved) { setTimeout(run,1); } else { //send result here waitForCalculating = false; //allow new calculating loop start } }

Run() function checks to see if the algorithm has stopped. Here Arduino sends data every 100ms, call kmeans() function before last calculating finished would cause error or wrong result. So here I create a boolean variable to prevent that.