竇本君，紀 勇，鄭尚高，馮冬青，羅 勇

(1.鄭州大學 電氣工程學院，河南 鄭州 450001； 2.河南騰龍信息工程有限公司，河南 鄭州 450007)

基于降維數據邊界點曲率的變電站設備識別

竇本君1，紀 勇2，鄭尚高2，馮冬青1，羅 勇1

(1.鄭州大學 電氣工程學院，河南 鄭州 450001； 2.河南騰龍信息工程有限公司，河南 鄭州 450007)

為了對變電站三維仿真模型進行快速重建，針對變電站設備三維數據量過大，不能快速識別的問題，通過對設備的三維數據做降維處理，減少數據處理量，研究利用降維后的數據對設備進行快速精確識別的方法.通過分析降維數據點集的特征，筆者提出一種利用降維數據邊界點曲率進行識別的方法，其中邊界點提取采用基于Alpha Shapes原理的滾圓法，邊界點的曲率通過點到弦的距離累積來計算，最后利用邊界點的曲率來識別不同的設備.仿真實驗表明，該識別方法簡潔高效，大大降低了計算量，并且能夠有效地識別不同設備.

三維數據；識別；降維；邊界點；曲率；仿真

0 引言

隨著地理信息系統(tǒng)向三維領域的逐漸發(fā)展，三維數字化電網的研究快速升溫，其中對三維對象的快速建模漸漸成為研究的熱點.想要對變電站進行三維模型重構，就必須對變電站里的設備進行識別，以便區(qū)分設備種類.傳統(tǒng)三維模型的重建，主要靠人眼對采集的三維點云數據進行識別辨認，然后在3dmax模型庫找到相匹配的模型，再用于建模，這消耗大量的人力，效率很低，影響整個建模的進程.目前還沒有一種很好的可以自動識別點云數據的方法.

針對三維物體的識別，文獻[1]引入自旋圖像(spin-image)的特征，對物體的三維特征進行描述，進而達到識別和定位的目的，但該方法計算量太大.RUSU等[2]提出的viewpoint feature histogram(VFH)算法，通過目標區(qū)域的三維點云數據計算它的VFH特征并進行匹配，但是這種方法對數據的空間分辨率有很高的要求，而且不能滿足實時性的要求.文獻[3]定義了一個最大一致形狀片，并且將它組織成一個無向圖，然后使用分層的圖同構方法來識別三維物體，但是該方法在處理物體的遮擋問題時比較困難.郭裕蘭等[4]提出采用“點云”正交表面投影特征來進行模型的快速預選，然后利用ICP算法把目標和模板的“點云”進行精確匹配.三維點云數據可以比較準確地表示物體的外形信息，研究人員將利用點云數據對設備進行識別，但是設備的三維數據量很大，直接用于識別計算量很大，所以筆者提出一種基于設備投影平面點集邊界點曲率的識別方法，從而實現對變電站設備的快速保真識別[5-6].

1 提取降維數據邊界點

投影平面點集邊界點的提取是變電站設備識別非常關鍵的一步.筆者采用基于Alpha Shapes原理[7]的滾圓法對變電站設備降維數據的邊界點進行提取.

1.1 滾圓法基本原理

對于任意一個點集，我們可以用釘在平面上的釘子來表示.假如用一個半徑為α的圓環(huán)從邊界靠近這個釘群，然后讓這個圓環(huán)圍繞釘群滾動一圈，當α足夠大時，每次滾動，這個圓環(huán)都會被兩個釘子卡住，這樣滾動一圈所接觸到的釘子就是這個釘群的邊界，也就是這個點集的外邊界點.利用滾圓法提取邊界點的示意圖如圖1所示.

模型判斷條件：在點集S內，任意選取兩點P1、P2，過這兩點繪制半徑為α的圓，若這個圓內不包含別的點，點P1、P2就被認為是邊界點.

1.2 滾圓法提取設備二維點集邊界點步驟

(1) 點云數據降維

將設備的點云數據分別向xoy、yoz、xoz平面投影，得到設備在3個平面的二維數據點集.

圖1 滾圓法提取邊界點示意圖

