王紹雷　　楊鶴標

摘要：近似字符串匹配算法string-k是一種高效的基于模板類的人體姿勢識別算法，其實時性能能保障在低端設備（如智能手機、平板等）上完美運行。由于該算法的識別率偏低，難以滿足用戶體驗。為此，提出一種優(yōu)化的姿勢識別算法。算法基本思想是：剔除與姿勢相關度低的骨骼節(jié)點，依據(jù)骨骼節(jié)點對識別姿勢貢獻度的大小分配相應權值，采用改進的Levenshtein距離計算姿勢序列降低識別過程的計算量。實驗結果表明，在保證實時性條件下，提高了多數(shù)姿勢的識別率。

關鍵詞：姿勢識別；骨骼節(jié)點；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骨骼節(jié)點的姿勢識別研究方法主要有深度學習和模板匹配兩大類。深度學習類如Lefebvre G等[1]使用深度學習算法識別人體姿勢，Wang P等[2]使用神經(jīng)網(wǎng)絡進行姿勢識別。這類算法模型復雜、運算量大，加之其對設備資源配置要求高，所以該方法大都用于游戲等高精準度場景。相對于那些高精準應用，現(xiàn)實生活諸如智能家居、多媒體教學、聾啞人手語等應用場景，對設備資源的配置要求不高，雖然對實時性有一定要求，但對精準度卻允許有一定的誤差，這無疑給模板匹配方法應用到實際生活場景帶來了契機[3]。

Ibaez R等 [4]提出的近似字符串匹配算法string-k，是模板類匹配算法中實時性較高的一種。相比其它模板類算法如DTW算法[5-6]，string-k算法通過對運動軌跡編碼縮短識別序列長度，提高了姿勢識別實時性，但是識別率偏低，降低了用戶體驗?，F(xiàn)實場景中由于每個關節(jié)點自由度不同，因而對姿勢描述貢獻度也不同[7]。為此，針對動作姿勢識別中骨骼節(jié)點貢獻度權重及計算量優(yōu)化，本文提出一種基于string-k的姿勢識別優(yōu)化算法，用以進一步提升NUI應用在一些低端設備上的用戶體驗。

1基于Kinect骨骼數(shù)據(jù)的姿勢識別模型

姿勢識別模型如圖1所示，主要包含訓練和識別過程。為了方便試驗中進行比較，將識別過程記作mstring-kw，k是編碼字符數(shù)目，w表示加權。

從圖1可以看出，姿勢識別過程與訓練過程都需要經(jīng)過以下幾個步驟：①預處理：通過參數(shù)選取過程排除了與姿勢識別無關的參數(shù)，通過權重分析過程，給出每個參數(shù)合理的權重，暫存并等待在相似度計算中使用；②運動軌跡處理：不同位置或不同身材的參與者在完成相同手勢時，所產(chǎn)生的行為軌跡不同。為排除非關鍵因素對實驗結果產(chǎn)生的影響，需要對行為軌跡作處理[8]，包括中心化、歸一化兩段過程；③軌跡編碼：通過軌跡編碼過程將原來一串較長的運動軌跡序列精簡成一小段可進行相似度匹配的字符序列；④相似度計算：使用字符串匹配算法，反應運動序列間的相似程度。相比原生string-k算法，該模型添加了步驟①，在步驟④中改進了相似度識別方法。

訓練的主要目的是確定模板和閾值的一個最佳K值，供識別過程使用，以尋求最大的識別率。

2行為姿勢識別流程

2.1數(shù)據(jù)預處理

從運動力學角度看，各個關節(jié)點有著不同的自由度，對動作姿勢的描述貢獻度上也存在差異。因此，在數(shù)據(jù)選取時，可依據(jù)不同的應用場景，在不影響對動作姿勢完整性表述基礎上，舍去一些動作姿勢表達中不那么明顯的骨骼關節(jié)點。kinect獲取到的人體骨骼節(jié)點模型如圖2所示[9]。本文選取對人體行為動作描述貢獻最大的13個關節(jié)點（左手、左手腕、左肩膀、左膝、左腳、肩膀中心、頭、臀部中心、右手、右手腕、右肩膀、右膝、右腳）。若選取全部節(jié)點，一方面會增大姿勢識別計算量，另一方面會放大誤差。

