DOI: 10.11817/j.issn.1672-7207.2016.12.021
基于混沌路径的移动式安全监控方法
王田，缪海星，蒋文贤，张国亮，蔡奕侨
(华侨大学 计算机科学与技术学院，福建 厦门，361021)
摘要：引入移动式的视频监控方法，将摄像头搭载在可以移动的小车上，对监测区域实现轮询式监控。通过对移动摄像头的路径进行规划，设计一种基于混沌路径的摄像头移动路径规划算法并实现移动式视频监控的原型系统。研究结果表明：与传统固定式监控方式相比，系统算法增加了随机性，提高了监控安全性，而与随机性移动方法相比，则提高了监控效率，是对传统固定式视频监控方式的有力补充。
关键词：视频监控；混沌路径；移动式监控；随机性
中图分类号：TP393 文献标志码：A 文章编号：1672-7207(2016)12-4115-07
Secure mobile surveillance based on chaotic paths
WANG Tian, MIAO Haixing, JIANG Wenxian, ZHANG Guoliang, CAI Yiqiao
(College of Computer Science & Technology, Huaqiao University, Xiamen 361021, China)
Abstract: A mobile video surveillance method that cameras are mounted on mobile vehicles to patrol the area was introduced. Through scheduling the movements of cameras, an algorithm based on chaotic paths of mobile cameras was designed and a prototype system of mobile video surveillance was implemented. The results show that the proposed method can increase the randomness and improve the security compared with traditional surveillance methods. Moreover, when compared with the method with random paths of cameras, the proposed method can improve the efficiency, which is a powerful supplement to traditional fixed surveillance methods.
Key words: video surveillance; chaotic paths; mobile surveillance; randomness
美国的“911”事件、西班牙马德里列车连环爆炸案和英国伦敦的地铁大爆炸等恐怖袭击的发生使全世界范围内对视频监控系统的需求空前高涨。据市场调查公司IMS Research预测，全球主要国家和地区的安防视频监控设备的销售收入将继续保持增长。全球市场销售额在2009—2013年保持11.86%的年均复合增长率，亚太地区将保持15%左右的增长率[1]。视频监控已经成为现代社会安保系统中一项重要的安全措施，这在一些重要场所是必不可少的。例如酒店、银行、博物馆等场所都需要有摄像头的监控来确保安全，防止受到非法入侵、破坏以及为一些案件侦办提供线索。这些摄像头可以进行区域监控、目标识别、跟踪[2]，并已经充斥于人们生活的方方面面。虽然当今的视频监控发展非常迅速，应用范围极为广泛，但是还存在不少问题。一方面，现今部署的摄像头存在安全问题。传统的摄像头基本上都是位置固定的，这种提前部署的摄像头容易被犯罪嫌疑人通过犯案前踩点，从而在作案的时候躲过摄像头的监控。另一方面，监控总是存在盲区。如在大型仓库里，面积大且地形复杂，需要重点监控的点可能很多，需要配备许多个传统固定式的摄像头，效率不高，且不能灵活配置。针对传统部署的固定位置的摄像头所存在的问题，提出移动式摄像头监控的方案，即将摄像头安装在可以控制其移动的装置上(如移动的机器人、小车)[3-6]。这样不仅可以扩大监控的范围，也能实现对目标的多角度监控。本文作者设计了一种混沌路径算法，使得摄像头的移动路径具有混沌性(即确定的但不可预知的运动状态)，以提高监测的安全性。此外，还实现了实验室环境下的移动式视频监控原型系统。相对于移动路径最优的TSP(travelling salesman problem)方法，该方法没有显著降低监控效率，而与随机访问的方法相比，大大提高了监控效率。
1 移动监控
1.1 路线受限制的移动监控
自2003年，美国安技新公司在我国推广车载移动监控，为国内车辆安防带来新的方案。地铁正成为现代城市的主要交通方式，通过无线的视频监控可以时刻感知车厢的情况，有利于提高对突发事件的处理能力，预防危险的发生。目前不少出租公司经常面临司乘纠纷以及车辆被劫等风险，车载监控的应用能减少纠纷的发生，并对车辆被劫等恶性事故保留足够的证据，为破案和找回车辆提供便利。
1.2 可控制移动路线的监控
随着现代机器人技术的发展，可以通过在机器人上搭载摄像头实现监控，从而使摄像头具备了移动能力。这是区别于传统的固定摄像头的一种移动式监控。PASQUALETTI等[8]提出了一种基于权重的协同巡逻策略，对每个监控点的访问间隔设为权重，时间间隔越大的访问优先级就越高。LEE等[8]提出了一种群体机器人基于时间变化的巡逻方案，相应的每个监控点都通过函数计算当前的安全等级，安全等级越低的越优先访问。KOLLING等[9]提出一种对监控区域进行图分割的方法，就是将监控的区域表示为图的形式。FRANCHI等[10]提出一种生成随机图的思想：以各个监控点建立一个随机连通图。TOMIOKA等[11]提出了一种最优路径的选择算法，该方法是基于摄像头的视角和视距，效果优于基于TSP的方法[12]，但是路径固定。以上方法虽然都基于移动式摄像头，但是摄像头移动路径一旦设计好后就是固定不变的，安全性不高。甘若迅等[13]提出了一种基于遗传算法的警车巡逻算法，虽然路径隐蔽性效果较好，但没有提及对于离散点的巡逻间隔。曹攀峰等[14]提出的基于随机策略的无人机巡逻路径规划算法，通过引入随机参数的方法规划随机路径，以同等的频率访问各个节点，以访问频率作为一个重要指标。由此可见，为了使摄像监控获得更高的安全性，路径的选择算法至关重要。混沌路径算法是针对视频监控的可变路径选择方法。该方法通过提高路径的随机性来应对安全问题，并兼顾监控效率的问题。
2 监控问题定义
在一个L×L的待监测平面区域内随机分布有k个待监测的关键点，记为n1(x1，y1)，n2(x2，y2)，…，nk(xk，yk)。一辆搭载有摄像头的移动小车对这些关键点进行轮询式监控，移动速率为v。假设小车对节点ni访问过m次，每次被访问到的时刻分别为t1，t2，…，tm。目标是：
1) 小车以不可预知的路径来访问区域内的关键点，即产生的访问序列和每一轮的访问时间呈现随机性(安全性目标)。
2) 对每一轮的访问时间尽可能的小(效率目标)。
图1所示为小车依次访问关键点的路径图，图中有6个关键点，移动式摄像头需要对这些关键点进行轮询式监控。假设小车第1轮从n1关键点开始访问，访问路径如图1(a)所示为n1→n2→n4→n5→n6→n3，最后访问节点n3，下一轮则从n3节点开始访问，访问路径如图1(b)所示为n3→n2→n6→n5→n1→n4。最后一轮则从n4节点开始访问，访问路径如图1(c)所示为n4→n2→n1→n5→n3→n6。
若关键点n1，n2，n3，…，n6的坐标分别为(10，44)，(46，48)，(30，25)，(8，18)，(30，6)，(58，18) m，小车移动速率v=2 m/s。表1所示为小车访问各个点的时间。可见：每一轮的移动路径都是不一样的，访问时间也没有明显的规律性。
图1 小车依次访问关键点的路径图
Fig. 1 Paths of movements of car
表1 小车访问时间
Table 1 Visiting time of car
3 算法设计
3.1 算法描述
基于对问题的建模，提出的解决方案需要同时满足安全性目标和效率目标。方案的基本思想是先根据所有监测点的坐标求出1条最优的TSP路径，然后每个监测点依据自身在这条TSP路径上到其他监测点的距离来生成自身到其他监测点的访问概率。当某个监测点被访问后，该监测点就会根据访问概率选择下一个监测点进行访问，以此类推不断地对区域内的关键点进行访问。算法如下。
算法1 基于透视原理的混沌路径规划算法
输入：n个位置已知的节点，一个长度为n的blacklist队列
输出：M轮的节点访问序列
1:运行1次TSP算法求出1组访问序列：w1，w2，w3，…，wn；
2:对每个节点wi，计算出到其他n-1个节点的访问概率;
3:k=1;
4:随机选取1个节点作为始发点;
5:while (k<=M) do
6: 清空blacklist，并将始发点加入blacklist队列;
7: while(blacklist没有满)do
8: 根据计算出的访问概率，选择下一个未在blacklist中的节点作为访问节点;
9: 将该点加入blacklist;
10: end while
11: 输出blacklist中的序列，以最后一个节点为始发点；
12: k++;
13:end while
14:END
假设有n个位置已知的监测点w1，w2，…，wn，将长度为n，名为blacklist的队列用于存储每一轮中已经访问过的节点，使得每一轮遍历所有的节点。
步骤1 根据监测点的坐标，运行现有的TSP解决算法(如蚁群算法)生成1条TSP路径。对每个节点wi，计算出到其他n-1个监测点的距离。需要强调的是，这里节点间的距离的计算不是两点之间的欧式距离，而是TSP路径上两点之间的长度。
4个节点的TSP路径如图2所示。可见：通过TSP算法得到的路径为w1→w2→w3→w4→w1，其中，w1→到w3的距离D13则是D13+ D23。当前节点到其他节点的访问概率是跟当前节点到其他节点的距离长度成反比，具体计算方法如下：
(1)
其中：指数β为常数，需要通过实验得到一个最优值；Dij为TSP路径上节点i到节点j的距离；Pij为节点i到节点j的访问概率。
图2 4个节点的TSP路径
Fig. 2 TSP path of four nodes
步骤2 随机选择一个监测点wi作为移动摄像头的始发点，清空blacklist队列，并将始发点加入blacklist队列中。
步骤3 若blacklist队列未满，则根据访问概率，选择一个未在blacklist的监测点作为移动摄像头下一个要到达的监测点并加入blacklist队列中。不断执行步骤3直到blacklist队列队满，输出blacklist队列的元素就是第1轮访问的路径。此时，清空blacklist队列，再以最后加入blacklist中的监测点作为始发点，重复步骤1~3。由于对于在TSP路径上的节点，距离近的访问概率高，距离远的访问概率低，类似透视原理中的“近大远小”，因此本文的算法取名为基于透视原理的混沌路径规划算法。
3.2 性能分析。
采用的是蚁群算法求解TSP问题，时间复杂度为O(Tmn2)，其中T为迭代总次数，m为蚂蚁的数量，n为探访节点的数量，即问题的规模。随后的每轮过程中，需依次选取n次节点，因此每轮算法的时间复杂度为O(n)。总的时间复杂度为O(Tmn2+n)。需要指出的是，用蚁群算法计算TSP问题，只需要在初始阶段计算1次，实际每一次的轮询过程中的时间复杂度仅为O(n)。
4 真实系统
设计了一个移动式摄像头监控的原型系统，图3所示为系统结构图，图4所示为原型系统。可移动小车搭载摄像头，通过电脑在无线或者有线网络环境下进行远程控制，小车由TP-Link路由器、单片机最小系统、电机驱动、摄像头、电池、车模、红外感应器等设备组成。路由器可以通过接收PC端发出的请求后运行脚本程序发送串口数据，从而将相应的动作指令发送给单片机以实现对小车的控制(移动方向控制、摄像头转向等)。或者使用软件切换控制程序模式，使其按预先设计行驶路线巡逻。单片机最小系统也就是小车的核心控制部件，实现对相关操作的处理。电机驱动芯片驱动小车的前后2个电机使后轮做匀速行驶(约为2 m/s)，而前轮作为左右转向轮；摄像头则对周围环境实施监控。当接收到自动行驶的命令后，小车可以在循迹算法的帮助下，通过红外感应器实现自动循迹从而按照预先设计路线进行移动监控。
图3 移动式监控系统结构图
Fig. 3 Structure of mobile surveillance system
图4 移动式监控原型系统
Fig. 4 Prototype system of mobile video surveillance
5 实验评估
为了在较大规模的场景下评估系统及算法的性能，结合原型系统，并通过omnet++4.0来进行实验评估，实验的场景参数如表2所示，其中移动速率等环境参数取自真实实验平台。为了进行对比，本文还实现了传统的基于TSP路径的方法(称为固定式访问算法)以及随机访问路径的方法(摄像头每次在随机选择一个节点作为访问的下一个节点)。为了减小误差，实验结果取10次实验得到数据的平均值。
表2 实验参数
Table 2 Experiment parameters
图5 实验场景
Fig. 5 Experimental scene
首先，确定式(1)中β的取值，为此对β从1开始测试。测试随机性的因素是产生的访问的节点序号的随机性和每一轮的访问时间的随机性。采取游程检测的方法进行随机性的检测。单样本变量的随机性检验是对某变量的取值出现是否随机进行检验，也称为游程检验(Run过程)。它的零假设为H0，即认为变量出现是随机的。单样本变量的随机性检验通过游程数来实现。
然后，利用SPSS19.0.0软件进行随机性测试。在SPSS单样本变量的随机性检验中，将利用游程构造Z统计量，并依据正态分布表给出对应的相伴概率。若相伴概率小于或等于用户的显著性水平α，则应拒绝零假设H0，认为样本值的出现不是随机的；若相伴概率大于显著性水平，则不能拒绝零假设H0，认为变量的出现是随机的。
表3所示为β=1.5时，SPSS软件得到的游程测试结果。由渐近显著性可知，在显著性水平为0.05下，移动摄像头访问关键点的单轮总时间和节点编号产生的序列满足随机性。
图6所示为在不同的β下混沌路径算法1 000轮访问所花费的总时间。由图6可知：随着β的增大，总时间在不断减少，也就是说β越大效率越高。这是因为该值越大，规划的路径就越接近TSP路径。但是在β＞1.6后，经游程测试得知：实验得到的访问序列在0.05显著性水平下不满足随机性的要求。在β=1.5及β＜1.5都通过了游程测试，因此，β的取值应为1.5。
表3 游程测试的结果(β=1.5)
Table 3 Result of runs test (β=1.5)
图6 在不同的β下混沌路径算法1 000轮访问所花费的总时间
Fig. 6 Total time of 1 000 rounds in chaotic paths algorithm with different β
图7所示为随机路径算法与混沌路径算法前10轮访问所花费的时间。由图7可知：混沌路径算法所花费的时间明显少于随机路径算法(约为后者的60%)。并且，随机路径算法每轮时间的起伏相较于混沌路径算法偏大。因此，在效率上混沌路径算法较好。
图8所示为3种算法分别访问1 000轮后所使用的总时间的对比图。由图8可知：固定路径算法所花费的时间最少，这是由于固定路径算法中移动摄像头按照TSP路径进行移动，每轮的路径都没有变化，所以时间最短。随机路径算法所花费的时间最多，混沌路径算法所花时间是随机路径算法的2/3左右。
图9所示为3种算法在边长为50 m的正方形场景中运行1 000轮时，访问总时间与节点数的变化关系图。由图9可见：随着场景规模的扩大，访问总时间也会增加。不过，随机路径算法增加的幅度要比其他2种算法大的多。在节点数为50个时，随机路径算法访问总时间是594 797.420 3 s，混沌路径算法访问总时间为288 083.820 6 s，这时监测效率相比随机路径算法提升了50%左右。可见，随着规模的增大，算法优势将更为明显。
图7 随机路径算法与混沌路径算法的前10轮时间对比
Fig. 7 Comparison of time of first ten rounds for Random paths algorithm and Chaotic paths algorithm
图8 3种算法进行1 000轮访问所花费的总时间对比
Fig. 8 Comparison of 1 000 rounds interview total time of three algorithms
图9 在不同节点规模下3种算法的效率
Fig. 9 Comparison of three algorithms with different node numbers
6 结论
1) 针对传统视频监控中存在的安全问题(摄像头位置固定，监控存在盲区等)，引入移动式的视频监控方式，在可移动装置(小车或机器人)上搭载摄像头，利用小车的移动特性执行监控任务。考虑到监控的安全性和效率，提出了一种基于混沌路径的移动视频监控算法并设计了移动式监控原型系统。
2) 与随机路径算法相比，该算法的监测效率提升了50%，并且小车移动产生的访问序列和每一轮的访问时间通过了游程测试，证明设计的路径满足随机性要求。因此，该方法提高了现有视频监控系统的安全性，可以应用在对监控有较高安全要求的应用中。
参考文献：
[1] 江怡曼. 安防行业攻守兼备视频监控公司最有看头[EB/OL]2014-08-01. http://news.hexun.com/2010-07-10/ 124207578.html.
JIANG Yiman. Both offensive and defensive video surveillance security industry are most worth seeing[EB/OL]2014-08-01. http://news.hexun.com/2010-07-10/124207578.html.
[2] HU W, TAN T, WANG L, et al. A survey on visual surveillance of object motion and behaviors[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2004, 34(3): 334-352.
[3] 罗元, 邵帅, 张毅. 基于信息融合的移动机器人定位与路径规划[J]. 计算机应用, 2010, 30(11): 3091-3096.
LUO Yuan, SHAO Shuai, ZHANG Yi. Location and path planning of mobile robots based on data fusion[J]. Journal of Computer Applications, 2010, 30(11): 3091-3096.
[4] 张志文, 崔建. 带摄像头的自循迹移动靶车控制系统研究[J]. 西安工业大学学报, 2010, 30(3): 287-292.
ZHANG Zhiwen, CUI Jian. The research of control system of self-tracking target vehicle with camera[J]. Journal of Xi’an Technological University, 2010, 30(3): 287-292.
[5] 徐晓晴, 朱庆保. 基于蛙跳算法的新型机器人路径规划算法[J]. 小型微型计算机系统, 2014, 35(7): 1631-1635.
XU Xiaoqing, ZHU Qingbao. A new mobile robot path planning based on shuffled frog leaping algorithm[J]. Journal of Chinese Computer System, 2014, 35(7): 1631-1635.
[6] 洪露, 龚成龙, 王经卓, 等. 移动机器人路径规划免疫网络算法研究[J]. 小型微型计算机系统, 2014, 35(6): 1437-1440.
HONG Lu, GONG Shenglong, WANG Jingzhuo, et al. Immune network algorithm for mobile robot path planning[J]. Journal of Chinese Computer System, 2014, 35(6): 1437-1440.
[7] PASQUALETTI F, DURHAM J W, BULLO F. Cooperative patrolling via weighted tours: performance analysis and distributed algorithms[J]. IEEE Transactions on Robotics, 2012, 28(5): 1181-1188.
[8] LEE J, KWON J W, JI S H. Time-varying patrolling scheme for multi-robots[C]//2012 9th International Conference on Ubiquitous Robots and Ambient Intelligence. Daejeon, Korea: IEEE, 2012: 341-343.
[9] KOLLING A, CARPIN S. The graph-clear problem: definition, theoretical properties and its connections to multirobot aided surveillance[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems. San Diego, USA: IEEE, 2007: 1003-1008.
[10] FRANCHI A, FREDA L, ORIOLO G, et al. The sensor-based random graph method for cooperative robot exploration[J]. IEEE/ASME Transactions on Mechatronics, 2009, 14(2): 163-175.
[11] TOMIOKA Y, TAKARA A, KITAZAWA H. Generation of an optimum patrol course for mobile surveillance camera[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(2): 216-224.
[12] LI Y, MA K, ZHANG J. An Efficient Multicore Based Parallel Computing Approach for TSP Problems[C]//The 9th International Conference on Semantics, Knowledge and Grids (SKG). Beijing, China: IEEE, 2013: 98-104.
[13] 甘若迅, 吕睿, 江一飞, 等. 基于遗传算法的警车巡逻问题求解[J]. 计算机应用. 2011, 31(6): 116-118.
GAN Ruoxun, L
Rui, JIANG Yifei, et al. Slution to police car patrolling problem based on genetic algorithm[J]. Journal of Computer Application, 2011, 31(6): 116-118.
[14] 曹攀峰, 崔升. 基于随机策略的无人机巡逻路径规划[J]. 复旦学报(自然科学版), 2012, 50(6): 787-791.
CAO Panfeng, CUI Sheng. UAV patrolling based on stochastic strategy[J]. Journal of Fudan University (Natural Science), 2012, 50(6): 787-791.
(编辑 赵俊)
收稿日期：2015-12-10；修回日期：2016-03-17
基金项目(Foundation item)：国家自然科学基金资助项目(61672441，61572206)；福建省自然科学基金资助项目(2014J01240，2016J01302)；福建省科技计划重点项目 (2014H01010199)；福建省泉州市科技计划重点项目(2014Z102)(Project(61672441, 61572206) supported by the National Natural Science Foundation of China; Project(2014J01240, 2016J01302) supported by the Natural Science Foundation of Fujian Province of China; Project(2014H01010199) supported by the Key Science and Technology Program of Fujian Province; Project(2014Z102) supported by the Key Science and Technology Program of Quanzhou City)
通信作者：王田，博士，从事物联网、移动计算等研究；Email：wsnman@gmail.com
