一种基于索引空间的三维运动捕获数据检索方法

徐从洋 徐江峰

(郑州大学信息工程学院 河南 郑州 450001)

一种基于索引空间的三维运动捕获数据检索方法

徐从洋 徐江峰

(郑州大学信息工程学院 河南 郑州 450001)

为能有效检索当前大量的三维人体运动捕获数据从而投入使用，针对三维人体运动捕获数据的独有特性，提出一种高效的检索方法。首先通过关键帧提取对原始运动数据降维，然后采用自定义的符合人体运动语义的特征将原始角度数据转换为特征序列。根据数据库中所有运动片段对应的特征序列构建一种基于姿态特征的索引空间。检索时通过在索引空间上顺序匹配姿态特征来查找时序一致的匹配运动片段。实验结果表明，与大多数现有方法相比，该方法由于较好的运动语义特征提取，因此具有更好的时间效率，更高的灵活性和检索精度，能够满足多种运动数据的检索需要。

运动捕获数据 运动检索 特征提取 索引空间

0 引 言

近年来，随着三维人体运动捕获技术的日益成熟以及多媒体技术的快速发展，大量的视觉真实感强、富有表现力的人体运动捕获数据被录制保存，并被有效地应用在了三维动画、电影制作和游戏等产业中。然而大量的运动捕获数据同时也增加了其被有效管理和重用的难度。因此，如何对运动数据库进行精确高效的检索成为了该领域的重要研究目标。

当前的运动检索方法主要有基于运动模板匹配、基于内容、基于索引和动态时间弯曲等方法[10]。基于内容的检索[13]因其能从运动数据本身充分提取描述运动的信息，从而设计出高效自动的运动检索方法的特征，被目前研究人员广泛使用[11]。本文的方法也是基于内容的运动捕获数据检索方法。

基于内容的检索方法主要包括两个技术难点：

(1) 运动数据的特征提取

原始运动捕获数据如BVH格式数据采用人体各关节相对于父关节旋转角度和整体偏移量描述运动姿态，高采集频率帧描述运动轨迹，构成了一个较大的二维原始数据空间。并且自然人体运动具有很大的灵活性,因而具有较高的自由度,导致人体运动特征的表示和描述存在较大的困难。因此，面对运动数据高时间、空间复杂度，找到一种有效的特征表示方法，对于数据降维和提高检索效率具有重大意义。

关键帧方法如潘红等[7]首先根据运动数据定义简单特征，然后提取关键帧代表整个运动时序序列，该方法对原数据有效降维但特征提取不够完善。聚类方法[2,9]以层次化方式描述运动，将相似的运动数据归类并提取特征值，用特征值集合表示运动。Wu等[2]、Deng等[9]将整个人体划分为几部分，并对每部分进行聚类。Chao等[4]使用了一组正交球面谐波基函数来代表运动轨迹，并将调和函数系数作为编码结果，提供了一种直观的规格化查询方法，但不能捕捉到人体运动的动态性。Barnachon等[1]用运动图中的关键路径代表运动片段。Wang等[6]使用局部线性回归模型学习多个拉普拉斯算子图以保留运动数据的局部几何结构，然后将这些图结合起来互补特征信息。Kapadia等[3]根据特定各肢体之间以及肢体与环境之间的关系自定义特征，这样做比直接帧间对比更节省运行时间且有很好检索效果。其中文献采用Laban运动分析定义了一组可以表示人体结构、几何与动态特征的运动键值来编码运动。

(2) 索引与相似度匹配

特征提取后如何构建索引结构是保证相似度匹配高效性、准确性、灵活性的前提。良好的索引结构应具有紧凑、独立于数据库大小、容易更新和支持子序列与模糊查找等特性。相似度匹配是运动检索最后的阶段，算法应具有良好的时间空间复杂度，并且能够在数值相似和逻辑相似之间找到一个合理的折中，从而得到符合用户需求的检索结果。