(2) 提取投影平面點集的邊界點

①首先選取點集S中y坐標最小(假如y值相同則取x值最大)的點為起始邊界點P1.

②選定半徑α，搜索距離P1點小于2×α的點構成的子集S2[8]，在S2中任取一點P2，求出經過P1、P2且半徑為α的圓的圓心O.

已知兩點坐標和半徑α，求該圓圓心的步驟如下：

假如兩點坐標分別為(x1,y1)、(x2,y2)，所給半徑為α，圓心坐標為(x,y).列出如下方程組

(1)

求解方程組(1)就可以得到圓心的坐標(x,y).但是直接對該方程組求解比較麻煩，我們可以用測繪學中的距離交匯法來求圓心坐標[9].

(2)

式中：

(3)

S2=(x1-x2)2+(y1-y2)2.

(4)

當兩點的距離小于2α時，能求得兩個過這兩點且半徑為α的圓[10]，H的取值有正負兩種情況，所求得的圓心分別為O和O′，如圖2所示.

③在點集S2中，分別求出(除去P1、P2外)所有點距離圓心O的長度L.

假如所有L都大于半徑α，則認為點P1、P2是邊界點；假如有L小于半徑α，則停止此步運行，轉去執(zhí)行第④步.由步驟②可知經過距離小于2α的兩點且半徑為α的圓有兩個，所以我們要考慮兩種情況，只要存在一個圓，且圓內沒有別的點時，我們認為P1、P2是所求的邊界點.

④對S2中的下一個點進行②～③步判斷，直到把S2中的所有點都進行一次邊界點判斷.

圖2 距離交匯法求圓心示意圖

⑤將②～③步得到的邊界點P2重新當作起始邊界點，重復②～④步判斷.每次搜索邊界點時都會得到兩個不同的邊界點，如果搜索到的新邊界點與已經得到的邊界點相同，則不保存，只保存不同的邊界點.直到重新搜索到第一個邊界點，則搜索結束.

2 計算邊界點曲率

2.1 相關研究

曲率表示曲線在一點的彎曲程度，從曲線的曲率圖上，可以知曉曲線的凹凸部分，并由此得到曲線的大致形狀.不過平面離散曲線一般都是不連續(xù)的，而且不可導，很難求得它的曲率.利用尺度空間理論[11]和圓弧擬合算法[12]可以求得離散曲線的曲率，但是這兩種方法計算量較大.彭鐵根[13]利用一條固定不動的弦，然后求得曲線段上每一點到弦的距離，最后求出一點的距離累積.該算法計算量較小，且具有較好的魯棒性能.

2.2 點到弦的距離累積

在此，距離符號可以利用一個判別矩陣的行列式值來進行判斷，設如下判別矩陣

Mj,L(i)=(xi+L-xi-Lyi+L-yi-Lxj-xi-Lyj-yi-L).

(5)

圖3 點到弦的距離

則有

(6)

(7)

設Pi點的距離累積和為SL(i)，則有

(8)

對于具有封閉特性的離散曲線，按照式(8)沿順時針方向環(huán)繞曲線一周，就可以獲得所有點的點到弦的距離累積值SL(i).我們可以用一點的距離累積來近似代表曲線上該點的曲率[14].

2.3 曲率分布直方圖相似度比較

求出邊界點曲率以后，再求曲率分布直方圖.用直方圖匹配方法來進行相似度比較，采用歐氏函數ME(Q,D)對直方圖間的距離進行衡量，

(9)

(10)

式中:k代表曲率相應分段取值;L是曲率分段的個數;nk是圖像中相應曲率段內點的個數;N是圖像邊界點總數.

3 實驗與仿真

試驗數據為2014年在鄭州-嵩山500 kV變電站采集，選用10種設備作為模板，編號ID為0～9.首先計算10種設備在3個投影平面的邊界點曲率分布，并存入模型數據庫.被測樣本選取20組，每種設備選取不同位置的兩組數據.求邊界點曲率時，參數L=5，繪制直方圖時，分別求出10種設備在3個平面邊界點曲率ρ的最小值和最大值，離散區(qū)間數num=(ρmax-ρmin)/0.06.10種模板設備點云數據的三維視圖,如圖4所示.

