基于连续数据流的动态手势识别算法

郑 韡 沈旭昆

（北京航空航天大学 虚拟现实技术与系统国家重点实验室，北京 100191）

基于连续数据流的动态手势识别算法

郑 韡 沈旭昆

（北京航空航天大学 虚拟现实技术与系统国家重点实验室，北京 100191）

为识别用户做出的动态手势序列，基于数据手套采集的连续数据流，运用奇异值分解消除数据噪点，提取手势的特征信息，并利用关节弯曲的生理学特性与用户解耦合，将各种动作片段抽象成用户无关的手势模板，从而唯一定义手势特征并屏蔽不同用户的手势差异，再基于Hill Climbing思想把连续数据流分割成有序的动作序列，并按时序对所有片段在预先构造的层次树上实时搜索，根据欧式距离度量序列与手势模板的相似性.该算法对手势序列的分割准确，对多用户具有良好的适应性，其有效性在使用5DT数据手套搭建的两组动态手势识别的实验中得以验证.

连续数据流;奇异值分解;动态手势识别

在虚拟现实的人机交互环境中，用户借助大量自然的输入设备（如触力觉设备、定位设备等）与计算机交互，计算机通过分析它们的数据理解用户的动作指令，实时做出反馈，从而让用户获得自然、真实的类人际交互的沉浸感和体验.对这类传感器数据的分析、处理过程和传统的数据库查询［1］操作存在很大的差异性，后者的数据稳定，基于精确匹配就能完成全局数据库的搜索，而传感器数据由于是连续到达、不断变化的［2］，它有着以下几个方面的特点:①连续性.传感器以连续的数据流形式输出，数据不断变化和更新，因此给查询、匹配操作带来了挑战.②高维度.通常测量实验需要部署大量传感器，数据输出维度高，采样密度大，对存储带宽和容量要求高，导致基于大数据量的实时查询难以保证.③干扰性.连续性的数据流中存在大量冗余、无效信息，从中分割源数据并提取有用的信息元比较困难.

目前基于连续数据流的工作主要集中在网络流量监控、数据挖掘等［3］领域，在人机交互以及智能机器人领域，连续数据流被用来做手势动作的识别［4］，通常需要先变换数据完成空间压缩，并选取合适的度量方法如Minkowski，Manhattan，Canberra［5］等，最后进行目标的匹配和分类.主要的降维方法是采用离散傅里叶变换（DFT，Discrete Fouriet Transform）、小波变换（DWT，Discrete Wavelet Transform）［6］以及主成分分析法（PCA，Principal Component Analysis）等，基于线性变换提取特征信息，缺点在于上述不能保证寻找到一个最低维度的子空间用于包含最大的特征点，无法适用于实时性要求高的精确匹配操作.匹配算法主要基于隐马尔科夫（HMM，Hidden Markov Model）［7］、模糊识别［8］、神经网络（NN，Neural Network）［9］和支持向量机（SVM，Support Vector Machine）［10］等，其基本思想是利用大量样本训练分类器，从而根据标签对样本分类，虽然这些方法识别率很高，但由于需要一个长时间的样本训练阶段，建立的手势库和佩戴用户耦合紧密，在更换用户的情况下需要重建手势库，过程复杂漫长，无法适应多用户协同工作的环境.

本文针对数据手套采集的连续数据流的特点，提出一种全新的动态手势的识别算法，既保证了识别的实时性和精确性，又能够方便适应于多用户的协调环境.

1）采取奇异值分解法（SVD，Singular Value Decomposition）压缩数据空间，同时最大化保留原始数据的特征信息，这种能量最优化的分解方法，在数据压缩和特征保留之间做了平衡，既保证了实时性又实现了匹配的精确性，从而满足对高维度数据实时精确匹配的要求.

2）基于Hill Climbing思想从数据流中提取出动作片段信息，利用关节弯曲范围的生理特性将动作元的冗余数据剔除，并与用户生理信息解耦合，抽象成一种通用的手势模板，从而适应在多用户协同工作环境中，无需重建手势库即能对当前用户的动态手势做出准确识别.

1 手势识别的方法分析

动态手势是不固定时长的一串动作序列，可以理解为一系列离散的动作片段按照先后次序排列构成，每个动作片段可以看成一种静态手势.

