一种通用的运动捕获数据检索方法
一种通用的运动捕获数据检索方法
【技术领域】
[0001] 本发明涉及一种通用的运动捕获数据检索方法。
【背景技术】
[0002] 运动捕获（MotionCapture)技术是一种数字化记录人体运动的技术，其中人体运 动包括全身运动和局部身体运动。运动捕获技术大大提高了动画制作的效率，而且使得人 体动画更加细致、逼真，目前已经成为人体动画制作的主流方法之一。随着运动捕获技术的 发展，运动捕获数据大量积累。如何对大量已有的运动捕获数据进行自动化的分析，高效而 准确的找到动画师想要的运动数据是计算机动画研宄领域亟待解决的关键问题。
[0003] 正如其他类型的数字媒体数据（如图片、视频）的检索一样，传统的基于文本标 注的方法只能提供有限的功能而且要耗费大量的人力和时间。因此，我们需要自动的分析 和描述每个运动捕获数据序列的内容，然后通过匹配运动数据的描述来执行基于内容的检 索。
[0004] 目前绝大多数基于内容的运动捕获检索算法所检索的对象都是整个身体的运动 数据。而且，他们假设运动对象都是具有相同骨架结构和关节标注的。在统一的骨架结构 基础上，将各个关节的关节角度信息抽取出运动特征，然后对运动特征进行相似度排序来 完成检索任务。然而，世界上不同的运动捕获系统可能会采用不同标记点粘贴方案，不同的 骨架结构和关节标注。即便是在同一个运动捕获系统下，所捕获的运动对象也不仅仅只是 演员的整个身体，也有可能捕获身体的一部分，像头部、面部、上肢、下肢等。这些运动对象 可能并不存在定义好的骨架结构。因此，研宄能工作在一个具有不同运动对象，不同标记点 粘贴方案，不同骨架结构，不同关节标注的异质运动捕获数据库中的通用运动捕获数据检 索算法是非常有必要的。但到目前为止，公开发表的能检索异质运动捕获数据的通用检索 算法几乎没有。
[0005] 既然不同的运动对象可能具有不同的骨架结构，甚至有的运动对象不存在骨架， 那么我们在检索算法中就不采用骨架信息，仅采用标记点的位置信息。但是不同运动对 象所贴的标记点数目是不同的，而且不同运动对象的标记点之间无法直接建立一一对应关 系。如何从数目不同的标记点位置信息中抽取出运动特征，并用一致性的结构进行表达是 要解决的首要问题。如何对维度不同的运动特征进行相似度比较是要解决的另一个关键性 问题。
【发明内容】
[0006] 为解决以上技术上的不足，本发明提供了一种检索效率高，而且准确率高，适用范 围广的通用的运动捕获数据检索方法。
[0007] 本发明是通过以下措施实现的：
[0008] 本发明是一种通用的运动捕获数据检索方法，包括以下步骤：
[0009] 步骤1，建立数据库，在数据库中存储若干运动捕获数据序列，并且每段运动捕获 数据序列离线计算出对应的运动签名；所述运动签名由基于整个标记点集构建的形态运动 结构MAKS图的高层描述和任意标记点对之间的低层运动学特征共同组成；运动签名是为 每一个标记点对定义一个特征向量，然后将所有点对的特征向量放在一起，形成的一个二 维矩阵；
[0010] 步骤2,将用户提交的一段运动捕获序列查询样例在线计算出与之对应的运动签 名，然后将该运动签名与数据库中存储的所有运动捕获数据序列的运动签名进行比对；
[0011] 步骤3,在数据库中找出与步骤2中在线计算出的运动签名之间距离最接近的若 干运动签名，并按照距离由小到大的顺序将与这些运动签名所对应存储在数据库中的运动 捕获序列作为查询结果集反馈给用户。
[0012] 上述在步骤1中形态运动结构MAKS图的构建包括以下步骤：
[0013] 第一步，首先基于标记点集推导出一个最小运动生成树；
[0014] 第二步，基于标记点对之间的相对运动来自适应地聚类标记点；
[0015] 第三步，根据聚类的结果修改最小运动生成树以构建形态运动结构MAKS图。
[0016] 上述在步骤1中，实现形态运动结构MAKS图的高层描述的方法是：为形态运动结 构MAKS图中的标记点对定义一个形状函数，并使用形状函数值的统计分布来描述形态运 动结构MAKS图的拓扑和几何特征；对于一对标记点叫和!!^，其形状函数的定义为 =U/L ;其中：标记点叫和m』在形态运动结构MAKS图上的最短路径距离，是路径上所有 边权重之和，记作lu;形态运动结构MAKS图上所有边的权重之和为L ;被L进行标准化后 使得形状函数具有尺度不变性，假设总共有M个标记点，那么可能的标记点对总共有T = C(M，2)对，为每一对标记点计算其形状函数值，这些形状函数值的直方图分布形成了一个 对形态运动结构MAKS图的形状分布描述符。
[0017] 上述在步骤1中，任意标记点对之间的低层运动学特征包括任意标记点对之间的 绝对运动特征和相对运动特征；
[0018] 对于绝对运动特征，在每一帧上计算点对中心点处的标量速度（vD和标量加速度 (叫）；对于相对运动特征，计算两个标记点之间在每一帧上的欧式距离（d)，相对速度（v2)， 相对加速度（a2)，相对角速度（v3)和相对角加速度（a3);
[0019] 计算上述量，获得一个具有F帧的运动捕获序列上每个标记点对的七条曲线： vjt)，ajt)，d(t)，v2(t)，a2(t)，v3(t)和a3(t)，t = 1，2,…，F;用前三个统计矩来描述每 条曲线，分别是平均值，方差和偏度；因此用21个统计量来描述每个标记点对的运动特征， 定义上述统计量为标记点对的低层运动学特征，并记它们为h，i e [1，21]。
[0020] 上述在步骤1中，将形态运动结构MAKS图的高层描述和任意标记点对之间的低层 运动学特征进行合成；假设所有可能组合的标记点对总共有T对；对于第p (1 < p < T)个 标记点对，标记它的形状函数值为sp，它的运动学特征为kp，^ 1彡i彡21 ;则第p (1彡p彡T) 个标记点对的特征向量可表示为fp= (s p, kp>1，kp，2，…，kp，21);按照特征向量的第一个成分 即形状函数值的升序排序，将所有标记点对的特征向量放在一起，最终获得了这段运动捕 获数据的运动签名。
[0021] 上述在步骤2、3中，将运动签名的注册问题转换为两个运动签名中标记点对的对 应问题，基于特征向量中的形状函数值来注册运动签名，首先在两个运动签名中寻找形状 函数值最接近的特征向量作为初始对应向量，在以初始对应向量为中心，大小为[-W，W]的 局部窗口中来搜索最佳匹配，以提高对应关系查找的鲁棒性，设定W= 7,然后计算两个运 动签名的距离，假设两个运动签名分别为S= [f\，f2，…，fP]和V= [f' ^f2，…， "^]，其中4，1￡[1，？]和"」，_]_￡[1，？']是22维的特征向量，？和1^是在对应 的两个运动签名中标记点对的个数；S和S'之间的距离用公式（1)进行计算：
[0023] 其中W是个权重向量，包含着特征向量每一维度的权重，DF(S，S'，1)如公式（2) 定义：
[0025] 在公式⑵中，h和h'是从运动签名S和S'获得的标准化形状分布直方图，DH(h， h')通过直方图求交的倒数来衡量了两个直方图之间的相似性，直方图越相似，函数值越 小；P通过最接近的形状函数值确定的初始对应向量，
[0026] 上述在步骤2、3中，通过学习来为数据库中的每一类运动数据确定一组特征权 重，以使得数据库中的正例和负例尽可能的分开；在运行时，对于一个给定的查询样例q， 它的运动签名为Sq，首先从预先学习的权重中选择权重向量Wq，然后对数据库中的每个运 动序列m，对应的运动签名为Sm，用公式（2)计算SjPSm之间每个特征分量的差异，即， DF(Sq，Sm，1)，1G[1，22];整个数据库中所有运动签名和样例运动签名之间差异在每个特 征分量或特征维度上分别进行高斯归一化；进一步地在公式（1)中带入这些高斯归一化后 的差异值和特征权重Wq，获得了从q到m的运动签名距离D(Sq，SJ;最后，数据库中所有的 运动捕获数据文件根据其与查询样例之间的运动签名距离从小到大排序，排在最前面的若 干个运动捕获数据文件作为查询结果返回。
[0027] 为一个任意给定的查询样例自动的选择合适的权重向量的方法为：通过一个二维 形状-速度直方图为一个运动捕获数据序列进行高层描述，这个直方图的两个维度分别是 形状函数值和绝对速度的平均值，直方图中的每一项代表具有特定形状函数值和绝对速度 平均值的标记点对所占的比例；每一种运动类型的形状-速度直方图是通过把训练集中所 有运动数据的形状-速度直方图做平均得到的，在运行时，计算查询样例的形状-速度直方 图，并将其与所有运动类别的形状-速度直方图进行比较，然后找到直方图最匹配的运动 类型作为查询样例的运动类型。
[0028] 本发明的有益效果是：定义了运动签名作为一种通用的运动数据表示形式，在检 索过程中不采用传统的骨架信息比对，而是采用适用范围更广的运动签名比对，对于具有 不同骨架结构和标记点数目的不同运动对象，甚至是不存在骨架的运动对象同样适用，检 索精确度高，检索速度快，适用范围广。 【附图说明】
[0029] 图1为本发明的工作流程框图。
[0030] 图2-1在第一个数据集上用算法（a)HM，（b)LR，（c)MI，⑷本专利的算法获得的 准确率-召回率曲线。
[0031] 图2-2在第一个数据集上用算法（a)HM，（b)LR，（c)MI，（d)本专利的算法获得的 混淆矩阵。
[0032] 图2-3第二个数据集上我们的算法获得的P-R曲线和混淆矩阵。
[0033] 图2-4我们的算法在第三个数据集上获得的P-R曲线和混淆矩阵。
【具体实施方式】
[0034] 下面结合附图对本发明做进一步详细的描述：
[0035] 如图1所示，本发明提出了一种通用的运动数据表示形式一运动签名：它以统计 学的角度从低层次和高层次全面描述了运动数据的形态学特征和运动学特征。不采用传 统的骨架信息比对，而是采用适用范围更广的运动签名比对，对于具有不同骨架结构的不 同运动对象，甚至是不存在骨架的运动对象同样适用。在离线状态下，先将运动数据的原 始标记点三维位置信息通过构造形态运动结构MAKS图的方式，抽取形状特征和运动学特 征，保存为运动签名的形式；当在线查询时，针对查询样例，先构造其运动签名，然后根据形 状-速度二维直方图判断它属于哪种运动类别，然后选择之前通过BDA学习到的这种运动 类别的权重系数，通过和数据库中所有运动数据的运动签名进行加权距离的计算并排序， 最后返回查询结果。
[0036] 主要包括以下步骤：
[0037] 步骤1，建立数据库，在数据库中存储若干运动捕获数据序列，并且每段运动捕获 数据序列离线计算出对应的运动签名；所述运动签名由基于整个标记点集构建的形态运动 结构MAKS图的高层描述和任意标记点对之间的低层运动学特征共同组成；运动签名是为 每一个标记点对定义一个特征向量，然后将所有点对的特征向量放在一起，形成的一个二 维矩阵；
[0038] 步骤2,将用户提交的一段运动捕获序列查询样例在线计算出与之对应的运动签 名，然后将该运动签名与数据库中存储的所有运动捕获数据序列的运动签名进行比对；
[0039] 步骤3,在数据库中找出与步骤2中在线计算出的运动签名之间距离最接近的若 干运动签名，并按照距离由小到大的顺序将与这些运动签名所对应存储在数据库中的运动 捕获序列作为查询结果集反馈给用户。
[0040] 一、构建形态运动结构MAKS图；
[0041] 一段运动捕获数据序列包含所有标记点的几何位置随时间的变化情况。当把标记 点位置视为一个整体的时候，它往往能反映出运动物体的形态。所有单独的标记点位置随 时间变化的情况合在一起可以定义运动物体的运动。相应的，我们构建运动签名来描述一 段运动捕获数据序列的形态学和运动学特点。我们首先抽取和描述一个图结构，它能高层 次提取运动中物体的形态学和运动学特点。以这个图作指导，我们描述在标记点对之间的 低层次运动学特征。所有这些高层次和低层次描述合起来形成了运动签名。
[0042] 我们希望构建出来的结构图能具有和真实的形态结构类似的结构（例如，骨架结 构），并且能同时反映出物体运动的整体运动学特点。因此，这个图被命名为形态运动结构 MAKS图(morphologicalandkinematicstructuregraph,MAKSgraph)。它是基于整个 标记点集来建的。
[0043] 构建形态运动结构MAKS图主要分为三步。第一步，基于标记点我们先推导出一个 最小运动生成树。第二步，我们基于标记点对之间的相对运动来自适应的聚类标记点。第 三步，我们根据聚类的结果修改最小运动生成树以产生MAKS图。
[0044] 其中最小运动生成树的推导方法是：我们先在所有标记点上构造一个全图，图中 任意两个结点之间存在一条边，边的权重为两个标记点在所有帧上距离的标准差。然后，我 们将基于这个全图抽取的最小生成树命名为最小运动生成树。最小运动生成树也反映了运 动捕获数据的全局运动学特点，因为它粗略的表达了标记点之间运动相关性的配置情况。 运动上高度相关的标记点对之间有一条边相连，而运动上相关度不大的标记点对之间则没 有边相连。
[0045]自适应标记点聚类方法是：我们采用谱聚类算法将标记点划分为不同的聚类，在 每一个聚类中使标记点之间的相对运动最小。我们用高斯函数来定义两个标记点％和 之间的相似度，如公式（3)所示，
[0047] 其中，STDOvnij)2是标记点mJPm』在所有帧上欧式距离的标准差。参数〇是通 过自调节技术设置的。我们为一个聚类结果先定义了一个成本测度，C:
[0049] 其中Ug是第g个聚类的标记点集合，K是聚类的数目。成本C越小，聚类中标记 点之间的关联性越高。我们迭代的执行谱聚类，在每一次迭代中，根据公式（4)计算聚类成 本。如果聚类成本已经低于一定的阈值，或迭代次数达到上限，就终止迭代；反之，增加K的 值，进入下一次循环。
[0050] 对于每个聚类中的标记点，我们将在最小运动生成树中修改对应的部分。如果一 个聚类包含多于一个标记点，我们在这个聚类中增加一个虚拟点，每一帧虚拟点位于这个 聚类中所有标记点的中心；否则，我们就不在此聚类中增加虚拟点。相应的，我们在最小运 动生成树上增加一个结点。接着，如果在最小运动生成树上，同一聚类中的标记点之间有边 连接的话，就把这些边删掉，然后增加连接虚拟结点和此聚类中所有标记点之间的边。最 后，对于改动后的树上的所有边，我们计算连接此边的两个结点在所有帧上的平均距离，并 将其作为此边的权重。
[0051 ] 一、运动签名；
[0052] 运动捕获数据的运动签名是由形态运动结构MAKS图的高层描述和任意标记点对 之间的低层运动学特征共同组成。
[0053] 对于形态运动结构MAKS图的高层描述，我们为MAKS图中的标记点对定义一个形 状函数，并使用形状函数值的统计分布来描述MAKS图的拓扑和几何特征。对于一对标记点 mdPm」，它们在MAKS图上的最短路径距离，是路径上所有边权重之和，记作li;j。MAKS图上 所有边的权重之和为L。我们定义标记点叫和111』对应的形状函数为sOi^nij) =li;j/L。被 L进行标准化后使得形状函数具有尺度不变性。假设总共有M个标记点，那么可能的标记点 对总共有T=C(M，2)对，我们为每一对标记点计算其形状函数值。这些形状函数值的直方 图分布形成了一个对MAKS图的形状分布描述符。
[0054] 对于任意标记点对之间的低层运动学特征，我们用一系列的量来描述标记点对的 绝对运动特征和相对运动特征。对于绝对运动特征，我们在每一帧上计算点对中心点处的 标量速度（Vl)和标量加速度（％);对于相对运动特征，我们计算两个标记点之间在每一帧 上的欧式距离（d)，相对速度（v2)，相对加速度（a2)，相对角速度（v3)和相对角加速度（a3)。 通过计算这些量，我们获得了一个具有F帧的运动捕获序列上每个标记点对的七条曲线： vjt)，a! (t)，d(t)，v2(t)，a2(t)，v3(t)和a3(t)，t = 1，2,…，F〇我们用前三个统计矩来描 述每条曲线，分别是平均值，方差和偏度。因此，我们用了21个统计量来描述每个标记点对 的运动特征。我们称这些量为标记点对的运动学特征，并记它们为h，i e [1，21]。
[0055] 最后，我们合成了高层次描述和低层次描述，共同组成了运动签名。运动签名实质 上是为每一个标记点对定义一个特征向量，然后将所有点对的特征向量放在一起，形成的 一个二维矩阵。假设所有可能组合的标记点对总共有T对。对于第p (1 < p < T)个标记点 对，我们标记它的形状函数值为sp，它的运动学特征为kp，i，1彡i彡21。则第p (1彡p彡T) 个标记点对的特征向量可表示为fp= (s p, kp>1，kp，2，…，kp，21)。按照特征向量的第一个成分 (形状函数值）的升序排序，将所有标记点对的特征向量放在一起，我们最终获得了这段运 动捕获数据的运动签名。
[0056] 三、比对过程中要解决的两个主要问题；
[0057] 1)由于每个运动文件中标记点数目有可能不同，因此导致运动签名中特征向量的 维度不同。怎样处理两个运动签名的维度不一致问题？
[0058] 2)对于给定的查询样例，如何优化的确定不同特征的权重，以使得数据库中的正 例和负例尽可能的分开？
[0059] 为了解决第一个问题，我们提出基于特征向量中的形状函数值来注册两个运动签 名的方法。为了解决第二个问题，我们为每一种运动类型预先学习一套优化的权重，在运行 时针对任意给定的查询样例自适应的选择一组权重。
[0060] 我们计算查询样例的运动签名和数据库中所有运动捕获数据的运动签名之间的 距离，并将其按升序进行排序作为查询结果返回。
[0061] 运动签名的对应问题本质上是标记点对的对应问题，即，为一个运动序列中的标 记点对到另一个运动序列中找对应的标记点对。如果两个运动序列非常相似，那么它们将 会有相似的MAKS图，对应的标记点对也将有相似的形状函数值。因此，在 运动签名A中，一 个形状函数值为s的特征向量，我们可以通过在运动签名B中找形状函数值接近于s的特 征向量与之对应。高效的折半查找可以完成搜索任务，因为在构造运动签名时其中的特征 向量已经按照形状函数值的升序排序存放了。
[0062] 然而，对应的标记点对的形状函数值有可能存在统计差别，在同一个MAKS图中不 同的标记点对也可能具有相同的形状函数值。因此，仅使用最接近的形状函数值来找标记 点对的对应关系并不总能可靠的得到正确结果。为提高鲁棒性，当建立标记点对之间的对 应关系时，我们在一个局部窗口中进行搜索而不是全局搜索最匹配的。
[0063] 假设有两个运动签名，分别为S = [f\，f2，…，fP]和S' = [f' ^ f'2，…， "^]，其中4，1￡[1，？]和"」，_]_￡[1，？']是22维的特征向量，？和1^是在对应 的两个运动签名中标记点对的个数。S和S'之间的距离用公式（1)进行计算，
[0065] 其中W是个权重向量，包含着特征向量每一维度的权重，DF(S，S'，1)如公式（2) 定义，
[0067]在公式⑵中，h和h'是从运动签名S和S'获得的标准化形状分布直方图，DH(h，h')通过直方图求交的倒数来衡量了两个直方图之间的相似性，直方图越相似，函数值越 小；(/^)是4江'P通过最接近的形状函数值确定的初始对应向量。为提高对应关系 查找的鲁棒性，我们在以初始对应向量为中心，大小为[_w，w]的局部窗口中来搜索最佳匹 配，计算方法如公式（2)所示。在实际实验中，我们设w = 7。
[0068]我们提出通过学习来为数据库中的每一类运动数据确定一组特征权重。对于每一 种运动类型，一定比例（我们的实验中取50%)的运动数据被选为训练集。一开始先设置 一个初始的权重向量W，然后通过迭代逐步优化。在每一次迭代过程中，我们用训练集中的 每一个运动数据作为查询样例执行基于内容的检索，从返回的查询结果中选择一定比例的 正例和负例。所有这些查询样例的正例构成了一个大的正例集合，所有这些查询样例的负 例构成了一个大的负例集合。大的正例集合和负例集合共同通过有偏判别分析（BDA)来学 习优化的权重向量W。如果两次迭代得到的W差别很小或迭代次数达到上限，那么迭代将会 结束。
[0069]在运行时，对于一个给定的查询样例q，它的运动签名为Sq，我们首先从预先学习 的权重中选择权重向量^。然后，对数据库中的每个运动序列m，对应的运动签名为Sm，我 们用公式（2)计算SjPSm之间每个特征分量的差异，S卩，DF(Sq，Sm，1)，1 e [1，22]。整个 数据库中所有运动签名和样例运动签名之间差异在每个特征分量或特征维度上分别进行 高斯归一化。进一步的，在公式（1)中带入这些高斯归一化后的差异值和特征权重Wq，我们 获得了从q到m的运动签名距离D(Sq，Sm)。最后，数据库中所有的运动捕获数据文件根据 其与查询样例之间的运动签名距离从小到大排序，排在最前面的若干个运动捕获数据文件 作为查询结果返回。在这个过程中最主要的挑战是为一个任意给定的查询样例自动的选择 合适的权重向量。我们通过一个二维形状-速度直方图为一个运动捕获数据序列进行高层 描述。这个直方图的两个维度分别是形状函数值和绝对速度的平均值，直方图中的每一项 代表具有特定形状函数值和绝对速度平均值的标记点对所占的比例。每一种运动类型的形 状-速度直方图是通过把训练集中所有运动数据的形状-速度直方图做平均得到的。在运 行时，我们计算查询样例的形状-速度直方图，并将其与所有运动类别的形状-速度直方图 进行比较，然后找到直方图最匹配的运动类型作为查询样例的运动类型。
[0070] 当计算两个运动签名之间的距离时，我们为运动签名中不同的特征赋予不同的权 重。我们事先在训练数据库上用有偏判别分析的方法为每种运动类型学习一组特征权重， 在查询时，基于运动数据的二维直方图来自适应的选择一套合适的权重。
[0071] 四、对比试验；
[0072]我们分别在三个数据集上做了四组实验，详细描述如下。
[0073] 第一个数据集。第一个实验是想和近期业界有代表性的查询算法比较查询性能， 因此我们使用了 HDM05数据库中人体运动捕获数据的一个子集作为第一个数据集。第一个 数据集包含了从HDM05数据库中挑选的七类不同运动类型的运动序列，分别是侧手翻（简 写为"cwheel"），肘碰膝（简写为"eTok"），跳（简写为"hop"），跳爆竹（简写为"jjack"）， 击拳（简写为" punch"），下蹲（简写为" squat"）以及走（简写为" walk"）。每一类运动 包含20个运动序列，总共数据库中有140个运动序列，共计27322帧。
[0074] 第二个数据集。第二个实验是想考察我们的算法在异质数据库中的查询性能。因 此，我们第二个数据集是个混合数据库，数据分别来自CMU数据库，HDM05数据库以及我们 自己用Vicon光学运动捕获系统捕获的运动数据。第二个数据集中共包含六种类型的运 动，分别是肘碰膝（简写为" eTok"），跳（简写为" hop"），跳爆竹（简写为" jjack"），演奏 乐器（简写为" pmi"），下蹲（简写为" squat"）以及走（简写为" walk"）。每一类运动包 含20个运动序列，数据库中有120个运动序列，共计22404帧。在捕获每一类运动时，我们 用了两位男演员和两位女演员来分别表演动作。总之，在这个数据集中的运动序列是来自 具有不同的贴点方式和骨架模板的数据源。
[0075] 第三个数据集。第三个数据集是用来展示我们的算法在检索由不同种运动对象 所做的运动时的性能。第三个数据集中的数据都是由我们自己捕获的。有的运动数据是 来自整个身体的，有的是来自身体的某一部分，例如头部、肩部、胳膊和腿部。这些运动 一共可以分为七种运动类型，分别是扭手腕（胳膊，简写为" atwist"），挥手（胳膊，简写 为" awave"），打羽毛球（全身，简写为" bbmt"），点头（胳膊，简写为" awave"），踢腿（腿 部，简写为" lkick"），下蹲（腿部，简写为" lsquat"）和耸肩（肩部，简写为" sshake"），每 种类型各自包含20个运动序列。在捕获每种运动类型时，我们采用了两位男演员和两位女 演员分别做动作。在这个数据集中，总共有140个运动序列，共计41688帧。
[0076] 我们将自己的算法与基于运动检索树的方法（简写为"MI"），基于低秩分解的方 法（简写为"LR"）和基于等级化模型的方法（简写为"HM"）在相同的数据集上做实验并 详细报告、分析了在不同测度下各种算法的查询性能表现。
[0077] 我们使用的性能测度包括信息检索领域常用的TPR，准确率-召回率曲线（P-R curve)，平均准确率（MAP)。TPR是在前N个检索结果中和查询样例类别相同所占的比例， 即在前N个检索结果的准确率，这里我们设N = 20。另外，我们还使用了混淆矩阵作为性能 评价测度。
[0078]结果与分析：
[0079]在实验中，算法MI，LR和HM仅在第一个数据集上获得了检索结果，因为他们都无 法处理像第二个和第三个数据集那样的异质运动捕获数据库。我们的算法则能够处理全部 三个数据集。在评估每个算法的检索性能时，我们用数据集中的每个运动序列作一次查询 样例，所有返回的查询结果集合在一起用于查询性能测度的计算。
[0080] 表2-1在第一个数据集上用我们有权重学习的算法，我们没有权重学习的算法， HM，LR，MI，获得的七类运动的TPR统计量
[0081]
[0082] 第一个实验。在第一个数据集上，执行了算法MI，算法LR，算法HM，并与我们的算 法进行比较。进一步的，我们关掉特征权重优化的部分，将所有的特征权重设为1，重新在 第一个数据集上获得查询结果。如表2.1所示，通过统计五个算法（算法MI，算法LR，算法 HM，我们的算法带权重学习模块，我们的算法即使没有权重学习模块，其在七类运动上的平 均查询准确率也已经超过了其他三种算法。增加权重学习之后，我们的算法查询准确率得 到了很大的提高，明显超过了其他三种算法。在图2-1中展示了算法MI，算法LR，算法HM 以及我们的算法在不同运动类型上的P-R曲线。从图2-1中可以观察到我们的算法在七类 运动上平均的准确率 -召回率曲线拥有最大的曲线下面积（area under curve，AUC)。在表 2-2和图2-2中分别显示了算法MI，算法LR，算法HM以及我们的算法的MAP统计量和混淆 矩阵。再一次观察到，我们的算法在查询准确率上明显优于其他算法。
[0083] 表2-2在第一个数据集上用算法MI，LR，HM，我们的算法获得的七类运动的MAP统 计量：
[0085]第二个实验。我们在第二个数据集上执行查询算法，获得了在不同查询性能测度 下的统计量。因为第二个数据集中的运动捕获数据在捕获时，采用了不同的坐标系，不同的 贴点方案以及不同的骨架模板。而现有的算法需要有一个统一的骨架模板，无法处理这种 异质的数据库。因此第二个实验仅仅给出我们算法的查询结果。P-R曲线和混淆矩阵显示 在图2-3中。从图2 -3中可以看出，我们的算法在异质运动数据库上取得了很高的查询准 确率，大部分超过95 %甚至达到100%。
[0086] 第三个实验。我们在第三个数据集上执行查询算法，获得了在不同查询性能测度 下的统计量。据我们所知，尚没有公开发表的算法能对全身运动和局部身体运动统一进行 检索，而第三个数据集包含了不同运动物体（全身、头部、上肢、下肢）的混合运动，因此，我 们仅获得了我们的算法在第三个数据集上的查询结果。在图2-4中给出了 P-R曲线和混淆 矩阵。第三个数据集中涉及的运动对象差别很大，我们的算法仍然获得了很高的查询准确 率，七种运动类型的查询准确率都在90 %左右。
[0087] 时间统计
[0088] 我们在VS2010环境下实现了算法，在一个配置有Intel Core Duo2. 93GHz CPU和 4GB内存的台式机上，获得了以下运行时间统计数据。在每一个数据集上，我们分为预处理 时间（运动签名生成），权重学习时间，平均查询时间（通过多次随机选取查询样例执行查 询的总时间，再进行平均而得到）。在表2-3中，我们展示了在三个数据集上预处理、权重 学习和查询的时间代价。从表2-3可以看出，我们的算法在第三个数据集上的查询效率最 高。这是因为查询时间代价与运动序列上的标记点对个数是成正比的。第三个数据集中 所包含的运动序列是对应局部身体的运动，局部身体上所贴的标记点相比整个身体要少得 多。
[0089]表2-3我们的算法在三个数据集上的时间统计：
[0091] 以上所述仅是本专利的优选实施方式，应当指出，对于本技术领域的普通技术人 员来说，在不脱离本专利技术原理的前提下，还可以做出若干改进和替换，这些改进和替换 也应视为本专利的保护范围。
【主权项】
1. 一种通用的运动捕获数据检索方法，其特征在于，包括以下步骤： 步骤1，建立数据库，在数据库中存储若干运动捕获数据序列，并且每段运动捕获数据 序列离线计算出对应的运动签名；所述运动签名由基于整个标记点集构建的形态运动结构 MKS图的高层描述和任意标记点对之间的低层运动学特征共同组成；运动签名是为每一 个标记点对定义一个特征向量，然后将所有点对的特征向量放在一起，形成的一个二维矩 阵； 步骤2,将用户提交的一段运动捕获序列查询样例在线计算出与之对应的运动签名，然 后将该运动签名与数据库中存储的所有运动捕获数据序列的运动签名进行比对； 步骤3,在数据库中找出与步骤2中在线计算出的运动签名之间距离最接近的若干运 动签名，并按照距离由小到大的顺序将与这些运动签名所对应存储在数据库中的运动捕获 序列作为查询结果集反馈给用户。2. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于：在步骤1中形态 运动结构MKS图的构建包括以下步骤： 第一步，首先基于标记点集推导出一个最小运动生成树； 第二步，基于标记点对之间的相对运动来自适应地聚类标记点； 第三步，根据聚类的结果修改最小运动生成树以构建形态运动结构MKS图。3. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于，在步骤1中，实现 形态运动结构MKS图的高层描述的方法是：为形态运动结构MKS图中的标记点对定义一 个形状函数，并使用形状函数值的统计分布来描述形态运动结构MAKS图的拓扑和几何特 征；对于一对标记点IHi和％，其形状函数的定义为= Ii, j/L ;其中：标记点叫和Hij在形态运动结构MAKS图上的最短路径距离，是路径上所有边权重之和，记作Iu;形态运动 结构MKS图上所有边的权重之和为L ;被L进行标准化后使得形状函数具有尺度不变性， 假设总共有M个标记点，那么可能的标记点对总共有T = C(M，2)对，为每一对标记点计算 其形状函数值，这些形状函数值的直方图分布形成了一个对形态运动结构MKS图的形状 分布描述符。4. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于，在步骤1中，任 意标记点对之间的低层运动学特征包括任意标记点对之间的绝对运动特征和相对运动特 征； 对于绝对运动特征，在每一帧上计算点对中心点处的标量速度（V1)和标量加速度 (?);对于相对运动特征，计算两个标记点之间在每一帧上的欧式距离（d)，相对速度（V2)， 相对加速度（a2)，相对角速度（V3)和相对角加速度（a3); 计算上述量，获得一个具有F帧的运动捕获序列上每个标记点对的七条曲线：Vl (t)， ajt)，d(t)，v2(t)，a2(t)，v3(t)和a3(t)，t = 1，2,…，F ;用前三个统计矩来描述每条曲线， 分别是平均值，方差和偏度；因此用21个统计量来描述每个标记点对的运动特征，定义上 述统计量为标记点对的低层运动学特征，并记它们为kpi e [1，21]。5. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于，在步骤1中，将形 态运动结构MKS图的高层描述和任意标记点对之间的低层运动学特征进行合成；假设所 有可能组合的标记点对总共有T对；对于第p(l < p < T)个标记点对，标记它的形状函数 值为sp，它的运动学特征为kp，i，1彡i彡21 ;则第p (1彡p彡T)个标记点对的特征向量可 表示为&=(81)，、1，、2，一，、21);按照特征向量的第一个成分即形状函数值的升序排序， 将所有标记点对的特征向量放在一起，最终获得了这段运动捕获数据的运动签名。6. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于：在步骤2、3中，将 运动签名的注册问题转换为两个运动签名中标记点对的对应问题，基于特征向量中的形状 函数值来注册运动签名，首先在两个运动签名中寻找形状函数值最接近的特征向量作为初 始对应向量，在以初始对应向量为中心，大小为[-W，W]的局部窗口中来搜索最佳匹配，以 提高对应关系查找的鲁棒性，设定W = 7,然后计算两个运动签名的距离，假设两个运动签 名分别为3=[4,4，一，心]和5'=[广1，广2，一，广1),]，其中4，1￡[1，？]和 f j，je [1，]是22维的特征向量，P和P是在对应的两个运动签名中标记点对的 个数；S和S'之间的距离用公式（1)进行计算：⑴ 其中W是个权重向量，包含着特征向量每一维度的权重，DF(S，S^，1)如公式（2)定义：在公式（2)中，h和h'是从运动签名S和S'获得的标准化形状分布直方图，DH(h， h')通过直方图求交的倒数来衡量了两个直方图之间的相似性，直方图越相似，函数值越 小；(Iij >是4江'P通过最接近的形状函数值确定的初始对应向量。7. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于：在步骤2、3中，通 过学习来为数据库中的每一类运动数据确定一组特征权重，以使得数据库中的正例和负例 尽可能的分开；在运行时，对于一个给定的查询样例q，它的运动签名为S,，首先从预先学习 的权重中选择权重向量W,，然后对数据库中的每个运动序列m，对应的运动签名为Sm，用公 式（2)计算5,和5"1之间每个特征分量的差异，8卩，0"\，5111，1)，1￡[1，22];整个数据库中 所有运动签名和样例运动签名之间差异在每个特征分量或特征维度上分别进行高斯归一 化；进一步地在公式（1)中带入这些高斯归一化后的差异值和特征权重W,，获得了从q到 m的运动签名距离D(S,，Sm);最后，数据库中所有的运动捕获数据文件根据其与查询样例之 间的运动签名距离从小到大排序，排在最前面的若干个运动捕获数据文件作为查询结果返 回。8. 根据权利要求7所述通用的运动捕获数据检索方法，其特征在于：为一个任意给定 的查询样例自动的选择合适的权重向量的方法为：通过一个二维形状-速度直方图为一个 运动捕获数据序列进行高层描述，这个直方图的两个维度分别是形状函数值和绝对速度的 平均值，直方图中的每一项代表具有特定形状函数值和绝对速度平均值的标记点对所占的 比例；每一种运动类型的形状-速度直方图是通过把训练集中所有运动数据的形状-速度 直方图做平均得到的，在运行时，计算查询样例的形状-速度直方图，并将其与所有运动类 别的形状-速度直方图进行比较，然后找到直方图最匹配的运动类型作为查询样例的运动 类型。
【专利摘要】一种通用的运动捕获数据检索方法。本发明提出了一种通用的运动数据表示形式—运动签名：它以统计学的角度从低层次和高层次全面描述了运动数据的形态学特征和运动学特征。在离线状态下，先将运动数据的原始标记点三维位置信息通过构造形态运动结构MAKS图的方式，抽取形状特征和运动学特征，保存为运动签名的形式；当在线查询时，针对查询样例，先构造其运动签名，然后根据形状-速度二维直方图判断它属于哪种运动类别，然后选择之前通过BDA学习到的这种运动类别的权重系数，通过和数据库中所有运动数据的运动签名进行加权距离的计算并排序，最后返回查询结果。本发明的有益效果是：采用适用范围更广的运动签名比对，检索精确度高，检索速度快，适用范围广。
【IPC分类】G06F17/30
【公开号】CN104899248
【申请号】CN201510204348
【发明人】吕娜, 冯志全, 彭京亮
【申请人】济南大学
【公开日】2015年9月9日
【申请日】2015年4月24日
【技术领域】
[0001] 本发明涉及一种通用的运动捕获数据检索方法。
【背景技术】
[0002] 运动捕获（MotionCapture)技术是一种数字化记录人体运动的技术，其中人体运 动包括全身运动和局部身体运动。运动捕获技术大大提高了动画制作的效率，而且使得人 体动画更加细致、逼真，目前已经成为人体动画制作的主流方法之一。随着运动捕获技术的 发展，运动捕获数据大量积累。如何对大量已有的运动捕获数据进行自动化的分析，高效而 准确的找到动画师想要的运动数据是计算机动画研宄领域亟待解决的关键问题。
[0003] 正如其他类型的数字媒体数据（如图片、视频）的检索一样，传统的基于文本标 注的方法只能提供有限的功能而且要耗费大量的人力和时间。因此，我们需要自动的分析 和描述每个运动捕获数据序列的内容，然后通过匹配运动数据的描述来执行基于内容的检 索。
[0004] 目前绝大多数基于内容的运动捕获检索算法所检索的对象都是整个身体的运动 数据。而且，他们假设运动对象都是具有相同骨架结构和关节标注的。在统一的骨架结构 基础上，将各个关节的关节角度信息抽取出运动特征，然后对运动特征进行相似度排序来 完成检索任务。然而，世界上不同的运动捕获系统可能会采用不同标记点粘贴方案，不同的 骨架结构和关节标注。即便是在同一个运动捕获系统下，所捕获的运动对象也不仅仅只是 演员的整个身体，也有可能捕获身体的一部分，像头部、面部、上肢、下肢等。这些运动对象 可能并不存在定义好的骨架结构。因此，研宄能工作在一个具有不同运动对象，不同标记点 粘贴方案，不同骨架结构，不同关节标注的异质运动捕获数据库中的通用运动捕获数据检 索算法是非常有必要的。但到目前为止，公开发表的能检索异质运动捕获数据的通用检索 算法几乎没有。
[0005] 既然不同的运动对象可能具有不同的骨架结构，甚至有的运动对象不存在骨架， 那么我们在检索算法中就不采用骨架信息，仅采用标记点的位置信息。但是不同运动对 象所贴的标记点数目是不同的，而且不同运动对象的标记点之间无法直接建立一一对应关 系。如何从数目不同的标记点位置信息中抽取出运动特征，并用一致性的结构进行表达是 要解决的首要问题。如何对维度不同的运动特征进行相似度比较是要解决的另一个关键性 问题。
【发明内容】
[0006] 为解决以上技术上的不足，本发明提供了一种检索效率高，而且准确率高，适用范 围广的通用的运动捕获数据检索方法。
[0007] 本发明是通过以下措施实现的：
[0008] 本发明是一种通用的运动捕获数据检索方法，包括以下步骤：
[0009] 步骤1，建立数据库，在数据库中存储若干运动捕获数据序列，并且每段运动捕获 数据序列离线计算出对应的运动签名；所述运动签名由基于整个标记点集构建的形态运动 结构MAKS图的高层描述和任意标记点对之间的低层运动学特征共同组成；运动签名是为 每一个标记点对定义一个特征向量，然后将所有点对的特征向量放在一起，形成的一个二 维矩阵；
[0010] 步骤2,将用户提交的一段运动捕获序列查询样例在线计算出与之对应的运动签 名，然后将该运动签名与数据库中存储的所有运动捕获数据序列的运动签名进行比对；
[0011] 步骤3,在数据库中找出与步骤2中在线计算出的运动签名之间距离最接近的若 干运动签名，并按照距离由小到大的顺序将与这些运动签名所对应存储在数据库中的运动 捕获序列作为查询结果集反馈给用户。
[0012] 上述在步骤1中形态运动结构MAKS图的构建包括以下步骤：
[0013] 第一步，首先基于标记点集推导出一个最小运动生成树；
[0014] 第二步，基于标记点对之间的相对运动来自适应地聚类标记点；
[0015] 第三步，根据聚类的结果修改最小运动生成树以构建形态运动结构MAKS图。
[0016] 上述在步骤1中，实现形态运动结构MAKS图的高层描述的方法是：为形态运动结 构MAKS图中的标记点对定义一个形状函数，并使用形状函数值的统计分布来描述形态运 动结构MAKS图的拓扑和几何特征；对于一对标记点叫和!!^，其形状函数的定义为 =U/L ;其中：标记点叫和m』在形态运动结构MAKS图上的最短路径距离，是路径上所有 边权重之和，记作lu;形态运动结构MAKS图上所有边的权重之和为L ;被L进行标准化后 使得形状函数具有尺度不变性，假设总共有M个标记点，那么可能的标记点对总共有T = C(M，2)对，为每一对标记点计算其形状函数值，这些形状函数值的直方图分布形成了一个 对形态运动结构MAKS图的形状分布描述符。
[0017] 上述在步骤1中，任意标记点对之间的低层运动学特征包括任意标记点对之间的 绝对运动特征和相对运动特征；
[0018] 对于绝对运动特征，在每一帧上计算点对中心点处的标量速度（vD和标量加速度 (叫）；对于相对运动特征，计算两个标记点之间在每一帧上的欧式距离（d)，相对速度（v2)， 相对加速度（a2)，相对角速度（v3)和相对角加速度（a3);
[0019] 计算上述量，获得一个具有F帧的运动捕获序列上每个标记点对的七条曲线： vjt)，ajt)，d(t)，v2(t)，a2(t)，v3(t)和a3(t)，t = 1，2,…，F;用前三个统计矩来描述每 条曲线，分别是平均值，方差和偏度；因此用21个统计量来描述每个标记点对的运动特征， 定义上述统计量为标记点对的低层运动学特征，并记它们为h，i e [1，21]。
[0020] 上述在步骤1中，将形态运动结构MAKS图的高层描述和任意标记点对之间的低层 运动学特征进行合成；假设所有可能组合的标记点对总共有T对；对于第p (1 < p < T)个 标记点对，标记它的形状函数值为sp，它的运动学特征为kp，^ 1彡i彡21 ;则第p (1彡p彡T) 个标记点对的特征向量可表示为fp= (s p, kp>1，kp，2，…，kp，21);按照特征向量的第一个成分 即形状函数值的升序排序，将所有标记点对的特征向量放在一起，最终获得了这段运动捕 获数据的运动签名。
[0021] 上述在步骤2、3中，将运动签名的注册问题转换为两个运动签名中标记点对的对 应问题，基于特征向量中的形状函数值来注册运动签名，首先在两个运动签名中寻找形状 函数值最接近的特征向量作为初始对应向量，在以初始对应向量为中心，大小为[-W，W]的 局部窗口中来搜索最佳匹配，以提高对应关系查找的鲁棒性，设定W= 7,然后计算两个运 动签名的距离，假设两个运动签名分别为S= [f\，f2，…，fP]和V= [f' ^f2，…， "^]，其中4，1￡[1，？]和"」，_]_￡[1，？']是22维的特征向量，？和1^是在对应 的两个运动签名中标记点对的个数；S和S'之间的距离用公式（1)进行计算：
[0023] 其中W是个权重向量，包含着特征向量每一维度的权重，DF(S，S'，1)如公式（2) 定义：
[0025] 在公式⑵中，h和h'是从运动签名S和S'获得的标准化形状分布直方图，DH(h， h')通过直方图求交的倒数来衡量了两个直方图之间的相似性，直方图越相似，函数值越 小；P通过最接近的形状函数值确定的初始对应向量，
[0026] 上述在步骤2、3中，通过学习来为数据库中的每一类运动数据确定一组特征权 重，以使得数据库中的正例和负例尽可能的分开；在运行时，对于一个给定的查询样例q， 它的运动签名为Sq，首先从预先学习的权重中选择权重向量Wq，然后对数据库中的每个运 动序列m，对应的运动签名为Sm，用公式（2)计算SjPSm之间每个特征分量的差异，即， DF(Sq，Sm，1)，1G[1，22];整个数据库中所有运动签名和样例运动签名之间差异在每个特 征分量或特征维度上分别进行高斯归一化；进一步地在公式（1)中带入这些高斯归一化后 的差异值和特征权重Wq，获得了从q到m的运动签名距离D(Sq，SJ;最后，数据库中所有的 运动捕获数据文件根据其与查询样例之间的运动签名距离从小到大排序，排在最前面的若 干个运动捕获数据文件作为查询结果返回。
[0027] 为一个任意给定的查询样例自动的选择合适的权重向量的方法为：通过一个二维 形状-速度直方图为一个运动捕获数据序列进行高层描述，这个直方图的两个维度分别是 形状函数值和绝对速度的平均值，直方图中的每一项代表具有特定形状函数值和绝对速度 平均值的标记点对所占的比例；每一种运动类型的形状-速度直方图是通过把训练集中所 有运动数据的形状-速度直方图做平均得到的，在运行时，计算查询样例的形状-速度直方 图，并将其与所有运动类别的形状-速度直方图进行比较，然后找到直方图最匹配的运动 类型作为查询样例的运动类型。
[0028] 本发明的有益效果是：定义了运动签名作为一种通用的运动数据表示形式，在检 索过程中不采用传统的骨架信息比对，而是采用适用范围更广的运动签名比对，对于具有 不同骨架结构和标记点数目的不同运动对象，甚至是不存在骨架的运动对象同样适用，检 索精确度高，检索速度快，适用范围广。 【附图说明】
[0029] 图1为本发明的工作流程框图。
[0030] 图2-1在第一个数据集上用算法（a)HM，（b)LR，（c)MI，⑷本专利的算法获得的 准确率-召回率曲线。
[0031] 图2-2在第一个数据集上用算法（a)HM，（b)LR，（c)MI，（d)本专利的算法获得的 混淆矩阵。
[0032] 图2-3第二个数据集上我们的算法获得的P-R曲线和混淆矩阵。
[0033] 图2-4我们的算法在第三个数据集上获得的P-R曲线和混淆矩阵。
【具体实施方式】
[0034] 下面结合附图对本发明做进一步详细的描述：
[0035] 如图1所示，本发明提出了一种通用的运动数据表示形式一运动签名：它以统计 学的角度从低层次和高层次全面描述了运动数据的形态学特征和运动学特征。不采用传 统的骨架信息比对，而是采用适用范围更广的运动签名比对，对于具有不同骨架结构的不 同运动对象，甚至是不存在骨架的运动对象同样适用。在离线状态下，先将运动数据的原 始标记点三维位置信息通过构造形态运动结构MAKS图的方式，抽取形状特征和运动学特 征，保存为运动签名的形式；当在线查询时，针对查询样例，先构造其运动签名，然后根据形 状-速度二维直方图判断它属于哪种运动类别，然后选择之前通过BDA学习到的这种运动 类别的权重系数，通过和数据库中所有运动数据的运动签名进行加权距离的计算并排序， 最后返回查询结果。
[0036] 主要包括以下步骤：
[0037] 步骤1，建立数据库，在数据库中存储若干运动捕获数据序列，并且每段运动捕获 数据序列离线计算出对应的运动签名；所述运动签名由基于整个标记点集构建的形态运动 结构MAKS图的高层描述和任意标记点对之间的低层运动学特征共同组成；运动签名是为 每一个标记点对定义一个特征向量，然后将所有点对的特征向量放在一起，形成的一个二 维矩阵；
[0038] 步骤2,将用户提交的一段运动捕获序列查询样例在线计算出与之对应的运动签 名，然后将该运动签名与数据库中存储的所有运动捕获数据序列的运动签名进行比对；
[0039] 步骤3,在数据库中找出与步骤2中在线计算出的运动签名之间距离最接近的若 干运动签名，并按照距离由小到大的顺序将与这些运动签名所对应存储在数据库中的运动 捕获序列作为查询结果集反馈给用户。
[0040] 一、构建形态运动结构MAKS图；
[0041] 一段运动捕获数据序列包含所有标记点的几何位置随时间的变化情况。当把标记 点位置视为一个整体的时候，它往往能反映出运动物体的形态。所有单独的标记点位置随 时间变化的情况合在一起可以定义运动物体的运动。相应的，我们构建运动签名来描述一 段运动捕获数据序列的形态学和运动学特点。我们首先抽取和描述一个图结构，它能高层 次提取运动中物体的形态学和运动学特点。以这个图作指导，我们描述在标记点对之间的 低层次运动学特征。所有这些高层次和低层次描述合起来形成了运动签名。
[0042] 我们希望构建出来的结构图能具有和真实的形态结构类似的结构（例如，骨架结 构），并且能同时反映出物体运动的整体运动学特点。因此，这个图被命名为形态运动结构 MAKS图(morphologicalandkinematicstructuregraph,MAKSgraph)。它是基于整个 标记点集来建的。
[0043] 构建形态运动结构MAKS图主要分为三步。第一步，基于标记点我们先推导出一个 最小运动生成树。第二步，我们基于标记点对之间的相对运动来自适应的聚类标记点。第 三步，我们根据聚类的结果修改最小运动生成树以产生MAKS图。
[0044] 其中最小运动生成树的推导方法是：我们先在所有标记点上构造一个全图，图中 任意两个结点之间存在一条边，边的权重为两个标记点在所有帧上距离的标准差。然后，我 们将基于这个全图抽取的最小生成树命名为最小运动生成树。最小运动生成树也反映了运 动捕获数据的全局运动学特点，因为它粗略的表达了标记点之间运动相关性的配置情况。 运动上高度相关的标记点对之间有一条边相连，而运动上相关度不大的标记点对之间则没 有边相连。
[0045]自适应标记点聚类方法是：我们采用谱聚类算法将标记点划分为不同的聚类，在 每一个聚类中使标记点之间的相对运动最小。我们用高斯函数来定义两个标记点％和 之间的相似度，如公式（3)所示，
[0047] 其中，STDOvnij)2是标记点mJPm』在所有帧上欧式距离的标准差。参数〇是通 过自调节技术设置的。我们为一个聚类结果先定义了一个成本测度，C:
[0049] 其中Ug是第g个聚类的标记点集合，K是聚类的数目。成本C越小，聚类中标记 点之间的关联性越高。我们迭代的执行谱聚类，在每一次迭代中，根据公式（4)计算聚类成 本。如果聚类成本已经低于一定的阈值，或迭代次数达到上限，就终止迭代；反之，增加K的 值，进入下一次循环。
[0050] 对于每个聚类中的标记点，我们将在最小运动生成树中修改对应的部分。如果一 个聚类包含多于一个标记点，我们在这个聚类中增加一个虚拟点，每一帧虚拟点位于这个 聚类中所有标记点的中心；否则，我们就不在此聚类中增加虚拟点。相应的，我们在最小运 动生成树上增加一个结点。接着，如果在最小运动生成树上，同一聚类中的标记点之间有边 连接的话，就把这些边删掉，然后增加连接虚拟结点和此聚类中所有标记点之间的边。最 后，对于改动后的树上的所有边，我们计算连接此边的两个结点在所有帧上的平均距离，并 将其作为此边的权重。
[0051 ] 一、运动签名；
[0052] 运动捕获数据的运动签名是由形态运动结构MAKS图的高层描述和任意标记点对 之间的低层运动学特征共同组成。
[0053] 对于形态运动结构MAKS图的高层描述，我们为MAKS图中的标记点对定义一个形 状函数，并使用形状函数值的统计分布来描述MAKS图的拓扑和几何特征。对于一对标记点 mdPm」，它们在MAKS图上的最短路径距离，是路径上所有边权重之和，记作li;j。MAKS图上 所有边的权重之和为L。我们定义标记点叫和111』对应的形状函数为sOi^nij) =li;j/L。被 L进行标准化后使得形状函数具有尺度不变性。假设总共有M个标记点，那么可能的标记点 对总共有T=C(M，2)对，我们为每一对标记点计算其形状函数值。这些形状函数值的直方 图分布形成了一个对MAKS图的形状分布描述符。
[0054] 对于任意标记点对之间的低层运动学特征，我们用一系列的量来描述标记点对的 绝对运动特征和相对运动特征。对于绝对运动特征，我们在每一帧上计算点对中心点处的 标量速度（Vl)和标量加速度（％);对于相对运动特征，我们计算两个标记点之间在每一帧 上的欧式距离（d)，相对速度（v2)，相对加速度（a2)，相对角速度（v3)和相对角加速度（a3)。 通过计算这些量，我们获得了一个具有F帧的运动捕获序列上每个标记点对的七条曲线： vjt)，a! (t)，d(t)，v2(t)，a2(t)，v3(t)和a3(t)，t = 1，2,…，F〇我们用前三个统计矩来描 述每条曲线，分别是平均值，方差和偏度。因此，我们用了21个统计量来描述每个标记点对 的运动特征。我们称这些量为标记点对的运动学特征，并记它们为h，i e [1，21]。
[0055] 最后，我们合成了高层次描述和低层次描述，共同组成了运动签名。运动签名实质 上是为每一个标记点对定义一个特征向量，然后将所有点对的特征向量放在一起，形成的 一个二维矩阵。假设所有可能组合的标记点对总共有T对。对于第p (1 < p < T)个标记点 对，我们标记它的形状函数值为sp，它的运动学特征为kp，i，1彡i彡21。则第p (1彡p彡T) 个标记点对的特征向量可表示为fp= (s p, kp>1，kp，2，…，kp，21)。按照特征向量的第一个成分 (形状函数值）的升序排序，将所有标记点对的特征向量放在一起，我们最终获得了这段运 动捕获数据的运动签名。
[0056] 三、比对过程中要解决的两个主要问题；
[0057] 1)由于每个运动文件中标记点数目有可能不同，因此导致运动签名中特征向量的 维度不同。怎样处理两个运动签名的维度不一致问题？
[0058] 2)对于给定的查询样例，如何优化的确定不同特征的权重，以使得数据库中的正 例和负例尽可能的分开？
[0059] 为了解决第一个问题，我们提出基于特征向量中的形状函数值来注册两个运动签 名的方法。为了解决第二个问题，我们为每一种运动类型预先学习一套优化的权重，在运行 时针对任意给定的查询样例自适应的选择一组权重。
[0060] 我们计算查询样例的运动签名和数据库中所有运动捕获数据的运动签名之间的 距离，并将其按升序进行排序作为查询结果返回。
[0061] 运动签名的对应问题本质上是标记点对的对应问题，即，为一个运动序列中的标 记点对到另一个运动序列中找对应的标记点对。如果两个运动序列非常相似，那么它们将 会有相似的MAKS图，对应的标记点对也将有相似的形状函数值。因此，在 运动签名A中，一 个形状函数值为s的特征向量，我们可以通过在运动签名B中找形状函数值接近于s的特 征向量与之对应。高效的折半查找可以完成搜索任务，因为在构造运动签名时其中的特征 向量已经按照形状函数值的升序排序存放了。
[0062] 然而，对应的标记点对的形状函数值有可能存在统计差别，在同一个MAKS图中不 同的标记点对也可能具有相同的形状函数值。因此，仅使用最接近的形状函数值来找标记 点对的对应关系并不总能可靠的得到正确结果。为提高鲁棒性，当建立标记点对之间的对 应关系时，我们在一个局部窗口中进行搜索而不是全局搜索最匹配的。
[0063] 假设有两个运动签名，分别为S = [f\，f2，…，fP]和S' = [f' ^ f'2，…， "^]，其中4，1￡[1，？]和"」，_]_￡[1，？']是22维的特征向量，？和1^是在对应 的两个运动签名中标记点对的个数。S和S'之间的距离用公式（1)进行计算，
[0065] 其中W是个权重向量，包含着特征向量每一维度的权重，DF(S，S'，1)如公式（2) 定义，
[0067]在公式⑵中，h和h'是从运动签名S和S'获得的标准化形状分布直方图，DH(h，h')通过直方图求交的倒数来衡量了两个直方图之间的相似性，直方图越相似，函数值越 小；(/^)是4江'P通过最接近的形状函数值确定的初始对应向量。为提高对应关系 查找的鲁棒性，我们在以初始对应向量为中心，大小为[_w，w]的局部窗口中来搜索最佳匹 配，计算方法如公式（2)所示。在实际实验中，我们设w = 7。
[0068]我们提出通过学习来为数据库中的每一类运动数据确定一组特征权重。对于每一 种运动类型，一定比例（我们的实验中取50%)的运动数据被选为训练集。一开始先设置 一个初始的权重向量W，然后通过迭代逐步优化。在每一次迭代过程中，我们用训练集中的 每一个运动数据作为查询样例执行基于内容的检索，从返回的查询结果中选择一定比例的 正例和负例。所有这些查询样例的正例构成了一个大的正例集合，所有这些查询样例的负 例构成了一个大的负例集合。大的正例集合和负例集合共同通过有偏判别分析（BDA)来学 习优化的权重向量W。如果两次迭代得到的W差别很小或迭代次数达到上限，那么迭代将会 结束。
[0069]在运行时，对于一个给定的查询样例q，它的运动签名为Sq，我们首先从预先学习 的权重中选择权重向量^。然后，对数据库中的每个运动序列m，对应的运动签名为Sm，我 们用公式（2)计算SjPSm之间每个特征分量的差异，S卩，DF(Sq，Sm，1)，1 e [1，22]。整个 数据库中所有运动签名和样例运动签名之间差异在每个特征分量或特征维度上分别进行 高斯归一化。进一步的，在公式（1)中带入这些高斯归一化后的差异值和特征权重Wq，我们 获得了从q到m的运动签名距离D(Sq，Sm)。最后，数据库中所有的运动捕获数据文件根据 其与查询样例之间的运动签名距离从小到大排序，排在最前面的若干个运动捕获数据文件 作为查询结果返回。在这个过程中最主要的挑战是为一个任意给定的查询样例自动的选择 合适的权重向量。我们通过一个二维形状-速度直方图为一个运动捕获数据序列进行高层 描述。这个直方图的两个维度分别是形状函数值和绝对速度的平均值，直方图中的每一项 代表具有特定形状函数值和绝对速度平均值的标记点对所占的比例。每一种运动类型的形 状-速度直方图是通过把训练集中所有运动数据的形状-速度直方图做平均得到的。在运 行时，我们计算查询样例的形状-速度直方图，并将其与所有运动类别的形状-速度直方图 进行比较，然后找到直方图最匹配的运动类型作为查询样例的运动类型。
[0070] 当计算两个运动签名之间的距离时，我们为运动签名中不同的特征赋予不同的权 重。我们事先在训练数据库上用有偏判别分析的方法为每种运动类型学习一组特征权重， 在查询时，基于运动数据的二维直方图来自适应的选择一套合适的权重。
[0071] 四、对比试验；
[0072]我们分别在三个数据集上做了四组实验，详细描述如下。
[0073] 第一个数据集。第一个实验是想和近期业界有代表性的查询算法比较查询性能， 因此我们使用了 HDM05数据库中人体运动捕获数据的一个子集作为第一个数据集。第一个 数据集包含了从HDM05数据库中挑选的七类不同运动类型的运动序列，分别是侧手翻（简 写为"cwheel"），肘碰膝（简写为"eTok"），跳（简写为"hop"），跳爆竹（简写为"jjack"）， 击拳（简写为" punch"），下蹲（简写为" squat"）以及走（简写为" walk"）。每一类运动 包含20个运动序列，总共数据库中有140个运动序列，共计27322帧。
[0074] 第二个数据集。第二个实验是想考察我们的算法在异质数据库中的查询性能。因 此，我们第二个数据集是个混合数据库，数据分别来自CMU数据库，HDM05数据库以及我们 自己用Vicon光学运动捕获系统捕获的运动数据。第二个数据集中共包含六种类型的运 动，分别是肘碰膝（简写为" eTok"），跳（简写为" hop"），跳爆竹（简写为" jjack"），演奏 乐器（简写为" pmi"），下蹲（简写为" squat"）以及走（简写为" walk"）。每一类运动包 含20个运动序列，数据库中有120个运动序列，共计22404帧。在捕获每一类运动时，我们 用了两位男演员和两位女演员来分别表演动作。总之，在这个数据集中的运动序列是来自 具有不同的贴点方式和骨架模板的数据源。
[0075] 第三个数据集。第三个数据集是用来展示我们的算法在检索由不同种运动对象 所做的运动时的性能。第三个数据集中的数据都是由我们自己捕获的。有的运动数据是 来自整个身体的，有的是来自身体的某一部分，例如头部、肩部、胳膊和腿部。这些运动 一共可以分为七种运动类型，分别是扭手腕（胳膊，简写为" atwist"），挥手（胳膊，简写 为" awave"），打羽毛球（全身，简写为" bbmt"），点头（胳膊，简写为" awave"），踢腿（腿 部，简写为" lkick"），下蹲（腿部，简写为" lsquat"）和耸肩（肩部，简写为" sshake"），每 种类型各自包含20个运动序列。在捕获每种运动类型时，我们采用了两位男演员和两位女 演员分别做动作。在这个数据集中，总共有140个运动序列，共计41688帧。
[0076] 我们将自己的算法与基于运动检索树的方法（简写为"MI"），基于低秩分解的方 法（简写为"LR"）和基于等级化模型的方法（简写为"HM"）在相同的数据集上做实验并 详细报告、分析了在不同测度下各种算法的查询性能表现。
[0077] 我们使用的性能测度包括信息检索领域常用的TPR，准确率-召回率曲线（P-R curve)，平均准确率（MAP)。TPR是在前N个检索结果中和查询样例类别相同所占的比例， 即在前N个检索结果的准确率，这里我们设N = 20。另外，我们还使用了混淆矩阵作为性能 评价测度。
[0078]结果与分析：
[0079]在实验中，算法MI，LR和HM仅在第一个数据集上获得了检索结果，因为他们都无 法处理像第二个和第三个数据集那样的异质运动捕获数据库。我们的算法则能够处理全部 三个数据集。在评估每个算法的检索性能时，我们用数据集中的每个运动序列作一次查询 样例，所有返回的查询结果集合在一起用于查询性能测度的计算。
[0080] 表2-1在第一个数据集上用我们有权重学习的算法，我们没有权重学习的算法， HM，LR，MI，获得的七类运动的TPR统计量
[0081]
[0082] 第一个实验。在第一个数据集上，执行了算法MI，算法LR，算法HM，并与我们的算 法进行比较。进一步的，我们关掉特征权重优化的部分，将所有的特征权重设为1，重新在 第一个数据集上获得查询结果。如表2.1所示，通过统计五个算法（算法MI，算法LR，算法 HM，我们的算法带权重学习模块，我们的算法即使没有权重学习模块，其在七类运动上的平 均查询准确率也已经超过了其他三种算法。增加权重学习之后，我们的算法查询准确率得 到了很大的提高，明显超过了其他三种算法。在图2-1中展示了算法MI，算法LR，算法HM 以及我们的算法在不同运动类型上的P-R曲线。从图2-1中可以观察到我们的算法在七类 运动上平均的准确率 -召回率曲线拥有最大的曲线下面积（area under curve，AUC)。在表 2-2和图2-2中分别显示了算法MI，算法LR，算法HM以及我们的算法的MAP统计量和混淆 矩阵。再一次观察到，我们的算法在查询准确率上明显优于其他算法。
[0083] 表2-2在第一个数据集上用算法MI，LR，HM，我们的算法获得的七类运动的MAP统 计量：
[0085]第二个实验。我们在第二个数据集上执行查询算法，获得了在不同查询性能测度 下的统计量。因为第二个数据集中的运动捕获数据在捕获时，采用了不同的坐标系，不同的 贴点方案以及不同的骨架模板。而现有的算法需要有一个统一的骨架模板，无法处理这种 异质的数据库。因此第二个实验仅仅给出我们算法的查询结果。P-R曲线和混淆矩阵显示 在图2-3中。从图2 -3中可以看出，我们的算法在异质运动数据库上取得了很高的查询准 确率，大部分超过95 %甚至达到100%。
[0086] 第三个实验。我们在第三个数据集上执行查询算法，获得了在不同查询性能测度 下的统计量。据我们所知，尚没有公开发表的算法能对全身运动和局部身体运动统一进行 检索，而第三个数据集包含了不同运动物体（全身、头部、上肢、下肢）的混合运动，因此，我 们仅获得了我们的算法在第三个数据集上的查询结果。在图2-4中给出了 P-R曲线和混淆 矩阵。第三个数据集中涉及的运动对象差别很大，我们的算法仍然获得了很高的查询准确 率，七种运动类型的查询准确率都在90 %左右。
[0087] 时间统计
[0088] 我们在VS2010环境下实现了算法，在一个配置有Intel Core Duo2. 93GHz CPU和 4GB内存的台式机上，获得了以下运行时间统计数据。在每一个数据集上，我们分为预处理 时间（运动签名生成），权重学习时间，平均查询时间（通过多次随机选取查询样例执行查 询的总时间，再进行平均而得到）。在表2-3中，我们展示了在三个数据集上预处理、权重 学习和查询的时间代价。从表2-3可以看出，我们的算法在第三个数据集上的查询效率最 高。这是因为查询时间代价与运动序列上的标记点对个数是成正比的。第三个数据集中 所包含的运动序列是对应局部身体的运动，局部身体上所贴的标记点相比整个身体要少得 多。
[0089]表2-3我们的算法在三个数据集上的时间统计：
[0091] 以上所述仅是本专利的优选实施方式，应当指出，对于本技术领域的普通技术人 员来说，在不脱离本专利技术原理的前提下，还可以做出若干改进和替换，这些改进和替换 也应视为本专利的保护范围。
【主权项】
1. 一种通用的运动捕获数据检索方法，其特征在于，包括以下步骤： 步骤1，建立数据库，在数据库中存储若干运动捕获数据序列，并且每段运动捕获数据 序列离线计算出对应的运动签名；所述运动签名由基于整个标记点集构建的形态运动结构 MKS图的高层描述和任意标记点对之间的低层运动学特征共同组成；运动签名是为每一 个标记点对定义一个特征向量，然后将所有点对的特征向量放在一起，形成的一个二维矩 阵； 步骤2,将用户提交的一段运动捕获序列查询样例在线计算出与之对应的运动签名，然 后将该运动签名与数据库中存储的所有运动捕获数据序列的运动签名进行比对； 步骤3,在数据库中找出与步骤2中在线计算出的运动签名之间距离最接近的若干运 动签名，并按照距离由小到大的顺序将与这些运动签名所对应存储在数据库中的运动捕获 序列作为查询结果集反馈给用户。2. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于：在步骤1中形态 运动结构MKS图的构建包括以下步骤： 第一步，首先基于标记点集推导出一个最小运动生成树； 第二步，基于标记点对之间的相对运动来自适应地聚类标记点； 第三步，根据聚类的结果修改最小运动生成树以构建形态运动结构MKS图。3. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于，在步骤1中，实现 形态运动结构MKS图的高层描述的方法是：为形态运动结构MKS图中的标记点对定义一 个形状函数，并使用形状函数值的统计分布来描述形态运动结构MAKS图的拓扑和几何特 征；对于一对标记点IHi和％，其形状函数的定义为= Ii, j/L ;其中：标记点叫和Hij在形态运动结构MAKS图上的最短路径距离，是路径上所有边权重之和，记作Iu;形态运动 结构MKS图上所有边的权重之和为L ;被L进行标准化后使得形状函数具有尺度不变性， 假设总共有M个标记点，那么可能的标记点对总共有T = C(M，2)对，为每一对标记点计算 其形状函数值，这些形状函数值的直方图分布形成了一个对形态运动结构MKS图的形状 分布描述符。4. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于，在步骤1中，任 意标记点对之间的低层运动学特征包括任意标记点对之间的绝对运动特征和相对运动特 征； 对于绝对运动特征，在每一帧上计算点对中心点处的标量速度（V1)和标量加速度 (?);对于相对运动特征，计算两个标记点之间在每一帧上的欧式距离（d)，相对速度（V2)， 相对加速度（a2)，相对角速度（V3)和相对角加速度（a3); 计算上述量，获得一个具有F帧的运动捕获序列上每个标记点对的七条曲线：Vl (t)， ajt)，d(t)，v2(t)，a2(t)，v3(t)和a3(t)，t = 1，2,…，F ;用前三个统计矩来描述每条曲线， 分别是平均值，方差和偏度；因此用21个统计量来描述每个标记点对的运动特征，定义上 述统计量为标记点对的低层运动学特征，并记它们为kpi e [1，21]。5. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于，在步骤1中，将形 态运动结构MKS图的高层描述和任意标记点对之间的低层运动学特征进行合成；假设所 有可能组合的标记点对总共有T对；对于第p(l < p < T)个标记点对，标记它的形状函数 值为sp，它的运动学特征为kp，i，1彡i彡21 ;则第p (1彡p彡T)个标记点对的特征向量可 表示为&=(81)，、1，、2，一，、21);按照特征向量的第一个成分即形状函数值的升序排序， 将所有标记点对的特征向量放在一起，最终获得了这段运动捕获数据的运动签名。6. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于：在步骤2、3中，将 运动签名的注册问题转换为两个运动签名中标记点对的对应问题，基于特征向量中的形状 函数值来注册运动签名，首先在两个运动签名中寻找形状函数值最接近的特征向量作为初 始对应向量，在以初始对应向量为中心，大小为[-W，W]的局部窗口中来搜索最佳匹配，以 提高对应关系查找的鲁棒性，设定W = 7,然后计算两个运动签名的距离，假设两个运动签 名分别为3=[4,4，一，心]和5'=[广1，广2，一，广1),]，其中4，1￡[1，？]和 f j，je [1，]是22维的特征向量，P和P是在对应的两个运动签名中标记点对的 个数；S和S'之间的距离用公式（1)进行计算：⑴ 其中W是个权重向量，包含着特征向量每一维度的权重，DF(S，S^，1)如公式（2)定义：在公式（2)中，h和h'是从运动签名S和S'获得的标准化形状分布直方图，DH(h， h')通过直方图求交的倒数来衡量了两个直方图之间的相似性，直方图越相似，函数值越 小；(Iij >是4江'P通过最接近的形状函数值确定的初始对应向量。7. 根据权利要求1所述通用的运动捕获数据检索方法，其特征在于：在步骤2、3中，通 过学习来为数据库中的每一类运动数据确定一组特征权重，以使得数据库中的正例和负例 尽可能的分开；在运行时，对于一个给定的查询样例q，它的运动签名为S,，首先从预先学习 的权重中选择权重向量W,，然后对数据库中的每个运动序列m，对应的运动签名为Sm，用公 式（2)计算5,和5"1之间每个特征分量的差异，8卩，0"\，5111，1)，1￡[1，22];整个数据库中 所有运动签名和样例运动签名之间差异在每个特征分量或特征维度上分别进行高斯归一 化；进一步地在公式（1)中带入这些高斯归一化后的差异值和特征权重W,，获得了从q到 m的运动签名距离D(S,，Sm);最后，数据库中所有的运动捕获数据文件根据其与查询样例之 间的运动签名距离从小到大排序，排在最前面的若干个运动捕获数据文件作为查询结果返 回。8. 根据权利要求7所述通用的运动捕获数据检索方法，其特征在于：为一个任意给定 的查询样例自动的选择合适的权重向量的方法为：通过一个二维形状-速度直方图为一个 运动捕获数据序列进行高层描述，这个直方图的两个维度分别是形状函数值和绝对速度的 平均值，直方图中的每一项代表具有特定形状函数值和绝对速度平均值的标记点对所占的 比例；每一种运动类型的形状-速度直方图是通过把训练集中所有运动数据的形状-速度 直方图做平均得到的，在运行时，计算查询样例的形状-速度直方图，并将其与所有运动类 别的形状-速度直方图进行比较，然后找到直方图最匹配的运动类型作为查询样例的运动 类型。
【专利摘要】一种通用的运动捕获数据检索方法。本发明提出了一种通用的运动数据表示形式—运动签名：它以统计学的角度从低层次和高层次全面描述了运动数据的形态学特征和运动学特征。在离线状态下，先将运动数据的原始标记点三维位置信息通过构造形态运动结构MAKS图的方式，抽取形状特征和运动学特征，保存为运动签名的形式；当在线查询时，针对查询样例，先构造其运动签名，然后根据形状-速度二维直方图判断它属于哪种运动类别，然后选择之前通过BDA学习到的这种运动类别的权重系数，通过和数据库中所有运动数据的运动签名进行加权距离的计算并排序，最后返回查询结果。本发明的有益效果是：采用适用范围更广的运动签名比对，检索精确度高，检索速度快，适用范围广。
【IPC分类】G06F17/30
【公开号】CN104899248
【申请号】CN201510204348
【发明人】吕娜, 冯志全, 彭京亮
【申请人】济南大学
【公开日】2015年9月9日
【申请日】2015年4月24日
最新回复(0)