基于帧间距的运动关键帧提取

李顺意,侯 进,2,甘凌云

(1.西南交通大学信息科学与技术学院,成都610031;

2.南京大学计算机软件新技术国家重点实验室,南京210093)

基于帧间距的运动关键帧提取

李顺意1,侯 进1,2,甘凌云1

(1.西南交通大学信息科学与技术学院,成都610031;

2.南京大学计算机软件新技术国家重点实验室,南京210093)

运动捕获数据中有大量的冗余数据,不利于运动数据的压缩、存储、检索以及进一步重用。为此,提出一种基于帧间距的运动关键帧提取方法,提取代表运动捕获数据内容的关键姿势。利用四元数之间的距离表示人体姿态差异,将人体各个关节上的总变化作为帧间距,以运动数据首帧作为第一个关键帧。通过不断计算当前帧同最后一个关键帧之间的差异,消除差异小于阈值的帧,差异超过阈值的帧被当作为新关键帧。对提取关键帧集合采用四元数球面插值方法重构。为表现人体运动特征,在重构误差中引入关节速度分量,用人体姿势误差位置与人体关节运动速率之和表示原始运动与重建运动序列之间的重构误差。实验结果表明,该方法对原始运动既有较高的压缩率,又有较强的视觉概括效果。

运动捕获;关键帧提取;帧间距;球面线性插值;重构误差;视觉概括力

1 概述

在计算机动画中,人体角色动画是很重要的组成部分,但也因人体包含自由度多、维数高,创建一个真实的和逼真的运动模型是非常困难的,人体角色动画一直是计算机动画技术中的难点[1]。目前人体角色动画主要有基于关键帧的动画、基于运动学的动画、物理模拟动画与基于捕获数据的人体动画技术。近年来,随着运动捕捉设备的广泛应用,运动捕获驱动的三维人体动画替代传统关键帧动画[2]成为研究的热点。运动捕获驱动方法是利用运动捕捉设备实时记录表演者肢体在空间中的运动,生成大量有真实感的人体运动数据,然后将捕获得到的真实感的角色运动数据映射到建立好的人体模型来生成动画序列。运动数据驱动方法被广泛地应用到计算机交互游戏、电影广告、体育训练以及医学仿真等多个领域。

本文利用四元数之间的距离表示人体姿态差异,将人体各个关节上的总变化作为帧间距,以运动数据首帧作为第一个关键帧,不断计算当前帧同最后一个关键帧之间的差异,消除差异小于设定阈值的帧,差异超过设定阈值被当作为新关键帧。对关键帧集合使用四元数球面插值方法重构出原始序列帧数相同的重建序列,将原始帧与重建帧的平均帧间距离表示为重构误差,并在重构误差中引入速度误差。

2 背景介绍

运动捕获数据是以较高的采样频率获得,平均每秒钟几十帧甚至上百帧,每一帧又包含了十几个甚至几十个关节点的旋转信息,得到的数据量庞大且有大量的数据冗余,非常不利于运动捕获数据的压缩、存储、检索以及进一步重用,需提取出代表运动数据内容的关键帧[3],关键帧提取技术被广泛应用于视频分析与检索领域[4]。运动关键帧提取主要有曲线简化方法、基于聚类方法和帧消减方法。曲线简化方法[5]将每一帧运动数据比作高维空间的一个点,运动序列看成是空一条运动轨迹,选择曲线上一些凹凸点作为关键帧。但是该方法采用欧式距离作为帧间的相似度,无法真实地反映人体运动姿态之间的差异。文献[6]改进了该算法,将人体的骨骼夹角作为运动特征表示,以此确定边界姿态帧作为候选关键帧,然后采用分层曲线方法精选候选关键帧,最终获得关键帧集合,该方法对边界帧具有概括力。文献[7]提出了基于聚类的关键帧提取方法,将相似运动数据聚类,每类选择一个关键帧。该方法能够提取表示原始数据内容的关键帧,但是没有考虑运动数据之间的时序相关性,容易导致对运动序列分析的失真问题。文献[8]通过消减不可能为关键帧的帧而获得的关键帧序列,用帧消减的方法计算消减帧的重构误差,从而得到一条重构误差曲线,根据曲线判断出具有最优压缩率的关键帧,但其无法保证具有最佳压缩率下得到关键帧的同时具有最小重建误差,并且未考虑关键帧的运动表示能力。文献[9]提出了一种基于运动分割的关键帧提取方法,将段与段之间的分割点作为关键帧点,其认为分割点最能表示运动变化最剧烈的姿态,但是该方法未考虑误差问题,不适合运动压缩。文献[10-12]提出一种基于混合遗传算法的人体捕获数据关键帧提取方法,将遗传算法与单纯行法相结合。文献[13]提取一种预选策略与重建误差优化的运动关键帧提取方法,将关键帧提取分为帧预选和基于重建误差优化的2个阶段。

