基于MVU降维的捕捉数据自动分割

张奕++王科琪

摘 要随着人体运动捕捉技术的不断发展，其在辅助训练，医疗康复等领域有着越来越广阔的前景。针对人工分割运动序列错误率高，效率底下等缺点，提出了一种基于最大方差展开的非线性降维的运动分割新方法。该方法包括以下几个步骤：首先选定检测窗口，对窗口内的片段采用最大方差展开方法对进行非线性降维，得到降维后的运动序列以及残差；然后在维度参数不变的情况下增大窗口区间，对其进行降维，同时通过迭代特征值估计降低计算复杂度；最后根据残差值的幅度跳变点衡量人体运动序列的分割点。通过实验，证明了该运动分割方法在准确率和召回率上均有良好的表现。

【关键词】人体运动分割 最大方差展开 残差 迭代特征值

随着运动捕捉的不断发展，其在电影电视，游戏动画，虚拟现实等产业的发展日新月异。在对运动捕捉数据的处理中，运动分割是尤为重要的一个环节。当采集的人体运动数据很多时，这些运动都保存在人体运动数据库中，这时自动地对人体运动捕获数据进行运动类型分割，将显得极为重要。分割后的数据应包含特有的行为语义，也就是说只具有一个行为类型。分割后的数据应包含特有的行为语义，也就是说只具有一个行为类型。将运动的捕获数据C分割为C1、C2、……、Cm，每个分割点需要精确求解，同时可以得到分割段数m。

目前对运动序列的分割方法主要可以分为两种：人工参与操作的人工分割，无人工参与的自动分割。人工手动分割又分为纯手动分割和含有预处理分割的半自动分割。总体而言，人工参与的分割速度慢效率低下，错误率高。自动分割是通过无监督学习将运动序列自动的分成不同行为的片段，可以实现全自动化。由于人工参与的分割方法有着速度慢，准确度低，且需要耗费大量的人力资源等缺点，所以自动分割运动序列的重要性显而见之。

对于自动分割算法的研究，国内外已有一些学者作出了较大的贡献。Barbic等人[2]提出了3种分割方法。首先，他们根据对不同阶段动作的本征值进行比对，发现相似的运动序列拥有平缓而且较低的本征值，而引入不同的运动序列会导致本征值的激增。根据观测本征值的突变点，从而提出了PCA 方法；他们还提出了概率主成分分析（PPCA）方法。 基于PCA方法，引入概率模型，假设不同的动作具有不同的高斯分布。最后，他们假设不同的运动数据围绕各个运动中心聚集以形成一个簇，并且每个簇可以由高斯分布模型表示，从而提出了GMM方法。Chang等[3]提议在贝叶斯框架的同时进行线运动估计和运动分割。 它将该字段表示为参数字段在MAP形式中，通过光流和分割的相互依赖吉布斯分布代表。 使用最高的信心优先和迭代条件模式算法对不同的运动行为进行分割。Zhou等[4]采用对齐聚类分析对运动序列进行谱分解，对相似的动作进行聚类后通过计算最小误差能量进行分割。在国内领域，冯林等[5]提出了人体运动分割的时间流形学习方法。该方法使用动作序列的局部关节弯曲指数来分析不同阶段各运动的相干性，并观察模糊过度段数据，通过测量关节弯曲斜率过零点，发现动作序列的轨迹。杜战战等[6]通过主测地线分析，结合姿势分布的马氏距离曲线对序列进行分割。肖俊等[7]提出了一种半自动分割方法。根据生理学模型，提取肢体中心骨架的关节角度作为人的描述特征。将高维运动序列降维成一维时序信号。胡晓雁等[8]通过线性聚类分析解决了运动序列分割点。该方法通过规划运动序列的距离，衡量出不同序列的合适距离指标，从而通过各种不同聚类分析方法完成分割。

人体运动序列数据是一个高维数据集。直接对高维数据集进行计算，计算成本高，耗时长，对噪声敏感。这就需要对高维的人体运动做适当的降维处理，使得维度简化，剔除维度间相关性，同时保存原始数据的大部分信息量。從而提高运算效率和精确度。

