多圖融合約束半非負矩陣分解的動作分割方法

李國朋，王連清，韓鹍，王宇弘，宋聃，余立,2

（1. 國防科技大學 試驗訓練基地, 陜西 西安 710106; 2. 國防科技大學 智能科學學院, 湖南 長沙 410073; 3. 國防科技大學 信息通信學院, 湖北 武漢 430035; 4. 國家工業信息安全發展研究中心, 北京 100040）

動作分割是將采集到的動作序列數據分割成若干個不同的動作片段，其在人體行為理解[1]、人機交互[2]、機器人控制[3]、數據挖掘[4]等多個領域具有廣泛的應用。與其他數據相比，動作序列數據通常包含多個動作片段。一般認為，序列中相鄰幀（點）的變化是連續的、緩慢的，具有較高的相似性[5]。動作分割時，屬于同一個動作片段內的相鄰幀應劃分到一起；而在不同動作片段邊界上的相鄰幀應分別劃分到對應的動作片段中。因此動作分割的關鍵包括同一動作片段內所有幀的一致分割和動作片段邊界幀的準確分割 (即動作邊界的準確判斷)。目前已有大量工作對該問題進行了深入研究，取得了一系列成果，提出了許多基于監督[6]或無監督學習[7]動作分割方法。如基于深度學習模型的方法[8]通過訓練數據集上學到的不同粒度、類型的時序特征，可以實現較好的動作分割效果。然而此類基于監督的方法需要大量標注數據，對計算資源要求也相對較高。相比之下，基于聚類的無監督學習方法將不同動作片段看作一類，動作分割就是將動作序列中所有幀聚類到相應動作片段中。這種方法簡單、直觀，建模靈活，受到越來越多的重視。

考慮到動作序列中的結構相似性特點，即相鄰幀之間是平滑的、緩慢變化的，它們之間具有較高的相似性，因此在基于聚類的分割方法中，特征表示學習過程中融入結構相似性是提升分割準確性的關鍵。如基于子空間聚類 (subspace clustering, SC)[9]，TSC（temporal subspace clustering）[5]構造了相鄰幀之間的約束正則項嵌入到子空間投影過程中；TLRSC (temporal plus low-rank subspace clustering)[10]在子空間投影中引入結構相似性約束和低秩約束，這些結構相似性的引入可以幫助獲得更好的動作序列圖表示用于聚類。而基于半非負矩陣分解(semi-nonnegative matrix factorization, Semi-NMF)方法[11]，文獻[12]在降維的過程中融入了多近鄰幀結構相似性約束，可以獲得更準確的動作序列低維特征表示用于后續的聚類。TW-FINCH (temporally- weighted hierarchical clustering)[13]是一種層次聚類方法，在相似性度量中利用結構最近鄰的高相似性來約束相鄰幀盡可能的劃分到同一動作中。ABD (action boundary detection)[1]通過尋找動過片段的邊界來分割不同動作，同樣也利用結構相似性來實現快速分割。顯然這些方法的核心思路是利用結構相似性約束相鄰幀盡可能一致歸屬到相同類，通過實現動作片段內部聚類的準確性有效提升動作分割的準確性。

然而，結構相似性雖然可以確保動作片段內部的一致歸屬，但是如果相鄰幀處在不同動作片段的邊界上，帶來的問題就是會造成邊界分割的不準確。這是因為邊界處的相鄰幀在實際中如果差異確實較大，那么該差異信息是準確判斷不同動作片段的依據，而結構相似性約束減小了這種邊界處的差異信息，使得邊界處不同動作的幀之間相似性關系增強，邊界變得更加難以判斷，給分割造成困難；并且在結構相似性約束中引入的相鄰幀數越多，差異信息減少越多，動作邊界越難以判斷，導致動作分割的準確性很難進一步提升，這是動作分割的難點[14]。針對該問題，可以考慮采用其他相似性信息來提升分割效果。如文獻[15]利用k 近鄰相似性約束來提升聚類的準確性，該約束是一種度量相似性，通過使用距離函數計算幀間相似性來尋找前k個高相似性關系，并在特征表示學習中保持該相似性關系。對于動作序列而言，如果邊界上的相鄰幀差異較大，那么該約束不會影響邊界處的差異性，可以減少邊界處的錯誤分割；但是如果不同動作片段中存在一些相似幀 (如跑步與跳躍動作中都存在雙腳離地的幀) ，那么該約束可能會將那些本屬于不同動作片段的幀歸屬到相同類，造成動作片段內部分割的不一致。可見，對于動作分割而言，不同的相似性約束各有利弊，為了實現準確分割，盡可能保持動作片段內所有幀的相同歸屬和邊界處的準確分割十分有必要。