基于以上分析,如何根据用户需求使提取运动关键帧既能够满足大规模实时压缩需要,又对原始运动具有很好的视觉概括力是关键帧的追求目标。

3 人体结构简化与运动表示

人体有200多块骨骼,600多个自由度,主要由骨架层、肌肉层和皮肤层组成,但为了降低人体运动复杂度,通常将关节运动简化。层架骨架模型是一种常用的人体模型,是支撑人体运动最核心的部分,决定了人体运动的各种姿态。两段刚体关节之间称为关节,连接相邻2个关节的刚体是骨骼段,人体关节点的数目决定了运动的丰富性,关节点过多则包含运动信息更丰富,但也加大了编辑和计算复杂度,反之人体模型太简单,则容易丢失重要运动细节信息,运动不够细腻。本文将人体骨架模型简化为29个关节点(含根节点,共计56个自由度)连接起来人体模型,人体树形结构拓扑如图1所示。

图1 人体树形结构拓扑

3.1 人体运动的描述

人体运动是由根节点的平移和其余各节点相对于其父节点的旋转来实现的,根节点的平移决定了人体的运动轨迹,根节点的旋转决定人体的运动方向。除根节点外,其他各节点的旋转在以父节点为坐标原点的局部坐标系下进行,其他节点旋转决定了人体旋转状态,通过每一段骨架的长度和旋转矩阵就能计算出各关节点在世界坐标系中的位置,关节点Jm+1在世界坐标系下的位置可由公式求出:

3.2 四元数

四元数q可以记为:

其中,w,x,y,z为实数,四元数可以写成抽象形式:

3.3 旋转的表示

表示将向量r绕向量v旋转θ角。

3.4 四元数球面线性插值与线性插值

四元数球面插值是2个单位四元数在单位超球面上插值,假设有单位四元数q1和q2,从q1到q2的球面线性插值记为Slerp(q1,q2,t),则有:

设相邻2帧t1和t2根节点位置分别为P1和P2,t时刻跟关节所处的Pt(t1＜t＜t2),则两者线性插值为:

3.5 四元数之间的距离

图2 四元数距离

若q1,q2为2个单位四元数且q2q-1=[ω,x,y,z],2个四元数之间的距离表示为:

在四元数表示法中,人体可以表示为离散时间向量函数:

其中,p(t)∈R3表示根关节平移运动;qi(i=1, 2,…,m)表示关节i旋转运动,在一个运动序列中不同时刻t1,t2上的2帧,它们之间的距离D(t1,t2)表示为:

d(qi(t1),qi(t2))表示在t1,t2时刻关节i旋转的四元数距离,wi(i=1,2,…,m)为各关节对运动姿势影响程度大小。

如果有不同的运动序列A与运动序列B,A的每一帧到B的每一帧之间的距离也可以用两者之间四元数的距离表示:

表1 各关节点对应权值

4 运动关键帧提取与运动重构

数组keynum[j]用来记录提取的关键帧集合,lastkey表示当前为止搜索到最后的关键帧,n为运动序列长度,δ为事先设定的阈值,主要根据用户针对不同运动对压缩率需求确定,keynum为提取关键帧数目,算法步骤如下:

Step 1将第一帧作为关键帧加入到keynum,并使lastkey=1,初始化循环变量t=2。

Step 2若t≥n,则算法停止;否则计算帧间距离d=D(t,lastkey)。

Step 3若d≥δ,第t帧作为关键帧被提取保存在keynum[j],并使lastkey=t。

Step 4t=t+1,返回Step2;直到算法结束,keynum[j],j∈[1,2,…,keynum]记录了所有关键帧。

运动重构是在提取关键集合后,对相邻关键帧之间的非关键帧进行插值重构,从而重构出与原始序列相同帧数,重建算法步骤如下:

Step 1初始化循环变量j=0。

Step 2若j≥keynum-1,则算法结束;否则取相邻关键帧T1=keynum[j],T2=keynum[j+1]。

Step 3对T1与T2之间的非关键帧进行插值重建,根关节采用一般线性插值,其他关节采用四元数球面插值。

Step 4j=j+1,返回Step2。

真实的人体运动具有较强的真实感,为较好地捕捉人体动态特征,考虑运动数据时序性与运动特性。用人体姿势误差位置与人体关节运动速率差来表示原始运动与重建运动序列之间的误差(重构误差),重构误差用原始帧与重建帧的平均帧间距离表示。重构误差与关键帧提取数目、人体关节运动速率密切相关,一般来说往往越少关键帧提取,重构误差越大。

设m1为原始运动序列,m2为关键帧集合插值重构序列,长度均为n,重构误差E(m1,m2)表示为:

D表示人体姿势加权距离,主要用以衡量人体姿势的位置误差,表示为:

5 实验结果及分析

5.1 实验结果

本文在Windows7操纵系统下,选择Microsoft Visual Studio 2010作为开发平台,使用OpenGL和卡耐基梅隆大学运动捕获数据库,以MFC框架搭建了虚拟人运动编辑平台,在该平台上实现对运动捕获数据关键帧的提取功能。选择骨架文件是asf(acclaim skeleton file)格式,运动数据是amc(acclaim motion capture data)格式,实验在英特尔core i3M380, 2.53 GHCPU,2 GB内存上的PC上进行。

实验选取行走、腾空跳跃、翻筋斗3种运动类型来测试本文算法的有效性,采样频率均为40 f/s。实验1对运动长度为150 f的行走走路运动分别采用文献[5]方法、文献[7]方法、文献[9]方法与本文方法进行关键帧提取,关键帧提取效果如图3～图6所示。实验2对运动长度为144帧的腾空跳跃运动分别采用文献[5]方法、文献[7]方法、文献[9]方法与本文方法提取关键帧,关键帧提取效果如图7～图10所示。实验3对运动长度为296帧的翻筋斗运动分别采用文献[5]方法、文献[7]方法、文献[9]方法与本文方法提取关键帧,关键帧提取效果如图11～图14所示。

图3 文献[5]方法提取的行走关键帧集合

图4 文献[7]方法提取的行走关键帧集合

图5 文献[9]方法提取的行走关键帧集合

图6 本文方法提取的行走关键帧集合

图7 文献[5]方法提取的腾空跳跃关键帧集合

图8 文献[7]方法提取的腾空跳跃关键帧集合

图9 文献[9]方法提取的腾空跳跃关键帧集合

图10 本文方法提取的腾空跳跃关键帧集合

图11 文献[5]方法提取的翻筋斗关键帧集合

图12 文献[7]方法提取的翻筋斗关键帧集合

图13 文献[7]方法提取的翻筋斗关键帧集合

图14 本文方法提取的翻筋斗关键帧集合

5.2 实验分析结果

从图3～图5提取关键帧集合视觉效果来看,本文方法较好地对行走运动进行概括,而文献[5]方法提取的关键帧无法反映运动帧之间的真实差异,文献[7]方法与文献[9]方法虽然也能概括行走运动序列,一些关键帧仍然丢失且可能导致运动序列分析的失真。

从图7～图10提取关键帧视觉效果可以看出,本文提出的方法对腾空跳跃运动提取没有丢失重要关键帧,文献[5]方法提取帧数过少,无法概括运动内容,文献[7]方法与文献[9]方法虽然也能概括行走运动序列,但是其一些关键帧仍然丢失且帧间距过大。

从图11～图14提取关键帧视觉效果来看,本文方法提取关键帧集合能较好地对翻筋斗运动进行概括,文献[5]方法关键帧与文献[7]方法无法反映运动帧之间的真实差异,丢失在关键时刻的过度帧,容易造成对运动序列内容分析的失真,文献[9]方法虽然也能概括行走运动序列,但视觉效果上不如本文方法。

运动重建部分采用使用四元数球面插值方法进行了重建,选用四元数插值算法原因是其能保证提取相邻关键帧键帧姿态差异较大时,也能插值生成较平滑的中间帧动画。重构误差大小与关键帧提取数目有关,对150帧行走运动的重建误差曲线如图15所示。

从图15可以看出提取关键帧数目越少,重构误差越大。u为加权拟合参数,主要调节速率差与位置差的加权比例。图16绘制的是144帧腾空跳跃运动的重建误差曲线,可以看出腾空跳跃运动特性更加明显,当然其加权拟合参数u越大,重构误差也比步行运动大。

图15 行走运动重建误差曲线

图16 腾空跳跃重建误差曲线

6 结束语

