基于信息熵特征选择及聚类的人体运动捕捉数据分割方法

1、基于信息熵特征选择及聚类的人体运动捕捉数据分割方法摘要:人体运动序列的分割是指将复杂的长运动捕捉数据进行分割，从而得到若干个具有独立语义的片段，分别表示不同的运动类型，以方便对数据进行存储、检索、编辑与合成等工作。为了实现对人体运动数据的分割，本文提出了一种基于信息熵特征选择和k均值聚类的人体运动捕捉数据分割方法，该方法首先通过计算每一维度的信息熵，提取信息量较大的维度，使用度量MDS将提取出来的数据映射到低维空间，然后通过k均值聚类算法对低维数据进行分类得到初始分割点集，最后进行相似性检测确定最终精确分割点，从而得到了若干不同类型的运动片段。实验表明该方法可以实现对运动捕捉序列的分割，且与其

2、它算法相比，准确率有一定的改进。关键词：信息熵，运动捕捉数据分割，k均值聚类，欧式距离1 引言人体运动分割是指在运动捕捉数据中找出相应的时间帧，将其两侧所属不同运动类型的数据分割开来，便于数据的存储以及在动画制作过程中对其进行重用。近年来，国内外很多科研人员对人体运动数据的分割方法进行了深入地探索和研究，取得了丰硕的成果，主要集中于以下几个方面：(1)基于特征的人体运动捕捉数据分割方法肖俊等人9，10提取肢体骨骼与中心骨骼之间的夹角作为运动捕捉数据的几何特征，以启发式的方式来检测运动的分割点，然后通过人工交互实现对运动数据的精确分割，然而这种方法相对耗时，涉及过多的人工干预，而且由于特征是多维

3、的，降低了分割的精度。Peng3提出了将人体的根关节与肢体其他关节的距离作为中心距离特征，使用PCA方法对中心距离特征进行降维，从而得到一条特征曲线，然后通过低通滤波查找局部极值点，最终实现对运动数据的分割。石祥滨等人2针对关节角度或关节点中心距离作为人体描述姿态的特征所存在的局限性，提出了一种基于关节联动特征的运动捕捉数据分割方法。（2）基于聚类的人体运动捕捉数据分割方法很多学者将聚类方法成功地应用到了对运动捕捉数据的处理上，郝高峰等人1针对人体运动捕捉数据的缺失问题，提出了一种结合模糊聚类和投影近似点算法的缺失数据数据重构恢复方法。刘晓平等人3针对现有方法不能在人工交互条件下实现对任意平地

4、运动数据的足迹自动检测，提出了一种基于谱聚类的足迹自动检测方法。（3）其他人体运动捕捉数据分割方法Lv N等人11 提出了一个通用的遗传算法框架用于人体运动捕获数据分割。Schulz等人4提出了一种自动分割算法，该算法使用过零分割技术，利用不同的动作其过零率也不同，定义了过零率阈值，进一步完成提取不同运动。Takashi AOKI等人5使用惯性传感器来对人体运动进行时序分割。Samer Salamah等人6以分类树的形式，其中，最高级别的动作捕捉数据分为动态和静态片段，而最低级别的运动捕捉数据使用功能单一的身体部位来识别广泛的人类动作。Lin J.F.S 等人7 在速度峰值和零速度交叉点分割运

5、动流，然后使用HMM对获得的片段进行提炼和分类。Carlos Orrite, Mario Rodriguez等人8提出了一种基于可观测的马尔科夫（OMMS）的方法来构造动作状态和中间状态的网络模型，在此模型中，通过在每一特定时间的状态进行解码来识别一个复杂的未知序列，在此基础上列入新的中间状态来模拟连续动作之间的转换，以此展开对长而复杂的运动序列的自动分割。Yan Wang等人13提出一种基于PCA的GMM方法能够有效探索去除每一个运动片段的运动过渡部分，从而产生干净的运动分割片段，有利于自然动作的生成。综上所述，寻找不同动作之间的分割特征是对人体运动序列分割的关键。从以上分析中不难看出在分割

