基于鄰域漂移的點(diǎn)云法向估計(jì)算法研究

張 杰, 劉 建, 王茜微

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院,遼寧 大連 116029)

近幾年來出現(xiàn)的各種三維激光掃描儀和深度照相機(jī),使得點(diǎn)云成為許多實(shí)際應(yīng)用的焦點(diǎn),法向是點(diǎn)云中一個(gè)重要的幾何屬性.高質(zhì)量的法向有助于諸多點(diǎn)云處理算法,例如曲面重建、點(diǎn)云分割、點(diǎn)云去噪以及特征描述等.雖然近年來涌現(xiàn)出大量法向估計(jì)的算法,但由于噪聲和非均勻采樣的影響,快速準(zhǔn)確地恢復(fù)點(diǎn)云的尖銳特征仍然是一個(gè)具有挑戰(zhàn)性的工作.

點(diǎn)云的法向估計(jì)算法可分為基于Voronoi/Delaunay算法[1-2]、基于法向修正的算法[3-4]和基于局部鄰域擬合法.基于Voronoi/Delaunay算法是利用三角剖分建立數(shù)據(jù)間的拓?fù)潢P(guān)系,然后基于重建出來的拓?fù)潢P(guān)系重建法向.這類算法對噪聲比較敏感,無法處理大噪聲及尖銳特征.基于法向修正的算法主要是一種基于平滑化的濾波方法,雖然這類方法在尖銳特征處可以得到較為理想的結(jié)果.但這類方法對輸入的初始法向要求較高,當(dāng)尖銳特征處的初始法向存在嚴(yán)重的光滑和污染,基于法向修正的算法無法準(zhǔn)確地恢復(fù)模型的尖銳特征.

基于局部鄰域擬合法是由Hoppe等人[5]首次提出的,該方法主要是利用主成分分析法(Principal Component Analysis, PCA)對鄰域結(jié)構(gòu)進(jìn)行分析.當(dāng)曲面是光滑的,PCA可以準(zhǔn)確地估計(jì)點(diǎn)云的法向.但對于尖銳特征點(diǎn),在擬合時(shí)由于受到位于其他光滑曲面上點(diǎn)的影響,導(dǎo)致估計(jì)的法向過于光滑.為了進(jìn)一步提高法向估計(jì)的結(jié)果,Guennebaud 等人[6]利用代數(shù)球?qū)︵徲蜻M(jìn)行擬合;Pauly 等人[7]利用高斯權(quán)對鄰域點(diǎn)進(jìn)行加權(quán),對距離當(dāng)前點(diǎn)較近的鄰域點(diǎn),賦予較大權(quán)重;Yoon 等人[8]利用統(tǒng)計(jì)學(xué)的集成技術(shù)改進(jìn)PCA算法的魯棒性.以上的改進(jìn)方法要求在加權(quán)和鄰域的放縮過程中是各向同性的,但位于不同光滑曲面的點(diǎn)仍然會對擬合的結(jié)果產(chǎn)生影響.

理想情況下,與當(dāng)前點(diǎn)位于不同光滑曲面上的點(diǎn)應(yīng)被忽略.近年來魯棒性技術(shù)[9-12]、子空間分割技術(shù)[13-15]以及深度學(xué)習(xí)[16-20]都被引入法向估計(jì)中來對鄰域進(jìn)行正確的選擇.上述各類點(diǎn)云法向估計(jì)方法,在法向估計(jì)的性能和效率上得到一定提升.然而,這些方法都是利用以當(dāng)前點(diǎn)為中心的鄰域進(jìn)行法向估計(jì).由于在尖銳特征附近,曲面是由兩個(gè)甚至多個(gè)光滑區(qū)域拼接而成,以當(dāng)前點(diǎn)為中心的鄰域并不適合用于法向估計(jì).

近期一些學(xué)者[21-22]受到圖像濾波方法[23]的啟發(fā),選擇以非當(dāng)前點(diǎn)為中心的鄰域進(jìn)行法向估計(jì).Cao等人[21]將尖銳特征點(diǎn)分為邊點(diǎn)和角點(diǎn).對于角點(diǎn),利用自適應(yīng)增長模式構(gòu)造一種完全嵌入在單一光滑曲面的鄰域.對于邊點(diǎn),利用帶方向約束的各項(xiàng)異性鄰域構(gòu)造算法,構(gòu)造一系列包含當(dāng)前點(diǎn)的候選鄰域,并利用協(xié)方差分析對候選鄰域的“平坦程度”進(jìn)行刻畫,最終選擇一中心盡量靠近當(dāng)前點(diǎn),且較為平坦的鄰域,用于法向估計(jì).Zhou等人[22]將包含當(dāng)前點(diǎn)的鄰域作為候選鄰域,然后對每一候選鄰域求解一最優(yōu)擬合平面,并利用鄰域內(nèi)點(diǎn)到擬合平面的距離對鄰域的“平坦程度”進(jìn)行刻畫.雖然文獻(xiàn)[21-22]都得到較好的效果,但用于生成候選鄰域[21]或用于計(jì)算鄰域“平坦程度”[22]的時(shí)間消耗較大,不適合實(shí)際應(yīng)用.