为了识别动态手势序列，将识别过程拆分成2部分，首先从连续数据流中分割出独立的动作片段，其次用一种相似性度量方法对它们进行匹配识别.用户做出的某种动态手势可以用G=（g1，g2，…，gn）描述，其中 g1，g2，…称为一个个独立的动作元片段，通过定位每个动作元的起始点和结束点，将他们分离，并对这些动作元进行数据压缩，抽取与用户无关的特征信息，抽象成手势模板，最后利用相似性度量方法，通过遍历预先构造的搜索树，查询匹配的手势.

整个识别流程包含手势库搭建和实时手势识别2个模块，如图1所示.

图1 动态手势识别的2个阶段

2 手势识别的关键技术

2.1 基于奇异值分解的特征提取

和传统的输入设备相比，数据手套能够提供更多的描述手指和手掌姿态的自由度，从而完整的定义佩戴用户当前所做的手型，并记录下时间戳.虽然这组数据详细描述了用户的手势信息，但是它不可避免的带有以下缺点:

1）数据和用户耦合.用户手型存在的个体性的生理差异（如尺寸长短、关节比例等），导致不同用户做同样的手势，传感器数据并不相同.

2）传感器值敏感.传感器的采样频率高（＞75 Hz），精度高（＞8位有效数字），同一用户重复做相同的手势，前后获得的数据也可能差异很大，导致数据冗余.

3）数据维度高.手的生理构造复杂，关节运动灵活，数据手套通常需要14～22个传感器才能准确描述手型的姿势.

4）噪点扰动大.传感器记录的时间段涵盖了手臂抖动、不同手势间的过渡动作，这些无效信息需要进行过滤.

为此需要进行适当的数据压缩和特征提取以保证算法的实时性.奇异值分解法（SVD）被广泛应用于信号处理、模式识别等领域.根据奇异值分解的性质，任意一个矩阵Gm×n，总存在m阶对角阵 U=［u1，u2，…，um］和 n 阶对角阵 V=［v1，v2，…，vn］，使得

其中 σ1≥σ2≥…≥σp≥0 是 Gm×n的奇异值.

根据分解矩阵和原始矩阵的能量关系，存在如下定理:

由定理1可以推出SVD分解后的矩阵能量，描述为

基于上述理论，SVD把数据集的特征值按照重要性排列，经过矩阵变换舍弃不重要的特征向量，完成数据降维，并把剩余的特征向量按照能量关系张成特征子空间，采取最优分布原则，从而最大化的保留了原始数据的核心特征信息.

假定用户佩戴一副有m个传感器的数据手套，重复做一种手势n次，以m作为行向量，n为列向量，将数据表示成矩阵形式Gm×n，为了最大限度的记录当前用户手势的全部信息，需要多次采样，该原始矩阵的n值通常很大.

对原始矩阵Gm×n进行SVD分解，对得到的m阶对角阵U提取左侧的r列向量SrU，r≪n，过程如图2所示.

图2 SVD从原始矩阵中提取最大子空间

由于通常情况下采集的样本数n远大于传感器数量m，又根据能量最优原理子空间最大程度的保留了原始矩阵的变化量.于是，经过SVD分解后，高维的原始矩阵在完成空间维数压缩的同时保留了手型的关键信息，该r维子空间称为手势的数据描述文档.

2.2 抽象手势模板

尽管不同用户做同样的手势，测得的数据不尽相同，但是人手的关节弯曲有一定的范围和限度，在定义一种初始状态的情况下（例如定义握拳为初始状态），不同的手势和初始状态的差量（即关节的弯曲变化区间）能够唯一的描述该手势，避免直接使用手势对应的关节弯曲角度量，因而这种描述和特定用户无关，它是一种通用的手势模板.

通过上述方法剔除和用户耦合的数据，抽象出一种通用的手势描述模板，能屏蔽用户在生理构造上的差异性，从而避免繁琐的标定步骤，并且模板库的更新和维护能够实时进行，极大的简化了用户操作流程，从而适应多人协同的工作环境.图3详细说明了构建抽象手势模板的具体过程.

图3 抽象手势模板的搭建过程

1）计算差值.

2）传感器值是连续线性变化的，在t时间段，不断刷新当前的最大值和最小值，获得手势的动态运动范围，把归一化到0～1区间:

3）由于数据流是连续的，选取合适的离散因子k进行离散化处理，获得不同关节弯曲范围的分布图.

