基于MVU降維的捕捉數(shù)據(jù)自動分割

張奕++王科琪

摘 要隨著人體運(yùn)動捕捉技術(shù)的不斷發(fā)展，其在輔助訓(xùn)練，醫(yī)療康復(fù)等領(lǐng)域有著越來越廣闊的前景。針對人工分割運(yùn)動序列錯誤率高，效率底下等缺點(diǎn)，提出了一種基于最大方差展開的非線性降維的運(yùn)動分割新方法。該方法包括以下幾個步驟：首先選定檢測窗口，對窗口內(nèi)的片段采用最大方差展開方法對進(jìn)行非線性降維，得到降維后的運(yùn)動序列以及殘差；然后在維度參數(shù)不變的情況下增大窗口區(qū)間，對其進(jìn)行降維，同時通過迭代特征值估計降低計算復(fù)雜度；最后根據(jù)殘差值的幅度跳變點(diǎn)衡量人體運(yùn)動序列的分割點(diǎn)。通過實(shí)驗(yàn)，證明了該運(yùn)動分割方法在準(zhǔn)確率和召回率上均有良好的表現(xiàn)。

【關(guān)鍵詞】人體運(yùn)動分割 最大方差展開 殘差 迭代特征值

隨著運(yùn)動捕捉的不斷發(fā)展，其在電影電視，游戲動畫，虛擬現(xiàn)實(shí)等產(chǎn)業(yè)的發(fā)展日新月異。在對運(yùn)動捕捉數(shù)據(jù)的處理中，運(yùn)動分割是尤為重要的一個環(huán)節(jié)。當(dāng)采集的人體運(yùn)動數(shù)據(jù)很多時，這些運(yùn)動都保存在人體運(yùn)動數(shù)據(jù)庫中，這時自動地對人體運(yùn)動捕獲數(shù)據(jù)進(jìn)行運(yùn)動類型分割，將顯得極為重要。分割后的數(shù)據(jù)應(yīng)包含特有的行為語義，也就是說只具有一個行為類型。分割后的數(shù)據(jù)應(yīng)包含特有的行為語義，也就是說只具有一個行為類型。將運(yùn)動的捕獲數(shù)據(jù)C分割為C1、C2、……、Cm，每個分割點(diǎn)需要精確求解，同時可以得到分割段數(shù)m。

目前對運(yùn)動序列的分割方法主要可以分為兩種：人工參與操作的人工分割，無人工參與的自動分割。人工手動分割又分為純手動分割和含有預(yù)處理分割的半自動分割?？傮w而言，人工參與的分割速度慢效率低下，錯誤率高。自動分割是通過無監(jiān)督學(xué)習(xí)將運(yùn)動序列自動的分成不同行為的片段，可以實(shí)現(xiàn)全自動化。由于人工參與的分割方法有著速度慢，準(zhǔn)確度低，且需要耗費(fèi)大量的人力資源等缺點(diǎn)，所以自動分割運(yùn)動序列的重要性顯而見之。

