藺志宇，陳國良

(武漢理工大學 機電工程學院，湖北 武漢 430070)

跨境追蹤過程中，監(jiān)控視頻的關聯(lián)性及分析機制上的研究尚顯不足，在監(jiān)控視頻間關聯(lián)方法研究中，主要有以下兩種思路：①直接建立監(jiān)控視頻間的拓撲網絡或者圖模型[1]，文獻[2]依據(jù)監(jiān)控點間的臨近關系來構建該模型；也有研究基于拓撲學習的方法，依據(jù)路徑統(tǒng)計結果構建監(jiān)控視頻間拓撲網絡[3]。這種思路構建的模型結構較為簡單，拓撲模型可直接將監(jiān)控視頻聯(lián)系起來，缺點是當監(jiān)控點分布環(huán)境較為復雜時，拓撲模型無法完全描述監(jiān)控點間的聯(lián)絡關系。②將視頻監(jiān)控系統(tǒng)和地理信息系統(tǒng)GIS(geographic information system)相結合構建模型[4-6]，該模型將監(jiān)控點映射到地理空間中，可以實現(xiàn)監(jiān)控視頻有效管理，且更易適應搜索跟蹤算法。在目前的研究中，該方法主要應用于大型商場等場景中，應用范圍相對較窄?；跇嫿ǖ哪Ｐ蛯δ繕藢ο筮M行跟蹤搜索的相關算法研究主要集中于兩個方面：①移動對象在監(jiān)控點間轉移路線判定算法研究，有部分算法直接依賴拓撲網絡中的鄰接關系進行擴展排查[7]；也有部分方法基于統(tǒng)計數(shù)據(jù)對目標對象在拓撲網絡節(jié)點間的轉移概率進行判定[8]，確定最優(yōu)搜索路徑，該方法搜索效率較高，但是依賴于大量數(shù)據(jù)，適應性較差。②移動對象在監(jiān)控點間的轉移時間預判算法，文獻[2]依據(jù)大量歷史數(shù)據(jù)建立高斯混合模型，利用該模型預測下一個監(jiān)控點目標出現(xiàn)的時間區(qū)間，進而在相應時間段內完成搜索任務，該算法可以避免噪聲干擾，但是由于監(jiān)控數(shù)據(jù)不易獲取，導致建立的模型適應性較差。

筆者將視頻監(jiān)控節(jié)點通過線性參考系統(tǒng)LRS(linear referencing system)坐標定位于拓撲地圖中，構建視頻監(jiān)控網絡模型并改進鄰接表對模型進行存儲；然后以該模型為基礎，提出基于廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法的目標搜索跟蹤策略；最后建立模型驗證算法的有效性和跟蹤搜索框架的可行性，并利用該搜索策略模擬完成行人的搜索跟蹤實驗。

1 基于LRS坐標的監(jiān)控點定位及存儲

線性參考系統(tǒng)(LRS)是一種利用沿著可測量線要素的相對方位來存儲地理位置的方法，其定位要素由所屬路徑、度量、事件構成[9]?？刹捎肔RS坐標將監(jiān)控節(jié)點定位于拓撲地圖中。

在拓撲地圖中對監(jiān)控節(jié)點進行定位，所屬路徑要素為其在拓撲地圖中的所在弧段。度量要素為監(jiān)控點距離拓撲地圖上較近節(jié)點的距離。某些建筑物出入口或者路徑為單向的，其對應監(jiān)控點只會記錄單向移動對象，因此將事件要素定為方向屬性，即單向S，或多向M。監(jiān)控節(jié)點在拓撲地圖中的坐標表示為：nwk(li,j,ni,si,k,D)，nwk為監(jiān)控節(jié)點；li,j表示所屬路徑要素；ni和si,k共同表示度量要素，分別代表在弧段li,j上距離監(jiān)控節(jié)點nwk較近的節(jié)點和兩點間對應的距離；D代表方向，指明單向S或多向M。監(jiān)控節(jié)點在拓撲地圖中的分布位置示意如圖1所示。

