王绍雷　　杨鹤标

摘要：近似字符串匹配算法string-k是一种高效的基于模板类的人体姿势识别算法，其实时性能能保障在低端设备（如智能手机、平板等）上完美运行。由于该算法的识别率偏低，难以满足用户体验。为此，提出一种优化的姿势识别算法。算法基本思想是：剔除与姿势相关度低的骨骼节点，依据骨骼节点对识别姿势贡献度的大小分配相应权值，采用改进的Levenshtein距离计算姿势序列降低识别过程的计算量。实验结果表明，在保证实时性条件下，提高了多数姿势的识别率。

关键词：姿势识别；骨骼节点；stringk；MSRC12；Levenshtein距离

DOIDOI：10.11907/rjdk.181221

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）009010105

英文标题Posture Recognition Algorithm Based on Approximate String Matching

--副标题

英文作者WANG ShaoLei， YANG HeBiao

英文作者单位（School of Computer Science and Communication Engineering， Jiangsu University， Zhenjiang 212013， China ）

英文摘要Abstract：Approximate string matching algorithm stringk is an efficient templatebased human pose recognition algorithm.It can smoothly run in low computing capability devices （smartphone，tablets etc.） with realtime performance.But it can not meet users' requirements because of its low recognition rate.Therefore，an optimized human post recognition algorithm is proposed.The basic idea of this algorithm is to remove the skeleton nodes with low relevancy to the pose，and adopt the improved Levenshtein distance calculation Posture sequence to reduce the computational complexity of the recognition process.Experimental results show thatthe algorithm can improve the recognition rate of most posts by ensuring the realtime performance.

英文关键词Key Words：gesture recognition；skeletal nodes；Stringk；MSRC12；Levenshtein distance

0引言

基于Kinect骨骼节点的姿势识别研究方法主要有深度学习和模板匹配两大类。深度学习类如Lefebvre G等[1]使用深度学习算法识别人体姿势，Wang P等[2]使用神经网络进行姿势识别。这类算法模型复杂、运算量大，加之其对设备资源配置要求高，所以该方法大都用于游戏等高精准度场景。相对于那些高精准应用，现实生活诸如智能家居、多媒体教学、聋哑人手语等应用场景，对设备资源的配置要求不高，虽然对实时性有一定要求，但对精准度却允许有一定的误差，这无疑给模板匹配方法应用到实际生活场景带来了契机[3]。

Ibaez R等 [4]提出的近似字符串匹配算法string-k，是模板类匹配算法中实时性较高的一种。相比其它模板类算法如DTW算法[5-6]，string-k算法通过对运动轨迹编码缩短识别序列长度，提高了姿势识别实时性，但是识别率偏低，降低了用户体验。现实场景中由于每个关节点自由度不同，因而对姿势描述贡献度也不同[7]。为此，针对动作姿势识别中骨骼节点贡献度权重及计算量优化，本文提出一种基于string-k的姿势识别优化算法，用以进一步提升NUI应用在一些低端设备上的用户体验。

1基于Kinect骨骼数据的姿势识别模型

姿势识别模型如图1所示，主要包含训练和识别过程。为了方便试验中进行比较，将识别过程记作mstring-kw，k是编码字符数目，w表示加权。

从图1可以看出，姿势识别过程与训练过程都需要经过以下几个步骤：①预处理：通过参数选取过程排除了与姿势识别无关的参数，通过权重分析过程，给出每个参数合理的权重，暂存并等待在相似度计算中使用；②运动轨迹处理：不同位置或不同身材的参与者在完成相同手势时，所产生的行为轨迹不同。为排除非关键因素对实验结果产生的影响，需要对行为轨迹作处理[8]，包括中心化、归一化两段过程；③轨迹编码：通过轨迹编码过程将原来一串较长的运动轨迹序列精简成一小段可进行相似度匹配的字符序列；④相似度计算：使用字符串匹配算法，反应运动序列间的相似程度。相比原生string-k算法，该模型添加了步骤①，在步骤④中改进了相似度识别方法。

训练的主要目的是确定模板和阈值的一个最佳K值，供识别过程使用，以寻求最大的识别率。

2行为姿势识别流程

2.1数据预处理

从运动力学角度看，各个关节点有着不同的自由度，对动作姿势的描述贡献度上也存在差异。因此，在数据选取时，可依据不同的应用场景，在不影响对动作姿势完整性表述基础上，舍去一些动作姿势表达中不那么明显的骨骼关节点。kinect获取到的人体骨骼节点模型如图2所示[9]。本文选取对人体行为动作描述贡献最大的13个关节点（左手、左手腕、左肩膀、左膝、左脚、肩膀中心、頭、臀部中心、右手、右手腕、右肩膀、右膝、右脚）。若选取全部节点，一方面会增大姿势识别计算量，另一方面会放大误差。

