The Microsoft Kinect SDK provides some really interesting opportunities to program rich, interactive applications. Berico Technologies recently hosted a great "Hack Day" where we tested out some concepts on a few recently acquired Kinects. In this article, I'll present an extension I cobbled together for the "Skeleton Viewer" sample solution--given Kinect's surprisingly good "joint tracking" abilities, I thought--what if we could predict the movement of someone's body parts based on accumulated knowledge about their trajectories?

 The lines flowing out of each joint correspond to a prediction: the JointPrediction project implements a streamlined exponentially weighted moving average on average velocities to predict an X Y Z vector corresponding to where we think each joint is headed in the next few seconds. I'll go through all of the math and the implementation in this post.

You can download the source at Codeplex.

Special thanks to John Ruiz and Robert Levy for their help!

Exponentially Weighted Moving Averages (EWMAs)

EWMAs are essentially schemes that allow us to keep a moving average of some streaming data while giving us fairly fine grained control over how volatile the moving average. Through the use of a decay constant that represents the half-life of the impact of a particular observation, we can make adjustments to just how much weight old observations will have on the current value of the moving average.

With different weights on the EWMA, you can see that the moving average can be very "stable" or it can hug the actual points very closely. The idea here is to adopt the same formula to joint movement in three dimensions (X,Y,Z) -- plus time -- and display a moving average of the joint as a predictor for the future placement of a joint in space. We will do this by modeling the EWMA of velocity.

Modeling observation and velocity

We start with two simple classes. The first tracks an observation of a joint at a discrete moment in time:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RedOwlConsulting.JointPrediction
{
    public class Observation
    {
        /// <summary>
        /// Horizontal component
        /// </summary>
        public double X { get; set; }
        /// <summary>
        /// Vertical component.
        /// </summary>
        public double Y { get; set; }
        /// <summary>
        /// Depth component.
        /// </summary>
        public double Z { get; set; }
        /// <summary>
        /// Time of the observation
        /// </summary>
        public DateTime DateTime { get; set; }

        /// <summary>
        /// Time elapsing since some past observation, in seconds
        /// </summary>
        /// <param name="pastObservation">A observation occurring in the past. Future observations will return negative numbers.</param>
        /// <returns>Elapsed time</returns>
        public double TimeElapsed(Observation pastObservation)
        {
            return (DateTime - pastObservation.DateTime).TotalSeconds;
        }

        /// <summary>
        /// Computes the approximate/average velocity between the past observation and the current observation.
        /// </summary>
        /// <param name="pastObservation"></param>
        /// <returns></returns>
        public Velocity ApproximateVelocity(Observation pastObservation)
        {
            double timeElapsed = TimeElapsed(pastObservation);
            return new Velocity { 
                X = (X - pastObservation.X) / timeElapsed, 
                Y = (Y - pastObservation.Y) / timeElapsed,
                Z = (Z - pastObservation.Z) / timeElapsed,
                DateTime = this.DateTime };
        }

        /// <summary>
        /// Used for debugging.
        /// </summary>
        /// <returns>A string printing the object</returns>
        public override string ToString()
        {
            return String.Format("{0:0.000} {1:0.000} {2:0.000} {3}", X, Y, Z, DateTime);
        }
    }
}

As you will note, the ApproximateVelocity function calculates average velocity in the usual way. Here's what the velocity class looks like:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RedOwlConsulting.JointPrediction
{
    /// <summary>
    /// This class is responsible for storing rates of movement on X Y Z coordinates, as well as the date time of calculation.
    /// </summary>
    public class Velocity
    {
        /// <summary>
        /// Horizontal component.
        /// </summary>
        public double X { get; set; }
        /// <summary>
        /// Vertical component.
        /// </summary>
        public double Y { get; set; }
        /// <summary>
        /// Depth component
        /// </summary>
        public double Z { get; set; }

        /// <summary>
        /// Timestamp of the calculated velocity
        /// </summary>
        public DateTime DateTime { get; set; }

        /// <summary>
        /// Used for debugging
        /// </summary>
        /// <returns>String of X Y Z datetime</returns>
        public override string ToString()
        {
            return String.Format("{0:0.000} {1:0.000} {2:0.000} {3}", X, Y, Z, DateTime);
        }
    }
}

Predicting Future Points with Average Velocity