基于以上分析，不同于當前大多數方法僅利用結構相似性約束來提升動作分割的準確性，為了發揮不同相似性約束的優勢，本文提出了融合結構相似性和度量相似性信息的多圖融合約束Semi-NMF (multi-raph constraint Semi-NMF, MGSeNMF)動作分割方法。該方法首先在特征表示學習過程中，通過融合兩種相似性關系圖構造正則約束項約束Semi-NMF 獲得序列的低維表示；進而生成動作序列的k 近鄰圖[16], 再使用圖割[17]進行分割。

本文工作可概括如下：

1) 提出一種融合結構相似性和度量相似性信息的多圖融合約束Semi-NMF 動作序列特征表示學習算法，在動作序列的表示中保持更合理、更準確的近鄰關系。

2) 提出一種求解多圖融合約束Semi-NMF 優化問題的方法，獲得動作序列的低維表示并生成動作序列的k 近鄰圖。

3) 在視頻和捕獲這兩類真實動作序列數據集上進行分割實驗。實驗結果表明與其他經典方法相比，所提方法適用于不同類型數據，能在保持動作片段內部一致歸屬的同時準確分割動作邊界，提升分割準確性，整體運行效率更高。

1 相關工作

當前基于聚類的動作分割方法主要思路是：首先在基于SC、Semi-NMF 等特征表示學習的過程中融入相似性信息，確保近鄰幀之間具有較高相似性；再利用k-means、圖割等對獲得的特征表示進行類劃分，實現分割的目的。其中融入結構相似性約束是此類方法的主要工作。本節主要從基于Semi-NMF 的特征表示學習和結構相似性約束正則項構造兩方面展開論述。

1.1 基于Semi-NMF 的特征表示學習

設輸入動作序列X∈Rd×n，包含n個連續的數據幀（點）記作：{x1,x2,···,xn}，每個數據幀的特征維度為d。基于SC 的各種方法可以獲得序列X的關系圖表示G∈Rn×n，而基于Semi-NMF 的方法是在特征空間Z∈Rd×p上獲得一個低維特征表示H∈Rp×n，再利用其他方法獲得關系圖表示G，其中p表示降維后的特征維數。因此，基于Semi-NMF 的特征表示學習可描述為一個優化問題：

其中H中的元素為非負值。Semi-NMF 能夠處理負值數據，具有建模簡單靈活，可解釋性強等特點。

研究表明在Semi-NMF 過程中施加相似性約束可以提高特征學習的質量[15,18]，從而實現聚類性能的提升。為了融入這種關系，通常設近鄰關系圖W∈Rn×n描述了原始數據之間的近鄰相似性關系，則約束Semi-NMF 可描述為

式中L是W的拉普拉斯矩陣。D是 對角矩陣，定義為通過在優化模型中施加此類相似性關系約束，Semi-NMF 在迭代中保持原數據點之間的關系，從而提高特征學習的性能。特別地，針對動作序列而言，設計結構相似性約束正則項融入到特征學習中是序列數據聚類的研究重點。

1.2 結構相似性約束正則項構造

為了在特征表示學習的過程中融入結構相似性，文獻[5]認為在動作關系圖G的學習過程中，當前數據幀xi與它之后的數據幀xi+1之間的差異應該盡可能的小。為此可以引入正則約束項‖GR‖1，其中R∈Rn×n是近鄰指示矩陣，定義如下：

