一个输电线系统净空排查算法的优化过程

游安清，韩晓言，潘旭东，贺喜

1.中国工程物理研究院应用电子学研究所，四川绵阳 621900

2.四川省电力公司绵阳电业局，四川绵阳 621000

一个输电线系统净空排查算法的优化过程

游安清1，韩晓言2，潘旭东1，贺喜1

1.中国工程物理研究院应用电子学研究所，四川绵阳 621900

2.四川省电力公司绵阳电业局，四川绵阳 621000

针对激光雷达扫描得到的输电线路三维点云数据，在对象分类的基础上，设计一个全自动的净空排查算法，以确定输电线路与周围地物是否有过于接近的情况。由于净空排查的基本算法相当耗时，故采用了包围盒、循环调整、降维、多分辨率、并行运算等措施，对基本算法作了7级优化，使算法速度提高超过20 000倍，最终达到亚秒级的耗时。

激光雷达；三维点云；输电线；距离排查

1 引言

净空排查是三维激光雷达电力巡线作业[1-3]的一项重要后处理任务，其目的在于分析并发现输电线路与其周围地物是否有过于接近的情况，这对确保输电安全有重要意义。针对激光雷达扫描得到的点云数据，在对象分类[4-6]的基础上，设计一个自动的净空排查算法很有必要。由于输电线路空间跨度大，使扫描所得的点云数据量相当巨大，普通的净空排查算法很难在可接受的时间内完成分析任务，所以，必须进行优化。本文从一个基本算法入手，先后采用包围盒、循环调整、降维、多分辨率、并行运算等多项优化措施，将算法速度提高20 000多倍，最终达到亚秒级耗时，大大促进算法的实时性和实用性。

2 基本算法

设有由NP个点组成的三维激光雷达点云{Pi(x，y，z，CP)(i=1，2，…，NP)}，每个点的数据是一个由三维坐标(x，y，z)和点的类型CP组成的4元素行向量。设点集中有Nw个电线点{Wi|i=1，2，…，Nw}和Ng个地物点{Gj|j=1，2，…，Ng}。设允许的输电线与地物间距离为a（称为邻近阈值），净空排查算法的目的就是找出满足下式的所有电线点和地物点对：

于是很容易有基本算法：

取从某电业局所辖的一段输电线路上的实验点云，如图1，其总点数NP=3 000 000、电线点数Nw=56 571（图中蓝色点）、地物点数Ng=2 943 429（图中绿色点）、邻近阈值a=1 m。用Matlab7.0编程实现基本算法，在一台主频2.33 GHz、内存3.5 GB的计算机上运行，完成一次净空排查共耗时3 h。可见，对海量点云数据进行净空排查的基本算法是很慢的。

图1 净空排查算法的实验点云

3 优化过程

3.1 优化一

基本算法耗时长的重要原因是：对电线点和地物点间的求距运算是均匀的，即对任一电线——地物点对，都要进行求距运算，而这些运算中绝大多数都是不必要的，因为距离小于邻近阈值的点对毕竟只是少数。于是，一项最简单的改进就是采用包围盒法[7-8]：

（1）将点云所占的三维空间按阈值a均匀划分成若干包围盒，每盒按其在空间的行、列、深进行索引，盒子本身做成结构体，内含盒内点数n、盒内点编号序列P、盒类型CB三个字段。即

（2）计算每个点应落入的包围盒的索引，将该点归入该盒。计算各盒内点数，并根据盒内点类型确定盒类型：只包含电线点的盒子，其类型字段CB置1；只包含地物点的，其类型置2；两种点都包含的，其类型置3。

（3）对1、3类盒，根据盒索引找出其27个邻盒（包括该盒本身），对该盒内的电线点与其2、3类邻盒中的地物点进行求距运算，输出距离小于阈值a的点对。

这个算法的前两步为“包围盒生成”过程，后一步为“距离排查”过程。

包围盒算法基于这样一种认识：各包围盒内的点只可能与其邻包围盒内的点距离小于盒边长。所以，避免了大量相隔很远的点对之间的求距运算。对同样的实验点云，按此算法编程、计算，在同样的机型上运行，结果，系统提示“Out of M emory”，计算失败。

3.2 优化二

