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

?

基于混沌路徑的移動式安全監(jiān)控方法

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

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

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

視頻監(jiān)控；混沌路徑；移動式監(jiān)控；隨機性

美國的“911”事件、西班牙馬德里列車連環(huán)爆炸案和英國倫敦的地鐵大爆炸等恐怖襲擊的發(fā)生使全世界范圍內(nèi)對視頻監(jiān)控系統(tǒng)的需求空前高漲。據(jù)市場調(diào)查公司IMS Research預測，全球主要國家和地區(qū)的安防視頻監(jiān)控設備的銷售收入將繼續(xù)保持增長。全球市場銷售額在2009—2013年保持11.86%的年均復合增長率，亞太地區(qū)將保持15%左右的增長率[1]。視頻監(jiān)控已經(jīng)成為現(xiàn)代社會安保系統(tǒng)中一項重要的安全措施，這在一些重要場所是必不可少的。例如酒店、銀行、博物館等場所都需要有攝像頭的監(jiān)控來確保安全，防止受到非法入侵、破壞以及為一些案件偵辦提供線索。這些攝像頭可以進行區(qū)域監(jiān)控、目標識別、跟 蹤[2]，并已經(jīng)充斥于人們生活的方方面面。雖然當今的視頻監(jiān)控發(fā)展非常迅速，應用范圍極為廣泛，但是還存在不少問題。一方面，現(xiàn)今部署的攝像頭存在安全問題。傳統(tǒng)的攝像頭基本上都是位置固定的，這種提前部署的攝像頭容易被犯罪嫌疑人通過犯案前踩點，從而在作案的時候躲過攝像頭的監(jiān)控。另一方面，監(jiān)控總是存在盲區(qū)。如在大型倉庫里，面積大且地形復雜，需要重點監(jiān)控的點可能很多，需要配備許多個傳統(tǒng)固定式的攝像頭，效率不高，且不能靈活配置。針對傳統(tǒng)部署的固定位置的攝像頭所存在的問題，提出移動式攝像頭監(jiān)控的方案，即將攝像頭安裝在可以控制其移動的裝置上(如移動的機器人、小車)[3?6]。這樣不僅可以擴大監(jiān)控的范圍，也能實現(xiàn)對目標的多角度監(jiān)控。本文作者設計了一種混沌路徑算法，使得攝像頭的移動路徑具有混沌性(即確定的但不可預知的運動狀態(tài))，以提高監(jiān)測的安全性。此外，還實現(xiàn)了實驗室環(huán)境下的移動式視頻監(jiān)控原型系統(tǒng)。相對于移動路徑最優(yōu)的TSP(travelling salesman problem)方法，該方法沒有顯著降低監(jiān)控效率，而與隨機訪問的方法相比，大大提高了監(jiān)控效率。

1 移動監(jiān)控

1.1 路線受限制的移動監(jiān)控

自2003年，美國安技新公司在我國推廣車載移動監(jiān)控，為國內(nèi)車輛安防帶來新的方案。地鐵正成為現(xiàn)代城市的主要交通方式，通過無線的視頻監(jiān)控可以時刻感知車廂的情況，有利于提高對突發(fā)事件的處理能力，預防危險的發(fā)生。目前不少出租公司經(jīng)常面臨司乘糾紛以及車輛被劫等風險，車載監(jiān)控的應用能減少糾紛的發(fā)生，并對車輛被劫等惡性事故保留足夠的證據(jù)，為破案和找回車輛提供便利。

1.2 可控制移動路線的監(jiān)控

隨著現(xiàn)代機器人技術的發(fā)展，可以通過在機器人上搭載攝像頭實現(xiàn)監(jiān)控，從而使攝像頭具備了移動能力。這是區(qū)別于傳統(tǒng)的固定攝像頭的一種移動式監(jiān)控。PASQUALETTI等[8]提出了一種基于權重的協(xié)同巡邏策略，對每個監(jiān)控點的訪問間隔設為權重，時間間隔越大的訪問優(yōu)先級就越高。LEE等[8]提出了一種群體機器人基于時間變化的巡邏方案，相應的每個監(jiān)控點都通過函數(shù)計算當前的安全等級，安全等級越低的越優(yōu)先訪問。KOLLING等[9]提出一種對監(jiān)控區(qū)域進行圖分割的方法，就是將監(jiān)控的區(qū)域表示為圖的形式。FRANCHI等[10]提出一種生成隨機圖的思想：以各個監(jiān)控點建立一個隨機連通圖。TOMIOKA等[11]提出了一種最優(yōu)路徑的選擇算法，該方法是基于攝像頭的視角和視距，效果優(yōu)于基于TSP的方法[12]，但是路徑固定。以上方法雖然都基于移動式攝像頭，但是攝像頭移動路徑一旦設計好后就是固定不變的，安全性不高。甘若迅等[13]提出了一種基于遺傳算法的警車巡邏算法，雖然路徑隱蔽性效果較好，但沒有提及對于離散點的巡邏間隔。曹攀峰等[14]提出的基于隨機策略的無人機巡邏路徑規(guī)劃算法，通過引入隨機參數(shù)的方法規(guī)劃隨機路徑，以同等的頻率訪問各個節(jié)點，以訪問頻率作為一個重要指標。由此可見，為了使攝像監(jiān)控獲得更高的安全性，路徑的選擇算法至關重要?；煦缏窂剿惴ㄊ轻槍σ曨l監(jiān)控的可變路徑選擇方法。該方法通過提高路徑的隨機性來應對安全問題，并兼顧監(jiān)控效率的問題。