6、算法中广泛应用到了降维技术。人体运动捕捉数据是一种多维度的数据，复杂度高，而且运动捕捉数据绝大部分都是非线性的，直接对高维数据进行处理分析费时费力，为了降低分割难度，并在保持原始数据原有拓扑结构及相关性的前提下，本文通过信息熵特征选择和度量MDS完成了对数据的降维，然后通过聚类及相似性检测得到最终的分割点，从而获得若干不同类型的运动片段。本文算法流程图如图1所示。 图1 运动序列分割流程图2 本文分割算法介绍本文提出了一种基于特征选择和k均值聚类的人体运动捕捉数据分割方法，该方法首先通过计算每一维度的信息熵，提取信息量较大的维度，使用度量MDS将提取出来的数据映射到低维空间，然后通过k均值聚类

7、算法对低维数据进行分类得到初始分割点集，最后通过计算指定窗口到前一个片段的帧间欧式距离来对初始分割点进行相似性检测，提取出该窗口中与前一片段的帧间距离方差最小的一帧作为最终精确分割点，从而得到了若干不同类型的运动片段。接下来分别对本文算法中所用到的特征选择和降维、聚类及分割两个方面来进行介绍。2.1 特征选择和降维人体运动捕捉数据维度高且其数据本身分布复杂，又因运动捕捉数据绝大部分是非线性的，直接对数据进行处理分析难度较大。为了降低对数据处理的难度，本文通过特征选择得到一组包含高信息量的新的特征属性，然后利用数据中每帧之间的相关性，采用度量MDS降维算法对其降维。（1）特征选择人体运动捕捉数据

8、是由若干连续运动帧数据组成，每一帧代表一个固定的姿态，每一维度表示不同关节点的运动参数，从而记录了各个关节在各个时间的状态。对于一定的人体运动捕捉数据，其中不乏冗余的维度来表示运动特征，比如简单的挥手动作，人体的下半身的各个关节点与此动作没有直接或者间接的关系，因此本文提出通过计算每一维度的信息熵来提取某一运动捕捉数据的特征，从而降低了数据的复杂性及冗余度。信息的基本作用就是消除人们对事物了解的不确定性。美国信息论创始人香农14发现任何信息都存在冗余，为了解决数据通信领域中信息传递过程中出现的信息冗余问题而提出，当时主要用于解决通信控制系统中普遍存在的信息度量、变换和传递等问题19。如今随着信

9、息和信息科学的不断发展，人们对信息论的意义及其价值的认识不断加深，信息论的研究范围已扩大到所有与信息有关的研究领域，如心理学、语言学和语义学等。信息熵是信息论中的一个概念，用来衡量信息中所包含的信息量的大小。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。因此，信息熵也可以说是系统有序化程度的度量。设人体运动捕捉数据集X第I维数据XI的概率分布为：其中，n表示运动序列的长度，J = 1,2,.,n I = 1,2,.,93, PI,J表示人体运动捕捉数据第I维数据中第J帧数据点的概率大小，则数据XI的信息熵定义为“加权平均信息量”。本文在特征选择时，计算出人体运动捕捉数据

10、每一维度的信息熵，其中信息熵越大表示数据中该维度所含信息量越多，说明此时运动状态发生改变的程度大，可能是不同运动状态的分割点。信息熵越小则表示该维度所含信息量越少，意味着运动状态的改变小，是同一种运动的概率比较大。在此提取信息熵较大的数据，从而获得一组包含高信息量的新的特征属性，以便于分析隐含在数据中的内在关系。（2）度量MDS降维经过特征选择后的人体运动捕捉数据仍然具有较高的维度且其数据本身分布复杂，又因运动捕捉数据绝大部分是非线性的，直接对特征选择后的数据进行处理分析仍有着很高的复杂度。考虑到数据内部有特定的拓扑结构，并且每个序列的帧与帧之间有一定的相关性，因此对数据进行降维不能破坏其原有

11、拓扑结构及相关性，满足对后续序列进行分割的基本要求。本文采用了度量MDS15对人体运动捕捉序列进行降维，该算法是一种基于欧式距离的非线性降维方法，适用于能够反应出研究对象间的相似性和差异性的数据，而运动捕获数据刚好符合这一要求。与其他降维方法相比，该算法针对非线性的数据降维，能够较好地保持原始数据的原有拓扑结构以及相关性。本文所采用的度量MDS的主要思想是，将原始多维数据点映射到欧式空间，再在欧式空间中使用合适的点距来近似表示原始数据点间的距离。设特征选择后的人体运动捕捉数据 X = (X1，X2，.，XN)t是t维空间内一包括n个输入向量的数据点集，用MDS降维方法从距离集合中重构出X的坐标