該約束項通過L1范數使得xi與xi+1之間的差異盡可能小。基于此約束項，人們設計了許多基于結構約束聚類的動作分割方法[19]。文獻[12]認為xi與其前后不止一個近鄰幀具有相似性，可以在構造約束項時同時考慮多個近鄰幀，因此可在低維特征表示H學習過程中，利用L2,1范數構造正則約束項‖HR‖2,1，其中，包含q個結構近鄰的近鄰指示矩陣R表示如下：

文獻[20]認為此類多近鄰相似性約束項中，離序列點越遠的點，其相似性越低，所占權重應當不同。因此，在關系圖G學習中引入遺忘因子來構造約束項包含3 個結構近鄰的近鄰指示矩陣R可描述為：

式中：參數β=1-α， α是遺忘因子。相關實驗表明，增加相鄰幀的個數，可以強化動作片段內部的劃分一致性，提升動作分割的準確性。

綜上可見，目前多數研究主要考慮如何設計更合理的結構近鄰約束，忽視了近鄰約束給動作邊界處的準確分割可能帶來的問題。如果要進一步提升動作分割的準確性，邊界處的準確分割也同樣重要。因此為了兼顧動作片段內部的一致歸屬和邊界處的分割問題，本文通過融合不同近鄰約束來有效降低目前方法存在的潛在弊端，實現更準確的動作分割。

2 基于多圖融合約束矩陣分解的特征表示

2.1 多圖融合約束項構建

2.1.1 兩種相似性關系圖的構建

設xi是動作序列中的一幀，考慮利用xi前后的各q個近鄰來構造該點結構近鄰約束，則xi的結構近鄰集合可描述為

式中：C(xi)表示xi的q結構近鄰集合，i和j分別表示xi和xj在序列中所處的位置，若它們之間所處位置相差不超過q，則xj是xi的一個結構近鄰。 此時序列中所有幀的q結構近鄰集合構成了序列的結構近鄰相似性關系，描述為一個無向無權圖W1=[V E1]。其頂點V={x1,x2,···,xn}是序列中所有幀的集合，E1是頂點之間邊的集合，定義如下：

同時，對于度量相似性關系，選擇經典的k近鄰進行描述[15]。采用“binary”距離計算所有幀與xi的距離，距離越小，說明與xi相似性越高，其中距離最小的前k個幀就構成了xi的k 近鄰集合，描述為

式中：dxi,xj表示xi和xj之間的距離，dik表示從最短距離開始的第k個最短距離。若dxi,xj≤dik，表明xj是xi的一個k 近鄰幀。同理，序列中所有幀的k 近鄰集合就構成了序列度量相似性關系，描述為無向無權圖W2=[V E2]。頂點V也是序列中所有幀的集合，而E2是頂點之間邊的集合，其定義如下:

2.1.2 兩多關系圖的融合

如前所述，W1和W2從不同相似性角度描述了幀間關系，各有利弊，為了充分吸收它們的優點，可以融合這兩種相似性信息來實現融合約束，提升特征表示學習的質量。基本思路是采用線性組合的策略[21]，對W1和W2進行融合。為此構建多圖融合約束項如下：

其中Li表示第i個關系圖的拉普拉斯矩陣，定義為表示第i個關系圖在組合中的權重，定義為

顯然，在融合約束項中，不同圖約束項的權重取決于各自圖差異值計算的結果。計算結果越小，說明相似性越高，該約束項權重越大。考慮到同一動作片段內，相鄰幀之間相似性較高，此時xi+1既是xi的結構近鄰又是度量近鄰，那么融合約束項可以有效保持它們之間的近鄰關系；而在邊界處，若xi+1不是xi的度量近鄰，那么圖W1計算所得相似性結果要小于W2計算結果，W1在融合約束項中權重小于W2權重，因此結構相似性約束力度將會減小，從而有利于邊界處差異性特征的保留。