2 監(jiān)控問題定義

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

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

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

圖1所示為小車依次訪問關鍵點的路徑圖，圖中有6個關鍵點，移動式攝像頭需要對這些關鍵點進行輪詢式監(jiān)控。假設小車第1輪從1關鍵點開始訪問，訪問路徑如圖1(a)所示為1→2→4→5→6→3，最后訪問節(jié)點3，下一輪則從n3節(jié)點開始訪問，訪問路徑如圖1(b)所示為3→2→6→5→1→4。最后一輪則從4節(jié)點開始訪問，訪問路徑如圖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所示為小車訪問各個點的時間。可見：每一輪的移動路徑都是不一樣的，訪問時間也沒有明顯的規(guī)律性。

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

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

Fig. 1 Paths of movements of car

表1 小車訪問時間

3 算法設計

3.1 算法描述

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

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

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

輸出：輪的節(jié)點訪問序列

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

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

3:=1;

4:隨機選取1個節(jié)點作為始發(fā)點;

5:while (<=) do

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

7: while(blacklist沒有滿)do

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

9: 將該點加入blacklist;

10: end while

11: 輸出blacklist中的序列，以最后一個節(jié)點為始發(fā)點；

12:++;

13:end while

14:END

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

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

4個節(jié)點的TSP路徑如圖2所示?？梢姡和ㄟ^TSP算法得到的路徑為1→2→3→4→1，其中，1→到3的距離13則是13+23。當前節(jié)點到其他節(jié)點的訪問概率是跟當前節(jié)點到其他節(jié)點的距離長度成反比，具體計算方法如下：

圖2 4個節(jié)點的TSP路徑

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

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

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

3.2 性能分析。

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

4 真實系統(tǒng)

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

圖3 移動式監(jiān)控系統(tǒng)結構圖

圖4 移動式監(jiān)控原型系統(tǒng)

5 實驗評估

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

表2 實驗參數(shù)

圖5 實驗場景

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

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

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

圖6所示為在不同的下混沌路徑算法1 000輪訪問所花費的總時間。由圖6可知：隨著的增大，總時間在不斷減少，也就是說越大效率越高。這是因為該值越大，規(guī)劃的路徑就越接近TSP路徑。但是在＞1.6后，經(jīng)游程測試得知：實驗得到的訪問序列在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輪時，訪問總時間與節(jié)點數(shù)的變化關系圖。由圖9可見：隨著場景規(guī)模的擴大，訪問總時間也會增加。不過，隨機路徑算法增加的幅度要比其他2種算法大的多。在節(jié)點數(shù)為50個時，隨機路徑算法訪問總時間是594 797.420 3 s，混沌路徑算法訪問總時間為288 083.820 6 s，這時監(jiān)測效率相比隨機路徑算法提升了50%左右?？梢姡S著規(guī)模的增大，算法優(yōu)勢將更為明顯。

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 在不同節(jié)點規(guī)模下3種算法的效率

Fig. 9 Comparison of three algorithms with different node numbers

6 結論

1) 針對傳統(tǒng)視頻監(jiān)控中存在的安全問題(攝像頭位置固定，監(jiān)控存在盲區(qū)等)，引入移動式的視頻監(jiān)控方式，在可移動裝置(小車或機器人)上搭載攝像頭，利用小車的移動特性執(zhí)行監(jiān)控任務。考慮到監(jiān)控的安全性和效率，提出了一種基于混沌路徑的移動視頻監(jiān)控算法并設計了移動式監(jiān)控原型系統(tǒng)。

2) 與隨機路徑算法相比，該算法的監(jiān)測效率提升了50%，并且小車移動產(chǎn)生的訪問序列和每一輪的訪問時間通過了游程測試，證明設計的路徑滿足隨機性要求。因此，該方法提高了現(xiàn)有視頻監(jiān)控系統(tǒng)的安全性，可以應用在對監(jiān)控有較高安全要求的應用中。

[1] 江怡曼. 安防行業(yè)攻守兼?zhèn)湟曨l監(jiān)控公司最有看 頭[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] 羅元, 邵帥, 張毅. 基于信息融合的移動機器人定位與路徑規(guī)劃[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] 張志文, 崔建. 帶攝像頭的自循跡移動靶車控制系統(tǒng)研究[J]. 西安工業(yè)大學學報, 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] 徐曉晴, 朱慶保. 基于蛙跳算法的新型機器人路徑規(guī)劃算法[J]. 小型微型計算機系統(tǒng), 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īng)卓, 等. 移動機器人路徑規(guī)劃免疫網(wǎng)絡算法研究[J]. 小型微型計算機系統(tǒng), 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] 曹攀峰, 崔升.基于隨機策略的無人機巡邏路徑規(guī)劃[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)

王田，博士，從事物聯(lián)網(wǎng)、移動計算等研究；Email：wsnman@gmail.com