通过中心化和归一化两个步骤，使运动轨迹从相似转变到可进行比较，排除人身体构造因素对识别结果的影响[10]。（1）中心化过程：使用公式（1）计算每个轨迹的中心，计算得到中心点Center，再通过公式（2）对运动轨迹上的点进行中心化处理，得到中心化轨迹{C1'，C2'，…，Cn'}，n为运动轨迹上点的个数。

Center=x-，y-，z-=∑ni=1xi，yi，zin（1）

C′i=x′i，y′i，z′i=xi-x-，yi-y-，zi-z-i∈（1，n）（2）

（2）归一化过程：通过公式（3）和公式（4）对中心化后的运动轨迹中的点进行归一化处理，得到归一化后的运动轨迹{C1″，C2″，…，Cn"}。

s=∑ni=1x′i，y′i，z′in（3）

C″i=x″i，y″i，z″i=x′is，y′is，z′isi∈（1，n）（4）

图3是预处理前的运动轨迹，可以很直观看出虽然这4条轨迹很相似，但从数据计算层面上相差还是很大的。

从图4可以看出，经过中心化和归一化处理之后，这4段相似的运动轨迹已经在视觉上达到了对准。

2.2特征值权重分析

姿势序列使用多骨骼节点表述，每个骨骼节点对于姿势的判别作用不尽相同，需要为每个节点赋予一个权值。本文使用骨骼节点的偏移量衡量它在姿势构成中的贡献，依据贡献大小分配相应的权值。

加权分两个步骤：①通过公式（5）计算出各个关节点的偏移量Ts，m值表示选取的骨骼节点个数；②通过公式（6）计算s节点的权值Ws。

Ts=∑ni=1（xi-xi-1）2+（yi-yi-1）2+（zi-zi-1）2

i∈1，n，s∈（1，m）（5）

Ws=Ts∑ml=1Tl，s∈（1，m）（6）

2.3轨迹序列编码

轨迹序列编码分为两个步骤：①使用 k-means算法对运动轨迹中的点进行分类；②依据分类结果将每一类的点进行编码。

K-means以确定的聚类数k为前提，对一组数据集进行聚类。但通常情况下最优聚类的k事先无法确定[11]，需要通过实验验证确定，分类步驟如下：①在运动轨迹中随机选取k个点作为质心初始值，表示为{P1，P2，…，Pk}；②将所有运动轨迹中的点指派到最近的质心，形成k个簇；③使用欧氏距离评估所有点，并重新计算每个簇的质心；④重复步骤②、步骤③直到每个运动轨迹中的点所属分类变化，或者达到最大的迭代次数。

编码过程就是将轨迹的每个点都编码成最近质心的标识号，如质心点P1对应的标号为1。

图5是对两段不同行为序列的编码结果。黑色数字和点标识了中心点的位置，k=5表示对着两段序列使用k为5的k-means算法进行分类。数字1到5标识了从开始到结束的运动序列上点的属类变化。

对比图5和图6可直观看出相似序列与不相似序列在编码后的差异。图5中轨迹1的编码1325，与轨迹2的编码324142编码字符串的差异很大。图6中轨迹1的编码256134与轨迹2的编码25134相比，轨迹2比轨迹1仅仅只差了一个6。轨迹之间的相似度比较由轨迹中多点序列的比较转变成简单、易区分的字符串之间的比较。相比直接使用原生的运动轨迹数据，轨迹编码这种方法大大降低了后续进行相似度识别过程的计算量[12]。

2.4相似度计算

本文采用Levenshtein距离完成相似度计算[13]。Levenshtein距离指两个字符串之间由一个转换成另一个所需要的最少编辑操作次数，这些操作包括替换、插入、删除字符[14]。Levenshtein计算对象是两段字符序列，而本文计算的是编码后的一个个点的集合，不能直接套用Levenshtein距离。结合2.2节中的设计的权重，使用加权欧式距离描述不同字符的差异程度，改进后的相似度识别算法如下：

算法1：相似度识别算法

输入：

字符串S，长度为m的字符串序列

字符串T，长度为n的字符串序列

数组C，长度为k的中心点集合

权重集合W{w1，w2，…，ws}

输出：两个字符串序列的编辑距离d

变量：大小为m﹡n的二维数组

步骤：

Di，0←∞，D0，j←∞，D0，0←0

for i=1→|S| do

for j=1→|T| do

u←CS（i），v←CT（j），d←0

for s=1→|W| do

d←d+‖us-vs‖*Ws

end for

Di，j ←d+min{Di-1，j，Di，j-1，D0，0}

end for

end for

return D|s|，|T|

算法1返回的是两个序列的相似度距离，下面举例说明。在图6中对单一关节点采用k=6编码，假设这两段序列为T和S，那么T：{2，5，6，1，4，3}； S：{2，6，1，4，3}。

观察表2可以看出，0.945就是最终返回的相似度距离。这个结果在图6上有标出，对比之下，图5的相似度结果6.288就非常大。通过对多组测试数据集训练，可得到最优的模板和相应阈值。

对于用字符串表示的行为序列之间的相似度计算，还可进一步利用字符串匹配特性降低计算量。在表2中， （3，3）、（4，4）、（5，5）、（6，6）这几个单元格数值都是0945，这些点的连线可看成一个正方形的对角线。对角线对应的T和S的序列片段都是{6，1，3，4}，相应的字符片段的相似距离为0。算法2是计算算法1在第3步之后可以跳过计算的长度。

经过算法2的精简之后，对于图7中的两段序列的相似度计算实际上缩减成了T：{2，5，6}；S{2，6}这两段序列的相似度计算。

与string-k算法相比，mstring-kw算法在相似度计算过程中，通过对字符串序列去重缩短了计算量，添加了加权部分。

3实验结果分析

3.1测试数据集说明

MSRC-12数据集包含594个行为序列（.csv文件），719 359帧（约值）数据，30种手势的表现类别。表3给出了数据集中的12种动作类。这个姿势类主要分为隐喻性手势和标志性手势两类。

剑桥计算机实验室招募的数据采集人员60%是男性，93%是右撇子，平均年龄31岁，这些人并不清楚采集目的[15]。

3.2实验环境

本实验在MATLABR2016a平台上测试。操作系统Windows 10 ，处理器I5 7300HQ，运行内存8GB。

3.3实验结果分析

3.3.1最佳k值选取

在轨迹编码中用到k-means聚类算法，k值是事先给定的，对多种姿势应用同一个K值可以减少计算量，提高姿势识别的实时性[16]。不同K值的识别率也不相同。结合算法1，发现K值越大，识别过程的计算量会相应提高，因此在实验中选取k值的范围是3-10，10以上不作考虑。实验测试结果如图7所示。

从图7可以看出，k=5时mstring-kw可达到最高的平均识别率，记作mstring-5w。

3.3.2实时性分析

实验使用string-6（Ibaez R等[4]实验中确定k=6是达到实时性与识别率的最佳点）、mstring-5w与 dtw算法分别对表4中的测试数据集模拟识别过程，得出识别过程中时间消耗对比。时间消耗主要包含3个部分：①测试集数据文件读取时间；②数据解析时间；③识别时间。由于3种算法都是相同的测试数据集，因此前两部分是固定的，差别在第三部分。

从图8可以看出，本文方法比单纯的string-6稍低，虽然加权需要消耗一定时间，但在相似度计算部分使用改进后的算法缩短了计算量，综合耗时较少。对比dtw算法可以发现，mstring-kw算法识别时间消耗非常少。

3.3.3识别率分析

对表4中的验证数据集分别做识别率分析实验，实验结果如图9所示。

从图9可以看出，mstring-kw在G1-G9这9种姿势识别中比其它两种方法要好，在G11和G12中与其它两种方法相差不大。因此，本文提出的mstring-kw算法在大部分情况下能有效提高mstring-k方法的识别率。

4结语

日常生活中不同的姿势使用频率是不同的，不同姿势达到最佳识别效果的K值也是不同的。人体骨骼各个关节点有着不同的自由度，在不同的应用场景中，对动作姿势的描述贡献度存在差异。基于上述观点，本文针对低端资源配置的应用场景，提出了一种基于string-k算法的骨骼节点姿势识别优化算法。实验结果和验证对比表明，该方法在实时性不减的情况下，能够更高效率地进行姿势识别。由于运动姿势的复杂性，骨骼节点在动作姿势运动中的权重与运动的轨迹有直接关系，今后的工作是在目前方法基础上，對动态权重的设置方法做进一步研究。

参考文献参考文献：

[1]LEFEBVRE G，CUMIN J.Recognizing human actions based on extreme learning machines[C].International Joint Conference on Computer Vision，Imaging and Computer Graphics Theory and Applications，2016.

[2]WANG P，LI Z，HOU Y，et al.Action recognition based on joint trajectory maps using convolutional neural networks[C].ACM on Multimedia Conference，2016：102106.

[3]陈静.基于Kinect的手势识别技术及其在教学中的应用[D].上海：上海交通大学，2013..

[4]IBANEZ R，SORIA L，TEYSEYRE A，et al.Approximate string matching：a lightweight approach to recognize gestures with Kinect[J].Pattern Recognition，2016（62）：7386.

[5]薛俊杰，陈健美.基于加权DTW手势识别方法的研究与实现[J].信息技术，2015（11）：125129.

[6]BOEHM J.Natural user interface sensors for human body measurement[J].International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences，2012（B3）：3940.

[7]SALVADOR S，CHAN P.Toward accurate dynamic time warping in linear time and space[J].Intelligent Data Analysis，2007，11（5）：561580.

[8]IBAEZ R，LVARO SORIA，TEYSEYRE A，etal.Easy gesture recognition for Kinect[J].Advances in Engineering Software，2014（76）：171180.