DTW(DynamicTimingWarping)

王者再临

可以用于kinect 的手势识别算法

* 本算法为DWT算法
* 输入: 两个时间序列矢量 A(a1,a2,a3,...an) B(b1,b2,b3,...bn)
* 输出: 一个关于两个序列矢量匹配度的数值
* 处理过程: 动态规划算法找最优解
* 原理:对于两个具有相同或相似特征的时间序列矢量元素其距离(欧几里得)之和最短

使用方法 ：（1）收集骨骼位置数据，如果用来手势识别 则可以取 Hand,Wrist,elbow 等位置（格式如下所示）
                          @gesturename36.9032810/24/2014                      手势名      
                             -0.0331086702644825                                       数据
                             -0.167759731411934
                             -0.206393882632256
                             -0.159131124615669
                             -0.856702625751495
                             -0.352049857378006
                             0.716807723045349
                            -0.580063939094543
                             1.17411589622498
                            -0.553598940372467
                           1.27646732330322
                           -0.494788020849228
                            ----
                  (2)使用 DynamicTimingWarping.Instance.LoadGesturesFromFile(file);                                           加载要识别的序列帧数据
                        Skeleton2DDataExtract.ProcessData(bodyData);                                                                    将每帧的数据加入
                        Skeleton2DDataExtract.Skeleton2DdataCoordReady += Skeleton2DdataCoordEventHandler;     获得一帧数据后的事件
                       DynamicTimingWarping.Instance.Recognize(arg.GetCoords())                                                  得到识别结果字符串

public class DynamicTimingWarping
{
        private static DynamicTimingWarping _instance;
        private readonly int _dimension;
        private readonly double _firstThreshold;
        private readonly double _minimumLength;
        private readonly double _globalThreshold;
        private readonly List<string> _labels;
        private readonly int _maxSlope;
        private List<List<double>> _sequences;
        public Dictionary<string, List<double>> sequencepairs = new Dictionary<string, List<double>>();
        public static DynamicTimingWarping Instance
    {
        get
        {
            if (_instance != null)
            {
                return _instance;
            }
            else
            {
                _instance = new DynamicTimingWarping(12,0.6,2,2,10);
            }
            return _instance;
        }
    }
        public void LoadGesturesFromFile(string fileLocation)
    {
        int    itemCount = 0;
        string line;
        string gestureName =  String.Empty;
        List<double> frames = new List<double>();
        System.IO.StreamReader file = new System.IO.StreamReader(fileLocation);
        while ((line = file.ReadLine()) != null)
        {
            if (line.StartsWith("@"))
            {
                gestureName = line;
                continue;
            }
            if (line.StartsWith("~"))
            {  
                continue;
            }
            if (!line.StartsWith("----"))
            {   
                frames.Add(Double.Parse(line));
            }
            itemCount++;
            if (line.StartsWith("----"))
            {
                AddOrUpdate(frames, gestureName);
                frames = new List<double>();
                gestureName = String.Empty;
            }
        }
        file.Close();
    }
           
        public DynamicTimingWarping(int dim, double threshold, double firstThreshold, int ms, double minLen)
        {
            _dimension = dim;
            _sequences = new List<List<double>>();
            _labels = new List<string>();
            _globalThreshold = threshold;
            _firstThreshold = firstThreshold;
            _maxSlope = ms;
            _minimumLength = minLen;
        }
     
        public void AddOrUpdate(List<double> seq, string lab)
        {
            if (!sequencepairs.ContainsKey(lab))
            {
                 _sequences.Add(seq);
                 _labels.Add(lab);
                 sequencepairs.Add(lab, seq);
                 NGUIDebug.Log("手势数据添加成功 +1" + "名称 :" + lab);
            }
        }
        public string Recognize(List<double> seq)
        {
            double minDist = double.PositiveInfinity;
            string classification = "未知手势";
            for (int i = 0; i < _sequences.Count; i++)
            {     
                if (Dist2(seq,_sequences) < _firstThreshold)
                {
                    double d = Dtw(seq, _sequences) / _sequences.Count;
                    if (d < minDist)
                    {
                        minDist = d;
                        classification = (string)_labels;
                    }
                }
            }
            return (minDist < _globalThreshold ? classification : "未知手势");
        }
      
        public string RetrieveText()
        {
            string retStr = String.Empty;
            int    count = 0;
            if (_sequences != null)
            {
                foreach (List<double> gusture in _sequences)
                {
                    retStr += _labels[count++] + "\r\n";
                    foreach (double db in gusture)
                    {
                        retStr += db + "\r\n";
                    }
                    retStr += "----";
                    if (count < _sequences.Count - 1)
                    {
                        retStr += "\r\n";
                    }
                }
            }
            return retStr;
        }
      