圖1 以當(dāng)前點(diǎn)為中心的鄰域和鄰域漂移結(jié)果的比較(a)輸入的噪聲點(diǎn)云;(b)以當(dāng)前點(diǎn)的k個(gè)近鄰點(diǎn)構(gòu)造的鄰域;(c)以漂移后的非當(dāng)前點(diǎn)的k個(gè)近鄰點(diǎn)構(gòu)造的鄰域Fig.1 Comparison of the neighborhood centered on the current point and the results of shifted neighborhood(a)The input noise point cloud; (b)The neighborhood constructed by k-nearest neighbors of the current point; (c)The neighborhood constructed by k-nearest neighbors of the shifted point

本文采用鄰域漂移的思想,設(shè)計(jì)了更為簡潔高效的算法用于候選鄰域生成和鄰域“平坦程度”計(jì)算.首先,以往算法在候選鄰域的構(gòu)造過程中強(qiáng)調(diào)候選鄰域要包含當(dāng)前點(diǎn).本文將這一條件放寬,只要求候選鄰域的中心點(diǎn)充分靠近當(dāng)前點(diǎn),將當(dāng)前點(diǎn)的所有近鄰點(diǎn)所對應(yīng)的鄰域作為候選鄰域.這樣對于一給定的鄰域,只需要判斷其中心點(diǎn)與當(dāng)前點(diǎn)之間的距離即可,不需要利用搜索法查找當(dāng)前點(diǎn)是否在該鄰域中,運(yùn)算效率更高.其次,雖然PCA在尖銳特征區(qū)域估計(jì)的法向過于平滑,但該算法能較好地刻畫點(diǎn)的分布情況,且在運(yùn)行速度上具有顯著的優(yōu)勢[5,13].本文利用PCA對候選鄰域的“平坦程度”進(jìn)行評價(jià),在確保準(zhǔn)確性的情況下,有效地提高了算法的計(jì)算速度,實(shí)驗(yàn)結(jié)果表明本文提出的方法在精度上與當(dāng)前的前沿算法持平,但在運(yùn)行速度上有明顯的改進(jìn),實(shí)用性較強(qiáng).

2 算 法

2.1 特征點(diǎn)的選取

對每點(diǎn)pi計(jì)算其大小為k的鄰域Ni,如圖1(a)所示.對于鄰域Ni,本文采用與文獻(xiàn)[11-12,21]相同的運(yùn)算方法估計(jì)每個(gè)點(diǎn)的初始法向和特征權(quán)重,并利用特征權(quán)重將所有點(diǎn)分為光滑點(diǎn)和候選特征點(diǎn),為了文章的完整性,將對該過程做一個(gè)簡單的介紹,具體過程見文獻(xiàn)[11-12,21].

首先對于點(diǎn)pi計(jì)算其局部鄰域Ni的協(xié)方差矩陣,協(xié)方差矩陣定義為

其中,0≤λ0≤λ1≤λ2是協(xié)方差矩陣Ti的奇異值.特征權(quán)重ωi刻畫了點(diǎn)pi位于尖銳特征的概率.ωi=0,表示pi為光滑點(diǎn),遠(yuǎn)離尖銳特征,其鄰域Ni為一平面.當(dāng)ωi大于給定的閾值ωt時(shí),將pi定義為候選特征點(diǎn).ωt利用文獻(xiàn)[11-12,21]的方法自動(dòng)估計(jì).

2.2 候選特征點(diǎn)的法向估計(jì)

