基于信息熵特征選擇及聚類的人體運(yùn)動捕捉數(shù)據(jù)分割方法

1、基于信息熵特征選擇及聚類的人體運(yùn)動捕捉數(shù)據(jù)分割方法摘要:人體運(yùn)動序列的分割是指將復(fù)雜的長運(yùn)動捕捉數(shù)據(jù)進(jìn)行分割，從而得到若干個具有獨(dú)立語義的片段，分別表示不同的運(yùn)動類型，以方便對數(shù)據(jù)進(jìn)行存儲、檢索、編輯與合成等工作。為了實(shí)現(xiàn)對人體運(yùn)動數(shù)據(jù)的分割，本文提出了一種基于信息熵特征選擇和k均值聚類的人體運(yùn)動捕捉數(shù)據(jù)分割方法，該方法首先通過計算每一維度的信息熵，提取信息量較大的維度，使用度量MDS將提取出來的數(shù)據(jù)映射到低維空間，然后通過k均值聚類算法對低維數(shù)據(jù)進(jìn)行分類得到初始分割點(diǎn)集，最后進(jìn)行相似性檢測確定最終精確分割點(diǎn)，從而得到了若干不同類型的運(yùn)動片段。實(shí)驗(yàn)表明該方法可以實(shí)現(xiàn)對運(yùn)動捕捉序列的分割，且與其

2、它算法相比，準(zhǔn)確率有一定的改進(jìn)。關(guān)鍵詞：信息熵，運(yùn)動捕捉數(shù)據(jù)分割，k均值聚類，歐式距離1 引言人體運(yùn)動分割是指在運(yùn)動捕捉數(shù)據(jù)中找出相應(yīng)的時間幀，將其兩側(cè)所屬不同運(yùn)動類型的數(shù)據(jù)分割開來，便于數(shù)據(jù)的存儲以及在動畫制作過程中對其進(jìn)行重用。近年來，國內(nèi)外很多科研人員對人體運(yùn)動數(shù)據(jù)的分割方法進(jìn)行了深入地探索和研究，取得了豐碩的成果，主要集中于以下幾個方面：(1)基于特征的人體運(yùn)動捕捉數(shù)據(jù)分割方法肖俊等人9，10提取肢體骨骼與中心骨骼之間的夾角作為運(yùn)動捕捉數(shù)據(jù)的幾何特征，以啟發(fā)式的方式來檢測運(yùn)動的分割點(diǎn)，然后通過人工交互實(shí)現(xiàn)對運(yùn)動數(shù)據(jù)的精確分割，然而這種方法相對耗時，涉及過多的人工干預(yù)，而且由于特征是多維

3、的，降低了分割的精度。Peng3提出了將人體的根關(guān)節(jié)與肢體其他關(guān)節(jié)的距離作為中心距離特征，使用PCA方法對中心距離特征進(jìn)行降維，從而得到一條特征曲線，然后通過低通濾波查找局部極值點(diǎn)，最終實(shí)現(xiàn)對運(yùn)動數(shù)據(jù)的分割。石祥濱等人2針對關(guān)節(jié)角度或關(guān)節(jié)點(diǎn)中心距離作為人體描述姿態(tài)的特征所存在的局限性，提出了一種基于關(guān)節(jié)聯(lián)動特征的運(yùn)動捕捉數(shù)據(jù)分割方法。（2）基于聚類的人體運(yùn)動捕捉數(shù)據(jù)分割方法很多學(xué)者將聚類方法成功地應(yīng)用到了對運(yùn)動捕捉數(shù)據(jù)的處理上，郝高峰等人1針對人體運(yùn)動捕捉數(shù)據(jù)的缺失問題，提出了一種結(jié)合模糊聚類和投影近似點(diǎn)算法的缺失數(shù)據(jù)數(shù)據(jù)重構(gòu)恢復(fù)方法。劉曉平等人3針對現(xiàn)有方法不能在人工交互條件下實(shí)現(xiàn)對任意平地