對于自動分割算法的研究，國內(nèi)外已有一些學(xué)者作出了較大的貢獻(xiàn)。Barbic等人[2]提出了3種分割方法。首先，他們根據(jù)對不同階段動作的本征值進(jìn)行比對，發(fā)現(xiàn)相似的運(yùn)動序列擁有平緩而且較低的本征值，而引入不同的運(yùn)動序列會導(dǎo)致本征值的激增。根據(jù)觀測本征值的突變點(diǎn)，從而提出了PCA 方法；他們還提出了概率主成分分析（PPCA）方法。 基于PCA方法，引入概率模型，假設(shè)不同的動作具有不同的高斯分布。最后，他們假設(shè)不同的運(yùn)動數(shù)據(jù)圍繞各個運(yùn)動中心聚集以形成一個簇，并且每個簇可以由高斯分布模型表示，從而提出了GMM方法。Chang等[3]提議在貝葉斯框架的同時進(jìn)行線運(yùn)動估計和運(yùn)動分割。 它將該字段表示為參數(shù)字段在MAP形式中，通過光流和分割的相互依賴吉布斯分布代表。 使用最高的信心優(yōu)先和迭代條件模式算法對不同的運(yùn)動行為進(jìn)行分割。Zhou等[4]采用對齊聚類分析對運(yùn)動序列進(jìn)行譜分解，對相似的動作進(jìn)行聚類后通過計算最小誤差能量進(jìn)行分割。在國內(nèi)領(lǐng)域，馮林等[5]提出了人體運(yùn)動分割的時間流形學(xué)習(xí)方法。該方法使用動作序列的局部關(guān)節(jié)彎曲指數(shù)來分析不同階段各運(yùn)動的相干性，并觀察模糊過度段數(shù)據(jù)，通過測量關(guān)節(jié)彎曲斜率過零點(diǎn)，發(fā)現(xiàn)動作序列的軌跡。杜戰(zhàn)戰(zhàn)等[6]通過主測地線分析，結(jié)合姿勢分布的馬氏距離曲線對序列進(jìn)行分割。肖俊等[7]提出了一種半自動分割方法。根據(jù)生理學(xué)模型，提取肢體中心骨架的關(guān)節(jié)角度作為人的描述特征。將高維運(yùn)動序列降維成一維時序信號。胡曉雁等[8]通過線性聚類分析解決了運(yùn)動序列分割點(diǎn)。該方法通過規(guī)劃運(yùn)動序列的距離，衡量出不同序列的合適距離指標(biāo)，從而通過各種不同聚類分析方法完成分割。

人體運(yùn)動序列數(shù)據(jù)是一個高維數(shù)據(jù)集。直接對高維數(shù)據(jù)集進(jìn)行計算，計算成本高，耗時長，對噪聲敏感。這就需要對高維的人體運(yùn)動做適當(dāng)?shù)慕稻S處理，使得維度簡化，剔除維度間相關(guān)性，同時保存原始數(shù)據(jù)的大部分信息量。從而提高運(yùn)算效率和精確度。

在上述分割方法中，普遍利用了線性降維方法作為對運(yùn)動序列做處理。然而人體時序運(yùn)動序列往往并不具有線性特征。由于其復(fù)雜性和多樣性，使用線性降維的過程中往往會導(dǎo)致不可忽視的誤差，一般情況下傳統(tǒng)線性降維難以提取出其中的線性規(guī)律。由于本方法引入了非線性降維，能夠更好的概括人體運(yùn)動的細(xì)節(jié)特征，從而實(shí)現(xiàn)準(zhǔn)確率的提升。本文提出一種基于非線性降維的運(yùn)動分割方法，采用了非線性降維算法MVU對運(yùn)動序列進(jìn)行降維，該方法計算效率高，收斂性強(qiáng)，魯棒性高，并對各種不同的非線性序列都能取得良好的降維效果。

1 MVU降維

1.1 原始降維算法

最大方差擴(kuò)展（ maximum variance unfolding，MVU ）是基于局部等距概念提出的非線性降維學(xué)習(xí)算法，可以被認(rèn)為是可以自動學(xué)習(xí)訓(xùn)練數(shù)據(jù)核矩陣K的KPCA特例[10]，MVU是一個高維數(shù)據(jù)流保持映射之前和之后相鄰點(diǎn)之間的歐氏距離的條件，具有以下兩個優(yōu)點(diǎn)：一方面不僅可以學(xué)習(xí)高維數(shù)據(jù)集中隱含的低維信息，而且可以揭示內(nèi)含尺寸。另一方面，由于該算法不需要測量高維數(shù)據(jù)點(diǎn)之間的歐氏距離，所以非凸數(shù)據(jù)集也具有理想的降維效果。此外，與PCA相比，兩者具有相同的優(yōu)化函數(shù)表達(dá)式，可以視為PCA的非線性形式。更重要的是，MVU維度可以更好地保持訓(xùn)練數(shù)據(jù)的分布。

