模型假設權重的三維運動分割

賴桃桃，郭磊，林舒源，李佐勇

（1.閩江學院 計算機與控制工程學院，福建 福州 350108；2.福建省茶產業大數據應用與智能化重點實驗室，武夷學院，福建 武夷山 354300；3.暨南大學 信息科學技術學院/網絡空間安全學院，廣東 廣州 510632）

運動分割是計算機視覺領域的一個重要課題，它可以為視頻監控、行為識別等視覺應用提供有效的預處理。運動分割的目標是根據運動物體的運動模式，把屬于不同運動物體的特征點分成不同的類。即運動分割算法接收一組特征點作為輸入，然后將它們分配到若干個運動物體組中作為輸出。近年來，研究人員提出了許多運動分割算法，主要可以分為兩類：基于兩幀的方法和基于多幀的方法[1-2]。

相比于基于兩幀的方法，基于多幀的方法能有效地使用視頻序列中所有幀的運動信息進行運動分割，因此通常能獲得較高的分割精度。基于多幀的方法把運動分割歸結為聚類問題：它們先計算特征點對之間的距離矩陣，然后在該矩陣上進行聚類從而把特征點分割成不同的類。基于多幀的方法又可以分為兩類[3]：基于子空間 (subspace-based) 的方法和基于仿射(affinity-based)的方法。基于子空間的方法，比如SSC(sparse subspace clustering)，直接利用特征點的坐標信息來計算特征點對之間的距離。相比之下，基于仿射的方法先用特征點的坐標信息來估計模型假設，然后用估計的模型假設來計算特征點對之間的距離。

雖然基于子空間的方法能在不包含特征點丟失的Hopkins 155 數據集[5]上獲得不錯的分割結果，但是這些方法在包含特征點丟失的真實數據集（如KT3DMoSeg[6]）上獲得的分割結果較差。因為真實數據集中的視頻的目標被遮擋時，被遮擋目標的部分特征點會丟失。因此，這些方法需要使用一種數據填充技術恢復丟失的數據，但并不能保證丟失的數據能夠完全被恢復。實驗結果顯示，盡管基于子空間的方法使用了數據填充技術，但是這些方法在分割包含特征點丟失的真實數據集時的性能顯著變差。

相比之下，基于仿射的方法對包含特征點丟失的真實數據集不太敏感，這主要歸功于它們只需要特征點對在視頻中的兩幀而非所有幀中可見，即可計算特征點對之間的距離。Li 等[2]的實驗結果顯示，基于仿射的方法在分割包含特征點丟失的真實數據集上能獲得較高的準確率。然而，Jung 等[1]的方法存在一個主要缺陷，即需要預先知道運動物體的數量，這在實際中是不現實的。雖然Li 等[2]的方法可以估計運動物體的數量，但它的計算成本非常高。因此，它很難應用于實際場景中。在較少的采樣次數下，為提高采樣到有效模型假設的概率，Dragon 等[3]中的方法使用低階單應矩陣來近似高階基礎矩陣。但是，在復雜場景中，單應矩陣不能很好地近似基礎矩陣，導致該方法在挑戰數據集（比如KT3DMoSeg）上得到的分割精度較低。

針對上述運動分割方法的優缺點，Lai 等[7]提出了一種基于稀疏仿射的運動分割方法(motion segmentation via a sparsity constraint,MSSC)。在MSSC中，首先提出一個簡單有效的累加策略。該策略簡單地累加一個視頻序列中所有連續幀對的距離矩陣來有效地構建一個距離矩陣。其次，在距離矩陣上使用信息理論原理來構建稀疏仿射（距離）矩陣。根據實驗結果表明，在上述稀疏距離矩陣上進行運動分割，MSSC 在挑戰數據集上的分割準確率得到顯著的提高。然而Xu 等[6]發現，在更具挑戰性的包含強透視和強前向平移（strong perspectives and strong forward translations）數據集KT3DMoSeg 上，已有的只使用一種幾何模型的基于仿射的方法，包括MSSC，都不能達到較滿意的分割準確率。于是，他們提出一種同時使用三種幾何模型（即affinity matrix、homography matrix和fundamental matrix）的Subset 方法。

Lin 等[8]將每個連續幀對之間的距離矩陣都視為等價，而忽略它們對運動分割的不同貢獻。換句話說，由更優的模型假設計算得到的距離矩陣應該賦予更大的權重。因此，提出了一種基于加權距離矩陣的運動分割方法。進一步發現，并非所有的模型假設都是有意義的，通過選擇有意義的模型假設并根據其權重來加權距離矩陣，能進一步提升運動分割的性能。

1 算法描述

算法主要由以下三個步驟組成：（1）先為視頻序列中的每個連續幀對生成三種幾何模型假設，然后用生成的模型假設為每個連續幀對構建初始仿射矩陣；（2）計算每個連續幀對中模型假設的權重，并通過信息理論來選擇有意義的模型假設，以及用它們的權重計算初始仿射矩陣的權重；（3）將上述權重乘以初始仿射矩陣得到該圖像對的仿射矩陣，然后累加所有連續幀對的仿射矩陣，得到該視頻序列的仿射矩陣。在仿射矩陣上用聚類方法把屬于不同運動物體的特征點聚成不同的類。

1.1 初始仿射矩陣的構建

假定一個視頻序列由F 幀組成，并記第f 幀和第（f+1）幀為第f 個連續幀對，其特征點對記為，其中n 為跟蹤的特征點個數且f∈[1,F-1][6，8]。采樣隨機采樣為affinity matrix、homography matrix 和fundamental matrix 三種幾何模型分別生成m 個數據子集，然后使用直接線性變換[9]分別生成m 個模型假設。