圖2 算法流程圖(a)選取候選點(diǎn)pi的k個(gè)近鄰點(diǎn)構(gòu)成鄰域Ni,尖銳特征邊用黑線表示;(b)候選點(diǎn)pi的k*個(gè)近鄰點(diǎn)構(gòu)成鄰域最終所選點(diǎn)pi,j的k個(gè)近鄰點(diǎn)構(gòu)成鄰域,淺灰色圓圈表示,鄰域仍跨越尖銳特征;(d)為pi,j的k*個(gè)近鄰點(diǎn)構(gòu)成最終的鄰域Fig.2 Algorithm flowchart (a) Given a candidate feature point pi, we select a neighborhood Niof size k.The sharp feature is represented by the black line. (b) For pi, we select a smaller neighborhood of size k*. (c)pi,jis the selected point. Its neighborhood with size k(represented by grey circle) may across borders. (d) For pi,j, we select a smaller neighborhood of size k* to construct the final

對于候選特征點(diǎn),其鄰域大都是由多個(gè)光滑曲面拼接而成的,PCA擬合而成的平面與候選特征點(diǎn)所在的局部平面存在較大偏差,估計(jì)的初始法向會過于光滑.因此,需要重新構(gòu)造用于法向估計(jì)的鄰域.

Ν={Ni,1,Ni,2,…,Ni,k*}.

Ν內(nèi)任意候選鄰域都對應(yīng)一特征權(quán)重,該權(quán)重的計(jì)算方式如2.1節(jié)所述.將所有的特征權(quán)重構(gòu)成的集合記為：ω={ωi,1,ωi.2,…,ωi,k*}.為了使得所選的候選鄰域Ni,j內(nèi)的所有點(diǎn)都位于同一光滑曲面,需找到特征權(quán)重集合中的最小值ωi,j*,其所對應(yīng)的點(diǎn)pi,j*為最終選用點(diǎn)：

pi,j*=arg min{ωi,j|j=1,2,…,k*}.

2.3 確定法向

3 實(shí)驗(yàn)結(jié)果及分析

為了評估算法性能,將本文的點(diǎn)云法向估計(jì)算法與一些具有代表性的、經(jīng)典的算法及當(dāng)前前沿算法進(jìn)行比較,包括PCA[5]、RNE[9]、HF[16]、HoughCNN[17]、PatchShift[22]、LRRFast[14]、PCV[15].其中，HoughCNN使用作者提供的已訓(xùn)練好的HoughCNN_5s模型,該模型同時(shí)使用5個(gè)鄰域尺度(32, 64, 128, 256, 512).HF根據(jù)不同的采樣策略共有3個(gè)版本.根據(jù)以往實(shí)驗(yàn),HF_cubes在運(yùn)算性能和計(jì)算效率上表現(xiàn)更優(yōu),本文選擇HF_cubes進(jìn)行比較.

本文測試了包含多種光滑曲面和尖銳特征的合成模型,并對這些模型添加了均值為0的高斯噪聲,其標(biāo)準(zhǔn)差定義為點(diǎn)間平均距離的百分比,分別為30%, 40%, 50%, 60%.

3.1 參數(shù)的選擇

本文算法主要有2個(gè)參數(shù),分別為

k: 用于計(jì)算初始法向的鄰域點(diǎn)的個(gè)數(shù).

k*: 用于計(jì)算候選特征點(diǎn)法向的鄰域點(diǎn)的個(gè)數(shù).

其中,噪聲的大小決定k和k*取值,當(dāng)噪聲越大時(shí)，k和k*的值越大.在實(shí)驗(yàn)中k=100,k*=k/2.其他方法鄰域點(diǎn)個(gè)數(shù)均設(shè)為100.所有算法的其余相關(guān)參數(shù)都采用默認(rèn)值.

3.2 評價(jià)函數(shù)

與LRRfast、HF_cubes等算法相同,本文使用具有閾值的均方根誤差(RMS_τ)[11-12]對計(jì)算結(jié)果進(jìn)行定量的評價(jià),如下所示：

3.3 結(jié)果分析

圖3和圖4展示了不同算法在各個(gè)模型上RMS_τ的變化情況及均值.圖5給出不同算法在多個(gè)模型上的可視化結(jié)果.

圖3 不同模型上的RMS_τ值隨噪聲的變化情況Fig.3 RMS_τ value on different models with various noise

圖4 不同模型上的RMS_τ均值Fig.4 The averageRMS_τof various methods

