基于排隊論的跨攝像頭乘客軌跡識別方法

摘要：目前攝像頭監控視頻群組中采用遍歷查找搜索全部攝像頭視頻，或者拓撲網查找重復搜索，導致人員追蹤查找效率低、準確性差，為解決這一問題，提出了一種基于排隊論和頂點加權有向圖的高效選擇監控攝像機視頻的方法。該方法借鑒排隊論理論的原理，將攝像頭視為頂點，并構建了一個加權有向圖。通過計算權值，能夠確定最優的監控路徑，同時考慮了攝像頭之間的連接和權值。這一方法的關鍵優勢在于高效地選擇監控攝像機視頻。此外，將城市軌道交通節點目標乘客的最優運動路徑與人員追蹤相結合，采用了頂點加權有向圖的思想，提高了識別的準確性和效率。研究結果表明，通過將排隊論和頂點加權有向圖理論應用于人員追蹤領域，為解決實際問題和提升系統性能提供了一種創新的方法。這一方法對于提升監控系統性能和人員追蹤能力具有重要意義。

關鍵詞：排隊論；頂點加權；軌跡識別；跨攝像頭追蹤

中圖分類號：U291.69文獻標志碼：A文章編號：1002-4026（2024）05-0062-07

開放科學（資源服務）標志碼（OSID）：

Queuing theory-based cross-camera passenger trajectory recognition method

WEN Zening1， ZENG Hongbo2， NIU Ling3*， LU Kai4， ZHAO Zhonghao5

（1.China Railway Design Group Co.， Ltd.， South China Branch， Shenzhen 518000， China；2.Shenzhen Metro Operator Group Co.， Ltd.，

Shenzhen 518026， China; 3.BeijiaoWisdom（Shandong） Intelligent Technology Co.， Ltd.， Jinan 250100， China; 4. Traffic Control

Technology Co.， Ltd.， Beijing 100070， China; 5.School of Transportation， Beijing Jiaotong University， Beijing 100044， China）

Abstract∶Currently， in surveillance video groups， traditional methods for searching camera videos involve traversing and searching through all cameras or performing repetitive searches in a network topology. These approaches result in low efficiency and poor accuracy in tracking individuals. To address this issue， we propose an efficient method for selecting surveillance camera videos based on the principles of the queuing and vertex-weighted directed graph theories. In this method， we treat cameras as vertices and construct a weighted directed graph. By calculating weights， we can determine the optimal monitoring paths considering the connections and weights between cameras. The key advantage of this method is its efficient selection of surveillance camera videos. Additionally， by combining the optimal movement paths of target passengers in urban rail transit nodes with individual tracking， we use the concept of vertex-weighted directed graphs to enhance the accuracy and efficiency of person recognition. The research results show the great significance of this method in improving the performance of surveillance systems and individual tracking capabilities. By applying the queuing and vertex-weighted directed graph theories for individual tracking， we offer an innovative approach to address practical problems and enhance system performance. This method holds great importance in enhancing surveillance system performance and individual tracking capabilities.

Key words∶queuing theory; vertex weighting; trajectory recognition method; cross-camera tracking

隨著社會和科技的飛速發展，城市軌道交通成為人們出行的重要方式，視頻監控系統作為保障安全的重要手段，其監控范圍在城市軌道交通中逐漸實現全面覆蓋。城市的發展對視頻監控系統提出了智能化要求，視頻分析技術的不斷發展是視頻監控系統智能化的表現之一。在特殊以及重大事件中，利用視頻分析技術尋找目標乘客以及還原乘客行動軌跡是重要的人員篩查方式之一［1］。

