基于非线性流形学习的运动图过渡点选取方法

摘要

本发明公开了一种基于非线性流形学习的运动图过渡点选取方法，属于计算机图像处理技术领域。本发明包括高维数据的降维分析，提取关键数据段，计算关键数据段帧间相似性，构建运动图几个步骤。

权利要求

1.一种基于非线性流形学习的运动图过渡点选取方法，其特征在于：包括以下步骤：步骤一：高维数据的降维分析

使用ISOMAP非线性流形学习算法，对高维人体运动数据进行降维处理，得到原始运动序列的低维流形结构，根据运动类型的不同，绘制与之匹配的低维特征曲线；

(1)取一段长度为L帧的n维人体运动数据，则输入数据集channel＝[L×n]，根据本文所使用的CMU数据库数据，每一帧数据包含n＝96维数据；

(2)计算每个点的近邻点，用K近邻或ε邻域；

(3)在样本集上定义一个无向图，以局部邻域的数据点来构建无向图G，边表示在局部邻域范围内点之间的连接；

(4)计算无向图的最短距离，使用Dijkstra算法计算图中两点(i，j)的最短距离，所得的距离矩阵为DG：DG＝{dG(i，j)}；

(5)使用MDS求解低维嵌入流形；

步骤二：提取关键数据段

根据人体运动低维特征曲线，提取关键运动段，在此关键运动段内计算帧间相似性；

基于对过渡平滑度的考虑，采用一个长度为W的窗口，将窗口内的数据加入新的数据集Yi，W的值由公式决定：W＝L/(ρC)；

其中，L为帧长度，ρ为权值，取决于人体姿态变化的频率，C为特征曲线顶点的数量；

确定W的值后，记录窗口内的帧数，在数据集channel中提取相对应的数据，存入新的数据集Yi中，i为对应的运动序列序号；

步骤三：计算关键数据段帧间相似性

使用欧氏距离的计算方法，计算关键数据段间每帧的相似性，画出距离图；

首先，将步骤二中提取的关键运动数据段建立数据集，原运动数据中提取出来的关键段为一个数据集；

其次，计算帧间相似性，两两计算各帧间的距离，采用欧式距离表示；将满足所设阈值的两点连接，形成一个跳转点；

步骤四：构建运动图

设定一个阈值M，将所有小于阈值M的帧间连接成边，经过剪支处理后，构建成运动图。

说明书

基于非线性流形学习的运动图过渡点选取方法

技术领域

[0001] 本发明涉及一种基于非线性流形学习的运动图过渡点选取方法，属于计算机图像处理技术领域。

背景技术

[0002] 近年来，随着计算机软硬件技术的进步，计算机动画技术得到了飞速的发展，计算机动画是指采用图形与图像的处理技术，以实体造型和真实感显示技术为基础，借助于编程或动画制作软件生成一系列的景物画面。其涉及到图像处理技术、运动控制原理、视频技术和艺术等众多领域，以独特的特点逐步成为一个多种学科和技术综合的领域。其中，运动捕捉技术的不断发展，人们可以利用捕捉设备抓取到的数据生成更多样化且复杂的虚拟人运动。但是，由于运动捕捉设备昂贵且受限于捕捉的外部条件，不可能对所需的人体运动数据每次都进行捕捉，运动数据重用技术和基于运动图的人体动画合成技术由此产生。将捕获的人体运动数据根据运动类型分类保存构建运动图，合成新的人体运动数据时，只需遍历运动图并结合插值技术即可由现有的人体运动数据片段合成新的所需人体运动数据。因此，基于运动捕捉数据的运动合成技术研究是计算机动画技术重要的研究领域之一。

[0003] 自2002年基于运动图的人体运动合成方法产生后，在人体运动数据合成领域，基于运动图的人体运动合成方法已成为目前的主要方法。如附图2所示，运动图的基本方法是将运动捕捉数据按运动类型分段，每帧为一个节点，然后计算每一个节点间的相似性，满足所设阈值的节点间构建为边，最后形成运动图，进行人体运动合成的过程就是在运动图上搜索所需路径的过程。尽管经过多年的发展，但其仍存在很多问题，例如运动图中点、边的定义，过渡点的选取，运动图上搜索路径的规划等。

