一種建筑物點云輪廓線的自動提取方法

秦家鑫，萬幼川，何培培，陳茂霖，盧維欣，王思穎

（武漢大學遙感信息工程學院，武漢430079）

一種建筑物點云輪廓線的自動提取方法

秦家鑫，萬幼川，何培培，陳茂霖，盧維欣，王思穎

（武漢大學遙感信息工程學院，武漢430079）

針對地面激光點云包含大量冗余數(shù)據(jù)、特征信息不明顯等缺點，提出了一種自動提取建筑物點云輪廓線的方法。首先基于主成分分析和熵函數(shù)計算每個點的最佳鄰域，再根據(jù)幾何位置關系，濾除散亂點和平面中的點，保留輪廓線點云。針對不同地面激光點云數(shù)據(jù)，無需反復調整閾值。實驗證明，該方法提取的建筑物點云輪廓線清晰完整，與現(xiàn)有方法提取的結果相比正確率有一定的提高，且冗余點云幾乎全部被濾除，自動化程度高，具有良好的適用性。

地面激光掃描儀；主成分分析；熵函數(shù)；最佳鄰域；輪廓線提??；LiDAR

0 引 言

地面激光掃描儀可以快速、精確、多方位地獲取建筑物的三維信息［1］，但點云數(shù)據(jù)通常包括大量冗余數(shù)據(jù)，限制了后續(xù)的存儲、處理等操作的速度和精度［2］。因此，如何在保留建筑物輪廓線點云的前提下，濾除散亂點和平面中的點，從而大幅度縮減點云數(shù)量，同時突出建筑物的特征信息，提高后續(xù)處理的計算速度和效率，成為當前研究的一個重點。

目前，國內外大多利用點的鄰域信息來描述每個點的特征信息，從而保留特征突出的點云，濾除特征不明顯的部分。Gelfand N、Bian Z、Yang Y L等人［3－5］利用積分不變量建立多尺度分析來提取點云特征，其中Gelfand N利用鄰域點來擬合曲面，并用體積積分計算該曲面與半球包圍的體積，用體積值描述點云特征。Rusu R B［6］在鄰域點集中建立局部坐標系，以兩個鄰域點為一組，每組計算4個特征值，構建16維特征直方圖，統(tǒng)計鄰域點集的分布信息。Milroy M J、Yang M、Woo H等人［7－9］估計點云的法矢方向和曲率值，利用法矢方向和曲率值的突變來提取邊界點。上述方法側重點云的不同特征，提取的特征信息也有一定的差異，不能很好地適用于所有點云，且精度受鄰域大小的影響。針對以上問題，基于文獻［10］、文獻［11］在維度方面研究的啟發(fā)，本文提出了一種自動提取建筑物點云輪廓線的方案，該方案不受點云密度、點云分布等屬性的影響，適用于不同情況的地面激光點云數(shù)據(jù)。實驗結果表明，該方法提取的輪廓線清晰完整，且自動化程度較高。

1 原理與方法

基于現(xiàn)有的理論方法研究，文中設計了一種地面激光點云數(shù)據(jù)建筑物輪廓線的自動提取方案，流程圖如圖1所示。該方案主要包括3個關鍵步驟。

①主成分分析［12］。設定鄰域范圍，分別在不同鄰域下進行主成分分析，得到3個維度特征值。

②獲取最佳鄰域并判定每個點的主維度。引入熵函數(shù)［13］，利用不同鄰域下的3個維度特征值求出熵的最小值，并由此得到每個點的最佳鄰域半徑，以最佳鄰域下的維度特征值，判定每個點的主維度，將原始點云分為線狀點云、面狀點云和散亂點云。

③輪廓線提取。利用空間幾何關系對面狀點云提取輪廓線，提取的面狀點云輪廓線和線狀點云的并集即為最終的輪廓線點云。

圖1 流程圖

1.1 主成分分析

不同地物的掃描點在三維空間中呈不同的分布形態(tài)，為了得到掃描點的分布信息，可以利用每個掃描點X及其鄰域點vr的三維坐標｛Xi＝（xi，yi，zi）｜i∈vr｝構造協(xié)方差矩陣：

對矩陣C進行主成分分析，可求得3個特征值，對它們按降序排列，得到λ1≥λ2≥λ3＞0。令，根據(jù)式（2）計算每個點的3個維度特征，即一維線狀特征a1D、二維面狀特征a2D和三維散亂點特征a3D。其中a1D、a2D、a3D的和為1，換言之，a1D、a2D、a3D分別代表了掃描點屬于3個維度特征的概率。為了得到每個點的主維度，引入主維度判定函數(shù)，見式（3）。