蓝荣祎等[5]将人体结构分上下两部分，分块对所有运动片段提取关键姿态并通过AP聚类找出具有代表性的关键姿态，然后将运动片段转换成运动文档后通过向量空间模型对数据进行检索。Deng等[9]建立身体各部分分层表示的运动序列索引表，然后使用快速字符串匹配算法进行运动序列的匹配。潘红等[7]在检索过程中构建距离矩阵求得运动片段间的相似度从而实现检索，需要在每次检索时消耗大量时间计算匹配路径与相似度。Kapadia等[3]建立单词查找树，然后用正则表达式表示样本特征与树中特征序列对比，但需要建立大量树才能对应所有特征并且需要检索时有一定先验知识。

本文采用参考Laban运动分析自定义的特征描述人体肢体之间以及肢体与环境之间的关系，利用特征值组合表示不同运动姿态从而构建一个与运动时序相关的索引空间，依据此索引空间可以完成快速且准确的运动检索。

1 运动特征定义与提取

根据Laban运动分析LMA( Laban Movement Analysis)[Laban 1971]定义，人类运动中包含很多特性：(1)结构特性和物理特性；(2)动作的动态性与意图；(3)运动中的人体形态。索引运动数据库的一个基本要求就是需要包含这些运动特性，尽可能全面而精炼的特征能够更好地描述动作，提高检索结果准确率。

我们先根据人体结构划分出一组身体躯段S，如图1所示。然后定义了一组布尔型运动特征F(p)={fk(p)}(k对应特征序号)，其中每个特征对应动作姿态p的一个特定动作特性，不同的特征由不同的身体躯段集合计算而来。虽然每个运动特征fk(p)对应的是一个关键帧姿态pj，但有些运动特征如关节瞬时速度是根据一定范围[j-Δ,j+Δ]内相邻帧计算出来的，因此保留了运动的动态性。

图1 人体骨骼分段模型

我们参照Laban运动分析将特征集合主要分为身体特征、动力学特征和外形特征。

(1) 身体特征主要描述人体运动的结构和几何特征，这个类别可以帮助识别人体哪一部分在移动，哪些部位间有接触和人体部位运动的模式。在这部分特征的定义中，我们考虑到了人体一些关节的自由度通常小于3，因此一些不太可能出现的姿态特征可以直接忽略以精简特征空间。

动作表现 这个特征表示人体躯段在当前是否是运动的状态，通过计算与相邻姿态间的位移量是否超过阈值。此特征主要针对四肢和整体的位移。

(1)

相对位置 描述各肢体间相对位置，例如左右腿在身体平面的前或后面，在平面前特征值为1，否则为0。(如图2(a)所示)此特征可描述身体各部位的位置状态，是所定义特征中最重要且最多的部分。

朝向信息 表示人体上下两部分相对于基础姿态时的朝向是否有大的变化。此特征可以描述例如转身等朝向信息有变化的运动。

(2)

肢体间接触信息 计算各肢体是否接触(两肢体之间距离是否小于阈值)，例如左右胳膊的分开与合并，可以更精确地区分动作。

(3)

夹角信息 计算当前姿态中四肢的夹角和人体上下两部分间的夹角是否小于阈值，例如可以通过大腿和小腿之间以及上半身和下半身之间的这一夹角特征判断人是直立还是蹲下(如图2(b)所示)。

(4)

其余还有中心位移、重心偏向和支撑点等特征。

(2) 动力学特征更多描述动作的逻辑动态性，同样的一个身体姿态可能是由两个语义完全不同的动作表现出来。例如向前伸手的动作，轻缓地递东西与愤怒地推搡在语义上完全不同，这是仅几何位置特征所不能表现的。参照Laban运动分析分为四个动力学特征：空间、力度、时间和平滑度。

空间 空间特征区分运动轨迹是直线或非直线，由当前姿态与前Δ帧区间的距离比率计算而来的。

(5)