近年來，我國開始重視智能視頻監控系統的研究。李守杰等［2］探討了如何利用云計算資源來處理和存儲大規模的視頻數據，以及如何通過云端的分布式計算和數據分析技術實現實時的視頻監控和智能分析功能，并提及了具體的應用場景，如城市軌道交通系統中的視頻監控系統。趙軍鋒等［3］研究了大規模數據并發環境下視頻監控系統的開發與實現，介紹了系統的架構設計和優化策略，并驗證了其在處理大規模數據并發訪問方面的有效性。該研究對于城市快軌交通領域的視頻監控系統設計和性能優化具有重要的參考價值。甘超瑩等［4］設計了一套采用智能視頻算法、基于圖像識別技術的智能視頻監控系統。該系統已在南寧軌道交通5號線廣西大學站和小雞村站完成了試點應用，有效提升了車站運營管理能力和對突發事件的處置應對能力。李小斌等［5］提出了一種創新的智能視頻監控系統云設計方案。該方案利用直流扭力電機控制云臺，利用聲源實現定位，通過差幀法實現目標精準跟蹤。這項研究也證明了通過視頻分析實現目標定位的可行性。馮凌等［6］開發了一款集現場視頻、監控和防竊電等功能于一體的智能視頻監控終端。該終端依托4G網絡，通過使用反竊電設備可以有效記錄各類竊電現象，從而使現場取證變得不再困難。朱向軍等［7］利用達芬奇技術開發了一種智能視頻監控終端。他們的算法針對運動目標的檢測和跟蹤進行優化，結合了邊緣檢測和背景減除技術的優點，成功實現了對運動目標的分割，并利用目標特征匹配方法建立了連續幀間的對應關系。方浩等［8］提出了一種基于DM6437的智能視頻監控系統，顯著提高了監控系統的智能化程度。他們設計的多用途智能視頻監控解決方案，利用DM6437芯片和改進的動態碼本檢測方法，提高了檢測水平。

就當前研究成果［9］而言，人物的攝像頭跟蹤多是采用對每個攝像機視頻進行背景建模、前景檢測以及運動目標的特征提取，當目標離開攝像機視域的時候，根據已知的拓撲關系向相關攝像機發布監控任務，當有目標進入處于有效監控狀態的攝像機視域時，進行目標匹配，從而實現在多攝像機系統中對行人目標的持續跟蹤。該方法是在非重疊攝像機場景中實現的目標跟蹤，拓撲網絡的查找保證了其較高的準確率，但隨著區域內監控攝像機逐漸增多，這種方式將需要耗費系統大量時間。

本文針對城市軌道交通節點乘客軌跡識別提出了一種新的監控攝像機視頻獲取方法，這種方法借鑒了排隊論理論的原理，將攝像頭作為頂點，并構建加權有向圖。通過計算權值，確定最優監控路徑，同時考慮了不同攝像頭之間的連接和權值。這樣就能夠高效選擇監控攝像機視頻，避免了遍歷查找和重復搜索的低效問題。此外，該方法將城市軌道交通節點目標乘客的最優運動路徑與人員追蹤相結合，通過頂點加權有向圖的思想，提高了準確性和效率。該方法的先進性在于不僅考慮了攝像頭之間的連接和權值，還將排隊論理論和頂點加權有向圖理論應用于人員追蹤領域，對提升監控系統性能和人員追蹤能力具有重要的意義。

1相關理論基礎

1.1排隊論基礎理論

排隊論通過對服務對象到來及服務時間的統計研究，得出等待時間、排隊長度、忙期長短等數量指標的統計規律，然后根據這些規律來改進服務系統的結構或重新組織被服務對象，使得服務系統既能滿足服務對象的需要，又能使機構的費用最經濟或某些指標最優［10］。本文主要利用排隊論研究利用數學模型控制視頻分析最佳工作順序，實現系統效果提升的目標。排隊過程見圖1：

在排隊論輸入過程中包括了視頻位置、相鄰攝像頭關聯位置、連續到達時間以及在不同時間段內連續到達的概率分布。服務機構采取多臺服務臺并行方式，服務時間取最小值模式。

1.2圖論理論基礎

圖論是本文進行有向加權計算的理論基礎。圖G由頂點集合V和邊集合E構成，表示為有序對（V，E）。其中E是一個點對邊集合，它是由V中的節點隨機組合而成。圖G的頂點集也記為V（G），邊集記為E（G）。圖G的頂點數（或階數）用符號n（G）表示，邊數用m（G）表示。本文以有向圖為基礎進行研究，并基于有向圖的頂點進行加權計算，如圖2示例。

