尖銳特征曲面散亂點(diǎn)云法向估計(jì)

袁小翠,吳祿慎,陳華偉

(1.南昌工程學(xué)院 江西省精密驅(qū)動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室，江西 南昌 330099;2.南昌大學(xué) 機(jī)電工程學(xué)院，江西 南昌 330031)

?

尖銳特征曲面散亂點(diǎn)云法向估計(jì)

袁小翠1*,吳祿慎2,陳華偉2

(1.南昌工程學(xué)院 江西省精密驅(qū)動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室，江西 南昌 330099;2.南昌大學(xué) 機(jī)電工程學(xué)院，江西 南昌 330031)

針對(duì)現(xiàn)有算法對(duì)尖銳特征曲面點(diǎn)云法矢估計(jì)不準(zhǔn)確，點(diǎn)云處理時(shí)容易丟失曲面細(xì)節(jié)特征等問(wèn)題，提出一 種尖銳特征曲面散亂點(diǎn)云法向估計(jì)法。該方法用主成分分析法粗估計(jì)點(diǎn)云法向；然后，根據(jù)各鄰域點(diǎn)的空間歐氏距離和法向距離對(duì)各鄰域法向加權(quán)，用加權(quán)鄰域法向之和來(lái)更新當(dāng)前點(diǎn)的法向；最后，測(cè)試估計(jì)法向與標(biāo)準(zhǔn)法向的誤差，評(píng)價(jià)估計(jì)法矢的準(zhǔn)確性，并且將估計(jì)的法向應(yīng)用到點(diǎn)云數(shù)據(jù)處理中來(lái)比較特征保留效果。實(shí)驗(yàn)結(jié)果表明：本文方法能夠準(zhǔn)確地估計(jì)尖銳特征曲面的法向，最小誤差接近0。另外，該方法對(duì)噪聲有較好的魯棒性，點(diǎn)云處理時(shí)能保留曲面的尖銳特征。相比于其他特征曲面法向估計(jì)法，所提出的方法估計(jì)的法向誤差更小、速度更快、耗時(shí)更少。

散亂點(diǎn)云；尖銳特征；法向估計(jì)；逆向工程；特征保留；主成分分析

1　引　言

法向量是點(diǎn)云的重要屬性之一，點(diǎn)云法向量的有效估計(jì)是逆向工程中點(diǎn)云數(shù)據(jù)處理的基礎(chǔ)，除了精確和高質(zhì)量的點(diǎn)云繪制方法主要依賴于法向量，此外，許多有效的點(diǎn)云處理方法也都需要準(zhǔn)確的法向量作為輸入，如點(diǎn)云去噪[1]、分割[2]、數(shù)據(jù)精簡(jiǎn)[3]、曲面重建等[4]。對(duì)尖銳特征面，若不能準(zhǔn)確估計(jì)特征區(qū)域(兩個(gè)或者多個(gè)曲面交界的過(guò)渡區(qū)域)的法向量，則點(diǎn)云處理時(shí)容易丟失曲面的細(xì)節(jié)特征，導(dǎo)致重建后的曲面難以恢復(fù)原始模型的幾何特征。

近年來(lái)點(diǎn)云的法向估計(jì)受到了越來(lái)越多的關(guān)注，點(diǎn)云法向估計(jì)方法可分為局部鄰域擬合法和Voronoi/Dalaunay方法兩類。局部鄰域擬合法由文獻(xiàn)[5]首次提出，此方法也稱為主成分分析(Principal Component Analysis,PCA)法向估計(jì)法。為了更準(zhǔn)確地估計(jì)點(diǎn)云法向，文獻(xiàn)[6]利用代數(shù)球擬合鄰域點(diǎn)來(lái)估計(jì)法向；文獻(xiàn)[7]通過(guò)對(duì)當(dāng)前點(diǎn)的鄰域賦予高斯權(quán)重，使得與當(dāng)前點(diǎn)距離越近的鄰域點(diǎn)對(duì)法向量作用越大，越遠(yuǎn)的點(diǎn)作用越??；文獻(xiàn)[8]使用統(tǒng)計(jì)學(xué)中的集成技術(shù)改進(jìn)PCA方法的魯棒性。以上這些改進(jìn)方法雖然一定程度上改善了點(diǎn)云的法向估計(jì)結(jié)果，但是PCA方法實(shí)際上是一種低通濾波的方法，特征點(diǎn)處的法向被平滑處理了。為了能夠準(zhǔn)確估計(jì)尖銳曲面的法向，學(xué)者們做了大量研究[9-16]，文獻(xiàn)[14]首次提出基于Voronoi/Delaunay方法，當(dāng)點(diǎn)云中不含噪聲或者噪聲較少時(shí)Voronoi圖對(duì)點(diǎn)云法向估計(jì)效果較好。文獻(xiàn)[15]將Voronoi單元格極點(diǎn)擴(kuò)展到大Delaunay球，來(lái)估計(jì)點(diǎn)云法向。文獻(xiàn)[16]將回歸方法和Voronoi方法相結(jié)合，以獲得更穩(wěn)定的結(jié)果。然而以上幾種基于Voronoi/Delaunay方法均不能很好地估計(jì)尖銳特征曲面的法向。

