博弈選擇模型在步態識別中的應用研究

柴艷妹，韓文英，王 堅，王友衛

中央財經大學 信息學院，北京 100081

1 引言

近年來，基于信息融合理論的生物特征識別算法已成為該領域最為活躍的研究方向之一。與單特征算法相比，多特征融合可以提供關于被測對象更為全面、完整的信息，從而有效提高識別算法的準確率。以步態識別為例，當前典型的特征融合算法包括四類：靜態特征和動態特征的融合；非結構特征和結構特征的融合；多視角特征的融合[1]；多模態特征的融合[2]。其實無論哪種類型的融合，都需要對不同信源的特征進行甄選，既要保證不同類型特征之間的互補性，也需要考慮同類特征之間的冗余性。但從目前發表的文獻來看，為了進一步提升識別性能，大多數的研究工作仍著眼于嘗試新的特征提取算法和新的融合機制。例如Ahmed等人[3]提出用關節相對距離（JRD）和關節相對角度（JRA）作為步態特征，并用遺傳算法度量它們之間的相關性，進行了決策級融合；Triloka等人[4]則構建了一個基于多層負反饋的神經網絡系統，將肌電圖信號和視頻采集到的小腿神經肌肉信號進行融合，用以分類；孫楠等[5]采用改進的粒子群優化MPSO-BP神經網絡方法識別不同運動模式下的人體步態相位，也取得了較好的識別效果。這些新的特征提取算法和融合機制往往需要使用更復雜的技術和架構，甚至耗費更多的算力來換取識別率上的些許提高。事實上，這方面的研究已遇到瓶頸。

目前，很少有人嘗試從特征選擇的角度來研究這個問題，即如何在眾多已有的類似特征中選擇出最優的特征組合進行融合，從而提高識別性能。特征選擇作為一種數據處理手段近年來被廣泛研究，并應用到了各行各業中。在早期的研究中，各種度量手段作為評估函數被應用到特征選擇算法，如信息論度量、關聯度量、一致性度量、距離度量和依賴性度量等。典型的算法如Yu等人[6]2004年提出的FCBF方法，使用了信息論中的對稱不確定性來衡量兩個特征的相關性，并結合Markov blanket技術刪除冗余特征；Peng等人[7]2005年提出的mRMR方法，利用互信息理論來兼顧特征和類別之間的相關性以及特征之間的冗余性。這類方法在考慮冗余問題時，都是計算成對特征的冗余性，而沒有考慮到特征加入或刪除后特征子集組合效應的變化。因此，近年的研究中特征的組合效應越來越被重視。例如，Dong等人[8]使用進化算法，楊曇等人[9]使用群體智能，段潔等人[10]提出基于粗糙集依賴來度量特征子集的組合效應；而Sun等人[11-12]也將合作博弈理論中的班次哈弗權利指數以及夏普利值運用到特征選擇方法中，用以評估特征在整個子集中的組合影響力。但這類方法在構建候選子集時復雜度高，需付出大量的時間代價。

在多源信息融合中，信源間的差異性是普遍存在的。因此，不同信源間不但有互補關系，也存在冗余和沖突。以一個靜態特征和動態特征的步態融合為例，靜態特征可選取人體形狀的描述，比如身高、體寬、緊致度、矩形度和伸長度等；而動態特征則可以選取身體各部位的動態時變信號，比如區域面積和區域方差等。一方面，同類特征之間有較大的冗余性，如果將這些特征全部進行融合會使樣本集特征空間維數過大，并且造成噪聲的二次引入，從而影響識別的效率和精度；另一方面，異類特征之間不僅具有互補性，也可能存在潛在的沖突，例如身體各部位的區域面積特征實際上也蘊含著被測對象的身高和體寬等信息。這些沖突關系也可能會影響融合算法在步態識別中的處理性能。

