軌跡樹層次關(guān)系模型多攝像機(jī)多目標(biāo)跟蹤研究*

劉冠群，李 婷

1.湖南廣播電視大學(xué) 網(wǎng)絡(luò)資源系，長沙410004

2.中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙410083

1 引言

多目標(biāo)跟蹤作為計算機(jī)視覺中的一項(xiàng)重要技術(shù)，已得到了廣泛研究。近年來，學(xué)者提出一系列利用目標(biāo)外觀和動態(tài)信息的在線和批量方法。但是這些方法在視覺監(jiān)控中容易受到遮擋，因?yàn)樗鼈冎皇褂靡粋€攝像頭。特別是在擁擠環(huán)境中，比如教室或商店，目標(biāo)分布密集，容易被各種障礙物遮擋。

為了克服遮擋問題，學(xué)者們提出了多攝像機(jī)多目標(biāo)跟蹤（multiple cameras multiple targets tracking，MCMTT）問題。例如，文獻(xiàn)[1]提出一種針對煤礦井下研究場景的多攝像機(jī)多目標(biāo)軌跡跟蹤算法研究，主要針對煤礦井的視頻跟蹤問題進(jìn)行有效解決。文獻(xiàn)[2]提出基于多伯努利卷積特征多攝像機(jī)多目標(biāo)跟蹤算法，該算法利用卷積算法對視頻特征進(jìn)行處理，目的是提高算法的跟蹤精度。文獻(xiàn)[3]提出一種基于全局分層關(guān)聯(lián)網(wǎng)絡(luò)的多攝像機(jī)多目標(biāo)跟蹤算法，實(shí)現(xiàn)目標(biāo)跟蹤精度提升。多攝像機(jī)多目標(biāo)跟蹤問題主要分為三類[1-2]：（1）重建/跟蹤方法。通過附加視圖的測量來克服遮擋或背景雜波導(dǎo)致的目標(biāo)檢測缺失問題。然后應(yīng)用基于攝像機(jī)的跟蹤方法來生成目標(biāo)的軌跡。例如，文獻(xiàn)[4]采用協(xié)同圖在場景中進(jìn)行目標(biāo)跟蹤，由于跟蹤區(qū)域的量化存在一定的局限性，協(xié)同圖存在幻影問題，導(dǎo)致目標(biāo)位置模糊。然而上述三種方法對背景減法的結(jié)果非常敏感。因此，這種算法會受到具有動態(tài)或復(fù)雜背景的場景的影響[5]。（2）跟蹤/重建方法。試圖將同一目標(biāo)的軌跡關(guān)聯(lián)起來，首先用一種基于攝像機(jī)的跟蹤方法在每個視圖獨(dú)立生成軌跡，然后制定組合問題來關(guān)聯(lián)這些軌跡。例如，文獻(xiàn)[6]將軌跡關(guān)聯(lián)問題表述為多維指派問題，這是著名的NP 難題。用一種啟發(fā)式算法解決了這個問題，即貪婪的隨機(jī)自適應(yīng)局部搜索過程，但是其只可解決短遮擋問題。文獻(xiàn)[7]采用了高階動力學(xué)模型對軌跡的跨視點(diǎn)關(guān)聯(lián)進(jìn)行了研究。該算法在沒有標(biāo)定信息的情況下具有很好的魯棒性。然而，由于高階動態(tài)模型之間的比較需要一個運(yùn)算來找到大矩陣秩，因此算法計算量很大。（3）統(tǒng)一框架。將重建和跟蹤問題表示為統(tǒng)一全局優(yōu)化問題，通過對整個輸入視頻序列進(jìn)行批量處理，取得良好性能。例如，文獻(xiàn)[8]嘗試使用統(tǒng)一框架的MCMTT 算法。該框架構(gòu)建了每臺攝像機(jī)的二維跟蹤圖，并構(gòu)建了不同攝像機(jī)檢測到圖像對的三維重建圖。然而，所提出的圖結(jié)構(gòu)過于復(fù)雜。文獻(xiàn)[9]提出一種基于超圖方法，用單個圖來表示重構(gòu)和跟蹤問題，但必須枚舉同時檢測之間所有可能的重構(gòu)來構(gòu)造圖。此外，該方法通過二元整數(shù)問題公式來求解圖形，算法計算量很大。

