基于單應性與相似度矩陣的運動分割

吳驍倫，楊 敏

(南京郵電大學 自動化學院、人工智能學院，江蘇 南京 210023)

0 引 言

運動分割[1]是計算機視覺中最重要的研究領域之一，在機器人技術的許多應用中是一項重要的預處理任務。它已被用作預處理步驟應用在智能交通系統，如視覺監控、動作識別、場景理解等。根據不同的運動模式認知和分離不同的運動物體(如移動的車輛或移動的人)，其中每個移動的物體被識別為一個連貫的實體。

描述這個問題的經典方法如下[2]:給定一組特征點，通過一系列圖像跟蹤，目標是根據它們所屬的不同運動將這些軌跡聚類。假設場景中包含多個物體，它們在三維空間中獨立地移動。傳統的運動分割方法或多或少都會存在一些問題，比如處理高維數據時計算復雜，實時性差，抗噪聲能力差，無法兼容相機運動等等。最近提出了許多運動分割方法，有些已經在一些流行的測試數據集上展示了出色的性能，例如Hopkins155數據集[3-4]。

運動分割方法可以分為基于兩幀[5]和基于多幀[6]的方法。后者由于能夠從視頻序列的所有幀提取運動信息以進行精確的運動分割，所以現在大多算法都運用多幀的方法。一般大致將以前的基于多幀的運動分割方法分為兩類:基于子空間的方法[7-9]和基于相似度矩陣[10-11]的方法?；谧涌臻g的方法利用視頻序列的所有特征點軌跡構造數據矩陣，對不同的運動進行聚類。另一方面，基于相似度的方法是基于特征點軌跡對構造的相似度矩陣來分割不同的運動。盡管在Hopkins155數據集上已經展現了良好的性能，但是在實際應用中，基于子空間的方法可能無法處理一些特殊情況。例如，當運動物體被暫時遮擋時，用基于子空間的方法得出的結果一般不會很理想。在這種情況下，被遮擋的物體的特征點軌跡就會丟失，而基于相似度的方法能有效處理這些問題。例如，稀疏約束的運動分割(MSSC)[12]方法針對這個問題取得了不錯的效果。

在運動分割問題[13]中，多種幾何模型被用來對不同類型的攝像機、場景和運動進行建模。在這個問題上，正如通常所說的那樣，基本矩陣模型通常被認為是適用于不同的情景和不重疊的背景。例如，當場景是全局運動時，基本矩陣被用來描述極上幾何，當場景是平面場景或者運動是純旋轉的時候，單應性是首選。在Hopkins155數據集中，這并不是最主要的問題，因為大多數序列的視場都很小，也許場景距離足夠遠，可以用基本矩陣來近似，基于仿射矩陣或單應矩陣的各種方法所獲得的良好結果驗證了這些想法。

該文旨在利用單應變換與相似度矩陣的優勢在Hopkins155數據集上取得更好的聚類效果，并且能處理一些遮擋問題。

1 單應變換

該文采用的是單應性模型[14]，先進行單應性的計算。單應映射是描述物體在世界坐標系和像素坐標系之間的位置映射關系。單應性模型能夠有很好效果的原因在于單應性假設過程中產生了很多的平面切片，這些在場景中不一定是真實的物理平面，但只要這些虛擬平面屬于相同的剛體運動，顯然就可以用單應性來擬合。這樣的切割在多個真實平面表面的點之間建立了強大的連接，從而產生了一個不會被過度分割的相似度矩陣。如果場景只包含緊湊的物體或分段光滑的結構，那么創建的這種連接足以將剛性運動的各個表面綁定在一起。所以在Hopkins155數據集中，大部分的視頻序列的場景都比較小，運動的物體的結構比較規則，所以用單應性去擬合其數據集中的場景是比較適合的，如圖1所示。

圖1 Hopkins155中的示例

如圖2所示，記m=(x,y,1)T，m'=(x',y',1)T為一對匹配點，映射的形式為：m'=Hm。這是一個齊次坐標的等式，H乘以一個非零的比例因子上述等式仍然成立，即H是一個3×3的齊次矩陣，具有8個未知量。

圖2 單應變換原理

