視頻傳感器覆蓋范圍精細(xì)化計(jì)算方法*

王自然，張亞南，劉學(xué)軍，4，王美珍，4(.南京師范大學(xué)泰州學(xué)院，江蘇泰州225300；2.南京師范大學(xué)地理科學(xué)學(xué)院，江蘇南京20023；3.江蘇省地理信息資源開(kāi)發(fā)與利用協(xié)同創(chuàng)新中心，江蘇南京20023；4.警用地理信息技術(shù)公安部重點(diǎn)實(shí)驗(yàn)室，江蘇常州23022)

視頻傳感器覆蓋范圍精細(xì)化計(jì)算方法*

王自然1，張亞南2，3，劉學(xué)軍2，3，4，王美珍2，3，4
(1.南京師范大學(xué)泰州學(xué)院，江蘇泰州225300；2.南京師范大學(xué)地理科學(xué)學(xué)院，江蘇南京210023；
3.江蘇省地理信息資源開(kāi)發(fā)與利用協(xié)同創(chuàng)新中心，江蘇南京210023；4.警用地理信息技術(shù)公安部重點(diǎn)實(shí)驗(yàn)室，江蘇常州213022)

視頻傳感器覆蓋范圍計(jì)算是視頻傳感器網(wǎng)絡(luò)初始配置、優(yōu)化部署等的核心基礎(chǔ)，其精度嚴(yán)重影響覆蓋分析的結(jié)果，然而現(xiàn)有很多方法并未考慮計(jì)算方法執(zhí)行效率與精度的影響，而方法的精度與效率在大范圍監(jiān)控視頻覆蓋分析應(yīng)用中顯得尤為重要。因此，提出一種兼顧速度與精度的視頻傳感器覆蓋范圍計(jì)算方法，將地理空間進(jìn)行格網(wǎng)化；計(jì)算每個(gè)格網(wǎng)角點(diǎn)被視頻傳感器覆蓋的狀況，用0或1表示；接著，以格網(wǎng)四個(gè)角點(diǎn)的覆蓋情況描述格網(wǎng)的覆蓋情況，將格網(wǎng)分為16種覆蓋狀態(tài)；逐步細(xì)化整個(gè)格網(wǎng)覆蓋狀態(tài)非(0000)和(1111)的格網(wǎng)，直至達(dá)到預(yù)設(shè)精度；獲得視頻傳感器的覆蓋范圍。實(shí)驗(yàn)結(jié)果表明，該方法能夠更為精確地獲得部署在地理場(chǎng)景中視頻傳感器的覆蓋范圍，同時(shí)兼顧了計(jì)算方法的速度和精度。

相機(jī)覆蓋；覆蓋分析；二值化網(wǎng)格；格網(wǎng)細(xì)化

視頻傳感器，作為物聯(lián)網(wǎng)中一種重要有向的視覺(jué)傳感器，能夠記錄豐富的時(shí)空信息，有全天候、高度覆蓋、實(shí)時(shí)性等優(yōu)點(diǎn)，已被廣泛應(yīng)用于公共安全、交通管理、軍事國(guó)防、環(huán)境監(jiān)測(cè)等領(lǐng)域。視頻傳感器覆蓋范圍是表征視頻傳感器有效性的重要指標(biāo)，是視頻監(jiān)控內(nèi)容與地理環(huán)境進(jìn)行融合展示的前提。覆蓋范圍計(jì)算是視頻傳感器網(wǎng)絡(luò)初始配置、優(yōu)化部署等分析［1-4］的核心基礎(chǔ)，覆蓋范圍的計(jì)算精度嚴(yán)重影響覆蓋分析的結(jié)果。

在傳感器網(wǎng)絡(luò)等相關(guān)領(lǐng)域，已經(jīng)提出了一些視頻的覆蓋范圍的算法。Erdem［5］提出了將視頻傳感器的可視域分割成多個(gè)“可視塊”的算法。H?rster等［6］、Mittal等［7］、Shen等［8］則用視線檢測(cè)方法檢測(cè)多邊形可視域中各個(gè)節(jié)點(diǎn)的覆蓋情況。Angella等［9］和Zhao等［10-14］將視線檢測(cè)的方法推廣到三維。Liu［15］分析了山體等錐形地形無(wú)線傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題。而在視頻傳感器網(wǎng)絡(luò)配置、優(yōu)化等算法中涉及視頻傳感器覆蓋計(jì)算的研究中，大部分研究將監(jiān)控場(chǎng)景簡(jiǎn)化為二維平面，少量研究障礙物遮擋問(wèn)題，無(wú)法表達(dá)視頻傳感器的真實(shí)覆蓋。障礙物的遮擋問(wèn)題方面，當(dāng)分析場(chǎng)景中的障礙物(樹(shù)木、建筑物等)時(shí)，多以簡(jiǎn)單的幾何圖形或者高墻代替。

