游安清，韓曉言，潘旭東，賀喜

1.中國工程物理研究院應用電子學研究所，四川綿陽 621900

2.四川省電力公司綿陽電業(yè)局，四川綿陽 621000

一個輸電線系統(tǒng)凈空排查算法的優(yōu)化過程

游安清1，韓曉言2，潘旭東1，賀喜1

1.中國工程物理研究院應用電子學研究所，四川綿陽 621900

2.四川省電力公司綿陽電業(yè)局，四川綿陽 621000

針對激光雷達掃描得到的輸電線路三維點云數(shù)據(jù)，在對象分類的基礎上，設計一個全自動的凈空排查算法，以確定輸電線路與周圍地物是否有過于接近的情況。由于凈空排查的基本算法相當耗時，故采用了包圍盒、循環(huán)調整、降維、多分辨率、并行運算等措施，對基本算法作了7級優(yōu)化，使算法速度提高超過20 000倍，最終達到亞秒級的耗時。

激光雷達；三維點云；輸電線；距離排查

1 引言

凈空排查是三維激光雷達電力巡線作業(yè)[1-3]的一項重要后處理任務，其目的在于分析并發(fā)現(xiàn)輸電線路與其周圍地物是否有過于接近的情況，這對確保輸電安全有重要意義。針對激光雷達掃描得到的點云數(shù)據(jù)，在對象分類[4-6]的基礎上，設計一個自動的凈空排查算法很有必要。由于輸電線路空間跨度大，使掃描所得的點云數(shù)據(jù)量相當巨大，普通的凈空排查算法很難在可接受的時間內完成分析任務，所以，必須進行優(yōu)化。本文從一個基本算法入手，先后采用包圍盒、循環(huán)調整、降維、多分辨率、并行運算等多項優(yōu)化措施，將算法速度提高20 000多倍，最終達到亞秒級耗時，大大促進算法的實時性和實用性。

2 基本算法

設有由NP個點組成的三維激光雷達點云{Pi(x，y，z，CP)(i=1，2，…，NP)}，每個點的數(shù)據(jù)是一個由三維坐標(x，y，z)和點的類型CP組成的4元素行向量。設點集中有Nw個電線點{Wi|i=1，2，…，Nw}和Ng個地物點{Gj|j=1，2，…，Ng}。設允許的輸電線與地物間距離為a（稱為鄰近閾值），凈空排查算法的目的就是找出滿足下式的所有電線點和地物點對：

于是很容易有基本算法：

取從某電業(yè)局所轄的一段輸電線路上的實驗點云，如圖1，其總點數(shù)NP=3 000 000、電線點數(shù)Nw=56 571（圖中藍色點）、地物點數(shù)Ng=2 943 429（圖中綠色點）、鄰近閾值a=1 m。用Matlab7.0編程實現(xiàn)基本算法，在一臺主頻2.33 GHz、內存3.5 GB的計算機上運行，完成一次凈空排查共耗時3 h?？梢?，對海量點云數(shù)據(jù)進行凈空排查的基本算法是很慢的。

圖1 凈空排查算法的實驗點云

3 優(yōu)化過程

3.1 優(yōu)化一

基本算法耗時長的重要原因是：對電線點和地物點間的求距運算是均勻的，即對任一電線——地物點對，都要進行求距運算，而這些運算中絕大多數(shù)都是不必要的，因為距離小于鄰近閾值的點對畢竟只是少數(shù)。于是，一項最簡單的改進就是采用包圍盒法[7-8]：

（1）將點云所占的三維空間按閾值a均勻劃分成若干包圍盒，每盒按其在空間的行、列、深進行索引，盒子本身做成結構體，內含盒內點數(shù)n、盒內點編號序列P、盒類型CB三個字段。即

（2）計算每個點應落入的包圍盒的索引，將該點歸入該盒。計算各盒內點數(shù)，并根據(jù)盒內點類型確定盒類型：只包含電線點的盒子，其類型字段CB置1；只包含地物點的，其類型置2；兩種點都包含的，其類型置3。

（3）對1、3類盒，根據(jù)盒索引找出其27個鄰盒（包括該盒本身），對該盒內的電線點與其2、3類鄰盒中的地物點進行求距運算，輸出距離小于閾值a的點對。

這個算法的前兩步為“包圍盒生成”過程，后一步為“距離排查”過程。