寫成矢量形式為：[m']×(Hm)=0，H稱為單應性。記H為hT，則有Ah=0，其中A為包含圖像點坐標變量的2×9的矩陣，h有九個變量，自由度為8個。

假設已經取得了兩圖像之間的單應，則可單應矩陣H可以將兩幅圖像關聯起來，其中(x,y,1)T表示圖像1中的點，(x',y',1)T表示圖像2中的點，也就是可以通過單應矩陣H將圖像1變換到圖像2。

所以場景中的點都在同一個平面上，可以使用單應矩陣計算像點的匹配點。相機的平移距離相對于場景的深度較小的時候，單應矩陣也比較適用。

2 基于相似度矩陣的運動分割算法

2.1 運動分割的目標

用tfp∈R2表示在F幀中跟蹤P條軌跡的二維坐標的集合，f對應幀，p對應軌跡。在多目標運動分割中，tfp對應于運動的剛體表面上的點。運動分割目標是將軌跡的點按它們所屬的運動分類。換句話說，在下面的數據矩陣中安排坐標，目的就是排列矩陣中的列，使同一個運動物體上的軌跡都能歸屬到同一類，這樣就完成了聚類。

(1)

2.2 假設估計

由上一節所講，單應變換的部分可見H的未知量為8，所以需要至少四對已知的對應點，也就是說在一對幀中抽取4個點。因為模型是四維空間，所以上面的a=4，假設值是通過使用直接線性變換從四個不丟失特征對應的最小子集中估計出來的，并隨機抽取S個假設，θ={θ1,θ2,…,θS}為使用隨機采樣從第f對連續幀生成的假定假設集。

2.3 用有序殘差核計算相關性

有序殘差核(ORK)對嚴重的采樣不平衡有很強的適應能力，這一觀點得到了普遍的認可，所以用有序殘差核來處理各種各樣的場景是一個重要的優勢。因此，該文采用有序殘差核來計算各個軌跡之間的相關性。

(2)

R(*)表示為所做的殘差運算。

(3)

(4)

(5)

(6)

這樣進一步地使計算更加簡便。

2.4 累加相關性構造相似度矩陣

(7)

2.5 用譜聚類進行運動分割

譜聚類是從圖論中演化出來的算法，后來在聚類中得到了廣泛的應用。它的主要思想是把所有的數據看作空間中的點，這些點之間可以用邊連接起來。距離較遠的兩個點之間的邊權重值較低，而距離較近的兩個點之間的邊權重值較高，通過對所有數據點組成的圖進行切圖，讓切圖后不同的子圖間邊權重和盡可能的低，而子圖內的邊權重和盡可能的高，從而達到聚類的目的。

該文利用上述方法已經求得了相似度矩陣D，接著需要求得度矩陣：

(8)

即相似度矩陣D的每一行元素之和。M為mi組成的n×n對角矩陣。

D為相似度矩陣，求得度矩陣M，標準的對稱拉普拉斯矩陣如下：

L=M-1/2DM1/2

(9)

然后用如下公式進行特征求解：

mintr(UTLU),s.t.UUT=I

(10)

其中，tr(*)表示跡運算。

計算L的特征值，將特征值從小到大排序，取前k個特征值，并計算前k個特征值的特征向量u1,u2,…,uk，將上面的k個列向量組成矩陣U={u1,u2,…,uk}，然后作為原始點的新特征表示處理。然后使用k-means算法進行聚類，最后得到聚類結果。

3 仿真實驗

3.1 數據集

3.1.1 Hopkins155

在實驗中，是針對Hopkins155數據集進行的算法設計。Hopkins155數據集是運動分割最流行的基準之一。它由120個二運動視頻序列和35個三運動視頻序列組成。

3.1.2 62-clip

62-clip數據集主要來自于Hopkins155數據集，包括來自Hopkins155的50個視頻序列，另外12個有物體遮擋的視頻序列已經添加到62-clip數據集中。在12個視頻序列中，有9個視頻序列具有透視效果。在62-clip數據集中有26個雙運動視頻序列和36個三運動視頻序列。

3.1.3 KITTI

KITTI數據集是由德國卡爾斯魯厄理工學院和豐田美國技術研究院聯合創辦，是目前國際上最大的自動駕駛場景下的計算機視覺算法評測數據集。KITTI包含市區、鄉村和高速公路等場景采集的真實圖像數據。該數據集比較契合真實場景，可以在此數據集上驗證文中算法的精度。

3.2 評價指標

運動分割性能是根據點軌跡的標記誤差來評估的，其中序列中的每個點都有一個真實值標簽。

分類錯誤率=被錯誤分類的特征點/總特征點

在Hopkins155數據集中，分別在兩運動序列、三運動序列與所有序列上進行實驗，以此來比較各個方法的優點。

在62-clip中，分別在12有遮擋序列和50無遮擋序列以及所有序列上進行實驗，來測試各個模型應對遮擋問題的能力。

在KITTI上，用平均與中位數這兩項指標比較各方法的穩定性。

3.3 實驗結果

在表1中，將文中方法與之前的算法(GPCA[9],SSC[15],LRR[16],ALC[7],ORK[8],TPV[5])進行對比。這些算法在發表的時候都是在Hopkins155數據集上有著很好的表現，但是隨著研究進一步深入，其局限性也顯露了出來。

表1 在Hopkins155數據集上的實驗結果

文中方法針對有遮擋的視頻做出了一些改進，在62-clips數據集中，有12個視頻是有遮擋的。在表2中可以看出，在12個有遮擋的序列中，只有文中方法有很好的效果，在其余50個不被遮擋的序列中，可以看到分類錯誤率的差距不是很大，說明文中方法在處理有遮擋問題時，確實起到了作用。

表2 在62-clips數據集上的實驗結果

表3是在KITTI數據集上進行的實驗。由于KITTI多是透視視角，更加趨近于真實場景，而且KITTI多是用于自動駕駛，所以文中方法也存在很高的錯誤率，但相對于別的方法具備一些優勢。

表3 在KITTI數據集上的實驗結果

圖3展示了最后的聚類效果，這是Hopkins155數據集中的一幀，可從圖中看出背景，卡車與小轎車被分為了不同的類別，說明聚類取得了一定的成功。

圖3 聚類效果

4 結束語

設計了一個基于相似度矩陣與單應變換的運動分割算法。為了在Hopkins155上發揮更好的效果，該文選擇了用單應矩陣模型來擬合。用相似度矩陣并且使用了累加的方法，使此方法在處理有遮擋的視頻時有著更好的魯棒性。仿真實驗結果表明，該方法在Hopkins155數據集上具有不錯的效果，但是在更加接近于真實世界與大的場景的KITTI數據集上，此方法表現不佳，所以還需進一步改進，以適應更多變的視角。