12、表示，为了让低维嵌入坐标中心在原点处且更好地与坐标轴对齐，原始数据可假设已被中心化。该算法主要分为三个步骤：step1求得距离平方矩阵D：其中，i，j = 1，2.，N，e为N´1维全1阵，B = (|X1|,.,|XN|)T。step2将距离平方矩阵双中心化：设J = I - eeT/N。其中，e为N´1维全1阵，I为N´N维单位矩阵，则Je = 0，eTJ = 0，JT =J ，(证明：同理可得：eTJ = 0)对任意包含N 个样本点的输入X = (X1,X2,.,XN)。利用J将距离平方矩阵双中心化，则有：令，则。step3得到原始数据低维坐标表示：令，将H

13、阵特征分解：。令为矩阵H 的特征值，令为其对应特征向量，取其前d个特征值和其对应前d个特征向量，进而得到输入X 的低维坐标表示Y，如下表示：，将Y作为降维结果输出，从而达到对原始运动捕捉数据降维的目的。2.2 k均值聚类及分割通过特征选择及度量MDS算法对特征维度数据进行降维，得到一组表征运动特征的低维数据。接下来对低维数据数据进行k均值聚类分析。（1）k均值聚类算法的基本思想麦克奎因（J.B.MacQueen）16于1967年提出了k均值聚类算法，用来对数据进行聚类，由于该算法过程简便且很早被提出，所以在工业和科学领域应用极其广泛。该算法主要解决的是将含有n个数据点的集合划分为k个类簇的问题

14、，该算法首先在集合中随机选取k个数据点作为k个类簇的初始聚类中心，集合中的每个数据点将被划分到与其距离最近的聚类中心所在类簇中，从而形成了k个聚类的初始分布。对分配后的每个类簇再次计算新的聚类中心，继续进行对数据的分配，以此迭代若干次之后，若果聚类中心不再发生变化则可说明该数据对象已全部被分配到自己所在的相应类簇中，聚类准则函数收敛，否则继续对数据进行迭代，直至收敛。聚类准则函数一般采用聚类误差平方和准则函数。该算法的一个特点是在每次的迭代过程都要对全部数据进行分配调整再重新计算聚类中心，然后进入下一次的迭代，如果在某次的迭代过程中所有的数据点的位置没有发生变化，且其相应的的聚类中心也没有发生

15、变化，此刻标志着聚类准则函数已经收敛，且算法结束。（2）k均值聚类算法的算法流程输入：将降维后所得的数据点集，聚类数目根据运动序列中所含运动的种类来确定，设为k；输出：k个类簇Cj，step1 令I = 1，随机地选取k个数据点作为k个类簇的初始聚类中心，；step2 计算每一数据点与k个聚类中心的距离，如果满足则；step3 计算k个新的聚类中心step4 判断：如果，则，返回step2；否则算法结束。（3）对运动序列的分割前面通过对运动捕捉数据进行特征选择、度量MDS算法降维、k均值聚类分析，对于长度为n的运动序列，我们得到被标记为1k的n个数组成的一维数组，其中1k为不同类簇的标记。在此

16、对一维数组按照顺序对其遍历，对相邻的两帧进行比较，如果相邻两帧属于不同的类簇，则将较小帧存入矩阵D1中，同时，为了保证初始分割点不能过密，在此处设置阈值T，判断矩阵D1中的相邻两帧的帧间长度是否大于阈值T，若条件成立，则两帧都作为初始分割点，否则去掉较大帧，从而我们得到了运动序列的初始分割点。其次，对初始分割点再次进行检测，该检测过程主要分为几个步骤：step1令；step2m = m + 1，以第m个初始分割点Pm为中心设置一个长度的窗口，即：帧，然后计算该窗口中的每一帧到前一个片段每一帧的帧间距离。由于各帧之间往往存在着不同的相关关系，帧间距离可选择欧式距离，欧式距离定义如下：step3将

