基于排队论的跨摄像头乘客轨迹识别方法

摘要：目前摄像头监控视频群组中采用遍历查找搜索全部摄像头视频，或者拓扑网查找重复搜索，导致人员追踪查找效率低、准确性差，为解决这一问题，提出了一种基于排队论和顶点加权有向图的高效选择监控摄像机视频的方法。该方法借鉴排队论理论的原理，将摄像头视为顶点，并构建了一个加权有向图。通过计算权值，能够确定最优的监控路径，同时考虑了摄像头之间的连接和权值。这一方法的关键优势在于高效地选择监控摄像机视频。此外，将城市轨道交通节点目标乘客的最优运动路径与人员追踪相结合，采用了顶点加权有向图的思想，提高了识别的准确性和效率。研究结果表明，通过将排队论和顶点加权有向图理论应用于人员追踪领域，为解决实际问题和提升系统性能提供了一种创新的方法。这一方法对于提升监控系统性能和人员追踪能力具有重要意义。

关键词：排队论；顶点加权；轨迹识别；跨摄像头追踪

中图分类号：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.