然而，視頻傳感器在實(shí)際應(yīng)用中是布設(shè)于真實(shí)的地理環(huán)境中的，并且視頻傳感器具有有向性的特點(diǎn)，其覆蓋范圍的計(jì)算可看作是一種特殊的可視域分析，得到的覆蓋范圍，可稱作“視頻可視域”［16］，因此視頻覆蓋范圍計(jì)算除了要考慮地形因素外，還需要考慮視頻傳感器參數(shù)，并且覆蓋范圍計(jì)算對(duì)視頻傳感器參數(shù)變化敏感，參數(shù)調(diào)整通常意味著覆蓋范圍的重新計(jì)算，而GIS領(lǐng)域主要關(guān)注地形起伏。近年來(lái)的研究多集中在提高方法效率，如并行化方法［17］、基于距離場(chǎng)映射的地形可視域分析方法［18］等，為視頻覆蓋范圍計(jì)算提供借鑒。方陸明等［16］提出了基于數(shù)字高程模型(Digital Elevation Model，DEM)的視頻可視域提取方法，實(shí)現(xiàn)了視頻在DEM上的同步跟蹤，但實(shí)驗(yàn)分析僅僅以單個(gè)視頻的可視域驗(yàn)證了方法的可用性，對(duì)算法的效率未作討論。

1 空間點(diǎn)覆蓋計(jì)算

空間中的一地面點(diǎn)被視頻傳感器感知必須滿足兩個(gè)條件:①空間點(diǎn)在視頻傳感器的視棱錐中，即空間點(diǎn)在視頻傳感器中成像；②視頻傳感器與空間點(diǎn)之間不存在遮擋。條件①與視頻傳感器感知模型相關(guān)，條件②還與地理環(huán)境中的障礙物有關(guān)。

視頻傳感器感知模型如圖1所示，視頻傳感器的光學(xué)中心C，坐標(biāo)記作(XC，YC，HC)，由CD1D2D3D4構(gòu)成的棱錐即為當(dāng)前視頻傳感器的理論覆蓋范圍，棱錐的大小可由相機(jī)的基本參數(shù)與姿態(tài)參數(shù)確定。基本參數(shù)包括:成像芯片尺寸、焦距(f)、中心點(diǎn)等。姿態(tài)參數(shù)包括:方位角P、俯仰角T、橫滾角v。方位角P以某點(diǎn)的指北方向線起，依順時(shí)針?lè)较虻侥繕?biāo)方向線之間的水平夾角；俯仰角T則指從某點(diǎn)的水平方向線起，依順時(shí)針?lè)较虻侥繕?biāo)方向線之間的垂直夾角；橫滾角v指視頻傳感器繞著“光學(xué)中心-靶面中心”軸順時(shí)針旋轉(zhuǎn)的角度。研究主要針對(duì)實(shí)際應(yīng)用中最為常見(jiàn)的監(jiān)控?cái)z像機(jī)——搖攝-傾斜-變焦(Pan-Tilt-Zoom，PTZ)攝像機(jī)，其可以改變方位角、俯仰角以及焦距，不能改變橫滾角，橫滾角接近0°。因此空間點(diǎn)G，坐標(biāo)記作(XG，YG，HG)，與其對(duì)應(yīng)圖像點(diǎn)，坐標(biāo)記作(x，y)，可通過(guò)式(1)計(jì)算而得。式(1)中λ為尺度因子，不影響圖像點(diǎn)的計(jì)算。

地理空間中一個(gè)點(diǎn)能被視頻傳感器感知到，需要視線與靶面有交點(diǎn)，即圖像坐標(biāo)滿足x∈［xmin，xmax］，y∈［ymin，ymax］；［xmin，xmax］與［ymin，ymax］分別表示圖像坐標(biāo)系中圖像點(diǎn)在坐標(biāo)軸方向上的最大最小值。同時(shí)，視線之間無(wú)障礙點(diǎn)，即判斷障礙物的高度是否高于當(dāng)前視線與障礙物交點(diǎn)的高度，如圖1所示，G1被覆蓋，而G2未被覆蓋。

圖1 視頻傳感器感知模型Fig.1 Perception model of camera

2 覆蓋范圍計(jì)算方法

2.1 方法基本思想

本文方法首先利用一個(gè)初始格網(wǎng)將地理環(huán)境進(jìn)行格網(wǎng)剖分；其次，根據(jù)第1節(jié)判斷格網(wǎng)點(diǎn)是否被當(dāng)前相機(jī)感知/可視，若可視，則格網(wǎng)點(diǎn)的值表示為1，否則表示為0；再次，利用格網(wǎng)四個(gè)角點(diǎn)的感知狀態(tài)表示單個(gè)格網(wǎng)的感知狀態(tài)，再將所有的格網(wǎng)組合在一起，模擬整個(gè)空間區(qū)域的感知狀態(tài)；最后，逐步細(xì)化格網(wǎng)覆蓋狀態(tài)非(0000)和(1111)的格網(wǎng)，直至達(dá)到預(yù)設(shè)精度，進(jìn)而最終獲得視頻傳感器的覆蓋范圍。該方法的核心思想是先空間離散，后空間內(nèi)插，從而快速、準(zhǔn)確估算視頻傳感器覆蓋范圍。