通過中心化和歸一化兩個步驟，使運動軌跡從相似轉變到可進行比較，排除人身體構造因素對識別結果的影響[10]。（1）中心化過程：使用公式（1）計算每個軌跡的中心，計算得到中心點Center，再通過公式（2）對運動軌跡上的點進行中心化處理，得到中心化軌跡{C1'，C2'，…，Cn'}，n為運動軌跡上點的個數(shù)。

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條軌跡很相似，但從數(shù)據(jù)計算層面上相差還是很大的。

從圖4可以看出，經(jīng)過中心化和歸一化處理之后，這4段相似的運動軌跡已經(jīng)在視覺上達到了對準。

2.2特征值權重分析

姿勢序列使用多骨骼節(jié)點表述，每個骨骼節(jié)點對于姿勢的判別作用不盡相同，需要為每個節(jié)點賦予一個權值。本文使用骨骼節(jié)點的偏移量衡量它在姿勢構成中的貢獻，依據(jù)貢獻大小分配相應的權值。

加權分兩個步驟：①通過公式（5）計算出各個關節(jié)點的偏移量Ts，m值表示選取的骨骼節(jié)點個數(shù)；②通過公式（6）計算s節(jié)點的權值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算法對運動軌跡中的點進行分類；②依據(jù)分類結果將每一類的點進行編碼。

K-means以確定的聚類數(shù)k為前提，對一組數(shù)據(jù)集進行聚類。但通常情況下最優(yōu)聚類的k事先無法確定[11]，需要通過實驗驗證確定，分類步驟如下：①在運動軌跡中隨機選取k個點作為質心初始值，表示為{P1，P2，…，Pk}；②將所有運動軌跡中的點指派到最近的質心，形成k個簇；③使用歐氏距離評估所有點，并重新計算每個簇的質心；④重復步驟②、步驟③直到每個運動軌跡中的點所屬分類變化，或者達到最大的迭代次數(shù)。

編碼過程就是將軌跡的每個點都編碼成最近質心的標識號，如質心點P1對應的標號為1。

圖5是對兩段不同行為序列的編碼結果。黑色數(shù)字和點標識了中心點的位置，k=5表示對著兩段序列使用k為5的k-means算法進行分類。數(shù)字1到5標識了從開始到結束的運動序列上點的屬類變化。

對比圖5和圖6可直觀看出相似序列與不相似序列在編碼后的差異。圖5中軌跡1的編碼1325，與軌跡2的編碼324142編碼字符串的差異很大。圖6中軌跡1的編碼256134與軌跡2的編碼25134相比，軌跡2比軌跡1僅僅只差了一個6。軌跡之間的相似度比較由軌跡中多點序列的比較轉變成簡單、易區(qū)分的字符串之間的比較。相比直接使用原生的運動軌跡數(shù)據(jù)，軌跡編碼這種方法大大降低了后續(xù)進行相似度識別過程的計算量[12]。

2.4相似度計算

本文采用Levenshtein距離完成相似度計算[13]。Levenshtein距離指兩個字符串之間由一個轉換成另一個所需要的最少編輯操作次數(shù)，這些操作包括替換、插入、刪除字符[14]。Levenshtein計算對象是兩段字符序列，而本文計算的是編碼后的一個個點的集合，不能直接套用Levenshtein距離。結合2.2節(jié)中的設計的權重，使用加權歐式距離描述不同字符的差異程度，改進后的相似度識別算法如下：

算法1：相似度識別算法

輸入：

字符串S，長度為m的字符串序列

字符串T，長度為n的字符串序列

數(shù)組C，長度為k的中心點集合

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

輸出：兩個字符串序列的編輯距離d

變量：大小為m﹡n的二維數(shù)組

步驟：

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中對單一關節(jié)點采用k=6編碼，假設這兩段序列為T和S，那么T：{2，5，6，1，4，3}； S：{2，6，1，4，3}。

觀察表2可以看出，0.945就是最終返回的相似度距離。這個結果在圖6上有標出，對比之下，圖5的相似度結果6.288就非常大。通過對多組測試數(shù)據(jù)集訓練，可得到最優(yōu)的模板和相應閾值。

對于用字符串表示的行為序列之間的相似度計算，還可進一步利用字符串匹配特性降低計算量。在表2中， （3，3）、（4，4）、（5，5）、（6，6）這幾個單元格數(shù)值都是0945，這些點的連線可看成一個正方形的對角線。對角線對應的T和S的序列片段都是{6，1，3，4}，相應的字符片段的相似距離為0。算法2是計算算法1在第3步之后可以跳過計算的長度。

經(jīng)過算法2的精簡之后，對于圖7中的兩段序列的相似度計算實際上縮減成了T：{2，5，6}；S{2，6}這兩段序列的相似度計算。

與string-k算法相比，mstring-kw算法在相似度計算過程中，通過對字符串序列去重縮短了計算量，添加了加權部分。

3實驗結果分析

3.1測試數(shù)據(jù)集說明

MSRC-12數(shù)據(jù)集包含594個行為序列（.csv文件），719 359幀（約值）數(shù)據(jù)，30種手勢的表現(xiàn)類別。表3給出了數(shù)據(jù)集中的12種動作類。這個姿勢類主要分為隱喻性手勢和標志性手勢兩類。

劍橋計算機實驗室招募的數(shù)據(jù)采集人員60%是男性，93%是右撇子，平均年齡31歲，這些人并不清楚采集目的[15]。

3.2實驗環(huán)境

本實驗在MATLABR2016a平臺上測試。操作系統(tǒng)Windows 10 ，處理器I5 7300HQ，運行內存8GB。

3.3實驗結果分析

3.3.1最佳k值選取

在軌跡編碼中用到k-means聚類算法，k值是事先給定的，對多種姿勢應用同一個K值可以減少計算量，提高姿勢識別的實時性[16]。不同K值的識別率也不相同。結合算法1，發(fā)現(xiàn)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中的測試數(shù)據(jù)集模擬識別過程，得出識別過程中時間消耗對比。時間消耗主要包含3個部分：①測試集數(shù)據(jù)文件讀取時間；②數(shù)據(jù)解析時間；③識別時間。由于3種算法都是相同的測試數(shù)據(jù)集，因此前兩部分是固定的，差別在第三部分。

從圖8可以看出，本文方法比單純的string-6稍低，雖然加權需要消耗一定時間，但在相似度計算部分使用改進后的算法縮短了計算量，綜合耗時較少。對比dtw算法可以發(fā)現(xiàn)，mstring-kw算法識別時間消耗非常少。

3.3.3識別率分析

對表4中的驗證數(shù)據(jù)集分別做識別率分析實驗，實驗結果如圖9所示。

從圖9可以看出，mstring-kw在G1-G9這9種姿勢識別中比其它兩種方法要好，在G11和G12中與其它兩種方法相差不大。因此，本文提出的mstring-kw算法在大部分情況下能有效提高mstring-k方法的識別率。

4結語

日常生活中不同的姿勢使用頻率是不同的，不同姿勢達到最佳識別效果的K值也是不同的。人體骨骼各個關節(jié)點有著不同的自由度，在不同的應用場景中，對動作姿勢的描述貢獻度存在差異?；谏鲜鲇^點，本文針對低端資源配置的應用場景，提出了一種基于string-k算法的骨骼節(jié)點姿勢識別優(yōu)化算法。實驗結果和驗證對比表明，該方法在實時性不減的情況下，能夠更高效率地進行姿勢識別。由于運動姿勢的復雜性，骨骼節(jié)點在動作姿勢運動中的權重與運動的軌跡有直接關系，今后的工作是在目前方法基礎上，對動態(tài)權重的設置方法做進一步研究。

參考文獻參考文獻：

[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手勢識別方法的研究與實現(xiàn)[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.