优化一算法的思路是好的，但计算过程失败，其原因在于它会产生大量空盒。一是因为输电线是悬空于地面的线状体，其所占的实体空间很小；二是因为地面景物一般是起伏不平的，整体空间中大部分是与它们互补的“空”空间，为这些“空”空间生成包围盒，很多都是空盒。正是大量的空盒（对于所给的实验点云，空盒占总盒数的99.4%）导致了内存溢出。

另外，优化一算法的步骤（1）是一个3重循环（因为要在x、y、z三个方向上遍历盒索引），步骤（2）是1重循环（遍历各点），步骤（3）是8重循环（其中3重用于锁定1类和3类包围盒，1重用于遍历此盒内的电线点，再3重用于遍历该盒的27个相邻盒，另1重用于遍历各邻盒中的地物点）。由于循环跳转最不利于并行计算，多重循环使算法耗时成指数级增长。所以，该算法即使内存不溢出，其速度也会很慢。

为此，对该算法作如下改进：

（1）去掉优化一的步骤（1），并修改盒结构体为6字段，包括盒的三维索引、盒内点数、盒内点编号序列和盒类型，即

（2）修改优化一的步骤（2）为：按阈值a将点云空间划分成若干子空间，遍历各子空间，以其6个边界面为界使用find函数找出属于该子空间的所有点。只有当find到的点数不为0时，才生成一个新盒，且将find到的点归入该盒中，子空间的三维索引（i、j、k值）赋给盒的前3个字段。即

此算法有3个优点：（1）将盒编号由3维降成了1维；（2）不产生空盒；（3）使算法一步骤（3）由8重循环降成了4重。此算法也有一个缺点：盒序列中任意两相邻盒Bq、Bq+1在空间上不一定是相邻的，也就意味着，对于Bq，其26个邻盒并不像算法一那样明显（在那里，B(i，j，k)的邻盒必是所以，需另行设计一个1维遍历算法，专门寻找Bq的邻盒。

用此算法对相同的实验点云进行计算，不再发生内存溢出，但耗时长于3 h。

3.3 优化三

深入分析发现，优化二算法中find语句是最耗时环节，因为每次find都在百万计的点中寻找包围在某个子空间内的点，这是一件很耗时的事，为此，再作两项改进：

（1）增加3个变量，分别记录子空间在三个方向上的下界，于是可将算法二中find语句内的乘法改加法：

（2）将find语句对3组边界的同时判断分解为3个递进判断，即

并且将第一个判断移到第二重循环之外，第二个判断移到第三重循之外，这样，越往里的循环需要判断的点数越少，这会大大提高find的速度。

经此循环调整后，算法耗时减少至33 m in。

3.4 优化四

优化三算法的find函数还存在不足之处：每重循环中的各次find语句要对上重循环过滤出的所有剩余点进行判断。这意味着，已经划入某个Bq盒的点还要继续被判断是否属于另一个子空间（其结果只能是NO）。对此，再作一项改进：对前一重循环过滤出的点进行位置排序，下一重循环中只对位置上界进行判断：小于某子空间上界的属于一个新包围盒，大于上界的留给后面的子空间进行判断。这样就避免了点的重复判断，但代价是增加点排序操作。此改进后算法耗时7 m in。

3.5 优化五

优化四算法虽然对算法一已经作了很大改进，速度提高了近26倍，但其绝对耗时（7 m in）仍不为小量，究其原因还是循环层数太多。要想再有大的提高，必须继续降维。为此，将点云数据增加一个列“所属子空间索引indxs”：{Pi(x，y，z，CP，indxs)(i=1，2，…，NP)}。这样，“包围盒生成”过程改为：

（1）将整个点云空间分成若干边长为a的子空间，并按先行、再列、后深的遍历顺利给这些子空间编上一维索引。即

（2）计算各点应落子空间的行、列、深序号(i，j，k)，计算它们对应的一维子空间索引indxs，将该索引值赋给点结构体第5列。并对所有点按此列排序。

（3）修改包围盒结构体为等长度的4元素行向量：Bq=(Ps，Pe，indxs，CB)。其中(Ps，Pe)表示该盒包含排序后编号为Ps～Pe的所有点。

（4）将排序后的点生成、归入包围盒。“生成、归入”的方法是：将第5列值相同的连续点归入同一个盒子，第5列值变化时生成新盒子（即q值加1）。连续点中的第一个点为Ps、最后一个点为Pe。

此算法将“包围盒生成”过程由三重循环降成了一重循环，且不对任何点、任何盒子进行重复操作，而且无空盒。

此项改进使算法速度大幅提高，完成同样点云的计算耗时为55.1 s。

