李御瑾，张雅丽，葛馨阳，赵佳鑫，施新凯

（中国人民公安大学信息网络安全学院，北京 100038）

0 引言

利用视频监控拍摄的画面判断出现在不同监控中的行人是否是同一个行人并生成其轨迹的技术已经广泛应用于智能视频监控、安保、刑侦等领域。这种运用计算机视觉和机器学习等方法判断监控视频中的特定行人是否出现在其他监控视频中的技术称为行人重识别（person Re-identification，Re-ID）。有学者将行人重识别系统划分为行人检测和行人重识别两部分，行人检测主要应用深度学习的方法对原始图像数据进行训练学习并提取出更有效的特征，基于深度学习的行人检测系统具备极高的鲁棒性和准确率。随着较大规模数据集的出现，深度学习在行人重识别领域的应用研究逐年递增。基于大规模数据集与深度学习的行人重识别方法根据任务不同分为两类，一类是基于图像，一类是基于视频序列。不管是基于图像还是基于视频序列，行人重识别的主要任务都是特征提取和相似度度量两个步骤。

在行人重识别系统的应用中，原始视频帧经过行人检测并提取特征之后与对应帧重新存入特征库。传统的行人重识别系统，其前端摄像头仅能够采集数据并不具备前置的计算处理功能，需要将数据回传至数据中心进行处理。随着边缘计算在行人重识别系统中的应用，系统逐渐从前端采集、后端分析的模式转变为前端智能化、前后端协同计算和软硬件一体化的新模式。

按照功能来说，行人重识别系统在特征提取与相似度度量之间应该还有一个阶段，即确定度量对象。如图1所示，文献［3］提供的行人重识别系统框架中，在特征提取与相似度度量之间加入“确定度量对象”阶段。该阶段的主要任务是从特征库的指定度量范围中检索出进行相似度度量的对象，进行相似度度量的次数与总耗时和所占用算力都成正比关系，因此，缩小检索范围可有效减少度量次数和度量耗时，节约算力。目前主流的行人重识别系统，在提取到待度量目标的特征后，通过遍历度量的方式或按照时间划分检索范围来在特征库中进行相似度度量。城市部署的摄像机数量将会越来越多，尽管单个视频所提取的目标特征信息所占空间不大，但是一个城市每天产生的视频监控数据量将只增不减，根据视频数据所提取的特征库也将随之增大，因此，不论是遍历检索还是按照时间划分度量范围对于行人重识别系统而言都将是一项高耗时、高占用的任务。为了提高度量效率，本文在已有的研究基础上提出一种基于泛洪算法并结合空间信息的检索度量方式，在前端采集数据时通过内嵌全球定位系统（global positioning system，GPS）芯片提供空间信息并回传，在后端将前端所提取的特征与其回传的空间信息进行关联并建立空间信息数据库。应用泛洪算法在进行度量时缩小度量范围，在不损失度量的准确度和完整度的前提下达到提高度量效率的目的，且能有效利用特征所关联的空间信息进行轨迹分析，整体提高行人重识别系统的应用效果。

图1 行人重识别系统

1 基于空间信息的泛洪度量算法

泛洪算法（flooding）在计算机网络领域中是一种路由算法，简单来说是设备群中交换信息的一种协议。分为不受控泛洪与受控泛洪两种。在不受控制的泛洪中，每个节点无条件地将数据包分发给它的每个邻居。如果没有条件逻辑来控制就会产生广播风暴（当广播数据充斥网络无法处理，并占用大量网络带宽，导致正常业务不能运行，甚至彻底瘫痪即为“广播风暴”）。在受控泛洪中有两种算法来避免广播风暴，分别是序列号受控泛洪（sequence number controlled flooding，SNCF）和反向路径转发（reverse path forwarding，RPF）。在SNCF中，节点将自己的地址和序列号附加到数据包中，每个节点都有地址和序列号的存储器。如果它在内存中收到一个数据包，它会立即丢弃它，而在RPF中，节点只会转发数据包。如果它是从下一个节点收到的，它将发送回发送者。