盡管基準(zhǔn)上的性能很好，但是這些算法都是基于批處理的算法，不能在每幀上提供即時跟蹤結(jié)果，且需要大量計算。對于許多應(yīng)用程序來說，這是嚴(yán)重限制。此外，算法只使用測量的幾何信息。因此，當(dāng)目標(biāo)接近度增加時，它們在一致性標(biāo)記方面存在困難。本文旨在提出一種高效不損失性能的在線MCMTT 算法，該算法與目前最先進(jìn)批處理算法具有可比性。

2 問題描述

2.1 多目標(biāo)跟蹤問題

給定多目標(biāo)軌跡檢測中，所有攝像機(jī)的一組檢測結(jié)果為D=(di|di=(li,si,ci,ti),i=1,2,…,ND)，其中l(wèi)i、si分別表示圖像坐標(biāo)位置和比例，ci∈(1,2,…,NC)是相機(jī)索引，ti表示檢測到di的時間戳，di則表示上述界定圖像位置的第i個檢測。ND是輸入檢測的總數(shù)。定義第j個追蹤為，式中是屬于Yj的檢測索引集。假設(shè)每個檢測不能由多個目標(biāo)共享，即對于i≠j，總是滿足。航跡是目標(biāo)在三維世界坐標(biāo)系下的估計軌跡。當(dāng)定義為與跟蹤Tk關(guān)聯(lián)的跟蹤索引集時，Tk、Zk?D的檢測集可以用中二維跟蹤定義。定義作為在時間t從所有攝像機(jī)觀察到的一組軌道檢測。令為目標(biāo)在時間t的三維估計位置，軌道Tk∈T定義為這些位置估計的序列，式中max({ti|di∈Zk})分別是Tk的起始時間和終止時間。全局假設(shè)Hn∈H是一組多目標(biāo)的估計軌跡，即T的一個子集。將定義為屬于Hn的一組索引時，Hn的定義是。

對于可行全局假設(shè)，屬于同一全局假設(shè)的任意兩個不同軌道Tk和Tl必須滿足以下相容條件：（1）任何兩條軌道中都沒有共用軌跡，即。（2）避免碰撞，即，式中θs指為避免目標(biāo)間碰撞所需的最小距離。定義兼容集?，它由兼容軌道的無序索引對組成，即對于所有k,l，滿足條件{k,l}∈?。多目標(biāo)跟蹤是尋找最優(yōu)的全局假設(shè)H?，在滿足相容條件的可行全局假設(shè)中，H?具有最大評估值：

式中，{k,l}∈?，?k,l∈IHn。由于式（1）中問題是NP困難問題，本文提出一種新的在線方案，利用已有解在幀找到式（1）的近似最優(yōu)解。

2.2 算法框架

圖1 給出該方法總體方案，它由四部分組成：軌跡、跟蹤、全局假設(shè)和修剪。在每個攝像頭上，為了在線關(guān)聯(lián)檢測，設(shè)計跟蹤匹配問題的檢測方法。然后，生成新的軌跡或用匹配的結(jié)果更新已建立的軌跡集。

Fig.1 Algorithmic framework圖1 算法框架

在全局假設(shè)部分，對當(dāng)前幀中所有軌跡的集合式（1）進(jìn)行求解。為減少計算量，引用生成模型式（1）的子問題，其包含上一級框架中的KH最佳全局假設(shè)集。為了解決NP 難題，采用BLS（Boneh-Lynn-Sshacham）方法，提出了一個良好的初始解和適當(dāng)?shù)牡螖?shù)，并修改BLS 以生成多個近似最優(yōu)解。在收集了所有通過解決子問題發(fā)現(xiàn)的全局假設(shè)之后，將KH最佳全局假設(shè)選為Ht。Ht存儲在全局假設(shè)部分，用于下一幀，并傳輸?shù)叫藜舨糠帧?/p>