2.2 多圖融合約束Semi-NMF 低維特征學習

對于輸入序列，將上述多圖融合約束項融入到Semi-NMF 中，構建低維特征學習優化模型如下所示：

1）更新Z

固定其他變量，由于Z可以取負值，此時根據矩陣運算規則，可得Z的閉式解為

2）更新H

固定其他變量，H的求解轉化為關于H的如下問題：

考慮到X和Z均可取負值，不失一般地，令M+、M-分別表示矩陣M非負部分和負值部分，即：M+=(|M| +M)/2，M-=(|M|-M)/2，于是問題可改寫為

根據Semi-NMF 的迭代規則求解理論[11]，H的更新規則推導可以通過構造輔助函數并求解該函數來完成。L(H)的輔助函數G(H,Ht)需滿足G(H,Ht)≥L(H)且G(H,H)=L(H)。可以定義L(H)的輔助函數為：

首先需要證明G(H,Ht)是L(H)的一個輔助函數。

證明 顯然G(H,H)=L(H)滿足，重點證明G(H,Ht)≥L(H)。

當非負矩陣S∈Rn×n、B∈Rp×p是對角矩陣時，如下不等式成立：

利用該不等式，可得：

利用不等式z＞1+logz（z＞0），可得：

綜上可得：G(H,Ht)≥L(H)，因此它是L(H)的輔助函數。

證畢。

其次通過求解G(H,Ht)來求解優化問題(14)，考慮到G(H,Ht)是一個凸優化，令：

可得H迭代規則：

3）更新τ

為了確定不同關系圖的權重，需要根據每次迭代過程中H的重新確定W1和W2的權重系數。因此迭代中τ需要按照式（11）重新計算權重。

通過以上的迭代更新，最終可以獲得動作序列的低維特征表示H，利用該特征表示可以獲取序列的k 近鄰圖表示。

3 基于k 近鄰圖的動作分割

考慮到獲得的矩陣H中蘊含豐富的各種幀間相似性關系，可以清晰地通過這種相似性關系描述整個動作序列的關系圖，因此矩陣H生成k 近鄰圖G∈Rn×n是一個無向無權圖G=[V E]，頂點V是序列中所有幀的集合，E是頂點之間邊的集合，定義如下：

其中N(hi)表示利用特征表示矩陣H計算獲取的第i幀的k 近鄰集合，k 近鄰計算同樣按照文獻[14]方法進行。

最后利用圖割方法對G進行分割，獲得動作分割結果。Ncut 是常用的圖分割方法，其利用D的拉普拉斯特征值第2 小所對應的特征向量來分割，詳細介紹可參考文獻[17]。

綜上，本文提出的MGSeNMF 動作分割方法可描述如下：

算法 基于MGSeNMF 動作分割

輸入X,q，k，α

1)初始化:

(Z,H)←Semi-NMF(X)，W1←式(6～7)，

W2←式(8～9) ，τ1=τ2=0.5

2)while 沒有收斂 do

Z←式(13)，H←式(24)，τ ←式(11)

3)end while

4)生成k 近鄰圖：G←H

5)聚類: Ncut(G)

輸出 分割結果

其中初始矩陣Z、H采用經典Semi-NMF 進行賦值， τ初始值都是0.5 表示兩種圖關系的權重相同。

4 實驗與討論

4.1 數據集及比較方法

實驗在兩類不同的真實動作序列共6 個數據集上進行。一類是視頻序列，包括Weizmann(Weiz)、Keck 和UT-Interaction (UT-I)[22]。其中Weiz 和UT-I 是人體動作序列，Keck 是手勢動作序列。與文獻[22]一樣，提取HoG 特征作為這些序列的輸入數據。另一類來自 CMU Mocap database 86 號運動捕獲序列數據[23]。這些運動序列主要由各個關節附著傳感器的人在一定時間內做出不同的動作而生成，共14 組。選取其中的第1、2、3 組，記作：mo-1、mo-2、mo-3。這些數據集信息如表1 所示。