圖4 模型數據庫設備的三維視圖

選取00號樣本進行試驗，將設備向3個平面投影，利用滾圓法提取投影平面點集的邊界點，結果如圖5所示.其中圖5(a)、圖5(b)、圖5(c)分別為樣本在xoy、yoz、xoz平面投影點集的邊界點.由圖5可知，不管設備的投影圖像是否規(guī)則，滾圓法都可以比較精確的提取點集的外邊界點.

圖5 邊界點提取

根據公式(5)～(8)，依次求得樣本設備在3個投影平面二維點集邊界點的曲率，曲率值如圖6所示，并用曲率的頻率分布直方圖來表示，如圖7所示.利用相同的方法求出其他樣本設備的邊界點曲率，并求出曲率分布.

圖6 樣本設備在3個投影平面的邊界點曲率

利用公式(9)和(10)，將20組樣本數據在3個投影平面邊界點的曲率分布與模型數據庫中比較，并將3個平面的比較結果求平均，得到表1，其中橫向ID為模板，豎向為測試樣本.

圖7 樣本設備在3個投影平面邊界點曲率分布直方圖

表1 20組待測樣本與模型庫在3個平面投影點集邊界點曲率分布直方圖相似性比較

Tab.1 Boundary points curvature distribution histogram similarity comparison between 20 samples and model base under three projection planes

樣本ID模型庫中10類模板ID0123456789000.00140.52130.79790.84820.96830.88650.93620.88640.93470.9426010.00130.57150.7810.85050.89620.92730.91050.89730.92630.9372100.59790.00440.86120.83930.87920.91580.88430.84730.90350.8843110.20250.37710.87140.86990.89470.84750.89520.78360.89420.8792200.84930.83750.00120.89500.79420.80140.84370.79050.83920.9017210.86170.88470.00250.85030.78510.83710.85430.80920.81520.8972300.79520.83620.60460.35210.88630.84730.90210.88640.25790.8745310.80610.83780.54720.00250.87520.89530.89050.87920.89530.8854400.89640.87660.88930.88730.00150.60730.88430.89060.87530.8945410.88740.90230.89720.87940.00120.58420.85720.86470.88350.8796500.89050.80720.86570.85730.65830.00150.88590.89050.88430.8495510.88630.79580.85490.86350.58490.00130.89430.87030.85700.8793600.88740.81470.88470.89250.85730.79580.00250.90130.88940.9025610.87480.85940.88520.87940.88620.82690.00230.89350.85730.8957700.85820.86050.89370.90150.89060.79580.80620.00150.80690.8837710.84930.85720.88530.88940.85470.82540.79380.00170.83620.8638800.87390.84730.86920.90610.28370.87360.80280.81470.32130.9017810.88270.85060.90250.89730.86530.89720.85730.84590.00180.8849900.86930.88060.91280.88560.86470.85740.86920.85720.89060.0015910.84720.87260.89170.85930.83290.84930.87480.90160.85470.0012

已知樣本00、01與模板0是同種設備，其他樣本命名類似.由表1可以看出，20種待測樣本中，除11、30、80號樣本外，其他均能得到有效的匹配，識別率為85%，其中11號樣本識別成了0號模型，30號樣本識別成了8號模型，80號樣本識別成了4號模型，這是由于采集的點云數據不完整造成的，數據足夠完整時，識別率將更高.

為了驗證本算法的效率，與文獻[14]相比較，平臺為Intel(R) Core(TM) Duo CPU 2.0GHz處理器，筆者通過提取二維平面點云數據邊界點，計算邊界點曲率并匹配，識別單個物體總共需要10 s左右.而文獻[14]通過找到最近點時間，找到對應匹配曲面對并驗證，總共需要50 s左右.因此可以看出筆者的算法具有很高的效率.

4 結論

筆者通過將設備在三個平面進行投影，減少數據處理量，然后求取三個投影平面的點集的邊界點曲率并用于識別.其中邊界點提取所采用的滾圓法以及求曲率時所采用的點到弦的距離累積近似，都大大減小了計算量.該識別方法簡單高效，可以快速地對采集的三維點云數據進行識別，加快了變電站三維模型的重建.