4、運(yùn)動數(shù)據(jù)的足跡自動檢測，提出了一種基于譜聚類的足跡自動檢測方法。（3）其他人體運(yùn)動捕捉數(shù)據(jù)分割方法Lv N等人11 提出了一個通用的遺傳算法框架用于人體運(yùn)動捕獲數(shù)據(jù)分割。Schulz等人4提出了一種自動分割算法，該算法使用過零分割技術(shù)，利用不同的動作其過零率也不同，定義了過零率閾值，進(jìn)一步完成提取不同運(yùn)動。Takashi AOKI等人5使用慣性傳感器來對人體運(yùn)動進(jìn)行時序分割。Samer Salamah等人6以分類樹的形式，其中，最高級別的動作捕捉數(shù)據(jù)分為動態(tài)和靜態(tài)片段，而最低級別的運(yùn)動捕捉數(shù)據(jù)使用功能單一的身體部位來識別廣泛的人類動作。Lin J.F.S 等人7 在速度峰值和零速度交叉點(diǎn)分割運(yùn)

5、動流，然后使用HMM對獲得的片段進(jìn)行提煉和分類。Carlos Orrite, Mario Rodriguez等人8提出了一種基于可觀測的馬爾科夫（OMMS）的方法來構(gòu)造動作狀態(tài)和中間狀態(tài)的網(wǎng)絡(luò)模型，在此模型中，通過在每一特定時間的狀態(tài)進(jìn)行解碼來識別一個復(fù)雜的未知序列，在此基礎(chǔ)上列入新的中間狀態(tài)來模擬連續(xù)動作之間的轉(zhuǎn)換，以此展開對長而復(fù)雜的運(yùn)動序列的自動分割。Yan Wang等人13提出一種基于PCA的GMM方法能夠有效探索去除每一個運(yùn)動片段的運(yùn)動過渡部分，從而產(chǎn)生干凈的運(yùn)動分割片段，有利于自然動作的生成。綜上所述，尋找不同動作之間的分割特征是對人體運(yùn)動序列分割的關(guān)鍵。從以上分析中不難看出在分割

6、算法中廣泛應(yīng)用到了降維技術(shù)。人體運(yùn)動捕捉數(shù)據(jù)是一種多維度的數(shù)據(jù)，復(fù)雜度高，而且運(yùn)動捕捉數(shù)據(jù)絕大部分都是非線性的，直接對高維數(shù)據(jù)進(jìn)行處理分析費(fèi)時費(fèi)力，為了降低分割難度，并在保持原始數(shù)據(jù)原有拓?fù)浣Y(jié)構(gòu)及相關(guān)性的前提下，本文通過信息熵特征選擇和度量MDS完成了對數(shù)據(jù)的降維，然后通過聚類及相似性檢測得到最終的分割點(diǎn)，從而獲得若干不同類型的運(yùn)動片段。本文算法流程圖如圖1所示。 圖1 運(yùn)動序列分割流程圖2 本文分割算法介紹本文提出了一種基于特征選擇和k均值聚類的人體運(yùn)動捕捉數(shù)據(jù)分割方法，該方法首先通過計算每一維度的信息熵，提取信息量較大的維度，使用度量MDS將提取出來的數(shù)據(jù)映射到低維空間，然后通過k均值聚類

7、算法對低維數(shù)據(jù)進(jìn)行分類得到初始分割點(diǎn)集，最后通過計算指定窗口到前一個片段的幀間歐式距離來對初始分割點(diǎn)進(jìn)行相似性檢測，提取出該窗口中與前一片段的幀間距離方差最小的一幀作為最終精確分割點(diǎn)，從而得到了若干不同類型的運(yùn)動片段。接下來分別對本文算法中所用到的特征選擇和降維、聚類及分割兩個方面來進(jìn)行介紹。2.1 特征選擇和降維人體運(yùn)動捕捉數(shù)據(jù)維度高且其數(shù)據(jù)本身分布復(fù)雜，又因運(yùn)動捕捉數(shù)據(jù)絕大部分是非線性的，直接對數(shù)據(jù)進(jìn)行處理分析難度較大。為了降低對數(shù)據(jù)處理的難度，本文通過特征選擇得到一組包含高信息量的新的特征屬性，然后利用數(shù)據(jù)中每幀之間的相關(guān)性，采用度量MDS降維算法對其降維。（1）特征選擇人體運(yùn)動捕捉數(shù)據(jù)