4）传感器的测量值是无符号的，需要额外加上方向信息，根据手势的差值，如下定义正、反两个运动方向:

将式（7）定义的方向信息加入Di中:

由于G描述了手势St相对初始状态St0的运动增量和方向，而不是具体的关节弯曲角度，因此G与特定用户的手型无关，它是该手势的一种抽象表述，图4是某个手势片段的原始数据流转成手势模板的文本描述示意图.

图4 原始数据流和手势模板的文本描述

2.3 基于Hill Climbing的手势提取

由于不同用户做同样一组手势的时间不尽相同，原始的动态手势是一串不固定长度的数据流信息，需要将其表示成由动作片段构成的序列，即分割成独立的静态手势的集合，由于片段间的时间间隙不确定，本文采用基于Hill Climbing启发式的思想，对这些动作片段的始末点进行检测并实时提取.

Hill Climbing广泛应用于寻求局部最优解，采用启发式方法，利用反馈信息帮助生成解的决策.初始状态算法随机选取一个节点，搜索从该节点开始，和周围邻居节点的值进行比较.如果当前节点是最大的，那么返回当前节点，作为最大值（即山峰最高点）;反之就用最高的邻居节点替换当前节点，从而实现向山峰的高处攀爬的目的，如此循环直到达到最高点，从而输出局部最优解.

本文用Gm×t表示一段时长为t的动态手势，含有m 个传感器，数据库（g1，g2，…，gn）表示已知的n种抽象手势模板，S（Gm×t，gi）度量当前数据流和某种手势模板的相似性.在Gm×t中检测已知的手势片段时，将待检测项与整串数据比较，一旦串中出现待检测项的开始点时，两者的相似性开始逐步累加，直到相似性出现拐点时说明检测到动作片段的结束点.记录下全局过程中的每个相似性变量，并把它们放入备选集中，最后从中输出一个全局最大值，这个值代表的数据串的始末点就是与待检测项最为匹配的部分，从而将手势转化为一组动作元序列.

图5显示了在时长约为3 s的一段数据流中提取3个静态手势的示意图，该串原始数据代表由手语L，V，I构成的动作序列.开始时段，由于手语Y的拇指关节的弯曲度和L很相似，造成Y的相似度较高，当测到差异性关节点时，Y的相似性开始急剧减少，L则稳固上升.在0～10时间段的检测中，可以判定存在手语L而排除Y.在10～25时段，字母U和V的手势非常相似，因此算法检测出2个局部最优解，最终通过全局最优判断是手势V.

图5 从连续数据流中提取手势片段

2.4 手势匹配

计算机要判别用户的手势，其实质是将n个数据映射为手势库中的一种，为此，逐次将这些动作元与模板进行相似性度量，即可确定动态手势的种类.

为提高搜索速度，将手势库按照不同姿态进行分类.根据操作对象的形状和动作性质的不同，可以对手指相应关节的变化做层次划分，图6示意了一种通用的姿态分类方法［11］.

图6 手势的层次分类图

例如在抓取手势中，食指和无名指的部分关节（指尖关节DIP、跟关节MIP）会产生显著变化，而在触碰手势中通常变化幅度不大，通过对不同关节进行组合，根据它们的变化趋势对应到手势分类中，构建一棵层次搜索树.由于相似手型基本都集中在某一个父节点之下，遍历时采取深度优先搜索，并根据搜索的叶子节点的上下限是否越界进行判定，能够实时的定位到所要匹配的手势模板.

由于手势模板是由大量样本聚合而成，因此利用欧式距离:

进行模板匹配时，必须设定一个阈值θ，以保证存在一个允许的扰动区间，并根据如下规则对手势进行判定:

其中，mi代表手势模板;gi代表动作元片段.对于Gm×t序列的每个片段均做如上的匹配，当且仅当动作序列的时序一致并且相应的匹配均落在预定的阈值范围内时，可以判定当前的动态手势.

当手势库涵盖待检测的动态手势的全部动作片段时，算法输出最佳匹配项;当出现动作元不在手势库的情况时，一般的识别算法如神经网络，由于样本类别未知而无法对其进行归类.本算法利用k最近邻法，计算它与手势库中每个模板的相似度，找出k个最相似的匹配项，根据加权距离判断所属类别，从而输出最为相似的手型作为识别结果.