3.6 优化六

虽然优化五算法有了很大改进，但仍有继续改进的空间。细致分析发现，由于包围盒尺寸取为a=1 m，会生成很多包围盒，对这些包围盒都要进行寻找相邻包围盒，由于多数包围盒之间是不相邻的，所以还是做了很多无用功，这就成了算法五中最耗时的环节。为此，引入多分辨率原理进行改进：对点云空间按8a、4a、2a、a等几个辨率层次依次进行“包围盒生成”和“寻找邻盒”运算；在每个分辨率层次上，舍掉不与2、3类盒相邻的1类盒（即舍掉周围没有地物点的电线点），也舍掉不与1、3类盒相邻的2类盒（即舍掉周围没有电线点的地物点），这步操作可称为“点云删减”；这样，进入下一分辨率层分析的点云数量会大大减少，点云空间大大缩小，从而加快细分辨率层上的分析过程。

实验表明，对于给定的实验点云，增加更大尺寸的分辨率层次（如32a、16a等），其减少点云数量的贡献已经不及抵销该层上计算分析的耗时，所以，这些更高层次的分辨率已经不必要，从8a到a的四层分辨率是合适的。

经此多分辨率改进后，对同样点云的算法耗时降到了1.44 s。

3.7 优化七

不难看出，优化六算法在引入多分辨率原理提高处理速度的同时，也引入了一项新的操作“点云删减”，这项操作也是要耗时的。对于算法六，这是最耗时环节。因为“点云删减”算法是两次二重循环：第一次的第一重用于遍历所有1类盒，第二重用于遍历它的26个邻盒，并判断邻盒中是否有2、3类盒，如果有，则保留这个1类盒，如果没有，则删除之；第二次的两重循环则用于删减不与1、3类盒相邻的2类盒。这些双重循环不利于算法的并行运行。

对此，作这样的改进：删减1类盒时，提取每个1类盒的indxs，将它用repmat函数扩展成26行的列向量，其元素的值取为该盒的26个邻盒的indxs；对这个列向量用ismember函数判断是否属于2、3类盒的索引集，返回值是一个由26个0或1组成的列向量（0表示对应元素不在2、3类盒索引集中，1表示在）；对此向量用sum求和，若和大于0，则说明至少有一邻盒属于2、3类盒；若和等于0，则说明26个邻盒都是1类盒，这时，中心的1类盒可以删减掉。对经过1类盒删减后的包围盒集再按同样方法进行2类盒删减。

表1 净空排查算法的优化过程

这项改进其实是用Matlab的矩阵运算代替了内循环，从而使二重循环降为一重，整个算法的耗时也降至0.47 s，达到亚秒级的耗时，这样的耗时量使数据处理员几乎感觉不到等待，所以是可以接受的。

4 数值实验

按上述算法对前面所述的实验点云进行计算，共找到55个与电力线接近距离小于邻近阈值的地物点，图2给出了其中一段，图中红色圈内粗红点即为排查出来的地物点。经派人到实验点云所在处实地考察，发现该处确实存在树木与电线很接近的情况，只是人工巡线方法比较费时费力、而且精度有限，这反而是本文净空排查算法的优势所在——快速、精确，这对提高电力巡线自动化很有帮助。

图2 净空排查算法输出的结果

5 总结

本文从净空排查的一个基本算法入手，经过7级优化后，算法耗时由3 h降至了0.47 s，速度提高20 000多倍。各级优化的主要改进项和速度提高程度归纳如表1所示。

由表1可以看出，主要的优化策略包括：引入包围盒、降维、循环调整、多分辨率、矩阵并行运算等。最后的算法描述如下：

（1）将点云用NP×5的矩阵表示，每行一个点，5列分别是点的三维坐标、点类型、所属子空间的一维索引，即P(x，y，z，CP，indxs)。填写各点的前4个元素值。

（2）按阈值a的倍数设定4个分辨率：8a、4a、2a、a。对每个分辨率层次，转（3）。

（3）按分辨率尺度将点云空间划分成若干子空间。

（4）将包围盒用NB×4的矩阵表示，每行一个盒，4列分别是各盒所包含的起点序号、止点序号、盒类型、盒的子空间索引，即Bq=(Ps，Pe，CB，indxs)。

（5）计算各点的第5元素值，即该点所属子空间的索引号indxs。

（6）对所有点按第5列值进行排序。