8、是由若干連續(xù)運(yùn)動幀數(shù)據(jù)組成，每一幀代表一個固定的姿態(tài)，每一維度表示不同關(guān)節(jié)點(diǎn)的運(yùn)動參數(shù)，從而記錄了各個關(guān)節(jié)在各個時間的狀態(tài)。對于一定的人體運(yùn)動捕捉數(shù)據(jù)，其中不乏冗余的維度來表示運(yùn)動特征，比如簡單的揮手動作，人體的下半身的各個關(guān)節(jié)點(diǎn)與此動作沒有直接或者間接的關(guān)系，因此本文提出通過計算每一維度的信息熵來提取某一運(yùn)動捕捉數(shù)據(jù)的特征，從而降低了數(shù)據(jù)的復(fù)雜性及冗余度。信息的基本作用就是消除人們對事物了解的不確定性。美國信息論創(chuàng)始人香農(nóng)14發(fā)現(xiàn)任何信息都存在冗余，為了解決數(shù)據(jù)通信領(lǐng)域中信息傳遞過程中出現(xiàn)的信息冗余問題而提出，當(dāng)時主要用于解決通信控制系統(tǒng)中普遍存在的信息度量、變換和傳遞等問題19。如今隨著信

9、息和信息科學(xué)的不斷發(fā)展，人們對信息論的意義及其價值的認(rèn)識不斷加深，信息論的研究范圍已擴(kuò)大到所有與信息有關(guān)的研究領(lǐng)域，如心理學(xué)、語言學(xué)和語義學(xué)等。信息熵是信息論中的一個概念，用來衡量信息中所包含的信息量的大小。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越是混亂，信息熵就越高。因此，信息熵也可以說是系統(tǒng)有序化程度的度量。設(shè)人體運(yùn)動捕捉數(shù)據(jù)集X第I維數(shù)據(jù)XI的概率分布為：其中，n表示運(yùn)動序列的長度，J = 1,2,.,n I = 1,2,.,93, PI,J表示人體運(yùn)動捕捉數(shù)據(jù)第I維數(shù)據(jù)中第J幀數(shù)據(jù)點(diǎn)的概率大小，則數(shù)據(jù)XI的信息熵定義為“加權(quán)平均信息量”。本文在特征選擇時，計算出人體運(yùn)動捕捉數(shù)據(jù)

10、每一維度的信息熵，其中信息熵越大表示數(shù)據(jù)中該維度所含信息量越多，說明此時運(yùn)動狀態(tài)發(fā)生改變的程度大，可能是不同運(yùn)動狀態(tài)的分割點(diǎn)。信息熵越小則表示該維度所含信息量越少，意味著運(yùn)動狀態(tài)的改變小，是同一種運(yùn)動的概率比較大。在此提取信息熵較大的數(shù)據(jù)，從而獲得一組包含高信息量的新的特征屬性，以便于分析隱含在數(shù)據(jù)中的內(nèi)在關(guān)系。（2）度量MDS降維經(jīng)過特征選擇后的人體運(yùn)動捕捉數(shù)據(jù)仍然具有較高的維度且其數(shù)據(jù)本身分布復(fù)雜，又因運(yùn)動捕捉數(shù)據(jù)絕大部分是非線性的，直接對特征選擇后的數(shù)據(jù)進(jìn)行處理分析仍有著很高的復(fù)雜度?？紤]到數(shù)據(jù)內(nèi)部有特定的拓?fù)浣Y(jié)構(gòu)，并且每個序列的幀與幀之間有一定的相關(guān)性，因此對數(shù)據(jù)進(jìn)行降維不能破壞其原有