3 实验结果和分析

为了验证本文所述算法的可行性和效果，按照图7的结构框架搭建了一个动态手势识别系统.

图7 手势识别系统设计框架

采用5DT Data Glove Ultra 14型号的数据手套［12］作为输入.该手套使用14个光学光纤传感器测量每个手指关节（基部关节PIP、中间关节MCP）的弯曲角度，输出8位有效数值，采样频率75 Hz（约0.01 s采样一次）.为了提高交互性，引入了基于骨骼驱动［13］的虚拟手模型，图8演示了利用传感器值驱动虚手模型按照用户的动作实时运动的效果.

图8 数据手套驱动虚拟手运动的视觉效果

使用搭建的系统，本文完成了2组实验.实验1中选取美国哑语（ASL）［14］的26个字母手语作为基本手势库，让用户A和B两人分别做26个字母的手势，每种手势重复10遍，用这些样本构建手语字母的模板库，并使用该模板库来识别用户C（没有采集他的手势样本）所作出的单词手势（单词手势是一系列的字母顺序组合而成）.该用户一共做了10个单词的动态手势，采样20次，表1是对这10个单词的动作序列的平均识别率.

表1 单词识别率

这些单词涵盖了字母表的所有字母，对这些字母的平均识别率如图9所示.传统的模板匹配和神经网络算法在对样本以外的数据（用户C）进行分类时，由于缺乏构建训练样本手势库的数据，无法对其中的某些手势进行相似性度量，进而不能对其进行准确分类，导致了识别率的不稳定现象.比较而言，SVD算法在构建手势库的过程中，提取训练样本的特征信息，同时消除和特定样本耦合的数据，在极大压缩空间数据的同时，保证了手势库的通用性，从而提高了算法分类的准确性和稳定性.

图9 ASL手语识别率

实验2参照图6的手势分类，重建了一组动作集.在手势库搭建阶段，让用户A在约3 s的时间内依次做如下动作，构成一段连续的动作序列:①食指触碰;②食指和中指同时按压;③拿捏小球（使用食指和拇指）;④拿捏细棒（使用食指和拇指）;⑤握住大球体;⑥抓取粗棒.利用该用户的数据构建如上6种手势的手势库.在识别阶段，实验采集了8位用户（包括构建动作集的用户A）做上述动作序列的原始数据，其中5男3女，身高分布在1.65～1.88 m 之间，手型大小、比例各不相同，以中指指端到手腕测量数据为例，长度值分布在17.1～20.3 cm之间，导致相同手势所对应的传感器值存在较大差异性.图10显示了采集过程中8位用户食指第1关节的数据值变化趋势.

图10 多用户的传感器原始值变化曲线图

实验2利用用户A的数据所构建的动作集来识别这8位用户的动作序列，测得的识别率如图11所示.图11a对比了神经网络和SVD算法的识别率，图11b～图11h显示了多用户情况下，由于神经网络算法的手势集依赖于特定用户，更换用户后没有相应的训练样本，识别算法已失效.SVD算法构建的抽象手势模板则能够屏蔽不用测试者之间的手型差异，在无需重建手势库的情况下，对

图11 采用A的手势集对多用户进行手势识别

多用户保持稳定的识别率.由此得出，本算法所构建的手势库适应于正常人群的手势识别.

上述实验分别测试了2组手势集，本文所提出的识别方法能够将用户的连续动作准确的分割成一系列的动作序列，它利用Hill Climbing思想实时提取动作元，使用预先构建的抽象手势集对不同用户的手势序列进行识别，无需标定，过程简单，识别效果稳定.

4 结论

对数据手套采集的连续数据流进行动态手势识别，是将这些原始值经过数据压缩、特征提取、手势抽象、数据分割，转化成动作元构成的序列，并利用模板库按序匹配，最终输出动态手势的识别结果.

本文所述的方法成功应用于5DT数据手套搭建的手势识别系统，在完全满足实时性的基础上，能够适应多用户的佩戴使用，无需标定，操作方便，提供的识别率准确稳定.

（References）

［1］Agrawal R，Faloutsos C，Swami A.Efficient similarity search in sequence databases［C］//FODO 1993 Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms.London:Springer-Verlag，1993:69－84

［2］Babu S，Widom J.Continuous queries over data streams［J］.ACM SIGMOD Record，2001，30（3）:109－120

