秦家鑫，萬(wàn)幼川，何培培，陳茂霖，盧維欣，王思穎

（武漢大學(xué)遙感信息工程學(xué)院，武漢430079）

一種建筑物點(diǎn)云輪廓線的自動(dòng)提取方法

秦家鑫，萬(wàn)幼川，何培培，陳茂霖，盧維欣，王思穎

（武漢大學(xué)遙感信息工程學(xué)院，武漢430079）

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

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

0 引 言

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

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

1 原理與方法

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

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

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

③輪廓線提取。利用空間幾何關(guān)系對(duì)面狀點(diǎn)云提取輪廓線，提取的面狀點(diǎn)云輪廓線和線狀點(diǎn)云的并集即為最終的輪廓線點(diǎn)云。

圖1 流程圖

1.1 主成分分析

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

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

當(dāng)σ1?σ2、σ3時(shí)，a1D在3個(gè)維度特征值中最大，判定為一維線特征；同理當(dāng)σ1、σ2?σ3時(shí)，a2D最大，判定為二維面特征；當(dāng)σ1≈σ2≈σ3時(shí)，a3D最大，判定為三維無(wú)序散亂點(diǎn)特征。

1.2 獲取最佳鄰域

點(diǎn)的維度特征會(huì)隨著鄰域點(diǎn)集的變化而改變，鄰域半徑r的取值會(huì)影響主維度的判定，有時(shí)甚至?xí)泻艽蟮牟町愋浴?duì)于點(diǎn)云中的每個(gè)點(diǎn)，理論上都存在一個(gè)最佳鄰域半徑r＊，使得鄰域中的信息可以最好地描述出該點(diǎn)處的維度特征。為了計(jì)算出r＊，設(shè)定r的取值范圍［rmin，rmax］，計(jì)算不同r值下鄰域點(diǎn)集的熵：

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

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

1.3 輪廓線提取

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

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

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

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

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

⑤判斷X′1與Xp的方向，如果X′1在Xp的順時(shí)針?lè)较?，就按照順時(shí)針?lè)较蛉ニ阉?；否則，按照逆時(shí)針?biāo)阉飨乱粋€(gè)鄰域點(diǎn)。

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

圖2 位置關(guān)系圖

2 實(shí)驗(yàn)與分析

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

圖3 華中師范大學(xué)正門(mén)原始點(diǎn)云

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

圖4 最佳半徑下點(diǎn)云主維度的判定結(jié)果

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

圖5 輪廓線整體效果圖

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

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

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

圖7 維度特征與鄰域半徑關(guān)系圖

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

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

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

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

表2 本文方法與現(xiàn)有方法的實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)／個(gè)

3 結(jié)束語(yǔ)

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

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

［2］ 張瑞菊，王晏民，李德仁.快速處理大數(shù)據(jù)量三維激光掃描數(shù)據(jù)的技術(shù)研究［J］.測(cè)繪科學(xué)，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計(jì)劃（2013AA122104－3）；博士點(diǎn)基金（20130141130003）；國(guó)家科技支撐（2012BAJ15B04）。

秦家鑫（1989—），男，碩士研究生，主要研究方向?yàn)榈孛婕す恻c(diǎn)云數(shù)據(jù)處理。

E－mail：qinjiaxin12345＠163.com