基于DTW和K-means的动作匹配和评估*

吴齐云，战荫伟，邵　阳

（广东工业大学 计算机学院，广东 广州 510006）

基于DTW和K-means的动作匹配和评估*

吴齐云，战荫伟，邵阳

（广东工业大学 计算机学院，广东 广州 510006）

为满足基于Kinecrt的康复训练系统的需要，提出一种人体动作匹配和评估方法。该方法通过Kinect实时提取骨骼关节点三维坐标，计算骨骼关节点的角度，得到一组动作序列的空间角度变化值；然后通过改进的DTW算法把两组动作序列的角度值进行匹配，得到两个序列之间的距离；最后通过 K-means聚类方法对距离的大小评估。实验表明，该方法能很好地实现人体动作匹配和评估，实时性好，较传统DTW算法在识别速率上有明显提高。

动作匹配；Kinect传感器；K-means；DTW

0　引言

康复训练是病人通过训练使患病的肢体逐渐恢复功能，达到治疗效果。Kinect体感外设可以在不受背景和光照等影响下监测人体动作，近几年被应用到康复训练中。文献[1]结合Kinect用于在学步车上提取腿部信息进行医疗分析。文献[2]利用 Kinect的深度传感器获取深度图像来识别3D人体姿态。基于Kinect的康复训练系统相较于传统的面对面指导训练方法不仅可以减少医生的工作量，更可以提高病患训练的便捷性和自主性。

康复系统的关键在于人体动作识别。近年来对人体动作识别的研究十分活跃。NATARAJAN P等人[3]将CRF用到了人体动作识别中。Shi Qinfeng等人[4]针对连续的动作序列提出一种判定式的马尔可夫模型(即HMM算法)。由于CRF和HMM算法需先建模，算法复杂度较大。故本文提出一种人体动作识别方法，该方法通过 Kinect实时提取骨骼关节点三维坐标，计算骨骼关节点空间角度，以空间角度变化值定义一组动作，然后通过改进的DTW算法把两组动作序列的角度值进行匹配，得到两个序列之间的失真值，最后通过K-means聚类方法得到动作评估结果。

1　特征提取

Kinect传感器是康复训练系统的核心数据采集装置。Kinect通过 20个关节点来表示一个站立的人体骨架，如图1。

图1　人体骨架关节点

图2　人体关节角度

一个关节与其相邻的两个关节构成一个夹角。如图2所示，肘关节E和腕关节W、肩关节J就构成一个以E为顶点的角。

使用余弦定理计算关节角度：

利用Kinect获得一组动作关节点坐标，计算每一帧关节点空间角度值，判定两组动作相似性即为判定两个角度序列之间的相似性。测定两个角度序列的相似性可看作是两个时间序列之间的距离测量。

2　动作匹配

康复训练中，训练者会尽量模仿标准动作，但在时序上仍会存在很大差异[5]。因此需要对动作序列进行时序规整，采用动态时间规整算法 DTW[6]来解决距离测量过程中时间轴差异问题。

2.1动态时间规整算法DTW

设X和Y分别是长度为m和n的序列：

记xm和yn间的距离为d(xm，yn)，简写为 d(m，n)，1≤m≤M，1≤n≤N。

两条序列匹配的距离即为距离dk(m，n)加权和：

为了确保求得的路径A是一条全局最优规整路径，有约束条件：路径必须起点（1，1）到终点（M，N）；路径保持时间顺序单调不减；m和n只能依次增加0或者1，即（m，n）后一点必须是（m+1，n），（m，n+1）或者（m+ 1，n+1）；路径的斜率不能太小也不能太大，可以限制斜率在0.5～2范围内。

具有最小累积距离的路径才是最优规整路径，有且仅有一条，根据式(5)和约束条件可得 DTW距离的递归公式：

2.2一般的DTW改进方式

DTW算法虽然测量距离精准度很高，但是运算量很大，时间复杂度和空间复杂度都是 O（M×N）[7]。近年来DTW 的算法改进方法最多的是：全局路径限制[8]和放宽端点对齐[9]改进方法。

文献[8]的全局路径限制方法是把路径的斜率限制在1/3～3之间，此方法减少了 DTW的运算量，但精确度会有所降低。

实际应用中由于环境等各种因素的影响，起点和终点会有变化，引起误差，故放宽端点对齐方法是起点在（1，1）、（1，2）、（2，1）、（1，3）、（3，1）等中选择一最小值作为松弛起点，终点在（N，M）、（N-1，M）、（N，M-1）、（N-2，M）等中选择一最小值作为松弛终点。此方法并没有减少运算量，但增加了精确度，减少误差。

2.3本文改进的DTW算法

目前一般的DTW改进算法在精确度和运算量上并不能同时很好地满足，本文提出一种改进DTW方法，为了在提高算法复杂度的同时，保证精确度。

在本文的实验中最终需要得到的是最优规整路径的累积距离值，只需要存储每一次迭代的一个对齐时间对(xm，yn)，简写为(m，n)。因此没有必要用一个矩阵来保存所有时间对，可改为只保存2列，由大小是2×n的数组dist[][]和 pos[][]分别存储距离值和时间对，两列由 pre和cur表示，即指针cur始终指向当前时间点信息，返回两个序列当前时间和距离，pre指向当前的前一时间，如图3。

图3　数据存储

故DTW算法式(6)可改为：

其中m是序列X中cur指向的时间点，上述存储的是求得的最优路径的全局距离，同样地，最优路径是由pos[][]存储：

数组 dist和 pos均有两列，pre和 cur指针循环以确保数组中移动并为数组元素指定操作，减少操作时间，如表1所示。

表1　指针循环