在修剪部分，根據(jù)是否確認(rèn)一條軌跡，對軌跡應(yīng)用兩種修剪技術(shù)。當(dāng)一條軌跡的持續(xù)時間超過某一長度時，該軌跡即被確認(rèn)。采用Ht計算每條軌跡的近似全局軌跡概率（approximate global trajectory probability，AGTP），并將其用于每種修剪技術(shù)中作為標(biāo)準(zhǔn)。然后，修剪信息被傳遞到軌跡部分，以減少下一幀中的軌跡數(shù)量。

2.3 多目標(biāo)跟蹤匹配驗(yàn)證

對匹配檢測和跟蹤應(yīng)用進(jìn)行驗(yàn)證，以增強(qiáng)跟蹤健壯性。定義Dt={di|ti=t}是隨時間t新檢測到的結(jié)果，Yt-1作為最近檢測時間為t-1 的所有軌跡集，即Yt-1=(Yj|max({ti|i∈Iyj})=t-1)。然后，軌道Yj∈Yt-1與檢測di∈Dt之間匹配度為：

式中，wδ(si)指示與si成比例的相鄰窗口大小，則差距主要是。通過使用以上前向跟蹤，可從中獲得，即前一幀中軌跡的最后一次檢測。

3 軌跡樹層次關(guān)系模型

3.1 軌跡模型描述

本節(jié)中描述了在線軌跡生成方案，并提出代表每個軌道質(zhì)量的軌跡分?jǐn)?shù)。此外，還定義軌跡樹，表示軌跡間層次關(guān)系。

軌跡關(guān)聯(lián)：令{Ω1(Y),Ω2(Y),…} 是整個軌跡集Y=(Y1,Y2,…,Yq)的所有可能分區(qū)的集合。然后，所提MCMTT 問題目標(biāo)是找到分區(qū)Ωi(Y)，最能描述目標(biāo)跟蹤。第i個分區(qū)定義為是假警報集。表示軌跡集合應(yīng)來自第i個分區(qū)中的第k個目標(biāo)，稱之為關(guān)聯(lián)集。定義所有可能的沒有分區(qū)索引的關(guān)聯(lián)集：

為簡化省略參數(shù)(Y)，將ωk對應(yīng)軌跡記為Tk，將ωk的相關(guān)檢測集記為Zk。定義三種操作：空間關(guān)聯(lián)、時間關(guān)聯(lián)和合并。

操作1（空間關(guān)聯(lián)）如圖2 中的T2和T7所示，空間關(guān)聯(lián)是由臨時重疊軌跡之間的關(guān)聯(lián)來定義的，這些軌跡應(yīng)該來自同一目標(biāo)，使用不同的攝像頭。為確定軌跡Yl和Ym是否來自同一目標(biāo)，提出了空間關(guān)聯(lián)條件，該條件檢查軌跡中同時檢測之間的距離是否受閾值ε3D的限制，如下所示：

Fig.2 Example of trajectory generation圖2 軌跡生成示例

操作2（時間關(guān)聯(lián)）同一攝像頭的臨時不重疊軌跡間關(guān)聯(lián)，或同一目標(biāo)不同攝像頭間的關(guān)聯(lián)。對于時間關(guān)聯(lián)，前向軌跡Yl和后面軌跡Ym須滿足：（1）根據(jù)每個目標(biāo)在每個視圖中最多只生成一個檢測的事實(shí)，Yl和Ym須是暫不重疊的，即{ti|di∈Yl}?{tj|?dj∈Ym}=?。（2）目標(biāo)不能突然改變其位置，因此dp（Yl最后一次檢測）和dn（Ym第一次檢測）在三維空間足夠接近。當(dāng)vmax被定義為目標(biāo)在一幀內(nèi)可移動最大距離時，條件是||Φ(dp)-Φ(dn)||2≤vmax×|tp-tn|。

操作3（合并關(guān)聯(lián)）如果兩個關(guān)聯(lián)集的聯(lián)合集滿足所有時空關(guān)聯(lián)條件，則聯(lián)合集也是關(guān)聯(lián)集。這兩個關(guān)聯(lián)集稱為可合并。其合并操作定義為：（1）如果ωi和ωj可合并，則ωi⊕ωj=ωi?ωj；（2）如果ωi和ωj不可合并，則ωi⊕ωj=?。

3.2 軌跡關(guān)系評估模型

考慮四個因素，評估軌跡得分：