當σ1?σ2、σ3時，a1D在3個維度特征值中最大，判定為一維線特征；同理當σ1、σ2?σ3時，a2D最大，判定為二維面特征；當σ1≈σ2≈σ3時，a3D最大，判定為三維無序散亂點特征。

1.2 獲取最佳鄰域

點的維度特征會隨著鄰域點集的變化而改變，鄰域半徑r的取值會影響主維度的判定，有時甚至會有很大的差異性。對于點云中的每個點，理論上都存在一個最佳鄰域半徑r＊，使得鄰域中的信息可以最好地描述出該點處的維度特征。為了計算出r＊，設定r的取值范圍［rmin，rmax］，計算不同r值下鄰域點集的熵：

當熵取最小值時，表示在此鄰域下該點的主維度特征最突出，求出使熵函數(shù)取最小值時，最佳鄰域半徑r＊值：

在得到每個點的最佳鄰域之后，按照式（1）、式（2）、式（3）得到每個點的主維度，將散亂點濾除，將線特征點視為點云輪廓線，對面特征點進行下一步輪廓線提取處理。

1.3 輪廓線提取

一般情況下，建筑物立面具有規(guī)整的幾何形狀，可看成由許多個平面構成，每個平面的特征信息為其輪廓線，故大量平面中的點是可以濾除的。本文利用空間幾何關系，先為每個點確定其所在的平面，再判斷此點是在平面的邊緣還是平面內部，根據(jù)平面中的點與其鄰域點形成的線段夾角和約為360°來濾除平面中的點，從而保留每個平面的輪廓線點云。具體步驟如下：

①根據(jù)1.2節(jié)得到的最佳鄰域確定X點的最佳鄰域點集vr＊。

②根據(jù)RANSAC算法，從vr＊中隨機抽取兩個不同點｛Xi，Xj｜i，j∈vr＊∩i≠j｝，并重復多次，計算X、Xi、Xj三點所在平面方程并統(tǒng)計vr＊中其余點到平面的歐氏距離和，選取使距離和最小的平面Sxpq的兩鄰域點Xp、Xq，將Xp、Xq從vr＊中刪除。

③遍歷vr＊計算每個∠XpXXi、∠XqXXi，設定角度閾值θ1，若∠XpXXi、∠XqXXi、∠XpXXq的位置關系如圖2（a）、圖2（b）、圖2（c）的一種時，滿足∠1＋∠2－∠3小于θ1；或者位置關系如圖2（d）時，滿足∠1＋∠2＋∠3－360°小于θ1，則認定該點在Sxpq上，否則將Xi從vr＊中刪除。

④設 XXp為起始邊，遍歷vr＊計算每個∠XpXXi，設定角度閾值θ2，選取小于θ2中使∠XpXXi最小的鄰域點X′1。

⑤判斷X′1與Xp的方向，如果X′1在Xp的順時針方向，就按照順時針方向去搜索；否則，按照逆時針搜索下一個鄰域點。

⑥將步驟④得到的鄰域點與X構成的線段設為起始邊，重復步驟④尋求滿足條件的下一個鄰域點X′2，X′3，…，X′n，直到搜索不到滿足條件的鄰域點。

圖2 位置關系圖

2 實驗與分析

為了驗證本文提出的方法的有效性，使用VC＋＋和OpenGL編程實現(xiàn)了該算法。實驗中采用Riegl公司VZ－400激光掃描儀采集的華中師范大學正門及其周圍環(huán)境點云。原始點云如圖3所示。點云數(shù)量約為110萬，點云平均精度約為6cm。點云數(shù)據(jù)對象結構復雜、材質多樣，除一般建筑物水泥、玻璃窗以外，還包括鋼板、LED顯示屏、布制廣告條幅等，在不同區(qū)域內點云密度差異較大，密度最大區(qū)域為400個／m2，而最小只有120個／m2。

圖3 華中師范大學正門原始點云

設置鄰域半徑搜索范圍為2cm到92cm，利用kd樹快速獲得鄰域點集，半徑每增加3cm計算一次維度特征和熵。如果鄰域點個數(shù)大于50，選擇最近的50個鄰域點，否則選擇所有的鄰域點進行計算，得到最佳鄰域下的主維度特征結果如圖4所示。大部分點云主維度判定正確，但也存在少量的錯分現(xiàn)象，例如少量樹葉點云因其鄰域范圍內近似呈現(xiàn)線、面狀分布而導致錯誤分類。

圖4 最佳半徑下點云主維度的判定結果