表1 實驗數據集信息Table 1 Characteristics of datasets

為了比較不同方法動作分割的效果，與TSC、TLRSC、SC-NMF、TW-FINCH 等基于聚類的動作分割方法進行比較。其中：TSC 和TLRSC 是基于SC 的動作分割方法；SC-NMF 是基于Semi-NMF 的方法，它在低維表示過程中引入了q個結構近鄰構造的約束項，再生成一個k 近鄰圖用于動作分割；TW-FINCH 是一個基于層次聚類的動作分割方法。

實驗的參數分別根據文獻的推薦進行設置。其中MGSeNMF 與SC-NMF 一樣，設置Weiz、Keck、UT-I 的特征維數為60，mo-1、mo-2、mo-3的特征維數為15； α取值范圍[0.001, 0.01, 0.1, 1,10, 100, 1 000]。 MGSeNMF 設置q取值范圍[1,2,3, 4, 5, 6, 8, 10]，k與q相同。SC-NMF 中q的取值與文獻保持一致，為MGSeNMF 中q的2 倍。所有方法獲取最優結果作為輸出。評價指標采用標準的ACC和NMI進行衡量[24-25]。

4.2 動作分割結果比較

表2 和表3 所示是不同方法動作分割的ACC和NMI 性能比較。可以看到，MGSeNMF 在大多數數據集上都獲得了更好的動作分割效果，特別是在3 個視頻序列數據集上性能提升效果明顯；在mo-1 和mo-3 上，MGSeNMF 也可以獲得最好的ACC 和NMI 值，在mo-2 上稍差于SC-NMF。

表2 不同方法的ACC 性能比較Table 2 ACC comparison with different methods

表3 不同方法的NMI 性能比較Table 3 NMI comparison with different methods

為進一步分析動作分割效果，圖1～6 所示為不同方法的最終動作分割結果（不同顏色表示不同的動作片段）比較，其中GND 表示數據集的標準結果。

圖1 Weiz 數據集上的動作分割結果Fig. 1 The action segmentation yielded on Weiz

圖2 Keck 數據集上的動作分割結果Fig. 2 The action segmentation yielded on Keck

圖3 UT-I 數據集上的動作分割結果Fig. 3 The action segmentation yielded on UT-I

圖4 mo-1 數據集上的動作分割結果Fig. 4 The action segmentation yielded on mo-1

圖5 mo-2 數據集上的動作分割結果Fig. 5 The action segmentation yielded on mo-2

圖6 mo-3 數據集上的動作分割結果Fig. 6 The action segmentation yielded on mo-3

可以看到，與其他方法相比，MGSeNMF 與SC-NMF 基本都可以保持動作序列內部的一致歸屬。它們的主要區別在于動作邊界處的分割結果。由于MGSeNMF 引入k 近鄰圖信息，在保持有效近鄰關系的同時，弱化了結構近鄰圖的強制性約束，從而可以在動作邊界處實現更客觀準確的分割。如在Weiz 數據集上，雖然MGSeNMF 將動作3 的結束部分劃分到動作5，但是主要動作之間的邊界都是清晰的， 與標準分割一致，沒有出現如SC-NMF 那樣將動作7 的結束和動作8 的開始分割為一個獨立新動作之類的錯誤。Keck數據集上，動作1 和動作2、動作9 和動作10 之間的分割更接近標準。可見利用多圖融合信息，MGSeNMF 在確保動作片段內一致歸屬的同時，邊界處的準確分割得到了進一步增強，從而使得動作分割的準確性得到了進一步提升。

4.3 參數分析