17、各帧间的欧式距离存入矩阵D3中，将D3作为样本，计算其每行的方差，提取出方差较小的一帧即为最终分割点。4 结束语本文提出了一种基于特征选择和k均值聚类的人体运动捕捉数据分割方法，该方法首先计算运动捕捉数据每一维度的信息熵，其中信息熵越大表示其所含信息量越多，提取信息熵较大的维度，通过度量MDS将提取出来的运动数据映射到低维空间，然后采用k均值聚类算法对低维数据进行分类得到初始分割点集，最后通过计算指定窗口到前一个片段的欧式距离来对初始分割点进行相似性检测，最后提取出该窗口中与前一片段的欧式距离方差最小的一帧作为最终精确分割点，从而得到了若干不同类型的运动片段。在以后的学习工作中，我们将对本文提

18、出的算法进行进一步的深入研究及改进，即：在特征选择过程中，针对不同类型的运动捕捉数据所要提取的信息量较多的维度的多少也不一样，复杂的运动序列可能要提取出较多的维度信息，而针对较为简单的运动序列则也许只需提取数据中的较少维度信息即可。所以我们将进一步地通过实验来探讨在保证分割准确的前提下，如何针对不同类型的运动捕捉数据提取出含高信息量的特征属性，以降低数据的冗余度和复杂度。参考文献1 赫高峰, 彭淑娟, 柳欣, 等. 结合模糊聚类和投影近似点算法的缺失人体运动捕捉数据重构J. 计算机辅助设计与图形学学报, 2015, 27(8): 1416-1425.2 石祥滨, 赵林, 代钦, 等. 基于关节

19、联动特征的运动捕获数据分割方法J. 系统仿真学报, 2014, 11: 018.3 刘晓平, 陆劲挺, 谢文军. 运动捕捉数据中足迹的谱聚类检测方法J. 中国图象图形学报, 2014, 9: 007.4 彭淑娟 ,柳欣. 一种结合双特征的运动捕获数据行为分割方法. 计算机科学.2013.5 Aoki T, Venture G, Kulic D. Segmentation of Human Body Movement Using Inertial Measurement UnitC/Systems, Man, and Cybernetics (SMC), 2013 IEEE Internatio

20、nal Conference on. IEEE, 2013: 1181-1186.6 Salamah S, Zhang L, Brunnett G. Hierarchical Method for Segmentation by Classification of Motion Capture DataM/Virtual Realities. Springer International Publishing, 2015: 169-186.7 Lin J.F.S, Kulic D. Segmenting human motion for automated rehabilitation exe

21、rcise analysisC/Engineering in Medicine and Biology Society (EMBC), 2012 Annual International Conference of the IEEE. IEEE, 2012: 2881-2884.8 Carlos Orrite, Mario Rodriguez et al. Automatic Segmentation and Recognition of Human Actions in Monocular Sequences. 2014 22nd International Conference on Pa

22、ttern Recognition of the IEEE. 2014:4218-4223.9 J. Zhang, J. Zhang, and S. Chen, “Discover novel visual categories from dynamic hierarchies using multimodal attributes,”IEEE Transactions on Industrial Informatics, vol. 9, no. 3, pp.16881696, 2013.10 Xiao J, Zhuang Y T, Wu F et al. A group of novel a

23、pproaches and a toolkit for motion capturedata reusing. Multimedia Tools and Applications. 2012, 47(30): 379-408.11 Lv N,Huang Y, Feng Z, et al A genetic algorithm approach to human motion capture data segmentationJ. Computer Animation and Virtual Worlds, 2014,25(3-4): 283-292.12 Peng S J. Motion Se

24、gmentation Using Central Distance Features and Low-pass Filter. International Conference on Computational Intelligence and Security, USA,2012:223-226.13 Yan Wang, Hyewon Seo, Soohyun Jeon. Automatic Transition Detection of Segmented Motion Clips Using PCA-based GMM MethodC. Cyberworlds: 2012 International Conference. 2012. 567572.14 15 X.-M. Liu, A.-M. Hao, and D. Zhao, “Optimization-basedkey frame extraction for motion ca