在上述分割方法中，普遍利用了线性降维方法作为对运动序列做处理。然而人体时序运动序列往往并不具有线性特征。由于其复杂性和多样性，使用线性降维的过程中往往会导致不可忽视的误差，一般情况下传统线性降维难以提取出其中的线性规律。由于本方法引入了非线性降维，能够更好的概括人体运动的细节特征，从而实现准确率的提升。本文提出一种基于非线性降维的运动分割方法，采用了非线性降维算法MVU对运动序列进行降维，该方法计算效率高，收敛性强，鲁棒性高，并对各种不同的非线性序列都能取得良好的降维效果。

1 MVU降维

1.1 原始降维算法

最大方差扩展（ maximum variance unfolding，MVU ）是基于局部等距概念提出的非线性降维学习算法，可以被认为是可以自动学习训练数据核矩阵K的KPCA特例[10]，MVU是一个高维数据流保持映射之前和之后相邻点之间的欧氏距离的条件，具有以下两个优点：一方面不仅可以学习高维数据集中隐含的低维信息，而且可以揭示内含尺寸。另一方面，由于该算法不需要测量高维数据点之间的欧氏距离，所以非凸数据集也具有理想的降维效果。此外，与PCA相比，两者具有相同的优化函数表达式，可以视为PCA的非线性形式。更重要的是，MVU维度可以更好地保持训练数据的分布。

MVU基本算法如下所示，设：X=[x1，x2，……xn]是高维数据集Y=[y1，y2，……yn]降维后的低维数据集，MVU算法设定一个以局部等距为前提的约束条件，在该条件下对点之间进行最大化展开，再以此为基础还原原始数据流形。算法先根据 X 构造一个邻域图G，如果xi是xj的k近邻，则权值Wij=1，否则Wij=0。这是一个在平方等式约束下的非凸二次规划问题，将它转化为一个半定规划问题获得最优解。定义Y的核矩阵Kij=yi·yj，则该半定规划可以转换为：

（1）

（2）

设K*为该优化问题的最优解，λα是K*的第α个特征值，Vαi为相应特征向量的第i个元素，对K*进行谱分解得到K*ij=∑nα=1λα Vαi Vaj。因此，高维数据xi的n维映射的第α个元素为。

1.2 降维误差衡量

由于降维过程中存在不可避免的数据损耗，为了衡量同原始数据的误差，我们采用残差来评判。通过定义能量百分比：

（3）

是数据集的原始维数，即原始采集信息维度。d是降维维数，即降维原始数据后用于分析的维数。λi表示原始数据集的核矩阵K*的第a个特征值。由于特征值揭示了原始数据集在投影到降维数据集上时对应特征向量方向的原有信息量，因此pd表示降维到d维度时变换所保留的信息量。通过残差，可以清楚的衡量现有降维结果同原始数据之间的误差。

2 基于MVU的运动分割方法

在对一段运动进行分析的时候，我们假设描述该运动不同阶段所需的维度是不同的。同时，运动包含的运动阶段越多，运动数据就越复杂，描述该运动所需的维度就越多。在MVU降维过程中，向子空间映射时，想要得到同前一运动段同样的误差，就需要更多的维度。即使用描述单一运动段的维度来描述多个合并的运动段，势必会导致误差的急剧增大。通过对误差的观测，会观测到误差急剧增大的帧，此时可以断定该帧即为运动序列的分割帧。

2.1 降维过程

在分析人体运动行为时，一般情况下使用关节点角度作为运动特征。为了避免万向锁，我们采用四元数代替欧拉角进行特征提取。而考虑到手，脚的子关节点对人体姿态影响不大，我们只选用了14个关节点，同时避免了引入不必要的误差。

首先根据邻域参数k，对原始数据构造等距约束，并计算该约束下的临域关系V，计算X中xi与其他点xj的欧氏距离dis（i，j）。若xi是xj的k邻近点，则两点彼此相邻，且边权值dis（i，j），否则xi，xj在V中断开。引入核函数求解该优化问题，得到最优解K*，从而可以根据最优解进行谱分解，得到特征值。

2.2 迭代特征值估计

在实际的求解过程当中，特征值的计算一般来说是非常复杂的。本例中，矩阵的阶数高，计算复杂度大，要想精确的计算出特征值是很困难的。因此，由矩阵元素估计出特征值的范围就显得尤为重要。本文采用迭代特征值估计的方法简化计算复杂度。对于符合特定条件下的矩阵，通过特征值的估计值转化原特征值于另一矩阵，从而得到对原特征值的数值解法。由圆盘定理的推论可得：已知给定n阶矩阵A，当A的n个圆盘互不相交时，则有估计式：