由于本文改进的DTW有两个数组dist和pos，每个数组的大小是2×N，每个时间点只需要运算两个数组，所以时间复杂度和空间复杂度都是O(N)，相比于传统DTW的O(M×N)，速率明显提高。

3　动作评价

在一个连续动作中涉及到的关节角度变化序列不止一个，通过改进的DTW算法得到两个动作过程中所有关节角度变化序列的距离后，取平均值，对该距离平均值进行分析得到评价结果。

选取5个人每个动作按优秀、良好、合格做出实验样本，分别和标准动作序列通过本文改进的DTW求距离。选取最长的距离作为“合格”的下界 D。将0～D分为3段区间，W-0=Q-W=D-Q，将W和Q作为良好和合格的初始中心点，优秀的中心点始终是0。

由于参数只有W和Q两个分割点，故选择Kmeans算法取K=2对各区域进行聚类。将样本点R与0、W及Q计算距离，取三个中最小的距离作为该样本点的区域所在。

分别计算良好、合格的所有样本点中心：

其中，C为良好区域的重心点，M为分散到区域内的样本点数，dcw为样本点到M距离。

通过Kmeans划分出区域的同时，已计算得出良好和合格的期望，假设各区域的期望方差都符合高斯分布，则通过最大似然估计得到各区域的期望和方差：

分别对θ1和θ2求导后，求解θ1和θ2得：

其中xk表示第k个样本和标准样本距离，N表示元素总数。归一化后得到隶属函数：

把测试动作和标准动作的角度序列在经过改进的DTW算法求得距离后，通过隶属函数确定动作的评估结果。

4　实验分析

实验在康复训练系统中进行。实验者通过Kinect控制虚拟人物模拟标准动作进行运动，把实验者的动作和标准动作进行动作匹配后，得到动作评价结果。实验选取10人进行4组动作训练，每组动作10次。图4示，训练动作：伸肘侧平举（1-2-1）、屈肘侧平举（1-3-4-1）、抱头张肩（1-5-6-7-1）和复杂动作（1-2-3-4-5-6-7-8）。

图4　动作示意图

实验中用DTW算法、HMM算法、一般的改进DTW算法以及本文改进的DTW算法分别进行动作匹配，实验结果以识别成功次数和速率（单位：s/次）作为比较标准，见表 2。

表2　实验对比（每组100次）

5　结语

实验表明，本文改进的DTW方法能准确有效地进行人体动作识别，相较于传统DTW算法、一般改进DTW算法、HMM算法匹配速率有明显的提高且不影响精确度，动作越复杂时间越长，速率提升效果越好。在接下来的工作中，将进一步研究康复训练系统的界面设计。

[1]HU R Z L，HARTFIEL A，TUNG J，et al.3D Pose tracking of walker users′lower limb with a structured-light camera on a moving platform[C].Computer Vision and Pattern Recognition Workshops，2011：29-36.

[2]Zheng Xiao，Fu Mengyin，Yang Yi，et al.3D Human postures recognition using Kinect[C].2012 4th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC)，2012：344-347.

[3]NATARAJAN P，NEVATIA R.View and scale invariant action Recognition using multiview shape flow models[C]. Proceedings of The IEEE International Conference on Computer Vision and The Pattern Recognition，Alaska，USA，2008：1-8.

[4]Shi Qinfeng，Cheng Li，Wang Li，et al.Human action segmentation and recognituin using discriminative semi-Markov models[J].International Journal of Computer Vision，2011，93(1)：22-32.

[5]黄天羽，石崇德，李凤霞，等．一种基于判别随机场模型的联机行为识别方法[J].计算机学报，2009，32(2)：275-281.

[6]KRUSKALL J，LIBERMAN M.The symmetric time warping problem：from continuous to discrete[J].In Time Warps，String Edits and Macromolecules：The Theory and Practice of Sequence Comparison.Addison-Wesley，1983，23(5)：125-161.

[7]ABID H，HARUNUR R.User independent hand gesture recognition by accelerated DTW[C].Informatics Electronics &Vision(ICIEV)，2012 International Conference，2012：1033-1037.

[8]HSU Y L，CHU C L.An inertial pen with dynamic time warping recognizer for handwriting and gesture recognition[J]. IEEE Sensors Journal，2015，15(2)：154-163.

[9]KAPRYKOWSKY H，RODET X.Globally optimal short-time dynamic time warping application to score to audio alignment[C].ICASSP 2006 Proceedings.2006.

Human motion matching and evaluation based on STDTW and K-means

Wu Qiyun，Zhan Yinwei，Shao Yang
(School of Computer，Guangdong University of Technology，Guangzhou 510006，China)

This paper presents a human motion matching and evaluation method with Kinect sensors aiming at motion rehabilitation. This method extracts the three-dimensional coordinates of bone joints by Kinect during exercise in real-time,and calculates the size of the space angle bone joints to obtain a set of spatial change angle of action sequence.Then through the improved DTW algorithm to match the two actions angle sequence of values,the distance between the two sequences is gotten.Finally through the K-means clustering method，the size of the distance is assessed.Experimental results show that this method can achieve a good match and evaluation of human action,good real-time.Compared with traditional DTW algorithm，its recognition rate has improved significantly.

action matching；Kinect sensor；K-means；DTW

TP391.4

A

10.16157/j.issn.0258-7998.2016.08.035

广东省科技项目（2014B040401012）；广州市科技计划项目（2014J4100204）

吴齐云(1989-)，女，硕士，主要研究方向：人机交互。

中文引用格式：吴齐云，战荫伟，邵阳.基于DTW和K-means的动作匹配和评估[J].电子技术应用，2016，42(8)：141-143，153.

英文引用格式：Wu Qiyun，Zhan Yinwei，Shao Yang.Human motion matching and evaluation based on STDTW and K-means[J]. Application of Electronic Technique，2016，42(8)：141-143，153.