力度 力度特征主要区分运动是猛烈的还是轻缓的。通常猛烈运动的特点是速度值由大到小变化非常快，减速明显；而轻缓的运动速度平均，减速较慢甚至没有。

(6)

时间 时间特征与力度特征相对应，根据运动速度由小到大变化快慢区分运动是突然的还是稳步变化的。此特征和力度特征一起可以详细描述动作从静止开始到运动再到静止结束的整个过程的风格。例如急切的敲门表现为突然和猛烈的，而原地起跳表现为突然和轻缓的。

平滑度 描述运动在一定时间范围内的连续性，体现在运动速度曲线是否在时间范围[j-Δ,j+Δ]内存在多个波峰波谷，即加速与减速切换是否频繁。

(3) 外形特征描述人体运动姿态的轮廓，特征主要定义人整体与四肢的不同外形状态。(如图2(c)所示)

(7)

图2 特征定义示例

2 索 引

经过第1节所描述的关键帧提取和自定义特征提取，原始运动数据得到了有效的降维和逻辑特征表示，每个运动姿态pj转化成了一个对应的布尔特征值序列F(pj)=f1(pj)f2(pj)…fk(pj)，而运动片段则可表示为特征序列集合：mi:={F(p1),F(p2),…,F(pn)}。由于一个特征序列代表特征相同的一类动作，因此我们得到了一个基于整个数据库的姿态特征空间，而每一个运动片段则可理解为空间中一些姿态按时序顺序的连接，如图3所示。

由此，我们定义了特征空间来索引整个运动数据库。对于一个运动姿态，其对应的布尔特征值序列可以作为该姿态在索引空间中的索引号，将该姿态特征序列与对应某特征位为1，其余位为0的序列相与，即可得到该姿态在某特征的值。在特征提取阶段，记录每个姿态所在的运动片段序号和对应帧序号，作为该姿态的索引信息。最后将所有姿态按布尔特征值大小排序，顺序存储。由此可以看出，索引空间将数据库中所有运动片段的不同姿态提取出来，同时包含了每个姿态在运动片段中的信息。而索引空间的更新(通常为增加信息)也非常容易，直接插入一个新的运动姿态及索引信息或只增加已有姿态的新索引信息即可。

图3 运动片段匹配索引空间

根据定义的索引结构的特点，可以很方便地实现运动子序列匹配，模糊查找等常见检索需求。

子序列匹配 当输入查询运动片段时，其有可能是数据库中某些长运动片段的子序列。在检索中，通过查询运动片段的第一关键帧姿态对应的特征值序列可以快速定位到索引空间中的相似姿态，即找到查询运动片段在长运动片段中相匹配的开端。

模糊查找 当用户需要与查询运动片段部分特征相似而非完全一致的运动数据时，可以通过指定部分特征要求匹配。指定特征越少，相匹配的就越多。

实时查找 由于构建索引空间是线下完成，并且检索时可以并发查找多个相似运动，因此检索速度快，能实现实时查找。

3 检 索

根据以上的特征提取与索引空间定义，我们结合折半查找算法和姿态特征匹配实现检索。在算法描述前，首先给出一些定义说明。

输入包括特征向量表示的查询运动片段Q，用户指定的需匹配特征sf和姿态索引空间FIndexSpace。其中sf转换为一个指定特征位为1，其余位为0的二进制序列。假如全部特征数为10，指定必须匹配的特征位为0、1、3、6、7(以0开始，从左向右)，则sf=1101001100。在查找中两特征序列分别和sf相与后值相等即为匹配。定义每次查找得到的运动片段集合M0和当前总命中运动片段集合Mh，记录匹配到的运动片段序号，命中次数以及帧序号。

算法描述如下：

Step3：如果mj∈M0∧mi∉Mh，将mi直接合并入Mh，记录其帧序号并置其命中次数为1；

Step4：如果mi∈M0∧mi∈Mh，比较mi在M0中的帧序号f0和在Mh中的最后一次命中的帧序号fh：如果f0>fh，将mi合并入Mh并将其命中次数加1；否则将Mh中对应mi的命中次数减1；