11、拓?fù)浣Y(jié)構(gòu)及相關(guān)性，滿足對后續(xù)序列進(jìn)行分割的基本要求。本文采用了度量MDS15對人體運(yùn)動捕捉序列進(jìn)行降維，該算法是一種基于歐式距離的非線性降維方法，適用于能夠反應(yīng)出研究對象間的相似性和差異性的數(shù)據(jù)，而運(yùn)動捕獲數(shù)據(jù)剛好符合這一要求。與其他降維方法相比，該算法針對非線性的數(shù)據(jù)降維，能夠較好地保持原始數(shù)據(jù)的原有拓?fù)浣Y(jié)構(gòu)以及相關(guān)性。本文所采用的度量MDS的主要思想是，將原始多維數(shù)據(jù)點(diǎn)映射到歐式空間，再在歐式空間中使用合適的點(diǎn)距來近似表示原始數(shù)據(jù)點(diǎn)間的距離。設(shè)特征選擇后的人體運(yùn)動捕捉數(shù)據(jù) X = (X1，X2，.，XN)t是t維空間內(nèi)一包括n個輸入向量的數(shù)據(jù)點(diǎn)集，用MDS降維方法從距離集合中重構(gòu)出X的坐標(biāo)

12、表示，為了讓低維嵌入坐標(biāo)中心在原點(diǎn)處且更好地與坐標(biāo)軸對齊，原始數(shù)據(jù)可假設(shè)已被中心化。該算法主要分為三個步驟：step1求得距離平方矩陣D：其中，i，j = 1，2.，N，e為N´1維全1陣，B = (|X1|,.,|XN|)T。step2將距離平方矩陣雙中心化：設(shè)J = I - eeT/N。其中，e為N´1維全1陣，I為N´N維單位矩陣，則Je = 0，eTJ = 0，JT =J ，(證明：同理可得：eTJ = 0)對任意包含N 個樣本點(diǎn)的輸入X = (X1,X2,.,XN)。利用J將距離平方矩陣雙中心化，則有：令，則。step3得到原始數(shù)據(jù)低維坐標(biāo)表示：令，將H

13、陣特征分解：。令為矩陣H 的特征值，令為其對應(yīng)特征向量，取其前d個特征值和其對應(yīng)前d個特征向量，進(jìn)而得到輸入X 的低維坐標(biāo)表示Y，如下表示：，將Y作為降維結(jié)果輸出，從而達(dá)到對原始運(yùn)動捕捉數(shù)據(jù)降維的目的。2.2 k均值聚類及分割通過特征選擇及度量MDS算法對特征維度數(shù)據(jù)進(jìn)行降維，得到一組表征運(yùn)動特征的低維數(shù)據(jù)。接下來對低維數(shù)據(jù)數(shù)據(jù)進(jìn)行k均值聚類分析。（1）k均值聚類算法的基本思想麥克奎因（J.B.MacQueen）16于1967年提出了k均值聚類算法，用來對數(shù)據(jù)進(jìn)行聚類，由于該算法過程簡便且很早被提出，所以在工業(yè)和科學(xué)領(lǐng)域應(yīng)用極其廣泛。該算法主要解決的是將含有n個數(shù)據(jù)點(diǎn)的集合劃分為k個類簇的問題

