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:

kmeansViz

  1. Randomly assign a position of each finger.
  2. Assign every point to it’s closest finger position.
  3. Change position of finger to the centroid of each group.
  4. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *