基于半监督距离学习的运动相似性度量算法

李 斌,孙怀江

(南京理工大学计算机科学与工程学院,南京210094)

基于半监督距离学习的运动相似性度量算法

李 斌,孙怀江

(南京理工大学计算机科学与工程学院,南京210094)

人体运动捕获技术的发展使得运动捕获数据不断积累,人体运动的检索技术成为运动数据管理和重用过程中的关键环节。由于逻辑相似的运动在数值上并不一定相似,使用欧式距离度量2个运动间的逻辑相似性难以取得理想的结果。为此,提出一种半监督的距离度量学习算法,利用带标记的运动和未标记运动进行训练以得到运动间的马氏距离度量,从而判断2个运动之间的逻辑相似性,实现运动检索。实验结果表明,与现有的大部分检索算法相比,该算法能够得到更高的查询精度,且没有任何人工干预,可应用于自动检索领域。

人体运动捕获数据;半监督;距离学习;相似性度量;检索;识别精度

1 概述

在计算机三维人体动画技术领域,人体运动捕获数据的研究是极具挑战性的课题。利用运动捕获数据来驱动人体运动,可以得到符合人们视觉要求的动画效果,这种方法为动画创作提供了重要的媒体素材。伴随着运动捕获技术的向前发展,大量的三维人体运动捕获数据得以积累,并已经建立起很多大规模运动数据库［1-2］。在对数据库进行管理和重用的过程中,不可避免地需要进行数据库的查询和浏览操作,因此,在数据库中如何精确高效地检索运动数据成为一个十分重要的问题。

在传统的人体运动捕获数据检索方法中,基于内容的方法往往可以得到较好的结果,该类方法中运动数据相似性度量的研究是其主要难点。在给定特征的情况下,比较2个运动之间的相似度是一件困难而又至关重要的事情。相似性度量最简单的方法是使用欧式距离度量,但是很多研究表明逻辑上相似的运动在数值上并不一定相似［3］,这样在运动捕获数据的相似性度量上欧式距离难以取得理想的结果。现有的方法往往使用字串匹配［3-5］、向量夹角余弦［6］、欧式距离［7］来度量运动间的相似性并用于检索,但很难得到满意的结果。另一方面,距离度量学习在信息检索中也扮演一个重要的角色,很多研究表明学习适当的距离度量并通过其进行相似性度量能够改善检索算法的精度［8］,文献［9-11］也证明使用监督或半监督度量学习,能够很好地改善通过度量相似性而得到的检索结果。因此,很多研究人员尝试通过少量的监督信息,自动地进行距离度量的学习,以提高检索质量。随着运动捕获数据的不断积累,人工标记运动数据变得越来越难,得到的数据往往只有一部分是标记了正确的信息,其他大量的数据都是未标记的。仅使用监督学习方法使得检索范围局限于有限的类别中,很难使其所学习到的距离度量准则扩展到其他类别运动数据上。文献［12］提出了一种半监督的距离学习方法,用来度量运动数据帧与帧之间的相似度,相对于传统的基于监督学习的建模方法,这类方法能够自动地(半自动地)建立模型,可以减轻人的负担,同时增强算法的适用性。

目前传统的运动数据检索方法大多着重于运动特征的提取。运动捕获数据是高维时序数据,并且帧率高、数据量庞大、缺少结构化信息。很多方法过度依赖于特征提取的好坏,并且这些方法所提供的特征往往只能够区分部分运动类别,很难应用于实际场合。为了能够尽可能地反映人体运动的内在规律,特征的选择上应该丰富、全面。但是这样也带来了一些问题,特征与特征相互之间的关系变得更加复杂,维度越高越难以进行分析,使得运动数据间相似度计算困难,简单的度量很难得到理想的结果。

针对这些问题,本文提出一种半监督距离学习方法,给出一种有效的相似性度量标准,用于运动数据的检索。尽可能有效地利用已标记运动数据的类别信息,使得逻辑相似的运动数据之间距离尽可能地小,而逻辑不相似运动数据之间的距离尽可能地大。同时,由于存在大量的未标记运动数据,使用稀疏表示中的相关方法［13］建模来挖掘未标记运动数据之间以及标记运动和未标记运动之间的相似性关系,而这些关系可以使所学习的度量准则更加准确。

2 特征提取

由于不同的运动捕获设备所捕获的人体运动数据结构不同,为了能够有效地处理来源不同的数据,本文使用人体最重要的15个关节进行特征提取,也即根关节、头部、颈部、躯干和四肢等重要关节。

一般情况下,2个运动数据在时间上是不等长的,需要使用动态时间规划(DTW)对2个数据在时间维度上进行对齐,但这样造成了一定的信息损失和不必要的干扰。文献［7］使用关节间的相对距离(JRD)作为特征,并在JRD基础上,提出了关节相对距离的方差(VJRD)作为特征,方差表示每个JRD在其均值上的波动范围。文献［12］提出了几何姿态描述符(GPD),几乎包含了运动姿态中的各种信息,如关节位置、关节间距离、关节间夹角和关节到某个平面的距离等信息,能够有效地表示运动数据。VJRD能够保留运动逻辑相似性的同时避免DTW的对齐操作。但是VJRD仅仅包含了关节间距离的信息,对于复杂的人体运动数据,其信息量包含不够,所以使用特征极为丰富的GPD替换JRD作为特征。

本文使用VGPD作为一个运动序列的特征。对于一个运动序列M,可以形式化地表示为M={F1, F2,…,FT},包含T帧运动数据,Ft(1≤t≤T)表示其中的一帧。对于每一帧来说,需计算1 683个特征。构造运动序列每一帧GPD,当一个运动序列得到其GPD后,可简单地通过式(1)求取其VGPD:

3 半监督距离学习

人体运动数据库可以形式化地表示成X={x1, x2,…,xi,…,xN},其中,N表示数据库中运动序列的个数,xi∈Rd(d=1 683),表示单个运动序列。另外,数据库中包含一部分带有类别标签的数据,用yij∈{0,1}表示第i个运动和第j个运动是否属于同一类别运动。任意2个运动序列之间的欧式距离为:

采用欧式距离进行相似性度量的优点是有较高的计算效率,而不足之处是计算过程忽略了运动数据特征的语义解释,这种度量方法不能和人的相似度感知取得一致,也即逻辑上相似的运动在数值上并不相似,而不是所希望的逻辑相似的运动间距离小,逻辑不相似运动间距离大,很难得到准确的度量结果。自然地需要学习一个与运动数据特征描述一致的相似度计算函数,也即使用度量学习学习得到一个马氏距离度量标准M,在新的变换空间中得到符合逻辑的度量标准,所以新的距离度量公式可以表示为:

其中,M∈R1683×1683,为了保证式(3)有效,需要保证M是一个对称、半正定矩阵。所以,可以将M写为M=WTW。那么距离度量公式可表示为:

其中,W∈Rd×d′,并且d′＜d。

本文目的是通过优化学习得到最优的W,为此需要定义一系列的损失函数来达到目的。文献［10］通过引入一系列的损失函数,通过优化得到帧之间的相似性度量准则。与文献［12］相类似,首先需要充分利用运动数据的标记信息。不同于文献［12］的地方在于,当2个运动数据属于同一类时,认为它们是相似的,也就是语义上的相似,也即逻辑相似的运动其数值距离也应尽可能地小。这样需要保证相同类别的运动数据间的距离小,不同类别间的距离大。用Esimilar来表示相同类别运动数据间的距离平方和:

为了保证相同类别的运动数据间的距离小,需要最小化Esimilar,即:

同样用Edissimilar来表示不同类别运动数据间的距离平方和:

另一方面在实际应用中,有标记的训练数据往往数量很小,而存在大量无标记数据。为此,本文提出一种半监督学习方法。认为任意的一个运动序列可以被其他的运动序列线性组合进行表示,并且相同类别的运动数据具有相近的表示方法。假设X=［x1,x2,…,xN］表示相同类别运动数据所组成的一个矩阵,每一列xi表示一个运动序列,X则表示为未标记运动数据所组成的一个矩阵,同样每一列代表一个运动序列。那么可以得到:

其中,A=［a1,a2,…,aN］。式(9)表示每个标记的运动数据可以由未标记的运动数据线性表示,ai表示每个运动序列xi的重构系数。由于未标记的数据量较大,通常情况下,只是用其中的一部分运动数据就可很好地进行重构。与此同时,由于X中的运动数据同属于一个类别,这些运动数据的重构方式是相似的,也就是说使用相同的未标记运动数据就可以很好地重构所有X中的运动数据。上述2个方面的特性正好与Group-lasso［13］类似。为此本文引入它来求解A。Group-lasso可以令A中的某些行全为0,这样意味着同一类别的运动数据用同样的一批未标记数据重构,符合人类的直觉。