MVU基本算法如下所示，設(shè)：X=[x1，x2，……xn]是高維數(shù)據(jù)集Y=[y1，y2，……yn]降維后的低維數(shù)據(jù)集，MVU算法設(shè)定一個以局部等距為前提的約束條件，在該條件下對點(diǎn)之間進(jìn)行最大化展開，再以此為基礎(chǔ)還原原始數(shù)據(jù)流形。算法先根據(jù) X 構(gòu)造一個鄰域圖G，如果xi是xj的k近鄰，則權(quán)值Wij=1，否則Wij=0。這是一個在平方等式約束下的非凸二次規(guī)劃問題，將它轉(zhuǎn)化為一個半定規(guī)劃問題獲得最優(yōu)解。定義Y的核矩陣Kij=yi·yj，則該半定規(guī)劃可以轉(zhuǎn)換為：

（1）

（2）

設(shè)K*為該優(yōu)化問題的最優(yōu)解，λα是K*的第α個特征值，Vαi為相應(yīng)特征向量的第i個元素，對K*進(jìn)行譜分解得到K*ij=∑nα=1λα Vαi Vaj。因此，高維數(shù)據(jù)xi的n維映射的第α個元素為。

1.2 降維誤差衡量

由于降維過程中存在不可避免的數(shù)據(jù)損耗，為了衡量同原始數(shù)據(jù)的誤差，我們采用殘差來評判。通過定義能量百分比：

（3）

是數(shù)據(jù)集的原始維數(shù)，即原始采集信息維度。d是降維維數(shù)，即降維原始數(shù)據(jù)后用于分析的維數(shù)。λi表示原始數(shù)據(jù)集的核矩陣K*的第a個特征值。由于特征值揭示了原始數(shù)據(jù)集在投影到降維數(shù)據(jù)集上時對應(yīng)特征向量方向的原有信息量，因此pd表示降維到d維度時變換所保留的信息量。通過殘差，可以清楚的衡量現(xiàn)有降維結(jié)果同原始數(shù)據(jù)之間的誤差。

2 基于MVU的運(yùn)動分割方法

在對一段運(yùn)動進(jìn)行分析的時候，我們假設(shè)描述該運(yùn)動不同階段所需的維度是不同的。同時，運(yùn)動包含的運(yùn)動階段越多，運(yùn)動數(shù)據(jù)就越復(fù)雜，描述該運(yùn)動所需的維度就越多。在MVU降維過程中，向子空間映射時，想要得到同前一運(yùn)動段同樣的誤差，就需要更多的維度。即使用描述單一運(yùn)動段的維度來描述多個合并的運(yùn)動段，勢必會導(dǎo)致誤差的急劇增大。通過對誤差的觀測，會觀測到誤差急劇增大的幀，此時可以斷定該幀即為運(yùn)動序列的分割幀。

2.1 降維過程

在分析人體運(yùn)動行為時，一般情況下使用關(guān)節(jié)點(diǎn)角度作為運(yùn)動特征。為了避免萬向鎖，我們采用四元數(shù)代替歐拉角進(jìn)行特征提取。而考慮到手，腳的子關(guān)節(jié)點(diǎn)對人體姿態(tài)影響不大，我們只選用了14個關(guān)節(jié)點(diǎn)，同時避免了引入不必要的誤差。

首先根據(jù)鄰域參數(shù)k，對原始數(shù)據(jù)構(gòu)造等距約束，并計算該約束下的臨域關(guān)系V，計算X中xi與其他點(diǎn)xj的歐氏距離dis（i，j）。若xi是xj的k鄰近點(diǎn)，則兩點(diǎn)彼此相鄰，且邊權(quán)值dis（i，j），否則xi，xj在V中斷開。引入核函數(shù)求解該優(yōu)化問題，得到最優(yōu)解K*，從而可以根據(jù)最優(yōu)解進(jìn)行譜分解，得到特征值。