（4）

从而可以得到λi的近似值。迭代估计法的具体实现如下。

算法1-1 计算矩阵A的近似特征向量

输入：矩阵A，近似幅度ε，

输出：近似特征向量y，近似特征值λ

任意取非零向量u0，对于m=1，2，3，….执行：

进行LU分解，即（A-αI）=LU

4.当|βm-βm-1|<ε时，停止迭代，其结果为λ≈βm，近似特征向量为ym-1。

2.3 分割过程

首先，对于待分割的原始运动序列，选定一个长度为K的可变时序窗口，该窗口随帧的导入而不断向前变长。对该窗口内部的帧进行MVU降维，计算该段运动同原始数据的残差R。在维度不变的情况下，对窗口进行扩展，幅度为s帧。其中s表示扩展段，可以有效降低计算负责度。在得到每隔s帧的残差值序列后，对于同一阶段的运动序列来说，残差增长的很平缓，但当运动序列开始发生变化时，所需维度增加，这时残差陡然增大，可以根据斜率增大点判断分割点。设残差增幅为，其中di为当前窗口的残差，di-1为前一窗口的残差。当D突变时，其所在的帧即为动作发生变化的帧。对残差增幅求平均值，当时，该所在帧可以看作为运动分割帧。此时重新归零残差R，并重新设定時序窗口，对剩余数据进行MVU降维，以此类推，从而对运动序列进行分割。

3 实验结果

为了对算法进行准确率和有效性的验证，本文通过对一组包含不同运动行为的连续时序运动数据进行了分割。实验采用的是美国CMU数据库。选择第86号视频捕捉数据库，该数据库包含了走路，跑步，静坐，攀爬，看书等一系列运动，选择其中的10条进行运动分割。主要动作姿态如图1所示。

为了衡量运动分割方法的性能指标，采用分割点的查准率和查全率，以手工分割的结果作为评价标准。查准率是指采用本方法自动探测到的分割点中正确分割点所占的比例，查全率是指采用本方法自动探测到的正确分割点占手工分割点的比例。公式如下：

（5）

（6）

其中，E为算法正确落入分割点区间个数，A为算法分割点总个数，M为手动分割点个数。作为对比实验，我们采用PCA和PPCA分割方法作为对比，分割结果如表1所示。

从对两段实验结果的分析可以清晰的了解本文方法的优势所在。

实验一：对86_01的分割结果如下所示：（简单序列分割）该运动序列为一个长度为4580的组合运动序列，包含了行走、下蹲、攀爬等不同运动。采用MVU降维，降维后的维度为10。结果如图所示：结果表明该段组合序列包含五个稳定片段。分别代表行走，立定跳远，行走，立定跳远，踢腿，击拳。将分割结果同PCA和手动分割结果，以及粗分割结果进行对比。如图2所示：由于第二次立定跳远动作比较迟缓，PCA未能正确对第一次立定跳远后进行正确分割，同时未能将踢腿和打拳正确分割开，而是将他们识别成了一个运动。而基于MVU的运动分割则成功的将迟缓的第二次立定跳远阶段分割开，同时正确的将踢腿和打拳分割成两个不同的运动，成功实现了对相似动作的分割，提高了分割准确率。

实验二：对86_09的结果如下所示：该运动序列为一个长度为4531的组合运动序列，包含了行走、坐下、读书、眺望、行走等运动。采用MVU降维，降维后的维度为10。结果如图3所示：该段组合序列包含五个稳定片段。而PCA分割则未能正确的对坐下行为进行分割，而基于MVU的运动分割则成功的命中这一段的分割，成功的提高了对复杂运动的分割精度。

通过上述实验的分割结果对比可以得出，基于MVU的运动分割方法可以基本保证对运动序列的正确分割，得到更精确的分割结果。同时，该方法未能成功的分割出读书和眺望两个运动，究其原因是由于读书同眺望两运动相隔太接近，小于区间窗口阈值，导致残差计算误差较大。这也是今后下一步研究的主要方向。

4 结语