其中,‖·‖F表示矩阵的F范数;‖·‖2,1表示l2,1范数。原始运动数据与重构后的运动数据间的距离也小,这种信息也需要在学习中保留下来。用EG表示它们之间的距离平方和:

其中,IN表示N×N的单位矩阵;SG=(IN-A)(INA)T,那么相应的损失函数为:

但是应当注意到在未标记的数据中还包含了大量未知类别的数据,这些运动数据同样十分重要,可以采用文献［12］的方式,不同的是将之前使用过的数据剔除掉。未标记数据矩阵X中的每一个运动序列xi同样可以被其他的运动序列线性重构,与上述方法类似,运动序列xi的重构系数是稀疏的,通过式(13)进行求解:

其中,‖·‖1表示l1范数。同上一样用ESr表示它们之间的距离平方和:

其中,xi∈,最小化得到损失函数为:

综合式(6)、式(8)、式(12)、式(15)可得最终的损失函数:

式(16)是一个 trace ratio优化问题,令 A= XSdissimilarXT,B=X(Ssimilar+SG+SSr)XT,那么式(16)可以写为:

由此可以很容易地得到最优的W,进而得到M。当新来一个查询样本,用该马氏距离度量求得其与数据库中其他运动数据间的距离,将这些距离由小到大排序,即可得到检索结果。

4 实验与评价

本文实验已标记数据使用来自波恩大学的运动捕获数据库HDM05［2］,该数据库中包含了3 634个不同的运动片段,其中所有的运动片段均是单一类别运动,包含52种不同类别的运动。数据库总大小为720 MB。为了验证本文方法的有效性,将有标记的一部分数据看作是未标记数据。首先在数据库中选取出90%的运动,其中一半作为训练样本集,另一半作为测试时的待检索数据库。训练样本集中,再选取出其中的40种类别的运动数据,其中40%的运动数据用于监督学习,剩余60%的运动数据与其他12种类别的作为无标记运动数据用于训练。数据库中剩余10%的运动序列作为测试样本集进行检索。为了验证本文方法的有效性,选取了一些比较典型的方法进行对比,即无监督类方法［14］,使用了部分监督信息,但未进行度量学习的方法［7］、监督学习方法［11］以及半监督学习方法［12］。同时本文采用TopN侧率来评价检索的质量,在统计检索精度时,N的取值为待检索数据库中相应类别的样本总数。

图1列出了本文方法与其他方法的部分类比运动检索精度比较。图1被分为2个部分,其中左边8条表示有标记运动数据的检索结果,而右边6条表示无标记运动数据的检索结果。从图中可以看出,本文方法在检索质量上具有明显的优势。文献［14］使用了几何特征,是一种无监督的检索方法,由于几何特征并不能很好地表示运动数据,并且需要大量的人工干预,检索精度很难达到一个理想的水平。文献［7］利用运动的类别信息对不同类别的运动进行特征选择,进而利用线性回归得到待检索运动序列较优的特征,在一定程度上弥补了欧式距离的不足,但并未解决逻辑相似运动在数值上不一定相似这一本质问题。文献［11-12］以及本文方法通过监督/半监督的度量学习,利用运动捕获数据的类别信息有效地弥补了欧式距离的不足,检索效果得到大幅的提升。

图1 TopN策略下运动数据检索精度

另一方面,文献［14］由于不需要任何监督信息,对于无标记运动的检索要稍逊于文献［7,11］。由于文献［12］和本文方法使用半监督学习方法,使用了大量的未标记运动用于训练,对于数据库中未标记的运动也能很好地检索出来,从图中也可以看出本文方法要明显优于其他方法。文献［11］由于只使用已标记的运动数据,所能挖掘到的信息有限,当标记数目不足或不全面时,其性能将大幅度下降,例如对于走路运动来说,细分可以划分为很多种类型,如正常走路和跛行,当训练数据库中无跛行运动时,使用文献［11］方法将很难检索出跛行的运动数据。对于这种情况,文献［12］所提出的方法也很难解决。由于正常行走和跛行都属于走路,包含了相同的内在规律,本文方法通过Group-lasso来挖掘标记运动与非标记运动之间的这种关系,用于相似性度量学习,从而可以应用于各种场合。从图2的P-R曲线中也可以看出本文提出方法的检索精度和召回率已经达到一个比较高的水平。

图2 检索精度-召回率曲线(P-R曲线)

5 结束语

