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

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

2、.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 ）英文SummaryAbstract：Approximate string

3、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 huma

4、n 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 sho

5、w thatthe algorithm can improve the recognition rate of most posts by ensuring the realtime performance.英文KeyKey Words：gesture recognition；skeletal nodes；Stringk；MSRC12；Levenshtein distance0引言基于Kinect骨骼節(jié)點的姿勢識別研究方法主要有深度學習和模板匹配兩大類。深度學習類如Lefebvre G等1使用深度學習算法識別人體姿勢，Wang P等2使用神經(jīng)網(wǎng)絡進行姿勢識別。這類算法模型復雜、運算量大，加之其

6、對設備資源配置要求高，所以該方法大都用于游戲等高精準度場景。相對于那些高精準應用，現(xiàn)實生活諸如智能家居、多媒體教學、聾啞人手語等應用場景，對設備資源的配置要求不高，雖然對實時性有一定要求，但對精準度卻允許有一定的誤差，這無疑給模板匹配方法應用到實際生活場景帶來了契機3。Ibaez R等 4提出的近似字符串匹配算法string-k，是模板類匹配算法中實時性較高的一種。相比其它模板類算法如DTW算法5-6，string-k算法通過對運動軌跡編碼縮短識別序列長度，提高了姿勢識別實時性，但是識別率偏低，降低了用戶體驗?，F(xiàn)實場景中由于每個關(guān)節(jié)點自由度不同，因而對姿勢描述貢獻度也不同7。為此，針對動作姿勢

7、識別中骨骼節(jié)點貢獻度權(quán)重及計算量優(yōu)化，本文提出一種基于string-k的姿勢識別優(yōu)化算法，用以進一步提升NUI應用在一些低端設備上的用戶體驗。1基于Kinect骨骼數(shù)據(jù)的姿勢識別模型姿勢識別模型如圖1所示，主要包含訓練和識別過程。為了方便試驗中進行比較，將識別過程記作mstring-kw，k是編碼字符數(shù)目，w表示加權(quán)。從圖1可以看出，姿勢識別過程與訓練過程都需要經(jīng)過以下幾個步驟：預處理：通過參數(shù)選取過程排除了與姿勢識別無關(guān)的參數(shù)，通過權(quán)重分析過程，給出每個參數(shù)合理的權(quán)重，暫存并等待在相似度計算中使用；運動軌跡處理：不同位置或不同身材的參與者在完成相同手勢時，所產(chǎn)生的行為軌跡不同。為排除非關(guān)鍵因

8、素對實驗結(jié)果產(chǎn)生的影響，需要對行為軌跡作處理8，包括中心化、歸一化兩段過程；軌跡編碼：通過軌跡編碼過程將原來一串較長的運動軌跡序列精簡成一小段可進行相似度匹配的字符序列；相似度計算：使用字符串匹配算法，反應運動序列間的相似程度。相比原生string-k算法，該模型添加了步驟，在步驟中改進了相似度識別方法。訓練的主要目的是確定模板和閾值的一個最佳K值，供識別過程使用，以尋求最大的識別率。2行為姿勢識別流程2.1數(shù)據(jù)預處理從運動力學角度看，各個關(guān)節(jié)點有著不同的自由度，對動作姿勢的描述貢獻度上也存在差異。因此，在數(shù)據(jù)選取時，可依據(jù)不同的應用場景，在不影響對動作姿勢完整性表述基礎上，舍去一些動作姿勢表

9、達中不那么明顯的骨骼關(guān)節(jié)點。kinect獲取到的人體骨骼節(jié)點模型如圖2所示9。本文選取對人體行為動作描述貢獻最大的13個關(guān)節(jié)點（左手、左手腕、左肩膀、左膝、左腳、肩膀中心、頭、臀部中心、右手、右手腕、右肩膀、右膝、右腳）。若選取全部節(jié)點，一方面會增大姿勢識別計算量，另一方面會放大誤差。通過中心化和歸一化兩個步驟，使運動軌跡從相似轉(zhuǎn)變到可進行比較，排除人身體構(gòu)造因素對識別結(jié)果的影響10。（1）中心化過程：使用公式（1）計算每個軌跡的中心，計算得到中心點Center，再通過公式（2）對運動軌跡上的點進行中心化處理，得到中心化軌跡C1，C2，Cn，n為運動軌跡上點的個數(shù)。Center=x-，y-，z

