層次化點云邊界快速精確提取方法研究

吳俊河，林 松，施向豐

(1.惠州市規劃勘測研究院，惠州 516000；2.河海大學 地球科學與工程學院，南京 211100；3.江西理工大學 土木與測繪工程學院， 贛州 341000)

引 言

近年來,3維激光掃描技術在快速高精度獲取3維空間信息中發揮著重要作用[1-2]，基于點云的目標識別和3維重建一直都是研究熱點，邊界提取是目標識別[3]、3維重建[4-5]過程中的重要步驟。精確的邊界不僅影響著曲面幾何特征的表達，還對重建后曲面模型的質量和精度有著重要的作用[6]。

目前邊界點云的提取算法較多，主要有柵格劃分法、微切平面法、三角網法和凸包類算法等。KE等人[7]對點云進行空間柵格劃分，建立空間拓撲關系，依據柵格內是否有點檢索邊界，這種算法速度快，但是受點云密度和柵格大小影響較大，且提取精度不高。基于微切平面的方法是將待判定點及其鄰域點投影到微切平面上，再依據一定的準則判別該點是否屬于邊界點。SUN等人[8]提出計算微切平面內投影點所構成的最大夾角作為判定依據。CHEN等人[9]通過模擬點與點間的拉力的合力判斷待定點是否是邊界點。SU等人[10]先計算各點法向量，然后將法向量投影至高斯球中，通過高斯映射法線聚類，依據聚類結果提取邊界點，基于微切平面的方法效率太低，對每個點都需要投影，然后根據判斷條件精確判定，耗時較長。基于三角網的方法，CHEN等人[11]提出通過遍歷所有三角形的邊長，依據邊長閾值確定邊界邊，這種方法需要事先構建三角網，耗時較多。LIN等人[12]也提出了一種過濾三角網的方法提取點云邊界，該方法也在點云數據量較少的情況下能取得較好的效果，在海量數據中提取效率較低?；谕拱愃惴ㄝ^為典型的是alpha shapes[13-14]，這種方法在2維點集中能取得較好的結果，但是在3維點集中提取結果不佳。LI等人[15]提出了凸殼內縮法提取離散點邊界，但是無法提取內部空洞邊界。JIANG等人[16]為了提高邊界提取的效率，先采用HAN[17]提出的模擬點間拉力的方法先粗提取邊界點，再依據SUN提出的最大夾角準則精提取邊界點，該方法能夠一定程度提高邊界點提取效率，但是粗提取的判斷準則計算量依然較大。

針對上述算法中邊界點提取耗時較長的問題，本文中提出一種層次化提取邊界點的方法。通常邊界點只占總點云數據的少部分，對每個點都進行精確判定效率不高，可以采取簡單的判定方法:先對整體點云進行初步篩選，提取出邊界點潛在點集，再對邊界點潛在點集進行精提取，從而能夠實現邊界點的高效提取。

1 算法描述

本文中的算法是首先對輸入的點云數據構建k維(k-dimensional，k-D)樹用于空間索引[18]，再采用R鄰域內重心差異準則粗提取邊界點，對粗提取的邊界點在局部投影面上精確提取邊界點。本文中算法的具體流程如圖1所示。

Fig.1 Algorithm flow chart

1.1 邊界點粗提取

3維激光掃描獲取的點云數據是離散且無序的，需建立空間索引結構提高數據檢索效率。k-D樹是點云常用的數據組織結構，可以快速檢索采樣點的鄰域點。對于非邊界點，其R鄰域內點集分布較為均勻，鄰域內點集的重心坐標與采樣點的距離較小；對于邊界點，其R鄰域內點集集中分布在采樣點的一側，鄰域內點集的重心坐標與采樣點的距離較大，如圖2所示。因此,本文中從采樣點R鄰域內點集重心坐標與采樣點位置的距離D出發，利用邊界點與非邊界點中D的差異性粗提取邊界點集。

Fig.2 Location map of barycenter points in the neighborhood of non-boundary points and boundary points R

粗提取的具體流程如下所述。

(1)構建k-D樹。采用快速分類的分割方法建立k-D樹，把指定維度的值放在根上，在這個維度上較小數值放在左子樹、較大的放在右子樹，然后分別在左右子樹上重復該過程，直至最后一個樹僅有一個點。

(2)計算R鄰域內點集重心。通過k-D樹檢索采樣點R鄰域內點，利用下式計算該鄰域內點集重心坐標：

(1)

(3)計算重心點與采樣點距離值D。設定距離閾值δ，若D≥δ，則采樣點被標記為邊界點，同時保存該點的索引。

(4)遍歷所有點。重復步驟(2)和步驟(3)，對所有點進行判定，完成邊界點的粗提取，得到粗提取邊界點集的索引。

圖3為邊界點粗提取結果圖。圖中的點云數據包括點云內部邊界點和點云外部邊界點，粗提取的邊界點集中包含邊界點、少量毛刺噪聲點、邊界邊緣內部點。粗提取方法可以有效地剔除大部分非邊界點，可以為后續精提取邊界點提高效率。

Fig.3 Crude extraction of boundary points

1.2 邊界點精提取

粗提取的邊界點中包含了邊界點、部分邊界邊緣內部點和少量毛刺噪聲點，精提取的目的就是將邊界點從粗提取的點集中分離處理來。目前精確提取邊界點的方法有很多，參考文獻中提出的基于鄰近點最大夾角的方法能夠有效的提取邊界點。將采樣點及其鄰域內點集投影至最小二乘擬合的微切平面上，尋找采樣點與鄰域內點連線構成的最大夾角εmax，若εmax大于設定的角度閾值，則該點為邊界點。