包圍盒算法基于這樣一種認識：各包圍盒內的點只可能與其鄰包圍盒內的點距離小于盒邊長。所以，避免了大量相隔很遠的點對之間的求距運算。對同樣的實驗點云，按此算法編程、計算，在同樣的機型上運行，結果，系統(tǒng)提示“Out of M emory”，計算失敗。

3.2 優(yōu)化二

優(yōu)化一算法的思路是好的，但計算過程失敗，其原因在于它會產(chǎn)生大量空盒。一是因為輸電線是懸空于地面的線狀體，其所占的實體空間很??；二是因為地面景物一般是起伏不平的，整體空間中大部分是與它們互補的“空”空間，為這些“空”空間生成包圍盒，很多都是空盒。正是大量的空盒（對于所給的實驗點云，空盒占總盒數(shù)的99.4%）導致了內存溢出。

另外，優(yōu)化一算法的步驟（1）是一個3重循環(huán)（因為要在x、y、z三個方向上遍歷盒索引），步驟（2）是1重循環(huán)（遍歷各點），步驟（3）是8重循環(huán)（其中3重用于鎖定1類和3類包圍盒，1重用于遍歷此盒內的電線點，再3重用于遍歷該盒的27個相鄰盒，另1重用于遍歷各鄰盒中的地物點）。由于循環(huán)跳轉最不利于并行計算，多重循環(huán)使算法耗時成指數(shù)級增長。所以，該算法即使內存不溢出，其速度也會很慢。

為此，對該算法作如下改進：

（1）去掉優(yōu)化一的步驟（1），并修改盒結構體為6字段，包括盒的三維索引、盒內點數(shù)、盒內點編號序列和盒類型，即

（2）修改優(yōu)化一的步驟（2）為：按閾值a將點云空間劃分成若干子空間，遍歷各子空間，以其6個邊界面為界使用find函數(shù)找出屬于該子空間的所有點。只有當find到的點數(shù)不為0時，才生成一個新盒，且將find到的點歸入該盒中，子空間的三維索引（i、j、k值）賦給盒的前3個字段。即

此算法有3個優(yōu)點：（1）將盒編號由3維降成了1維；（2）不產(chǎn)生空盒；（3）使算法一步驟（3）由8重循環(huán)降成了4重。此算法也有一個缺點：盒序列中任意兩相鄰盒Bq、Bq+1在空間上不一定是相鄰的，也就意味著，對于Bq，其26個鄰盒并不像算法一那樣明顯（在那里，B(i，j，k)的鄰盒必是所以，需另行設計一個1維遍歷算法，專門尋找Bq的鄰盒。

用此算法對相同的實驗點云進行計算，不再發(fā)生內存溢出，但耗時長于3 h。

3.3 優(yōu)化三

深入分析發(fā)現(xiàn)，優(yōu)化二算法中find語句是最耗時環(huán)節(jié)，因為每次find都在百萬計的點中尋找包圍在某個子空間內的點，這是一件很耗時的事，為此，再作兩項改進：

（1）增加3個變量，分別記錄子空間在三個方向上的下界，于是可將算法二中find語句內的乘法改加法：

（2）將find語句對3組邊界的同時判斷分解為3個遞進判斷，即

并且將第一個判斷移到第二重循環(huán)之外，第二個判斷移到第三重循之外，這樣，越往里的循環(huán)需要判斷的點數(shù)越少，這會大大提高find的速度。

經(jīng)此循環(huán)調整后，算法耗時減少至33 m in。

3.4 優(yōu)化四

優(yōu)化三算法的find函數(shù)還存在不足之處：每重循環(huán)中的各次find語句要對上重循環(huán)過濾出的所有剩余點進行判斷。這意味著，已經(jīng)劃入某個Bq盒的點還要繼續(xù)被判斷是否屬于另一個子空間（其結果只能是NO）。對此，再作一項改進：對前一重循環(huán)過濾出的點進行位置排序，下一重循環(huán)中只對位置上界進行判斷：小于某子空間上界的屬于一個新包圍盒，大于上界的留給后面的子空間進行判斷。這樣就避免了點的重復判斷，但代價是增加點排序操作。此改進后算法耗時7 m in。

3.5 優(yōu)化五

優(yōu)化四算法雖然對算法一已經(jīng)作了很大改進，速度提高了近26倍，但其絕對耗時（7 m in）仍不為小量，究其原因還是循環(huán)層數(shù)太多。要想再有大的提高，必須繼續(xù)降維。為此，將點云數(shù)據(jù)增加一個列“所屬子空間索引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列值相同的連續(xù)點歸入同一個盒子，第5列值變化時生成新盒子（即q值加1）。連續(xù)點中的第一個點為Ps、最后一個點為Pe。

