窦本君，纪 勇，郑尚高，冯冬青，罗 勇

(1.郑州大学 电气工程学院，河南 郑州 450001； 2.河南腾龙信息工程有限公司，河南 郑州 450007)

基于降维数据边界点曲率的变电站设备识别

窦本君1，纪 勇2，郑尚高2，冯冬青1，罗 勇1

(1.郑州大学 电气工程学院，河南 郑州 450001； 2.河南腾龙信息工程有限公司，河南 郑州 450007)

为了对变电站三维仿真模型进行快速重建，针对变电站设备三维数据量过大，不能快速识别的问题，通过对设备的三维数据做降维处理，减少数据处理量，研究利用降维后的数据对设备进行快速精确识别的方法.通过分析降维数据点集的特征，笔者提出一种利用降维数据边界点曲率进行识别的方法，其中边界点提取采用基于Alpha Shapes原理的滚圆法，边界点的曲率通过点到弦的距离累积来计算，最后利用边界点的曲率来识别不同的设备.仿真实验表明，该识别方法简洁高效，大大降低了计算量，并且能够有效地识别不同设备.

三维数据；识别；降维；边界点；曲率；仿真

0 引言

随着地理信息系统向三维领域的逐渐发展，三维数字化电网的研究快速升温，其中对三维对象的快速建模渐渐成为研究的热点.想要对变电站进行三维模型重构，就必须对变电站里的设备进行识别，以便区分设备种类.传统三维模型的重建，主要靠人眼对采集的三维点云数据进行识别辨认，然后在3dmax模型库找到相匹配的模型，再用于建模，这消耗大量的人力，效率很低，影响整个建模的进程.目前还没有一种很好的可以自动识别点云数据的方法.

针对三维物体的识别，文献[1]引入自旋图像(spin-image)的特征，对物体的三维特征进行描述，进而达到识别和定位的目的，但该方法计算量太大.RUSU等[2]提出的viewpoint feature histogram(VFH)算法，通过目标区域的三维点云数据计算它的VFH特征并进行匹配，但是这种方法对数据的空间分辨率有很高的要求，而且不能满足实时性的要求.文献[3]定义了一个最大一致形状片，并且将它组织成一个无向图，然后使用分层的图同构方法来识别三维物体，但是该方法在处理物体的遮挡问题时比较困难.郭裕兰等[4]提出采用“点云”正交表面投影特征来进行模型的快速预选，然后利用ICP算法把目标和模板的“点云”进行精确匹配.三维点云数据可以比较准确地表示物体的外形信息，研究人员将利用点云数据对设备进行识别，但是设备的三维数据量很大，直接用于识别计算量很大，所以笔者提出一种基于设备投影平面点集边界点曲率的识别方法，从而实现对变电站设备的快速保真识别[5-6].

1 提取降维数据边界点

投影平面点集边界点的提取是变电站设备识别非常关键的一步.笔者采用基于Alpha Shapes原理[7]的滚圆法对变电站设备降维数据的边界点进行提取.

1.1 滚圆法基本原理

对于任意一个点集，我们可以用钉在平面上的钉子来表示.假如用一个半径为α的圆环从边界靠近这个钉群，然后让这个圆环围绕钉群滚动一圈，当α足够大时，每次滚动，这个圆环都会被两个钉子卡住，这样滚动一圈所接触到的钉子就是这个钉群的边界，也就是这个点集的外边界点.利用滚圆法提取边界点的示意图如图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小于半径α，则停止此步运行，转去执行第④步.由步骤②可知经过距离小于2α的两点且半径为α的圆有两个，所以我们要考虑两种情况，只要存在一个圆，且圆内没有别的点时，我们认为P1、P2是所求的边界点.

④对S2中的下一个点进行②～③步判断，直到把S2中的所有点都进行一次边界点判断.

图2 距离交汇法求圆心示意图

⑤将②～③步得到的边界点P2重新当作起始边界点，重复②～④步判断.每次搜索边界点时都会得到两个不同的边界点，如果搜索到的新边界点与已经得到的边界点相同，则不保存，只保存不同的边界点.直到重新搜索到第一个边界点，则搜索结束.

2 计算边界点曲率

2.1 相关研究

曲率表示曲线在一点的弯曲程度，从曲线的曲率图上，可以知晓曲线的凹凸部分，并由此得到曲线的大致形状.不过平面离散曲线一般都是不连续的，而且不可导，很难求得它的曲率.利用尺度空间理论[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)沿顺时针方向环绕曲线一周，就可以获得所有点的点到弦的距离累积值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个平面边界点曲率ρ的最小值和最大值，离散区间数num=(ρmax-ρmin)/0.06.10种模板设备点云数据的三维视图,如图4所示.

图4 模型数据库设备的三维视图

选取00号样本进行试验，将设备向3个平面投影，利用滚圆法提取投影平面点集的边界点，结果如图5所示.其中图5(a)、图5(b)、图5(c)分别为样本在xoy、yoz、xoz平面投影点集的边界点.由图5可知，不管设备的投影图像是否规则，滚圆法都可以比较精确的提取点集的外边界点.

图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数据的建筑轮廓线提取及规则化算法研究[J]. 遥感学报, 2008, 12(5):692-698.

[9] 张宏,温永宁,刘爱利,等. 地里信息系统算法基础[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].系统仿真学报, 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