2.2 障礙物數(shù)據(jù)的獲取與表示

障礙物高度可以從原始空間數(shù)據(jù)中獲得，可以為固定值、圖層的屬性值、屬性的表達(dá)式、無(wú)限高(∞)。修剪整齊的植被、圍墻、電線桿等高度規(guī)格一致的障礙物可以使用固定值。一些障礙物的高度會(huì)保存在圖層的屬性值中，可以直接指定屬性值為高度數(shù)據(jù)的來(lái)源。一些建筑物的圖層沒(méi)有高度信息，但是有層數(shù)的信息，此時(shí)建筑物的高度可以通過(guò)表達(dá)式(層高乘以層數(shù))估計(jì)。此外，實(shí)踐中在一些場(chǎng)合里，例如在計(jì)算道路兩側(cè)的路面視頻監(jiān)控的覆蓋范圍時(shí)，不需要考慮建筑物等障礙物的真實(shí)數(shù)值，可將障礙物看作是一堵無(wú)限高的墻，任何與墻有交點(diǎn)的視線都不能穿越，從而大大提升計(jì)算效率。

一般而言，地理數(shù)據(jù)可用點(diǎn)、線、面三種類型進(jìn)行表達(dá)，不同的類型其幾何信息都以坐標(biāo)序列的形式存儲(chǔ)，這就便于對(duì)其進(jìn)行統(tǒng)一處理，因?yàn)楦鶕?jù)實(shí)際情況，本文方法面狀對(duì)象看作為閉合的線對(duì)象，將點(diǎn)與面對(duì)象轉(zhuǎn)化為線對(duì)象進(jìn)行統(tǒng)一處理，將點(diǎn)根據(jù)實(shí)際情況做一個(gè)緩沖區(qū)，形成一個(gè)閉合的線，如樹(shù)木在地理信息系統(tǒng)中通常作為點(diǎn)對(duì)象存儲(chǔ)，可根據(jù)樹(shù)冠的大小將其變?yōu)榫€對(duì)象參與本文方法的計(jì)算。

本文方法主要關(guān)注視線上是否有遮擋，只需要獲得視線上的對(duì)象高度即可，因此本方法在三維GIS可視域分析中也適用。

表1 格網(wǎng)二進(jìn)制編碼、覆蓋情況及其面積Tab.1 Binary coding coverage and area of grids

2.3 格網(wǎng)覆蓋狀態(tài)二值表達(dá)

每個(gè)單元格有四個(gè)角點(diǎn)，每個(gè)角點(diǎn)有可被感知和不可被感知兩種狀態(tài)，分別用1和0標(biāo)記，此值可根據(jù)1.2節(jié)方法計(jì)算而得。四個(gè)角點(diǎn)的感知狀態(tài)(0或者1)按左上、右上、左下、右下排列組合，一共16種狀態(tài)，用二進(jìn)制編碼可表示為(0000)2到(1111)2，對(duì)應(yīng)十進(jìn)制的0～15，每個(gè)編碼表達(dá)了格網(wǎng)的一種被覆蓋狀態(tài)。編碼與格網(wǎng)覆蓋狀態(tài)的對(duì)應(yīng)關(guān)系如表1所示，從表1可以看出(0110)2和(1001)2狀態(tài)存在歧義，即可能存在兩種格網(wǎng)一個(gè)編碼的情況。此時(shí)，檢測(cè)格網(wǎng)中心點(diǎn)的感知狀態(tài)，若格網(wǎng)中心可被感知，那么對(duì)應(yīng)第一種狀態(tài)，否則為第二種狀態(tài)。

當(dāng)一個(gè)格網(wǎng)的編碼為(0000)2時(shí)，整個(gè)格網(wǎng)內(nèi)狀態(tài)視為“空”；同理，編碼為(1111)2時(shí)，視為“滿”。當(dāng)格網(wǎng)狀態(tài)為“空”或者“滿”時(shí)，格網(wǎng)內(nèi)

部狀態(tài)勻質(zhì)，表示當(dāng)前格網(wǎng)表達(dá)的地理環(huán)境未被覆蓋或者被覆蓋；否則，當(dāng)前格網(wǎng)非勻質(zhì)，需要進(jìn)一步處理以獲得精確的覆蓋范圍。

2.4 格網(wǎng)逐步細(xì)化

