薛萍 姚娟 鄒學(xué)洲 王宏民
摘要:逆向工程數(shù)據(jù)采集點云數(shù)據(jù)的離群點和噪聲點的存在,直接影響數(shù)據(jù)的多視圖拼合,特征提取,數(shù)據(jù)精簡以及曲面重構(gòu)的質(zhì)量。在對雙邊濾波和三邊濾波算法的研究的基礎(chǔ)上,提出了一種基于法矢修正的點云數(shù)據(jù)去噪平滑的算法。對于噪聲點通過加權(quán)協(xié)方差矩陣估算點云鄰域內(nèi)幾何特征,將具有相似幾何特征的點限制在法向量相似的區(qū)域,在相似鄰域內(nèi)的采樣點法矢和位置分別進行保特征的三邊濾波。改進后的算法能夠有效地濾出點云數(shù)據(jù)中的離群點和噪聲點,同時保證了點云數(shù)據(jù)的尖銳及邊緣特征,取得良好的去噪效果。
關(guān)鍵詞:
點云數(shù)據(jù);去噪平滑;加權(quán)協(xié)方差矩陣;三邊濾波;法矢修正
DOI:10.15938/j.jhust.2018.05.015
中圖分類號: TP3919
文獻標(biāo)志碼: A
文章編號: 1007-2683(2018)05-0086-06
Abstract:The presence of outliers and noise points in the cloud data of the reverse engineering data collection directly affects the multviews combination of the data, feature extraction, data reduction and the quality of surface reconstruction Based on the research of bilateral filtering and trilateration filtering algorithm, this paper presents an algorithm of denoising and smoothing of point cloud data based on normal vector correction Firstly, the local neighborhood of the point cloud data is constructed, and the noise points of the scattered data collected by the data acquisition system are classified and processed For outliers in the point cloud data, mathematical statistics analysis is used to filter out the points whose KNN is lower than the threshold The points with similar geometric characteristics are restricted to the regions where the normal vectors are similar, and the normal vectors and positions of the samples in the similar neighborhoods are triangulated The improved algorithm can effectively filter the outliers and noise points in the point cloud data, and ensure the sharp and edge features of the point cloud data and obtain good denoising effect
Keywords:point cloud data; denoising smoothing; weighted covariance matrix; trilateration filtering; normal vector correction
0引言
逆向工程中對實體表面的數(shù)據(jù)獲取[1]方式分為接觸式測量和非接觸式測量。隨著三維測量技術(shù)的不斷發(fā)展和完善,各種各樣的三維測量設(shè)備很容易對物體表面的數(shù)據(jù)進行采集,同時得到的測量數(shù)據(jù)不可避免的存在著噪聲信號,這些測量的噪聲信號受到測量物體的形狀,物體的材料,光線或者其他環(huán)境因素的影響。這些測量誤差統(tǒng)稱為噪聲點,與此同時點云數(shù)據(jù)[2]中也存在離主體點云較遠的離群點。由于點云數(shù)據(jù)的離群點和噪聲點的存在,直接影響數(shù)據(jù)的多視圖拼合,特征提取,數(shù)據(jù)精簡以及曲面重構(gòu)的質(zhì)量,因此需要對噪聲進行濾波處理。在濾除噪聲點的同時要注意濾波過度的問題,保持點云的特征點不被大量濾除,以免影響曲面重構(gòu)[3]后模型的質(zhì)量,所以點云數(shù)據(jù)的去噪和平滑顯得尤為重要。首先對噪聲的來源和產(chǎn)生噪聲的原因進行分析,有利于對噪聲的研究,發(fā)現(xiàn)噪聲點的特征,然后根據(jù)噪聲和有效點云的區(qū)別進行有效的點云去噪。
目前點云數(shù)據(jù)去噪的方法主要有:一是將散亂點云數(shù)據(jù)網(wǎng)格化,對網(wǎng)格數(shù)據(jù)進行去噪處理;二是對散亂點云數(shù)據(jù)直接去噪處理。拉普拉斯(Laplace)去噪[4]是一種常用而且算法實現(xiàn)又簡單的散亂點云數(shù)據(jù)去噪方法,該算法首先對點云數(shù)據(jù)中的每個數(shù)據(jù)點進行拉普拉斯算子,并將其進行多次迭代,將噪聲點調(diào)整到附近鄰域位置,從而達到去噪光順的目的。但是這種方法存在很大的問題,就是經(jīng)過多次迭代后對于網(wǎng)格分布不均勻的點云區(qū)域會產(chǎn)生原來網(wǎng)格的大面積變形,嚴(yán)重影響曲面重構(gòu)的質(zhì)量。雙邊濾波去噪算法是由圖像處理算法雙邊濾波算法發(fā)展而來的點云數(shù)據(jù)去噪算法,該算法能較好地保留數(shù)據(jù)的局部特征,但是也存在一定的問題,針對較大的噪聲的處理上就會出現(xiàn)過
光順的現(xiàn)象,使重構(gòu)后的模型顯得模糊失真。本文所述算法的思想是,采用數(shù)理統(tǒng)計的方法,濾出點云數(shù)據(jù)中的離群點,去除K近鄰點低于設(shè)定閾值的點,通過加權(quán)協(xié)方差矩陣,分析估算點云鄰域內(nèi)的幾何特征[5],將具有相似幾何特征的點限制在法向量相似的區(qū)域,在相似鄰域內(nèi)的采樣點法矢和位置分別進行保特征的三邊濾波。
1點云數(shù)據(jù)去噪平滑方法
11八叉樹法空間劃分及K鄰域數(shù)據(jù)搜索
建立點云數(shù)據(jù)的最小包圍立方體,該最小立方體稱為八叉樹[6]的根節(jié)點,然后把根節(jié)點劃分為8個邊長相同的子立方體,被劃分的8個子立方體稱為根節(jié)點的子節(jié)點,包含點云數(shù)據(jù)的子節(jié)點稱為“黑體”,不包含點云數(shù)據(jù)的子節(jié)點稱為“白體”。當(dāng)“黑體”的邊長大于預(yù)先設(shè)定的最小劃分邊長Lmin時,以此類推對子節(jié)點進行劃分,直至被劃分的子立方體的邊長小于或等于預(yù)先設(shè)定的最小劃分邊長Lmin,劃分結(jié)束。
對點云數(shù)據(jù)進行八叉樹劃分后,利用0-7的八進制對子立方體進行數(shù)據(jù)編碼[7],每個子立方體都可以用一個唯一的八進制碼唯一表示:
Q=qn-18n-1+qn-28n-2+…+qk8k+…+q181+q080(1)
式(1)中qi為八進制數(shù)編碼,qi∈[0,7],i∈[0,n-1]。
其中qi/22表示qi/2取整,qi/42表示qi/4取整,n表示分層數(shù)。
由八叉樹法空間劃分規(guī)則和子節(jié)點編碼方式可以知道,當(dāng)給定子節(jié)點在空間中的坐標(biāo)位置,可以求出其節(jié)點編碼,同樣知道子節(jié)點的編碼,可以求出其在根節(jié)點中的位置坐標(biāo)。
12離群點濾除
對點云數(shù)據(jù)離群點的濾除在點云數(shù)據(jù)處理中是十分重要的,將直接影響到點云分割、特征提取、精簡等一系列的后續(xù)處理過程。
設(shè)點云的集合P={pi|i∈1,2…,pi∈R3},通過建立點云的拓撲關(guān)系對點云集合中的任意一個點pi,其K鄰域集合pij={pi1,pi2,pi3,…},令其為Nb(pi),對點云數(shù)據(jù)中的離群點采用數(shù)理統(tǒng)計方法濾出,即基于數(shù)據(jù)點K鄰域的距離特征濾出離群點。對點云數(shù)據(jù)中的任意采樣點pi計算K鄰域[8]的平均距離并記為di,然后對整個點云數(shù)據(jù)集合P中的點云計算全局距離平均值uN和標(biāo)準(zhǔn)方差σN,K鄰域的平均距離在全局距離之外的點視為離群點,并把該點從點云數(shù)據(jù)中濾除。濾出離群點后的點云數(shù)據(jù)可用集合表示為:
P*={p*i∈P|(uN-ασN)≤di*≤(uN+ασN)}
濾除離群點的過程如下:
1)八叉樹空間拓撲關(guān)系的建立及對數(shù)據(jù)點云中的任意數(shù)據(jù)點pi的K鄰域搜索,K鄰域點集合Nb(pi);
2)對于點云數(shù)據(jù)中的任意采樣點pi計算K鄰域的平均距離并記為di
di=1k∑kj=1‖pi-pij‖(5)
3)對于整個點云集合
P={pi|i∈1,2…,pi∈R3}計算全局距離平均值uN和標(biāo)準(zhǔn)方差σN;
uN=1N∑Ni=1di,σN2=1N∑Ni=1(di-uN)2(6)
4)通過K鄰域平均距離與uN±ασN的比較,其中α為標(biāo)準(zhǔn)差的倍數(shù),滿足di
13法向量估計
濾除后的點云數(shù)據(jù)[10]就是不包含離群點的點云數(shù)據(jù),然后就可以進行去噪平滑的算法,采用加權(quán)協(xié)方差矩陣的方法進行幾何特征的計算。點云集合中的任意一個點pi,通過K近鄰搜索得到其K鄰域點數(shù)據(jù)集合,通過最小二乘法擬合平面L,平面L滿足pi的鄰近點到該平面的距離之和值最小。這樣的平面L可用數(shù)學(xué)公式表示為:
L(n,d)=arg min(n,d)∑ki=1(n·pi-d)2(7)
式(7)中,n表示pi的K近鄰點擬合平面的法向量,d表示坐標(biāo)原點到L(n,d)的距離。通過分析式(7)得出L經(jīng)過數(shù)據(jù)點K近鄰點的質(zhì)心pi,構(gòu)造協(xié)方差矩陣C:由L的公式可以通過分析得出L經(jīng)過數(shù)據(jù)點的K近鄰點的質(zhì)心pi,構(gòu)造協(xié)方差矩陣C:
C=1k∑kj=1(pij-pi)·(pij-pi)T,
C·el=λl·el l∈{0,1,12}(8)
式(8)中k為通過K近鄰搜索得到其K鄰域點數(shù)據(jù)個數(shù),pi是L經(jīng)過數(shù)據(jù)點的K近鄰點的質(zhì)心,λl為協(xié)方差矩陣的特征值,el為特征值相對應(yīng)的特征向量。設(shè)特征值λ0<λ1<λ2,pi處的法向量可以用特征向量的值來表示,即ni=el。因此可以用協(xié)方差矩陣的特征值來估計采樣點的曲面尖銳程度。由Pauly定義的曲面可由點pi處的曲率表示為:
ρi=λ0λ0+λ1+λ2(9)
式(9)中,由于λ0<λ1<λ2,因此0<ρi<1/3,通過這樣的方法,很容易估算出點云中任意一點pi處的曲率,但是對于尖銳特征區(qū)域的點云數(shù)據(jù),這樣的估算方法顯得不那么準(zhǔn)確,可通過加權(quán)來改善。
14采樣點去噪平滑
設(shè)平滑采樣點后的坐標(biāo)的位置為pi′,可表示為:
pi′=pi+ni′f2(pi)∑pij∈Nb(pi)
G3=e-
0ni′·nij′ 式(11)中σ3是一個鄰域點法相與采樣點法相之差對采樣點的影響因子,Ti′為法相角度閾值。G3是一個與采樣點、采樣點鄰域內(nèi)點的法向量、σ3相關(guān)的特征保持權(quán)重函數(shù)。由式(11)可知,G3反映了向量pi-pij在ni上的投影長度,進一步地反映了采樣點在其鄰域的切平面的收斂性。G3越小,說明近鄰點集中與切平面存在,這樣的設(shè)定是為了保持這些點對采樣點特征的影響較大。對G3這樣調(diào)整能夠使采樣點的噪聲[11]偏移限制在法向投影的可控范圍內(nèi),即鄰域點法相投影的最大投影距離和最小投影距離之間,不引入新的噪聲點。 2對初始法向量的改進和修正 21法向量估計的改進 通過在協(xié)方差矩陣中添加加權(quán)值,改進后的協(xié)方差矩陣可表示為:
C=1k∑kj=1(pij-pi)·(pij-pi)Tφ(‖pij-pi‖/r)(12)
式(12)中φ表示協(xié)方差函數(shù)的權(quán)重函數(shù),r表示pi的K鄰域數(shù)據(jù)的最小包圍球的半徑。上述協(xié)方差矩陣考慮了近鄰點的距離對采樣點特征的影響[12],但是在對法向量的計算上并不能夠保尖銳特征,需要對協(xié)方差矩陣做進一步的改進,調(diào)整緊鄰點對采樣點的影響。改進后的加權(quán)協(xié)方差矩陣:
C=1k∑kj=1εi(pij-pi)·(pij-pi)T(13)
假設(shè)采樣點pi到最小二乘法擬合平面L的最大距離為dmax,K鄰域搜索的近鄰點pij到L的距離為dij,若dij
這種加權(quán)函數(shù)的設(shè)定,更加能夠反映鄰域內(nèi)的點對采樣點的影響,距離小于dmax的采樣點對采樣點的影響較大,設(shè)置較大的權(quán)重函數(shù),當(dāng)采樣點距離大于dmax時,應(yīng)用較小的權(quán)值函數(shù),這樣就能夠減小遠距離鄰域點對采樣點的影響,抑制噪聲,保留幾何特征。
22法矢修正
通過對加權(quán)協(xié)方差矩陣的權(quán)重因子設(shè)定不同的權(quán)值函數(shù)可以抑制一定的噪聲,但是當(dāng)點云數(shù)據(jù)中的噪聲較大時,初始法向量的估計[13]就難以滿足要求,因此需要對法矢進一步的修正??紤]雙邊濾波算法能夠在一定的程度上保持特征,但這種特征的保持只考慮了空間域和頻域特性,也會存在過光順的問題。綜合考慮散亂點云數(shù)據(jù)的空間特性、法向量和曲率的三種特性,對初始法向量進行修正,得到保特征的點云數(shù)據(jù)。
對于數(shù)據(jù)點云pi,其中包含采樣點的空間位置坐標(biāo)(xi,yi,zi),數(shù)據(jù)點的采樣曲率hi,法向量ni。設(shè)修正后的法向量為ni′,法向量的修正公式:
ni′=ni+1f1(pi)∑pij∈Nb(pi)‖ni-nij‖G1G2(1+hi)(14)
G1=e-‖ni-nij‖2/2σ21(15)
G2=e-‖ni-nij‖2/2σ22,ni·nij>Ti′
0,ni·nij hi=(ρi-ρmax)/(ρmax-ρmin)(17) 式中σ1表示K近鄰點對采樣點法向量的影響因子,σ2表示K鄰域點法向量平均值與當(dāng)前的采樣點的法向量的差值對采樣點的影響因子,σ2可以表示為σ2=α(max 對于法矢修正采樣點的去噪能夠保持采樣點的幾何特征[14],但也可能存在降噪點漂移,需要對降噪點進行穩(wěn)定。通過位置坐標(biāo)因子G1、法相投影因子G3和曲率hi對鄰域內(nèi)數(shù)據(jù)點進行濾波,這樣就能夠?qū)⒉蓸狱c位置限定在法向量和曲率近似的空間位置內(nèi),可以有效地避免降噪點的漂移,沿著新的法相調(diào)整降噪點的位置。 3算法流程及實驗結(jié)果分析 31算法流程 本文同時考慮了采樣點與K個緊鄰點間的局部平均距離與整個點云采樣點間全局平均距離做比較,對離群點有效的濾除,同時又能夠保留數(shù)據(jù)特征。濾除離群點后的點云數(shù)據(jù)通過加權(quán)協(xié)方差矩陣的方法進行幾何特征的計算,估算出法向量和曲率,通過自適應(yīng)鄰域?qū)⑧徲螯c限制在法向量最相似的區(qū)域,然后在鄰域內(nèi)對數(shù)據(jù)點進行法向量,曲率和坐標(biāo)為特征的三邊濾波因子的濾波。基于法矢修正的點云數(shù)據(jù)去噪平滑算法的流程圖如圖2所示: 算法的過程如下: 1)點云讀入,拓撲劃分。點云數(shù)據(jù)讀入,采用八叉樹法對點云數(shù)據(jù)空間劃分,直至劃分的子節(jié)點不包含數(shù)據(jù)點或者子節(jié)點立方體的邊長小于最小劃分邊長Lmin。 2)K鄰域搜索。對八叉樹劃分的子節(jié)點進行數(shù)據(jù)編碼,計算數(shù)據(jù)點在子節(jié)點內(nèi)到臨近點的歐式距離,計算點的K鄰域,擴大搜索范圍到相鄰的子節(jié)點至完成搜索。 3)離群點去除。點云數(shù)據(jù)中的離群點濾出,采用數(shù)理統(tǒng)計分析技術(shù)濾除K近鄰點低于設(shè)定閾值的點。 4)初始法向量和曲率的估計。通過加權(quán)協(xié)方差矩陣的方法進行幾何特征的計算,估算出法向量和曲率。 5)法矢修正和平滑。以空間位置坐標(biāo),曲率以及法向量為三邊濾波因子,對采樣點數(shù)據(jù)進行法向量修正,調(diào)整采樣點的位置。法矢修正平滑后的點云數(shù)據(jù)能夠保持點云數(shù)據(jù)的尖銳特征,模型的平滑。 32實驗結(jié)果分析 321離群點濾除結(jié)果分析 通過對點云數(shù)據(jù)建立的拓撲關(guān)系和K鄰域搜索的方法,K鄰域的搜索直接影響到鄰域點的最小二乘法擬合的切平面L(n,d),K值的選取太小,會使搜索時間大大減小,但是不能夠保證光順。當(dāng)K的選擇過大時,K鄰域搜索的時間過長,同時也不能保證光順。通過實驗驗證,K值的大小在15~20之間時能夠有很好的效果,本文選取k=18。在初始法向量的估計過程中點,采樣點pi到最小二乘法擬合平面L的最大距離dmax的選取經(jīng)過多次試驗,把其設(shè)定為K鄰域點到鄰域點擬合平面的距離的平均值。σ1的值取K鄰域的包圍點球體的半徑,σ2的值通過試驗比較控制在01~02之間較好,在這里取015。在角度閾值的選取上,在07~08為最好,本文取075。σ3取采樣點鄰域的標(biāo)準(zhǔn)差。
322去噪平滑實驗分析
對改進后的算法進行實驗分析,圖3(a)為原始的點云數(shù)據(jù),圖3(b)為濾除離群點后的點云數(shù)據(jù),圖3(c)為去除離群點后的點云數(shù)據(jù)曲面[15]重構(gòu)的結(jié)果,圖3(d)為采用本文去噪平滑后的點云曲面重構(gòu)的模型。通過試驗比較可以知道,建立拓撲關(guān)系后的點云數(shù)據(jù)采用數(shù)理統(tǒng)計的離群點的濾除方法能夠有效地濾除噪聲點云數(shù)據(jù)中的離群點。沒有經(jīng)過去噪光順后[16]的點云數(shù)據(jù)曲面重構(gòu)后的模型出現(xiàn)大量的空洞,對于特征變化明顯的區(qū)域顯得更加的突出。離群點濾除后的曲面重構(gòu)模型有效的濾除了離群點,能夠從一定程度上提高點云數(shù)據(jù)的質(zhì)量[17]。
通過試驗的方法來驗證基于法矢修正的點云數(shù)據(jù)去噪平滑算法的濾波效果,與中值濾波算法,雙邊濾波算法和三邊濾波算法進行比較。圖3為經(jīng)過不同的濾波算法后的點云數(shù)據(jù)曲面重構(gòu)[18]的結(jié)果。圖4(a)為原始的點云數(shù)據(jù),圖4(b)為加入噪聲點后重構(gòu)模型,圖4(c)為中值濾波后曲面重構(gòu)模型,圖4(d)雙邊濾波后曲面重構(gòu)模型,圖4(e)為三邊濾波后曲面重構(gòu)模型,圖4(f)為本文算法后曲面重構(gòu)模型。中值濾波使頂點產(chǎn)生漂移,雙邊濾波會產(chǎn)生過光順,三邊濾波能夠取得很好的光順效果,本文的算法是在三邊濾波的基礎(chǔ)上進行的改進算法,能夠?qū)υ肼朁c的位置進行有效的調(diào)整,保留了數(shù)據(jù)點的幾何特征,達到很好的濾波效果。在去噪平滑的時間上,由于算法是建立在點云數(shù)據(jù)的拓撲關(guān)系之上,加快了去噪的運算速度。
4結(jié)論
經(jīng)過法矢修正和位置平滑后重構(gòu)的曲面能夠明顯地改善重構(gòu)曲面中大光順問題,幾何特征變化明顯的區(qū)域重構(gòu)的結(jié)果也能夠突出幾何特征。從以上的比較可以得出基于法矢修正的點云數(shù)據(jù)平滑濾波算法不但能夠?qū)Υ蟮脑肼曅盘枺x群點)有效的濾除,也能夠有效的平滑較小的噪聲點,能夠達到降噪平滑的作用。本文提出的點云數(shù)據(jù)去噪算法中閥值的選取大多采用經(jīng)驗值或?qū)嶒炛?,如何實現(xiàn)各種閥值的自動選取,提高算法的魯棒性是下一步研究的重點和難點。
參 考 文 獻:
[1]FLEISHMAN S, COHENOr D, SILVA CT Robust Moving Leastsquares Fitting with Sharp Features [C]// ACM Transactions on Graphics, 2005, 24(3):544-552
[2]SUN W, BRADLEY C, ZHANG Y F, etal Cloud data modeling employing a unified nonredundant triangular mesh [J]. Computer Aided Design, 2001, 33(2): 183-193
[3]尹婷三維激光掃描數(shù)據(jù)處理技術(shù)的研究[D].武漢:武漢理工大學(xué),2010
[4]李天蘭三維點云數(shù)據(jù)的處理與應(yīng)用[D].昆明:昆明理工大學(xué),2011
[5]張金花,吳思,胡本剛,等基于地面三維激光掃描儀點云數(shù)據(jù)的去噪算法研究[J].測繪與空間地理信息,2016(3):76-78
[6]MEDELLIN H, CORNEY J, DAVIES J B Algorithms for the Physical and Assembly of Octree Models [J]. ComputerAided Design, 2006, 38(1):69-85
[7]SUN Xiaoxia, SUN Dianzhu, LI Yanrui, et al Algorithm of Point Data Direct Reduction in Reverse Engineering[J]. Machinery Design & Manufacture, 2006(8):37-38
[8]HUANG G Z, LU Z P Methods of Point Cloud Data Reduction for Reverse Engineering[J]. Machine Design and Research, 2005, 21(3): 59-61
[9]王麗輝三維點云數(shù)據(jù)處理的技術(shù)研究[D].北京:北京交通大學(xué),2011
[10]何東健,邵小寧,王丹,等Kinect獲取植物三維點云數(shù)據(jù)的去噪方法[J].農(nóng)業(yè)機械學(xué)報,2016(1):331-336
[11]張育鋒三維數(shù)據(jù)點云的去噪及其檢測[D].南京:南京信息工程大學(xué),2014
[12]PIEGL LA, TILLER W Algorithm for Finding All K Nearest Neighbors [J].Computer Aided Design, 2002, 34(2): 167-172
[13]XU Dong, ZHANG Quanfang, LIU Xianguo, et al Geometry Compression for Genreal Polygon Meshes[J].Journal of Computer Aided Design & Computer Graphics, 2002, 14(9): 815-819
[14]張帆點云數(shù)據(jù)幾何處理方法研究[D].西安:西北大學(xué),2013
[15]羅格三維模型去噪算法的研究及其在三維曲面重建上的應(yīng)用[D].哈爾濱:哈爾濱工業(yè)大學(xué),2015
[16]梁士超三維點云預(yù)處理技術(shù)研究[D].綿陽:西南科技大學(xué),2015
[17]吳瓊?cè)S點云模型數(shù)據(jù)的濾波算法與配準(zhǔn)算法研究[D].秦皇島:燕山大學(xué),2014
[18]姜曉通離散點云數(shù)據(jù)重建關(guān)鍵技術(shù)的研究[D].南京:南京航空航天大學(xué),2013
(編輯:關(guān)毅)