本文提出了一种半监督的度量学习方法,得到运动间的相似性度量标准,该标准能够很好地判断运动捕获数据之间的相似性,通过比较运动间的相似性达到运动检索的目的。实验结果表明,本文方法要优于现有的大部分检索方法,能够达到较高的检索精度和召回率。但是本文所使用的运动特征为VGPD,具有较高的维度,随着数据量的增加,需要花费更多时间进行训练。同时,本文方法在训练过程中使用了运动数据的类别信息,每种类别的运动都有较为充足的训练样本,但是在实际应用中,某些运动类别的数据可能十分少,这将直接影响训练的结果,如何有效地利用这些数据并得到较好的训练结果也是今后的研究方向之一。

［1］ CMU.Carnegie Mellon Mo-cap Database［EB/OL］.(2003-10-29).http://mocap.cs.cmu.edu.

［2］ Müller M,RöderT,Clausen M,etal.A Weber: Documentation mo-cap Database HDM05［EB/OL］.(2011-08-31).http://mocap.cs.cmu.edu.

［3］ Müller M,Röder T,Clausen M.Efficient Content-based Retrieval of Motion Capture Data［J］.ACM Transactions on Graphics,2005,24(3):667-685.

［4］ 田 枫,刘贤梅,沈旭昆,等.一种基于运动姿态的三维人体运动检索方法［J］.计算机仿真,2012,29(11): 42-46.

［5］ 刘云根,刘金刚.基于人体姿势编码的运动数据检索［J］.计算机辅助设计与图形学学报,2011,23(4): 586-593.

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

［7］ Tang J,Leung H.Retrieval of Logically Relevant 3D Human Motions by Adaptive Feature Selection with Graded Relevance Feedback［J］.Pattern Recognition Letters,2012,33(4):420-430.

［8］ 罗 辛,邰晓英,Masami S,等.一种基于度量距离学习的图像检索方法［J］.广西师范大学学报:自然科学版,2007,25(2):186-189.

［9］ Müller H,Pun T,Squire D.Learning from User Behavior in Image Retrieval:Application ofMarketBasket Analysis［J］.International Journal of Computer Vision, 2004,56(2):65-77.

［10］ Weinberger K Q,Blitzer J,Saul L K.Distance Metric Learning for Large Margin Nearest Neighbor Classification［J］.The Journal of Machine Learning Research,2009,(10):207-244.

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

［12］ Chen Cheng,Zhuang Yueting,Nie Feiping,et al.Learning a 3D Human Pose Distance Metric from Geometric Pose Descriptor［J］.IEEE Transactions on Visualization and Computer Graphics,2011,17(11):1676-1689.

［13］ Yuan Ming,Lin Yi.Model Selection and Estimation in Regression with Grouped Variables［J］.Journal of the Royal Statistical Society,Series B,2007,68(1):49-67.

［14］ 祝铭阳,蓝荣祎,孙怀江,等.一种人体运动相似性度量方法［J］.计算机工程,2011,37(12):155-157.

编辑 顾逸斐

Motion Similarity Measurement Algorithm Based on Semi-supervised Distance Learning

LI Bin,SUN Huaijiang
(School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China)

With the rapid development of the human motion capture technology,large amount of motion capture data is gradually accumulated,then human motion retrieval and recognition technology becomes the essential issue for motion data management and reuse.Logically similar motions may be numerically dissimilar,so it is difficult to get feasible results if the logical similarity between two movements is measured with Euclidean distance.This paper presents a semisupervised distance learning method for measuring the logical similarity with Mahalanobis distance which is trained by labeled and unlabeled motion data.Experimental evaluation result of the method shows that the proposed method is effective for motion retrieval.

human motion capture data;semi-supervised;distance learning;similarity measurement;retrieval;

1000-3428(2014)11-0178-05

A

TP391

10.3969/j.issn.1000-3428.2014.11.035

南京理工大学自主科研专项计划基金资助项目(2011YBXM79)。

李 斌(1987-),男,硕士研究生,主研方向:三维人体动画,运动数据检索;孙怀江,教授、博士、博士生导师。

2013-11-19

2013-12-19E-mail:lbin@outlook.com

中文引用格式:李 斌,孙怀江.基于半监督距离学习的运动相似性度量算法［J］.计算机工程,2014,40(11):178-182.

英文引用格式:Li Bin,Sun Huaijiang.Motion Similarity Measurement Algorithm Based on Semi-supervised Distance Learning［J］.Computer Engineering,2014,40(11):178-182.

identification precision