基于圖優(yōu)化的時(shí)變特征跟蹤算法研究

鄭瑾

(福建船政交通職業(yè)學(xué)院 信息與智慧交通學(xué)院，福建 福州350007)

時(shí)變數(shù)據(jù)分析是實(shí)現(xiàn)信息可視化的關(guān)鍵技術(shù)之一，而基于特征的可視化是處理高維時(shí)變數(shù)據(jù)的有效策略[1]。離散化是處理時(shí)變數(shù)據(jù)的常用手段，離散化后的數(shù)據(jù)刻畫了系統(tǒng)在每個(gè)時(shí)刻的狀態(tài)(即系統(tǒng)的快照)。時(shí)變數(shù)據(jù)集的每個(gè)快照都會(huì)產(chǎn)生一組特征對(duì)象，它表示給定時(shí)間的特征狀態(tài)。特征跟蹤技術(shù)可以在連續(xù)的時(shí)間步中找到相應(yīng)的特征對(duì)象，將它們組合成時(shí)空特征，這些跨越連續(xù)時(shí)間步的對(duì)應(yīng)關(guān)系代表了特征演化中的個(gè)體解釋。本文所考慮的解釋包括了延續(xù)、分裂和合并[1-2]。在跟蹤問(wèn)題中，潛在解釋的數(shù)量會(huì)呈指數(shù)增長(zhǎng)，而這些解釋也可能相互矛盾。大多數(shù)現(xiàn)有的特征跟蹤算法僅覆蓋一小部分的數(shù)據(jù)域，所產(chǎn)生的特征較為稀疏。除此以外，如果數(shù)據(jù)域中的特征是密集的，那么數(shù)據(jù)的特征則具有空間填充結(jié)構(gòu)。為了搜索到最佳的擬合，必須考慮所有候選對(duì)象的冪集。冪集是原集合中所有子集構(gòu)成的集族，其大小要遠(yuǎn)遠(yuǎn)大于原集合的大小，使特征跟蹤會(huì)變得十分困難。再者，將一個(gè)特征對(duì)象與相鄰時(shí)間步長(zhǎng)中的一個(gè)或多個(gè)特征對(duì)象相關(guān)聯(lián)的解釋可能相互矛盾，即一個(gè)特征對(duì)象可能會(huì)被分配給一個(gè)或多個(gè)候選對(duì)象。對(duì)此，基于圖優(yōu)化的相關(guān)技術(shù)，提出了一種基于圖優(yōu)化的特征跟蹤算法。

1 基于圖優(yōu)化的跟蹤算法

通過(guò)解決兩個(gè)連續(xù)時(shí)間步的對(duì)應(yīng)問(wèn)題，可以降低特征跟蹤算法的復(fù)雜度。首先，基于一個(gè)時(shí)間步的所有候選對(duì)象與相鄰時(shí)間步的候選對(duì)象的相似性來(lái)構(gòu)建一組潛在的解釋，然后從中選擇能使相似性最大化且無(wú)沖突的解釋子集。在特征跟蹤中，潛在解釋的數(shù)量隨著重疊特征對(duì)象的數(shù)量呈指數(shù)增長(zhǎng)，因此在空間填充設(shè)置中，準(zhǔn)確、快速地解決跟蹤問(wèn)題變得棘手。貪婪策略是一種用來(lái)選擇潛在解釋的簡(jiǎn)單方法，在使用貪婪策略選擇了一個(gè)解釋后，所有與解釋關(guān)聯(lián)的特征對(duì)象都會(huì)從搜索空間中刪除，與此同時(shí)，與這些特征對(duì)象關(guān)聯(lián)的所有解釋都會(huì)被刪除[3]。這樣一來(lái)，求解的過(guò)程容易陷入局部最優(yōu)。

為了應(yīng)對(duì)上述挑戰(zhàn)，提出了兩個(gè)連續(xù)解決的圖優(yōu)化問(wèn)題的組合，如圖 1 所示。為了將潛在解釋集減少到易于處理的大小，假設(shè)連續(xù)性解釋了絕大多數(shù)特征。首先通過(guò)在二分圖上計(jì)算最大權(quán)重、最大基數(shù)匹配來(lái)實(shí)現(xiàn)1∶1的分配。與貪婪選擇策略相比，該方法可以在所有特征中選擇到最合理的候選者。