按照主維度將點云分類之后，對面狀點云進行輪廓線提取。經(jīng)試驗，設θ1＝10°、θ2＝100°時效果最佳，該閾值同樣適用于其他點云數(shù)據(jù)，不需要根據(jù)點云的密度、精度等屬性重新設置。最佳鄰域下提取的輪廓線整體效果如圖5（a）所示，整體輪廓保留比較完整，大量散亂點和平面中的點被濾除，點云數(shù)量從110萬降到17萬，濾除率約為85%。細節(jié)部分如圖6所示，圖6（a）校門立柱和圖6（b）屋頂?shù)妮喞€清晰完整，平面中的點云幾乎全部被濾除，結構相對比較復雜的圖6（c）圖中的“廣埠屯”3個漢字輪廓也能明顯看出。

圖5 輪廓線整體效果圖

為了說明鄰域大小對實驗結果的影響，同時證明本文提出方法的優(yōu)越性，對全部數(shù)據(jù)點云在統(tǒng)一半徑下進行了相同的處理，并對結果做了對比分析。通常，較大的鄰域內各個維度呈現(xiàn)更大的區(qū)分性，但也有特殊的情況。為得到鄰域大小對不同維度特征的影響，分別選取3個維度特征明顯區(qū)域，統(tǒng)計其在不同鄰域半徑下的取值，如圖7所示。

圖6 輪廓線細節(jié)效果圖

圖7 中所取樣本在點云中的位置在圖3中用相應顏色的矩形標出。三幅圖中，當熵取最小值時，對應的r＊為最佳鄰域半徑，此時主維度特征值為最大。圖7（a）中，當r大于r′時，主維度特征值明顯減小，原因主要是遇到拐點、直線方向改變，故點集趨于面狀分布，二維特征值明顯增加；圖7（b）、圖7（c）圖中，當r小于r′時，鄰域點數(shù)量不足，維度特征隨r變化劇烈且無規(guī)律，不能反映出主維度特征。實驗證明：①不同區(qū)域點云的最佳鄰域差異較大，若使用統(tǒng)一的鄰域對全部點云進行處理，必定會造成部分區(qū)域的分類錯誤，如圖8所示；②鄰域過大或過小都會影響主維度的判定；③主成分分析所需的最少鄰域點個數(shù)約為10個，當點數(shù)不足時，計算結果無意義，應繼續(xù)擴大鄰域范圍，直到鄰域點個數(shù)滿足要求。

圖7 維度特征與鄰域半徑關系圖

圖8 最佳鄰域和統(tǒng)一鄰域下主成分分析結果

本次實驗數(shù)據(jù)的建筑物對象包含了多種材質并且結構復雜，這就造成了點云密度在不同區(qū)域的明顯差異。若使用統(tǒng)一鄰域半徑對點云進行處理，不但不能達到很好的效果，而且針對其他數(shù)據(jù)還需要重新修改鄰域大小。對比實驗中將鄰域半徑設為50cm，在此鄰域下輪廓線提取效果如圖5（b）所示，輪廓線保留得較為完整，但與圖5（a）相比較，保留了過多平面中的點和散亂點，如紅色矩形標示區(qū)域。細節(jié)對比如圖8所示，圖8（a下）由于r較小，導致部分散亂點錯分為線特征；圖8（b下）由于r較大，造成部分線、面點云錯分為散亂點。表1定量分析了兩者的分類結果，統(tǒng)計了當鄰域取0.3m、0.5m、0.7m、0.9m時與最佳鄰域下的對比結果。在統(tǒng)一鄰域下，線特征的正確率下降得最多，僅為最佳鄰域下的60%左右，線、面特征的正確率隨鄰域的增大引入散亂點而降低，而散亂點的正確率隨鄰域的增大變化不大，但正確率也只有最佳鄰域下的80%左右。

為了驗證本文提出的方法的優(yōu)越性，引入對比實驗，使用現(xiàn)有的點云特征提取方法對實驗數(shù)據(jù)進行處理，計算點云的法矢方向和曲率值，根據(jù)法矢方向和曲率值的突變來提取邊界點。表2為兩種方法結果對比，其中A表示手動提取的點云個數(shù)，即特征點云個數(shù)；B表示運用本文方法和現(xiàn)有方法計算得到的點云個數(shù)。由表2可知，本文方法提取點云的正確率為92.98%，高于現(xiàn)有方法的83.85%；同時冗余數(shù)據(jù)被大量剔除，冗余率從25.85%下降為3.54%。

表1 最佳鄰域與統(tǒng)一鄰域的主成分分析結果統(tǒng)計／個

