2024年5月2日发(作者：)

(19)中华人民共和国国家知识产权局

(12)发明专利说明书

(21)申请号 CN2.0

(22)申请日 2012.11.16

(71)申请人 浙江大学

地址 310058 浙江省杭州市西湖区余杭塘路866号

(72)发明人 肖俊 齐天 庄越挺

(74)专利代理机构 杭州求是专利事务所有限公司

代理人 周烽

(51)

H03M7/30

权利要求说明书 说明书 幅图

(10)申请公布号 CN 103023510 A

(43)申请公布日 2013.04.03

(54)发明名称

方法

(57)摘要

本发明为一种基于稀疏表达的运动

一种基于稀疏表达的运动数据压缩

数据压缩方法，该方法首先对输入的运动

数据进行分析生成稀疏表达字典；然后基

于稀疏表达字典对运动数据中的每一帧进

行稀疏线性表达；最后用K-SVD算法对字

典和稀疏表示进行迭代优化。本方法在将

重建误差控制在合理范围的前提下，可以

达到较高的压缩比，特别适用于对较短运

动数据的压缩。

法律状态

法律状态公告日

法律状态信息

法律状态

权 利 要 求 说 明 书

1.一种面向运动数据的压缩方法，其特征在于，该方法包括如下步骤：

（1）运动数据采集：采集人体运动时的关节点运动轨迹，并存为bvh或trc格

（2）解析运动数据文件：将运动数据文件中的运动数据Y和其他数据H（包括

（3）运动数据字典生成：通过K-means聚类算法将运动数据Y聚为K类，生成

（4）稀疏表达求解：对运动数据Y中每一帧的信息用步骤3中生成的初始化的

运动数据字典D⁽⁰⁾进行线性表达，并用Sparse方法求解

阵A，该稀疏表达矩阵A即为运动数据

初始化的运动数据字典D⁽⁰⁾，其中，K为字典大小；

模型信息、帧数、采样率等）进行区分；

式的运动数据文件；

运动数据Y的稀疏表达矩

Y的压缩形式；

（5）应用K-SVD优化方法对步骤3生成的初始化的运动数据字典D⁽⁰⁾

和步骤4 生成的稀疏表达矩阵A进行迭代优化，得到优化后的

后的稀疏表达矩阵A

运动数据字典D_优化和优化

优化，减小步骤4带来的数据重建误差；

（6）后续无损编码压缩：该步骤对步骤2中抽取的其他数据H、步骤5中生成

的优化后的运动数据字典D_优化和优化后的稀疏表达矩

压缩，得到最终压缩后的二阵A_优化进行Huffman编码

进制数据文件，压缩过程完成。

说 明 书

技术领域

本发明涉及动画制作、运动捕获以及机器学习领域，特别涉及一种对运动

背景技术

随着动画产业的发展，动画制作中越来越多的用到运动数据（其格式以bvh、

trc等为主），这些数据多来源于运动捕获系统。运动数据文件中一般包括

型信息、运动片段总帧数、采样率等基础信息以及大量的运动

模型每个关节点的三维坐标或旋转角度，依文件格式而

采样率普遍较高，因此运动数据中冗余度也相对

量运动数据时会消耗过多的磁盘空间。因

意义的实际问题。

数据进行压缩的方法。

角色模

数据信息（角色

不同）。由于运动数据的

较高，重复性较强，在需要大

此，对运动数据的压缩成为了一个有

随着人体运动数据在科研和生产应用中的普及以及用于科研与商用目的的

家

表的

《Compression of Human Motion Animation Using the Reduction of Interjoint

Correlation》，该方法公开了一种通过正向和反向运动学对运动序列中的关

进行表示，基于反向运动学的预测对运动数据进行压缩的方法。与之

2009年的Computer Graphics上发表的

geodesics analysis》，公开了一种

的简化骨骼模型，并通过储

据，从而实现运动数

动数据压缩中，

大型三维人体运动数据库的出现，对运动数据的高效压缩与存储正逐渐被大

所重视。2008年在EURASIP Journal on Image and Video Processing发

节点

类似，在

《Motion compression using principal

基于PGA(Principal Geodesics Analysis)构建

存人体骨骼根结点和所有末端节点轨迹代替原始数

据压缩效果的方法。此外，数据降维的方法也被引入到运

例如基于PCA和CPCA的运动数据压缩方法。此外，另一类减少 数据重