圖1 監(jiān)控節(jié)點在拓撲地圖中的分布位置示意

監(jiān)控節(jié)點在拓撲地圖中的位置可分成兩個類別: 位于弧段上，不與普通節(jié)點重合; 與普通節(jié)點重合，如圖1 所示。具體到坐標，對于類型Ⅱ，其所屬路徑為null，距離要素的值為0。兩種情況下監(jiān)控節(jié)點的坐標表示分別為: nw1 ( li，j，ni，si，1，D)和nw2 ( null，nj，0，D) 。

通過LRS坐標將視頻監(jiān)控節(jié)點在拓撲地圖中定位，構成視頻監(jiān)控網絡模型，其模型如下：

H=(N,L,W)

(1)

N={n0,n1,n2…}

(2)

L={…,lij,…}

(3)

W={nw0,nw1,nw2,…}

(4)

式中：H為拓撲網絡；N為節(jié)點的集合；L為節(jié)點間中經的集合；W為監(jiān)控節(jié)點集合。

圖2為監(jiān)控網絡模型圖。

圖2 視頻監(jiān)控網絡模型圖

視頻監(jiān)控網絡模型可以通過改進的鄰接表來進行存儲，相比于普通鄰接表，其改進主要為以下兩個部分：

(1)依據(jù)監(jiān)控節(jié)點分布類型，增添標志位，標明鄰節(jié)點是否同時為監(jiān)控節(jié)點(類型Ⅱ)，標明對應弧段上是否有監(jiān)控節(jié)點(類型Ⅰ)。

(2)增添監(jiān)控節(jié)點坐標位，依據(jù)(1)中標志位設定對應監(jiān)控節(jié)點坐標。

圖3為改進鄰接表示意圖，其中FL為標志位，由兩位2進制數(shù)表示；CW為監(jiān)控節(jié)點坐標位，存儲兩種監(jiān)控節(jié)點坐標。標志位FL及監(jiān)控節(jié)點CW設定及含義如表1所示。

圖3 改進鄰接表節(jié)點設計

表1 標志位FL及監(jiān)控節(jié)點CW設置

2 視頻監(jiān)控網絡模型下的目標搜索算法

2.1 監(jiān)控鄰域及總體搜索框架

在視頻監(jiān)控網絡模型中，以點Q為起始節(jié)點，目標對象沿任意路徑Rk移動均會遇到一監(jiān)控節(jié)點nwk，任意路徑Rk可構成集合Rψ，對應全體監(jiān)控節(jié)點nwk可構成集合Vψ，定義Rψ和Vψ的合集Oψ為節(jié)點Q的監(jiān)控鄰域。監(jiān)控鄰域的數(shù)學表達如下：

Oψ=(Rψ，Vψ)

(5)

(6)

(7)

(8)

在視頻監(jiān)控網絡模型中對目標對象搜索跟蹤，搜索框架如下：

步驟1從起始節(jié)點開始，獲取其監(jiān)控鄰域，劃定監(jiān)控鄰域中所包含監(jiān)控節(jié)點的搜索優(yōu)先級；

步驟2計算步驟1中監(jiān)控節(jié)點相應監(jiān)控視頻的搜索時間段；

步驟3依據(jù)步驟1劃定的搜索優(yōu)先級和步驟2得到的搜索時間段，對相應的監(jiān)控視頻進行搜索，當搜索到目標對象時停止繼續(xù)搜索；

步驟4以步驟3中搜索到目標對象的監(jiān)控節(jié)點為新起始節(jié)點，重復步驟1～步驟3，直至目標對象消失為止，結束搜索跟蹤。

2.2 監(jiān)控鄰域獲取算法

獲取節(jié)點Q的監(jiān)控鄰域Oψ，即為獲取Oψ包含的監(jiān)控節(jié)點集合Vψ以及節(jié)點Q到Vψ中每一個監(jiān)控節(jié)點的路徑集合Rψ。利用廣度優(yōu)先搜索算法BFS(breadth first search)[10]獲取集合Vψ， 具體步驟如下：

