基于视频监控网络模型的行人搜索跟踪策略研究

蔺志宇，陈国良

(武汉理工大学 机电工程学院，湖北 武汉 430070)

跨境追踪过程中，监控视频的关联性及分析机制上的研究尚显不足，在监控视频间关联方法研究中，主要有以下两种思路：①直接建立监控视频间的拓扑网络或者图模型[1]，文献[2]依据监控点间的临近关系来构建该模型；也有研究基于拓扑学习的方法，依据路径统计结果构建监控视频间拓扑网络[3]。这种思路构建的模型结构较为简单，拓扑模型可直接将监控视频联系起来，缺点是当监控点分布环境较为复杂时，拓扑模型无法完全描述监控点间的联络关系。②将视频监控系统和地理信息系统GIS(geographic information system)相结合构建模型[4-6]，该模型将监控点映射到地理空间中，可以实现监控视频有效管理，且更易适应搜索跟踪算法。在目前的研究中，该方法主要应用于大型商场等场景中，应用范围相对较窄。基于构建的模型对目标对象进行跟踪搜索的相关算法研究主要集中于两个方面：①移动对象在监控点间转移路线判定算法研究，有部分算法直接依赖拓扑网络中的邻接关系进行扩展排查[7]；也有部分方法基于统计数据对目标对象在拓扑网络节点间的转移概率进行判定[8]，确定最优搜索路径，该方法搜索效率较高，但是依赖于大量数据，适应性较差。②移动对象在监控点间的转移时间预判算法，文献[2]依据大量历史数据建立高斯混合模型，利用该模型预测下一个监控点目标出现的时间区间，进而在相应时间段内完成搜索任务，该算法可以避免噪声干扰，但是由于监控数据不易获取，导致建立的模型适应性较差。

笔者将视频监控节点通过线性参考系统LRS(linear referencing system)坐标定位于拓扑地图中，构建视频监控网络模型并改进邻接表对模型进行存储；然后以该模型为基础，提出基于广度优先搜索算法和深度优先搜索算法的目标搜索跟踪策略；最后建立模型验证算法的有效性和跟踪搜索框架的可行性，并利用该搜索策略模拟完成行人的搜索跟踪实验。

1 基于LRS坐标的监控点定位及存储

线性参考系统(LRS)是一种利用沿着可测量线要素的相对方位来存储地理位置的方法，其定位要素由所属路径、度量、事件构成[9]。可采用LRS坐标将监控节点定位于拓扑地图中。

在拓扑地图中对监控节点进行定位，所属路径要素为其在拓扑地图中的所在弧段。度量要素为监控点距离拓扑地图上较近节点的距离。某些建筑物出入口或者路径为单向的，其对应监控点只会记录单向移动对象，因此将事件要素定为方向属性，即单向S，或多向M。监控节点在拓扑地图中的坐标表示为：nwk(li,j,ni,si,k,D)，nwk为监控节点；li,j表示所属路径要素；ni和si,k共同表示度量要素，分别代表在弧段li,j上距离监控节点nwk较近的节点和两点间对应的距离；D代表方向，指明单向S或多向M。监控节点在拓扑地图中的分布位置示意如图1所示。

图1 监控节点在拓扑地图中的分布位置示意

监控节点在拓扑地图中的位置可分成两个类别: 位于弧段上，不与普通节点重合; 与普通节点重合，如图1 所示。具体到坐标，对于类型Ⅱ，其所属路径为null，距离要素的值为0。两种情况下监控节点的坐标表示分别为: nw1 ( li，j，ni，si，1，D)和nw2 ( null，nj，0，D) 。

通过LRS坐标将视频监控节点在拓扑地图中定位，构成视频监控网络模型，其模型如下：

H=(N,L,W)

(1)

N={n0,n1,n2…}

(2)

L={…,lij,…}

(3)

W={nw0,nw1,nw2,…}

(4)

式中：H为拓扑网络；N为节点的集合；L为节点间中经的集合；W为监控节点集合。

图2为监控网络模型图。

图2 视频监控网络模型图

视频监控网络模型可以通过改进的邻接表来进行存储，相比于普通邻接表，其改进主要为以下两个部分：

(1)依据监控节点分布类型，增添标志位，标明邻节点是否同时为监控节点(类型Ⅱ)，标明对应弧段上是否有监控节点(类型Ⅰ)。

(2)增添监控节点坐标位，依据(1)中标志位设定对应监控节点坐标。

图3为改进邻接表示意图，其中FL为标志位，由两位2进制数表示；CW为监控节点坐标位，存储两种监控节点坐标。标志位FL及监控节点CW设定及含义如表1所示。

图3 改进邻接表节点设计

表1 标志位FL及监控节点CW设置

2 视频监控网络模型下的目标搜索算法

2.1 监控邻域及总体搜索框架