Step5：如果Q还有下一帧，转至Step2；否则除去Mh中命中次数小于Q关键帧长度50%的运动片段，所得Mh即为最终检索结果。

算法中使用折半查找在姿态空间中找到与查询片段Q中某一帧相匹配的姿态，并可以按照第2节索引结构的定义得到匹配姿态所在运动数据库中的运动片段集合，表示为该查询姿态在这些运动片段中出现。由此知当命中同一运动片段次数越多，表示该运动片段与查询片段Q越相似。同时记录匹配姿态的帧序号，每次命中下一帧时比较帧序号是否按照升序排列，保证检索结果与Q时序一致。最后排除只有少数帧与Q时序一致的运动片段，所得结果按命中次数排序即为与Q相似度由大到小的运动检索结果。

由于Q中每一帧只在索引空间中查找一次，避免了运动的重复匹配。检索结果中包含匹配运动片段中第一帧命中Q的帧序号，因此可以实现子序列匹配的首帧定位。

4 实验结果与分析

本文实验数据包括卡内基梅隆大学人体运动捕获数据库[12]的共约400个运动片段，分为8类，如表1所示。所有运动捕获数据关节数为23，帧频率为24 fps，运动片段长度为40帧到5 000帧不等。我们使用C++开发出一个检索系统，实现检索前的运动数据预处理和检索时的整个过程。实验中系统运行在Intel P4 2.7 GHz CPU和2 GB内存的PC机上。

表1 实验数据库运动数据分类

4.1 运动数据预处理阶段

运动数据预处理即为对原始运动数据集进行检索前的线下处理，包括关键帧提取，特征提取和构建索引空间三个步骤。

1) 考虑到线下处理的要求，我们采用计算量大但更准确稳定的刘云根等[8]的重建误差最优化的关键帧提取方法。实验通过文中方法对所有原始运动数据提取关键帧，不同动作的最优压缩率不同，简单缓慢的动作最优压缩率高，而复杂猛烈的动作最优压缩率较低。如缓慢行走的压缩率平均为7%，而舞蹈的压缩率平均为16%。最终所有运动数据提取过后的总帧数为40 238帧，总平均压缩率为约11%，可以看出大大减少了后期对运动数据处理的量。

2) 本文第1节共定义了36个布尔特征，因此特征提取阶段会将运动片段的每一关键帧转换为一个长度为36的布尔序列，对应值范围为[0，236]。最终将每个运动片段转化为一个特征向量。

3) 构建索引空间将所有特征向量的每个特征提取出来，记录下所在运动片段的序号和帧序号，并将所有特征排序。由特征定义可知索引空间大小不会超过236，但实际中由于一些常见的姿态如直立不动，普通的慢走等会重复出现在多个不同的运动中(如图中两个峰值)；同时一些特征定义中理论上的姿态基本不会出现，因此最终的索引空间会远小于236。本实验中，最终提取的不同特征值共31 386个，特征分布与姿态重复度如图4所示。根据运动数据集的不同，姿态重复的多少有无和峰值的分布会有所不同，但基本会体现为少数几个姿态重复度较高，而大部分姿态只出现一到几次。最终虽然减少的重复姿态不多，但是在检索一些有重复动作的运动片段时仍能有效减少检索阶段对相同姿态的重复比较。

图4 特征分布与姿态重复度

4.2 检索阶段

线下构建好索引空间后，即可通过输入查询片段并指定需匹配特征进行线上检索。其中查询片段也要通过关键帧提取和特征提取转化为特征向量。根据第3节对检索算法的描述，得到部分实验结果如图5-图7，并按相似性高低从上到下排序。

