王迎春，王義春，侯艷權(quán)，郭樹(shù)強(qiáng)，張 帆

(1.國(guó)網(wǎng)黑龍江省電力有限公司七臺(tái)河供電公司，黑龍江 七臺(tái)河 154600; 2.東北電力大學(xué) 計(jì)算機(jī)學(xué)院，吉林 吉林132012)

0 引 言

近年來(lái)，電網(wǎng)規(guī)模不斷擴(kuò)大，工程安全性問(wèn)題也成為了重中之重。為了滿足日益增長(zhǎng)的安全性需求，智慧工地在電網(wǎng)行業(yè)得到了廣泛的應(yīng)用。智慧工地即通過(guò)物聯(lián)網(wǎng)技術(shù)獲取工地中的現(xiàn)場(chǎng)視頻等實(shí)時(shí)數(shù)據(jù)進(jìn)行提取分析，以達(dá)到降低事故發(fā)生概率等目的。其提取處理的內(nèi)容包括對(duì)獲取的視頻中的人物進(jìn)行目標(biāo)檢測(cè)、越界檢測(cè)等。越界檢測(cè)是防止施工現(xiàn)場(chǎng)的工人走出安全區(qū)產(chǎn)生危險(xiǎn)的一個(gè)解決辦法，但傳統(tǒng)的越界檢測(cè)中，安全區(qū)域一般固定為矩形，不能滿足電力工程中復(fù)雜的施工環(huán)境，難以解決工地中工人走出安全區(qū)進(jìn)入高壓危險(xiǎn)區(qū)域的問(wèn)題，所以提出將多邊形內(nèi)外點(diǎn)判斷算法應(yīng)用于電網(wǎng)智慧工地中的越界檢測(cè)，將多邊形作為安全區(qū)域的邊界，通過(guò)目標(biāo)檢測(cè)確認(rèn)目標(biāo)工人的一點(diǎn)，通過(guò)該點(diǎn)是否在多邊形內(nèi)部的判斷實(shí)現(xiàn)工人是否越界的判斷，完成安全區(qū)域內(nèi)工人的越界檢測(cè)，提高電力施工的安全性。

判斷目標(biāo)點(diǎn)是否在多邊形內(nèi)是計(jì)算機(jī)視覺(jué)中的傳統(tǒng)問(wèn)題，主要應(yīng)用于地理信息系統(tǒng)等方面。該問(wèn)題自提出后，得到了眾多學(xué)者的關(guān)注。目前主要有文獻(xiàn)[1-2]提出的射線法、文獻(xiàn)[3]提出的夾角之和檢驗(yàn)法、文獻(xiàn)[4]提出的面積和法等，這些算法雖過(guò)程簡(jiǎn)單、空間復(fù)雜度較低，但是算法的時(shí)間復(fù)雜度較高，應(yīng)用到實(shí)際項(xiàng)目中時(shí)耗時(shí)嚴(yán)重。因此，在二叉空間分隔(Binary Space Partitioning, BSP)樹(shù)的基礎(chǔ)上進(jìn)行多邊形內(nèi)外點(diǎn)判斷算法的改進(jìn)，提高判斷速度以應(yīng)用于實(shí)際問(wèn)題中。

1 傳統(tǒng)多邊形內(nèi)外點(diǎn)判斷算法

1.1 射線法

射線法是最早提出的多邊形內(nèi)外點(diǎn)判斷算法，判斷過(guò)程如下[5]：

1)判斷目標(biāo)點(diǎn)A(x0,y0)與多邊形的頂點(diǎn)P(xi,yi),(i=1,2,...,n)是否相同或目標(biāo)點(diǎn)是否在多邊形的邊上，若都不在則進(jìn)行下一步。

2)計(jì)算|y0-yi|的最小非0值，記為my；計(jì)算|x0-xi|的最大值，記為Mx。

3)由目標(biāo)點(diǎn)引出1條射線，為了避免射線與多邊形頂點(diǎn)相交，將射線斜率定為my/2Mx。所以射線參數(shù)方程為R=(x0,y0)+k(2Mx,my),(0

4)將應(yīng)用射線法將判斷點(diǎn)與多邊形的關(guān)系轉(zhuǎn)換為判斷該射線和多邊形的邊的交點(diǎn)數(shù)。計(jì)算交點(diǎn)數(shù)需計(jì)算D1(D-D1)>0和D2(D-D2)>0，其中：