在视频监控网络模型中，以点Q为起始节点，目标对象沿任意路径Rk移动均会遇到一监控节点nwk，任意路径Rk可构成集合Rψ，对应全体监控节点nwk可构成集合Vψ，定义Rψ和Vψ的合集Oψ为节点Q的监控邻域。监控邻域的数学表达如下：

Oψ=(Rψ，Vψ)

(5)

(6)

(7)

(8)

在视频监控网络模型中对目标对象搜索跟踪，搜索框架如下：

步骤1从起始节点开始，获取其监控邻域，划定监控邻域中所包含监控节点的搜索优先级；

步骤2计算步骤1中监控节点相应监控视频的搜索时间段；

步骤3依据步骤1划定的搜索优先级和步骤2得到的搜索时间段，对相应的监控视频进行搜索，当搜索到目标对象时停止继续搜索；

步骤4以步骤3中搜索到目标对象的监控节点为新起始节点，重复步骤1～步骤3，直至目标对象消失为止，结束搜索跟踪。

2.2 监控邻域获取算法

获取节点Q的监控邻域Oψ，即为获取Oψ包含的监控节点集合Vψ以及节点Q到Vψ中每一个监控节点的路径集合Rψ。利用广度优先搜索算法BFS(breadth first search)[10]获取集合Vψ， 具体步骤如下：

步骤1建立容器vector和队列queue，分别用于存放监控节点和普通节点。设起始节点为当前结点Q，建立全局节点访问状态数组vis，点Q对应数组值置1，其余数值初始化为0，查询邻接表获取当前结点的邻节点(若Q为类型Ⅰ，则直接指定其邻节点为弧段端点)，判定每个邻节点和当前节点Q间是否有监控节点，若有，则将该监控节点添加至vector中；若无，则判定邻节点是否同时为监控节点，若是，则将该监控节点添加至vector中，若否，则将该邻节点存储于队列queue中；

步骤2将队列queue中的节点依序取出，依次作为当前结点，重复步骤1，操作完成后将其从队列queue中弹出，并将其状态数组值置1。注意，在重复步骤1向vector和queue中添加节点时，判定其状态数组值是否为1，如果为1，则不添加，避免重历；

步骤3重复步骤2，直到队列queue为空，无法继续扩展搜索为止，此时容器vector中存放全部监控节点即构成集合Vψ。

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

步骤2继续建栈。从辅栈中取出集合NQ的第一个节点nQ1(栈顶元素)，压入主栈，并将nQ1弹出辅栈。然后查询邻接表将nQ1的相邻节点集合Nnq1压入辅栈，此时主栈、辅栈元素继续增多。将Nnq1压入辅栈时要对每一个元素进行判定，若其对应状态数组值为1，则不作为Nnq1元素压入辅栈，压入辅栈的节点对应状态数组值置1；

步骤3削栈。重复步骤2，并且判定主栈元素构成路径中是否出现其余监控节点，若包含，则将栈顶节点弹出，若循环至辅栈栈顶为空集时，此时无法再继续建栈，将主栈栈顶元素弹出，同时将辅栈栈顶空集弹出，搜索其余支路；

然后找出起始节点Q到集合Vψ中第1个监控节点nw1的全部路径，即集合R1，如步骤5。

步骤5重复步骤4，主栈元素构成路径中出现目的节点nw1，则削栈，同时保存路径，直至主栈为空时结束搜索，此时VR1中保存的全部路径构成集合R1；

步骤6对集合Vψ中的全部监控节点轮循执行步骤1～步骤5，得到全部的集合Ri，其合集即为Rψ。

2.3 搜索优先级的划定

起点Q到其监控邻域中各个监控节点的路径数目不同，则目标对象移动时经过这些监控节点的概率不同。从起点Q出发，通向某一个监控节点的路径数目越多，则目标对象向该监控节点移动的概率越大。基于此原理，依据式(9)的计算方法划定搜索优先级。

Pk=NRk/NRψ

(9)

式中：NRk为从起始节点通向其监控邻域中第k个监控节点全部路径集合Rk中的元素数量；NRψ为从起始节点通向其监控邻域中全部监控节点路径集合Rψ中的元素数量；Pk即为通向第k个监控节点的概率，其值越大，则搜索优先级越高。

2.4 监控视频搜索时间区间的确定及优化

目标对象从当前节点向监控邻域中的监控节点移动时，可对其在下一个监控点出现的时间点进行预判，以确定对应监控视频的检测时间点。目标对象到达下一个监控节点的时间区间，可采用式(10)～式(13)计算：

(10)

(11)

(12)

(13)

通过以上计算可以得到目标对象在监控点开始出现的时间区间，若目标对象在该时间区间内未出现，则认为目标对象未经过该节点。

目标对象从起始节点Q移动至其监控邻域中任意一个监控节点，若存在多条路径，则相应的出现时间区间也就有多个，并且这些时间区间可能相互重合，为了避免对一段监控视频重复检测，提出时间区间组合优化算法如下：