針對(duì)以上問(wèn)題，本研究提出一種鄰域法向迭代加權(quán)的點(diǎn)云法向估計(jì)法，可以在點(diǎn)云處理時(shí)保留曲面的尖銳特征，相比于其他特征曲面法向估計(jì)法，所提出的方法估計(jì)的法向誤差更小、速度更快、耗時(shí)更少。

2　法向估計(jì)

假設(shè)點(diǎn)云的采樣曲面處處光滑，任何點(diǎn)的局部鄰域均可以用平面進(jìn)行擬合，給定點(diǎn)集X={x1,x2,…,xt}，其中t為點(diǎn)云總數(shù)，點(diǎn)xi的k鄰域表示為Nb(xi)，其中Nb為鄰域。對(duì)任意一點(diǎn)xi，用其k鄰域擬合的最小二乘平面表示為：

(1)

式中：n為平面Pl的法向量，須滿足‖n‖2=1；d為鄰域點(diǎn)到擬合平面的距離。式(1)可以轉(zhuǎn)化為對(duì)中半正定協(xié)方差矩陣C進(jìn)行特征值分解，C最小特征值的特征向量可被當(dāng)作xi的法向量，這即是PCA方法。

(2)

C可以分解為3個(gè)特征向量v2，v1和v0，3個(gè)特征向量對(duì)應(yīng)的特征值分別是λ2，λ1和λ0，其中λ2≥λ1≥λ0。最小特征值對(duì)應(yīng)的特征向量為平面的法向量，即n=v0。若曲面處處光滑，則PCA方法能快速準(zhǔn)確地估計(jì)點(diǎn)云法向，然而當(dāng)曲面包含尖銳特征時(shí)，在特征點(diǎn)處，由于用來(lái)擬合平面的k鄰域點(diǎn)位于多個(gè)曲面上，則擬合平面被平滑。

文獻(xiàn)[7]通過(guò)對(duì)當(dāng)前點(diǎn)的鄰域賦予高斯權(quán)重，使距當(dāng)前點(diǎn)越近的鄰域點(diǎn)對(duì)擬合平面的作用越大，距離越遠(yuǎn)作用越小，并將式(1)改寫(xiě)為：

(3)

文獻(xiàn)[9]在文獻(xiàn)[7]的基礎(chǔ)上疊加了殘差因子，又將式(3)改進(jìn)為：

Pl(n,d)=argmin∑ρ(d+(x-xi)Tn)ωd(xi),

(4)

(5)

(6)

式中u=∑ωd(xi)ωr(ri)(x-xi)/∑ωd(xi)ωr(ri)。

式(5)是通過(guò)對(duì)鄰域點(diǎn)迭代加權(quán)來(lái)逐步減小不在同一曲面的鄰域點(diǎn)對(duì)擬合平面的作用來(lái)求解法向的，相對(duì)于文獻(xiàn)[7]，式(5)得到的法向在特征點(diǎn)處改善明顯。文獻(xiàn)[10]提出了自適應(yīng)特征保留法向估計(jì)法，其主要在式(5)的基礎(chǔ)上加入了法向偏差，當(dāng)前點(diǎn)的法向與鄰域點(diǎn)的偏差越大，該鄰域點(diǎn)對(duì)當(dāng)前點(diǎn)擬合的平面作用越小，其改進(jìn)為：

(7)

式(7)中有σd，σr和σn3個(gè)帶寬，但是都無(wú)須用戶指定，均能隨著曲面的變化自適應(yīng)更新。