表2 本文方法與現(xiàn)有方法的實驗結果統(tǒng)計／個

3 結束語

目前，地面激光已成為建筑物三維重建的一種重要數(shù)據(jù)源，但建筑物點云的輪廓線提取還處于研究階段。本文提出的建筑物點云輪廓線自動提取方法，針對復雜建筑物點云能夠正確計算出最能反映點云特征的鄰域大小，并將點云按照主維度分類之后濾除散亂點云，再根據(jù)幾何位置關系，濾除平面中的點。最終提取出的輪廓線點云清晰完整，冗余點云濾除率高，驗證了算法的準確度和穩(wěn)定性。在算法設計中特地將距離閾值轉換為角度閾值，用每個點與鄰域點的相對位置關系替代絕對位置關系，這樣針對不同點云數(shù)據(jù)無需修改實驗中的閾值，達到自動提取的目的，提高了算法的適用性。

［1］ 趙煦.基于地面激光掃描點云數(shù)據(jù)的三維重建方法研究［D］.武漢：武漢大學，2010.

［2］ 張瑞菊，王晏民，李德仁.快速處理大數(shù)據(jù)量三維激光掃描數(shù)據(jù)的技術研究［J］.測繪科學，2006，31（5）：93－94.

［3］ GELFAND N，MITRA N J，GUIBAS L J，et al.Robust global registration［C］.Symposium on geometry processing，2005，2（3）：5.

［4］ BIAN Z，TONG R.Feature－preserving mesh denoising based on vertices classification［J］.Computer Aided Geometric Design，2011，28（1）：50－64.

［5］ YANG Y L，LAI Y K，HU S M，et al.Robust principal curvatures on multiple scales［C］.Symposium on Geometry Processing，2006：223－226.

［6］ RUSU R B，BLODOW N，MARTON Z C，et al.Aligning point cloud views using persistent feature histograms［C］.Intelligent Robots and Systems，2008.IROS 2008.IEEE／RSJ International Conference on.IEEE，2008：3384－3391.

［7］ MILROY M J，BRADLEY C，VICKERS G W.Segmentation of a wrap－around model using an active contour［J］.Computer－Aided Design，1997，29（4）：299－320.

［8］ YANG M，LEE E.Segmentation of measured point data using aparametric quadric surface approximation［J］.Computer－Aided Design，1999，31（7）：449－457.

［9］ WOO H，KANG E，WANG S，et al.A new segmentation method for point cloud data［J］.International Journal of Machine Tools and Manufacture，2002，42（2）：167－178.

［10］ GRESSIN A，MALLET C，DEMANTKéJ，et al.Towards 3Dlidar point cloud registration improvement using optimal neighborhood knowledge［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2013，79：240－251.

［11］ DEMANTKéJ，MALLET C，DAVID N，et al.Dimensionality based scale selection in 3Dlidar point clouds［J］.International Archives of Photogrammetry，Remote Sensing and Spatial Information Sciences，Laser Scanning，2011.

［12］ GROSS H，JUTZI B，THOENNESSEN U.Segmentation of tree regions using data of a full－waveform laser［J］.International Archives of Photogrammetry，Remote Sensing and Spatial Information Sciences，2007，36（part 3）：W49A.

［13］ SHANNON C E.A mathematical theory of communication［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2001，5（1）：3－55.

An Automatic Building Boundary Extraction Method of TLS Data

QIN Jia－xin，WAN You－chuan，HE Pei－pei，CHEN Mao－lin，LU Wei－xin，WANG Si－ying
（School of Remote Sensing and Information Engineering，Wuhan University，Wuhan 430079）

In view of the redundancy of point cloud data and the shortcoming of unconspicuous features，this paper presents an automatic method of building boundary extraction.Firstly，the optimal neighborhood is acquired according to the principal component analysis and entropy function.Then，scattered points are deleted and boundaries of planes are extracted by geometry information.Experimental results show that this method can not only extract boundary completely and filter almost all improper point cloud data，but also has a high applicability and automaticity without adjusting threshold to different TLS data.

terrestrial laser scanner；principal component analysis；entropy function；optimal neighborhood；boundary extraction；LiDAR

10.3969／j.issn.1000－3177.2015.04.001

TP751

A

1000－3177（2015）140－0003－05

2014－06－17

2014－08－31

863計劃（2013AA122104－3）；博士點基金（20130141130003）；國家科技支撐（2012BAJ15B04）。

秦家鑫（1989—），男，碩士研究生，主要研究方向為地面激光點云數(shù)據(jù)處理。

E－mail：qinjiaxin12345＠163.com