[1] LIU Y, MA J, ZHAO J. Three dimensional automatic target recognition based on spin-images [J]. Infrared and laser engineering, 2012, 41(2):543-548.

[2] RUSU R B, BRADSKI G, THIBAUX R, et al. Fast 3d recognition and pose using the viewpoint feature historam[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems. Taibei: IEEE Conference Publications, 2010:2155-2162.

[3] DORAI C H. COSMOS: A framework for representation and recognition of 3d free-from objects[D]. Dissertation: Michigan State Univ,1997.

[4] GUO Y L, LU M, TAN Z G. Fast target recognition in laser using projection contour features [J]. Chinese journal of lasers, 2012(2):200-205.

[5] GRAHAM R L. An efficient algorithm for determining the convex hull of a finite planar set [J]. Information processing letters, 1972, 1(4): 132-133.

[6] SAMPATH A, SHAN J. Buliding boundary tracing and regularization from airborne LiDAR point clouds[J]. Photogrammetric engineering and remote sensing, 2007, 73(7):805-812.

[7] EDELSBRUNNER H, KIRKPATRICK D, SEIDEL R. On the shape of a set of points in the plane[J]. IEEE information theory society, 1983, 29(4):551-559.

[8] 沈蔚,李京,陳云浩,等. 基于LIDAR數據的建筑輪廓線提取及規(guī)則化算法研究[J]. 遙感學報, 2008, 12(5):692-698.

[9] 張宏,溫永寧,劉愛利,等. 地里信息系統(tǒng)算法基礎[M].北京：科學出版社, 2006.

[10]王宗躍,馬洪超,徐宏根,等. 海量點云的邊緣快速提取算法[J]. 計算機工程與應用, 2010, 46(36):213-215.

[11]MOKHTARIAN F, MACKWORTH A. Scale-based description and recognition of planar curves and two-dimensional shapes[J]. IEEE transaction pattern analysis and machine intelligence, 1986, 8(1):34-43.

[12]YANG X N, WANG G Z. Planar point set fairing and fitting by arc splines[J]. Computer-aided design, 2001, 33(1):35-43.

[13]彭鐵根,吳惕華. 基于負曲率極值點的零件識別與檢測技術研究[J].系統(tǒng)仿真學報, 2006,18(11):3058-3062.

[14]魏永超,劉長華,杜冬. 基于曲面分割的三維點云物體識別 [J].光子學報, 2010, 39(12):2268-2273.

Substation Equipment Identification Based on Boundary Curvature of Dimension-reduced Point Set

DOU Benjun1, JI Yong2, ZHENG Shanggao2, FENG Dongqing1, LUO Yong1

(1.School of Electrical Engineering, Zhengzhou University, Zhengzhou 450001, China； 2.Henan Tenglong Information and Engineering Company, Zhengzhou 450007,China )

In order to build 3D simulation model of transformer substation, the device should be indentified quickly. But the 3D data of substation equipment was so large that it was difficult to identify quickly. This paper used dimension reduction to reduce the amount of data. It provided a method to identify equipment quickly using the dimension-reduced data. After analyzing the characteristic of the dimension-reduced data, a method using boundary curvature of dimension reduction point set was proposed. In the process, a rolling method based on principle of Alpha Shapes to extract the boundary points was proposed. The curvature of the boundary point was acquired by point-to-chord distance accumulation. Then equipment was idenfified by using boundary curvature. The simulation results showed that the method was concise and efficient. It could identify different equipment and reduce the amount of calculation greatly.

3D data; identify; dimension-reduced; boundary points; curvature; simulation

2016-07-08；

2016-08-18

國家自然科學基金資助項目(61473266)；河南省產學研合作項目(152107000058)

馮冬青(1958— )，男，廣東佛山人，鄭州大學教授，主要從事智能控制理論與應用、圖像處理、模式識別等研究，E-mail：dqfeng@zzu.edu.cn.

1671-6833(2017)02-0061-05

TP391

A

10.13705/j.issn.1671-6833.2017.02.014