文獻(xiàn)[9-10]估計(jì)法向都是通過(guò)對(duì)鄰域點(diǎn)迭代加權(quán)來(lái)擬合平面的，減小不在同一連續(xù)曲面鄰域點(diǎn)的作用，使得最終用來(lái)擬合平面的鄰域具有各項(xiàng)異性。然而每一次迭代的過(guò)程中都需擬合平面、求解協(xié)方差的特征向量、鄰域點(diǎn)到擬合平面的距離，迭代次數(shù)越大計(jì)算越耗時(shí)。文獻(xiàn)[10]引入了法向偏差作為擬合平面的權(quán)重因子，鄰域點(diǎn)的法向與當(dāng)前點(diǎn)的法向夾角越小，該鄰域點(diǎn)對(duì)當(dāng)前點(diǎn)的作用越大，反之越小。當(dāng)鄰域點(diǎn)的法向夾角大于給定帶寬時(shí)，該鄰域點(diǎn)被當(dāng)做外點(diǎn)丟棄。在平坦區(qū)域，一般方法都能夠準(zhǔn)確估計(jì)出點(diǎn)云法向，只是在特征區(qū)域估計(jì)的法矢被平滑，此時(shí)可以用平坦區(qū)域獲得的準(zhǔn)確法矢來(lái)修正特征點(diǎn)的法矢。對(duì)于特征區(qū)域的點(diǎn)，其鄰域位于一個(gè)或者多個(gè)曲面上，同一曲面上的法矢相似，不同曲面上點(diǎn)的法矢偏差較大，而且曲面越尖銳，不同曲面上對(duì)應(yīng)點(diǎn)的法向夾角越大；因此，這里采用鄰域中準(zhǔn)確法矢迭代加權(quán)對(duì)不準(zhǔn)確法矢進(jìn)行修正。與當(dāng)前點(diǎn)法矢夾角越大的鄰域點(diǎn)對(duì)當(dāng)前點(diǎn)的法矢修正作用越小，而且距離越遠(yuǎn)的點(diǎn)作用也越小。經(jīng)過(guò)多次迭代，逐步修正不正確的法矢，本文法矢估計(jì)法可表示為：

(8)

式中σd和σn分別為距離帶寬和法向偏差帶寬。

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

采用C++語(yǔ)言在Microsoft visual studio 2008上實(shí)現(xiàn)法向估計(jì)算法，并且調(diào)用OpenGL庫(kù)函數(shù)顯示點(diǎn)云，實(shí)驗(yàn)所用的計(jì)算機(jī)配置為Intel Core 2.30 GHz CPU，1.19 GB內(nèi)存。為了驗(yàn)證算法的有效性，測(cè)試估計(jì)法矢與標(biāo)準(zhǔn)法矢偏差(估計(jì)誤差)，將估計(jì)的法矢作為點(diǎn)云處理的輸入來(lái)驗(yàn)證特征保留效果。將本文方法與文獻(xiàn)[5]的PCA方法、文獻(xiàn)[10]的自適應(yīng)迭代鄰域擬合法、文獻(xiàn)[11]的魯棒法向估計(jì)法進(jìn)行定量和定性比較。

3.1參數(shù)選擇