通過(guò)增加附加邊的匹配來(lái)創(chuàng)建1∶n或n∶1的關(guān)系來(lái)檢測(cè)事件。為此，為匹配階段未覆蓋的所有特征對(duì)象構(gòu)建了一個(gè)非平凡的潛在解釋圖，即分裂和合并。由于解釋可能存在沖突，通過(guò)將問(wèn)題轉(zhuǎn)化為在所有可能的解釋圖中搜索最大權(quán)重獨(dú)立集來(lái)計(jì)算有效解決方案。為此，互不相鄰的節(jié)點(diǎn)代表了一組無(wú)沖突的解釋，而最大權(quán)重的屬性確保相似性的全局最大化。在這兩個(gè)步驟之后未分配的節(jié)點(diǎn)被假定為出生或死亡事件的結(jié)果。下面將詳細(xì)介紹這兩個(gè)算法步驟。

1.1 加權(quán)二分圖匹配

使用具有不相交的節(jié)點(diǎn)集U和V、E邊集和權(quán)重函數(shù)w的加權(quán)二分圖G=(U∪V,E,w)來(lái)表示兩個(gè)連續(xù)時(shí)間步的分配問(wèn)題。假設(shè)在特征提取過(guò)程中已經(jīng)生成了快照St和St+1的不同特征對(duì)象集合，如圖1所示。時(shí)間步t和t+1中的每個(gè)特征對(duì)象分別由集合U和V中的節(jié)點(diǎn)表示。

集合U和V中節(jié)點(diǎn)之間的邊表示底層特征對(duì)象之間的潛在對(duì)應(yīng)關(guān)系。為此，計(jì)算每對(duì)節(jié)點(diǎn)(u,v)∈U×V之間的相似度值，使用兩個(gè)特征對(duì)象之間的歸一化體積重疊作為其相似度的度量。假設(shè)Ou,Ov?Ω是組成各個(gè)特征對(duì)象的域點(diǎn)集，歸一化重疊定義為：

(1)

該相似性度量的取值范圍是[0, 1]，如果相似度的值接近1，說(shuō)明特征對(duì)象之間的相似度更高。對(duì)于所有節(jié)點(diǎn)對(duì)(u,v)，若其所對(duì)應(yīng)的c(u,v)大于0，則在集合E中插入一條邊(u,v)，并使用該相似度值作為邊權(quán)重w(u,v)=c(u,v)；否則，則將邊(u,v)的權(quán)重設(shè)置為0。

為了避免對(duì)所有特征對(duì)象進(jìn)行比較，通過(guò)在兩個(gè)時(shí)間步長(zhǎng)中對(duì)所有頂點(diǎn)進(jìn)行線性遍歷來(lái)構(gòu)建相似度矩陣，并計(jì)算對(duì)象的出現(xiàn)次數(shù)?；谶@個(gè)計(jì)數(shù)結(jié)果，就可以使用式(1)計(jì)算c(u,v)。給定時(shí)間步長(zhǎng)的特征對(duì)象之間的對(duì)應(yīng)關(guān)系是通過(guò)在圖G上找到最大權(quán)重、最大基數(shù)匹配M來(lái)確定的。該過(guò)程對(duì)應(yīng)于在圖中找到邊的子集，使得集合U和V中的每個(gè)節(jié)點(diǎn)都與在所有潛在的最大基數(shù)匹配中，恰好有一條邊，并且與這些邊相關(guān)聯(lián)的權(quán)重總和是最大的。解決這個(gè)匹配問(wèn)題等價(jià)于解決線性分配問(wèn)題(Linear Assignment Problem，LAP)[4]。

第一個(gè)階段提供了一個(gè)匹配M，它對(duì)應(yīng)于t和t+1之間最大數(shù)量的特征對(duì)象的1∶1分配。每個(gè)匹配邊m∈M描述了一個(gè)連續(xù)或分裂/合并事件的最大分量。

1.2 加權(quán)獨(dú)立集求解

基于匹配M，在算法的第二階段執(zhí)行事件檢測(cè)。通過(guò)使用來(lái)自集合E的附加邊來(lái)擴(kuò)充匹配邊，為每個(gè)未分配的特征對(duì)象構(gòu)建一組可能的解釋。我們的目標(biāo)是通過(guò)增加相似度值的總和來(lái)為盡可能多的對(duì)象找到合適的解釋。