14、，該算法首先在集合中隨機(jī)選取k個數(shù)據(jù)點(diǎn)作為k個類簇的初始聚類中心，集合中的每個數(shù)據(jù)點(diǎn)將被劃分到與其距離最近的聚類中心所在類簇中，從而形成了k個聚類的初始分布。對分配后的每個類簇再次計算新的聚類中心，繼續(xù)進(jìn)行對數(shù)據(jù)的分配，以此迭代若干次之后，若果聚類中心不再發(fā)生變化則可說明該數(shù)據(jù)對象已全部被分配到自己所在的相應(yīng)類簇中，聚類準(zhǔn)則函數(shù)收斂，否則繼續(xù)對數(shù)據(jù)進(jìn)行迭代，直至收斂。聚類準(zhǔn)則函數(shù)一般采用聚類誤差平方和準(zhǔn)則函數(shù)。該算法的一個特點(diǎn)是在每次的迭代過程都要對全部數(shù)據(jù)進(jìn)行分配調(diào)整再重新計算聚類中心，然后進(jìn)入下一次的迭代，如果在某次的迭代過程中所有的數(shù)據(jù)點(diǎn)的位置沒有發(fā)生變化，且其相應(yīng)的的聚類中心也沒有發(fā)生

15、變化，此刻標(biāo)志著聚類準(zhǔn)則函數(shù)已經(jīng)收斂，且算法結(jié)束。（2）k均值聚類算法的算法流程輸入：將降維后所得的數(shù)據(jù)點(diǎn)集，聚類數(shù)目根據(jù)運(yùn)動序列中所含運(yùn)動的種類來確定，設(shè)為k；輸出：k個類簇Cj，step1 令I(lǐng) = 1，隨機(jī)地選取k個數(shù)據(jù)點(diǎn)作為k個類簇的初始聚類中心，；step2 計算每一數(shù)據(jù)點(diǎn)與k個聚類中心的距離，如果滿足則；step3 計算k個新的聚類中心step4 判斷：如果，則，返回step2；否則算法結(jié)束。（3）對運(yùn)動序列的分割前面通過對運(yùn)動捕捉數(shù)據(jù)進(jìn)行特征選擇、度量MDS算法降維、k均值聚類分析，對于長度為n的運(yùn)動序列，我們得到被標(biāo)記為1k的n個數(shù)組成的一維數(shù)組，其中1k為不同類簇的標(biāo)記。在此

16、對一維數(shù)組按照順序?qū)ζ浔闅v，對相鄰的兩幀進(jìn)行比較，如果相鄰兩幀屬于不同的類簇，則將較小幀存入矩陣D1中，同時，為了保證初始分割點(diǎn)不能過密，在此處設(shè)置閾值T，判斷矩陣D1中的相鄰兩幀的幀間長度是否大于閾值T，若條件成立，則兩幀都作為初始分割點(diǎn)，否則去掉較大幀，從而我們得到了運(yùn)動序列的初始分割點(diǎn)。其次，對初始分割點(diǎn)再次進(jìn)行檢測，該檢測過程主要分為幾個步驟：step1令；step2m = m + 1，以第m個初始分割點(diǎn)Pm為中心設(shè)置一個長度的窗口，即：幀，然后計算該窗口中的每一幀到前一個片段每一幀的幀間距離。由于各幀之間往往存在著不同的相關(guān)關(guān)系，幀間距離可選擇歐式距離，歐式距離定義如下：step3將

17、各幀間的歐式距離存入矩陣D3中，將D3作為樣本，計算其每行的方差，提取出方差較小的一幀即為最終分割點(diǎn)。4 結(jié)束語本文提出了一種基于特征選擇和k均值聚類的人體運(yùn)動捕捉數(shù)據(jù)分割方法，該方法首先計算運(yùn)動捕捉數(shù)據(jù)每一維度的信息熵，其中信息熵越大表示其所含信息量越多，提取信息熵較大的維度，通過度量MDS將提取出來的運(yùn)動數(shù)據(jù)映射到低維空間，然后采用k均值聚類算法對低維數(shù)據(jù)進(jìn)行分類得到初始分割點(diǎn)集，最后通過計算指定窗口到前一個片段的歐式距離來對初始分割點(diǎn)進(jìn)行相似性檢測，最后提取出該窗口中與前一片段的歐式距離方差最小的一幀作為最終精確分割點(diǎn)，從而得到了若干不同類型的運(yùn)動片段。在以后的學(xué)習(xí)工作中，我們將對本文提