本文算法有5個(gè)參數(shù)，分別是PCA方法估計(jì)初始化法向時(shí)的k鄰域、式(8)中k1鄰域、距離帶寬σd、法向偏差帶寬σn和迭代次數(shù)t。文獻(xiàn)[5]中用PCA方法估計(jì)法向時(shí)擬合平面的k鄰域大小取8～64比較合適，本文取k=16。在平坦區(qū)域，PCA方法能準(zhǔn)確估計(jì)點(diǎn)云法向，在特征點(diǎn)處估計(jì)的法向被平滑。若點(diǎn)xi是特征點(diǎn)，點(diǎn)xi的k1鄰域中有許多點(diǎn)處于平坦區(qū)域，則用平坦區(qū)域的點(diǎn)來(lái)修正特征區(qū)域點(diǎn)的法矢，因此，式(8)中用來(lái)加權(quán)的k1鄰域應(yīng)該大于PCA估計(jì)法向的k鄰域，這里取k1=3k=48。σd表示點(diǎn)xi到其鄰域的歐氏距離帶寬，σd值越大包括的鄰域點(diǎn)越多，為了確保當(dāng)前點(diǎn)的鄰域都在帶寬范圍內(nèi)，σd取點(diǎn)xi到鄰域點(diǎn)的最大距離。σn表示法向偏差帶寬，帶寬內(nèi)的鄰域?qū)Ξ?dāng)前法向的修正作用大，帶寬外的鄰域?qū)i法向的修正作用小，法向偏差越大，作用越小。當(dāng)曲面夾角比較大(或者過(guò)渡面比較平緩)時(shí)，σn應(yīng)該取較小值；當(dāng)曲面的夾角比較尖銳時(shí)σn應(yīng)該取較大值。實(shí)驗(yàn)發(fā)現(xiàn)：對(duì)于過(guò)渡邊比較平滑和尖銳的曲面，帶寬分別取0.2和0.3時(shí)結(jié)果比較理想。實(shí)際物體的曲面包括不同尖銳程度的曲面，σn取全局值難以滿足要求，然而設(shè)定自適應(yīng)帶寬較復(fù)雜，計(jì)算耗時(shí)。對(duì)過(guò)渡邊比較平滑的曲面，若σn取值偏大，或者尖銳曲面的σn取值偏小，則須增加迭代次數(shù)來(lái)補(bǔ)償過(guò)大或過(guò)小帶寬帶來(lái)的不足。當(dāng)曲面比較光滑時(shí)，t取較小值；曲面越尖銳，t越大，實(shí)驗(yàn)發(fā)現(xiàn)對(duì)過(guò)渡邊比較平緩和尖銳的模型，迭代次數(shù)分別為5，10時(shí)，模型為閾值法向基本調(diào)整到最佳狀態(tài)。當(dāng)t增大時(shí)，法向幾乎不再變化，為了提高計(jì)算效率，折衷帶寬值和迭代次數(shù)t將帶寬設(shè)為全局值σn=0.25，最大迭代次數(shù)為t=15。

3.2誤差分析

在設(shè)備研發(fā)方面，2019年我們的目標(biāo)是日日順物流有一樣設(shè)備在全國(guó)是最大的，在智能化設(shè)備有一個(gè)領(lǐng)域是全國(guó)最大的。

為了測(cè)試估計(jì)法矢的準(zhǔn)確性，計(jì)算估計(jì)法向與標(biāo)準(zhǔn)法向的偏差，采用法向偏差均方根(Root Mean Square，RMS)來(lái)表示估計(jì)誤差，RMS表示估計(jì)法向與標(biāo)準(zhǔn)(參考)法向的平均偏移量，RMS值越大，估計(jì)法向的誤差越大，文獻(xiàn)[9-12]均采用RMS來(lái)測(cè)量估計(jì)法向的誤差。

式中：nref，nest分別為單位化的參考法向和估計(jì)法向；|S|為曲面S的點(diǎn)云數(shù)量；τ為閾值，當(dāng)參考法向與估計(jì)法向的點(diǎn)積大于閾值τ時(shí)，認(rèn)為該點(diǎn)的法向與標(biāo)準(zhǔn)法向偏差為90°。文獻(xiàn)[9-12]法向夾角閾值均取為10°，即τ=0.984 8。

因?yàn)閺?fù)雜曲面難以得到標(biāo)準(zhǔn)法向，所以用Matlab合成規(guī)則點(diǎn)云模型(不含噪聲)，根據(jù)點(diǎn)云坐標(biāo)計(jì)算其標(biāo)準(zhǔn)法向。合成模型分別是立方體和圓柱體，兩模型的點(diǎn)云數(shù)量分別為6 147和28 832。立方體模型包含尖銳特征點(diǎn)，如兩平面交叉的邊界特征點(diǎn)和三平面交叉的角點(diǎn)。圓柱體包含的特征點(diǎn)比較平緩，其特征點(diǎn)是上下兩平面和圓柱面的交叉點(diǎn)。為了測(cè)試估計(jì)法向?qū)υ肼暤拿舾行裕瑢?duì)理想模型添加不同程度的噪聲，計(jì)算理想模型及各噪聲模型的RMS。當(dāng)估計(jì)的法向與標(biāo)準(zhǔn)法向偏差大于10°時(shí)稱該點(diǎn)為壞點(diǎn)，4種方法比較結(jié)果如圖1(彩圖見(jiàn)期刊電子版)和圖2(彩圖見(jiàn)期刊電子版)所示，圖中：SSNR為信噪比；紅色點(diǎn)表示壞點(diǎn)。表1所示為兩個(gè)模型的RSM和壞點(diǎn)數(shù)量(Bad Point Number, BPN)。

