張 杰, 劉 建, 王茜微

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

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

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

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

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

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

圖1 以當前點為中心的鄰域和鄰域漂移結(jié)果的比較(a)輸入的噪聲點云;(b)以當前點的k個近鄰點構(gòu)造的鄰域;(c)以漂移后的非當前點的k個近鄰點構(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è)計了更為簡潔高效的算法用于候選鄰域生成和鄰域“平坦程度”計算.首先,以往算法在候選鄰域的構(gòu)造過程中強調(diào)候選鄰域要包含當前點.本文將這一條件放寬,只要求候選鄰域的中心點充分靠近當前點,將當前點的所有近鄰點所對應的鄰域作為候選鄰域.這樣對于一給定的鄰域,只需要判斷其中心點與當前點之間的距離即可,不需要利用搜索法查找當前點是否在該鄰域中,運算效率更高.其次,雖然PCA在尖銳特征區(qū)域估計的法向過于平滑,但該算法能較好地刻畫點的分布情況,且在運行速度上具有顯著的優(yōu)勢[5,13].本文利用PCA對候選鄰域的“平坦程度”進行評價,在確保準確性的情況下,有效地提高了算法的計算速度,實驗結(jié)果表明本文提出的方法在精度上與當前的前沿算法持平,但在運行速度上有明顯的改進,實用性較強.

2 算 法

2.1 特征點的選取

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

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

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

2.2 候選特征點的法向估計

圖2 算法流程圖(a)選取候選點pi的k個近鄰點構(gòu)成鄰域Ni,尖銳特征邊用黑線表示;(b)候選點pi的k*個近鄰點構(gòu)成鄰域最終所選點pi,j的k個近鄰點構(gòu)成鄰域,淺灰色圓圈表示,鄰域仍跨越尖銳特征;(d)為pi,j的k*個近鄰點構(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

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

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

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

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

2.3 確定法向

3 實驗結(jié)果及分析

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

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

3.1 參數(shù)的選擇

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

k: 用于計算初始法向的鄰域點的個數(shù).

k*: 用于計算候選特征點法向的鄰域點的個數(shù).

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

3.2 評價函數(shù)

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

3.3 結(jié)果分析

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

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

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

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

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

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

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

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

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

3.4 時間比較

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

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

4 結(jié) 論

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