Now that we have two classes to deal with modeling points in space-time and their velocity, we can move on to calculating EWMAs on-line. We do this with the following class:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RedOwlConsulting.JointPrediction
{
    /// <summary>
    /// A class which is responsible for predicting future movement based on past movement using an online algorithm
    /// for calculating exponentially weighted moving averages of velocity along three dimensions in space.
    /// </summary>
    public class JointPredictor
    {
        /// <summary>
        /// Stores the last observation to be ingested by the online algorithm
        /// </summary>
        Observation lastObservation;
        /// <summary>
        /// Stores the current value of the exponentially weighted moving average velocity
        /// </summary>
        public Velocity EwmaVelocity { get; private set; }
        /// <summary>
        /// Stores the decay constant to be used by the algorithm. Larger (+) values mean that past observations have much
        /// less sway over the current EwmaVelocity value. Values close to zero mean that past observations will have a
        /// lingering effect.
        /// </summary>
        public Double DecayConstant { get; set; }

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="decay">Value of the decay constant</param>
        public JointPredictor(double decay)
        {
            DecayConstant = decay;
        }

        /// <summary>
        /// Update ingests a new observation an is responsible for calculating, online, the update to the EwmaVelocity
        /// based on the new observation.
        /// </summary>
        /// <param name="newObservation">The new observation.</param>
        public void Update(Observation newObservation)
        {
            if (lastObservation == null)
            {
                lastObservation = newObservation;
                EwmaVelocity = new Velocity { X = 0, Y = 0, Z = 0, DateTime = lastObservation.DateTime };
            }
            else
            {
                Velocity currentVelocity = newObservation.ApproximateVelocity(lastObservation);
                double timeElapsed = newObservation.TimeElapsed(lastObservation);
                double decay = Math.Exp(-1 * DecayConstant * timeElapsed);
                EwmaVelocity.X = (1 - decay) * EwmaVelocity.X + decay * currentVelocity.X;
                EwmaVelocity.Y = (1 - decay) * EwmaVelocity.Y + decay * currentVelocity.Y;
                EwmaVelocity.Z = (1 - decay) * EwmaVelocity.Z + decay * currentVelocity.Z;
                EwmaVelocity.DateTime = currentVelocity.DateTime;
                lastObservation = newObservation;
            }
        }

    }
}

The Update function is responsible for calculating the EWMA pair-wise on the X, Y, and Z coordinates. You'll notice the familiar EWMA formula in the body!

Wiring JointPrediction into the Skeleton Viewer

The Skeleton Viewer sample solution ships with the Kinect SDK. Since it provides a great platform to build on for our purposes, we will simply hack the EwmaVelocity as a vector onto the "Skeleton Screen" whenever a joint's position is updated. In the MainWindow.xaml.cs, add the following dictionary:

Dictionary<JointID, JointPredictor> jointPredictor = new Dictionary<JointID, JointPredictor>();

Note that we are tracking the joints for only a single skeleton (strange things WILL happen if you try this out with another person in Kinect's vision!). An interesting addition to the project would be to add an index to this dictionary for another skeleton.

Within the function SkeletonFrameReady. You'll see essentially two loops. The first is over the SkeletonData, which corresponds to an object for an identified skeleton/person concept (e.g. if there are two people in the view of Kinect, there will be two SkeletonData objects available). For each SkeletonData, there is a collection Joints, which is also looped over. Within this loop, we add some logic to update our JointPredictors. Once the JointPredictors are updated, we then draw a line:

void nui_SkeletonFrameReady(object sender, SkeletonFrameReadyEventArgs e)
        {
            foreach (SkeletonData data in skeletonFrame.Skeletons)
            {
                if (SkeletonTrackingState.Tracked == data.TrackingState)
                {

                    // Draw bones ...
                    // Draw joints
                    foreach (Joint joint in data.Joints)
                    {
                        // ...

                        // If the jointPredictor entry is not yet initialized, do it
                        if (!jointPredictor.Keys.Contains(joint.ID))
                        {
                            jointPredictor.Add(joint.ID, new JointPredictor(20F));
                        }

                        // Ingest the new observation using the current position of the joint
                        Observation obs = new Observation
                        {
                            X = data.Joints[joint.ID].Position.X,
                            Y = data.Joints[joint.ID].Position.Y,
                            Z = data.Joints[joint.ID].Position.Z,
                            DateTime = DateTime.Now
                        };
                        jointPredictor[joint.ID].Update(obs);

                        // Create a line for the predicted direction of motion
                        Line direction = new Line();
                        Point displayPosition = getDisplayPosition(data.Joints[joint.ID]);

                        direction.Stroke = jointColors[joint.ID];
                        direction.StrokeThickness = 10;
                        
                        // These points correspond to the X Y planar projection of the velocity.
                        direction.X1 = displayPosition.X;
                        direction.Y1 = displayPosition.Y;
                        direction.X2 = direction.X1 + jointPredictor[joint.ID].EwmaVelocity.X * 25;
                        direction.Y2 = direction.Y1 - jointPredictor[joint.ID].EwmaVelocity.Y * 25;

                        // Add the line to the GUI
                        skeleton.Children.Add(direction);
                    }
                }
                iSkeleton++;
            } // for each skeleton
        }

The result is what we get in the demo video above. There are lots of great extensions to this general idea to think about--different weighting schemes, fitting probability distributions onto the joints that can take into account uncertainty/variance and of dependencies between the joints. It would be neat to take this technique and attempt to find "tells" for penalty kicks--which side does a person choose to kick based on some trends for their movements? Can this help a goalie to pick the right side?

Thats it! Kinect SDK is a great way to program for fun. Check out Code4fun for some more cool ideas.