步骤1区间排序。将所有时间区间依照区间左端进行升序排列，建立容器VT存放组合之后的时间区间；

步骤2区间组合。从头开始，先将前两个区间进行组合，设两区间组合之后的临时区间为[l,r]，若两个区间分别为[a,b]，[c,d],则存在以下两种情况：

(a)c>b,即两个区间不存在交集，则不进行合并，将前一个区间[a,b]保存至容器VT中，组合之后的临时区间l=c,r=d;

(b)c≤b，则判断b，d两值大小，若b≥d，则组合之后的临时区间l=a,r=b;若b

步骤3用临时区间[l,r]和后序的时间区间继续进行组合，循环步骤2，直至最后一个时间区间组合完成，此时容器VT中存放的时间区间即为最终的时间区间集合。

3 实验及分析

图4是根据某学校实际地理信息和监控点安置情况构建对应的视频监控拓扑网络图，行人移动信息均来自真实的轨迹数据。图4标注了102个普通节点和40个监控节点，路径长度信息通过网络地图可以获取。

3.1 监控邻域获取算法的验证

从图4中截取网络的一部分来对算法进行验证分析，如图5所示。图5中白色节点为普通节点，直接用数字标记，例如30号节点，代表普通节点n30；图5中带nw标记的黑色节点分布于弧段，只为监控节点；其余用数字标记的黑色节点和普通节点重合，即是监控节点，也是普通节点，例如27号节点，同时代表普通节点n27和监控节点nw27。

图5 监控邻域获取算法验证网络图

设定32号节点为起始节点Q，现根据提出算法获取其监控邻域。

首先验证监控邻域中监控节点的获取算法。表2为搜索过程中每一次循环队列queue和容器vector存放节点状态变化情况，最后一次循环后，queue变为空队列，vector中存放的监控节点即为监控邻域中包含的全部监控节点。

再验证监控邻域中从起始节点Q到其监控邻域中每一个监控节点的路径集合获取算法，在表2所示的实验中，已经获取的监控邻域中的监控节点有44,nw34,28,nw43,45,47,27,33,24,27,16,14,22，共计13个。现以点Q(32号节点)到22号节点为例，求取两节点间全部路径。

表2 实验过程中queue和vector存放状态变化表

路径搜索过程中主栈和辅栈部分关键变化的情况如表3所示。从表3可知从32号节点到22号节点只有一条路径，在第14次循环时找到。

表3 实验过程中主栈和辅栈存放状态变化表

3.2 总体搜索框架的验证和分析

查阅相关数据，平直路面上，行人速度为v=1.1～1.5 m/s，将随机误差设为10 s。

模拟系统验证的步骤如下：

步骤1事先收集搜索跟踪对象的轨迹信息，记录其到达各个监控点的时间点；

步骤2确定搜索跟踪对象的起始节点，作为第一个当前节点，利用本文算法确定其监控邻域和其中监控点的搜索时间段；

步骤3判定真实数据中的时间点是否在计算出的搜索时间段内，如在，则匹配成功，接下来以得到匹配的监控点为起点进行下一次搜索跟踪，重复步骤2和步骤3，直到匹配不到或者搜索到轨迹尽头为止，则该次实验结束。

以其中一次实验为例对上述方法进行解释，如图6所示，深色标记的是某一条实际的行人轨迹，该人从66号楼走向了图书馆，其经过的普通节点、监控节点以及每一个包含途经监控节点的监控包围圈的信息如表4所示。

图6 某次实验行人路径图

表4 跟踪搜索节点变化表

从表4可知，每一个当前节点的监控邻域中包含了下一个路径上出现的监控节点。

3.3 实验效果和算法评价

与传统直接建立在监控点间的拓扑网络模型进行对比实验，共进行10条行人轨迹的实验验证。

图7为10次实验的统计结果，从图7可知，有部分实验没有完全追踪成功，主要原因为：①本实验设定行人行走于平直路面上，且只考虑行人是正常行走，没有考虑跑动等情况，这导致对行人出现在监控点的时间段计算存在未考虑的误差；②本实验标注的监控点及路线有限，当追踪对象走向地图边缘或未标注路径时就会导致追踪失败，即使行人后期再回到地图标注范围内，也无法继续实现追踪。针对第一种情况，只要依据实际情况调整误差估计，就可以使得实验效果得到改善；针对第二种情况，将网络标注细化，即可避免。经计算，10次追踪试验的综合成功率为88.14%。

4 结论

笔者针对在监控系统中对目标对象搜索跟踪时的效率低下问题，提出一种基于视频监控网络模型的搜索策略。实验表明，该搜索策略可有效完成对目标对象连续搜索跟踪，相比直接建立在监控点间的监控网络模型及只依赖广度优先搜索算法进行对象的跟踪搜索，其可以划定搜索优先级，有效提升搜索效率，并且不必依赖大量数据，适应性更强，跟踪节点成功率在80%以上，性能较为优异。