(a) PCA　(b) 文獻(xiàn)[11]　 (c) 文獻(xiàn)[10]　 (d) 本文方法(a) PCA　(b)Reference　 (c)Reference　 (d) Proposed method　　　[11]　　　[10]圖1　立方體模型的法向估計(jì)結(jié)果Fig.1　Normal estimation results of cube point cloud model

可知，對(duì)于立方體模型，當(dāng)模型不含噪聲時(shí)，文獻(xiàn)[10]和本文方法沒(méi)有壞點(diǎn)，文獻(xiàn)[11]在特征點(diǎn)處有少數(shù)的壞點(diǎn)。當(dāng)SSNR=40 dB時(shí)，本文方法的BPN為0，RSM接近0，文獻(xiàn)[11]和文獻(xiàn)[10]均有少數(shù)壞點(diǎn)，PCA方法的壞點(diǎn)主要是特征點(diǎn)及其周?chē)狞c(diǎn)。當(dāng)數(shù)據(jù)被噪聲嚴(yán)重干擾時(shí)(SSNR=30 dB)，如圖1中第三行所示，立方體已經(jīng)嚴(yán)重失真，角點(diǎn)和邊界點(diǎn)模糊。PCA方法估計(jì)法向有一半是壞點(diǎn)(BPN為3 064，詳見(jiàn)表1)，其次是文獻(xiàn)[11]，本文方法得到BPN和RSM最小，其壞點(diǎn)主要分布在角點(diǎn)周?chē)?duì)圓柱體模型，本文方法得到的BPN和RSM比其他方法的都小，幾種方法結(jié)果比較見(jiàn)圖2和表1。

為了清楚比較各壞點(diǎn)的法向與標(biāo)準(zhǔn)法向的偏差，統(tǒng)計(jì)立方體和圓柱體模型在SSNR=30 dB時(shí)不同偏差角度下壞點(diǎn)數(shù)量，稱之為法向偏差直方圖，結(jié)果如圖3(彩圖見(jiàn)期刊電子版)所示。對(duì)于立方體模型，在法向偏差為[10°，20°]區(qū)域，PCA，文獻(xiàn)[11]，文獻(xiàn)[10]及本文方法分別有65.5%，75.4%，83%和97.7%的壞點(diǎn)，在法向偏差為[20°, 30°]區(qū)域，分別有14.5%，8.4%，9.2%和2.3%的壞點(diǎn)。同樣，對(duì)圓柱體模型，在角度偏差為[10°, 20°]區(qū)域，本文方法的壞點(diǎn)數(shù)的比例最大。本文方法估計(jì)的法向其壞點(diǎn)主要分布在低法向偏差區(qū)域，即估計(jì)得到的法向更準(zhǔn)確。

(a) PCA　(b)文獻(xiàn)[11]　 (c) 文獻(xiàn)[10]　 (d) 本文(a) PCA　(b)Reference　(c)Reference　(d) Proposed method　　　[11]　　　[10]圖2　圓柱體模型法向估計(jì)結(jié)果Fig.2　Normal estimation results of cylinder point cloud model

模型SSNR/dB　　　PCA　　　文獻(xiàn)[11]　　文獻(xiàn)[10]　　　本文　BPNRMSBPNRMSBPNRMSBPNRMS立方體無(wú)噪10980．6642230．11660000．03104011120．6702451510270．123500．05003030641．111911670．69007390．55164550．4376圓柱體無(wú)噪2490．3321340．0654140．057840．03094014310．36151780．1329760．093670．04243084600．872340630．604932190．541624050．4730

(a) 立方體模型壞點(diǎn)直方圖 　　　　　(b)圓柱體模型壞點(diǎn)直方圖(a) Histogram of BPN for cube model 　　　 (b) Histogram of BPN for cylinder model圖3　模型中壞點(diǎn)直方圖分布Fig.3　Histogram of BPN for point cloud models

3.3法矢可視化和應(yīng)用

3.3.1法矢可視化