（1）重建評估SR(·)，表示軌道位置與檢測相同程度。重建評估基于PZ(·)構(gòu)建，即在特定時間對目標(biāo)可能性進(jìn)行檢測。將Xtk作為t時Tk跟蹤目標(biāo)位置的隨機(jī)變量，則重建分?jǐn)?shù)為：

式中，似然度PZ(·)的計算可參見文獻(xiàn)[10]有關(guān)描述進(jìn)行計算。

（2）連接分?jǐn)?shù)SL(·)，它考慮了軌道連續(xù)位置的幾何適宜性。有些運(yùn)動很難預(yù)測，例如行人等，因?yàn)樗ǔＪ欠蔷€性的。因此，只考慮軌道上連續(xù)位置鄰近性，以確定連接這些位置是否合適。所提連接分?jǐn)?shù)定義為隨軌道上連續(xù)位置之間的距離發(fā)生變化，即：

式中，vmax是一個設(shè)計參數(shù)，用于模擬行人在一幀內(nèi)可以移動的最大距離。當(dāng)遠(yuǎn)大于vmax時，鏈接視為無效，此時放棄對其跟蹤。參見文獻(xiàn)[11]。

（3）初始評估SI(·)和最終評估ST(·)。如前所述，在可見區(qū)域中間突然啟動或終止的軌跡不太可能。為反映趨勢，起始/終止評估定義為：

式中，Ps和Pe分別是目標(biāo)在可見區(qū)域出現(xiàn)和消失的概率。τs和τe是目標(biāo)與可見區(qū)域邊界之間距離的懲罰系數(shù)。τl是防止長軌跡終止的懲罰系數(shù)。是和可見區(qū)域邊界之間的距離。mB是實(shí)驗(yàn)中設(shè)定為1 m 的邊界。在起始幀附近開始的軌跡不受起始懲罰，因此其起始評估為lb(Ps)。通過這些起始/終止評估，可以避免目標(biāo)軌跡中出現(xiàn)過多的碎片。參見文獻(xiàn)[12]。

（4）視覺評估SV(·)，表示與軌道相關(guān)的檢測間的視覺相似性。假設(shè)目標(biāo)不會突然改變它的外觀，因此每個視圖中相同軌跡的相鄰檢測應(yīng)該具有相似的外觀。對任意軌跡Tk的ωk時間關(guān)聯(lián)處的得分賦值。令是根據(jù)其開始時間攝像機(jī)c的軌跡有序集合，單位為ωk。檢測的有序?qū)x為：

式中，av和τv模型參數(shù)隨著檢測之間的時間間隔增加，視覺相似性置信度下降。參見文獻(xiàn)[13]。

最后，利用（1）～（4）所示因素可定義軌跡評估形式：

3.3 全局假設(shè)

每個MWCP（maximum weight clique problem）由構(gòu)成，一組軌跡是當(dāng)前最佳全局假設(shè)候選者，假設(shè)先前最佳全局假設(shè)是。把稱為相關(guān)軌跡集。它包含三種類型軌道：（1）的軌跡；（2）在當(dāng)前幀中新生成兩個子項(xiàng)軌跡，即；（3）未確認(rèn)軌跡。

未確認(rèn)軌跡是比Nconf幀短的軌跡，無法確定它是否為假陽性。因此，不斷將未確認(rèn)軌跡插入軌跡集，即使這些未確認(rèn)軌跡不在先前解決方案中。則定義為。則 對 于n=1,2,…,KH，每個的MWCP 問題定義為：

式中，與輸入視頻序列的起始幀Ht-1=?一樣，構(gòu)造并求解了完整的跟蹤集Tt的單重網(wǎng)絡(luò)控制點(diǎn)。當(dāng)精確求解多路徑控制點(diǎn)時，求解多路徑控制點(diǎn)的計算與軌道數(shù)成指數(shù)比例。

3.4 算法步驟

將Ht定義為Tt中所有可能的全局假設(shè)集時，Ti∈Tt軌跡的GTP（global trajectory probability）定義為：

修剪有零軌跡作為軌跡修剪的第一步。由于KH最佳全局假設(shè)定義，零軌跡意味著軌跡不屬于KH最佳全局假設(shè)中的任何一個。