本文应用泛洪算法的受控泛洪原理，在特征库检索中改进该算法，算法主要目的是改进并缩小度量范围。目前主流的行人重识别系统在提取到待度量目标的特征后通过遍历度量的方式或按照时间划分度量范围来在特征库中选取对象进行相似度度量，目标的轨迹在时空上具有一定的相关性，即当目标被一台摄像机拍摄到以后，该目标被另一台摄像机再次拍摄到的可能性与两台摄像机的间距以及两次拍摄时间间隔均成反比，简单来说就是当一台摄像机拍摄到一个目标之后，与该台摄像机相距最近的几台摄像机在较小的时间间隔内再次拍摄到目标的可能性最大。然而，遍历度量或根据时间划分度量范围并没有较好地利用目标轨迹的时空相关性，没有优先选择可能性较大的摄像机提取的特征进行度量，而是对所有摄像机或者指定时间段内摄像机提取的特征进行度量。算法实现方法是充分利用目标轨迹的时空相关性，将度量范围以空间距离和时间间隔进行优先级划分，逐级进行相似度度量。将高优先级的度量范围定义为源点度量，低优先级的度量范围定义为节点度量。算法流程如图2所示，图中左边部分为源点度量，右边部分为节点度量。是源点列表信号量，当为0时源点列表为空，当为1时源点列表不为空。是节点列表信号量，当为0时，节点列表为空，反之亦然。首先将和置为零，分别依次执行源点度量和节点度量，然后检测源点列表和节点列表，如果为空，则返回0。如此循环，直到源点列表和节点列表都为空，和都为0的时候代表度量完成。

图2 算法流程图

由于需要搭建空间信息数据库，因此本文采用mysql进行数据存储。在mysql中建立名为camerafile的数据库，在库中分别建立两张表，一张表是设备档案表（命名为cameraid），另一张是设备距离表（命名为distance_table）。设备档案表中的字段为“Lon”，“Lat”，分别为该设备的经纬度。然后分别对每台设备两两之间计算直线距离，根据结果建立设备距离表。设备距离表中字段为“Orig”、“Dest”和“distance”，“Orig”为源点的设备编号，“Dest”为目标设备的编号，“distance”为两点之间的直线距离。搭建空间信息数据库的前提是获取摄像机的经纬信息以及物理地址信息，两两分别计算直线距离据此建立距离表。定义为与源点摄像机相聚最近的摄像机台数，定义为总度量范围。

在创建空间信息数据库时需提前建立设备档案表以及设备距离表，在输入待度量目标并获取采集该图片的设备编号后，通过泛洪算法（如图3所示）从数据库中的设备距离表中提取出指定范围内的最近个其他设备编号，并设置总度量半径以在这些设备采集的视频数据中进行相似度度量，与两个参数可根据实际情况进行设定。泛洪度量分为源点度量与节点度量。如果在该范围内出现高于阈值的结果则将该节点加入到源点列表，如果没有则加入节点列表，待源点度量结束后再进行节点度量。

图3 泛洪算法示意图

1.1 源点度量

从源点列表中顺序选出一个源点，根据设备距离表计算出与源点相距最近的个节点，然后进行特征相似度计算。如果有节点高于阈值，则将该节点加入到源点列表中，如果个节点都没有高于阈值的节点，则将源点加入到节点列表中，然后从源点列表中顺序选出下一个源点，直到源点列表遍历完，源点度量结束，源点度量示意图如图4所示。

图4 源点、节点度量示意图

1.2 节点度量

从节点列表中顺序选出一个节点，然后计算出与该节点相距最近的个节点并依次进行度量，如果有节点度量成功则将该节点加入源点列表，否则将节点加入次节点列表，然后从节点列表中选出下一个节点，如图5所示。进行完节点度量之后，所有节点被分别加入源点列表和次节点列表。如果次节点列表不为空，则将次节点列表赋值给节点列表重新进行节点度量。直到节点列表遍历完，节点度量结束。此时，分别检测源点列表与节点列表，直到源点列表与节点列表均为空，即在指定区域内无法再计算得出新的节点。

图5 节点度量示意图

泛洪算法是根据源点最近的点位进行度量，单次最大摄像头数量越多，则单次搜索半径越大，总搜索时间增加。总搜索半径是预先设置的总搜索区域，算法中体现为以初始源点为圆心的总搜索半径，凡是超过该搜索范围的其他节点均不会被度量。

2 实验及结果分析

本文在行人检测部分使用的是YOLOv3目标检测算法，并且使用YOLO416 COCO权重。在行人重识别部分是在Bag of Tricks and A Strong ReID Baseline的开源代码基础上进行改进。训练部分将MSMT17数据集、Market1501数据集和CUHK03数据集进行了联合训练，然后在没有进行训练的DukeMTMC27数据集进行测试，测试效果满足使用需求。本文实验共设置两组实验模型，一组使用空间信息并结合泛洪算法进行度量，另一组使用遍历算度量方式。