對有向圖集G的每條邊，可賦以一個實數，稱為權，頂點連同它邊上的權稱為賦權圖。若H是賦權圖的一個子圖，則H的權W（H）=∑e∈E（H）w（e）賦權圖中路P的長定義為W（P），距離d（u，v）定義為最短（u，v）路的長。在一個賦權圖中找出某類具有最小（或最大）權的子圖，其中之一就是最短路徑問題。常用的求解最短路徑的算法有Dijkstra算法、Bellman-Ford算法、Floyd算法等。

2跨攝像頭乘客最優路徑獲取方法

在本文的研究中，將跨攝像頭乘客視頻分析過程看作一個排隊系統，那么可供分析的監控攝像機視頻是顧客來源，需要分析的監控攝像機視頻是排隊等候服務的顧客，視頻分析系統是服務機構，系統遵從先到先服務、等待機制的服務規則，如圖3表示。

在此排隊系統中對輸入過程進行優化，可有效提高排隊系統效率，即對可供分析的多個監控攝像機視頻進行最優選擇，獲取代表乘客最優行動路徑的攝像機監控視頻集合，作為排隊等候的顧客。此方法可減少不必要的監控攝像機視頻排隊等待服務，有效減少系統分析時間，提高視頻分析系統效能。

在現實世界中，許多復雜問題都可以被描述為有向圖及在其上的遍歷問題，將軌道交通節點各設施之間的位置關系和乘客運動軌跡用有向圖表示，假設某個節點設施關系和某乘客行動軌跡情況如圖4表示。

將站點中每處設施結點（如進站口、安檢口、樓梯、地鐵門等）的監控攝像機作為圖中有向圖的頂點，依次對頂點的監控視頻進行目標分析，可以追蹤到目標乘客從進站到乘坐列車的行動軌跡。從圖4可以看出，目標乘客可能從進站口1或者進站口2進站，此結點經過的頂點為v1或v2，進站后可能從3個安檢口中的任意一個安檢，此結點經過的頂點為v3、v4、v5，依次類推，下樓梯經過的頂點為v6、v7、v8、v9，上地鐵經過的頂點為v10、v11、v12…，找到目標乘客經過每個結點處的頂點則可追蹤到該乘客的行動軌跡。實際生活中的設施結點很多也更復雜，采用隨機遍歷或拓撲網絡的方式確定目標乘客在每個結點處的頂點，以此來追蹤乘客行動軌跡將讓系統變得低效。如何提高這個過程的效率，是本文研究的內容。

基于加權有向圖理論基礎［11］，將圖4進一步優化。定義一個有向加權圖G=（V，E，W），定義設施結點集合為P=p1，p2，…，pn，頂點集合表示為V=V（p1），V（p2），…，V（pn），則V（pi）=vi1，vi2，…，vij，其中0≤i≤n，j為結點i下的1～j個頂點，如圖5示例。

在這里不采用常規的邊加權方式進行討論，而采用頂點加權。在基于頂點加權的模型中，使用圖算法來搜索乘客在不同攝像頭之間的最優路徑。與傳統的邊加權方法不同，路徑搜索時考慮的是節點（攝像頭）之間的權重，而非傳統只采用邊的權重。頂點權重集合表示為W=w11，w12，…，wij，（其中wij是頂點vij的權重），定義頂點權重為wij=Aij·Tij·Bij。其中Aij為頂點vij的監控視頻找到目標乘客的概率，可以基于歷史數據、人流密度、人臉識別算法等信息來估計；Tij為乘客經過頂點vij代表的監控攝像機的時長；Bij為頂點vij的監控視頻的清晰度，較好的攝像頭將具有較高的權值。

將某設施結點處的頂點集合中，權重A、T、B值均最大的頂點作為此結點處的最優選擇頂點。為了找到乘客到達設施結點的最短路徑，可以定義最優選擇頂點為具有最小的權重值和路徑長度的頂點，定義為乘客到此結點的最短路徑minpi，記為