（7）将排序后的点生成、归入包围盒：将第5列值相同的连续点归入同一盒，第5列值变化时生成新盒。连续点中的第一个为Ps、最后一个为Pe。同时确定包围盒类型CB：只包含电线点的盒子为1类；只包含地物点的为2类；两种点都包含的为3类。

（8）对于各1类盒，考察其26个邻盒中是否有2、3类盒，若没有，则删掉此盒；对于各2类包围盒，考察其26个邻盒中是否有1、3类盒，若没有，也删掉此盒。

（9）将剩余包围盒中的点组成新点云，进入下一分辨率层的处理：如果4个分辨率层均已处理完，则转（10），否则转（3）。

（10）在最后的包围盒集中找出1、3类盒，以这些盒为中心盒，分别找出它们的27个邻盒（包括中心盒本身），对中心盒与其邻盒中的每对电线——地物点进行求距运算，输出距离小于邻近阈值a的点对。

这个净空排查算法是为电力巡线业务专门设计的，目的是增加电力巡线的自动化程度，减少人工现场巡线的作业难度和劳动强度并增加准确性。所设计的算法与Terrasolid等激光点云商业处理软件相比，具有过程全自动和阈值可灵活设置的优势。不过，后者是一个综合的点云数据预处理软件，内含点云分类功能，这是它的优势，而本算法是建立在点云已经被正确分类的基础上。

[1]黄潇嵘，阮毅，李正，等.500 kV超高压架空输电线路巡线机器人的空间巡线方法研究[J].机床与液压，2011，39（11）：36-39.

[2]左来明.遥控航模实现输电线路巡线[J].东北电力技术，2010（5）：41-47.

[3]陈晓兵，马玉林，徐祖舰.无人飞机输电线路巡线技术探讨[J].南方电网技术，2008，2（6）：59-61.

[4]Qiao Jigang，Liu Xiaoping，Zhang Yihan.Land cover classification using LiDAR height texture and ANNs[J].Journal of Remote Sensing，2011，15（3）：539-545.

[5]杨耘，隋立春.面向对象的LiDAR数据多特征融合分类[J].测绘通报，2010（8）：11-14.

[6]龚亮，李正国，包全福.融合航空影像的LiDAR地物点云分类[J].测绘工程，2012，21（1）：34-38.

[7]刘涛，徐铮，沙成梅，等.基于包围盒法的散乱点云数据的曲率精简[J].科学技术与工程，2009，9（12）：3333-3336.

[8]刘健，孙殿柱，李延瑞，等.散乱点云局部点集最小包围盒快速求解算法[J].农业装备与车辆工程，2010（6）：27-29.

YOU Anqing1,HAN Xiaoyan2,PAN Xudong1,HE Xi1

1.Institute of Applied Electronics, China Academy of Engineering Physics, Mianyang, Sichuan 621900, China
2.Mianyang Power Bureau, Sichuan Power Company, Mianyang, Sichuan 621000, China

For 3D laser point cloud scanned by LiDAR on power wires, an automatic algorithm is needed for spatial distance check to inspect whether wires are too close somewhere to ground objects. The basic algorithm for distance check is very time-consuming, so 7 optimizations are applied to the algorithm, including enclosing box, loop adjustment, dimension decrease, multiple resolution, parallel calculation and so on, to speed the algorithm for over 20000 times. The final consumed time is decreased to less than one second.

Light Detection And Ranging（LiDAR）; 3D point cloud; power wires; distance check

YOU Anqing, HAN Xiaoyan, PAN Xudong, et al. Optimizations of spatial distance check algorithm in power transmission system. Computer Engineering and Applications, 2014, 50（17）：259-262.

A

TP274.2

10.3778/j.issn.1002-8331.1209-0220

国家高技术研究发展计划（863）（No.2010AA 7010419）。

游安清（1975—），男，博士，副研究员，研究方向为图像处理与计算机视觉技术；韩晓言（1965—），男，博士，高级工程师，研究方向为电力系统运行与控制、智能电网技术；潘旭东（1972—），男，副研究员，研究方向为硬件电路设计技术；贺喜（1987—），男，工程师，研究方向为光电工程技术。E-mail：anqingyou@163.com

2012-09-21

2012-11-26

1002-8331（2014）17-0259-04

CNKI网络优先出版：2012-12-18,http://www.cnki.net/kcms/detail/11.2127.TP.20121218.1522.020.htm l