在計(jì)算視頻傳感器覆蓋范圍過(guò)程中，視頻傳感器覆蓋計(jì)算所確定的掃描格網(wǎng)的大小至關(guān)重要，掃描格網(wǎng)粒度過(guò)大，可能會(huì)導(dǎo)致面積較小的信息丟失；而格網(wǎng)粒度過(guò)小，會(huì)浪費(fèi)大量的計(jì)算資源、存儲(chǔ)資源。

針對(duì)格網(wǎng)尺寸對(duì)視頻傳感器覆蓋精度與效率的影響，提出了通過(guò)細(xì)化格網(wǎng)采樣的方法，對(duì)非(0000)2和(1111)2編碼的格網(wǎng)進(jìn)行逐步細(xì)化。本節(jié)將以圖2為例，說(shuō)明掃描細(xì)化過(guò)程。圖2(a)表示初始掃描格網(wǎng)的大小，記作w0，格網(wǎng)編碼為(1101)2，為非勻質(zhì)網(wǎng)格，需要對(duì)格網(wǎng)進(jìn)一步細(xì)化；格網(wǎng)大小取w0/2，如圖2(b)所示，格網(wǎng)四條邊的中點(diǎn)和格網(wǎng)的中心點(diǎn)這5個(gè)點(diǎn)，將格網(wǎng)分割成4份，計(jì)算5個(gè)點(diǎn)被視頻傳感器覆蓋的情況，四個(gè)格網(wǎng)的編碼從左到右從上到下分別為(1101)2，(1111)2，(0100)2，(1101)2，由于右上方的細(xì)化格網(wǎng)勻質(zhì)，不需要進(jìn)一步細(xì)化，其他三個(gè)格網(wǎng)需要進(jìn)一步細(xì)化；取格網(wǎng)大小w0/4，每個(gè)二級(jí)格網(wǎng)被進(jìn)一步細(xì)化，同時(shí)判斷新增加的5個(gè)點(diǎn)的覆蓋情況，細(xì)化結(jié)果如圖2(c)所示，若當(dāng)前細(xì)化粒度達(dá)到預(yù)期則不再細(xì)化，或者，當(dāng)網(wǎng)格細(xì)化到一定程度，所有級(jí)別的網(wǎng)格都是“空”或“滿”，格網(wǎng)也無(wú)須進(jìn)一步細(xì)化。

圖2 格網(wǎng)分級(jí)細(xì)化Fig.2 Different levels of girds

格網(wǎng)細(xì)化結(jié)束后，覆蓋面積CA可根據(jù)式(2)以及表1中的編碼進(jìn)行估算:

式(2)由兩部分組成，前部分表示所有非最細(xì)層次的格網(wǎng)覆蓋的面積之和，后部分表示所有最細(xì)層次的格網(wǎng)覆蓋的面積之和。式(2)中，d表示格網(wǎng)細(xì)化的層數(shù)，count(i)表示第i層次中編號(hào)為(1111)2的格網(wǎng)數(shù)量，而count(j)表示編號(hào)為j (j=0，1，…，15)的格網(wǎng)的個(gè)數(shù)，ap(j)表示編號(hào)為j的格網(wǎng)其覆蓋面積占當(dāng)前細(xì)節(jié)層次的格網(wǎng)的比例，其取值參考如表1所示。圖2(c)覆蓋的面積即為:

2.5 二值格網(wǎng)覆蓋范圍計(jì)算方法

二值格網(wǎng)覆蓋范圍計(jì)算方法描述如下:

算法1二值格網(wǎng)覆蓋范圍計(jì)算算法Alg.1 Algorithm for Coverage estimation based on binary coded grids

本文方法中用一個(gè)三元組(d，i，j)表達(dá)格網(wǎng)中的一個(gè)格網(wǎng)的角點(diǎn)，d為層數(shù)，i表示行號(hào)，j表示列號(hào)。記0層格網(wǎng)的寬度為w0，0層格網(wǎng)的起始點(diǎn)(0，0，0)空間坐標(biāo)為(X0，Y0)，那么第0層的(0，i0，j0)點(diǎn)的空間坐標(biāo)是(X0+i0×w0，Y0+j0×w0)。記(d，i，j)在第d+1層的標(biāo)號(hào)為(d+1，2×i，2×j)，可以得出結(jié)論:(d，i，j)與(d+n，2n×i，2n×j)空間位置相同。(d，i，j)點(diǎn)所在的空間坐標(biāo)為(X0+(i×w0)/2d，Y0+(j×w0)/ 2d)。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證方法的有效性和效率，并討論初始格網(wǎng)尺寸和格網(wǎng)層次對(duì)方法的影響，本文設(shè)計(jì)了視頻傳感器覆蓋分析實(shí)驗(yàn)。實(shí)驗(yàn)中障礙物主要包括建筑物與樹(shù)木。

圖3視頻傳感器覆蓋計(jì)算結(jié)果Fig.3 Results of cameras coverage