5)算出交點(diǎn)個(gè)數(shù)，若為奇數(shù)則點(diǎn)在多邊形內(nèi)，若為偶數(shù)則點(diǎn)在多邊形外。

1.2 傳統(tǒng)基于BSP樹(shù)的多邊形內(nèi)外點(diǎn)判斷算法

1.2.1 BSP樹(shù)的原理和構(gòu)建

BSP樹(shù)是一種空間分割樹(shù)，它主要用于游戲中的場(chǎng)景管理，尤其是室內(nèi)場(chǎng)景的管理。它的本質(zhì)是二叉樹(shù)，也就是用一個(gè)面把空間分割成兩部分，分割出的空間則繼續(xù)用面分割，以此類推，直到達(dá)到特定遞歸深度，或者空間中不再有物體或只剩下1個(gè)物體。

應(yīng)用于二維空間的BSP的基本原理是將所有平面建成一棵樹(shù)，每個(gè)平面都將它所在的空間分為2個(gè)部分，空間位于平面的前后位置決定了代表空間的節(jié)點(diǎn)在樹(shù)中的位置。

傳統(tǒng)基于BSP樹(shù)進(jìn)行點(diǎn)在多邊形內(nèi)外判斷的算法將BSP樹(shù)應(yīng)用于二維空間進(jìn)行分區(qū)[6]：假設(shè)給出平面P及直線方程ax+by+c=0，該直線穿過(guò)平面并將平面分成兩個(gè)部分,直線的法向量n(a,b)指向的一側(cè)為正，而另一側(cè)為負(fù)。用BSP樹(shù)來(lái)表示分區(qū)結(jié)果：樹(shù)中的每1個(gè)節(jié)點(diǎn)表示1條分割平面的直線，節(jié)點(diǎn)的左子樹(shù)表示正側(cè)，右子樹(shù)表示負(fù)側(cè)；每1個(gè)分割的區(qū)域都可以由另外的直線再次分割，遞歸下去最后得到的區(qū)域由樹(shù)的葉子節(jié)點(diǎn)表示。如圖1的多邊形分區(qū)后由圖2的二叉樹(shù)表示，多邊形中a代表分區(qū)直線，p代表所分區(qū)域。

圖1 多邊形分區(qū)結(jié)果

圖2 BSP樹(shù)表示結(jié)果

1.2.2 算法流程

傳統(tǒng)基于BSP樹(shù)的多邊形內(nèi)外點(diǎn)判斷算法的流程如下所述：

1)給定1個(gè)任意的簡(jiǎn)單多邊形，根據(jù)多邊形的具體形狀以及頂點(diǎn)坐標(biāo)進(jìn)行垂直分解，形成多條垂直掃描線，每2條掃描線形成1個(gè)垂直區(qū)域并結(jié)合BSP樹(shù)構(gòu)建的方法構(gòu)建1顆BSP樹(shù)以表示這些垂直區(qū)域。

2)利用多邊形的邊作為劃分直線，基于劃分直線兩邊的區(qū)域個(gè)數(shù)構(gòu)成1棵與多邊形的邊有關(guān)的BSP樹(shù)。

3)在判斷目標(biāo)點(diǎn)是否在給定的多邊形中時(shí)，用建好的垂直區(qū)域部分的BSP樹(shù)查找目標(biāo)點(diǎn)所在的垂直范圍，如果查找到，利用邊部分的BSP樹(shù)確定目標(biāo)節(jié)點(diǎn)所在的具體區(qū)域，從而可以判斷出目標(biāo)點(diǎn)是否在多邊形內(nèi)部。

傳統(tǒng)算法的時(shí)間復(fù)雜度不穩(wěn)定，當(dāng)BSP樹(shù)的每個(gè)節(jié)點(diǎn)只有左子樹(shù)或右子樹(shù)時(shí)，樹(shù)結(jié)構(gòu)會(huì)退化為鏈表，時(shí)間復(fù)雜度會(huì)上升。

2 多邊形內(nèi)外點(diǎn)判斷算法的改進(jìn)及應(yīng)用

2.1 改進(jìn)多邊形內(nèi)外點(diǎn)判斷算法的流程

為了防止BSP樹(shù)退化為鏈表，首先對(duì)多邊形各個(gè)頂點(diǎn)的橫坐標(biāo)值進(jìn)行歸并排序，其次用二分法遍歷已經(jīng)有序頂點(diǎn)的垂直直線，最后建立垂直區(qū)域的BSP樹(shù)。經(jīng)過(guò)排序再遍歷可以使最后形成的BSP樹(shù)為平衡二叉樹(shù)，不會(huì)退化為鏈表，具體流程如下。