對(duì)兩個(gè)經(jīng)典模型(八面體和Fandisk模型，其中八面體模型添加了SSNR=40 dB的噪聲)進(jìn)行法向可視化，如圖4～6(彩圖見(jiàn)期刊電子版)所示，紅色線表示一致的法矢方向，八面體模型的特征點(diǎn)包括多個(gè)平面交接的角點(diǎn)和兩個(gè)平面交接的過(guò)渡邊界點(diǎn)，角點(diǎn)處的曲面比較尖銳，過(guò)渡邊則相對(duì)平緩。Fandisk模型由平面、球面、圓柱面等基面組成，其過(guò)渡邊有尖銳邊和平緩邊等。為了更清楚的顯示模型，將模型三角化加光照顯示，如圖4(a)和5(a)所示。準(zhǔn)確的法向應(yīng)該垂直于點(diǎn)云所在的局部曲面，兩個(gè)不同曲面上的點(diǎn)云法向夾角為兩曲面的夾角，局部區(qū)域同一曲面上的法向接近平行，在兩個(gè)曲面交界的邊界處有清晰的邊界。圖4(d)和(e)以及圖5(d)和(e)的邊界清晰，圖4(c)和圖5(c)有部分特征點(diǎn)的法向誤差大，如角點(diǎn)的法向不垂直于其所在的曲面。圖6(a)為圖5(a)紅色矩形框的區(qū)域的放大圖，圖6(b)～(e)為圖6(a)曲面對(duì)應(yīng)方法估算的法向量。

(a)三角化曲面　(b)PCA　　(c) 文獻(xiàn)[11]　 　　　 (d)文獻(xiàn)[10]　 　　　 (e)本文　　(a) Wraped surface 　　 (b) PCA 　　 　 (c) Reference [11]　 　 (d) Reference[10]　 (e) Proposed method圖4　八面體模型法矢可視化Fig.4　Normal vector visualization of Octahedron point model

(a)三角化曲面　(b)PCA　　　(c) 文獻(xiàn)[11]　 　　　 (d)文獻(xiàn)[10]　 　 (e)本文　　(a) Wraped surface 　　(b) PCA 　　 　(c) Reference [11]　 　 (d) Reference[10]　 (e) Proposed method圖5　Fandisk模型法矢可視化Fig.5　Normal vector visualization of Fandisk point model

(a)放大后的三角化曲面　　(b)PCA　　 (c) 文獻(xiàn)[11]　 　　 (d)文獻(xiàn)[10]　　 (e)本文　　　　(a) Amplified surface　　　(b) PCA 　　 (c) Reference [11]　　 (d) Reference[10]　　 (e) Proposed method 圖6　局部區(qū)域放大后的法矢Fig.6　Amplification and visualization of normal vector

將估計(jì)的法向應(yīng)用到點(diǎn)云處理中，對(duì)噪聲模型進(jìn)行去噪。雙邊濾波去噪法能在去噪的同時(shí)保留曲面的幾何特征，具有特征保留的性質(zhì)，但是獲得準(zhǔn)確的法向是雙邊濾波特征保留的前提，若法向在特征點(diǎn)處被平滑，則雙波濾波后尖銳特征也被平滑，文獻(xiàn)[18]對(duì)經(jīng)典雙邊濾波算法進(jìn)行了改進(jìn)，其特征保留效果更優(yōu)。為了消除其他因素的影響，雙邊濾波算法中除了法向不一樣外，其他參數(shù)值均相同?；诓煌ㄏ虻妮S承模型去噪結(jié)果如圖7所示。PCA估計(jì)的法向在特征點(diǎn)被平滑，從而7(c)中的邊界被平滑，文獻(xiàn)[10]和本文方法估計(jì)的法向在特征點(diǎn)處比較準(zhǔn)確，去噪后可保留清晰的邊界。

圖7　基于不同法向的軸承模型去噪Fig.7　Denoising results of bearing model with different normals

3.4耗時(shí)分析