圖3 中共部署了6個(gè)監(jiān)控?cái)z像機(jī)，其中4個(gè)為云臺(tái)槍機(jī)，其俯仰角和水平角度可調(diào)節(jié)，2個(gè)為固定槍機(jī)，其參數(shù)不可調(diào)，傳感器參數(shù)參見(jiàn)表2，攝像機(jī)部署的地理位置及其覆蓋范圍如圖3所示，圖中深色半透明區(qū)域是視頻傳感器可以覆蓋到的區(qū)域，半透明多邊形中的編號(hào)對(duì)應(yīng)表2中的編號(hào)。實(shí)驗(yàn)中以1m，2m，4m，5m為初始格網(wǎng)寬度，相對(duì)應(yīng)的格網(wǎng)細(xì)化層次為0，1，0/1/2，2。由于布設(shè)在實(shí)際地理環(huán)境中的監(jiān)控相機(jī)不易預(yù)先獲取其真實(shí)的覆蓋范圍，因此無(wú)法與真實(shí)值進(jìn)行比較，本實(shí)驗(yàn)中，將地理場(chǎng)景分別分為最大尺寸(4m ×4m)和最小尺寸(1m×1m)的剖分格網(wǎng)進(jìn)行覆蓋面積的計(jì)算，理論上，若本文方法覆蓋面積與最小尺寸格網(wǎng)的計(jì)算結(jié)果接近，則表示效率相當(dāng)。而格網(wǎng)點(diǎn)的個(gè)數(shù)表示需要掃描的點(diǎn)的個(gè)數(shù)，體現(xiàn)算法的執(zhí)行效率，因此，實(shí)驗(yàn)中以掃描格網(wǎng)角點(diǎn)作為衡量效率的標(biāo)準(zhǔn)，實(shí)驗(yàn)結(jié)果見(jiàn)表3。

3.2 分析

理論分析本文最耗時(shí)的過(guò)程為格網(wǎng)角點(diǎn)覆蓋情況判斷。假設(shè)當(dāng)前空間初始劃分N×M個(gè)格網(wǎng)，即層次數(shù)d=0，此時(shí)需要判斷(N+1)×(M+ 1)個(gè)角點(diǎn)的覆蓋狀況，這為本文方法的最好情況；若當(dāng)前空間每一個(gè)格網(wǎng)都需要細(xì)化到d(d＞0)層次，則需要判斷(N+1)×(M+1)×(2×d) ×(2×d)個(gè)角點(diǎn)的覆蓋狀況，此為本文方法的最差情況。因此，從理論上講，本文方法的效率介于將覆蓋范圍按照初始格網(wǎng)大小進(jìn)行剖分和按照最細(xì)層次格網(wǎng)大小進(jìn)行剖分的效率之間，且接近于按照初始格網(wǎng)大小進(jìn)行剖分的效率，而覆蓋面積精度接近于將地理環(huán)境剖分為最小網(wǎng)格時(shí)候的情況。若地理環(huán)境較為復(fù)雜，遮擋視線的障礙物多，其效率接近將空間劃分為最細(xì)層次的格網(wǎng)時(shí)的效率；而當(dāng)?shù)乩憝h(huán)境中地勢(shì)平坦、障礙物少時(shí)，其效率接近將空間劃分為最高層次的格網(wǎng)時(shí)的效率；若地理環(huán)境復(fù)雜度介于兩者之間時(shí)，本文方法在計(jì)算效率方面具有明顯的優(yōu)勢(shì)。

表2 視頻傳感器部署參數(shù)Tab.2 Parameters of cameras

本文方法以格網(wǎng)的四個(gè)角點(diǎn)的覆蓋狀態(tài)表示格網(wǎng)的覆蓋情況，而不是用格網(wǎng)中心點(diǎn)的覆蓋情況表示，以16種不同的覆蓋情況代替2種覆蓋情況，格網(wǎng)的覆蓋情況被細(xì)化，相比較而言，本文方法估算的覆蓋面積更精細(xì)。從理論上講，地理環(huán)境被分割得越精細(xì)，覆蓋面積計(jì)算的精度越高，但當(dāng)?shù)乩憝h(huán)境簡(jiǎn)單時(shí)，精細(xì)格網(wǎng)分割并不能帶來(lái)計(jì)算精度的顯著提高，反而提高了計(jì)算時(shí)間；而地理環(huán)境復(fù)雜時(shí)，較大尺寸的格網(wǎng)分割必然導(dǎo)致格網(wǎng)內(nèi)部信息的丟失。本文方法顧及了地理環(huán)境的復(fù)雜性，達(dá)到了計(jì)算效率與計(jì)算精度的平衡。

