留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种监控摄像机网络-路网覆盖优化调度方法

高飞 王美珍 刘学军 王自然

高飞, 王美珍, 刘学军, 王自然. 一种监控摄像机网络-路网覆盖优化调度方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(3): 362-373. doi: 10.13203/j.whugis20180247
引用本文: 高飞, 王美珍, 刘学军, 王自然. 一种监控摄像机网络-路网覆盖优化调度方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(3): 362-373. doi: 10.13203/j.whugis20180247
GAO Fei, WANG Meizhen, LIU Xuejun, WANG Ziran. A Road Network Coverage Optimization Method in Surveillance Camera Network[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 362-373. doi: 10.13203/j.whugis20180247
Citation: GAO Fei, WANG Meizhen, LIU Xuejun, WANG Ziran. A Road Network Coverage Optimization Method in Surveillance Camera Network[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 362-373. doi: 10.13203/j.whugis20180247

一种监控摄像机网络-路网覆盖优化调度方法

doi: 10.13203/j.whugis20180247
基金项目: 

国家重点研发计划 2016YFE0131600

国家自然科学基金 41771420

江苏省高等学校自然科学研究面上项目 18KJB170007

江苏高校优势学科建设工程 164320H116

江苏省研究生科研与实践创新计划 KYCX17_1067

详细信息

A Road Network Coverage Optimization Method in Surveillance Camera Network

Funds: 

The National Key Research and Development Program of China 2016YFE0131600

the National Natural Science Foundation of China 41771420

the Natural Science Research in Colleges and Universities in Jiangsu Province 18KJB170007

the Priority Academic Program Development of Jiangsu Higher Education Institutions 164320H116

the Postgraduate Research and Practice Innovation Program of Jiangsu Province KYCX17_1067

More Information
    Author Bio:

    GAO Fei, postgraduate, specializes in video-GIS, intelligent optimization algorithm. E-mail: gaofei_gis@163.com

    Corresponding author: WANG Meizhen, PhD, associate professor. E-mail: wangmeizhen@njnu.edu.cn
图(11) / 表(1)
计量
  • 文章访问数:  1190
  • HTML全文浏览量:  166
  • PDF下载量:  84
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-06-21
  • 刊出日期:  2020-03-05

一种监控摄像机网络-路网覆盖优化调度方法

doi: 10.13203/j.whugis20180247
    基金项目:

    国家重点研发计划 2016YFE0131600

    国家自然科学基金 41771420

    江苏省高等学校自然科学研究面上项目 18KJB170007

    江苏高校优势学科建设工程 164320H116

    江苏省研究生科研与实践创新计划 KYCX17_1067

    作者简介:

    高飞, 硕士生, 主要从事视频GIS、智能优化算法研究。gaofei_gis@163.com

    通讯作者: 王美珍, 博士, 副教授。wangmeizhen@njnu.edu.cn
  • 中图分类号: P208

摘要: 针对监控摄像机网络-路网的覆盖优化问题,提出了一种面向多优化目标的摄像机网络调度优化方法。该方法根据摄像机的感知特性,通过引入主光轴缓冲区系数来划分摄像机主光轴方向的活动范围,进而动态控制摄像机的调度规模及对特定摄像机、路段的覆盖应用偏好,并利用粒子群优化算法对路段覆盖数量、路网覆盖长度和摄像机调度数量等多个优化目标进行协同优化。实验结果表明,该方法具有较好的有效性和鲁棒性,同时考虑多个覆盖优化目标时,其可以提供摄像机网络的调度优化方案集合。

English Abstract

高飞, 王美珍, 刘学军, 王自然. 一种监控摄像机网络-路网覆盖优化调度方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(3): 362-373. doi: 10.13203/j.whugis20180247
引用本文: 高飞, 王美珍, 刘学军, 王自然. 一种监控摄像机网络-路网覆盖优化调度方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(3): 362-373. doi: 10.13203/j.whugis20180247
GAO Fei, WANG Meizhen, LIU Xuejun, WANG Ziran. A Road Network Coverage Optimization Method in Surveillance Camera Network[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 362-373. doi: 10.13203/j.whugis20180247
Citation: GAO Fei, WANG Meizhen, LIU Xuejun, WANG Ziran. A Road Network Coverage Optimization Method in Surveillance Camera Network[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 362-373. doi: 10.13203/j.whugis20180247
  • 监控摄像机作为物联网、智慧城市和对地观测传感网中重要的传感器,因其实时性好、现势性强、可靠性高等优势,在社会安防、智能交通、环境监测等领域发挥了重要作用。在实际应用中,监控摄像机被广泛部署于具有行驶方向的路网中的交叉路口,并以行人和车辆作为主要的监控目标,由于两者的运动方向和轨迹极大地受到路网的约束,因此摄像机网络-有向路网的覆盖优化是视频监控系统建设中的重点问题,也是当前学术界关注的热点之一。尽管当前各大城市已经构建了较为完备的监控摄像机网络,但是由于实际应用场景及需求的多样性和多变性,监控摄像机网络的机动性和灵活性也面临着更大的挑战,要求能够充分分析和利用现有监控资源并进行有效调度,以实现面向不同监控任务的覆盖优化,同时也为新增摄像机的部署提供重要的决策参考。

    摄像机网络-有向路网的覆盖优化主要分为构建覆盖优化目标模型和优化求解两个关键步骤[1-2]。当前研究围绕覆盖优化目标建模取得了诸多创造性成果,如栅栏覆盖[3]k重覆盖[4]β-QoM覆盖[5]、全视野覆盖[6]等。强栅栏覆盖是指移动目标沿任意路径穿越目标窄带区域时,都至少可以被一个摄像机感知,而弱栅栏覆盖可以感知移动目标沿垂直于窄带区域方向的穿越行为;k重覆盖强调在目标区域的任意位置处都至少有k个摄像机可以进行感知;β-QoM覆盖以栅栏覆盖的监控质量为重点,保证移动目标在任意摄像机中的成像宽度至少为β;全视野覆盖则关注从不同角度感知移动目标在目标区域的穿越行为,以便获取更加全面、多样的监控信息。在此基础上,针对不同的覆盖优化目标也设计了多种优化方法进行求解,例如投票算法[7]、基于几何和图论的方法[8-9]、贪婪策略[10]、虚拟势场[11]以及多种启发式算法,其中以粒子群优化算法[12]、遗传算法[13]、模拟退火算法[14]等最为典型。启发式算法因其自适应性好、鲁棒性强、全局优化性等特点,已经成为了主要的优化求解方法之一。

    因此,在当前研究中已经针对特定的监控需求构建了相应的覆盖优化目标模型,并采用不同的优化方法进行覆盖优化方案的求解。但是,上述研究都是基于特定的单一优化目标,而在实际应用中,摄像机网络-有向路网的覆盖优化往往受到多方面因素的约束,采用单一优化目标模型可能无法支持对监控效果的全面评价,导致其优化结果难以应用于实际场景。因此,为了能够实现有效的覆盖优化,需要建立多目标的覆盖优化目标模型。

    针对多目标优化问题,目前主要有两种处理策略:(1)通过加权将多目标优化问题转化为单目标优化问题进行求解[15];(2)在单一目标最优化的约束下,求解其他目标的最优解[16]。从本质上讲,这两种策略都局限于对单一目标的最优化,因而难以在多目标之间进行有效协调。综上所述,亟需建立一种能够面向复杂有向路网、协同多个覆盖优化目标、充分调度现有监控资源的摄像机网络调度优化方法。

    对于通用性的监控任务,增加路网的覆盖长度可以增加监控目标的暴露时间,增加路段的覆盖数量可以增加监控目标被捕捉的概率,因此这两个优化目标是评价监控质量最重要的方面。同时,考虑到监控资源的有效性和经济性,摄像机的调度数量也应当是摄像机网络覆盖优化问题的重要因素。因此,本文以路段覆盖数量、路网覆盖长度和摄像机调度数量作为覆盖优化目标,提出了一种面向多优化目标的摄像机网络调度优化方法。为了实现只改变摄像机的主光轴方向即可对多个优化目标进行统一控制和协同优化,将摄像机是否被选中参与调度的离散目标空间映射到主光轴方向的连续目标空间,同时有效地体现决策者对特定摄像机和路段的覆盖应用偏好,本文引入了主光轴缓冲区系数来划分摄像机主光轴方向的活动范围,通过判断当前主光轴方向所在的区间来决定摄像机的调度性,从而动态控制摄像机的调度规模和覆盖情况,并利用改进粒子群优化算法求解摄像机网络的调度优化方案集合。

    • 一般来说,监控摄像机主要有枪型摄像机(静态摄像机)和平移倾斜变焦(pan-tilt-zoom,PTZ)摄像机两种。其中,枪型摄像机一旦安装, 其视域范围固定; 而PTZ摄像机虽然某一时刻视域范围固定, 但一般可以通过调节其焦距、旋转角、俯仰角等参数来实现动态监控与目标跟踪。摄像机某一时刻的实际视域范围是一个三维截头棱锥。为了简化问题,本文采用扇形模型表达摄像机的二维视域,则摄像机的覆盖模型可以抽象为一个4元组G=F (P, m, θ, R),其中P表示摄像机的平面位置(x, y), m表示摄像机的主光轴方向,θ表示摄像机的视域角,R表示摄像机的视域半径。如图 1所示,摄像机1为PTZ摄像机,摄像机2和3为枪型摄像机,当前主光轴方向由红色矢量线表示,视域范围由灰色扇形表示。由于本文关注摄像机网络的调度优化,并不涉及其布局优化,因此摄像机的平面位置P保持不变,同时本文假定摄像机在其初始部署完成后,θR均为定值。由摄像机的感知特性可知,枪型摄像机的主光轴方向始终保持不变,而PTZ摄像机的主光轴方向可以在图 1中圆形虚线所示的范围内进行调整, 以实现覆盖优化。

      图  1  摄像机网络-有向路网有效覆盖模型

      Figure 1.  Valid Coverage Model of Camera Network and Directional Road Network

    • 本文采用节点-弧段模型对有向路网进行表达,根据路段是否对移动目标有单向性约束将其分为有向路段和无向路段。其中,有向路段只允许由起点至终点的单向运动,而无向路段则对目标沿路段的运动不做约束。如图 1中点ABCDEFGHIJ表示路段节点,无向虚线段A-BA-DB-CD-E为无向路段,有向实线段B-EE-FF-IF-GG-CG-JH-DH-II-J表示有向路段。

    • 在实际应用中,针对不同的场景和监控任务,摄像机的成像角度往往需要满足特定的约束,此时就需要对摄像机与有向路网覆盖的有效性进行界定。由于路网的拓扑关系相对固定,约束着移动目标的运动方向和轨迹,由此可以利用摄像机视线方向与路段方向的夹角来定义有效覆盖。另外,针对摄像机网络的调度优化方案,并不需要所有有条件的摄像机都参与,因此就需要设计一种能够动态控制摄像机调度状态的策略。针对这两方面的问题,本节将对有效覆盖的相关概念进行定义,并提出主光轴缓冲区系数来划分摄像机主光轴的活动范围,进而实现对摄像机网络调度规模的有效控制。

      定义1  有效视线:摄像机可以对目标路网有效覆盖的视线矢量集合,记作X。有效视线对应的坐标方位角区间称为有效视线范围,记作(αx_min, αx_max)。对于PTZ摄像机,有效视线X={x| < x, r>≥τ, rR},其中x表示摄像机的视线矢量,r表示路段矢量, < x, r>表示二者的夹角,τ表示夹角阈值,R表示路网矢量;对于枪型摄像机,$X = \{ \mathit{\boldsymbol{x}}|\left\langle {\mathit{\boldsymbol{x}}, \mathit{\boldsymbol{r}}} \right\rangle > \ge \tau, {\alpha _x} \in \alpha \left(\theta \right), \mathit{\boldsymbol{r}} \in \mathit{\boldsymbol{R}}\}$,其中αx表示正北方向与视线矢量的坐标方位角,α(θ)表示当前视域对应的坐标方位角区间。如图 1φ表示PTZ摄像机1在有向路段H-D上的有效视线范围,φ′表示枪型摄像机2在无向路段A-B上的有效视线范围,而φ″虽然满足夹角阈值约束,但因其不在初始视域范围中,所以不是有效视线范围。同理,枪型摄像机3在有向路段G-C上无有效视线范围。由此,可以通过设置τ来决定摄像机与有向路网覆盖的有效性及范围,且当τ= 0°时,表示无成像角度约束。

      定义2  有效主光轴:有效视线对应的主光轴集合,记作Mv。有效主光轴对应的坐标方位角区间称为有效主光轴范围,记作(αm_minαm_max)。对于PTZ摄像机,${M_v} = \{ \mathit{\boldsymbol{m}}|{\alpha _\mathit{\boldsymbol{m}}} \in \left({{\alpha _{\mathit{\boldsymbol{x}}\_{\rm{min}}}} - \theta /2, {\alpha _{\mathit{\boldsymbol{x}}\_{\rm{max}}}} + \theta /2} \right)\} $,其中m表示主光轴方向矢量;对于枪型摄像机,${M_v} = \{ \mathit{\boldsymbol{m}}|\mathit{\boldsymbol{m}} = {\mathit{\boldsymbol{m}}_0}, X \ne \emptyset \} $,m0表示初始主光轴方向。如图 1中黄色扇形范围,PTZ摄像机1在有向路段H-D上的有效主光轴范围为[φ-θ/2,φ+θ/2],而枪型摄像机2在无向路段A-B上的有效主光轴即为其初始主光轴方向。

      定义3  主光轴缓冲区:以PTZ摄像机有效主光轴范围的区间长度为单位,对区间上限和下限按照一定的倍数进行扩大,所得到的主光轴方向的扩大区间,记作Mb。这个扩大的倍数称为主光轴缓冲区系数,记作k,即${M_b} = \{ \mathit{\boldsymbol{m}}|{\alpha _\mathit{\boldsymbol{m}}} \in \left({{\alpha _{\mathit{\boldsymbol{m}}\_{\rm{min}}}} - k{\rm{\Delta }}{\alpha _\mathit{\boldsymbol{m}}}, {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{min}}}}} \right)$∪$\left({{\alpha _{\mathit{\boldsymbol{m}}\_{\rm{max}}}}, {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{max}}}} + k{\rm{\Delta }}{\alpha _\mathit{\boldsymbol{m}}}} \right)\}$,其中,Δαm=αm_max-αm_min表示有效主光轴范围的区间长度。如图 1δ表示PTZ摄像机1的一个主光轴缓冲区,即点填充的紫色扇形范围,则δ=k(φ+θ)。当mMv时,表示该摄像机被选中进行调度优化,而当mMb时,表示该摄像机不参与调度优化。因此,利用主光轴缓冲区系数可以动态控制PTZ摄像机的调度性,通过增大主光轴缓冲区系数以扩大主光轴缓冲区,进而降低PTZ摄像机被选中的概率;对于枪型摄像机,因其无主光轴缓冲区,是否被选中参与调度优化取决于初始主光轴方向。若初始视域范围包含有效视线范围,则表示一定参与调度优化,如图 1中枪型摄像机2;反之则一定不参与,如图 1中枪型摄像机3。

      定义4  可行主光轴:有效主光轴和主光轴缓冲区的并集,记作${M_f} = \{ \mathit{\boldsymbol{m}}|\mathit{\boldsymbol{m}} \in {M_v}\mathop \cup \nolimits {M_b}\} $。可行主光轴对应的坐标方位角区间称为可行主光轴范围。可行主光轴是主光轴方向的可行解空间,摄像机网络中有条件参与调度的摄像机均满足mMf图 1中区间[φ-θ/2-δφ+θ/2+δ]表示PTZ摄像机1在有向路段H-D上的一个可行主光轴范围,而白色扇形范围β表示一个非可行主光轴范围。

      定义5  有效覆盖路段:有效视线覆盖的路段,记作RV。有效覆盖路段被覆盖的长度称为有效覆盖长度,记作LV;当前视域范围内包含有效视线范围的枪型摄像机或当前主光轴方向在有效主光轴范围内的PTZ摄像机称为有效摄像机,记作CV。如图 1中枪型摄像机2在无向路段A-B上的有效视线范围φ′是其初始视域范围的子集,则该摄像机为有效摄像机,无向路段A-B为有效覆盖路段,线段K-L为有效覆盖长度,而枪型摄像机3为无效摄像机。PTZ摄像机1在初始状态无法有效覆盖目标路网的任意路段,但是在调整其主光轴方向后,可以实现对有向路段H-D或无向路段D-E的有效覆盖。

      需要进一步说明,本文所讨论的摄像机网络-有向路网覆盖优化问题只针对有效覆盖问题。因此,摄像机网络-有向路网的有效覆盖模型可以抽象为G= F (P, m, θ, R, τ, k),其中τk可以根据实际应用对摄像机的成像角度和调度性的偏好来确定,并且摄像机网络-有向路网的覆盖优化可以通过只调整主光轴方向m来实现。

    • 根据以上定义,本文用于建模的是通用性视频监控任务中最关注的3个优化目标:(1)路段覆盖数量;(2)路网覆盖长度;(3)摄像机调度数量。因此,摄像机网络在有向路网中的调度问题是一个多目标优化问题。则此问题即为通过求解一组调度优化方案{m}以实现路段覆盖数量、路网覆盖长度的最大化及摄像机调度数量的最小化。目标函数表示如下:

      $${\rm{max}}{N_R}\left( {\left\{ \mathit{\boldsymbol{m}} \right\}} \right) = \sum\limits_{i = 1}^n {\left( {{R_{{V_i}}}} \right)} $$ (1)
      $${\rm{max}}\mathit{L}\left( {\left\{ \mathit{\boldsymbol{m}} \right\}} \right) = \sum\limits_{i = 1}^n {\left( {{L_{{V_i}}}} \right)} $$ (2)
      $${\rm{max}}{\mathit{N}_\mathit{C}}\left( {\left\{ \mathit{\boldsymbol{m}} \right\}} \right) = \sum\limits_{i = 1}^n {\left( {{C_{{V_i}}}} \right)} $$ (3)

      式中,{m}表示摄像机网络的主光轴方向集合;n表示摄像机网络中摄像机的数量;NR({m})表示路段覆盖数量;L({m})表示路网覆盖长度;NC({m})表示摄像机调度数量。

      其约束条件为:

      $$\mathit{\boldsymbol{m}} \in {M_f} $$ (4)
      $${R_V} = \left\{ {\begin{array}{*{20}{c}} {1\begin{array}{*{20}{c}} , &{\mathit{\boldsymbol{m}} \in {M_v}} \end{array}}\\ {0\begin{array}{*{20}{c}} , &{\mathit{\boldsymbol{m}} \in {M_b}} \end{array}} \end{array}} \right. $$ (5)
      $${C_V} = \left\{ {\begin{array}{*{20}{c}} {1\begin{array}{*{20}{c}} , &{\mathit{\boldsymbol{m}} \in {M_v}} \end{array}}\\ {0\begin{array}{*{20}{c}} , &{\mathit{\boldsymbol{m}} \in {M_b}} \end{array}} \end{array}} \right. $$ (6)
    • 针对摄像机网络-有向路网的覆盖优化问题,为了能够对多个优化目标进行有效权衡与协调,进而动态控制参与调度摄像机的规模,本文引入主光轴缓冲区系数对摄像机主光轴方向的活动范围进行划分,并利用粒子群优化算法求解调度优化方案集合,算法流程如图 2所示,主要分为筛选有条件摄像机、计算可行主光轴范围和求解调度优化方案集合3个阶段。

      图  2  算法流程图

      Figure 2.  Flowchart of the Proposed Algorithm

      筛选有条件摄像机阶段主要完成摄像机网络和有向路网的初始建模,根据几何距离和夹角阈值的约束对摄像机网络中有条件参与调度的摄像机进行筛选,并由此得到摄像机的有效主光轴范围;计算可行主光轴范围阶段是根据主光轴缓冲区系数计算主光轴缓冲区,并由此得到摄像机的可行主光轴范围;求解调度优化方案集合阶段是基于改进粒子群优化算法在路段覆盖数量、路网覆盖长度和摄像机调度数量这3个优化目标约束下求解调度优化方案集合。由此,在算法流程中输入摄像机网络-有向路网结构,经处理后即可得到摄像机网络的调度优化方案集合。

    • 1)初始化摄像机网络和有向路网。基于节点-弧段模型构建目标路网的拓扑结构及方向,并初始化摄像机网络中各个摄像机的主光轴方向。

      2)根据几何距离筛选有条件摄像机。逐一计算各摄像机与各路段的最短距离,若该距离小于摄像机的视域半径,则说明二者有条件进行覆盖,并由此删除对任意一条路段均无条件进行覆盖的摄像机,更新摄像机网络-有向路网结构。

      3)根据夹角阈值筛选有条件摄像机。根据实际应用需求设定各路段的视线夹角阈值,并计算摄像机在其有条件覆盖路段上是否存在有效视线范围,如果存在,则作为最终参与调度优化的摄像机,反之则进行删除。

      4)计算有效主光轴范围。对于摄像机网络中所有有条件参与调度的摄像机,利用主光轴方向与有效视线范围的几何关系,计算其有效主光轴范围。

    • 为了能够有效地控制摄像机的调度规模,需要设置合适的主光轴缓冲区系数,本节将对主光轴缓冲区系数的取值范围、重要阈值及其对摄像机网络调度性的影响机制进行说明。一个摄像机网络由多个摄像机组成,每个摄像机可能存在多个有效主光轴范围。对于一个有效主光轴范围而言,随着主光轴缓冲区系数的增大,其区间两侧的主光轴缓冲区也不断增大,进而相邻区间的上限或下限会相交合并成一个新的区间,本文将这个主光轴缓冲区系数的取值称为区间上限最大主光轴缓冲区系数km_max或者区间下限最大主光轴缓冲区系数km_min;随着主光轴缓冲区系数的继续增大,摄像机的所有可行主光轴范围都将合并成一个区间,取得最大值,本文将这个数值称为摄像机的最大主光轴缓冲区系数kC;当主光轴缓冲区系数继续增大到某个数值时,摄像机网络中所有摄像机可行主光轴范围都达到最大值,本文将这个数值称为摄像机网络最大主光轴缓冲区系数kN,则三者之间的关系如下:

      $$\begin{array}{*{20}{l}} {{k_{\mathit{\boldsymbol{m}}\_{\rm{ma}}{{\rm{x}}_i}}} = \frac{{{\alpha _{\mathit{\boldsymbol{m}}\_{\rm{mi}}{{\rm{n}}_{i + 1}}}} - {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{ma}}{{\rm{x}}_i}}}}}{{{\alpha _{\mathit{\boldsymbol{m}}\_{\rm{ma}}{{\rm{x}}_{i + 1}}}} - {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{mi}}{{\rm{n}}_{i + 1}}}} + {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{ma}}{{\rm{x}}_i}}} - {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{mi}}{{\rm{n}}_i}}}}}}\\ {\left( {i = 1, 2 \ldots n} \right)} \end{array} $$ (7)
      $$\begin{array}{*{20}{l}} {{k_{\mathit{\boldsymbol{m}}\_{\rm{mi}}{{\rm{n}}_i}}} = \frac{{{\alpha _{\mathit{\boldsymbol{m}}\_{\rm{mi}}{{\rm{n}}_i}}} - {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{ma}}{{\rm{x}}_{i - 1}}}}}}{{{\alpha _{\mathit{\boldsymbol{m}}\_{\rm{ma}}{{\rm{x}}_i}}} - {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{mi}}{{\rm{n}}_i}}} + {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{ma}}{{\rm{x}}_{i - 1}}}} - {\alpha _{\mathit{\boldsymbol{m}}\_{\rm{mi}}{{\rm{n}}_{i - 1}}}}}}}\\ {\left( {i = 12 \ldots n} \right)} \end{array} $$ (8)
      $${k_C}{\rm{}} = {\rm{max}}\left( {{k_{\mathit{\boldsymbol{m}}\_{\rm{ma}}{{\rm{x}}_i}}}, {k_{\mathit{\boldsymbol{m}}\_{\rm{mi}}{{\rm{n}}_i}}}} \right), i = 1, 2 \cdots n $$ (9)
      $${k_N} = {\rm{max}}\left( {{k_{{C_j}}}} \right), j = 1, 2 \cdots s $$ (10)

      式中,αm_maxiαm_mini表示摄像机第i个有效主光轴范围的区间上限和下限;km_maxikm_mini表示摄像机第i个有效主光轴范围的区间上限和下限的最大主光轴缓冲区系数;kC表示摄像机的最大主光轴缓冲区系数;kN表示摄像机网络的最大主光轴缓冲区系数;n表示摄像机的有效主光轴范围数量;s表示摄像机网络中摄像机的数量。

      为了尽可能保证摄像机网络中每个摄像机在初始化过程中都有相同的概率被选中参与调度,本文设置每个摄像机的有效主光轴范围都选择相同的主光轴缓冲区系数,由此计算主光轴缓冲区,进而得到各个摄像机的可行主光轴范围,即调度优化方案集合的解空间。

    • 粒子群优化(particle swarm optimization,PSO)算法是一种模拟鸟类群体社会行为的智能搜索算法,具有易于实现、搜索效率高等优点,是当前优化求解中应用最广泛的算法之一[17]。本文基于摄像机的感知特性,采用改进PSO算法求解摄像机网络的调度优化方案集合,并通过引入变异策略[18]、约束策略[19]、逃逸策略[20]和拥挤距离策略[19]来控制摄像机主光轴方向的调度状态,从而提高PSO算法在摄像机网络-有向路网覆盖优化问题中的适用性。

      变异策略是对部分随机选取的摄像机的主光轴方向增加随机扰动,以增强粒子对局部空间的搜索能力,避免陷入局部最优解,如图 3m飞行到m'的过程;约束策略关注当主光轴方向飞出可行主光轴范围时,通过执行此操作改变粒子飞行方向,使其重新飞回最近的可行主光轴范围,确保能够得到可行解,如图 3m''飞行到m'''的过程;逃逸策略是针对一个摄像机可能存在多个独立的可行主光轴范围的情况,如果各个区间距离较远时,粒子难以直接飞行到不同的解空间,因此可以通过随机选取部分摄像机,使其主光轴方向强制飞行到其他区间进行搜索,以保障优化解集的多样性,如图 3m飞行到m''''的过程;而拥挤距离策略则是通过度量优化解集中非支配解的分布密度,引导搜索过程趋向于已知解分布密度较低的空间,以便于获得不同类型的解。

      图  3  PSO算法改进策略示意图

      Figure 3.  Improved Strategies Diagram of PSO Algorithm

      因此,上述改进策略是对利用主光轴缓冲区系数来控制主光轴方向运动状态的一种补充,以增强PSO算法在本文问题的优化性能,从而提高优化解集的有效性和多样性。

      另外,为了能够对不同非支配优化方案解集的整体质量进行定量评价,本文引入了超体积[21]这一指标,它可以定量地表示非支配解集所支配区域的尺寸大小,能够对解集收敛性、均匀性以及广泛性进行综合评价,同时当且仅当解集中只包含帕累托前沿时超体积取得最大值[22]。那么,在求解得到非支配优化方案解集后,首先需要进行归一化处理,然后可以采用基于映射的空间切分方法[23]计算超体积,由此筛选出更优的调度优化方案集合。

    • 本文实验中摄像机有效覆盖模型的主要参数有视域角、视域半径、夹角阈值和主光轴缓冲区系数,其中θ = 50°,R= 50 m,τ= 135°,k = 0.5;PSO算法参数包括粒子群规模、外部档案规模、更新代数等,具体设置如表 1所示。本文的实验环境为Intel Core,CPU:i5-6300HQ,4.00 GB内存、主频2.30 GHz,64位Windows 10操作系统,并以C++作为编程语言进行开发实现。

      表 1  PSO算法参数

      Table 1.  Parameters of PSO Algorithm

      参数 取值 说明
      k 0.5 主光轴缓冲区系数
      ω 0.4 文献[24]中式(1)
      c1 1 文献[24]中式(1)
      c2 1 文献[24]中式(1)
      粒子群规模 100 文献[24]
      外部档案规模 500 文献[19]
      最大更新代数 500 文献[24]
      逃逸代数 30% 执行逃逸策略的代数占最大更新代数的比例[20]
      逃逸阈值 70% 执行逃逸策略的粒子规模占粒子群规模的比例[20]
    • 为了验证与分析本文方法的有效性和效率等,设计了如图 4(a)所示的摄像机网络和有向路网数据。其中,绿色矩形表示路段节点,有向实线段表示有向路段,无向虚线段表示无向路段,则目标有向路网中包含29条路段,其中有向路段25条,无向路段4条;蓝色三角形表示枪型摄像机,红色圆点表示PTZ摄像机,灰色扇形表示初始视域范围,则摄像机网络中包含37个摄像机,其中枪型摄像机12个,PTZ摄像机25个;斜线填充阴影区域表示摄像机对目标有向路网的有效视线范围。

      图  4  实验数据(k = 0.5)

      Figure 4.  Experimental Data(k = 0.5)

      实验数据中,单个摄像机与路网的覆盖情况存在3种基本类型:(1)只覆盖一条路段,如摄像机35只覆盖路段B-C;(2)同时覆盖多条路段,如摄像机68可以同时覆盖路段P-LC-L;(3)有多条路段备选,但是某一时刻只能覆盖部分路段,如摄像机10某一时刻可以覆盖路段O-NH-N。摄像机网络-有向路网的覆盖问题不仅是单个摄像机覆盖问题的叠加,而是多个摄像机的协同覆盖,可能存在两种情况:

      1) 摄像机相互独立,如摄像机35和24;

      2) 摄像机可能存在覆盖重叠,如摄像机48和61在路段A-B上可能有覆盖重叠区域。

      根据图 2的算法流程图,在摄像机网络和有向路网初始化完成后,首先根据几何距离和夹角阈值筛选有条件参与调度的摄像机,共计21个摄像机,如图 4(b)所示,包括3个枪型摄像机和18个PTZ摄像机;然后根据主光轴方向与有效视线范围的几何关系,得到有效主光轴范围,即黄色扇形范围;接着根据式(7)~(10)分别计算km_maxkm_minkCkN作为主光轴缓冲区系数选择的重要参考阈值,并结合实际应用需求合理设置主光轴缓冲区系数,计算摄像机的主光轴缓冲区,即点填充的紫色扇形范围。由此,最终可以得到所有有条件参与调度的摄像机的可行主光轴范围。

    • 对于摄像机网络中所有满足有效覆盖条件约束的摄像机,将其主光轴方向以1°为精度在可行主光轴范围内进行穷举,进而构建涵盖所有摄像机网络-有向路网覆盖情况的真值解集。

      图 5所示,灰色线段集合表示在路段覆盖数量、路网覆盖长度和摄像机数量3个优化目标下的真值解集;灰色三角形,即灰色线段的顶端点表示局部最优方案;紫色叉号表示全局最优方案。基于改进PSO算法求解摄像机网络-有向路网的调度优化方案集合,并计算30次独立重复实验中解集的概率密度分布。

      图  5  真值解集与优化结果(k = 0.5)

      Figure 5.  True Value Solution Set and Optimization Results(k = 0.5)

      图 5可知,本文方法搜索到的优化方案基本都聚集在局部最优方案和全局最优方案周围,因此可以有效支持多目标约束下摄像机网络-有向路网的覆盖优化。

    • 当主光轴缓冲区系数取值大于或等于kN时,本文方法将退化为无可行解空间约束的粒子群优化算法,本文称之为随机粒子群优化算法。为了评价本文方法的优化性能,分析主光轴缓冲区系数对摄像机网络调度性的影响机制,本节将对本文方法与随机粒子群优化算法进行对比分析,总结主光轴缓冲区系数动态控制优化结果的一般规律,进而给出设置主光轴缓冲区系数的一般原则。本文方法并未与遗传算法、模拟退火算法等其他主流的优化算法进行对比分析,这是由于不同优化算法的原理不尽相同,其优化性能对于参数和改进策略的选取较为敏感,因此难以在这两方面对不同算法进行合理设置,并以此作为算法性能优劣的评价依据。在图 4所示的实验数据中,根据式(7)~(10)计算主光轴缓冲区系数的取值范围及其重要阈值的分布,最终取值0.1、1.0、2.8进行实验分析,并以30次独立重复实验的平均值作为每组实验的最终结果。主光轴缓冲区系数的最小值为0,表示摄像机网络中所有有条件的摄像机都被选中参与调度,随着k逐渐增大,越来越多摄像机不被选中的概率逐渐增大,直至主光轴缓冲区系数取值kN=2.8,摄像机网络中调度的随机性达到最大值。主光轴缓冲区系数对调度优化方案解集分布的影响如图 6~8所示。

      图  6  主光轴缓冲区系数对摄像机数量和路网覆盖长度的影响

      Figure 6.  Influence of k on Camera Number and Road Network Length

      图  7  主光轴缓冲区系数对路段覆盖数量和路网覆盖长度的影响

      Figure 7.  Influence of k on Road Section Number and Road Network Length

      图  8  主光轴缓冲区系数对摄像机数量和路段覆盖数量的影响

      Figure 8.  Influence of k on Camera Number and Road Section Number

      图 6~8中真值解集的分布可知,3个优化目标既相互联系也相互制约。图 6中增加摄像机数量可以在一定程度上增加路网覆盖长度,但是由于覆盖重叠等情况,当摄像机数量达到一定规模时,再继续增加摄像机反而会造成监控资源的浪费;图 7中随着路段覆盖数量的增加,路网覆盖长度也逐渐增加,但是当只关注于路段覆盖数量时,到达一定规模就会以牺牲路网覆盖长度为代价换取路段覆盖数量的增加,导致路网覆盖长度的减少;图 8中增加摄像机数量可以增加路段的覆盖长度,但是当摄像机数量达到一定规模时,路段覆盖数量也会保持不变。另外,虽然不同优化目标之间无法直接比较,但是在实际应用中决策者往往对摄像机规模或者特定的摄像机和路段存在一定的覆盖偏好,希望能够有效地控制优化的方向,得到更多符合期望的、多样性的优化方案集合,因此对于多目标摄像机网络调度优化问题,其关键在于如何能够在体现决策者应用偏好的基础上实现对多优化目标的动态控制和协同优化。

      图 6~8中不同主光轴缓冲区系数下优化方案解集的概率密度分布可知,主光轴缓冲区系数可以显著地影响优化解集的分布,当k = 0.1时,搜索到的优化方案大部分集中于摄像机数量较多的情况,即本文方法对大规模摄像机下的优化方案搜索能力较强,随着主光轴缓冲区系数的增大,搜索的随机性不断增强,此时对小规模摄像机覆盖情况的搜索能力也逐渐增强,直至k= 2.8时,本文方法对不同规模摄像机下优化方案的搜索能力相对较为均衡,从而得到分布较均匀、多样性较强的优化方案解集。因此,在实际应用中,决策者可以动态地调整主光轴缓冲区系数的取值,以控制摄像机的调度规模。同样,针对特定摄像机和路段的覆盖情况,如果希望增加某个摄像机被选中的概率,则可以对其有效主光轴范围均赋予较小的k;如果想要增大某条路段的覆盖概率,则可以对覆盖该路段的有效主光轴范围赋予较小的k,由此来动态控制优化求解过程的搜索方向,以增强在实际应用中的适用性和灵活性。

      图 9为主光轴缓冲区系数对解集质量的影响。由图 9可知,不同主光轴缓冲区系数下的超体积均呈现出向帕累托前沿收敛的趋势,说明随着更新代数的递增,优化解集也趋于稳定。由于主光轴缓冲区系数决定着初始粒子群体在可行解空间中的分布状态,则该系数取值越大,粒子分布越均匀,所对应的超体积也越大。当优化解集已足够收敛时,超体积最大值对应的k = 1.0,而不是kN= 2.8,这是由于相对适中的主光轴缓冲区系数可以对不同规模下摄像机网络与路网的覆盖情况进行有效协调,进而得到在收敛性、均匀性和广泛性这3个方面均表现较为均衡的解集分布,获得更大的超体积。

      图  9  主光轴缓冲区系数对解集质量的影响

      Figure 9.  Influence of k on Solution Set Quality

      图 10为主光轴缓冲区系数对运行时间的影响。可以看出,本文方法在不同主光轴缓冲区系数下的运行时间均随更新代数线性增加,且主光轴缓冲区系数越小,运行时间越长。这是由于在相同条件下,该系数取值越小,粒子的可行解空间越小,则在优化求解过程中执行约束操作的概率就越大,相应的运行时间也就越长。在实际应用中,可以根据给定时间合理设置更新代数,或者通过比较一定步长下相邻两代的超体积来控制更新代数,当其变化率小于阈值时,即可认为优化解集已经收敛,无需继续更新迭代。

      图  10  主光轴缓冲区系数对运行时间的影响

      Figure 10.  Influence of k on Running Time

      综上所述,利用主光轴缓冲区系数,本文方法比随机粒子群优化算法具有更好的灵活性和适用性,可以动态控制优化过程的解集质量、解集分布和运行时间,从而便于决策者根据不同类型的监控应用需求,有效地将应用偏好转化为主光轴缓冲区系数的取值,以便获得更多期望的调度优化方案解集。

    • 由上一节的分析可知,本文方法在不同主光轴缓冲区系数下都遵循相同的规律,因此仅以k=kN(2.8)为例,分别对视域角、视域半径和夹角阈值设计3组对照实验进行分析,其中对照组参数为θ= 50°,R = 50 m,τ= 135°,实验组参数如图 11所示,以30次独立重复实验的平均值作为每组实验的最终结果。

      图  11  摄像机参数对实验结果的影响

      Figure 11.  Influence of Camera Parameters on Experimental Results

      当摄像机参数改变时,摄像机网络-有向路网的覆盖情况也随之改变,则图 11中不同真值解集下实验组优化解集超体积的大小不具备可比性,但是仍然可以看出,调度优化方案解集的超体积均逐渐收敛,说明本文方法能够有效适应不同的摄像机网络-有向路网覆盖情况,具有一定的鲁棒性。

    • 静态场景和动态目标是摄像机网络覆盖优化的主要方面,尽管本文方法主要关注前者,但经过适当拓展之后,也可以为移动目标的动态监控提供支持。

      移动目标跟踪可以分为目标发现、目标覆盖和目标离开3个过程[25],为了更好地说明,假设移动目标沿道路网络匀速运动,且进入路网的初始状态可以被感知。当摄像机检测到目标出现在其视域范围内时,获取目标当前所在的路段和位置坐标;根据道路网络的拓扑关系,预测目标下一时刻可能出现的候选路段和位置坐标,并利用摄像机网络与路网的覆盖关系对相应的摄像机进行调度优化以实现目标覆盖;当目标离开摄像机的感知范围或摄像机在特定时间约束下未发现目标时,解除临时调度并恢复原始覆盖状态,并更新广播下一时刻目标运动的候选路段集合,由此实现对移动目标在道路网络中的动态跟踪。

      面向移动目标跟踪的摄像机网络调度优化也是多目标优化问题,以§1.4中的优化目标为例,当关注于路段覆盖数量时,可以更加精准地确定目标经过的路段,但可能减少路网的覆盖长度。同样,当关注路网覆盖长度时,可以增加目标的暴露时间,但可能因覆盖路段减少而增大目标跟踪丢失的不确定性。

      因此,在本文提出的面向多优化目标的摄像机网络调度优化方法的基础上,通过拓展摄像机网络、道路网络与移动目标的时间、空间约束,筛选不同时刻下移动目标的候选路段和摄像机作为输入进行求解,即可以为面向移动目标跟踪的监控任务提供摄像机网络调度优化的决策支持。

    • 针对摄像机网络-有向路网的覆盖优化问题,本文提出了一种面向多优化目标的摄像机网络调度优化方法,该方法首先对摄像机网络-有向路网的有效覆盖进行建模,选择通用性监控任务中最关注的3个方面:路段覆盖数量、路网覆盖长度和摄像机调度数量作为优化目标,然后引入主光轴缓冲区系数以划分摄像机主光轴方向的活动范围,进而动态控制参与调度的摄像机的规模,并基于改进粒子群优化算法求解了摄像机网络的调度优化方案集合,分析了主光轴缓冲区系数对优化结果的影响机制,总结了设置主光轴缓冲区系数的一般原则。

      实验结果表明,对于复杂的摄像机网络-有向路网的覆盖优化问题,该方法具有较好的有效性、鲁棒性和灵活性,能够在体现决策者应用偏好的基础上实现多个目标的协同优化,从而实现视频监控资源的优化配置和资源利用率的最大化。

      在实际应用中,面向不同的监控任务,其他优化目标可以直接加入该方法的优化模型进行求解而无需更改算法流程,该方法也可以为其他有向传感器资源的多目标优化配置提供参考和借鉴。

参考文献 (25)

目录

    /

    返回文章
    返回