對于已確認(rèn)的軌跡樹，保持每棵樹中的所有軌跡是很難的，因?yàn)槊靠脴渲械能壽E數(shù)呈指數(shù)增長。因此，將N掃描后退方法應(yīng)用于已確認(rèn)的軌道樹。這是基于延遲決策的修剪技術(shù)。在找到最佳全局假設(shè)后，它會掃描N幀，并根據(jù)當(dāng)前的最佳全局假設(shè)確定目標(biāo)的位置。然后它修剪所有與目標(biāo)固定位置不兼容的軌跡。從樹結(jié)構(gòu)的角度來看，除了當(dāng)前最佳全局假設(shè)中包含軌跡的分支外，它以前在N幀處修剪每個軌跡樹的分支。在算法1 中總結(jié)了本文的在線方案。

算法1軌跡樹層次關(guān)系模型

輸入：檢測視頻數(shù)據(jù)集D。

算法1 中，第1 行是對算法進(jìn)行參數(shù)初始化，第2～第6 行是根據(jù)2.3 節(jié)內(nèi)容生成多攝像機(jī)多目標(biāo)跟蹤軌跡，第8 行是對軌跡關(guān)聯(lián)性進(jìn)行計算，然后在第9行中，根據(jù)計算的軌跡關(guān)聯(lián)性進(jìn)行新軌跡生成，第13～第15 行進(jìn)行最佳軌跡初始化，第20～第22 行是根據(jù)3.3 節(jié)、3.4 節(jié)內(nèi)容對軌跡結(jié)果進(jìn)行評估，并對其進(jìn)行軌跡調(diào)整和更新。

上述算法中，從計算復(fù)雜度角度分析，因?yàn)闊o嵌套迭代過程，因此其計算復(fù)雜度是O(N)，具有相對較小的計算復(fù)雜度，體現(xiàn)了算法的計算效率。從算法收斂性角度分析，根據(jù)第16 行可知，在算法迭代計算過程中，每次選取的是當(dāng)代進(jìn)化迭代過程的最佳值，因此該算法可保證多攝像機(jī)多目標(biāo)跟蹤過程的收斂。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)置

（1）實(shí)驗(yàn)硬件：處理器CPU 為i5-6400K 3.2 GHz，內(nèi)存RAM 為ddr4-2 400 GHz 8 GB，系統(tǒng)為Win10 旗艦版，仿真平臺選取Matlab2012a。

（2）數(shù)據(jù)集：選取PETS 2009 數(shù)據(jù)集作為實(shí)驗(yàn)對象，數(shù)據(jù)集示例見圖3 所示。場景中使用3 個集合：S2.L1、S2.L2 和S2.L3。這些裝置包括4 到7 個不同的視角，重疊室外攝像機(jī)視角。每個視圖有數(shù)百個幀，以7 frame/s 的速度捕獲10～74 個行人。每個場景都有不同行人密度，從低（S2.L1）到高（S2.L3）?；鶞?zhǔn)數(shù)據(jù)集還通過Tsai 的攝像機(jī)模型提供每個攝像機(jī)的固有和外在參數(shù)。在評估中，給出每幀感興趣區(qū)域內(nèi)目標(biāo)位置。

為檢驗(yàn)所提成本函數(shù)參數(shù)和條件對性能精度影響，構(gòu)造新數(shù)據(jù)集，即pilsun 數(shù)據(jù)集，包含來自4 個重疊攝像頭的333 frame，每個攝像頭捕捉10 個行人，這些攝像頭以6 frame/s 的速度密集分布在一個小型室內(nèi)環(huán)境中。數(shù)據(jù)集還為每個攝像頭提供了Tsai的攝像頭模型，以及由手工標(biāo)記的跟蹤結(jié)果生成的地面實(shí)況。

（3）參數(shù)設(shè)置：比較間隔長度Lc=4 frame，靜態(tài)特征點(diǎn)閾值δmin=0.05，連續(xù)檢測之間的最大允許3D距離εΦ=0.5 m，一幀內(nèi)目標(biāo)的最大允許三維高度變化εh=0.3 m，相鄰窗口大小差異ωδ(si)=0.3×si，避免碰撞的最小3D 距離θs=0.3 m，同時檢測最大三維距離ε3D=2.5 m，目標(biāo)最大三維速度vmax=0.8 m/s，軌跡上允許最大框架間隙δa=9 frame。