如圖5所示,即使在非均勻采樣的情況下, PCA算法仍能準(zhǔn)確估計(jì)光滑曲面的法向信息(如圖5中第6行和第7行所示).但是該算法在尖銳特征處估計(jì)的法向過于平滑,其RMS_τ值亦遠(yuǎn)遠(yuǎn)大于其他算法.這主要是因?yàn)镻CA是利用整個(gè)鄰域?qū)η衅矫孢M(jìn)行擬合.但在尖銳特征處,點(diǎn)的鄰域大多是由兩個(gè)以上光滑曲面拼接而成.在擬合時(shí)受到其他光滑曲面上點(diǎn)的影響, PCA算法無法準(zhǔn)確地恢復(fù)出尖銳特征處的法向.

RNE和HF_cubes在尖銳特征處的效果要優(yōu)于PCA(如圖5中前5行所示),且在尖銳特征模型上的RMS_τ值低于PCA(如圖3(a)～圖3(d)所示).但當(dāng)處理比較復(fù)雜的鄰域結(jié)構(gòu)時(shí)所估計(jì)的法向仍稍有光滑(如圖5中第3行所示).

HoughCNN_5s使用了當(dāng)前流行的深度學(xué)習(xí)算法,且通過考慮多個(gè)鄰域尺度來提高算法性能.但當(dāng)輸入數(shù)據(jù)具有特殊屬性時(shí),需要重新訓(xùn)練網(wǎng)絡(luò)模型.從圖5所示的結(jié)果來看,Hough_CNN_5s在尖銳特征處仍稍有光滑,且其RMS_τ值要高于 LRRfast和PCV.

LRRfast、PatchShift和 PCV可以很好地恢復(fù)各種尖銳特征(如圖5中前5行所示).但是在處理光滑曲面時(shí),計(jì)算的法向具有較大偏差(如圖5的第6行和第7行所示),導(dǎo)致RMS_τ值較高(如圖3(e)所示).

本文算法在不同模型和噪聲上都得到了較好的結(jié)果.在具有尖銳特征的模型上,本文算法的效果與LRRfast、PatchShift和 PCV持平(如圖3(a)～圖3(d)及圖5的前5行所示),且其在所有模型上的RMS_τ均值與PCV持平并低于其他所有算法(如圖4所示).對于光滑曲面(如圖3(e)所示),其RMS_τ值與 PCA 基本持平,且明顯低于其他算法.

圖5 不同算法法向估計(jì)結(jié)果的可視化比較Fig.5 Visualization of estimated normals via various methods

3.4 時(shí)間比較

表1 不同算法的RMS_τ均值和時(shí)間均值的比較

表1展示了不同算法的RMS_τ均值及時(shí)間均值.所有實(shí)驗(yàn)所使用的電腦配置為1CPU Intel(R) Core i3 (TM) 2.4GHz.由于PCA算法較為簡單,即使在MATLAB 實(shí)現(xiàn)下,其運(yùn)行速度也是最快的.但PCA估計(jì)的法向過于光滑,無法準(zhǔn)確對尖銳特征進(jìn)行刻畫.使用C/C++實(shí)現(xiàn)(表中記為“C”)的算法(RNE,HF_cubs,HoughCNN_5s)速度也較快.而其中使用 MATLAB 實(shí)現(xiàn)(包括MATLAB 和C/C++ 混編實(shí)現(xiàn)的表中記為“M&C”)的PCV算法的時(shí)間消耗僅好于LRRFast和PatchShift.本文算法的時(shí)間消耗僅次于PCA,但其性能顯著高于PCA,且RMS_τ值與PCV和LRRfast相持平,顯著好于其他算法.總之,本文算法能更好地兼顧輸出的法向的質(zhì)量與計(jì)算速度.

4 結(jié) 論

本文提出一種基于鄰域漂移的法向估計(jì)算法,實(shí)現(xiàn)快速準(zhǔn)確的法向估計(jì).對于位于尖銳特征邊附近的點(diǎn),該算法首先通過k-近鄰搜索和協(xié)方差分析,在當(dāng)前點(diǎn)附近尋找一最優(yōu)鄰域,該鄰域遠(yuǎn)離尖銳特征,但靠近當(dāng)前點(diǎn),可以對當(dāng)前點(diǎn)所在曲面的結(jié)構(gòu)進(jìn)行有效刻畫.然后對最優(yōu)鄰域使用PCA算法,獲得最終法向.本文算法在確保法向估計(jì)準(zhǔn)確性的基礎(chǔ)上,最大程度縮短運(yùn)行時(shí)間,提高算法效率.但本文算法沒有考慮尖銳特征情況下的非均勻采樣問題.如何在確保準(zhǔn)確性和提高算法效率的基礎(chǔ)上,考慮尖銳特征下的非均勻采樣問題,這是未來的一項(xiàng)重要工作.