層次化點(diǎn)云邊界快速精確提取方法研究

吳俊河，林 松，施向豐

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

引 言

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

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

針對(duì)上述算法中邊界點(diǎn)提取耗時(shí)較長(zhǎng)的問(wèn)題，本文中提出一種層次化提取邊界點(diǎn)的方法。通常邊界點(diǎn)只占總點(diǎn)云數(shù)據(jù)的少部分，對(duì)每個(gè)點(diǎn)都進(jìn)行精確判定效率不高，可以采取簡(jiǎn)單的判定方法:先對(duì)整體點(diǎn)云進(jìn)行初步篩選，提取出邊界點(diǎn)潛在點(diǎn)集，再對(duì)邊界點(diǎn)潛在點(diǎn)集進(jìn)行精提取，從而能夠?qū)崿F(xiàn)邊界點(diǎn)的高效提取。

1 算法描述

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

Fig.1 Algorithm flow chart

1.1 邊界點(diǎn)粗提取

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

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

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

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

(2)計(jì)算R鄰域內(nèi)點(diǎn)集重心。通過(guò)k-D樹(shù)檢索采樣點(diǎn)R鄰域內(nèi)點(diǎn)，利用下式計(jì)算該鄰域內(nèi)點(diǎn)集重心坐標(biāo)：

(1)

(3)計(jì)算重心點(diǎn)與采樣點(diǎn)距離值D。設(shè)定距離閾值δ，若D≥δ，則采樣點(diǎn)被標(biāo)記為邊界點(diǎn)，同時(shí)保存該點(diǎn)的索引。

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

圖3為邊界點(diǎn)粗提取結(jié)果圖。圖中的點(diǎn)云數(shù)據(jù)包括點(diǎn)云內(nèi)部邊界點(diǎn)和點(diǎn)云外部邊界點(diǎn)，粗提取的邊界點(diǎn)集中包含邊界點(diǎn)、少量毛刺噪聲點(diǎn)、邊界邊緣內(nèi)部點(diǎn)。粗提取方法可以有效地剔除大部分非邊界點(diǎn)，可以為后續(xù)精提取邊界點(diǎn)提高效率。

Fig.3 Crude extraction of boundary points

1.2 邊界點(diǎn)精提取

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

(2)

(3)

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

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

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

(4)

(5)

圖5為精提取結(jié)果圖。可以看出，基于鄰近點(diǎn)最大夾角的方法剔除了少量毛刺噪聲點(diǎn)和邊界邊緣內(nèi)部點(diǎn)，能夠精確提取邊界點(diǎn)。對(duì)粗提取過(guò)程中篩選出的點(diǎn)集進(jìn)行精確提取，避免對(duì)每一個(gè)原始點(diǎn)進(jìn)行微切平面擬合及精確判定，故能夠極大地提高邊界點(diǎn)的提取效率。

Fig.5 Essence extraction of boundary points

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

選取掃描的桌子點(diǎn)云數(shù)據(jù)驗(yàn)證本文中算法的可行性，再采用瑞格VZ-1000掃描的白塔數(shù)據(jù)對(duì)本文中算法的提取精度進(jìn)行分析。實(shí)驗(yàn)在配置為i5-6200U CPU 2.30GHz、內(nèi)存8GB、Windows 10 64位操作系統(tǒng)的PC機(jī)運(yùn)行，在MATLAB R2016a軟件中編寫(xiě)腳本實(shí)現(xiàn)本文中的算法、參考文獻(xiàn)[8]中的算法和參考文獻(xiàn)[16]中的算法。

2.1 可行性驗(yàn)證分析

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

Fig.6 Table boundary points extract results

表1中對(duì)3種不同邊界提取方法的提取結(jié)果進(jìn)行了比較。參考文獻(xiàn)[8]中可視為不進(jìn)行粗提取，直接對(duì)原始數(shù)據(jù)進(jìn)行精提取，總耗時(shí)最長(zhǎng)，但能得到精確的邊界點(diǎn)集。參考文獻(xiàn)[16]中粗提取的點(diǎn)云個(gè)數(shù)比本文中的方法多，但是精提取后點(diǎn)云個(gè)數(shù)比本文中方法少，說(shuō)明本文中粗提取的點(diǎn)集包含更多的邊界點(diǎn)，本文中粗提取的精度更高，因此后續(xù)精提取的時(shí)間能縮短35.54%。本文中提出的粗提取方法運(yùn)行時(shí)間相較于參考文獻(xiàn)[16]中的縮短了21.21%，總耗時(shí)相較于參考文獻(xiàn)[8]中的縮短了28.21%，較參考文獻(xiàn)[16]中的縮短了22.89%。

Table 1 Comparison of operation efficiency of different boundary extraction methods

2.2 精度分析

對(duì)白塔點(diǎn)云數(shù)據(jù)先進(jìn)行網(wǎng)格法下采樣，網(wǎng)格大小為0.01m，共55049個(gè)點(diǎn)，如圖7a所示。同樣粗提取中R取0.03m，距離D取0.01m，最大夾角閾值取90°，本文中邊界點(diǎn)的提取結(jié)果如圖7b所示，參考文獻(xiàn)[8]中提取的白塔邊界點(diǎn)結(jié)果如圖7c所示，參考文獻(xiàn)[16]中提取的邊界點(diǎn)結(jié)果如圖7d所示。

Fig.7 Extraction results of white tower boundary points

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

Table 2 Comparison of extraction precision between different boundary extraction methods

3 結(jié) 論

本文中提出了一種快速精確提取邊界點(diǎn)的方法，針對(duì)傳統(tǒng)的基于鄰近點(diǎn)最大夾角提取邊界點(diǎn)方法進(jìn)行改進(jìn)，首先依據(jù)R鄰域點(diǎn)集重心坐標(biāo)與采樣點(diǎn)的距離粗提取邊界點(diǎn)，將大量的非邊界點(diǎn)剔除，提高提取效率，再依據(jù)鄰近點(diǎn)最大夾角精確提取邊界點(diǎn)。實(shí)驗(yàn)表明本文中提出的方法能夠快速精確的提取邊界點(diǎn)，層次化快速邊界提取方法中盡管縮短了提取時(shí)間，但是降低了提取精度，通過(guò)白塔數(shù)據(jù)實(shí)驗(yàn)表明，相對(duì)于傳統(tǒng)的依據(jù)鄰近點(diǎn)最大夾角提取邊界點(diǎn)方法，本文中的方法在損失5.23%的精度下能縮短22.11%的運(yùn)行時(shí)間，相較于其它層次化提取方法，本文中的提取精度在提高7.17%的同時(shí)能縮短10.99%的運(yùn)行時(shí)間。但本文中的方法易受到點(diǎn)云密度的影響，相關(guān)閾值的選取都與點(diǎn)云密度有關(guān)，對(duì)密度分布不均勻的數(shù)據(jù)提取的效果不佳，下一步研究方向?yàn)樘岣咚惴ǖ淖赃m應(yīng)程度。