本文提出的方法在重构误差中引入速度分量,充分考虑了人体运动节奏性强的特点,从视觉上看,提取关键帧对原始运动数据具有较好的视觉概括能力。针对不同运动类型都压缩率较高(小于7%)且能代表运动内容,满足了大规模实时压缩的需要,大大降低了运动编辑的复杂度。今后工作是研究一种自动评价指标,甚至引入语义信息,从而更加精确地提取人体边界姿势,更好地致力于大规模运动捕捉数据的合成、检索与编辑。

[1] 刘贤梅,张巧生.数据驱动的人体动画合成研究综述[J].计算机工程与设计,2010,31(18):4054-4057.

[2] 刘贤梅.数据驱动的人体动画的关键帧技术研究综述[J].计算机工程与设计,2011,32(3):1006-1009.

[3] 潘志庚,吕 培,徐明亮,等.低维人体运动数据驱动的角色动画生成方法综述[J].计算机辅助设计与图形学学报,2013,25(12):1775-1785.

[4] 孙淑敏,张建明,孙春梅.基于改进K-means算法的关键帧提取[J].计算机工程,2012,38(23):169-172.

[5] 杨 涛,肖 俊,吴 飞,等.基于分层曲线简化的运动捕获数据关键帧提取[J].计算机辅助设计与图形学学报,2006,18(11):1691-1697.

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

[7] Zhang Qiang,Yu Shaopei.An Efficient Method of Keyframe Extraction Based on a Cluster Algorithm[J]. Journal of Human Kinetics,2013,39(1):5-14.

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

[9] 朱登明,王兆其.基于运动序列分割的运动捕获数据关键帧提取[J].计算机辅助设计与图形学学报, 2008,20(6):787-792.

[10] 刘贤梅,郝爱民,赵 丹.基于混合遗传算法的人体运动捕获数据关键帧提取[J].模式识别与人工智能, 2011,24(5):619-628.

[11] Liu Xianmei,Hao Aimin,Zhao Dan.Optimization-based Key Frame ExtractionforMotionCaptureAnimation[J].The Visual Computer,2013,29(1):85-95.

[12] 刘贤梅,赵 丹.四元数样条插值的人体运动数据重构[J].计算机工程与应用,2012,47(36):151-154.

[13] 蔡美玲,邹北骥,辛国江.预选策略和重建误差优化的运动捕获数据关键帧提取[J].计算机辅助设计与图形学学报,2012,24(11):1485-1492.

编辑 顾逸斐

Extraction of Motion Key-frame Based on Inter-frame Pitch

LI Shunyi1,HOU Jin1,2,GAN Lingyun1
(1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031,China;
2.State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093,China)

To solve the problem that the motion capture data has a large number of data redundancy,this paper proposes a key frame extraction method based on inter-frame pitch.In order to compress,storage,reconstruct and further reuse motion data,key-frame is needed to be extracted which represents the content of the motion.Quaternion is introduced to represent the difference between two rotations.The distance between two frames is defined by the total rotation differences and first frame is regarded as the first key frame.Then,calculate the difference between the current frame and the last key frame continuously.The frame is eliminated when the difference is smaller than the set threshold or the opposite is reserved for the new key frame.Spherical linear interpolation is used to reconstruct the sequence.To express the characteristics of human motion,the joint velocity is introduced.Reconstruction error is defined by the human body posture error of position and the motion speed error between the original frame and the reconstructed frame.Experimental result demonstrates that the original motion capture can be compressed in a high ratio and gives a good visual summary performance.

motion capture;key-frame extraction;inter-frame gap;spherical linear interpolation;reconstruction error; visual summary performance

李顺意,侯 进,甘凌云.基于帧间距的运动关键帧提取[J].计算机工程,2015,41(2):242-247.

英文引用格式:Li Shunyi,Hou Jin,Gan Lingyun.Extraction of Motion Key-frame Based on Inter-frame Pitch[J]. Computer Engineering,2015,41(2):242-247.

1000-3428(2015)02-0242-06

:A

:TP391

10.3969/j.issn.1000-3428.2015.02.046

国家自然科学基金资助面上项目(61371165);浙江大学CAD&CG国家重点实验室开放课题基金资助项目(A1416);计算机软件新技术国家重点实验室开放课题基金资助项目(KFKT2013B22);四川省动漫研究中心2012年度科研基金资助项目(DM201204)。

李顺意(1988-),男,硕士研究生,主研方向:人体动画;侯 进(通讯作者),副教授;甘凌云,硕士研究生。

2014-03-24

:2014-05-05E-mail:jhou@swjtu.edu.cn