如圖1所示，節(jié)點(diǎn)u1可以延續(xù)為v1，也可以分裂成{v1,v2}，又可以分裂成{v1,v3}，還可以分裂為{v1,v2,v3}。為上述任意一個(gè)解釋定義一個(gè)效益，即

(2)

無(wú)沖突的解釋選擇問(wèn)題等效于尋找圖的最大獨(dú)立集。為了最大化整體效益，使用分支定界策略計(jì)算最大權(quán)重獨(dú)立集。將最大權(quán)重獨(dú)立集問(wèn)題建模為整數(shù)線性規(guī)劃問(wèn)題，然后使用CBC(COIN-OR Branch and Cut)求解器解決該問(wèn)題。找到最大權(quán)重獨(dú)立集意味著找到具有最大總權(quán)重的最大節(jié)點(diǎn)集，該集合中沒(méi)有節(jié)點(diǎn)對(duì)是相鄰的。CBC求解器具有多種用于收斂檢測(cè)的啟發(fā)式方法，而本文使用的收斂閾值θ為0.01。

求解的結(jié)果是一組相互不連接的節(jié)點(diǎn)。這些對(duì)應(yīng)于一組非沖突的解釋，即與兩個(gè)后續(xù)時(shí)間步長(zhǎng)的特征對(duì)象相關(guān)的分裂、合并和延續(xù)。通過(guò)用圖G中相應(yīng)的邊來(lái)擴(kuò)展M，得到最終的跟蹤解決方案，如圖1所示。最終得到的結(jié)果圖表示了兩個(gè)時(shí)間步長(zhǎng)之間所有特征對(duì)象的演變。所有未通過(guò)邊連接的節(jié)點(diǎn)表示在相鄰時(shí)間步中無(wú)法分配的特征對(duì)象。

2 實(shí)驗(yàn)評(píng)估

使用包含稀疏和空間填充特征的數(shù)據(jù)集來(lái)評(píng)估本算法。將本算法與現(xiàn)有的算法進(jìn)行對(duì)比，考察本算法在合成和模擬數(shù)據(jù)集上的跟蹤性能。

由于模擬數(shù)據(jù)集缺少已標(biāo)注的數(shù)據(jù)，因此構(gòu)建了合成的數(shù)據(jù)集。雖然合成數(shù)據(jù)集不能完全反映實(shí)際模擬數(shù)據(jù)的真實(shí)動(dòng)態(tài)，但是它們?nèi)匀豢梢栽谝欢ǔ潭壬显u(píng)估算法的跟蹤性能。合成數(shù)據(jù)集的相關(guān)參數(shù)如表1所示。

表1 數(shù)據(jù)集信息

本方法跟蹤并存儲(chǔ)所有時(shí)間步長(zhǎng)內(nèi)所有特征的演變。從整個(gè)集合中選擇了一些具有代表性的案例。對(duì)于這些情況中的每一種，只顯示參與相應(yīng)事件的實(shí)際特征。在圖像中添加了一個(gè)網(wǎng)格，以更好地顯示特征的移動(dòng)趨勢(shì)。圖像用跟蹤圖進(jìn)行了注釋，該圖詳細(xì)描述了所選特征的演變和事件。為了區(qū)分隨時(shí)間變化的特征，通過(guò)隨機(jī)分配的顏色進(jìn)行顏色編碼。如果特征在兩個(gè)時(shí)間步中延續(xù)(即沒(méi)有變化)，那么其顏色就不會(huì)發(fā)生變化。在分割的情況下，只有最大部分保留了前一個(gè)時(shí)間步的顏色，參與分割的所有其他特征都會(huì)收到一個(gè)新的、隨機(jī)選擇的顏色。類似地，當(dāng)一個(gè)特征即將合并時(shí)，合并的特征在前一個(gè)時(shí)間步中以隨機(jī)顏色顯示，最終合并特征的顏色逐漸變成最大連通分量的顏色。

將體積跟蹤算法作為基準(zhǔn)算法，該算法同樣假設(shè)構(gòu)成相同時(shí)間相關(guān)特征的特征對(duì)象在相鄰的時(shí)間步長(zhǎng)中產(chǎn)生重疊[6]。該算法使用閾值來(lái)分配基于體積差異測(cè)試的特征相似性。對(duì)于有效的分配，兩個(gè)特征的相似度值必須低于閾值。在此對(duì)比實(shí)驗(yàn)中，將閾值設(shè)置為0.5。