從上述分析來看，由于傳統特征選擇方法在構建候選子集時復雜度高，需付出大量的時間代價，因此很少有人考慮將其運用到多生物特征融合的識別領域。然而，步態特征融合過程中存在的不僅僅是選擇特征的問題，更重要的是如何解決特征之間的合作和沖突。博弈論是一門完整的決策理論，主要研究在多個參與者參與的對抗性或合作性活動中，博弈的參與者應采取何種合理的策略，以取得有利的個人利益或聯盟的集體利益。將博弈論和信息融合理論相結合是新的嘗試，本文構建了新的博弈特征選擇模型，通過定義支付函數大大降低了選擇最優特征組合的計算量。下文將詳細描述博弈選擇特征模型的構建和求解方法，最后用步態識別的示例和實驗驗證模型的有效性。

2 博弈特征選擇模型

博弈論模型是從人類社會的政治、經濟、軍事等活動中抽象出來的一種數學模型。從19世紀發展至今，它形成了很多種分類，如技能博弈、自然博弈以及策略型博弈等。和步態融合問題比較吻合的是策略型博弈模型。

2.1 策略型博弈模型

構成策略型博弈模型的三要素是局中人、策略和支付函數。

定義1局中人指參與博弈的對象，可以是兩個或多個，記為Pi。所有局中人構成的集合稱為局中人集合，記為，其中N是參與人或局中人的個數。

定義2策略指局中人所選擇的行動。用sj(j∈n)表示局中人Pi所擁有的n個策略中的某一個，則局中人Pi的所有策略的集合稱為該局中人的策略集，記為Si(i∈N)。

定義3支付函數指局中人Pi的定義在策略組合集合S上、取值于實數空間R的一個函數，記為ui()s，用以描寫局中人Pi在策略組合s∈S之下所獲得的某種收益或所遭受的某種損失。

定義4當以上三種要素都已明確，那么就可以用表示一個策略型博弈模型。在策略型博弈模型中，如果每個局中人對于N,S1,S2,…,SN,u1,u2,…,un都了解，那么該模型是信息完全的。如果N個局中人同時選擇策略，那么該模型是靜態的。

定義5設為一完全信息的靜態博弈模型，稱策略組合，并且為一個納什均衡。如果對?i∈N ，是在條件下局中人Pi的最優選擇，即

2.2 構建步態融合中的博弈選擇模型

根據博弈論思想，在進行步態融合特征選擇時可以將存在冗余和互補關系的特征空間中的特征選擇看作是步態特征間的博弈問題。博弈的目標是在眾多同類和異類特征中找到最佳的特征組合用于融合分類，從而提高步態識別的算法性能。

2.2.1 局中人設計

在博弈特征選擇模型中，可以把同類的、具有冗余關系的步態特征定義為同一個局中人，把異類的、具有互補關系的步態特征定義為不同的局中人。例如，動態步態特征和靜態步態特征可分別定義成局中人P1和局中人P2。

2.2.2 策略設計

第Pi個局中人的某個策略sj可以定義成具有冗余關系的同類特征中的某一個特征。因此，該類特征（即局中人Pi）的策略集為Si={ }s1,s2,…,sn，其中n為第i個局中人所擁有的特征個數。

2.2.3 支付函數設計

支付函數在博弈模型中起著至關重要的作用，它是計算博弈局中人收益、構建博弈矩陣進而求取均衡解的基礎。因此，支付函數的準確程度關系到博弈結果的準確程度。在信息融合系統中，單信源所提供特征往往是不完整或不精確的；多信源特征或許可提供互補信息，但也可能提供不同置信度的冗余信息，甚至是矛盾或沖突信息。融合系統不得不依據這些具有不確定性的信息進行推理，以達到決策和控制功能。在步態特征的博弈選擇模型中，支付函數值應能反映出局中人的沖突關系和分類能力，并能對其進行可信度量。信息論中的熵作為不確定性度量，有著其他方法無法比擬的優勢。

（1）信息熵：對于在給定論域上的隨機變量X，其概率分布為，則：

其中，k是一個取決于度量單位正常數。信息熵表征了信源整體的統計特征，是總體的平均不確定性的度量。

（2）條件熵：用來表示二維概率系統中，在已知一個隨機變量情況下，對另一個隨機變量不確定性的度量，公式如下：

條件熵又稱信道疑義度，當隨機變量X和Y分別表示信息傳遞系統中的輸入變量和輸出變量時，H(Y|X)表示在輸出端接收到信息Y后，對輸入變量X尚存的平均不確定性，即，條件熵描述了輸入信號和輸出信號之間的依賴關系。