實(shí)驗(yàn)分析實(shí)驗(yàn)結(jié)果也證明了上述理論分析。由表3可知，本文方法采用逐層細(xì)化的策略，相對(duì)于地理環(huán)境以較小格網(wǎng)尺寸進(jìn)行均一化劃分時(shí)需要判斷的格網(wǎng)角點(diǎn)顯著減少，使得計(jì)算的時(shí)間大大縮短；相對(duì)于以較大格網(wǎng)尺寸進(jìn)行劃分時(shí)地理空間的信息可能被丟失，盡量細(xì)化非勻質(zhì)的格網(wǎng)，從而使得計(jì)算精度得到保證。本文方法做到了精度和效率的平衡，尤其在大規(guī)模的傳感器覆蓋計(jì)算時(shí)，本文方法優(yōu)勢(shì)顯著。

表3 實(shí)驗(yàn)結(jié)果Tab.3 Results of experiment

初始格網(wǎng)大小與格網(wǎng)層次是影響本文方法效率和精度的兩個(gè)重要參數(shù)。從實(shí)際地理環(huán)境的實(shí)驗(yàn)可知:①在利用均一格網(wǎng)大小進(jìn)行剖分時(shí)，即格網(wǎng)層次為0，如表3所示的第一大列(注:包括計(jì)算面積和掃描格網(wǎng)角點(diǎn)的個(gè)數(shù)，下同)和第二大列，初始格網(wǎng)越小計(jì)算的精度越高，格網(wǎng)每縮小1/2，所要掃描的格網(wǎng)點(diǎn)的數(shù)量即變?yōu)樵瓉?lái)的4倍；②在初始格網(wǎng)大小一定的情況下，如表3中的第二、三、四大列，分割的格網(wǎng)層次越大，精度越高，但當(dāng)格網(wǎng)層次到達(dá)一定程度后精度提高不明顯，耗費(fèi)的時(shí)間卻明顯增加；③在最小層次的格網(wǎng)大小相同的情況下，如表3中的第一、四、五大列，選用本文方法，其計(jì)算的精度幾乎一致，與相同大小的格網(wǎng)均一剖分的精度相差無(wú)幾，但其效率卻提高數(shù)倍，此時(shí)初始格網(wǎng)大，效率越高；④當(dāng)最小層次的格網(wǎng)大小接近，但初始格網(wǎng)大小和層次均不相同時(shí)，如表3中的第六大列，初始格網(wǎng)為5m剖分層次為2，其最細(xì)層次格網(wǎng)大小為1.25m，初始格網(wǎng)為4m剖分層次為2，兩組數(shù)據(jù)的精度相當(dāng)，并且掃描格網(wǎng)的數(shù)目也相當(dāng)。與格網(wǎng)分割方向的關(guān)系的影響。如圖4所示，圖4(a)中梯形表示當(dāng)前視頻傳感器地面高度上的可感知范圍，圓點(diǎn)為掃描的點(diǎn)，黑色實(shí)心圓點(diǎn)處可被感知，白色空心圓點(diǎn)處不可被感知，圖片下方中間位置的矩形區(qū)域局部細(xì)節(jié)放大效果圖如圖4 (b)所示，在梯形邊緣處點(diǎn)非常的密集，而在其他區(qū)域比較稀疏，這是由于掃描格網(wǎng)方向與視頻傳感器覆蓋范圍的邊緣并非正交，同時(shí)邊緣區(qū)域的障礙物對(duì)視線的遮擋，導(dǎo)致視頻傳感器視域范圍邊緣處的格網(wǎng)內(nèi)部非勻質(zhì)，需要逐步細(xì)化格網(wǎng)才能獲得精確覆蓋范圍值。

圖4 二值格網(wǎng)覆蓋掃描Fig.4 Coverage of corner points for the proposed method

本文方法在覆蓋范圍計(jì)算精度方面存在一些誤差。分析誤差來(lái)源:①離散化方法的固有特性，一方面，由于將地理環(huán)境進(jìn)行離散的過(guò)程中不可避免的誤差，增加格網(wǎng)的細(xì)分層次，細(xì)分格網(wǎng)到一定程度即可逼近真實(shí)覆蓋范圍，但實(shí)際應(yīng)用中并不是無(wú)限制地細(xì)化，而是細(xì)化到覆蓋面積變化不大即可；另一方面，格網(wǎng)剖分的方法無(wú)法處理格網(wǎng)中間有洞或者有島的情況，本文方法也不例外，即使當(dāng)前格網(wǎng)大小非最細(xì)級(jí)別，因?yàn)槠渚幋a為(1111)2和(0000)2，格網(wǎng)將不再細(xì)化，覆蓋面積將被高估/低估，若格網(wǎng)中洞/島面積不大，則對(duì)最終精度影響不大，否則將無(wú)法忽視其影響。在實(shí)際應(yīng)用中，此種屬于較為極端的情況，可以預(yù)先將較大尺寸的格網(wǎng)疊加在地理數(shù)據(jù)上，直觀判斷是否存在此種情況，然后通過(guò)調(diào)整格網(wǎng)大小來(lái)避免此種情況的發(fā)生。②地理場(chǎng)景復(fù)雜度，結(jié)合圖4和表3分析，由于地理環(huán)境中存在遮擋，不同剖分格網(wǎng)大小對(duì)計(jì)算精度影響較大。因此，在地理環(huán)境簡(jiǎn)單的情況下，可選用較小的剖分層次，以減少格網(wǎng)點(diǎn)覆蓋與否的判斷過(guò)程，提高效率，同時(shí)使精度不下降。

