基于混沌路徑的移動式安全監控方法

王田，繆海星，蔣文賢，張國亮，蔡奕僑

?

基于混沌路徑的移動式安全監控方法

王田，繆海星，蔣文賢，張國亮，蔡奕僑

(華僑大學計算機科學與技術學院，福建廈門，361021)

引入移動式的視頻監控方法，將攝像頭搭載在可以移動的小車上，對監測區域實現輪詢式監控。通過對移動攝像頭的路徑進行規劃，設計一種基于混沌路徑的攝像頭移動路徑規劃算法并實現移動式視頻監控的原型系統。研究結果表明：與傳統固定式監控方式相比，系統算法增加了隨機性，提高了監控安全性，而與隨機性移動方法相比，則提高了監控效率，是對傳統固定式視頻監控方式的有力補充。

視頻監控；混沌路徑；移動式監控；隨機性

美國的“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]提出的基于隨機策略的無人機巡邏路徑規劃算法，通過引入隨機參數的方法規劃隨機路徑，以同等的頻率訪問各個節點，以訪問頻率作為一個重要指標。由此可見，為了使攝像監控獲得更高的安全性，路徑的選擇算法至關重要?；煦缏窂剿惴ㄊ轻槍σ曨l監控的可變路徑選擇方法。該方法通過提高路徑的隨機性來應對安全問題，并兼顧監控效率的問題。

2 監控問題定義

在一個×的待監測平面區域內隨機分布有個待監測的關鍵點，記為1(1，1)，2(2，2)，…，n(x，y)。一輛搭載有攝像頭的移動小車對這些關鍵點進行輪詢式監控，移動速率為。假設小車對節點n訪問過次，每次被訪問到的時刻分別為1，2，…，t。目標是：

1) 小車以不可預知的路徑來訪問區域內的關鍵點，即產生的訪問序列和每一輪的訪問時間呈現隨機性(安全性目標)。

2) 對每一輪的訪問時間盡可能的小(效率目標)。

圖1所示為小車依次訪問關鍵點的路徑圖，圖中有6個關鍵點，移動式攝像頭需要對這些關鍵點進行輪詢式監控。假設小車第1輪從1關鍵點開始訪問，訪問路徑如圖1(a)所示為1→2→4→5→6→3，最后訪問節點3，下一輪則從n3節點開始訪問，訪問路徑如圖1(b)所示為3→2→6→5→1→4。最后一輪則從4節點開始訪問，訪問路徑如圖1(c)所示為4→2→1→5→3→6。

若關鍵點1，2，3，…，6的坐標分別為(10，44)，(46，48)，(30，25)，(8，18)，(30，6)，(58，18) m，小車移動速率=2 m/s。表1所示為小車訪問各個點的時間。可見：每一輪的移動路徑都是不一樣的，訪問時間也沒有明顯的規律性。

(a)第1輪路徑；(b)第2輪路徑；(c)第3輪路徑

圖1 小車依次訪問關鍵點的路徑圖

Fig. 1 Paths of movements of car

表1 小車訪問時間

3 算法設計

3.1 算法描述

基于對問題的建模，提出的解決方案需要同時滿足安全性目標和效率目標。方案的基本思想是先根據所有監測點的坐標求出1條最優的TSP路徑，然后每個監測點依據自身在這條TSP路徑上到其他監測點的距離來生成自身到其他監測點的訪問概率。當某個監測點被訪問后，該監測點就會根據訪問概率選擇下一個監測點進行訪問，以此類推不斷地對區域內的關鍵點進行訪問。算法如下。

算法1基于透視原理的混沌路徑規劃算法

輸入：個位置已知的節點，一個長度為的blacklist隊列

輸出：輪的節點訪問序列

1:運行1次TSP算法求出1組訪問序列：1，2，3，…，w；

2:對每個節點w，計算出到其他?1個節點的訪問概率;

3:=1;

4:隨機選取1個節點作為始發點;

5:while (<=) do

6: 清空blacklist，并將始發點加入blacklist隊列;

7: while(blacklist沒有滿)do

8: 根據計算出的訪問概率，選擇下一個未在blacklist中的節點作為訪問節點;

9: 將該點加入blacklist;

10: end while

11: 輸出blacklist中的序列，以最后一個節點為始發點；

12:++;

13:end while

14:END

假設有個位置已知的監測點1，2，…，w，將長度為，名為blacklist的隊列用于存儲每一輪中已經訪問過的節點，使得每一輪遍歷所有的節點。

步驟1 根據監測點的坐標，運行現有的TSP解決算法(如蟻群算法)生成1條TSP路徑。對每個節點w，計算出到其他?1個監測點的距離。需要強調的是，這里節點間的距離的計算不是兩點之間的歐式距離，而是TSP路徑上兩點之間的長度。

4個節點的TSP路徑如圖2所示。可見：通過TSP算法得到的路徑為1→2→3→4→1，其中，1→到3的距離13則是13+23。當前節點到其他節點的訪問概率是跟當前節點到其他節點的距離長度成反比，具體計算方法如下：

圖2 4個節點的TSP路徑

其中：指數為常數，需要通過實驗得到一個最優值；D為TSP路徑上節點到節點的距離；P為節點到節點的訪問概率。

步驟2 隨機選擇一個監測點w作為移動攝像頭的始發點，清空blacklist隊列，并將始發點加入blacklist隊列中。