（3）平均互信息：由于事物之間的相互聯系，使得在已知隨機變量Y的情況下，對X的平均不確定性的消除程度可用平均互信息來表示。

在博弈選擇模型中，支付函數的設計首先應能表現出局中人之間的對立統一關系；其次要能區分出不同策略的分類能力，分類能力強的策略支付值大。因此，本文利用信息熵表示策略分類能力的大小，采用平均互信息表示信源間的沖突。其中，H(X)和H(Y )分別表示特征X和Y的信息熵，即局中人選取某一特征進行融合時，這一策略對系統正確分類的能力。平均互信息I(C ;X )表示在已知特征X的情況下，對分類信息C的平均不確定性的消除程度，即特征X對分類C的可信度。則特征X和Y可信度之間的沖突可以用[I(C:X)-I(C:Y)]表示。構造的支付函數如下：

3 博弈選擇模型在步態融合中的應用示例

經過多年的研究和發展，步態識別領域已積累了大量特征提取算法。為了驗證上述模型的有效性，示例特征的選取既要考慮同類特征間的冗余性，也考慮異類特征間的互補性。因此，本文將以3個經典的人體輪廓描述特征（緊致度、矩形度和伸長度）和2個動態區域描述特征（區域方差和區域面積）為例進行實驗。

3.1 特征提取

人體輪廓是步態識別的重要特征之一，也是現實生活中人類視覺系統識別人的主要依據。描述人體整體輪廓的方法有很多種，這里引用了3種較常用的特征[13]。

（1）緊致度

緊致度是抽象代數的概念，其中，L表示輪廓周長，A表示輪廓的面積。在靜止狀態下，緊致度在一定程度上反映了人的高矮胖瘦等物理形態，而人在行走的時候骨骼和肌肉的變化也是會反映到輪廓上來的。因此，一個輪廓序列的緊致度是可以表達人體的步態特征的。

（2）矩形度

矩形度是輪廓與其外接矩形的面積之比，其中，H表示輪廓的高度，W表示輪廓的寬度，A表示輪廓面積。它反映了人在行走時，其相對于外接矩形的松緊程度，間接反映了人走路時的步幅和步距。

（3）伸長度

其中，H表示輪廓的高度，W表示輪廓的寬度。事實上，輪廓的高度和寬度隱含了目標的高矮胖瘦信息。但是這兩個參數常常隨著攝像機拍攝距離的變化而變化。例如，同樣焦距下，一個高個子目標由于拍攝距離較遠會顯得比近處的矮個子目標還要矮小。寬度所代表的胖瘦信息也是如此。因此，它們都不可以單獨作為形體特征來進行步態識別。為了消除這種誤差，可用伸長度來描述人體的輪廓特征。

僅以人體輪廓作為步態特征，粒度過大。據觀察，人在走路過程中，身體不同部位的運動特征是不一樣的，為了捕捉這種差異，可以提取身體不同部位的步態特征。為此，可先將人體側影按照身體比例劃分為頭、身體和腿3個區域（見圖1），然后分別計算不同身體部位在走路過程中的方差和面積變化特征[14]。

圖1 人體區域分割比例圖

（4）區域面積

其中，R1表示頭部，R2表示軀干，R3表示腿部，fk(i,j)代表某個區域(k=1,2,3)中位置(i,j)處的像素值，且f(i,j)∈{0,1}。由于區域是固定的，因此當身體某一部分在走路過程中有較大幅度運動時，前后幾幀圖像在該區域中呈現出來的目標面積會隨之改變，從而體現出步態的運動特征。

（5）區域方差

3.2 博弈選擇模型