2.1 实验数据

2.1.1 空间信息数据

本文所提出的方法主要应用于缩小度量范围，对于监控设备数据要求的经纬度。由于目前还未大规模部署内嵌GPS芯片的网络摄像机，因此从无锡市城市管理局发布的《无锡市城市管理视频监控系统点位调整信息公示》中获取到无锡市部分监控点位的物理位置和经纬度原始数据，处理后得到图6。

图6 部分监控点位原始数据

空间信息数据库创建两张表，一张表是采集设备档案表，另一张是设备距离表。由于从无锡市城市管理局所收集到的监控点位信息并没有对摄像机进行编号，因此将每一台设备进行编号，并输入其物理位置与经纬度信息。然后对每一台采集设备建立设备档案表并存入mysql数据库中，如图7（a）所示；对每台设备两两之间根据经纬度计算直线距离，根据结果依次建立设备距离表，如图7（b）所示。

图7 设备档案表与设备距离表

2.1.2 视频图像数据

视频数据使用在校园录制的模拟街道监控视频，录制设备为索尼HDR-CX405，随机选取校园道路五个位置架设高约3 m的三脚架进行录制，共计403段，平均每段有5 s，由151帧构成，行人监控截图如图8所示。本文分别将某台设备所采集的视频放置在该设备编号命名的文件夹中，其中视频的命名格式为（摄像机编号_视频编号），监控点位共有311个，随机从403段中抽取10段依次放置于编号文件夹中，相当于总视频库中共有3110个监控视频。

图8 行人监控示意图

2.2 评价指标

为了验证算法对特征库进行泛洪度量的有效性，本文设置了四个评价指标，分别是度量次数、度量准确度、度量完整度以及度量时间。度量次数越少对计算机的算力占用越低，在度量准确度相同的情况下度量时间越短则度量效率越高。度量准确度与度量完整度的定义如下：

度量准确度=度量到的相关视频数/总度量视频数

度量完整度=度量到的相关视频数/库中实际相关视频数

2.3 实验环境及参数设置

2.3.1 实验环境

本实验的操作系统为Microsoft Windows 10（64位）,CPU型号为（英特尔）Intel（R）Core（TM）i7-10750H CPU@2.60GHz（2592 MHz），本实验使用一块NVIDIA GeForce RTX 2060（6144 MB）显卡，使用pytorch 1.7.1以及tensorflow-gpu 2.1.0作为深度学习框架，依赖Python 3.7.1环境完成编程。

2.3.2 参数设置

实验中先将一组节点设置为目标轨迹路线，然后分别调用泛洪度量与遍历度量从起始节点的视频监控开始度量，并将度量结果与设置的目标轨迹路线进行比较。本次实验将待度量目标设置为身穿深蓝色短袖和黑色长裤的行人，如图9中（a）所示。

图9 目标与度量成功示意图

2.4 实验结果与实验分析

为验证泛洪算法的有效性，本文设置三个对照试验，共计十五组。在泛洪算法中需设置单节点最大摄像机数和最大度量半径，最大摄像机数以及最大度量半径的取值取决于监控点位的密集程度，在监控点位密集区域最大摄像机数和单节点最大搜索半径应设置较小，单次度量总量小能够提高度量速度，而在监控点位稀疏的地区二者均可以设置较大半径，增加单次度量数量以提高度量效率。如果度量成功则会标记目标并输出该节点视频，如图9中（b）所示。

实验对象：第一组至第五组

不变量：轨迹节点（节点间距均小于1 km）、泛洪算法参数设置（最大摄像机数设置为5（=5），单节点最大搜索半径设置为1 km（=1））

变量：分别使用泛洪算法与遍历算法

实验目的：验证泛洪算法的有效性

实验结果见表1

表1 实验一结果

实验分析：在该五组实验中，轨迹节点平均间距在1 km以内。对于视频图像库而言度量时间主要取决于度量次数。遍历度量的范围始终为全库共计3110段视频，因此其度量次数、度量时间、度量准确度与度量完整度都不变，采用泛洪算法之后视频的平均度量次数会减少，如图10所示，度量出相似视频图像的时间大幅缩短，如图11所示。在度量完整度相同的情况下，泛洪算法结果，平均准确度为27.63%，平均度量次数为19.2次，平均度量时间为239.68 s，而遍历算法结果的平均准确度为1.61%，平均度量次数为3110次，平均度量时间为2139.26 s。

图10 实验一度量次数