步驟3 若blacklist隊列未滿，則根據訪問概率，選擇一個未在blacklist的監測點作為移動攝像頭下一個要到達的監測點并加入blacklist隊列中。不斷執行步驟3直到blacklist隊列隊滿，輸出blacklist隊列的元素就是第1輪訪問的路徑。此時，清空blacklist隊列，再以最后加入blacklist中的監測點作為始發點，重復步驟1~3。由于對于在TSP路徑上的節點，距離近的訪問概率高，距離遠的訪問概率低，類似透視原理中的“近大遠小”，因此本文的算法取名為基于透視原理的混沌路徑規劃算法。

3.2 性能分析。

采用的是蟻群算法求解TSP問題，時間復雜度為(2)，其中為迭代總次數，為螞蟻的數量，為探訪節點的數量，即問題的規模。隨后的每輪過程中，需依次選取次節點，因此每輪算法的時間復雜度為()。總的時間復雜度為(2+)。需要指出的是，用蟻群算法計算TSP問題，只需要在初始階段計算1次，實際每一次的輪詢過程中的時間復雜度僅為()。

4 真實系統

設計了一個移動式攝像頭監控的原型系統，圖3所示為系統結構圖，圖4所示為原型系統?？梢苿有≤嚧钶d攝像頭，通過電腦在無線或者有線網絡環境下進行遠程控制，小車由TP-Link路由器、單片機最小系統、電機驅動、攝像頭、電池、車模、紅外感應器等設備組成。路由器可以通過接收PC端發出的請求后運行腳本程序發送串口數據，從而將相應的動作指令發送給單片機以實現對小車的控制(移動方向控制、攝像頭轉向等)。或者使用軟件切換控制程序模式，使其按預先設計行駛路線巡邏。單片機最小系統也就是小車的核心控制部件，實現對相關操作的處理。電機驅動芯片驅動小車的前后2個電機使后輪做勻速行駛(約為2 m/s)，而前輪作為左右轉向輪；攝像頭則對周圍環境實施監控。當接收到自動行駛的命令后，小車可以在循跡算法的幫助下，通過紅外感應器實現自動循跡從而按照預先設計路線進行移動監控。

圖3 移動式監控系統結構圖

圖4 移動式監控原型系統

5 實驗評估

為了在較大規模的場景下評估系統及算法的性能，結合原型系統，并通過omnet++4.0來進行實驗評估，實驗的場景參數如表2所示，其中移動速率等環境參數取自真實實驗平臺。為了進行對比，本文還實現了傳統的基于TSP路徑的方法(稱為固定式訪問算法)以及隨機訪問路徑的方法(攝像頭每次在隨機選擇一個節點作為訪問的下一個節點)。為了減小誤差，實驗結果取10次實驗得到數據的平均值。

表2 實驗參數

圖5 實驗場景

首先，確定式(1)中的取值，為此對從1開始測試。測試隨機性的因素是產生的訪問的節點序號的隨機性和每一輪的訪問時間的隨機性。采取游程檢測的方法進行隨機性的檢測。單樣本變量的隨機性檢驗是對某變量的取值出現是否隨機進行檢驗，也稱為游程檢驗(Run過程)。它的零假設為0，即認為變量出現是隨機的。單樣本變量的隨機性檢驗通過游程數來實現。

然后，利用SPSS19.0.0軟件進行隨機性測試。在SPSS單樣本變量的隨機性檢驗中，將利用游程構造統計量，并依據正態分布表給出對應的相伴概率。若相伴概率小于或等于用戶的顯著性水平，則應拒絕零假設0，認為樣本值的出現不是隨機的；若相伴概率大于顯著性水平，則不能拒絕零假設0，認為變量的出現是隨機的。

表3所示為=1.5時，SPSS軟件得到的游程測試結果。由漸近顯著性可知，在顯著性水平為0.05下，移動攝像頭訪問關鍵點的單輪總時間和節點編號產生的序列滿足隨機性。

圖6所示為在不同的下混沌路徑算法1 000輪訪問所花費的總時間。由圖6可知：隨著的增大，總時間在不斷減少，也就是說越大效率越高。這是因為該值越大，規劃的路徑就越接近TSP路徑。但是在＞1.6后，經游程測試得知：實驗得到的訪問序列在0.05顯著性水平下不滿足隨機性的要求。在=1.5及＜1.5都通過了游程測試，因此，的取值應為1.5。

表3 游程測試的結果(β=1.5)

圖6 在不同的β下混沌路徑算法1 000輪訪問所花費的總時間

圖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%左右。可見，隨著規模的增大，算法優勢將更為明顯。

1—隨機路徑算法；2—混沌路徑算法。

圖7 隨機路徑算法與混沌路徑算法的前10輪時間對比

Fig. 7 Comparison of time of first ten rounds for Random paths algorithm and Chaotic paths algorithm

圖8 3種算法進行1 000輪訪問所花費的總時間對比

1—固定路徑算法；2—隨機路徑算法；3—混沌路徑算法。

圖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.

(編輯 趙俊)

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)

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.

video surveillance; chaotic paths; mobile surveillance; randomness

10.11817/j.issn.1672-7207.2016.12.021

TP393

A

1672?7207(2016)12?4115?07

2015?12?10；

2016?03?17

國家自然科學基金資助項目(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