［3］Gehrke J，Korn F，Srivastava D.On computing correlated aggregates over continuous data streams［C］//2001 ACM SIGMOD InternationalConference on ManagementofData.NY:Association for Computing Machinery，2001

［4］Mitra S.Gesture recognition:a survey［J］.IEEE Transactions on Systems，Man，and Cybernetics，PartC:Applicationsand Reviews，2007，37（3）:311－324

［5］Emran S M，Ye N.Robustness of canberra metric in computer intrusion detection［C］//Proceedings of the 2001 IEEE Workshop on Information Assurance and Security.NY:United States Military Academy，West Point，2001

［6］Chan Kinpong，Waichee Fu A.Efficient time series matching by wavelets［C］//Proceedings-International Conference on Data Engineering.Los Alamitos，CA:Institute of Electrical and Electronics Engineers Computer Society，1999:126－133

［7］Ju Zhaojie，Liu Honghai，Zhu Xiangyang，et al.Dynamic grasp recognition using time clustering，gaussian mixture models and hidden markov models［C］//Intelligent Robotics and Applications-First International Conference，ICIRA 2008，Proceedings.Heidelberg:Springer-Verlag，2008，23（10）:669－678

［8］Bedregal B C，Costa A C R，Dimuro G P.Fuzzy rule-based hand gesture recognition，artificial intelligence in theory and practice［C］//IFIP International Federation for Information Processing.Boston，MA:World Computer Congress，2006，217:285－294

［9］Vamplew P，Adams A.Recognition and anticipation of hand motions using a recurrent neural network［C］//IEEE International Conference on Neural Networks.Piscataway，NJ:IEEE，1995，6:2904－2907

［10］Zollner R，Rogalla O，Dillmann R，et al.Dynamic grasp recognition within the framework of programming by demonstration［C］//Robot and Human Communication-Proceedings of the IEEE International Workshop.Piscataway，NJ:IEEE，2001:418－423

［11］Frolov V，Deml B，Hannig G.Geture recognition with hidden Markov models to enable multimodal haptic feedback［C］//Proceedings of the 6th international conference on Haptics:Perception，Devices and Scenarios.Berlin，Heidelberg:Springer-Verlag，2008，5024:786－795

［12］Fifth Dimension Technologies Corporation.5DT data glove ultra manual［M/CD］.Irvine，CA:Fifth Dimension Technologies，2004:42－56

［13］Lewis J P，Cordner M，Fong N.Pose space deformations:a unified approach to shape interpolation and skeleton-driven deformation［C］//Proceedings ofthe ACM SIGGRAPH Conference on Computer Graphics.NY:ACM Press，2000:165－172

［14］Costello E.Random House Webster's concise American sign language dictionary［M］.NY:Random House，1999:3－25

Algorithm based on continuous data stream for dynamic gesture recognition

Zheng WeiShen Xukun

（The State Key Laboratory of Virtual Reality Technology and Systems，Beijing University of Aeronautics and Astronautics，Beijing 100191，China）

For the purpose of recognizing the sequence of dynamic gesture made by operator，a method was presented based on continuous data streams sampled from data glove，which used singular value decomposition（SVD）to eliminating noise and extracting features.The characteristics of physiology about joint bend was applied making user-dependent information be culled.A set of gesture template which across different users was set up.The template which gives a complete description of gesture’s feature and generalizes it is therefore user-independent.Based on Hill Climbing heuristic，these streams were separated into action sequences，then a similarity measurement using Euclidian distance was adopted in real time between all segments and templates on a hierarchy search tree built in advance.The sequences segmented by this method are accuracy and suitable for multi users.The effectiveness of this approach for identifying dynamic gesture was verified by two empirical experiments which using 5DT data glove.

continuous data stream;singular value decomposition（SVD）;dynamic gesture recognition

TP 391.4

A

1001-5965（2012）02-0273-07

2010-10-27;< class="emphasis_bold">网络出版时间:

时间:2012-02-21 11:46;

CNKI:11-2625/V.20120221.1146.020

www.cnki.net/kcms/detail/11.2625.V.20120221.1146.020.html

国家高科技研究发展计划重点资助项目（2009AA012103）

郑 韡（1985－），男，安徽铜陵人，硕士生，zhengwei@vrlab.buaa.edu.cn.

（编 辑:文丽芳）