此算法將“包圍盒生成”過程由三重循環(huán)降成了一重循環(huán)，且不對任何點、任何盒子進行重復操作，而且無空盒。

此項改進使算法速度大幅提高，完成同樣點云的計算耗時為55.1 s。

3.6 優(yōu)化六

雖然優(yōu)化五算法有了很大改進，但仍有繼續(xù)改進的空間。細致分析發(fā)現(xiàn)，由于包圍盒尺寸取為a=1 m，會生成很多包圍盒，對這些包圍盒都要進行尋找相鄰包圍盒，由于多數(shù)包圍盒之間是不相鄰的，所以還是做了很多無用功，這就成了算法五中最耗時的環(huán)節(jié)。為此，引入多分辨率原理進行改進：對點云空間按8a、4a、2a、a等幾個辨率層次依次進行“包圍盒生成”和“尋找鄰盒”運算；在每個分辨率層次上，舍掉不與2、3類盒相鄰的1類盒（即舍掉周圍沒有地物點的電線點），也舍掉不與1、3類盒相鄰的2類盒（即舍掉周圍沒有電線點的地物點），這步操作可稱為“點云刪減”；這樣，進入下一分辨率層分析的點云數(shù)量會大大減少，點云空間大大縮小，從而加快細分辨率層上的分析過程。

實驗表明，對于給定的實驗點云，增加更大尺寸的分辨率層次（如32a、16a等），其減少點云數(shù)量的貢獻已經(jīng)不及抵銷該層上計算分析的耗時，所以，這些更高層次的分辨率已經(jīng)不必要，從8a到a的四層分辨率是合適的。

經(jīng)此多分辨率改進后，對同樣點云的算法耗時降到了1.44 s。

3.7 優(yōu)化七

不難看出，優(yōu)化六算法在引入多分辨率原理提高處理速度的同時，也引入了一項新的操作“點云刪減”，這項操作也是要耗時的。對于算法六，這是最耗時環(huán)節(jié)。因為“點云刪減”算法是兩次二重循環(huán)：第一次的第一重用于遍歷所有1類盒，第二重用于遍歷它的26個鄰盒，并判斷鄰盒中是否有2、3類盒，如果有，則保留這個1類盒，如果沒有，則刪除之；第二次的兩重循環(huán)則用于刪減不與1、3類盒相鄰的2類盒。這些雙重循環(huán)不利于算法的并行運行。

對此，作這樣的改進：刪減1類盒時，提取每個1類盒的indxs，將它用repmat函數(shù)擴展成26行的列向量，其元素的值取為該盒的26個鄰盒的indxs；對這個列向量用ismember函數(shù)判斷是否屬于2、3類盒的索引集，返回值是一個由26個0或1組成的列向量（0表示對應元素不在2、3類盒索引集中，1表示在）；對此向量用sum求和，若和大于0，則說明至少有一鄰盒屬于2、3類盒；若和等于0，則說明26個鄰盒都是1類盒，這時，中心的1類盒可以刪減掉。對經(jīng)過1類盒刪減后的包圍盒集再按同樣方法進行2類盒刪減。

表1 凈空排查算法的優(yōu)化過程

這項改進其實是用Matlab的矩陣運算代替了內循環(huán)，從而使二重循環(huán)降為一重，整個算法的耗時也降至0.47 s，達到亞秒級的耗時，這樣的耗時量使數(shù)據(jù)處理員幾乎感覺不到等待，所以是可以接受的。

4 數(shù)值實驗

按上述算法對前面所述的實驗點云進行計算，共找到55個與電力線接近距離小于鄰近閾值的地物點，圖2給出了其中一段，圖中紅色圈內粗紅點即為排查出來的地物點。經(jīng)派人到實驗點云所在處實地考察，發(fā)現(xiàn)該處確實存在樹木與電線很接近的情況，只是人工巡線方法比較費時費力、而且精度有限，這反而是本文凈空排查算法的優(yōu)勢所在——快速、精確，這對提高電力巡線自動化很有幫助。

圖2 凈空排查算法輸出的結果

5 總結

本文從凈空排查的一個基本算法入手，經(jīng)過7級優(yōu)化后，算法耗時由3 h降至了0.47 s，速度提高20 000多倍。各級優(yōu)化的主要改進項和速度提高程度歸納如表1所示。