min pi=minW（v）+d（v），（1）

其中，v表示設施結點上的頂點，W（v）表示該頂點的權重值，d（v）表示從起始節點到達該頂點的路徑長度［12］。由此可得出

min P=minp1，min p2，…，minpn，（2）

定義求得的min P為目標乘客從某一階段到下一階段的最優選擇路徑，即為追蹤乘客行動軌跡的最優路徑。

在實際追蹤乘客行動軌跡的過程中，如果在當前設施結點選擇的 最優頂點未找到目標乘客，則在當前結點剩下的頂點集合中再次運用公式（1）選擇最優頂點，直到在當前結點追蹤到乘客信息。

3實例驗證與討論

3.1實例驗證

為了確保頂點加權方法的準確性與可行性，選取某地鐵站2023年5月1日—5日共5天，篩選早高峰 7：00—9：00 的人流量數據，以早高峰日出行均值數據為分析對象。此外，還收集了與乘客進站軌跡相關的數據，包括進站口、安檢口、樓梯和地鐵門的位置信息，以及收集攝像頭監控視頻數據，如視頻的清晰度和持續時間等信息。該地鐵站布置圖如圖6所示。

首先將使用普通遍歷方法以及頂點加權的方法來搜索地鐵站中某一位乘客的進站軌跡。在給定的路徑選擇中，有多個路徑可供乘客選擇，每條路徑都由進站口點位、安檢口點位、樓梯點位和地鐵門點位組成。通過不同的組合，乘客可以選擇從不同的進站口進入，通過相應的安檢口進入地鐵站，然后使用樓梯前往不同的地鐵門點位。如圖6所示，乘客可選擇從進站口v11—安檢口點位v21—樓梯點位v31—地鐵門點位v41，或可選擇v11—v22—v31—v41或v11—v21—v32—v41…以此類推，遍歷所有的選擇方案，共需查找144條攝像頭路徑，時間共計960 min，以實現追蹤人員軌跡。如表1所示。

以圖6為基礎，賦予各點位相應的權值，如圖7所示。當使用監控視頻找到目標乘客的概率、乘客經過頂點vij代表的監控攝像機的時長及頂點vij的監控視頻的清晰度作為頂點權值，并根據邊權值來計算規劃最短、最優路徑后，按照路徑優先順序追蹤人員軌跡，最短一條路徑即可查找完畢，查找到此乘客軌跡為進站口v11—安檢口v22—樓梯v33—地鐵門v41，總用時20 min，效率提升最高可達97.9%以上。

3.2討論與分析

為了確保頂點加權方法的準確性與可行性，將選取的高峰日出行均值數據為分析對象，使用廣度優先搜索、深度優先搜索、頂點加權搜素來進行客流軌跡搜索對比。

將這5天站點客流軌跡提取出300個乘客樣本，使用廣度優先搜索、深度優先搜索、頂點加權要素來進行搜索。為了確保準確性，將搜索結果取均值，結果如表2所示。

通過結果對比，可以得出基于排隊論理論和頂點加權有向圖理論的頂點加權搜索方法在搜索乘客軌跡方面相比廣度優先搜索和深度優先搜索算法具有顯著的優勢。這種方法的高效性體現在平均搜索次數和平均搜索時間的顯著提升。平均搜索次數從廣度優先搜索的161.32次減少到35.52次，平均搜索時間從廣度優先搜索的322.64 s減少到71.04 s。這意味著頂點加權搜索方法在搜索效率方面提高了78%。

綜上所述，基于排隊論理論和頂點加權有向圖理論的高效選擇監控攝像機視頻的方法在搜索乘客軌跡方面具有明顯的優勢。該方法通過賦予攝像頭權值并應用加權計算，能夠找到城市軌道交通節點上目標乘客的最優運動路徑，從而實現對跨攝像頭目標乘客行動軌跡的高效追蹤。

4結論與展望