图5第一行为用户输入的查询运动片段“走”，并指定两腿的相对位置特征、身体运动特征匹配走的形态，指定两腿力度特征来区别于跑步运动。图5(a)-(e)为数据库中运动“走”的几类检索结果。可以看出指定特征较少时，检索结果为“走”的模糊查找结果。但同时检索结果类别间相差比较大，则可以通过指定更多的特征来更精确化检索。图5(a)为最近似于查询运动的结果；图5(b)为愉悦地走路，身体有大幅度上下摆动，可通过附加中心位移特征去除此类走的结果；图5(c)为双臂水平向后张开走路，可通过附加匹配胳膊的相对位置特征去除；图5(d)为转圈走，运动轨迹为非直线，可通过简单地附加身体空间特征去除。

图6第一行为查询运动片段，描述为“从坐到站起直走”。除了上述对走的特征指定外，还指定了身体上下部分夹角和两腿的夹角特征以及外形特征。图6(a)为最接近的检索结果；图6(b)为站起来时转弯走，因此可通过附加身体空间特征去除；图6(c)为翘起腿坐并将一只手放在腿上，可以通过附加肢体间接触信息特征去除；图6(d)为迅速站起走，可通过附加时间特征去除；图6(e)为醉酒下的从坐到走，表现为身体来回摆动，并且动作不稳，因此可附加重心偏向和平滑度特征去除。

图7为反映子序列查询的检索，第一行为查询片段“双腿合并向前跳”，图7(a)为匹配到的运动片段，然而其匹配的片段为图7(b)“向前走后双腿合并向前跳”运动片段开始于第39帧的子序列，即实现了子序列的匹配。

图5 运动“走”检索结果

图6 运动“从坐到站起直走”检索结果

图7 运动“双腿合并向前跳”子序列检索结果

本文检索算法在查找某一帧对应特征序列时使用折半查找搜索索引空间，查找时间复杂度log2n，n为姿态总数，最多为236，则每个特征序列查找次数最多为log2236=36。对于本文实验环境，原始查询运动片段为300帧时，查找平均时间为0.034 s。

为了对比不同算法在测试运动数据库的检索效果，图8为各算法在多个运动类别上的P-R(precision-recall)曲线，可以看到由于本文算法通过特征提取将原始角度数值转换成具有逻辑语义的特征值，并在检索时适配查询运动选择要匹配的特征进行检索，因此具有相对较好的查准率与查全率。文献[3]方法构建字典树并结合正则表达式检索，提高了检索速度。但由于每棵字典树只对应一个特征，因此在匹配多棵字典树后需要将结果合并，合并的过程不能保证特征之间的时序一致，而这也将提高错误匹配的几率。文献[7]定义八段骨骼角度特征对数据集比较敏感，不同风格的运动在匹配网络中较难形成匹配路径，因此会丢失一些语义相同但风格不同的匹配运动。并且文献[7]每次检索都需要通过大量计算来得到查询运动与数据库运动的相似度与匹配路径，相对耗时。

本文对文献[3]的特征定义进行改进并提出了一种新的索引构建和检索方法，具有灵活、快速、准确检索的特点，能够运用在大规模运动数据库检索中。

图8 多种方法在几种不同运动类别上检索结果的P-R对比

图9所示为本文算法和文献[3,7]在不同大小的运动数据库上检索时间的对比。实验使用多个类型不同、长度均为300帧的查询片段，将每种方法在同样大小数据库下的多次检索时间求平均。由图中可以看出，在运动数据库较小时，三种方法的检索时间基本一致，但随着运动数据库的增大，文献[3]和文献[7]方法的检索时间都有明显增加。文献[7]由于每次检索都有匹配路径和相似度的计算开销，因此检索时间随数据库的增大增加尤为明显，文献[3]构建的单词查找树可以减少重复的匹配，但随数据库的增大，构建的树会大量增加，因此检索时间也有增加。而本文方法由于构建了与数据库大小无关的索引空间，而检索是在索引空间上进行的，因此数据库的增大对本文算法的检索时间没有太大影响。

图9 多种方法在不同数据库大小下的检索时间

5 结 语