MGSeNMF 中參數k和q分別描述兩種相似圖中近鄰的個數，實驗取值在[1，2，3，4，5，6，8，10，12，15，20]范圍內，如圖7～12 所示為不同取值下的NMI 性能。可以看到，同時增大k和q，NMI 性能在Weiz、Keck、UT-I、mo-3 上提升明顯，說明引入較多的結構近鄰節點，可以更有效約束動作序列結構近鄰之間表示盡可能的一致，從而確保動作片段內部歸屬到相同類。同時需要注意到，過大的q仍意味著會將不同動作邊界處的數據幀建立高相似性關系，從而導致錯誤分割。如當q=20時，NMI 性能在Weiz、Keck、UT-I、mo-1、mo-3 上下降明顯，在其他數據集上也有下降，因此q的選擇不能過大。同理對于k的取值，和文獻[14]所得結論一樣，過大的k也將導致性能的下降，因此對k的討論本文不再贅述。

圖7 Weiz 數據集上不同q 和k 下的NMI 值Fig. 7 The NMI with different q and k on Weiz

圖8 Keck 數據集上不同q 和k 下的NMI 值Fig. 8 The NMI with different q and k on Keck

圖9 UT-I 數據集上不同q 和k 下的NMI 值Fig. 9 The NMI with different q and k on UT-I

圖10 mo-1 數據集上不同q 和k 下的NMI 值Fig. 10 The NMI with different q and k on mo-1

圖11 mo-2 數據集上不同q 和k 下的NMI 值Fig. 11 The NMI with different q and k on mo-2

圖12 mo-3 數據集上不同q 和k 下的NMI 值Fig. 12 The NMI with different q and k on mo-3

MGSeNMF 中參數 α描述了多圖融合約束項在優化目標中的權重。固定其他參數，設置 α取值[0.001, 0.01, 0.1, 1, 10,100, 1 000]，以Weiz 和mo-1 為例，圖13～14 所示為不同 α取值下的ACC和NMI 值。可以看到，在Weiz 數據集上，當α ≤1時，ACC 和NMI 提升明顯，之后略有下降；與之相反，在mo-1 數據集上，當α ≥0.1時，ACC和NMI 下降明顯。這是因為對于Weiz 之類的高維數據而言，需要較大的 α值來提升多圖融合約束項在整個優化模型中的權重；反之對于mo-1 等數據而言，由于原始數據特征維數相對較小，因此需要較小的 α值來調節多圖融合約束項在優化模型中的權重。

圖13 Weiz 數據集上ACC 和NMI 值隨 α變化情況Fig. 13 The ACC and NMI with different set of α on Weiz

圖14 mo-1 數據集上ACC 和NMI 值隨 α變化情況Fig. 14 The ACC and NMI with different set of α on mo-1

4.4 運行時間分析

表4 為不同方法所需時間的統計。可以看到，TW-FINCH 所需時間最少，SC-NMF 方法最耗時，TLRSC 次之。結合前述分割性能分析可以看到，在整體上取得更好分割準確性的情況下，MGSeNMF 運行所需時間大大縮小，運行效率明顯提升。這說明雖然增加了一個圖約束，但是MGSeNMF 的多圖融合約束項設計采用L2范數，計算比SC-NMF 中的L2,1更高效，因此MGSeNMF整體計算效率更高。特別是隨著數據量的增大，MGSeNMF 運行效率更具優勢。

表4 不同方法的運行時間比較Table 4 The comparison of the running time with different methodss

5 結束語

針對當前基于聚類的動作分割方法常采用結構相似性約束易導致邊界上的錯誤而造成動作分割不準確的問題，提出了一種融合結構相似性和度量相似性的基于多圖融合約束Semi-NMF 的動作分割方法MGSeNMF。該方法主要在特征表示學習中，利用不同權重的相似性關系圖融合約束實現序列的降維，從而確保了后續獲得更好的序列關系圖表示和更準確的動作分割。實驗表明該方法可以有效提升動作分割的準確性，特別是在視頻序列中，平均精度較第二名方法SC-NMF 提升了近4%；并且在準確性得到提高的同時，運行效率明顯提升，與SC-NMF 相比，總的運行時間縮短了近一個數量級。下一步，針對自動設置最優近鄰個數，更準確確定動作邊界以及運用多模態數據實現更優動作分割等問題持續開展研究。