(2)

(3)

在微切平面內，通過(4)式得到鄰域投影點q′與采樣點p(x,y,z)的單位方向向量。這樣就將點p鄰域內點分布在以點p為圓心的單位圓上，如圖4a所示。選擇單位圓內任意方向向量pqi′為起始方向，計算pqi′與微切平面法向量n的叉積v，分別計算其它方向向量與pqi′和v的夾角αi，βi，如圖4b所示。

Fig.4 The included angle on the projection plane of neighborhood point

若βi≥90°，則αi=360°-αi。將αi從小到大排序，通過(5)式計算相鄰向量間的夾角，最大夾角閾值一般設置為90°：

(4)

(5)

圖5為精提取結果圖?？梢钥闯?，基于鄰近點最大夾角的方法剔除了少量毛刺噪聲點和邊界邊緣內部點，能夠精確提取邊界點。對粗提取過程中篩選出的點集進行精確提取，避免對每一個原始點進行微切平面擬合及精確判定，故能夠極大地提高邊界點的提取效率。

Fig.5 Essence extraction of boundary points

2 實驗與分析

選取掃描的桌子點云數據驗證本文中算法的可行性，再采用瑞格VZ-1000掃描的白塔數據對本文中算法的提取精度進行分析。實驗在配置為i5-6200U CPU 2.30GHz、內存8GB、Windows 10 64位操作系統的PC機運行，在MATLAB R2016a軟件中編寫腳本實現本文中的算法、參考文獻[8]中的算法和參考文獻[16]中的算法。

2.1 可行性驗證分析

原始點云平均間距為0.001m，共454943個點，首先對原始點云精簡，采用網格法下采樣[19-20]，網格間距為0.01m，精簡后點云個數為20988個，如圖6a所示。參考文獻[8]中提取的邊界結果如圖6b所示。本文中算法粗提取中R取3倍網格間距，即R=0.3m，距離D取網格間距，即點云平均間距0.01m，粗提結果如圖6c所示，粗提取過程中最大夾角閾值設置為90°，最終提取的邊界點結果如圖6d所示。參考文獻[16]中同樣采用先粗提取后精提取的思路，其粗提取的結果如圖6e所示，精提取結果如圖6f所示。由實驗結果可以看出，本文中算法相較于參考文獻[16]中的能更為完整地提取邊界點云，驗證了本文中算法的可行性。

Fig.6 Table boundary points extract results

表1中對3種不同邊界提取方法的提取結果進行了比較。參考文獻[8]中可視為不進行粗提取，直接對原始數據進行精提取，總耗時最長，但能得到精確的邊界點集。參考文獻[16]中粗提取的點云個數比本文中的方法多，但是精提取后點云個數比本文中方法少，說明本文中粗提取的點集包含更多的邊界點，本文中粗提取的精度更高，因此后續精提取的時間能縮短35.54%。本文中提出的粗提取方法運行時間相較于參考文獻[16]中的縮短了21.21%，總耗時相較于參考文獻[8]中的縮短了28.21%，較參考文獻[16]中的縮短了22.89%。

Table 1 Comparison of operation efficiency of different boundary extraction methods

2.2 精度分析

對白塔點云數據先進行網格法下采樣，網格大小為0.01m，共55049個點，如圖7a所示。同樣粗提取中R取0.03m，距離D取0.01m，最大夾角閾值取90°，本文中邊界點的提取結果如圖7b所示，參考文獻[8]中提取的白塔邊界點結果如圖7c所示，參考文獻[16]中提取的邊界點結果如圖7d所示。

Fig.7 Extraction results of white tower boundary points

表2中對3種邊界提取方法進行了比較分析。參考文獻[8]中提出的方法能夠有效精確地提取邊界點，且本文中和參考文獻[16]中精提取方法都與參考文獻[8]中邊界提取方法一致，故可以假設參考文獻[8]中提取的邊界點是精確且完整的，通過將本文中和參考文獻[16]中的提取結果與參考文獻[8]中的提取結果進行比較，分析本文中算法的提取精度。對于本文中和參考文獻[16]中提取的結果，通過與參考文獻[8]中的提取結果進行同名點檢索，若本文中或參考文獻[16]中提取的點能在參考文獻[8]中提取的點集中能檢索到同名點，則該點被標記為正確提取點，否則為錯誤提取點。分析表2中正確率和運行時間可知，本文中算法相對與參考文獻[16]不僅耗時較少，而且精度更高，這是由于在粗提取過程中本文中采用了更簡單、更有效的邊界點判定規則。

Table 2 Comparison of extraction precision between different boundary extraction methods

3 結 論

本文中提出了一種快速精確提取邊界點的方法，針對傳統的基于鄰近點最大夾角提取邊界點方法進行改進，首先依據R鄰域點集重心坐標與采樣點的距離粗提取邊界點，將大量的非邊界點剔除，提高提取效率，再依據鄰近點最大夾角精確提取邊界點。實驗表明本文中提出的方法能夠快速精確的提取邊界點，層次化快速邊界提取方法中盡管縮短了提取時間，但是降低了提取精度，通過白塔數據實驗表明，相對于傳統的依據鄰近點最大夾角提取邊界點方法，本文中的方法在損失5.23%的精度下能縮短22.11%的運行時間，相較于其它層次化提取方法，本文中的提取精度在提高7.17%的同時能縮短10.99%的運行時間。但本文中的方法易受到點云密度的影響，相關閾值的選取都與點云密度有關，對密度分布不均勻的數據提取的效果不佳，下一步研究方向為提高算法的自適應程度。