图11 实验一度量时间

实验结论：当轨迹节点平均间距在1 km以内时，在完整度相同的前提下，泛洪算法的准确度、度量次数和时间均优于遍历算法。

实验对象：第一组至第十组

不变量：前五组沿用第一组实验结果，泛洪算法参数设置（最大摄像机数设置为5（=5），单节点最大搜索半径设置为1 km（=1））

变量：第一组至第五组的平均间距较小（在1 km左右）、第六组至第十组平均间距较大（在1 km以上）

实验目的：分析节点平均间距对泛洪算法的影响

实验结果见表2。

表2 实验二结果

实验分析：在前五组实验中，轨迹节点平均间距在1 km以内；后五组中平均间距大于1 km。十组实验中泛洪算法的参数设置都相同（即最大摄像机数和单节点最大度量半径都相同），当节点平均间距增大之后，对于未改变参数设置的泛洪算法，其度量准确度与完整度均有所下降，如图12所示。前五组泛洪算法结果：平均准确度为27.63%，平均度量次数为19.2次，平均度量时间为239.68 s，后五组结果平均为度量完整度为60%，度量准确度为14.68%，度量次数为23次，度量时间为286.26 s；前五组遍历算法结果为平均准确度为1.61%，平均度量次数为3110次，平均度量时间为2139.26 s，后五组遍历算法结果为平均准确度为1.61%，平均度量次数为3110次，平均度量时间为2146.50 s。

图12 实验二度量完整度

实验结论：在泛洪算法的参数设置为（最大摄像机数设置为5（=5），单节点最大搜索半径设置为1 km（=1）），当轨迹节点平均间距大于1 km之后，泛洪算法的准确度、完整度明显降低，度量时间与度量次数均明显增加，可见平均节点间距对泛洪算法有直接影响，对遍历算法无较大影响。

实验对象：第六组至第十五组

不变量：第六组至第十组沿用实验二结果，轨迹节点均相同

变量：第六组至第十组泛洪算法设置参数为最大摄像机数设置为5（=5），单节点最大搜索半径设置为1 km（=1）；第十一组至第十五组设置参数为最大摄像机数设置为5（=5），单节点最大搜索半径设置为2 km（=2）

实验目的：分析泛洪算法中单节点最大搜索半径对算法影响

实验结果见表3。

表3 实验三结果

实验分析：十组实验的轨迹节点都相同，平均间距在1 km以上，前五组的单节点最大搜索半径为1 km（=1），后五组单节点最大搜索半径为2 km（=2）。通过增大泛洪算法单节点最大搜索半径，能够有效地提高泛洪算法的度量完整度，如图13所示。

图13 实验三泛洪算法度量完整度

前五组泛洪算法的结果平均为度量完整度为60%，度量准确度为14.68%，度量次数为23次，度量时间为286.26 s，后五组结果平均为度量完整度为100%，度量准确度为8.11%，度量次数为64次，度量时间为868.31 s。

表4 遍历算法度量时间

实验结论：轨迹节点平均间距大于1 km之后，通过调节泛洪算法的单节点最大搜索范围能够提高完整度，但准确度会降低，度量次数和度量时间增加。在相同度量完整度的情况下，通过对比调节参数前后的度量时间，可以得出虽然增大了单节点最大搜索半径会增加度量时间，但为了获得较高的度量完整度，度量尽量多的目标，增加的度量时间仍远远少于遍历度量的时间，如图14所示。

图14 实验三度量时间比较

3 结语

本文提出一种结合空间信息并以泛洪算法为基础的改进度量方法。该方法将空间信息与特征建立关联，在行人重识别系统进行相似度度量时，有效利用目标轨迹的时空相关性并根据特征关联的空间信息来缩小度量范围，快速度量目标特征。实验结果表明，在度量出所有目标特征的情况下泛洪算法的度量时间与度量次数均优于遍历算法；而在牺牲度量完整度的情况下，泛洪算法能够更快速地度量出目标特征。如果增加单点最大度量范围，则会增加度量次数与时间，但能够提高泛洪算法的度量完整度。结合空间信息的泛洪算法在行人重识别系统中的应用能够协助民警在公安工作中迅速检索度量出目标并得出其轨迹路线。此外，对于任何在原始数据中能够提供空间信息的数据均能够使用本方法进行快速度量，例如在全球新冠病毒肆虐的背景下，使用本方法能够迅速度量目标，对于快速进行精准高效的流调工作、及时排查风险、消除隐患具有重要意义。