2.2 迭代特征值估計

在實(shí)際的求解過程當(dāng)中，特征值的計算一般來說是非常復(fù)雜的。本例中，矩陣的階數(shù)高，計算復(fù)雜度大，要想精確的計算出特征值是很困難的。因此，由矩陣元素估計出特征值的范圍就顯得尤為重要。本文采用迭代特征值估計的方法簡化計算復(fù)雜度。對于符合特定條件下的矩陣，通過特征值的估計值轉(zhuǎn)化原特征值于另一矩陣，從而得到對原特征值的數(shù)值解法。由圓盤定理的推論可得：已知給定n階矩陣A，當(dāng)A的n個圓盤互不相交時，則有估計式：

（4）

從而可以得到λi的近似值。迭代估計法的具體實(shí)現(xiàn)如下。

算法1-1 計算矩陣A的近似特征向量

輸入：矩陣A，近似幅度ε，

輸出：近似特征向量y，近似特征值λ

任意取非零向量u0，對于m=1，2，3，….執(zhí)行：

進(jìn)行LU分解，即（A-αI）=LU

4.當(dāng)|βm-βm-1|<ε時，停止迭代，其結(jié)果為λ≈βm，近似特征向量為ym-1。

2.3 分割過程

首先，對于待分割的原始運(yùn)動序列，選定一個長度為K的可變時序窗口，該窗口隨幀的導(dǎo)入而不斷向前變長。對該窗口內(nèi)部的幀進(jìn)行MVU降維，計算該段運(yùn)動同原始數(shù)據(jù)的殘差R。在維度不變的情況下，對窗口進(jìn)行擴(kuò)展，幅度為s幀。其中s表示擴(kuò)展段，可以有效降低計算負(fù)責(zé)度。在得到每隔s幀的殘差值序列后，對于同一階段的運(yùn)動序列來說，殘差增長的很平緩，但當(dāng)運(yùn)動序列開始發(fā)生變化時，所需維度增加，這時殘差陡然增大，可以根據(jù)斜率增大點(diǎn)判斷分割點(diǎn)。設(shè)殘差增幅為，其中di為當(dāng)前窗口的殘差，di-1為前一窗口的殘差。當(dāng)D突變時，其所在的幀即為動作發(fā)生變化的幀。對殘差增幅求平均值，當(dāng)時，該所在幀可以看作為運(yùn)動分割幀。此時重新歸零殘差R，并重新設(shè)定時序窗口，對剩余數(shù)據(jù)進(jìn)行MVU降維，以此類推，從而對運(yùn)動序列進(jìn)行分割。

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

為了對算法進(jìn)行準(zhǔn)確率和有效性的驗(yàn)證，本文通過對一組包含不同運(yùn)動行為的連續(xù)時序運(yùn)動數(shù)據(jù)進(jìn)行了分割。實(shí)驗(yàn)采用的是美國CMU數(shù)據(jù)庫。選擇第86號視頻捕捉數(shù)據(jù)庫，該數(shù)據(jù)庫包含了走路，跑步，靜坐，攀爬，看書等一系列運(yùn)動，選擇其中的10條進(jìn)行運(yùn)動分割。主要動作姿態(tài)如圖1所示。

為了衡量運(yùn)動分割方法的性能指標(biāo)，采用分割點(diǎn)的查準(zhǔn)率和查全率，以手工分割的結(jié)果作為評價標(biāo)準(zhǔn)。查準(zhǔn)率是指采用本方法自動探測到的分割點(diǎn)中正確分割點(diǎn)所占的比例，查全率是指采用本方法自動探測到的正確分割點(diǎn)占手工分割點(diǎn)的比例。公式如下：

（5）

（6）