顯然，PCA方法估計(jì)法矢最簡(jiǎn)單，而且其只對(duì)每個(gè)點(diǎn)的鄰域擬合一次平面、從而耗時(shí)最小。文獻(xiàn)[11]方法需從一個(gè)大鄰域(鄰域大小k=500)中采用隨機(jī)采樣一致法尋找一個(gè)最優(yōu)切平面，計(jì)算非常耗時(shí)。文獻(xiàn)[10]方法在每一次迭代中都需擬合一個(gè)平面，計(jì)算鄰域點(diǎn)到擬合平面的距離，采用層次聚類法估計(jì)特征系數(shù)。本文方法只在迭代初始化時(shí)擬合平面，其后的每一次迭代只對(duì)鄰域點(diǎn)加權(quán)，且迭代次數(shù)與文獻(xiàn)[10]相同，相比文獻(xiàn)[10]和文獻(xiàn)[11]，本文方法更簡(jiǎn)單，耗時(shí)更小。4種方法對(duì)以上模型的法向估計(jì)耗時(shí)如表2所示，可見(jiàn)PCA方法最快，本文方法次之，文獻(xiàn)[11]最慢。

表2　4種方法耗時(shí)比較

4　結(jié)　論

本文對(duì)尖銳特征曲面的法向估計(jì)進(jìn)行了研究。用PCA方法粗估計(jì)曲面法向?？紤]到PCA方法估計(jì)的法矢在平坦區(qū)域比較準(zhǔn)確，在特征區(qū)域被平滑，又采用鄰域點(diǎn)中的正確法矢來(lái)修正特征區(qū)域不準(zhǔn)確的法矢。因此，對(duì)鄰域法向加權(quán)，其權(quán)重包括距離權(quán)重和法向偏差權(quán)重，使距當(dāng)前點(diǎn)越遠(yuǎn)的鄰域點(diǎn)對(duì)當(dāng)前法向修正作用越小，反之越大，與當(dāng)前點(diǎn)法向偏差越小的鄰域點(diǎn)的作用越大，修正的法矢是鄰域法矢的迭代加權(quán)和。實(shí)驗(yàn)結(jié)果表明： 本文方法能夠準(zhǔn)確估計(jì)尖銳特征曲面的法向，最小誤差等于零，估計(jì)的法向應(yīng)用到點(diǎn)云處理時(shí)能很好地保留曲面幾何特征，相比于其他特征曲面法向估計(jì)法，本文方法簡(jiǎn)單且快速。然而本文方法的法向偏差帶寬是根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)設(shè)定的，將來(lái)需進(jìn)一步研究自適應(yīng)帶寬以減少迭代次數(shù)來(lái)提高算法的執(zhí)行效率。

[1]吳祿慎,史皓良,陳華偉. 基于特征信息分類的三維點(diǎn)數(shù)據(jù)去噪[J]. 光學(xué) 精密工程, 2016, 24(6): 1465-1473.

WU L SH, SHI H L, CHEN H W. Denoising of three-dimensional point cloud based on classfication of feature information [J].Opt.PrecisionEng., 2016, 24(6): 1465-1473.(in Chinese)

[2]WANG Y H, HAO W, NING X J,etal.. Automatic segmentation of urban point clouds based on the Gaussian map[J].PhotogrammetricRecord, 2013, 28(144): 342-361.

[3]袁小翠, 吳祿慎, 陳華偉. 特征保持點(diǎn)云數(shù)據(jù)精簡(jiǎn)[J]. 光學(xué) 精密工程, 2015, 23(9): 2666-2676.

YUAN X C, WU L SH, CHEN H W. Feature preserving point cloud simplification [J].Opt.PrecisionEng., 2015, 23(9): 2666-2676.(in Chinese)

[4]TANG P, HUBER D, AKINCI B,etal.. Automatic reconstruction of as-built building information models from laser-scanned point clouds: A review of related techniques [J].AutomationinConstruction, 2010, 19(7): 829-843.

[5]HOPPE H, De ROSE T, DUCHAMP T,etal.. Surface reconstruction from Unorganized Points [J].ComputerGraphics, 1992, 26(2): 71-78.

[6]GUENNEBAUD G, GROSS M,ZURICH E. Algebraic point set surfaces [J].ACMTransactionsonGraphics,2007, 26(3):23.

[7]PAULY M, GROSS M, KOBBELT L P. Efficient simplification of point-sampled surfaces [C].IEEEVisualization2002,WashingtonDC:IEEEComputerSocietyPress, 2002:163-170.

[8]YOON M, LEE Y, LEE S,etal.. Surface and normal ensembles for surface reconstruction[J].Computer-AidedDesign, 2007, 39(5): 408-420.

[9]MEDEROS B, VELHO L, FIGUIREDO L H. Robust smoothing of noisy point clouds [C].ProceedingsoftheSIAMConferenceonGeometricDesignandComputing,Seattle:SIAM, 2003: 405-416.