這里選用的特征既有明顯的互補性，也有暗藏的冗余和沖突性。緊致度、矩形度和伸長度都是對人體輪廓的整體描述，使用了寬度W、高度H和面積A等信息，特征之間具有較大的冗余性，可以歸為一類；而區域面積和區域方差反映的則是步態的運動特征，它們的計算很類似，特征之間也具有較大的冗余性，可以歸為另一類。同時，兩類特征一個是對步態的靜態描述，粒度較粗；另一個是對步態動態特征的描述，粒度較細，它們之間存在明顯的互補性，因此可用于特征融合算法，以提高識別性能。但是如果將五類特征直接進行融合，會使樣本集特征空間維數過大，并且冗余特征會造成噪聲的二次引入，從而影響識別的效率和精度。另一方面，這兩類特征之間不僅具有互補性，也可能存在潛在的沖突，例如身體各部位的區域面積特征實際上也蘊含著被測對象的身高、體寬和面積等信息。這些沖突關系也可能會影響融合算法在步態識別中的處理性能，因此，如何在不用窮舉的情況下，找到最佳的融合特征組合正是本文研究的目標。

（1）局中人

把同類的、具有冗余關系的步態特征定義為同一個局中人；把異類的、具有互補關系的步態特征定義為另一個局中人。即局中人P1用來描述細粒度的動態區域特征，而局中人P2則用來描述粗粒度的人體輪廓特征。

（2）策略

S1={區域面積，區域方差}用來描述局中人P1所能采取的策略；S2={緊致度，矩形度，伸長度}用來描述局中人P2所能采取的策略。

（3）支付函數

（4）均衡點求解

為了選擇最佳策略，局中人可使用極大化極小原理（即行的最小值和列的最大值），也就是說，選擇包含著最壞的可能結果中的最佳答案，這樣就可保證收益不會低于一個確定的值——極小中的極大值。當然行局中人和列局中人都可采用這個方法，但它們選擇的策略可能一致，也可能不一致；如果它們一致，那么這個博弈就有均衡點，即最優解。如果它們不一致，這個博弈沒有均衡點，即純優策略不存在。這時可以根據實際應用情況給各策略分配一個概率值，即求取極小化極大混合策略的值。關于博弈矩陣的均衡點求解問題可參看文獻[15]。

4 實驗結果分析

4.1 實驗數據庫

采用兩個國際上通用的步態數據庫進行實驗，它們分別涵蓋了數據庫的室內/室外、快走/慢走以及數據規模大/小等因素對自動步態識別的影響。

（1）Carnegie Mellon University（CMU）數據集：由25個人組成，分快走、慢走、傾斜和抱球4種方式。本文分別實驗了快走和慢走兩種方式的側視序列，每個序列7～8個步態循環。室內拍攝，人離攝像機較近。

（2）中科院CASIA Dataset B：有124個受測者，分別考慮了視角、衣服和帶物3種情況的變化，所有視頻均是在室外的遠距離拍攝。本文實驗了107個受測者“e090”視角的步態序列。實驗所用數據示例圖，如圖2所示。

圖2 實驗數據示例圖

4.2 實驗方案

為了驗證博弈選擇模型的有效性，設計如下實驗方案：

（1）首先根據3.2節所述方法求取支付函數矩陣；

（2）利用極大化極小原理求解均衡點，均衡點所在位置，即最佳融合策略；

（3）分別在CMU數據庫和CASIA數據庫上對所有特征進行窮舉組合，并利用特征級融合方法得到其融合識別結果；

（4）對比實驗結果，判斷博弈選擇模型得到的最佳組合是否具有最好的識別結果。

在特征提取之前，CMU數據庫和CASIA數據庫中的圖像都經過了二值化、模板提取和周期性分析等預處理，并采用最近鄰分類器（NN）進行模式分類。由于步態數據具有周期性、循環性的特征，相似性度量則采用基于周期的算法，具體做法見文獻[16]。分類性能的評價采用模式識別領域常見的累計匹配分值（CMS）和相關操作特征（ROC）曲線。

4.3 最佳融合策略

對于CMU數據庫，將數據庫中每個樣本序列按照步態周期拆分為若干子序列（每個快步走序列大約包含8個步態周期，每個慢步走序列大約包含7個步態周期），再每人隨機抽取一個步態周期作為訓練集，其余步態周期序列作為測試集，來進行步態識別。首先，分別計算5類特征單獨作為步態特征進行識別時得到每一類別的條件概率。然后，再根據博弈選擇模型支付函數的計算方法，計算其支付矩陣。進一步，利用極大化極小原理（即行的最小值和列的最大值）找到博弈矩陣的均衡點。