1)假定給出任意的簡(jiǎn)單多邊形Q，如圖3所示。

圖3 簡(jiǎn)單多邊形Q

2)根據(jù)多邊形的最大及最小坐標(biāo)值，建立多邊形的外包圍盒，如圖4所示。

3)對(duì)多邊形Q的各個(gè)頂點(diǎn)的橫坐標(biāo)值進(jìn)行歸并排序并用二分法對(duì)有序的豎直直線進(jìn)行遍歷，構(gòu)建垂直區(qū)域的平衡二叉樹(shù)。由于使用二分法進(jìn)行遍歷，所以從邊a7開(kāi)始處理。a7的x1將多邊形劃分為2個(gè)區(qū)域，而a7的x2將其中1個(gè)區(qū)域又劃分為2個(gè)部分，如圖5所示。

圖4 簡(jiǎn)單多邊形的外包圍盒

圖5 被x1與x2分割后的包圍盒

4)劃分完1個(gè)垂直區(qū)域后，將這個(gè)區(qū)域之中的多邊形的邊插入，使得1個(gè)區(qū)域被劃分為若干個(gè)梯形區(qū)域。如圖6所示，劃分完垂直區(qū)域后，生成垂直區(qū)域的BSP樹(shù)，再將邊a7插入，即將a7按其所對(duì)應(yīng)的區(qū)域插入BSP樹(shù)中。

圖6 插入邊a7的結(jié)果

5)對(duì)于余下各邊，均采取同樣的方式進(jìn)行處理，將每一個(gè)垂直區(qū)域和垂直區(qū)域內(nèi)的若干梯形區(qū)域都使用BSP樹(shù)進(jìn)行管理，多邊形的處理結(jié)果如圖7所示，所構(gòu)建的二叉樹(shù)如圖8所示。

6)構(gòu)建好二叉樹(shù)后，判斷點(diǎn)和多邊形的關(guān)系，首先在垂直區(qū)域的BSP樹(shù)查找目標(biāo)點(diǎn)所在的垂直區(qū)域，確定了垂直區(qū)域后，再查找相應(yīng)邊的BSP樹(shù)，最后確定點(diǎn)是否在多邊形內(nèi)部。

圖7 插入所有邊的結(jié)果

圖8 改進(jìn)算法后構(gòu)建的二叉查找樹(shù)

2.2 改進(jìn)多邊形內(nèi)外點(diǎn)判斷算法的實(shí)現(xiàn)

算法的輸入為任意簡(jiǎn)單多邊形，輸出為判斷點(diǎn)是否在多邊形內(nèi)的結(jié)果，具體步驟如下：

1)讀入離散點(diǎn)和多邊形；

2)構(gòu)造多邊形的外包圍盒；

3)對(duì)多邊形的端點(diǎn)橫坐標(biāo)值排序；

4)用二分法遍歷排序后端點(diǎn)的垂直分割線，構(gòu)建垂直區(qū)域的BSP樹(shù)；

5)遍歷多邊形的邊，將邊插入到對(duì)應(yīng)垂直區(qū)域的BSP樹(shù)中，生成與邊有關(guān)的BSP樹(shù)；

6)在BSP樹(shù)中查找目標(biāo)點(diǎn)并給出結(jié)果。

2.3 算法的特殊情況

當(dāng)要查詢的目標(biāo)點(diǎn)正好位于劃分直線上，即多邊形的邊上時(shí)，將該點(diǎn)進(jìn)行單獨(dú)處理。將該點(diǎn)分別左移、右移一小段距離，兩次移動(dòng)后分別對(duì)移動(dòng)后的點(diǎn)是否在多邊形內(nèi)再次進(jìn)行判斷。若兩次結(jié)果都在多邊形內(nèi)(外)部，則說(shuō)明移動(dòng)前該點(diǎn)在多邊形內(nèi)(外)部；若兩次結(jié)果不一致，則采用其他方法進(jìn)行判別。

2.4 算法的實(shí)驗(yàn)結(jié)果及應(yīng)用