其中，E為算法正確落入分割點(diǎn)區(qū)間個數(shù)，A為算法分割點(diǎn)總個數(shù)，M為手動分割點(diǎn)個數(shù)。作為對比實(shí)驗(yàn)，我們采用PCA和PPCA分割方法作為對比，分割結(jié)果如表1所示。

從對兩段實(shí)驗(yàn)結(jié)果的分析可以清晰的了解本文方法的優(yōu)勢所在。

實(shí)驗(yàn)一：對86_01的分割結(jié)果如下所示：（簡單序列分割）該運(yùn)動序列為一個長度為4580的組合運(yùn)動序列，包含了行走、下蹲、攀爬等不同運(yùn)動。采用MVU降維，降維后的維度為10。結(jié)果如圖所示：結(jié)果表明該段組合序列包含五個穩(wěn)定片段。分別代表行走，立定跳遠(yuǎn)，行走，立定跳遠(yuǎn)，踢腿，擊拳。將分割結(jié)果同PCA和手動分割結(jié)果，以及粗分割結(jié)果進(jìn)行對比。如圖2所示：由于第二次立定跳遠(yuǎn)動作比較遲緩，PCA未能正確對第一次立定跳遠(yuǎn)后進(jìn)行正確分割，同時未能將踢腿和打拳正確分割開，而是將他們識別成了一個運(yùn)動。而基于MVU的運(yùn)動分割則成功的將遲緩的第二次立定跳遠(yuǎn)階段分割開，同時正確的將踢腿和打拳分割成兩個不同的運(yùn)動，成功實(shí)現(xiàn)了對相似動作的分割，提高了分割準(zhǔn)確率。

實(shí)驗(yàn)二：對86_09的結(jié)果如下所示：該運(yùn)動序列為一個長度為4531的組合運(yùn)動序列，包含了行走、坐下、讀書、眺望、行走等運(yùn)動。采用MVU降維，降維后的維度為10。結(jié)果如圖3所示：該段組合序列包含五個穩(wěn)定片段。而PCA分割則未能正確的對坐下行為進(jìn)行分割，而基于MVU的運(yùn)動分割則成功的命中這一段的分割，成功的提高了對復(fù)雜運(yùn)動的分割精度。

通過上述實(shí)驗(yàn)的分割結(jié)果對比可以得出，基于MVU的運(yùn)動分割方法可以基本保證對運(yùn)動序列的正確分割，得到更精確的分割結(jié)果。同時，該方法未能成功的分割出讀書和眺望兩個運(yùn)動，究其原因是由于讀書同眺望兩運(yùn)動相隔太接近，小于區(qū)間窗口閾值，導(dǎo)致殘差計算誤差較大。這也是今后下一步研究的主要方向。

4 結(jié)語

在本文中，我們提出了一種基于MVU非線性維數(shù)降低的運(yùn)動數(shù)據(jù)分割方法。由于人體運(yùn)動數(shù)據(jù)有著非線性的特征，所以對于給定的人類時間序列運(yùn)動數(shù)據(jù)，MVU能夠克服線性尺寸縮減難以處理的非線性特征的缺點(diǎn)，可以更好的擬合人體運(yùn)動數(shù)據(jù)，實(shí)現(xiàn)更高的正確率。本方法首先對選定的運(yùn)動序列窗口進(jìn)行MVU降維，并且通過迭代特征值以減少運(yùn)動序列的計算復(fù)雜度，然后依賴特征值求得運(yùn)動序列的殘差，不斷擴(kuò)大序列窗口，從而構(gòu)建殘差曲線。通過衡量殘差曲線的跳變點(diǎn)，從而實(shí)現(xiàn)整個運(yùn)動數(shù)據(jù)的分割。由于分段穩(wěn)定片段具有特定的運(yùn)動語義，因此可以進(jìn)一步用于運(yùn)動合成，搜索等應(yīng)用。在未來的工作中，我們將進(jìn)一步優(yōu)化非線性降維運(yùn)動分割算法，包括進(jìn)一步的提高分割算法效率，以及提高對復(fù)雜動作分割的準(zhǔn)確率。