可以看出，兩個矩陣的均衡點均在x1y3處，即局中人取“區域面積”，局中人2取“伸長度”的位置。也就是說，按照博弈選擇模型，在CMU數據庫中將“區域面積”和“伸長度”進行特征融合，可取得最優的融合效果。

而對于CASIA數據庫的“e090”視角數據集，也可采用同樣的周期拆分處理方法，隨機抽取107個子序列作為訓練集，剩余的535個子序列作為測試集，來進行步態識別。采用和CMU數據庫上同樣的算法，計算支付函數，并利用極大化極小原理找到博弈矩陣的均衡點。

可以看出，在CASIA數據庫上的支付矩陣也找到了博弈均衡點，該均衡點在x2y2處，即選取“區域方差”和“矩形度”特征進行融合，可取得最優的融合效果。

4.4 實驗結果比較

為了驗證該方法的有效性，本文對局中人1和局中人2的策略進行了窮舉法融合，并給出了特征集融合方法下的平均識別率進行對比。實驗結果如表1～3所示。

4.5 實驗結論及分析

對實驗結果進行深入分析，本文得到以下結論：

（1）從表1和表2中最近鄰分類器的識別率來看，在CMU數據庫中的快走和慢走數據集上取得了一致的實驗結果，即“區域面積+矩形度”和“區域面積+伸長度”均得到了較高的識別率。再仔細觀察圖3（a）可以發現，CMU快走數據集上在CMS橫坐標約為7的位置，“區域面積+伸長度”的識別性能略有優勢，因此進一步評價了CMS取10以內的平均識別率，發現CMU快走數據集上“區域面積+伸長度”更優一些，而在CMU慢走數據集上兩者基本持平（見圖4）。這和博弈選擇模型得到的結論基本一致。

（2）從表3中最近鄰分類器的識別率來看，“區域方差+矩形度”和“區域方差+伸長度”均取得了較高的識別率。再進一步通過CMS取5以內的平均識別率，可以發現“區域方差+矩形度”的識別性能更好一些，而圖5（b）中ROC曲線也證明了這一結論。這和博弈選擇模型的結論也是一致的。

表1 CMU快走數據集上的實驗結果比較

表2 CMU慢走數據集上的實驗結果比較

表3 CASIA數據集上各融合策略的融合結果比較

圖3 CMU快走數據集的識別校驗性能曲線

圖4 CMU慢走數據集的識別校驗性能曲線

圖5 CASIA e090數據集的識別校驗性能曲線

（3）從上述分析來看，可以肯定本文提出的博弈選擇模型是行之有效的。進一步綜合分析表1～3的實驗結果發現，“矩形度”和“伸長度”這兩個特征分類性能極為類似，且結果較“緊致度”要好很多，因此，局中人2選“矩形度”或“伸長度”都可以。而“區域面積”和“區域方差”的分類性能在不同的數據庫上各有優勢，使用博弈選擇模型可將其有效選出。

（5）本文所設計的18個實驗不僅涵蓋了室內/室外不同的應用場景，還測試了快走/慢走不同的目標情況，并在樣本規模不同的兩個數據庫上進行了實驗。從表1～3的實驗結果來看，本文結論對不同場景和不同目標均有較好的普適應。

5 結論

本文最大的特點是從特征選擇的角度，通過引入博弈論來解決步態特征融合過程中的特征合作和沖突問題。在多特征組成的特征空間中，把具有冗余關系的特征定義為博弈過程中的同一個局中人，具有互補關系的特征定義為另一個局中人。利用信息論中的信息熵和互信息構建了支付函數，使其能表現局中人之間的可信度沖突關系。使用極大化極小原理求得博弈矩陣的均衡點，從而得到融合的最佳策略組合。為了驗證該方法的有效性，以冗余度極大且有互補性的3個人體輪廓特征（緊致度、矩形度和伸長度）和2個區域特征（區域方差和區域面積）作為例子進行了實驗。從實驗對比和分析來看，本文提出的博弈選擇模型是行之有效的方法，它可以用較少的計算量得到最優的融合特征組合。但目前所選用的特征都過于簡單，下一步將嘗試此算法在不同視角及不同模態下的普適性及嘗試設計新的博弈支付函數。