所提算法在研究點(diǎn)是否在多邊形內(nèi)時(shí)，分為創(chuàng)建BSP樹(shù)和查找兩個(gè)階段。在創(chuàng)建BSP樹(shù)時(shí)，對(duì)多邊形各個(gè)頂點(diǎn)的橫坐標(biāo)值進(jìn)行排序，由于使用的是歸并排序，所以時(shí)間復(fù)雜度為O(nlgn)；創(chuàng)建多邊形對(duì)應(yīng)的BSP樹(shù)的時(shí)間復(fù)雜度為O(nlgn)；所以，創(chuàng)建BSP樹(shù)的時(shí)間復(fù)雜度是O(nlgn)。創(chuàng)建完成后，對(duì)點(diǎn)是否在多邊形內(nèi)部進(jìn)行判斷，在垂直區(qū)域的BSP樹(shù)中查找目標(biāo)點(diǎn)所在的垂直區(qū)域，由于排序之后是平衡二叉樹(shù)，所以時(shí)間復(fù)雜度為O(lgn)；確定點(diǎn)屬于的垂直區(qū)域后，對(duì)確定的垂直區(qū)域?qū)?yīng)的邊的BSP樹(shù)進(jìn)行查找，假定每個(gè)垂直區(qū)域包含m條邊(一般m

將算法應(yīng)用到電力智慧工地中時(shí)，根據(jù)應(yīng)用場(chǎng)景的實(shí)際情況，選擇在能拍到目的區(qū)域的點(diǎn)處安裝攝像頭，并提前對(duì)攝像頭能拍攝到的區(qū)域圖像做劃分處理，用坐標(biāo)的方法在圖像中劃分出安全區(qū)。以圖9場(chǎng)景為例進(jìn)行越界檢測(cè)，畫(huà)線區(qū)域內(nèi)部為安全區(qū)，畫(huà)線外部為危險(xiǎn)區(qū)域。

圖9 越界檢測(cè)實(shí)驗(yàn)場(chǎng)景

在對(duì)工人的目標(biāo)檢測(cè)方面，首先，把VGG16卷積神經(jīng)網(wǎng)絡(luò)模型在ImageNet數(shù)據(jù)集上進(jìn)行參數(shù)初始化；其次，在CVC行人數(shù)據(jù)庫(kù)的數(shù)據(jù)集(數(shù)據(jù)集地址：http://www.cvc.uab.es/adas/site/?q=node/7)上訓(xùn)練基于VGG16的SSD檢測(cè)模型；最后，在攝像頭傳輸?shù)囊曨l中，每秒抽取24幀圖像作為檢測(cè)圖像，對(duì)工人進(jìn)行目標(biāo)檢測(cè)。將檢測(cè)結(jié)果返回回歸框的左上角和右下角的坐標(biāo)點(diǎn)，提取回歸框下邊界的中心點(diǎn)，再進(jìn)一步利用改進(jìn)多邊形內(nèi)外點(diǎn)判斷算法判斷工人是否越過(guò)安全區(qū)。

射線法、傳統(tǒng)多邊形內(nèi)外點(diǎn)判斷算法與改進(jìn)多邊形內(nèi)外點(diǎn)判斷算法的時(shí)間對(duì)比結(jié)果如表1所示，表中數(shù)據(jù)為各個(gè)算法的相對(duì)運(yùn)行時(shí)間。根據(jù)表1可知，改進(jìn)多邊形內(nèi)外點(diǎn)判斷算法的判斷速度更快。將改進(jìn)多邊形內(nèi)外點(diǎn)判斷算法應(yīng)用于電力智慧工地中進(jìn)行工人是否越過(guò)安全區(qū)的判斷，試驗(yàn)結(jié)果表明，該算法能有效地解決工人越界問(wèn)題，使電力智慧工地中的安全區(qū)域劃分更加精準(zhǔn)，并提高施工安全性。

表1 不同算法的判斷時(shí)間對(duì)比Table 1 Comparison of judgment time under different algorithms ms

3 結(jié) 語(yǔ)

對(duì)改進(jìn)多邊形內(nèi)外點(diǎn)判斷算法進(jìn)行闡述，并將改進(jìn)算法與傳統(tǒng)算法等進(jìn)行對(duì)比實(shí)驗(yàn)，比較判斷時(shí)間后給出實(shí)驗(yàn)結(jié)果，結(jié)果表明改進(jìn)算法比傳統(tǒng)算法的判斷速度快。同時(shí)，將改進(jìn)算法應(yīng)用到電力工程領(lǐng)域，用于實(shí)際的行人越界檢測(cè)，檢測(cè)結(jié)果表明該算法可以有效判斷行人是否跨出安全區(qū)，提高了電力工程的安全性，有較大的實(shí)用價(jià)值。