步驟1建立容器vector和隊列queue，分別用于存放監(jiān)控節(jié)點和普通節(jié)點。設起始節(jié)點為當前結點Q，建立全局節(jié)點訪問狀態(tài)數(shù)組vis，點Q對應數(shù)組值置1，其余數(shù)值初始化為0，查詢鄰接表獲取當前結點的鄰節(jié)點(若Q為類型Ⅰ，則直接指定其鄰節(jié)點為弧段端點)，判定每個鄰節(jié)點和當前節(jié)點Q間是否有監(jiān)控節(jié)點，若有，則將該監(jiān)控節(jié)點添加至vector中；若無，則判定鄰節(jié)點是否同時為監(jiān)控節(jié)點，若是，則將該監(jiān)控節(jié)點添加至vector中，若否，則將該鄰節(jié)點存儲于隊列queue中；

步驟2將隊列queue中的節(jié)點依序取出，依次作為當前結點，重復步驟1，操作完成后將其從隊列queue中彈出，并將其狀態(tài)數(shù)組值置1。注意，在重復步驟1向vector和queue中添加節(jié)點時，判定其狀態(tài)數(shù)組值是否為1，如果為1，則不添加，避免重歷；

步驟3重復步驟2，直到隊列queue為空，無法繼續(xù)擴展搜索為止，此時容器vector中存放全部監(jiān)控節(jié)點即構成集合Vψ。

利用深度優(yōu)先搜索算法DFS(depth first search)[11]獲取集合Rψ的方法如下：

步驟2繼續(xù)建棧。從輔棧中取出集合NQ的第一個節(jié)點nQ1(棧頂元素)，壓入主棧，并將nQ1彈出輔棧。然后查詢鄰接表將nQ1的相鄰節(jié)點集合Nnq1壓入輔棧，此時主棧、輔棧元素繼續(xù)增多。將Nnq1壓入輔棧時要對每一個元素進行判定，若其對應狀態(tài)數(shù)組值為1，則不作為Nnq1元素壓入輔棧，壓入輔棧的節(jié)點對應狀態(tài)數(shù)組值置1；

步驟3削棧。重復步驟2，并且判定主棧元素構成路徑中是否出現(xiàn)其余監(jiān)控節(jié)點，若包含，則將棧頂節(jié)點彈出，若循環(huán)至輔棧棧頂為空集時，此時無法再繼續(xù)建棧，將主棧棧頂元素彈出，同時將輔棧棧頂空集彈出，搜索其余支路；

然后找出起始節(jié)點Q到集合Vψ中第1個監(jiān)控節(jié)點nw1的全部路徑，即集合R1，如步驟5。

步驟5重復步驟4，主棧元素構成路徑中出現(xiàn)目的節(jié)點nw1，則削棧，同時保存路徑，直至主棧為空時結束搜索，此時VR1中保存的全部路徑構成集合R1；

步驟6對集合Vψ中的全部監(jiān)控節(jié)點輪循執(zhí)行步驟1～步驟5，得到全部的集合Ri，其合集即為Rψ。

2.3 搜索優(yōu)先級的劃定

起點Q到其監(jiān)控鄰域中各個監(jiān)控節(jié)點的路徑數(shù)目不同，則目標對象移動時經過這些監(jiān)控節(jié)點的概率不同。從起點Q出發(fā)，通向某一個監(jiān)控節(jié)點的路徑數(shù)目越多，則目標對象向該監(jiān)控節(jié)點移動的概率越大?；诖嗽?，依據(jù)式(9)的計算方法劃定搜索優(yōu)先級。

Pk=NRk/NRψ

(9)

式中：NRk為從起始節(jié)點通向其監(jiān)控鄰域中第k個監(jiān)控節(jié)點全部路徑集合Rk中的元素數(shù)量；NRψ為從起始節(jié)點通向其監(jiān)控鄰域中全部監(jiān)控節(jié)點路徑集合Rψ中的元素數(shù)量；Pk即為通向第k個監(jiān)控節(jié)點的概率，其值越大，則搜索優(yōu)先級越高。