[0004] 另一方面，基于非线性流形学习的方法被引入到人体运动合成领域，非线性流形学习可以对高维人体运动数据进行降维分析，常用的非线性流形学习方法有ISOMAP、ST-ISOMAP、SOM和LLE等，前三种属于全局方法，后者则属于局部方法。ISOMAP降维方法可用于运动段的分割，提取边界关键帧，以区分原始运动数据段中不同类型的分段。ST-ISOMAP方法可将人体运动数据片段投影到低维流形上进行重排得到新的运动数据片段。而SOM方法得到高维数据在低维流形上的分布。

[0005] 已有的研究表明，基于全局非线性流形学习的方法适合于人体运动片段的分割、提取关键帧等操作，降维后的低维数据可以很好的反映运动序列的高维姿态，可以有效的发掘运动数据片段最本质的运动特征。同时，降低运动图过渡点选取时间复杂度仍然是一个具有挑战性的任务。

发明内容

[0006] 本发明针对以上问题的提出，而研制一种基于非线性流形学习的运动图过渡点选取方法，该方法通过建立计算关键运动数据段间的相似性，着重解决在运动图构建过程中跳转点选取时间复杂度高，选取不准确的问题，从而提高运动图的构建效率，使得生成的运动数据更加平滑自然。

[0007] 本发明包括如下步骤：

[0008] 步骤一：高维数据的降维分析。

[0009] 步骤二：提取关键数据段。

[0010] 步骤三：计算关键数据段帧间相似性。

[0011] 步骤四：构建运动图。

[0012] 本发明的原理：通过ISOMAP降维算法对高维人体运动数据进行降维处理，使用降维后的低维数据，绘制低维特征曲线。根据低维特征曲线选取人体运动片段中的关键数据段，计算关键运动数据段帧间的相似性，满足所设阈值的帧连接成边，最终形成一个由关键数据段组成的运动图结构，合成新的人体运动数据时，只需遍历此运动图即可。

[0013] 本发明与现有技术相比具有以下优点：

[0014] 在表一中，方法A为计算过渡点的标准方法。方法B为一种过渡点快速选取算法。通过表一可见，计算所得的距离矩阵分别为A[344*163]，B[115*55]，C[250*88]。时间消耗对比数据表示计算距离图所需的时间，方法A为117.572319秒，方法B为19.229195秒，本发明所提方法C为45.487492秒，因此本发明所提方法在时间效率上优于标准算法，与快速法接近。第三项对比数据准确率表示当前算法找到的过渡点占所有可连接点的比率，因为方法A为标准算法，计算当前运动序列所有帧间的相似性，因此假设方法A的准确率为
100％，设定阈值M，其他2种方法均已A为基底计算准确率，以R表示准确率，当前算法找到过渡点的总数为Si(i＝a,b,c)，由于考虑到标准算法在计算时会产生大量的无效边，特别是在参与计算的2段运动类型相似的情况下，不符合物理定律的2帧运动间也可能连接成边，因此设定一个权值ρ，ρ值根据参与计算的2段运动类型的不同而不同，在0～1范围内，值越大，运动类型差距越大。则计算公式为：

[0015] R＝ρ(Si/Sa)，

[0016] 通过公式计算，方法B准确率为33.4％，本文所提方法C准确率为78.1％。对比可见，本发明所提方法寻找合适过渡点的准确率优于快速选择法，接近标准算法。因此，基于非线性流形学习的运动图过渡点选取方法在时间和准确率上都有一定的优势，这种方法在大幅降低时间消耗的同时，保持了一定的准确率，是一种有效可靠的运动图过渡点选取算法。

[0017] 表一：与其他方法对比

[0018]方法 A B C
帧数 344*163 115*55 250*88
时间消耗 117.572319s 19.229195s 45.487492s
准确率 100％ 33.4％ 78.1％

附图说明

[0019] 图1本发明算法流程图。

[0020] 图2标准运动图计算原理。

[0021] 图3人体运动数据低维特征曲线示意图。

[0022] 图4关键数据段选取示意图1。

[0023] 图5关键数据段选取示意图2。

[0024] 图6相似性计算结果图。图中颜色越深处，表示距离越接近，即可建立运动图连接边的点。

具体实施方式

[0025] 下面结合附图对本发明做进一步的解释，本发明单位一个实施例为：

[0026] 本发明的实施例是在以本发明技术方案为前提下进行实施的，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述实施例。