（4）作為定量評估的指標(biāo)，在事件、活動和關(guān)系的分類中使用了多對象跟蹤MOTA（multiple object tracking accuracy）和MOTP（multiple object tracking precision）指標(biāo)，這是MCMTT 最流行指標(biāo)。

4.2 結(jié)果分析

（1）參數(shù)影響。所提方法的運(yùn)行參數(shù)設(shè)置KH=1,5,10,15,20,25,30 和。研究KH和最大值對計算精度和計算時間的影響。圖4 顯示了處理時間、MOTA 隨參數(shù)變化的影響實(shí)驗(yàn)。

Fig.4 Parametric influence experiment圖4 參數(shù)影響實(shí)驗(yàn)

（2）算法對比實(shí)驗(yàn)。為了驗(yàn)證所提求解方案的有效性，將其與變分方案和基線方案進(jìn)行了比較。圖5 顯示了每個解決方案的定量結(jié)果。對比算法選?。何墨I(xiàn)[14]僅使用一個MWCP 求解的基線解算方案，沒有來自先前全局假設(shè)的反饋信息。文獻(xiàn)[15]采用一個MWCP 求解的基線解算方案，并采用來自先前全局假設(shè)的反饋信息。圖6 給出三種對比算法在實(shí)驗(yàn)數(shù)據(jù)集上的1 幀跟蹤結(jié)果示例對比結(jié)果。

根據(jù)圖5、圖6 實(shí)驗(yàn)結(jié)果可知，當(dāng)KH=1 時，基線方案優(yōu)于其他方案。然而這是微不足道的，因?yàn)槠渌桨盖蠼獾膱D形比基線方案小，這意味著它們無法從先前解決方案附近或周圍的局部最優(yōu)解中逃脫。然而，盡管解決的是較小的圖而不是基線方案，但當(dāng)KH值較大時，性能會提高。當(dāng)KH=5 或更大時，建議方案的性能優(yōu)于基線方案。當(dāng)KH=5 或更大時，所提算法（沒有初始解決方案）也取得了與基線方案相當(dāng)?shù)男阅?。相對于對比算法，本文算法在?zhí)行時間和求解精度上均要顯著優(yōu)于文獻(xiàn)[14]和文獻(xiàn)[15]兩種算法，體現(xiàn)了算法性能優(yōu)勢。同時，在圖6 實(shí)驗(yàn)結(jié)果上可直觀地看出，本文算法對于目標(biāo)的跟蹤精度更高，可實(shí)現(xiàn)對目標(biāo)的準(zhǔn)確識別和追蹤。而在對比算法中，文獻(xiàn)[14]和文獻(xiàn)[15]兩種算法的目標(biāo)追蹤精度相對較低，與本文算法具有顯著的差異。

Fig.5 Algorithmic contrast experiments圖5 算法對比實(shí)驗(yàn)

Fig.6 Comparison of tracking results between two adjacent frames圖6 前后兩幀跟蹤結(jié)果對比

5 結(jié)束語

本文提出基于MHT（multi-hypothesis tracking）框架的在線MCMTT 算法，該框架是由MWCP 為軌跡關(guān)聯(lián)實(shí)現(xiàn)的，可以找到多個對象跟蹤，直到當(dāng)前幀。通過使用軌跡模型和關(guān)聯(lián)條件，所提跟蹤算法生成優(yōu)化的候選跟蹤，并拒絕一些不可靠候選跟蹤。為解決多目標(biāo)跟蹤問題，提出一種在線方案，該方案根據(jù)前一框架中過去的全局假設(shè)，生成多個具有小軌道集的多目標(biāo)跟蹤問題。這些子問題的解搜索空間比原來的多目標(biāo)控制算法小得多，因此該方案大大縮短了求解時間。此外，該方案也比用全軌跡求解多目標(biāo)控制問題找到更好的解決方案。提出的初始解和迭代次數(shù)有助于在迭代次數(shù)較少的情況下找到近似最優(yōu)解。下一步，將重點(diǎn)在算法的收斂性分析方面進(jìn)行研究，完善算法理論基礎(chǔ)。