本文基于排隊論的理論基礎，利用定義的監控攝像頭權重和最短路徑公式，提出跨攝像頭乘客行動軌跡識別方法，搜索效率可提高78%，從而縮短視頻分析系統的分析時間，提高系統效能。

基于本研究的結果，可以進一步改進，不斷改善軌道交通規劃系統，結合智能化技術和用戶導向的設計，為乘客提供更優質、高效和舒適的進站體驗，提高城市交通運輸的效率和乘客的出行滿意度。如將人流密度、車站設施等更多因素納入權重定義中，從而更準確地評估路徑選擇和設施結點的重要性；通過實時數據與交通管理系統或乘客移動數據的集成，實現定期更新權重和路徑，以適應交通狀況的變化，并為乘客提供實時導航和路徑推薦；將地鐵路徑規劃與智能交通系統相結合，為乘客提供更多元化的路徑選擇和綜合交通信息。

同時本文提出的頂點3個權重以及最大加權頂點的理論具有拓展性，在其他行業及領域具有適用性。

參考文獻：

［1］王栓杰， 李華， 陳智博. 基于全局圖遍歷的加權頻繁模式研究［J］. 中國新通信，2016， 18（19）： 155. DOI： 10.3969/j.issn.1673-4866.2016.19.120.

［2］李守杰， 朱益龍， 柏澤鈿. 基于云平臺架構的視頻監視系統技術應用［J］. 城市軌道交通研究， 2021， 24（12）： 190-193. DOI： 10.16037/j.1007-869x.2021.12.039.

［3］趙軍鋒， 莊懷東， 趙亮， 等. 大規模數據并發環境下視頻監控系統的研究與實現［J］. 都市快軌交通， 2016， 29（6）： 11-15. DOI： 10.3969/j.issn.1672-6073.2016.06.003.

［4］甘超瑩， 甘建文， 顧野. 基于圖像識別技術的城市軌道交通車站智能視頻監控系統的設計與應用［J］. 城市軌道交通研究， 2023， 26（2）： 76-80. DOI： 10.16037/j.1007-869x.2023.02.017.

［5］李小斌， 吳宏岐， 袁戰軍， 等. 智能視頻監控系統關鍵技術及算法研究［J］. 控制工程， 2016， 23（S1）： 18-22. DOI： 10.14107/j.cnki.kzgc.150047.

［6］馮凌， 熊德智， 楊華夏， 等. 基于4G網絡的防竊電智能視頻監控終端設計［J］. 自動化與儀表， 2017， 32（8）： 48-52. DOI： 10.19557/j.cnki.1001-9944.2017.08.012.

［7］朱向軍， 毛劍飛， 鮑衛兵. 基于達芬奇技術的智能視頻監控終端的開發［J］. 電信科學，2011， 27（2）： 100-104. DOI： 10.3969/j.issn.1000-0801.2011.02.019.

［8］方浩， 李艾華， 王濤. 基于 DM6437的智能視頻監控系統設計與實現［J］. 計算機應用與軟件， 2016， 33（2）： 192-196. DOI： 10.3969/j.issn.1000-386x.2016.02.046.

［9］梁貴， 滕廣華， 羅傳，等. 基于圖算法的跨攝像頭多目標追蹤技術模型［J］. 電腦知識與技術， 2023， 19（14）： 29-32. DOI： 10.14004/j.cnki.ckt.2023.0742.

［10］孫平安， 譚秋月， 郭進輝. 基于頂點加權有向圖與邊加權圖的景區動態客流統計與預測［J］. 蘇州科技學院學報（自然科學版）， 2012， 29（3）： 61-65. DOI： 10.3969/j.issn.1672-0687.2012.03.012.

［11］蹇冬宇， 程永利. 基于廣度優先遍歷加權圖生成的啟發式圖分區［J］. 計算機系統應用， 2023， 32（12）： 218-223. DOI： 10.15888/j.cnki.csa.009314.

［12］高駿濤. 基于行人重識別和姿態估計的跨攝像頭多目標跟蹤算法研究［D］. 杭州： 杭州電子科技大學， 2022.