本文提出一种新的运动捕获数据检索方法，通过关键帧提取和自定义的特征提取对运动数据进行有效降维，然后定义了一种记录运动数据库中所有运动姿态分布信息的索引空间；在检索阶段采用快速查询索引空间进行运动片段的匹配。本文方法构建的索引空间不依赖于数据库的大小且修改容易，检索时通过灵活地指定特征匹配可以进行不同精确程度的匹配，因此具有很好的检索性能和效果。

由于在检索时唯一的参数“需匹配特征”的指定会影响到检索结果，需要用户具有一定的先验知识，因此下一步我们的目标是自适应地针对不同类别运动匹配其突出的运动特征，达到智能检索的目的。

[1] Barnachon M, Bouakaz S, Boufama B, et al. A real-time system for motion retrieval and interpretation[J]. Pattern Recognition Letters, 2013, 34(15): 1789-1798.

[2] Wu S, Wang Z, Xia S. Indexing and retrieval of human motion data by a hierarchical tree[C]//Proceedings of the 16th ACM Symposium on Virtual Reality Software and Technology, 2009: 207-214.

[3] Kapadia M, Chiang I K, Thomas T, et al. Efficient motion retrieval in large motion databases[C]//Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. ACM, 2013: 19-28.

[4] Chao M W, Lin C H, Assa J, et al. Human motion retrieval from hand-drawn sketch[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(5): 729-740.

[5] 蓝荣祎，孙怀江，连荷清，等．人体运动捕获数据的向量空间建模与检索[J]. 计算机辅助设计与图形学学报, 2011, 23(8): 1357-1364.

[6] Wang Z, Feng Y, Qi T, et al. Adaptive multi-view feature selection for human motion retrieval[J]. Signal Processing, 2016, 120: 691-701.

[7] 潘红，肖俊，吴飞，等．基于关键帧的三维人体运动检索[J]．计算机辅助设计与图形学学报, 2009, 21(2): 214-222.

[8] 刘云根，刘金刚．重建误差最优化的运动捕获数据关键帧提取[J]．计算机辅助设计与图形学学报, 2010, 22(4): 670-675.

[9] Deng Z, Gu Q, Li Q. Perceptually consistent example-based human motion retrieval[C]//Proceedings of the 2009 Symposium on Interactive 3D Graphics and Games. ACM, 2009: 191-198.

[10] 肖伯祥，张强，魏小鹏．人体运动捕捉数据特征提取与检索研究综述[J]．计算机应用研究, 2010, 27(1): 10-13.

[11] 连荷清．人体运动捕获数据的检索方法研究[D]．南京：南京理工大学, 2013.

[12] Carnegie Mellon University. CMU Graphics Lab Motion Capture Database[EB/OL]. http://mocap.cs.cmu.edu.

[13] 刘贤梅，赵丹．面向内容的三维人体运动检索技术研究综述[J]．计算机工程与应用, 2012, 48(18): 148-153,163.

A RETRIEVAL METHOD OF 3D MOTION CAPTURE DATA BASED ON INDEX SPACE

Xu Congyang Xu Jiangfeng

(SchoolofInformationEngineering,ZhengzhouUniversity,Zhengzhou450001,Henan,China)

In order to effectively retrieve a large number of 3D human motion capture data and put it into use, this paper proposes an efficient retrieval method for the unique characteristics of 3D human motion capture data. Firstly, the original motion data dimension is reduced by key frame extraction, and then the original angle data is transformed into the feature sequence by using the customized human motion semantic feature. According to the feature sequences of all the moving segments in the database, an index space based on attitude feature is constructed. At the time of retrieval, By matching the attitude features sequentially in the index space, the matching motion fragments with the same timing are found. Experimental results show that the proposed method has better time efficiency, higher flexibility and retrieval precision than most existing methods because of better motion semantic feature extraction.

Motion capture data Motion retrieval Feature extraction Index space

2016-02-28。国家科技支撑计划项目(2014BAH09F00);国家自然科学基金项目(61379079)。徐从洋，硕士，主研领域：虚拟现实。徐江峰，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.04.025