參考文獻(xiàn)

[1]李豪杰，林守勛，張勇東.基于視頻的人體運(yùn)動捕捉綜述[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2006（11）：1645-1651.

[2]Barbi? J，Safonova A，Pan J Y，et al. Segmenting motion capture data into distinct behaviors[C].Proceedings of Graphics Interface 2004.Canadian Human-Computer Communications Society，2004：185-194.

[3]Michael M Chang，A Murat Tekalp， M Ibrahim Sezan.An Algorithm for Simulta-neous Motion Estimation and Segmentation[C].IEEE Internal Conference on Acoustics，Speech and Signal Processing（ICASSP94）， Adelaide，Australia，1994：221-224.

[4]Zhou Feng，Torre F，Hodgins J K.Aligned cluster analysis for temporal segmen-tation of human motion[C].8th IEEE International Conference on Automatic Face & Gesture Recognition，Amsterdam，The Netherlands，2008：1-7.

[5]馮林，劉勝藍(lán)，王靜，肖堯.人體運(yùn)動分割算法：序列局部彎曲的流形學(xué)習(xí)[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2013（04）：460-467+473.

[6]杜戰(zhàn)戰(zhàn)，孫懷江.基于PGA的人體運(yùn)動捕獲數(shù)據(jù)分割方法[J].計算機(jī)工程與應(yīng)用，2016（10）：141-146.

[7]肖俊，莊越挺，吳飛.三維人體運(yùn)動特征可視化與交互式運(yùn)動分割[J].軟件學(xué)報，2008（08）：1995-2003.

[8]胡曉雁，孫波，朱小明，魏云剛.基于譜聚類的運(yùn)動捕獲數(shù)據(jù)分割[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2016（08）：1306-1315.

[9]Weinberger，Kilian Q.，and Lawrence K. Saul."An introduction to nonlinear dimensionality reduction by maximum variance unfolding."AAAI.Vol.6. 2006.

[10]Yang J， Frangi A F，Yang J，et al. KPCA plus LDA：a complete kernel Fisher discriminant framework for feature extraction and recognition[J].IEEE Transactions on pattern analysis and machine intelligence，2005，27（02）：230-244.

[11]Liu Y J，Chen T，Yao Y.Nonlinear process monitoring and fault isolation using extended maximum variance unfolding[J].Journal of Process Control，2014，24（06）：880-891.

[12]陳如清.基于改進(jìn)MVU的非線性動態(tài)過程故障檢測方法[J].儀器儀表學(xué)報，2013（09）：2111-2117.

[13]Chaloner K，Brant R.A Bayesian approach to outlier detection and residual analysis[J].Biometrika， 1988：651-659.

[14]Shoemake K.Animating rotation with quaternion curves[C].ACM SIGGRAPH computer graphics.ACM，1985，19（03）：245-254.

[15]Ran R S，Huang T Z.Bounds for Modules of Eigenvalues of Iterative Matrices[J].Journal of University of Electronic Science and Technology of China，2006，35（01）：133-136.

[16]Wu H T，Yang J F，Chen F K. Source number estimators using transformed Gerschgorin radii[J].IEEE Transactions on Signal Processing，1995，43（06）：1325-1333.

作者簡介

張奕（1984-），男，山東省濟(jì)南市人。博士學(xué)位。現(xiàn)為大連大學(xué)信息工程學(xué)院副教授。主要研究方向?yàn)檫\(yùn)動捕捉及壓縮感知。

王科琪（1991-），男，安徽省蕭縣人。碩士研究生?，F(xiàn)為大連大學(xué)信息工程學(xué)院碩士研究生。主要研究方向?yàn)檫\(yùn)動捕捉。

作者單位

大連大學(xué)信息工程學(xué)院 遼寧省大連市 116000