        public double Dtw(List<double> seq1R,List<double> seq2R)
        {
            var tab = new double[seq1R.Count + 1, seq2R.Count + 1];
            var slopeI = new int[seq1R.Count + 1, seq2R.Count + 1];
            var slopeJ = new int[seq1R.Count + 1, seq2R.Count + 1];
            for (int i = 0; i < seq1R.Count + 1; i++)
            {
                for (int j = 0; j < seq2R.Count + 1; j++)
                {
                    tab[i, j] = double.PositiveInfinity;
                    slopeI[i, j] = 0;
                    slopeJ[i, j] = 0;
                }
            }
            tab[0, 0] = 0;
            for (int i = 1; i < seq1R.Count + 1; i++)
            {
                for (int j = 1; j < seq2R.Count + 1; j++)
                {
                    if (tab[i, j - 1] < tab[i - 1, j - 1] && tab[i, j - 1] < tab[i - 1, j] &&
                        slopeI[i, j - 1] < _maxSlope)
                    {
                        tab[i, j] = Dist21(seq1R[i - 1], seq2R[j - 1]) + tab[i, j - 1];
                        slopeI[i, j] = slopeJ[i, j - 1] + 1;
                        slopeJ[i, j] = 0;
                    }
                    else if (tab[i - 1, j] < tab[i - 1, j - 1] && tab[i - 1, j] < tab[i, j - 1] &&
                             slopeJ[i - 1, j] < _maxSlope)
                    {
                        tab[i, j] = Dist21(seq1R[i - 1],seq2R[j - 1]) + tab[i - 1, j];
                        slopeI[i, j] = 0;
                        slopeJ[i, j] = slopeJ[i - 1, j] + 1;
                    }
                    else
                    {
                        tab[i, j] = Dist21(seq1R[i - 1], seq2R[j - 1]) + tab[i - 1, j - 1];
                        slopeI[i, j] = 0;
                        slopeJ[i, j] = 0;
                    }
                }
            }
            double bestMatch = double.PositiveInfinity;
            for (int i = 1; i < (seq1R.Count + 1) - _minimumLength; i++)
            {
                if (tab[i, seq2R.Count] < bestMatch)
                {
                    bestMatch = tab[i, seq2R.Count];
                }
            }
            return bestMatch;
        }
        private double Dist2(List<double> a, List<double> b)
        {
            double d = 0;
            for (int i = 0; i < _dimension; i++)
            {
                d += Math.Pow(a - b, 2);
            }
            return Math.Sqrt(d);
        }
        private double Dist21(double a,double b)
        {
            return  Mathf.Sqrt((float)Math.Pow(a-b,2));
        }
}

class Skeleton2DDataExtract
    {
        public delegate void Skeleton2DdataCoordEventHandler(object sender,BodydataCoordEventArgs a);
        public static event Skeleton2DdataCoordEventHandler Skeleton2DdataCoordReady;

        public static void ProcessData(KinectInterop.BodyData data)
        {
            Vector2 [] p = new Vector2[6];
            Vector2 shoulderRight = new Vector2(), shoulderLeft = new Vector2();
            for (int i = 0; i < data.joint.Length;i++)
            {   
                JointType j =  data.joint.jointType;
                switch (j)
                {
                    case JointType.HandLeft:
                        p[0] = new Vector2(data.joint.kinectPos.x, data.joint.kinectPos.y);
                        break;
                    case JointType.WristLeft:
                        p[1] = new Vector2(data.joint.kinectPos.x, data.joint.kinectPos.y);
                        break;
                    case JointType.ElbowLeft:
                        p[2] = new Vector2(data.joint.kinectPos.x, data.joint.kinectPos.y);
                        break;
                    case JointType.ElbowRight:
                        p[3] = new Vector2(data.joint.kinectPos.x, data.joint.kinectPos.y);
                        break;
                    case JointType.WristRight:
                        p[4] = new Vector2(data.joint.kinectPos.x, data.joint.kinectPos.y);
                        break;
                    case JointType.HandRight:
                        p[5] = new Vector2(data.joint.kinectPos.x, data.joint.kinectPos.y);
                        break;
                    case JointType.ShoulderLeft:
                        shoulderLeft = new Vector2(data.joint.kinectPos.x, data.joint.kinectPos.y);
                        break;
                    case JointType.ShoulderRight:
                        shoulderRight = new Vector2(data.joint.kinectPos.x, data.joint.kinectPos.y);
                        break;
                }
            }
            var center = new Vector2((shoulderLeft.x + shoulderRight.x) / 2, (shoulderLeft.y + shoulderRight.y) / 2);
            for (int i = 0; i < 6; i++)
            {
                p.x -= center.x;
                p.y -= center.y;
            }
            double shoulderDist =
                          Mathf.Sqrt(Mathf.Pow((shoulderLeft.x - shoulderRight.x), 2) +
                          Mathf.Pow((shoulderLeft.y - shoulderRight.y), 2));
            for (int i = 0; i < 6; i++)
            {
                p.x /= (float)shoulderDist;
                p.y /= (float)shoulderDist;
            }
            if (Skeleton2DdataCoordReady !=null)
            Skeleton2DdataCoordReady(null, new BodydataCoordEventArgs(p));
        }
    }

public class BodydataCoordEventArgs
{
        private readonly Vector2[] _points;
        public BodydataCoordEventArgs(Vector2[] points)
        {
            _points = (Vector2[])points.Clone();
        }
        public Vector2 GetPoint(int index)
        {
            return _points[index];
        }
        internal  List<double> GetCoords()
        {
            List<double> temp = new List<double>();
            for (int i = 0; i < _points.Length; i++)
            {
                temp.Add(_points.x);
                temp.Add(_points.y);
            }
            return temp;
       }
}

hyui

Great stufff !!!!