4 結(jié)論

本文提出了用二值格網(wǎng)掃描近似計(jì)算視頻傳感器覆蓋范圍的方法。該方法顧及地理環(huán)境中的障礙物等，將視頻傳感器覆蓋范圍計(jì)算從一個(gè)連續(xù)空間的通視性分析轉(zhuǎn)變到多個(gè)離散點(diǎn)的通視性分析，快速計(jì)算出覆蓋范圍；同時(shí)，利用格網(wǎng)細(xì)化的策略，分層次精細(xì)化覆蓋范圍，既可以降低需要處理的數(shù)據(jù)量，又可以保障覆蓋范圍計(jì)算的精度。為大范圍地理空間中視頻傳感器快速、精細(xì)覆蓋分析提供方法支持。本文的地理數(shù)據(jù)為二維矢量數(shù)據(jù)，對(duì)象的高度通過(guò)圖層屬性、手動(dòng)設(shè)置等方式設(shè)置，能夠用于地形較為平坦的城市區(qū)域的監(jiān)控。

本文方法可移植到三維GIS平臺(tái)中，因?yàn)槠浔举|(zhì)是基于數(shù)字表面模型(Digtal Surface Model，DSM)的可視域分析，只是此處可視域還受到相機(jī)參數(shù)的限制。本文方法尤其適合格網(wǎng)形式的DSM數(shù)據(jù)，其求得的覆蓋面積即為DSM在平面上的投影面積，在以覆蓋率為目標(biāo)的視頻監(jiān)控網(wǎng)絡(luò)/有向傳感器網(wǎng)絡(luò)優(yōu)化方法中，用投影面積代替曲面面積，影響并不大。若能夠利用三維數(shù)據(jù)更“真實(shí)”地模擬地理環(huán)境中的對(duì)象，采用本文方法能夠快速獲得更為精確的視頻傳感器覆蓋范圍。

References)

［1］陳文萍，楊萌，洪弋，等.視頻傳感器網(wǎng)絡(luò)覆蓋問(wèn)題［J］.計(jì)算機(jī)應(yīng)用，2013，33(6):1489-1494.CHEN Wenping，YANG Meng，Hong Yi，et.al.Coverage problems in visual sensor networks［J］.Journal of Computer Application，2013，33(6):1489-1494.(in Chinese)

［2］肖甫，王汝傳，葉曉國(guó)，等.基于改進(jìn)勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)路徑覆蓋增強(qiáng)算法［J］.計(jì)算機(jī)研究與發(fā)展，2009，46(12):2126-2133.XIAO Fu，WANG Ruchuan，YE Xiaoguo，et al.A path coverage-enhancing algorithm for directional sensor network based on improved potential field［J］.Journal of Computer Research and Development，2009，46(12):2126-2133.(in Chinese)

［3］蔣一波，王萬(wàn)良，陳偉杰，等.視頻傳感器網(wǎng)絡(luò)中無(wú)盲區(qū)監(jiān)視優(yōu)化［J］.軟件學(xué)報(bào)，2012，23(2):310-322.JIANG Yibo，WANG Wanliang，CHEN Weijie，et al.Coverage optimization of occlusion-free surveillance for video sensor networks［J］.Journal of Software，2012，23(2):310 -322.(in Chinese)

［4］陶丹，馬華東.有向傳感器網(wǎng)絡(luò)覆蓋控制算法［J］.軟件學(xué)報(bào)，2011，22(10):2317-2334.TAO Dan，MA Huadong.Coverage control algorithms for directional sensor networks［J］.Journal of Software，2011，22(10):2317-2334.(in Chinese)

［5］Erdem U M，Sclaroff S.Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements［J］.Computer Vision and Image Understanding，2006，103(3): 156-169.

［6］H?rster E，Lienhart R.On the optimal placement ofmultiple visual sensors［C］//Proceedings of the4th ACM International Workshop on Video Surveillance and Sensor Networks，ACM，2006:111-120.

［7］Malik R，Bajcsy P.Automated placement ofmultiple stereo cameras［C］//Proceedings of the 8th Workshop on Omnidirectional Vision，Camera Networks and Non-classical Cameras-OMNIVIS，2008.

［8］Shen C S，Zhang C，F(xiàn)els S.A multi-camera surveillance system that estimates quality-of-view measurement［C］// Proceedings of IEEE International Conference on Image Processing，IEEE，2007，3:193-196.