[10]WANG Y, FENG H Y, DELORME F,etal.. An adaptive normal estimation method for scanned point clouds with sharp features [J].Computer-AidedDesign, 2013, 45(11): 1333-1348.

[11]LI B, SCHNABEL R, KLEIN R,etal.. Robust normal estimation for point clouds with sharp features [J].Computers&Graphics, 2010, 34(2): 94-106.

[12]蘇志勛, 栗志揚(yáng), 王小超. 基于法向修正及中值濾波的點(diǎn)云平滑[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2010, 22(11): 1892-1898.

SU ZH X, LI ZH Y, WANG X CH. Denoising of point-sampled model based on norm al mollification and median filtering [J].JournalofComputer-AidedDesign&ComputerGraphics, 2010, 22(11): 1892-1898.(in Chinese)

[13]ZHANG J, CAO J, LIU X,etal.. Point cloud normal estimation via low-rank subspace clustering[J].Computers&Graphics, 2013, 37(6): 697-706.

[14]AMENTA N, BERN M. Surface reconstruction by Voronoi filtering [J].Discrete&ComputationalGeometry, 1999, 22(4): 481-504.

[15]DEY T K, GOSWAMI S. Provable surface reconstruction from noisy samples [C].IEEESymposiumonParallelandLarge-DataVisualizationandGraphics,Piscataway:IEEE, 2001: 19-27.

[16]ALLIEZ P, COHEN-STEINER D, TONG Y,etal.. Voronoi-based variational reconstruction of unoriented point sets [C].Proceedingsofthe5thEurographicsSymposiumonGeometryprocessing,Geneve:Wiley, 2007: 39-48.

[17]HUBER P J.RobustStatistics[M]. Berlin: Springer, 2011.

[18]ZHENG Y, FU H, AU O C,etal.. Bilateral normal filtering for mesh denoising[J].IEEETransactionsonVisualizationandComputerGraphics, 2011, 17(10): 1521-1530.

袁小翠(1988-)，女，江西撫州人，博士，講師，主要研究方向?yàn)閳D像處理與逆向工程。E-mail：yuanxc2012@163.com

吳祿慎(1953-)，男，江西樂(lè)平人，碩士，教授，博士生導(dǎo)師，1978年于北京航空航天大學(xué)獲得學(xué)士學(xué)位，1990年于清華大學(xué)獲得碩士學(xué)位，主要從事面外“moire”法、三維光學(xué)圖像測(cè)量與逆向工程的研究。E-mail：wulushen@163.com

(版權(quán)所有未經(jīng)許可不得轉(zhuǎn)載)

Normal estimation of scattered point cloud with sharp feature

YUAN Xiao-cui1*,WU Lu-shen2,CHEN Hua-wei2

(1.Jiangxi Province Key Laboratory of Precision Drive & Control,NanchangInstituteofTechnology,Nanchang330099,China;2.SchoolofMechanicalandElectricalEngineering,NanchangUniversity,Nanchang330031,China)*Correspondingauthor,E-mail:yuanxc2012@163.com

A novel method was proposed to estimate the normal for a scattered point cloud with sharp features to overcome the shortcomings that existing methods are unable to reliably estimate the normal of point cloud model and lead to the smoothed sharp features. With proposed method, the normal of point cloud was estimated with principal component analysis method. Then, different values were weighted on neighborhood normals according to spatial distance and normal distance of current points of the neighborhood, and the revised or current normals were updated by the sum of weighted neighborhood normal. Finally, the average deviation between standard normal and estimated normal was measured and the accuracy of estimated normal was evaluated. The estimated normal was applied to point cloud processing to verify the feature-preserving property. The proposed method was validated. The results demonstrate that proposed method accurately estimates the normal for data with noise and the least average deviation is close to 0. Moreover, the method has good robustness to the niose, and it keeps the original geometry well when the normal is used as input of the point cloud processing. Comparing with other sharp feature preserving normal estimation methods, the proposed method shows smaller average deviation, higher processing speeds and less computation time.

scattered point cloud；sharp feature; normal estimation; reverse engineering; feature preserving; principal component analysis

2016-06-15；

2016-07-19.

國(guó)家自然科學(xué)基金資助項(xiàng)目(No.51365037,No.51065021)

1004-924X(2016)10-2581-08

TP391.7

Adoi:10.3788/OPE.20162410.2581