10、-=ni=1xi，yi，zin（1）Ci=xi，yi，zi=xi-x-，yi-y-，zi-z-i（1，n）（2）（2）歸一化過程：通過公式（3）和公式（4）對中心化后的運動軌跡中的點進行歸一化處理，得到歸一化后的運動軌跡C1，C2，Cn。s=ni=1xi，yi，zin（3）Ci=xi，yi，zi=xis，yis，zisi（1，n）（4）圖3是預處理前的運動軌跡，可以很直觀看出雖然這4條軌跡很相似，但從數(shù)據(jù)計算層面上相差還是很大的。從圖4可以看出，經(jīng)過中心化和歸一化處理之后，這4段相似的運動軌跡已經(jīng)在視覺上達到了對準。2.2特征值權(quán)重分析姿勢序列使用多骨骼節(jié)點表述，每個骨骼節(jié)點對于姿勢的判別作用

11、不盡相同，需要為每個節(jié)點賦予一個權(quán)值。本文使用骨骼節(jié)點的偏移量衡量它在姿勢構(gòu)成中的貢獻，依據(jù)貢獻大小分配相應的權(quán)值。加權(quán)分兩個步驟：通過公式（5）計算出各個關(guān)節(jié)點的偏移量Ts，m值表示選取的骨骼節(jié)點個數(shù)；通過公式（6）計算s節(jié)點的權(quán)值Ws。Ts=ni=1（xi-xi-1）2+（yi-yi-1）2+（zi-zi-1）2i1，n，s（1，m）（5）Ws=Tsml=1Tl，s（1，m）（6）2.3軌跡序列編碼軌跡序列編碼分為兩個步驟：使用 k-means算法對運動軌跡中的點進行分類；依據(jù)分類結(jié)果將每一類的點進行編碼。K-means以確定的聚類數(shù)k為前提，對一組數(shù)據(jù)集進行聚類。但通常情況下最優(yōu)聚類的k

12、事先無法確定11，需要通過實驗驗證確定，分類步驟如下：在運動軌跡中隨機選取k個點作為質(zhì)心初始值，表示為P1，P2，Pk；將所有運動軌跡中的點指派到最近的質(zhì)心，形成k個簇；使用歐氏距離評估所有點，并重新計算每個簇的質(zhì)心；重復步驟、步驟直到每個運動軌跡中的點所屬分類變化，或者達到最大的迭代次數(shù)。編碼過程就是將軌跡的每個點都編碼成最近質(zhì)心的標識號，如質(zhì)心點P1對應的標號為1。圖5是對兩段不同行為序列的編碼結(jié)果。黑色數(shù)字和點標識了中心點的位置，k=5表示對著兩段序列使用k為5的k-means算法進行分類。數(shù)字1到5標識了從開始到結(jié)束的運動序列上點的屬類變化。對比圖5和圖6可直觀看出相似序列與不相似序列

13、在編碼后的差異。圖5中軌跡1的編碼1325，與軌跡2的編碼324142編碼字符串的差異很大。圖6中軌跡1的編碼256134與軌跡2的編碼25134相比，軌跡2比軌跡1僅僅只差了一個6。軌跡之間的相似度比較由軌跡中多點序列的比較轉(zhuǎn)變成簡單、易區(qū)分的字符串之間的比較。相比直接使用原生的運動軌跡數(shù)據(jù)，軌跡編碼這種方法大大降低了后續(xù)進行相似度識別過程的計算量12。2.4相似度計算本文采用Levenshtein距離完成相似度計算13。Levenshtein距離指兩個字符串之間由一個轉(zhuǎn)換成另一個所需要的最少編輯操作次數(shù)，這些操作包括替換、插入、刪除字符14。Levenshtein計算對象是兩段字符序列，而

14、本文計算的是編碼后的一個個點的集合，不能直接套用Levenshtein距離。結(jié)合2.2節(jié)中的設計的權(quán)重，使用加權(quán)歐式距離描述不同字符的差異程度，改進后的相似度識別算法如下：算法1：相似度識別算法輸入：字符串S，長度為m的字符串序列字符串T，長度為n的字符串序列數(shù)組C，長度為k的中心點集合權(quán)重集合Ww1，w2，ws輸出：兩個字符串序列的編輯距離d變量：大小為mn的二維數(shù)組步驟：Di，0，D0，j，D0，00for i=1|S| dofor j=1|T| douCS（i），vCT（j），d0for s=1|W| dodd+us-vs*Wsend forDi，j d+minDi-1，j，Di，j-1