[0027] 如图1所示为本发明算法流程图，其具体包括以下技术环节：

[0028] 步骤一：高维数据的降维分析

[0029] 使用ISOMAP非线性流形学习算法，对高维人体运动数据进行降维处理，得到原始运动序列的低维流形结构，根据运动类型的不同，绘制与之匹配的低维特征曲线。

[0030] (1)取一段长度为L帧的n维人体运动数据，则输入数据集channel＝[L×n]，根据本文所使用的CMU数据库数据，每一帧数据包含n＝96维数据；

[0031] (2)计算每个点的近邻点，用K近邻或ε邻域；

[0032] (3)在样本集上定义一个无向图，以局部邻域的数据点来构建无向图G，边表示在局部邻域范围内点之间的连接；

[0033] (4)计算无向图的最短距离，使用Dijkstra算法计算图中两点(i，j)的最短距离，所得的距离矩阵为DG：

[0034] DG＝{dG(i，j)}；

[0035] (5)使用MDS求解低维嵌入流形；

[0036] 本发明公开的方法如附图3所示，图3表示一段三维运动经过ISOMAP降维后的低维特征曲线。曲线随人体高维运动规律变化，在曲线的转折处，高维空间的人体运动改变其原有运动状态。

[0037] 步骤二：提取关键数据段

[0038] 根据人体运动低维特征曲线，提取关键运动段，在此关键运动段内计算帧间相似性。

[0039] 基于对过渡平滑度的考虑，采用一个长度为W的窗口，将窗口内的数据加入新的数据集Yi，W的值由公式决定：

[0040] W＝L/(ρC)；

[0041] 其中，L为帧长度，ρ为权值，取决于人体姿态变化的频率，C为特征曲线顶点的数量。确定W的值后，记录窗口内的帧数，在数据集channel中提取相对应的数据，存入新的数据集Yi中，i为对应的运动序列序号；

[0042] 如图4所示：灰色区域为一段人体运动中，需要提取的关键数据段。

[0043] 步骤三：计算关键数据段帧间相似性

[0044] 使用欧氏距离的计算方法，计算关键数据段间每帧的相似性，画出距离图。

[0045] 首先，将步骤二中提取的关键运动数据段建立数据集，原运动数据中提取出来的关键段为一个数据集；

[0046] 其次，计算帧间相似性，两两计算各帧间的距离，采用欧式距离表示。将满足所设阈值的两点连接，形成一个跳转点；

[0047] 附图6为利用本文所提算法对一组走与跑经过降维、运动提取关键运动数据段最后计算相似性的距离图，图中颜色越深处，表示距离越接近，即可建立运动图连接边的点。表二所示为经过降维处理后，提取的关键数据段帧数与原始数据段帧数对比。运用本文所提方法，相比提取过渡点的标准方法，提取速度提高40％以上，提取完整率约为78％～
100％。

[0048] 如附图6所示：使用二维灰度图表示距离值的大小，距离越近，颜色越深，表示可以建立跳转点。反之，颜色越浅则意味着2帧运动差别过大，不可建立跳转点。

[0049] 步骤四：构建运动图

[0050] 设定一个阈值M，将所有小于阈值M的帧间连接成边，经过剪支处理后，构建成运动图。图2为标准运动图的计算原理，如图2所示左侧为运动数据段，右侧表示在运动数据段上计算帧间相似性后，满足所设阈值的帧之间可以建立跳转边。

[0051] 实例选取一组走与跑运动进行验证，运动数据低维特征曲线如附图3所示，关键数据段选取如附图4及附图5所示，在图4中，灰色区域为一段人体运动中，需要提取的关键数据段，对应于图5中的灰色或黑色点，一个点表示一帧数据。

[0052] 附图6为利用本文所提算法对一组走与跑经过降维、运动提取关键运动数据段最后计算相似性的距离图，图中颜色越深处，表示距离越接近，即可建立运动图连接边的点。表二所示为经过降维处理后，提取的关键数据段帧数与原始数据段帧数对比。运用本文所提方法，相比提取过渡点的标准方法，提取速度提高40％以上，提取完整率约为78％～
100％。

[0053] 表二：关键数据段提取结果

[0054]运动数据 原始帧数 提取后帧数
走 344 150
跑 174 110
跳 484 225
舞蹈 1124 570
踢球 360 250

[0055] 以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。