接著為每種幾何模型構建相應的初始仿射矩陣。不失一般性，以affinity matrix 為例，下文描述如何為其構建初始仿射矩陣。

1.2 初始仿射矩陣權重的計算

第f 個連續幀對的第i 個模型假設的權重記為wi[8，10]。計算第f 個連續幀對的所有m 個模型假設的權重并記為Wf=[w1,w2,…,wm]。用信息理論原理選擇有意義的模型假設。

首先，Wf中最大元素和Wf第l 個元素的間隔計算(在這之前對wi進行了歸一化)為

其次，計算ηl的概率，即

然后，Wf的熵計算如下

接著，用Ef清除Wf中較小的值，具體操作如下

經過上述操作后，Wf中值較小的權重被清除。把Wf中值的和作為第f 個連續幀對初始仿射矩陣的權重。三種幾何模型第f 個連續幀對的初始仿射矩陣的權重分別記為。

1.3 加權仿射矩陣的構建

在上述兩步計算獲得初始仿射矩陣及其權重后，可以得到該視頻序列的最終仿射矩陣，其計算如下。首先，如文獻[6-8]，使用公式(2)至(5)對第一步獲得的初始仿射矩陣，和進行稀疏化得到稀疏仿射矩陣，分別記為。然后，通過累加所有連續幀對的加權仿射矩陣得到該視頻序列的最終仿射矩陣。

最后，在上述仿射矩陣上用聚類方法[7-8]把屬于不同運動物體的特征點聚成不同的類，從而完成運動分割。

2 實驗結果與分析

在來自KITTI 數據集[11]的挑戰性KT3DMoSeg 數據集[8]上進行實驗。KT3DMoSeg 共有22 個具有強透視和強前向平移的戶外視頻序列。每個視頻序列包含2到5 個運動物體。這增加了運動分割的難度和復雜度。采用聚類錯誤率來評價算法性能[6-8]，其計算式為：

聚類錯誤率越低，算法的性能越好。

該方法與九種運動分割方法作比較：包括GPCA[12]，LSA[13]，ALC[14]，BDR[15]，SSC[4]，SUBSET[6]，MCMS[16]，NCRS[17]和HMFMS[8]。運行提出的方法和HMFMS 二十次，并報告其均值和中值。在算法的實現中，為了公平起見，與[6，8]相同的參數，為其設置相同的值，具體見表1。

表1 所提出方法的參數及其值Tab.1 Parameters of the proposed method,and their values

在初始仿射矩陣的構建時，提出的方法和HMFMS 使用相同的隨機生成的模型假設。其他對比方法（包括GPCA、LSA、ALC、BDR、SSC、SUBSET、MCMS和NCRS）的結果[8]。所有方法的結果見表2 和圖1。

圖1 所提出方法在KT3DMoSeg 數據集上的分割示例Fig.1 examples of segmenting results obtained by the proposed method on KT3DMoSeg

表2 十個方法在KT3DMoSeg 數據集上獲得的聚類錯誤率的均值和中值（最好的結果加粗）Tab.2 Mean and median of clustering errors obtained by ten methods on KT3DMoSeg dataset (best results bold)

提出的方法通過信息理論來選擇有意義的模型假設，并用有意義的模型假設而不是所有模型假設的權重來計算初始仿射矩陣的權重。提出的方法接著由初始仿射矩陣和上述權重得到該圖像對的仿射矩陣；最后，累加所有圖像對的仿射矩陣得到該視頻序列的仿射矩陣，并在仿射矩陣上用聚類方法把屬于不同運動物體的特征點聚成不同的類。表2 結果顯示，通過上述操作，提出的方法獲得最低的聚類錯誤均值和中值。這表明，選取有意義的模型假設的權重來構建仿射矩陣是有效的。圖1 顯示提出的方法成功地分割六個視頻序列中的不同運動體。

然而，使用隨機采樣方法來生成有意義模型假設并不理想。HMFMS 使用所有假設的權重給相應的仿射矩陣計算權重，也有效地提高分割準確率。HMFMS獲得第二低的聚類錯誤均值和中值，其錯誤率顯著地低于SUBSET 的。MCMS、NCRS 和SUBSET 分別獲得第三、第四和第五低的錯誤率，它們的錯誤率均值都小于10%。因為GPCA、LSA、ALC、BDR 和SSC 不能直接處理包含缺失數據的視頻序列，所以在處理包含缺失數據的視頻序列時，這些方法需要先使用數據填充技術：填充丟失數據，然后在填充后的數據上進行運動分割[18]。不過，這類方法獲得的聚類錯誤均值都較高，其值遠高于基于模型擬合的方法獲得的值。這表明，基于模型擬合的方法在處理包含缺失數據的視頻序列上有獨特的優勢。

3 研究結論與展望

使用有意義的模型假設而不是所有模型假設的權重來構建仿射矩陣。這有效地提高運動分割準確率。然而，使用隨機采樣方法來生成有意義模型假設并不理想，因此Lai 等[19-22]提出許多數據采樣方法，這類方法能更有效地生成有意義模型假設。嘗試直接把提出的方法中使用的隨機采樣替換成指導性采樣，但并不能提高分割準確率，反而會降低準確率。這是因為在計算相關系數時，僅使用了十分之一模型假設的索引而使用指導性采樣時有意義模型假設可能遠不止十分之一，這使得計算得到的相關系數更沒區分能力。因此，如何使用指導性采方法采樣更多有意義模型假設來構建有效仿射矩陣還有待深入研究。