由表1可以看出，主要的優(yōu)化策略包括：引入包圍盒、降維、循環(huán)調整、多分辨率、矩陣并行運算等。最后的算法描述如下：

（1）將點云用NP×5的矩陣表示，每行一個點，5列分別是點的三維坐標、點類型、所屬子空間的一維索引，即P(x，y，z，CP，indxs)。填寫各點的前4個元素值。

（2）按閾值a的倍數(shù)設定4個分辨率：8a、4a、2a、a。對每個分辨率層次，轉（3）。

（3）按分辨率尺度將點云空間劃分成若干子空間。

（4）將包圍盒用NB×4的矩陣表示，每行一個盒，4列分別是各盒所包含的起點序號、止點序號、盒類型、盒的子空間索引，即Bq=(Ps，Pe，CB，indxs)。

（5）計算各點的第5元素值，即該點所屬子空間的索引號indxs。

（6）對所有點按第5列值進行排序。

（7）將排序后的點生成、歸入包圍盒：將第5列值相同的連續(xù)點歸入同一盒，第5列值變化時生成新盒。連續(xù)點中的第一個為Ps、最后一個為Pe。同時確定包圍盒類型CB：只包含電線點的盒子為1類；只包含地物點的為2類；兩種點都包含的為3類。

（8）對于各1類盒，考察其26個鄰盒中是否有2、3類盒，若沒有，則刪掉此盒；對于各2類包圍盒，考察其26個鄰盒中是否有1、3類盒，若沒有，也刪掉此盒。

（9）將剩余包圍盒中的點組成新點云，進入下一分辨率層的處理：如果4個分辨率層均已處理完，則轉（10），否則轉（3）。

（10）在最后的包圍盒集中找出1、3類盒，以這些盒為中心盒，分別找出它們的27個鄰盒（包括中心盒本身），對中心盒與其鄰盒中的每對電線——地物點進行求距運算，輸出距離小于鄰近閾值a的點對。

這個凈空排查算法是為電力巡線業(yè)務專門設計的，目的是增加電力巡線的自動化程度，減少人工現(xiàn)場巡線的作業(yè)難度和勞動強度并增加準確性。所設計的算法與Terrasolid等激光點云商業(yè)處理軟件相比，具有過程全自動和閾值可靈活設置的優(yōu)勢。不過，后者是一個綜合的點云數(shù)據(jù)預處理軟件，內含點云分類功能，這是它的優(yōu)勢，而本算法是建立在點云已經(jīng)被正確分類的基礎上。

[1]黃瀟嶸，阮毅，李正，等.500 kV超高壓架空輸電線路巡線機器人的空間巡線方法研究[J].機床與液壓，2011，39（11）：36-39.

[2]左來明.遙控航模實現(xiàn)輸電線路巡線[J].東北電力技術，2010（5）：41-47.

[3]陳曉兵，馬玉林，徐祖艦.無人飛機輸電線路巡線技術探討[J].南方電網(wǎng)技術，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數(shù)據(jù)多特征融合分類[J].測繪通報，2010（8）：11-14.

[6]龔亮，李正國，包全福.融合航空影像的LiDAR地物點云分類[J].測繪工程，2012，21（1）：34-38.

[7]劉濤，徐錚，沙成梅，等.基于包圍盒法的散亂點云數(shù)據(jù)的曲率精簡[J].科學技術與工程，2009，9（12）：3333-3336.

[8]劉健，孫殿柱，李延瑞，等.散亂點云局部點集最小包圍盒快速求解算法[J].農(nóng)業(yè)裝備與車輛工程，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

國家高技術研究發(fā)展計劃（863）（No.2010AA 7010419）。

游安清（1975—），男，博士，副研究員，研究方向為圖像處理與計算機視覺技術；韓曉言（1965—），男，博士，高級工程師，研究方向為電力系統(tǒng)運行與控制、智能電網(wǎng)技術；潘旭東（1972—），男，副研究員，研究方向為硬件電路設計技術；賀喜（1987—），男，工程師，研究方向為光電工程技術。E-mail：anqingyou@163.com

2012-09-21

2012-11-26

1002-8331（2014）17-0259-04

CNKI網(wǎng)絡優(yōu)先出版：2012-12-18,http://www.cnki.net/kcms/detail/11.2127.TP.20121218.1522.020.htm l