第一個(gè)合成數(shù)據(jù)集是由在空間中隨機(jī)分布球體對(duì)象構(gòu)成的，這些球體會(huì)隨著時(shí)間的變化在空間中移動(dòng)，每個(gè)球體的移動(dòng)都是獨(dú)立的。該數(shù)據(jù)集的特征對(duì)象由重疊球體連接而成的組件構(gòu)成，球體的移動(dòng)會(huì)導(dǎo)致這些組件發(fā)生分裂或合并。定義新球體加入定義為出生事件，將刪除球體定義為死亡事件。每個(gè)組件都是一個(gè)單獨(dú)的特征對(duì)象，每個(gè)特征對(duì)象都有一個(gè)唯一的識(shí)別號(hào)，將延續(xù)事件定義為：一個(gè)組件在移動(dòng)后仍包含相同的球體。

跟蹤算法的對(duì)比結(jié)果如表2所示，在表2中呈現(xiàn)了兩種算法檢測(cè)不同事件類型的檢測(cè)正確性。

表2 第一個(gè)數(shù)據(jù)集的跟蹤準(zhǔn)確率對(duì)比

在兩種算法在檢測(cè)分裂事件上均具有較高的準(zhǔn)確度(均超過(guò)95%)。在延續(xù)事件中，本算法與基準(zhǔn)算法的差距超過(guò)10%。而對(duì)于合并事件，本算法的性能要遠(yuǎn)遠(yuǎn)優(yōu)于基準(zhǔn)算法。

圖2展示了該合成數(shù)據(jù)集的時(shí)變特征和相應(yīng)的跟蹤圖。如圖2所示，實(shí)驗(yàn)開始時(shí)，三個(gè)單獨(dú)的、不重疊的球體是三個(gè)不同的特征對(duì)象。隨著時(shí)間的遷移，球體發(fā)生移動(dòng)，其中兩個(gè)球體發(fā)生了合并，成為一個(gè)特征對(duì)象。隨后，三個(gè)球體發(fā)生合并，三個(gè)球體成為一個(gè)特征對(duì)象。最后，一個(gè)球體從群體中分裂出來(lái)，成為一個(gè)獨(dú)立的特征對(duì)象。

第二個(gè)合成數(shù)據(jù)集是由隨機(jī)分布的點(diǎn)集所構(gòu)成的多邊形組成的。每個(gè)多邊形單元定義了一個(gè)特征對(duì)象。實(shí)驗(yàn)對(duì)比的結(jié)果如表3所示。在這個(gè)合成數(shù)據(jù)集中，體積跟蹤算法的性能對(duì)相似性閾值非常敏感。因此，還在表3中呈現(xiàn)了相似度閾值為0.3的跟蹤結(jié)果。由結(jié)果可知，本算法仍然具有較高的準(zhǔn)確率。尤其是在檢測(cè)分裂事件方面，本算法的性能要遠(yuǎn)遠(yuǎn)優(yōu)于基準(zhǔn)算法。

表3 第二個(gè)數(shù)據(jù)集的跟蹤準(zhǔn)確率對(duì)比

3 結(jié)論

基于特征的相似性，使用圖優(yōu)化技術(shù)來(lái)解決跟蹤問(wèn)題。首先，使用加權(quán)二分匹配來(lái)計(jì)算一對(duì)一的分配。隨后，通過(guò)計(jì)算最大權(quán)重的獨(dú)立集來(lái)實(shí)現(xiàn)分裂和合并事件的匹配。最后，在含有稀疏特征和空間填充結(jié)構(gòu)合成數(shù)據(jù)集上評(píng)估了本算法的跟蹤性能。實(shí)驗(yàn)結(jié)果證實(shí)了跟蹤結(jié)果的合理性。由于目前缺少已標(biāo)注的真實(shí)數(shù)據(jù)集，因此在未來(lái)的工作中，將對(duì)數(shù)據(jù)集進(jìn)行人工標(biāo)注，并采用真實(shí)的數(shù)據(jù)集來(lái)進(jìn)一步驗(yàn)證本算法的有效性。