竇本君,紀(jì) 勇,鄭尚高,馮冬青,羅 勇
(1.鄭州大學(xué) 電氣工程學(xué)院,河南 鄭州 450001; 2.河南騰龍信息工程有限公司,河南 鄭州 450007)
基于降維數(shù)據(jù)邊界點(diǎn)曲率的變電站設(shè)備識(shí)別
竇本君1,紀(jì) 勇2,鄭尚高2,馮冬青1,羅 勇1
(1.鄭州大學(xué) 電氣工程學(xué)院,河南 鄭州 450001; 2.河南騰龍信息工程有限公司,河南 鄭州 450007)
為了對(duì)變電站三維仿真模型進(jìn)行快速重建,針對(duì)變電站設(shè)備三維數(shù)據(jù)量過大,不能快速識(shí)別的問題,通過對(duì)設(shè)備的三維數(shù)據(jù)做降維處理,減少數(shù)據(jù)處理量,研究利用降維后的數(shù)據(jù)對(duì)設(shè)備進(jìn)行快速精確識(shí)別的方法.通過分析降維數(shù)據(jù)點(diǎn)集的特征,筆者提出一種利用降維數(shù)據(jù)邊界點(diǎn)曲率進(jìn)行識(shí)別的方法,其中邊界點(diǎn)提取采用基于Alpha Shapes原理的滾圓法,邊界點(diǎn)的曲率通過點(diǎn)到弦的距離累積來計(jì)算,最后利用邊界點(diǎn)的曲率來識(shí)別不同的設(shè)備.仿真實(shí)驗(yàn)表明,該識(shí)別方法簡(jiǎn)潔高效,大大降低了計(jì)算量,并且能夠有效地識(shí)別不同設(shè)備.
三維數(shù)據(jù);識(shí)別;降維;邊界點(diǎn);曲率;仿真
隨著地理信息系統(tǒng)向三維領(lǐng)域的逐漸發(fā)展,三維數(shù)字化電網(wǎng)的研究快速升溫,其中對(duì)三維對(duì)象的快速建模漸漸成為研究的熱點(diǎn).想要對(duì)變電站進(jìn)行三維模型重構(gòu),就必須對(duì)變電站里的設(shè)備進(jìn)行識(shí)別,以便區(qū)分設(shè)備種類.傳統(tǒng)三維模型的重建,主要靠人眼對(duì)采集的三維點(diǎn)云數(shù)據(jù)進(jìn)行識(shí)別辨認(rèn),然后在3dmax模型庫找到相匹配的模型,再用于建模,這消耗大量的人力,效率很低,影響整個(gè)建模的進(jìn)程.目前還沒有一種很好的可以自動(dòng)識(shí)別點(diǎn)云數(shù)據(jù)的方法.
針對(duì)三維物體的識(shí)別,文獻(xiàn)[1]引入自旋圖像(spin-image)的特征,對(duì)物體的三維特征進(jìn)行描述,進(jìn)而達(dá)到識(shí)別和定位的目的,但該方法計(jì)算量太大.RUSU等[2]提出的viewpoint feature histogram(VFH)算法,通過目標(biāo)區(qū)域的三維點(diǎn)云數(shù)據(jù)計(jì)算它的VFH特征并進(jìn)行匹配,但是這種方法對(duì)數(shù)據(jù)的空間分辨率有很高的要求,而且不能滿足實(shí)時(shí)性的要求.文獻(xiàn)[3]定義了一個(gè)最大一致形狀片,并且將它組織成一個(gè)無向圖,然后使用分層的圖同構(gòu)方法來識(shí)別三維物體,但是該方法在處理物體的遮擋問題時(shí)比較困難.郭裕蘭等[4]提出采用“點(diǎn)云”正交表面投影特征來進(jìn)行模型的快速預(yù)選,然后利用ICP算法把目標(biāo)和模板的“點(diǎn)云”進(jìn)行精確匹配.三維點(diǎn)云數(shù)據(jù)可以比較準(zhǔn)確地表示物體的外形信息,研究人員將利用點(diǎn)云數(shù)據(jù)對(duì)設(shè)備進(jìn)行識(shí)別,但是設(shè)備的三維數(shù)據(jù)量很大,直接用于識(shí)別計(jì)算量很大,所以筆者提出一種基于設(shè)備投影平面點(diǎn)集邊界點(diǎn)曲率的識(shí)別方法,從而實(shí)現(xiàn)對(duì)變電站設(shè)備的快速保真識(shí)別[5-6].
投影平面點(diǎn)集邊界點(diǎn)的提取是變電站設(shè)備識(shí)別非常關(guān)鍵的一步.筆者采用基于Alpha Shapes原理[7]的滾圓法對(duì)變電站設(shè)備降維數(shù)據(jù)的邊界點(diǎn)進(jìn)行提取.
1.1 滾圓法基本原理
對(duì)于任意一個(gè)點(diǎn)集,我們可以用釘在平面上的釘子來表示.假如用一個(gè)半徑為α的圓環(huán)從邊界靠近這個(gè)釘群,然后讓這個(gè)圓環(huán)圍繞釘群滾動(dòng)一圈,當(dāng)α足夠大時(shí),每次滾動(dòng),這個(gè)圓環(huán)都會(huì)被兩個(gè)釘子卡住,這樣滾動(dòng)一圈所接觸到的釘子就是這個(gè)釘群的邊界,也就是這個(gè)點(diǎn)集的外邊界點(diǎn).利用滾圓法提取邊界點(diǎn)的示意圖如圖1所示.
模型判斷條件:在點(diǎn)集S內(nèi),任意選取兩點(diǎn)P1、P2,過這兩點(diǎn)繪制半徑為α的圓,若這個(gè)圓內(nèi)不包含別的點(diǎn),點(diǎn)P1、P2就被認(rèn)為是邊界點(diǎn).
1.2 滾圓法提取設(shè)備二維點(diǎn)集邊界點(diǎn)步驟
(1) 點(diǎn)云數(shù)據(jù)降維
將設(shè)備的點(diǎn)云數(shù)據(jù)分別向xoy、yoz、xoz平面投影,得到設(shè)備在3個(gè)平面的二維數(shù)據(jù)點(diǎn)集.
圖1 滾圓法提取邊界點(diǎn)示意圖
(2) 提取投影平面點(diǎn)集的邊界點(diǎn)
①首先選取點(diǎn)集S中y坐標(biāo)最小(假如y值相同則取x值最大)的點(diǎn)為起始邊界點(diǎn)P1.
②選定半徑α,搜索距離P1點(diǎn)小于2×α的點(diǎn)構(gòu)成的子集S2[8],在S2中任取一點(diǎn)P2,求出經(jīng)過P1、P2且半徑為α的圓的圓心O.
已知兩點(diǎn)坐標(biāo)和半徑α,求該圓圓心的步驟如下:
假如兩點(diǎn)坐標(biāo)分別為(x1,y1)、(x2,y2),所給半徑為α,圓心坐標(biāo)為(x,y).列出如下方程組
(1)
求解方程組(1)就可以得到圓心的坐標(biāo)(x,y).但是直接對(duì)該方程組求解比較麻煩,我們可以用測(cè)繪學(xué)中的距離交匯法來求圓心坐標(biāo)[9].
(2)
式中:
(3)
S2=(x1-x2)2+(y1-y2)2.
(4)
當(dāng)兩點(diǎn)的距離小于2α?xí)r,能求得兩個(gè)過這兩點(diǎn)且半徑為α的圓[10],H的取值有正負(fù)兩種情況,所求得的圓心分別為O和O′,如圖2所示.
③在點(diǎn)集S2中,分別求出(除去P1、P2外)所有點(diǎn)距離圓心O的長(zhǎng)度L.
假如所有L都大于半徑α,則認(rèn)為點(diǎn)P1、P2是邊界點(diǎn);假如有L小于半徑α,則停止此步運(yùn)行,轉(zhuǎn)去執(zhí)行第④步.由步驟②可知經(jīng)過距離小于2α的兩點(diǎn)且半徑為α的圓有兩個(gè),所以我們要考慮兩種情況,只要存在一個(gè)圓,且圓內(nèi)沒有別的點(diǎn)時(shí),我們認(rèn)為P1、P2是所求的邊界點(diǎn).
④對(duì)S2中的下一個(gè)點(diǎn)進(jìn)行②~③步判斷,直到把S2中的所有點(diǎn)都進(jìn)行一次邊界點(diǎn)判斷.
圖2 距離交匯法求圓心示意圖
⑤將②~③步得到的邊界點(diǎn)P2重新當(dāng)作起始邊界點(diǎn),重復(fù)②~④步判斷.每次搜索邊界點(diǎn)時(shí)都會(huì)得到兩個(gè)不同的邊界點(diǎn),如果搜索到的新邊界點(diǎn)與已經(jīng)得到的邊界點(diǎn)相同,則不保存,只保存不同的邊界點(diǎn).直到重新搜索到第一個(gè)邊界點(diǎn),則搜索結(jié)束.
2.1 相關(guān)研究
曲率表示曲線在一點(diǎn)的彎曲程度,從曲線的曲率圖上,可以知曉曲線的凹凸部分,并由此得到曲線的大致形狀.不過平面離散曲線一般都是不連續(xù)的,而且不可導(dǎo),很難求得它的曲率.利用尺度空間理論[11]和圓弧擬合算法[12]可以求得離散曲線的曲率,但是這兩種方法計(jì)算量較大.彭鐵根[13]利用一條固定不動(dòng)的弦,然后求得曲線段上每一點(diǎn)到弦的距離,最后求出一點(diǎn)的距離累積.該算法計(jì)算量較小,且具有較好的魯棒性能.
2.2 點(diǎn)到弦的距離累積
在此,距離符號(hào)可以利用一個(gè)判別矩陣的行列式值來進(jìn)行判斷,設(shè)如下判別矩陣
Mj,L(i)=(xi+L-xi-Lyi+L-yi-Lxj-xi-Lyj-yi-L).
(5)
圖3 點(diǎn)到弦的距離
則有
(6)
(7)
設(shè)Pi點(diǎn)的距離累積和為SL(i),則有
(8)
對(duì)于具有封閉特性的離散曲線,按照式(8)沿順時(shí)針方向環(huán)繞曲線一周,就可以獲得所有點(diǎn)的點(diǎn)到弦的距離累積值SL(i).我們可以用一點(diǎn)的距離累積來近似代表曲線上該點(diǎn)的曲率[14].
2.3 曲率分布直方圖相似度比較
求出邊界點(diǎn)曲率以后,再求曲率分布直方圖.用直方圖匹配方法來進(jìn)行相似度比較,采用歐氏函數(shù)ME(Q,D)對(duì)直方圖間的距離進(jìn)行衡量,
(9)
(10)
式中:k代表曲率相應(yīng)分段取值;L是曲率分段的個(gè)數(shù);nk是圖像中相應(yīng)曲率段內(nèi)點(diǎn)的個(gè)數(shù);N是圖像邊界點(diǎn)總數(shù).
試驗(yàn)數(shù)據(jù)為2014年在鄭州-嵩山500 kV變電站采集,選用10種設(shè)備作為模板,編號(hào)ID為0~9.首先計(jì)算10種設(shè)備在3個(gè)投影平面的邊界點(diǎn)曲率分布,并存入模型數(shù)據(jù)庫.被測(cè)樣本選取20組,每種設(shè)備選取不同位置的兩組數(shù)據(jù).求邊界點(diǎn)曲率時(shí),參數(shù)L=5,繪制直方圖時(shí),分別求出10種設(shè)備在3個(gè)平面邊界點(diǎn)曲率ρ的最小值和最大值,離散區(qū)間數(shù)num=(ρmax-ρmin)/0.06.10種模板設(shè)備點(diǎn)云數(shù)據(jù)的三維視圖,如圖4所示.
圖4 模型數(shù)據(jù)庫設(shè)備的三維視圖
選取00號(hào)樣本進(jìn)行試驗(yàn),將設(shè)備向3個(gè)平面投影,利用滾圓法提取投影平面點(diǎn)集的邊界點(diǎn),結(jié)果如圖5所示.其中圖5(a)、圖5(b)、圖5(c)分別為樣本在xoy、yoz、xoz平面投影點(diǎn)集的邊界點(diǎn).由圖5可知,不管設(shè)備的投影圖像是否規(guī)則,滾圓法都可以比較精確的提取點(diǎn)集的外邊界點(diǎn).
圖5 邊界點(diǎn)提取
根據(jù)公式(5)~(8),依次求得樣本設(shè)備在3個(gè)投影平面二維點(diǎn)集邊界點(diǎn)的曲率,曲率值如圖6所示,并用曲率的頻率分布直方圖來表示,如圖7所示.利用相同的方法求出其他樣本設(shè)備的邊界點(diǎn)曲率,并求出曲率分布.
圖6 樣本設(shè)備在3個(gè)投影平面的邊界點(diǎn)曲率
利用公式(9)和(10),將20組樣本數(shù)據(jù)在3個(gè)投影平面邊界點(diǎn)的曲率分布與模型數(shù)據(jù)庫中比較,并將3個(gè)平面的比較結(jié)果求平均,得到表1,其中橫向ID為模板,豎向?yàn)闇y(cè)試樣本.
圖7 樣本設(shè)備在3個(gè)投影平面邊界點(diǎn)曲率分布直方圖
表1 20組待測(cè)樣本與模型庫在3個(gè)平面投影點(diǎn)集邊界點(diǎn)曲率分布直方圖相似性比較
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是同種設(shè)備,其他樣本命名類似.由表1可以看出,20種待測(cè)樣本中,除11、30、80號(hào)樣本外,其他均能得到有效的匹配,識(shí)別率為85%,其中11號(hào)樣本識(shí)別成了0號(hào)模型,30號(hào)樣本識(shí)別成了8號(hào)模型,80號(hào)樣本識(shí)別成了4號(hào)模型,這是由于采集的點(diǎn)云數(shù)據(jù)不完整造成的,數(shù)據(jù)足夠完整時(shí),識(shí)別率將更高.
為了驗(yàn)證本算法的效率,與文獻(xiàn)[14]相比較,平臺(tái)為Intel(R) Core(TM) Duo CPU 2.0GHz處理器,筆者通過提取二維平面點(diǎn)云數(shù)據(jù)邊界點(diǎn),計(jì)算邊界點(diǎn)曲率并匹配,識(shí)別單個(gè)物體總共需要10 s左右.而文獻(xiàn)[14]通過找到最近點(diǎn)時(shí)間,找到對(duì)應(yīng)匹配曲面對(duì)并驗(yàn)證,總共需要50 s左右.因此可以看出筆者的算法具有很高的效率.
筆者通過將設(shè)備在三個(gè)平面進(jìn)行投影,減少數(shù)據(jù)處理量,然后求取三個(gè)投影平面的點(diǎn)集的邊界點(diǎn)曲率并用于識(shí)別.其中邊界點(diǎn)提取所采用的滾圓法以及求曲率時(shí)所采用的點(diǎn)到弦的距離累積近似,都大大減小了計(jì)算量.該識(shí)別方法簡(jiǎn)單高效,可以快速地對(duì)采集的三維點(diǎn)云數(shù)據(jù)進(jìn)行識(shí)別,加快了變電站三維模型的重建.
[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數(shù)據(jù)的建筑輪廓線提取及規(guī)則化算法研究[J]. 遙感學(xué)報(bào), 2008, 12(5):692-698.
[9] 張宏,溫永寧,劉愛利,等. 地里信息系統(tǒng)算法基礎(chǔ)[M].北京:科學(xué)出版社, 2006.
[10]王宗躍,馬洪超,徐宏根,等. 海量點(diǎn)云的邊緣快速提取算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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]彭鐵根,吳惕華. 基于負(fù)曲率極值點(diǎn)的零件識(shí)別與檢測(cè)技術(shù)研究[J].系統(tǒng)仿真學(xué)報(bào), 2006,18(11):3058-3062.
[14]魏永超,劉長(zhǎng)華,杜冬. 基于曲面分割的三維點(diǎn)云物體識(shí)別 [J].光子學(xué)報(bào), 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
國家自然科學(xué)基金資助項(xiàng)目(61473266);河南省產(chǎn)學(xué)研合作項(xiàng)目(152107000058)
馮冬青(1958— ),男,廣東佛山人,鄭州大學(xué)教授,主要從事智能控制理論與應(yīng)用、圖像處理、模式識(shí)別等研究,E-mail:dqfeng@zzu.edu.cn.
1671-6833(2017)02-0061-05
TP391
A
10.13705/j.issn.1671-6833.2017.02.014