15、，D0，0end forend forreturn D|s|，|T|算法1返回的是兩個序列的相似度距離，下面舉例說明。在圖6中對單一關(guān)節(jié)點采用k=6編碼，假設這兩段序列為T和S，那么T：2，5，6，1，4，3； S：2，6，1，4，3。觀察表2可以看出，0.945就是最終返回的相似度距離。這個結(jié)果在圖6上有標出，對比之下，圖5的相似度結(jié)果6.288就非常大。通過對多組測試數(shù)據(jù)集訓練，可得到最優(yōu)的模板和相應閾值。對于用字符串表示的行為序列之間的相似度計算，還可進一步利用字符串匹配特性降低計算量。在表2中， （3，3）、（4，4）、（5，5）、（6，6）這幾個單元格數(shù)值都是0945，這些點的連線可

16、看成一個正方形的對角線。對角線對應的T和S的序列片段都是6，1，3，4，相應的字符片段的相似距離為0。算法2是計算算法1在第3步之后可以跳過計算的長度。經(jīng)過算法2的精簡之后，對于圖7中的兩段序列的相似度計算實際上縮減成了T：2，5，6；S2，6這兩段序列的相似度計算。與string-k算法相比，mstring-kw算法在相似度計算過程中，通過對字符串序列去重縮短了計算量，添加了加權(quán)部分。3實驗結(jié)果分析3.1測試數(shù)據(jù)集說明MSRC-12數(shù)據(jù)集包含594個行為序列（.csv文件），719 359幀（約值）數(shù)據(jù)，30種手勢的表現(xiàn)類別。表3給出了數(shù)據(jù)集中的12種動作類。這個姿勢類主要分為隱喻性手勢和標

17、志性手勢兩類。劍橋計算機實驗室招募的數(shù)據(jù)采集人員60%是男性，93%是右撇子，平均年齡31歲，這些人并不清楚采集目的15。3.2實驗環(huán)境本實驗在MATLABR2016a平臺上測試。操作系統(tǒng)Windows 10 ，處理器I5 7300HQ，運行內(nèi)存8GB。3.3實驗結(jié)果分析3.3.1最佳k值選取在軌跡編碼中用到k-means聚類算法，k值是事先給定的，對多種姿勢應用同一個K值可以減少計算量，提高姿勢識別的實時性16。不同K值的識別率也不相同。結(jié)合算法1，發(fā)現(xiàn)K值越大，識別過程的計算量會相應提高，因此在實驗中選取k值的范圍是3-10，10以上不作考慮。實驗測試結(jié)果如圖7所示。從圖7可以看出，k=5

18、時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稍低，雖然加權(quán)需要消耗一定時間，但在相似度計算部分使用改進后的算法縮短了計算量，綜合耗時較少。對比dtw算法可以發(fā)現(xiàn)，ms

19、tring-kw算法識別時間消耗非常少。3.3.3識別率分析對表4中的驗證數(shù)據(jù)集分別做識別率分析實驗，實驗結(jié)果如圖9所示。從圖9可以看出，mstring-kw在G1-G9這9種姿勢識別中比其它兩種方法要好，在G11和G12中與其它兩種方法相差不大。因此，本文提出的mstring-kw算法在大部分情況下能有效提高mstring-k方法的識別率。4結(jié)語日常生活中不同的姿勢使用頻率是不同的，不同姿勢達到最佳識別效果的K值也是不同的。人體骨骼各個關(guān)節(jié)點有著不同的自由度，在不同的應用場景中，對動作姿勢的描述貢獻度存在差異?；谏鲜鲇^點，本文針對低端資源配置的應用場景，提出了一種基于string-k算法的

20、骨骼節(jié)點姿勢識別優(yōu)化算法。實驗結(jié)果和驗證對比表明，該方法在實時性不減的情況下，能夠更高效率地進行姿勢識別。由于運動姿勢的復雜性，骨骼節(jié)點在動作姿勢運動中的權(quán)重與運動的軌跡有直接關(guān)系，今后的工作是在目前方法基礎上，對動態(tài)權(quán)重的設置方法做進一步研究。ReferenceReference：1LEFEBVRE G，CUMIN J.Recognizing human actions based on extreme learning machinesC.International Joint Conference on Computer Vision，Imaging and Computer Graphics Theory and Applications，2016.2WANG P，LI Z，HOU Y，et al.Action recognition based on joint trajectory maps using convolutional neural networksC.ACM on Multimedia Conference，2016：10