基于近似字符串匹配的姿勢識(shí)別算法

王紹雷　　楊鶴標(biāo)

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

關(guān)鍵詞：姿勢識(shí)別；骨骼節(jié)點(diǎn)；stringk；MSRC12；Levenshtein距離

DOIDOI：10.11907/rjdk.181221

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2018）009010105

英文標(biāo)題Posture Recognition Algorithm Based on Approximate String Matching

--副標(biāo)題

英文作者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.

英文關(guān)鍵詞Key Words：gesture recognition；skeletal nodes；Stringk；MSRC12；Levenshtein distance

0引言

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

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

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

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

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

訓(xùn)練的主要目的是確定模板和閾值的一個(gè)最佳K值，供識(shí)別過程使用，以尋求最大的識(shí)別率。

2行為姿勢識(shí)別流程

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

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

通過中心化和歸一化兩個(gè)步驟，使運(yùn)動(dòng)軌跡從相似轉(zhuǎn)變到可進(jìn)行比較，排除人身體構(gòu)造因素對(duì)識(shí)別結(jié)果的影響[10]。（1）中心化過程：使用公式（1）計(jì)算每個(gè)軌跡的中心，計(jì)算得到中心點(diǎn)Center，再通過公式（2）對(duì)運(yùn)動(dòng)軌跡上的點(diǎn)進(jìn)行中心化處理，得到中心化軌跡{C1'，C2'，…，Cn'}，n為運(yùn)動(dòng)軌跡上點(diǎn)的個(gè)數(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）對(duì)中心化后的運(yùn)動(dòng)軌跡中的點(diǎn)進(jìn)行歸一化處理，得到歸一化后的運(yùn)動(dòng)軌跡{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是預(yù)處理前的運(yùn)動(dòng)軌跡，可以很直觀看出雖然這4條軌跡很相似，但從數(shù)據(jù)計(jì)算層面上相差還是很大的。

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

2.2特征值權(quán)重分析

姿勢序列使用多骨骼節(jié)點(diǎn)表述，每個(gè)骨骼節(jié)點(diǎn)對(duì)于姿勢的判別作用不盡相同，需要為每個(gè)節(jié)點(diǎn)賦予一個(gè)權(quán)值。本文使用骨骼節(jié)點(diǎn)的偏移量衡量它在姿勢構(gòu)成中的貢獻(xiàn)，依據(jù)貢獻(xiàn)大小分配相應(yīng)的權(quán)值。

加權(quán)分兩個(gè)步驟：①通過公式（5）計(jì)算出各個(gè)關(guān)節(jié)點(diǎn)的偏移量Ts，m值表示選取的骨骼節(jié)點(diǎn)個(gè)數(shù)；②通過公式（6）計(jì)算s節(jié)點(diǎn)的權(quán)值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軌跡序列編碼

軌跡序列編碼分為兩個(gè)步驟：①使用 k-means算法對(duì)運(yùn)動(dòng)軌跡中的點(diǎn)進(jìn)行分類；②依據(jù)分類結(jié)果將每一類的點(diǎn)進(jìn)行編碼。

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

編碼過程就是將軌跡的每個(gè)點(diǎn)都編碼成最近質(zhì)心的標(biāo)識(shí)號(hào)，如質(zhì)心點(diǎn)P1對(duì)應(yīng)的標(biāo)號(hào)為1。

圖5是對(duì)兩段不同行為序列的編碼結(jié)果。黑色數(shù)字和點(diǎn)標(biāo)識(shí)了中心點(diǎn)的位置，k=5表示對(duì)著兩段序列使用k為5的k-means算法進(jìn)行分類。數(shù)字1到5標(biāo)識(shí)了從開始到結(jié)束的運(yùn)動(dòng)序列上點(diǎn)的屬類變化。

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

2.4相似度計(jì)算

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

算法1：相似度識(shí)別算法

輸入：

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

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

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

權(quán)重集合W{w1，w2，…，ws}

輸出：兩個(gè)字符串序列的編輯距離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返回的是兩個(gè)序列的相似度距離，下面舉例說明。在圖6中對(duì)單一關(guān)節(jié)點(diǎn)采用k=6編碼，假設(shè)這兩段序列為T和S，那么T：{2，5，6，1，4，3}； S：{2，6，1，4，3}。

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

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

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

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

3實(shí)驗(yàn)結(jié)果分析

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

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

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

3.2實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)在MATLABR2016a平臺(tái)上測試。操作系統(tǒng)Windows 10 ，處理器I5 7300HQ，運(yùn)行內(nèi)存8GB。

3.3實(shí)驗(yàn)結(jié)果分析

3.3.1最佳k值選取

在軌跡編碼中用到k-means聚類算法，k值是事先給定的，對(duì)多種姿勢應(yīng)用同一個(gè)K值可以減少計(jì)算量，提高姿勢識(shí)別的實(shí)時(shí)性[16]。不同K值的識(shí)別率也不相同。結(jié)合算法1，發(fā)現(xiàn)K值越大，識(shí)別過程的計(jì)算量會(huì)相應(yīng)提高，因此在實(shí)驗(yàn)中選取k值的范圍是3-10，10以上不作考慮。實(shí)驗(yàn)測試結(jié)果如圖7所示。

從圖7可以看出，k=5時(shí)mstring-kw可達(dá)到最高的平均識(shí)別率，記作mstring-5w。

3.3.2實(shí)時(shí)性分析

實(shí)驗(yàn)使用string-6（Ibaez R等[4]實(shí)驗(yàn)中確定k=6是達(dá)到實(shí)時(shí)性與識(shí)別率的最佳點(diǎn)）、mstring-5w與 dtw算法分別對(duì)表4中的測試數(shù)據(jù)集模擬識(shí)別過程，得出識(shí)別過程中時(shí)間消耗對(duì)比。時(shí)間消耗主要包含3個(gè)部分：①測試集數(shù)據(jù)文件讀取時(shí)間；②數(shù)據(jù)解析時(shí)間；③識(shí)別時(shí)間。由于3種算法都是相同的測試數(shù)據(jù)集，因此前兩部分是固定的，差別在第三部分。

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

3.3.3識(shí)別率分析

對(duì)表4中的驗(yàn)證數(shù)據(jù)集分別做識(shí)別率分析實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖9所示。

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

4結(jié)語

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

參考文獻(xiàn)參考文獻(xiàn)：

[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的手勢識(shí)別技術(shù)及其在教學(xué)中的應(yīng)用[D].上海：上海交通大學(xué)，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]薛俊杰，陳健美.基于加權(quán)DTW手勢識(shí)別方法的研究與實(shí)現(xiàn)[J].信息技術(shù)，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.