18、出的算法進(jìn)行進(jìn)一步的深入研究及改進(jìn)，即：在特征選擇過程中，針對不同類型的運(yùn)動捕捉數(shù)據(jù)所要提取的信息量較多的維度的多少也不一樣，復(fù)雜的運(yùn)動序列可能要提取出較多的維度信息，而針對較為簡單的運(yùn)動序列則也許只需提取數(shù)據(jù)中的較少維度信息即可。所以我們將進(jìn)一步地通過實(shí)驗(yàn)來探討在保證分割準(zhǔn)確的前提下，如何針對不同類型的運(yùn)動捕捉數(shù)據(jù)提取出含高信息量的特征屬性，以降低數(shù)據(jù)的冗余度和復(fù)雜度。參考文獻(xiàn)1 赫高峰, 彭淑娟, 柳欣, 等. 結(jié)合模糊聚類和投影近似點(diǎn)算法的缺失人體運(yùn)動捕捉數(shù)據(jù)重構(gòu)J. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2015, 27(8): 1416-1425.2 石祥濱, 趙林, 代欽, 等. 基于關(guān)節(jié)

19、聯(lián)動特征的運(yùn)動捕獲數(shù)據(jù)分割方法J. 系統(tǒng)仿真學(xué)報, 2014, 11: 018.3 劉曉平, 陸勁挺, 謝文軍. 運(yùn)動捕捉數(shù)據(jù)中足跡的譜聚類檢測方法J. 中國圖象圖形學(xué)報, 2014, 9: 007.4 彭淑娟 ,柳欣. 一種結(jié)合雙特征的運(yùn)動捕獲數(shù)據(jù)行為分割方法. 計算機(jī)科學(xué).2013.5 Aoki T, Venture G, Kulic D. Segmentation of Human Body Movement Using Inertial Measurement UnitC/Systems, Man, and Cybernetics (SMC), 2013 IEEE Internatio

20、nal Conference on. IEEE, 2013: 1181-1186.6 Salamah S, Zhang L, Brunnett G. Hierarchical Method for Segmentation by Classification of Motion Capture DataM/Virtual Realities. Springer International Publishing, 2015: 169-186.7 Lin J.F.S, Kulic D. Segmenting human motion for automated rehabilitation exe

21、rcise analysisC/Engineering in Medicine and Biology Society (EMBC), 2012 Annual International Conference of the IEEE. IEEE, 2012: 2881-2884.8 Carlos Orrite, Mario Rodriguez et al. Automatic Segmentation and Recognition of Human Actions in Monocular Sequences. 2014 22nd International Conference on Pa

22、ttern Recognition of the IEEE. 2014:4218-4223.9 J. Zhang, J. Zhang, and S. Chen, “Discover novel visual categories from dynamic hierarchies using multimodal attributes,”IEEE Transactions on Industrial Informatics, vol. 9, no. 3, pp.16881696, 2013.10 Xiao J, Zhuang Y T, Wu F et al. A group of novel a

23、pproaches and a toolkit for motion capturedata reusing. Multimedia Tools and Applications. 2012, 47(30): 379-408.11 Lv N,Huang Y, Feng Z, et al A genetic algorithm approach to human motion capture data segmentationJ. Computer Animation and Virtual Worlds, 2014,25(3-4): 283-292.12 Peng S J. Motion Se

24、gmentation Using Central Distance Features and Low-pass Filter. International Conference on Computational Intelligence and Security, USA,2012:223-226.13 Yan Wang, Hyewon Seo, Soohyun Jeon. Automatic Transition Detection of Segmented Motion Clips Using PCA-based GMM MethodC. Cyberworlds: 2012 International Conference. 2012. 567572.14 15 X.-M. Liu, A.-M. Hao, and D. Zhao, “Optimization-basedkey frame extraction for motion ca