复性的思路是信号处理方法，例如小波变换等。然而实验表明，仅用一

随着可用运动数据的不断增加，采用数据驱动方法实现运动数据压缩成为

一个可行的思路。2008年在Computer Graphics上发表的

些简单的数据降维和信号处理方法对运动数据进行压缩，其效果并不理想。

《Compression of human

motion capture data using motion pattern indexing》，该方法先将三维人体运

据进行结构化处理，并在数据库中识别具有相似特征的数据，然后将

体运动数据用数据库中已有的样本进行表达，用数据库索引替

现压缩目的。这种运动特征索引的思路也在其他一些方

年在

动数

结构化人

代原始数据以实

法中有所体现，如2007

IEEE Transaction on Visualization and Computer Graphics上发表的《Human

但

motion capture data compression by model-based indexing：A power aware

approach》。基于数据驱动的运动数据压缩方法确实能达到较好的压缩效果，

从大量训练数据中提取特征和生成模型是计算复杂且耗时的过程。此

驱动的压缩过程还需要一定规模的数据库支持，且在很大程度

赖于所选择的训练样本，这与数据压缩的目的相悖。

外，数据

其重建效果还依

在以上这些运动数据压缩方法中，大多数只适用于较长运动序列，或需要

对数据库中所有运动数据片段拼接形成一个超长运动序列后再对其进行压缩。

然而，如前文所述，由于运动捕获流程中采集的运动片段一般都不超

短时长的运动序列应用更为广泛，且拼接成的整段超长运动序

数据库和数据变更的处理。遗憾的是，目前仍没有一种

的压缩方法。

过几分钟，

列不利于对增量

适用于短时长运动序列

发明内容

本发明的目的在于针对现有技术的不足，提供了一种基于稀疏表达的运动数

本发明的目的是通过以下技术方案来实现的：一种基于稀疏表达的运动数

（1）运动数据采集：采集人体运动时的关节点运动轨迹，并存为bvh或trc格

（2）解析运动数据文件：将文件中运动数据Y和其他数据H（包括模型信息、

（3）运动数据字典生成：通过K-means聚类算法聚为K类，生成初始化的运动

（4）稀疏表达求解：对运动数据Y中每一帧的信息用步骤3中生成的初始化的

运动数据字典D⁽⁰⁾进行线性表达，并用Sparse方法求解运动数

阵A，该稀疏表达矩阵A即为运动数据Y的压缩形式；

数据字典D⁽⁰⁾，其中，K为字典大小；

帧数、采样率等）进行区分；

式的运动数据文件；

据压缩方法，该方法包括如下步骤：

据压缩方法。

据Y的稀疏表达矩

（5）应用K-SVD优化方法对步骤3生成的初始化的运动数据字典D⁽⁰⁾

和步骤4 生成的稀疏表达矩阵A进行迭代优化，得到优化后的运动数

后的稀疏表达矩阵A_优化，

据字典D_优化和优化

减小步骤4带来的数据重建误差；

（6）后续无损编码压缩：该步骤对步骤2中抽取的其他数据H、步骤5中生成

的优化后的运动数据字典D_优化和优化后的稀疏表达矩阵

A_优化进行无损数学编码 压缩，

压缩过程采用Huffman编码，得到最终压缩后的二进制数据文件，压缩

本发明的有益效果是，本发明公开了一种针对运动数据的压缩方法，利用

对生成字典的线性组合来表达每一帧的运动数据，实现了高效的运动数据压

本方法可以达到较高的压缩比，同时保证恢复后的重建误差控制在一

低的水平。此外，这一方法对较短运动数据效果良好，解决了

对于较短运动数据无法有效压缩的难题；因此还可有效

库，为动画制作等相关应用领域提供了极大的方

义。

过程完成。

缩。

个相对很

该领域其他方法

支持增量式的运动数据

便，在实际生产中具有重大意

具体实施方式

下面对本方法具体步骤及涉及的预备知识进行详细描述，本发明的内容将

一、K-means聚类算法

K-means聚类算法将给定的n个数据对象自动划分为k个聚类（k为输入量），

1）从n个数据对象随机选择k个对象作为初始聚类中心（默认为随机选

择，也可以指定k个对象或指定k个初始聚类中心点坐标，在本方法中由于

化流程的需要，只能随机选择k个对象，因此聚类结果会存在较小的