2.4 監(jiān)控視頻搜索時間區(qū)間的確定及優(yōu)化

目標對象從當前節(jié)點向監(jiān)控鄰域中的監(jiān)控節(jié)點移動時，可對其在下一個監(jiān)控點出現(xiàn)的時間點進行預判，以確定對應監(jiān)控視頻的檢測時間點。目標對象到達下一個監(jiān)控節(jié)點的時間區(qū)間，可采用式(10)～式(13)計算：

(10)

(11)

(12)

(13)

通過以上計算可以得到目標對象在監(jiān)控點開始出現(xiàn)的時間區(qū)間，若目標對象在該時間區(qū)間內未出現(xiàn)，則認為目標對象未經過該節(jié)點。

目標對象從起始節(jié)點Q移動至其監(jiān)控鄰域中任意一個監(jiān)控節(jié)點，若存在多條路徑，則相應的出現(xiàn)時間區(qū)間也就有多個，并且這些時間區(qū)間可能相互重合，為了避免對一段監(jiān)控視頻重復檢測，提出時間區(qū)間組合優(yōu)化算法如下：

步驟1區(qū)間排序。將所有時間區(qū)間依照區(qū)間左端進行升序排列，建立容器VT存放組合之后的時間區(qū)間；

步驟2區(qū)間組合。從頭開始，先將前兩個區(qū)間進行組合，設兩區(qū)間組合之后的臨時區(qū)間為[l,r]，若兩個區(qū)間分別為[a,b]，[c,d],則存在以下兩種情況：

(a)c>b,即兩個區(qū)間不存在交集，則不進行合并，將前一個區(qū)間[a,b]保存至容器VT中，組合之后的臨時區(qū)間l=c,r=d;

(b)c≤b，則判斷b，d兩值大小，若b≥d，則組合之后的臨時區(qū)間l=a,r=b;若b

步驟3用臨時區(qū)間[l,r]和后序的時間區(qū)間繼續(xù)進行組合，循環(huán)步驟2，直至最后一個時間區(qū)間組合完成，此時容器VT中存放的時間區(qū)間即為最終的時間區(qū)間集合。

3 實驗及分析

圖4是根據(jù)某學校實際地理信息和監(jiān)控點安置情況構建對應的視頻監(jiān)控拓撲網絡圖，行人移動信息均來自真實的軌跡數(shù)據(jù)。圖4標注了102個普通節(jié)點和40個監(jiān)控節(jié)點，路徑長度信息通過網絡地圖可以獲取。

3.1 監(jiān)控鄰域獲取算法的驗證

從圖4中截取網絡的一部分來對算法進行驗證分析，如圖5所示。圖5中白色節(jié)點為普通節(jié)點，直接用數(shù)字標記，例如30號節(jié)點，代表普通節(jié)點n30；圖5中帶nw標記的黑色節(jié)點分布于弧段，只為監(jiān)控節(jié)點；其余用數(shù)字標記的黑色節(jié)點和普通節(jié)點重合，即是監(jiān)控節(jié)點，也是普通節(jié)點，例如27號節(jié)點，同時代表普通節(jié)點n27和監(jiān)控節(jié)點nw27。

圖5 監(jiān)控鄰域獲取算法驗證網絡圖

設定32號節(jié)點為起始節(jié)點Q，現(xiàn)根據(jù)提出算法獲取其監(jiān)控鄰域。

首先驗證監(jiān)控鄰域中監(jiān)控節(jié)點的獲取算法。表2為搜索過程中每一次循環(huán)隊列queue和容器vector存放節(jié)點狀態(tài)變化情況，最后一次循環(huán)后，queue變?yōu)榭贞犃?，vector中存放的監(jiān)控節(jié)點即為監(jiān)控鄰域中包含的全部監(jiān)控節(jié)點。