在本文中，我们提出了一种基于MVU非线性维数降低的运动数据分割方法。由于人体运动数据有着非线性的特征，所以对于给定的人类时间序列运动数据，MVU能够克服线性尺寸缩减难以处理的非线性特征的缺点，可以更好的拟合人体运动数据，实现更高的正确率。本方法首先对选定的运动序列窗口进行MVU降维，并且通过迭代特征值以减少运动序列的计算复杂度，然后依赖特征值求得运动序列的残差，不断扩大序列窗口，从而构建残差曲线。通过衡量残差曲线的跳变点，从而实现整个运动数据的分割。由于分段稳定片段具有特定的运动语义，因此可以进一步用于运动合成，搜索等应用。在未来的工作中，我们将进一步优化非线性降维运动分割算法，包括进一步的提高分割算法效率，以及提高对复杂动作分割的准确率。

参考文献

[1]李豪杰，林守勋，张勇东.基于视频的人体运动捕捉综述[J].计算机辅助设计与图形学学报，2006（11）：1645-1651.

[2]Barbi? J，Safonova A，Pan J Y，et al. Segmenting motion capture data into distinct behaviors[C].Proceedings of Graphics Interface 2004.Canadian Human-Computer Communications Society，2004：185-194.

[3]Michael M Chang，A Murat Tekalp， M Ibrahim Sezan.An Algorithm for Simulta-neous Motion Estimation and Segmentation[C].IEEE Internal Conference on Acoustics，Speech and Signal Processing（ICASSP94）， Adelaide，Australia，1994：221-224.

[4]Zhou Feng，Torre F，Hodgins J K.Aligned cluster analysis for temporal segmen-tation of human motion[C].8th IEEE International Conference on Automatic Face & Gesture Recognition，Amsterdam，The Netherlands，2008：1-7.

[5]冯林，刘胜蓝，王静，肖尧.人体运动分割算法：序列局部弯曲的流形学习[J].计算机辅助设计与图形学学报，2013（04）：460-467+473.

[6]杜战战，孙怀江.基于PGA的人體运动捕获数据分割方法[J].计算机工程与应用，2016（10）：141-146.

[7]肖俊，庄越挺，吴飞.三维人体运动特征可视化与交互式运动分割[J].软件学报，2008（08）：1995-2003.

[8]胡晓雁，孙波，朱小明，魏云刚.基于谱聚类的运动捕获数据分割[J].计算机辅助设计与图形学学报，2016（08）：1306-1315.

[9]Weinberger，Kilian Q.，and Lawrence K. Saul."An introduction to nonlinear dimensionality reduction by maximum variance unfolding."AAAI.Vol.6. 2006.

[10]Yang J， Frangi A F，Yang J，et al. KPCA plus LDA：a complete kernel Fisher discriminant framework for feature extraction and recognition[J].IEEE Transactions on pattern analysis and machine intelligence，2005，27（02）：230-244.

[11]Liu Y J，Chen T，Yao Y.Nonlinear process monitoring and fault isolation using extended maximum variance unfolding[J].Journal of Process Control，2014，24（06）：880-891.

[12]陈如清.基于改进MVU的非线性动态过程故障检测方法[J].仪器仪表学报，2013（09）：2111-2117.

[13]Chaloner K，Brant R.A Bayesian approach to outlier detection and residual analysis[J].Biometrika， 1988：651-659.

[14]Shoemake K.Animating rotation with quaternion curves[C].ACM SIGGRAPH computer graphics.ACM，1985，19（03）：245-254.

[15]Ran R S，Huang T Z.Bounds for Modules of Eigenvalues of Iterative Matrices[J].Journal of University of Electronic Science and Technology of China，2006，35（01）：133-136.

[16]Wu H T，Yang J F，Chen F K. Source number estimators using transformed Gerschgorin radii[J].IEEE Transactions on Signal Processing，1995，43（06）：1325-1333.

作者简介

张奕（1984-），男，山东省济南市人。博士学位。现为大连大学信息工程学院副教授。主要研究方向为运动捕捉及压缩感知。

王科琪（1991-），男，安徽省萧县人。硕士研究生。现为大连大学信息工程学院硕士研究生。主要研究方向为运动捕捉。

作者单位

大连大学信息工程学院 辽宁省大连市 116000