使得每个数据对象被分配到欧氏距离最近的聚类中。具体实现步骤如下：

变得更加易于理解。

自动

误差）。

2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象

3）重新计算每个聚类的均值（中心对象）。

4）循环2）到3）直到每个聚类不再发生变化为止。

二、Sparse方法

对于给定原始数据列向量b，字典L/K＝K/n(L≥2)，Sparse方法旨在求解下

mi>b-

φx||22

,0≤L;

其中，L是指定的参数，用来约束每一组字典的线性组合b中非零元素的个

解决Sparse问题的算法有很多，本方法中用到的是OMP算法，具体方法如

输入：矩阵φ，向量b，稀疏度m。

初始化：定义余向量r₀＝b。

循环执行下列步骤，循环变量t=1～m

下：

数上限，是约束表达式x稀疏性的参数。

面方程：

的距离，并根据最小距离重新对相应对象进行划分。

A.在φ中找出与余向量最相关的列向量ω_t：

B.解下列最小二乘问题并更新余向量r_t：

y_t=arg min||b-Φ_ty||₂，

r_t=b-Φ_ty_t，

其中，

输出：系数表达向量

本发明基于稀疏表达的运动数据压缩方法，包括如下步骤：

1、运动数据采集

运动数据是逐帧存储的人体骨骼关节点信息的数据，在动画制作、3D游戏、

关

交互娱乐、运动仿真等领域都有广泛应用。运动数据的采集一般通过对演员

节部位贴标记点，并通过多视角的专业运动捕获设备，在专门的场景

员运动时的关节点运动轨迹，并存为通用格式（包括bvh、trc

文件。

中采集演

等）的运动数据

本发明中所用的运动数据通过运动捕获系统采集得到。使用Vicon运动捕获

系统（/），对贴于人体关节处的marker点的

捕捉，为了与数据库中的数据保持一致，我们也使用

University，卡耐基梅隆大学）的marker点集配

轨迹信息进行

CMU（Carnegie Mellon

置方案（参考

/markerPlacementGuide．pdf）。这样可以保

处理数据具有相同维度和关节对应关系。 证数据库与待

2、解析运动数据文件

这一步为预处理步骤。一般运动数据文件格式包括bvh、trc等。对运动数据

文件的解析是将文件中运动数据Y（数据矩阵形式）和其他数据H（包括模

息、帧数、采样率等）进行区分，以方便后续处理。 型信

3、运动数据字典生成

本步骤对步骤2中抽取的运动数据Y进行处理，通过K-means聚类算法聚为

4、稀疏表达（Sparse Coding）求解

对运动数据中每一帧的信息用步骤3中生成初始化的运动数据字典D⁽⁰⁾

进行 线性表达，并用Sparse方法（OMP算法）求解运动数据Y的稀疏表

该稀疏表达矩阵A即为运动数据

K类，生成初始化的运动数据字典D⁽⁰⁾，其中，K为字典大小。

达矩阵A，

Y的压缩形式。

这一步的求解过程是有损的，但步骤5的优化过程可使得数据重建误差控制

5、应用K-SVD优化方法对步骤3生成的初始化的运动数据字典D⁽⁰⁾

和步骤4 生成的稀疏表达矩阵A进行迭代优化，优化后的运动数据字

稀疏表达矩阵A_优化，减小

在很低的范围内。

典D_优化和优化后的

步骤4带来的数据重建误差。

本步骤基于Sparse理论及其求解方法，并用K-means和K-SVD方法对字典

输入：运动数据Y，字典大小K，稀疏表达上限L，循环次数J。

输出：优化后的运动数据字典D_优化，优化后的稀疏表达矩阵A

优化。

初始化：

用K-means算法将运动数据Y聚类为K类，令D⁽⁰⁾为每类中心位置向

量的集

循环执行下列步骤，循环变量j＝1～J；

（1）用Sparse方法（OMP算法）求解下列方程，计算稀疏表达矩阵

A^(j)：

${\min }_{a_i}$

>=||y

mi>i-

Dai||

n>22,i＝1,2,…,n；

i||₀≤L；

其中，a_i为A^(j)的第i列，y_i为Y的第i列。

合。对D⁽⁰⁾做归一化处理。

生成过程进行处理和优化，具体如下：

（2）循环执行下列步骤，循环变量k=1～K；

（a）定义