再驗證監(jiān)控鄰域中從起始節(jié)點Q到其監(jiān)控鄰域中每一個監(jiān)控節(jié)點的路徑集合獲取算法，在表2所示的實驗中，已經獲取的監(jiān)控鄰域中的監(jiān)控節(jié)點有44,nw34,28,nw43,45,47,27,33,24,27,16,14,22，共計13個?，F(xiàn)以點Q(32號節(jié)點)到22號節(jié)點為例，求取兩節(jié)點間全部路徑。

表2 實驗過程中queue和vector存放狀態(tài)變化表

路徑搜索過程中主棧和輔棧部分關鍵變化的情況如表3所示。從表3可知從32號節(jié)點到22號節(jié)點只有一條路徑，在第14次循環(huán)時找到。

表3 實驗過程中主棧和輔棧存放狀態(tài)變化表

3.2 總體搜索框架的驗證和分析

查閱相關數(shù)據(jù)，平直路面上，行人速度為v=1.1～1.5 m/s，將隨機誤差設為10 s。

模擬系統(tǒng)驗證的步驟如下：

步驟1事先收集搜索跟蹤對象的軌跡信息，記錄其到達各個監(jiān)控點的時間點；

步驟2確定搜索跟蹤對象的起始節(jié)點，作為第一個當前節(jié)點，利用本文算法確定其監(jiān)控鄰域和其中監(jiān)控點的搜索時間段；

步驟3判定真實數(shù)據(jù)中的時間點是否在計算出的搜索時間段內，如在，則匹配成功，接下來以得到匹配的監(jiān)控點為起點進行下一次搜索跟蹤，重復步驟2和步驟3，直到匹配不到或者搜索到軌跡盡頭為止，則該次實驗結束。

以其中一次實驗為例對上述方法進行解釋，如圖6所示，深色標記的是某一條實際的行人軌跡，該人從66號樓走向了圖書館，其經過的普通節(jié)點、監(jiān)控節(jié)點以及每一個包含途經監(jiān)控節(jié)點的監(jiān)控包圍圈的信息如表4所示。

圖6 某次實驗行人路徑圖

表4 跟蹤搜索節(jié)點變化表

從表4可知，每一個當前節(jié)點的監(jiān)控鄰域中包含了下一個路徑上出現(xiàn)的監(jiān)控節(jié)點。

3.3 實驗效果和算法評價

與傳統(tǒng)直接建立在監(jiān)控點間的拓撲網絡模型進行對比實驗，共進行10條行人軌跡的實驗驗證。

圖7為10次實驗的統(tǒng)計結果，從圖7可知，有部分實驗沒有完全追蹤成功，主要原因為：①本實驗設定行人行走于平直路面上，且只考慮行人是正常行走，沒有考慮跑動等情況，這導致對行人出現(xiàn)在監(jiān)控點的時間段計算存在未考慮的誤差；②本實驗標注的監(jiān)控點及路線有限，當追蹤對象走向地圖邊緣或未標注路徑時就會導致追蹤失敗，即使行人后期再回到地圖標注范圍內，也無法繼續(xù)實現(xiàn)追蹤。針對第一種情況，只要依據(jù)實際情況調整誤差估計，就可以使得實驗效果得到改善；針對第二種情況，將網絡標注細化，即可避免。經計算，10次追蹤試驗的綜合成功率為88.14%。

4 結論

筆者針對在監(jiān)控系統(tǒng)中對目標對象搜索跟蹤時的效率低下問題，提出一種基于視頻監(jiān)控網絡模型的搜索策略。實驗表明，該搜索策略可有效完成對目標對象連續(xù)搜索跟蹤，相比直接建立在監(jiān)控點間的監(jiān)控網絡模型及只依賴廣度優(yōu)先搜索算法進行對象的跟蹤搜索，其可以劃定搜索優(yōu)先級，有效提升搜索效率，并且不必依賴大量數(shù)據(jù)，適應性更強，跟蹤節(jié)點成功率在80%以上，性能較為優(yōu)異。