［9］Angella F，Reithler L，Gallesio F.Optimal deployment of cameras for video surveillance systems［C］//Proceedings of IEEE Conference on Advanced Video and Signal Based Surveillance，2007:388-392.

［10］Zhao J，F(xiàn)usion S，Planning S，et al.Camera planning and fusion in a heterogeneous camera network［J］.Dissertations＆Theses-Gradworks，2012.

［11］Zhao J，Cheung S C，Nguyen T.Optimal visual sensor network configuration［J］.Multi-camera Networks:Principles and Applications，2009:139-141.

［12］Zhao J，Cheung S S.Optimal visual sensor planning［C］// Proceedings of IEEE International Symposium on Circuits and Systems，IEEE，2009:165-168.

［13］Zhao J，Cheung S S.Multi-camera surveillance with visual tagging and generic camera placement［C］//Proceedings of 1stACM/IEEE International Conference on Distributed Smart Cameras，IEEE，2007:259-266.

［14］Zhao J，Yoshida R，Cheung S S，et al.Approximate techniques in solving optimal camera placement problems［J］.International Journal of Distributed Sensor Networks，2013.

［15］Liu L，Ma H D，Zhang X.Analysis for localization-oriented coverage in camera sensor networks［C］//Proceedings of Wireless Communications and Networking Conference，IEEE，2008:2579-2584.

［16］方陸明，柴紅玲，唐麗華，等.基于DEM的視頻可視域提取算法［J］.北京林業(yè)大學(xué)學(xué)報(bào)，2010，32(3):27-32.FANG Luming，CHAI Hongling，TANG Lihua，et al.An extraction algorithm of a DEM based video visualization domain［J］.Journal of Beijing Forestry University，2010，32(3):27-32.(in Chinese)

［17］張剛，湯國(guó)安，宋效東，等.基于DEM的分布式并行通視分析算法研究［J］.地理與地理信息科學(xué)，2013，29(4): 81-85.ZHANG Gang，TANG Guoan，SONG Xiaodong，et al.Research on distributed parallel visibility analysis algorithm based on DEM［J］.Geography and Geo-Information Science，2013，29(4):81-85.(in Chinese)

［18］王晨昊，湯曉安，馬伯寧，等.基于距離場(chǎng)映射的地形可視域分析方法［J］.測(cè)繪學(xué)報(bào)，2011，5:563-568.WANG Chenhao，TANG Xiaoan，MA Boning，et al.Terrain viewshed analysismethod based on distance field mapping［J］.Acta Geodaetica et Cartographica Sinica，2011，5:563-568.(in Chinese)

Fine camera coverage calculation method

WANG Ziran1，ZHANGYanan2，3，LIU Xuejun2，3，4，WANGMeizhen2，3，4
(1.Nanjing Normal University Taizhou College，Taizhou 225300，China；2.School of Geography Science，Nanjing Normal University，Nanjing 210023，China；3.Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application，Nanjing 210023，China；4.Key Laboratory of Police Geographic Information Technology Ministry of Public Security，Changzhou 213022，China)

Camera coverage is an important basis of camera network initial configuration，optimal deployment and so on.Its precision and efficiency are the critical influences on the results of coverage analysis，which are very important to the application of large area camera coverage analysis，butmanymethods do not consider them.A new method to efficiently estimate camera coverage was proposed.Firstly，the geographic space was dispersed into grids.Secondly，the statuses of the four corners of each grid were computed.If the cornerwas covered by the camera，the statuswas denoted by using1 or0.So the statusof the gird can be presented by the codewhich iseither0 or1.Consequently there are16 statuses to represent the status of a grid.Finally，if the code of the grid was not(0000)or(1111)，the gird would be divided into four isometrical subgirds until the sub-girdswere small enough or their codes were(0000)or(1111).According to the levels and statues of all grids，the whole camera coveragewas estimated.Experimental results show that the proposed method can obtain more precise camera and can give consideration to both efficiency and accuracy.

camera coverage；coverage analysis；bi-valued grid；grid-fractionizing

TN95

A

1001-2486(2015)05-054-07

10.11887/j.cn.201505009

http://journal.nudt.edu.cn

2015-06-25

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金資助項(xiàng)目(41401442，41201417)；國(guó)家863計(jì)劃資助項(xiàng)目(2015AA123901)；江蘇省高校自然科學(xué)研究面上資助項(xiàng)目(14KJB170011)；博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(新教師類)(20133207120017)；江蘇省測(cè)繪科研資助項(xiàng)目(JSCHKY201204)；測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(12E01)；公安部科技強(qiáng)警基礎(chǔ)工作專項(xiàng)資助項(xiàng)目(2014GABJC009)；泰州市科技局科技支撐計(jì)劃資助項(xiàng)目(TS036)

王自然(1983—)，男，江蘇鹽城人，講師，碩士，E-mail:wangzr@outlook.com