基于多數(shù)投票法的掃描點云尖銳特征保留方法

郭東兵，董黎君，梁國星

(1.太原理工大學(xué) 機械工程學(xué)院， 太原 030024； 2.精密加工山西省重點實驗室， 太原 030024)

近年來，越來越多的研究人員使用3D點云作為物體的表達(dá)模型，3D點云在逆向工程、質(zhì)量檢測和3D重建等領(lǐng)域應(yīng)用日益廣泛。但受掃描儀器精度不夠、光照問題或被測物體表面特性等因素影響，獲取的點云數(shù)據(jù)容易被噪聲污染，直接影響后期點云數(shù)據(jù)的使用。因此，為了保證后續(xù)工作順利進行，散亂點云的去噪顯得尤為重要。

針對點云去噪、特征保留的問題，國內(nèi)外許多學(xué)者都有所研究。本文主要從網(wǎng)格去噪和法向去噪兩個方面進行介紹。

網(wǎng)格去噪方法主要是在原始點云中輸入網(wǎng)格模型，目的是在雜亂的網(wǎng)格模型中恢復(fù)原始網(wǎng)格模型，同時保留其豐富的細(xì)節(jié)和銳邊等特征。Taubin等[1]首先將三角網(wǎng)格引入到信號處理過程中，然后通過后續(xù)的非線性擴展、各向異性和雙邊濾波等相關(guān)概念的使用將其轉(zhuǎn)入圖像處理特征保留領(lǐng)域[2-3]。Yadav等[4]提出一種正態(tài)投票方法，通過優(yōu)化正態(tài)投票張量的特征值實現(xiàn)了尖銳特征的保留。Lu等[5]采用頂點濾波、法向濾波和頂點更新的方法進行網(wǎng)格去噪，但當(dāng)噪聲過多、模型過于不規(guī)則時可能導(dǎo)致錯誤的處理結(jié)果，此方法需要大量的人工調(diào)參。Sun等[6]提出了一種利用L0范數(shù)最小化的各向異性點云去噪方法，但其處理邊界的能力較差，難以形成預(yù)期的完整邊界，且當(dāng)噪聲水平過大時，L0范數(shù)將難以區(qū)分噪聲和特征，使得結(jié)果過于平滑或尖銳。

相較于網(wǎng)格去噪需要預(yù)先輸入網(wǎng)格模型，法向去噪則不需要過多的預(yù)處理，可以直接在散亂點云中進行。Lu等[7]提出一種基于高斯混合模型的特征保持點云過濾，該方法主要以含噪點集及其濾波法向作為輸入，但噪聲密度過大時會產(chǎn)生錯誤的結(jié)果，且不能處理邊界未封閉模型或模型數(shù)據(jù)缺失較多等情況。Mattei等[8]提出一種基于魯棒PCA的框架，可以去除離群值，并能準(zhǔn)確去噪。Zheng等[9]提出一種點位置更新的滾動制導(dǎo)法濾波進行點云去噪，采用多范式策略來克服尖銳邊緣收縮，可保留尖銳特征，但此方法用時較長且效率不高。

針對上述方法中存在的問題，本文提出一種新的尖銳特征保留方法。多數(shù)投票法是一種集體決策方案。對于輸入的樣本，每個投票者都會產(chǎn)生一個唯一的決策，然后根據(jù)大多數(shù)投票者的決策對樣本進行判別。這種多數(shù)投票的方法主要運用于模式識別和圖像分析[10]，也可用于三維形狀識別[11]。先使用多數(shù)投票法準(zhǔn)確識別模型中的噪聲，再設(shè)定閾值去除噪聲。相較于直接采用閾值法對模型進行預(yù)處理的方法，此方法可以更加完全地去除噪聲，高效地保留尖銳特征。

1 本文方法

本文算法流程如圖1所示，采用smooth-feature模型進行闡述。輸入散亂點云P={pi}，使用k-d tree來查找每個點pi的k近鄰Nk(pi)，并使用PCA法來估計鄰域中每個點的法向[12]。根據(jù)曲面變化度對點云模型區(qū)域進行分類，識別特征區(qū)域，然后采用多數(shù)投票算法對特征區(qū)域中模糊點進行分類。最后輸出采用閾值法去除識別噪聲和離群值，并同時保留尖銳特征的點云模型。

圖1 本文方法流程

1.1 基于曲面變化度的區(qū)域分類

點云在沒有任何法向和連接信息情況下是一種非結(jié)構(gòu)化數(shù)據(jù)點，通常包括億萬個點，采用k-d tree空間劃分來搜索k鄰域可以極大地提高工作效率。任意一點pi的k鄰域確定之后便可近似估計點的法向。常規(guī)的法向估計方法采用PCA法，使用對稱半正定矩陣C的最小特征值對應(yīng)的特征向量作為點的估計法向：

(1)

其中：μ是點pi鄰域數(shù)據(jù)的質(zhì)心；C是一個協(xié)方差矩陣。矩陣C表示Nk(pi)中鄰域內(nèi)點和質(zhì)心μ之間的距離情況。通過對矩陣進行奇異值分解即可得到對應(yīng)的特征值λi(0<λ0≤λ1≤λ2)，其對應(yīng)的特征向量分別為v0、v1和v2，最小特征值λ0所對應(yīng)的特征向量v0近似為點pi的法向。λ0描述了點pi在法向方向的變化程度，所以曲面變化度可以定義為

(2)

局部曲面變化可以表示局部鄰域形成光滑曲面的程度，當(dāng)σn(pi)=0時，表示局部鄰域形成一個平面，隨著曲面變化度的增大，曲面將越來越尖銳。因此，可通過設(shè)定閾值利用曲面變化度[13]對點云區(qū)域進行分類。

1.2 基于多數(shù)投票法的點分類

區(qū)域分類后，處于光滑區(qū)域的點被認(rèn)為是正常點，處于尖銳特征區(qū)域的點、噪聲和離群值被認(rèn)為是非正常點。非正常點中，有的點屬于噪聲或離群值應(yīng)當(dāng)去除，但有的點屬于特征點應(yīng)當(dāng)保留，多數(shù)投票法由于其多數(shù)決策的特性可對這類模糊點進行高效的處理。

圖2(a)為齒輪模型齒牙部分的掃描圖，紅框內(nèi)部分為模糊黏連區(qū)域，與被掃描模型表面連接部分難以確定是該去除的噪聲點還是正常點。因此，需要采用多數(shù)投票法進行判別。圖2(b)為輪廓切片的提取，紅框內(nèi)為模糊區(qū)域。多數(shù)投票法程序在圖3中進行闡述，采用圖2(b)中的輪廓切片點云數(shù)據(jù)進行分析。在圖3中，任選一非正常點p，其k鄰域的Q范圍內(nèi)的正常點作為選民，對于每一個鄰域內(nèi)的正常點qi用移動最小二乘法[14]擬合局部曲面。qi的局部幾何可視為切平面上的高度場，局部二元多項式可擬合為qi的球面鄰域R，鄰域R的半徑為點qi與點p之間的距離。因為k鄰域范圍內(nèi)的一些相鄰正常點是離群值，所以R鄰域中點的最小二乘擬合將偏向于這些離群值。為解決這個問題，采用迭代重加權(quán)最小二乘(IRLSs)[15]的二次曲面擬合方法，通過賦值權(quán)重來精化曲面擬合結(jié)果，對具有較大擬合殘差的點進行去除。p點也需要進行二次曲面擬合，在擬合之前，首先應(yīng)建立一個局部坐標(biāo)系統(tǒng)。從協(xié)方差矩陣C得到的3個特征值可以作為點p的局部框架，p點的鄰域就可以轉(zhuǎn)變成這種框架。點p周圍的局部曲面幾何可以看作是切平面上的高度場。二次曲面公式為

fβ(x)=β·xT

(3)

式中：β=[a,b,c,d,e,f]是系數(shù)向量，X=[x2,xy,y2,x,y,1]是二次基向量。

圖2 齒輪模型

圖3 多數(shù)投票法程序

為補償噪聲和表面不連續(xù)性，采用IRLSs最小化沿著局部z軸方向的加權(quán)殘差總和，形式如下：

(4)

是高斯核函數(shù)，用來去除具有較大擬合殘差的點鄰域，帶寬σd、σx以及相關(guān)參數(shù)根據(jù)文獻(xiàn)[15]進行選擇。在擬合完二次曲面之后，根據(jù)點p是否落在距離擬合表面一定距離的閾值之內(nèi)對p行投票。

1.3 特征保留

若直接采用閾值法進行噪聲或離群值的識別與去除，由于閾值設(shè)定值較為單一，處理結(jié)果較粗糙，可能會將小的特征點也一并去除掉，導(dǎo)致丟失幾何特征。如圖4(a)，直接采用閾值去噪會將邊緣的尖銳特征點去除，導(dǎo)致出現(xiàn)圖4(b)中的過度光順情況。

本文使用多數(shù)投票法對點進行分類，以準(zhǔn)確識別正常點、噪聲和離群值，然后再使用閾值方法，以完全去除非正常點，同時保留尖銳特征，如圖4(c)所示。

圖4 特征保留效果

Kittler[16]提出了閾值法中最經(jīng)典的最小誤差閾值法，經(jīng)過對其進行二維[17]和三維[18]的推廣，可以應(yīng)用于對3D點云進行去噪。借鑒文獻(xiàn)[18]的方法，設(shè)f(x,y)表示尺寸大小為M×N的數(shù)字圖像(x,y)范圍內(nèi)任意像素的灰度級，圖像灰度級的取值范圍G={0，1，2，…,L-1},且f(x,y)∈G。分別定義坐標(biāo)為(x,y)像素點的K鄰域灰度均值和灰度中值為g(x,y)和h(x,y)，用f(x,y)，g(x,y)，h(x,y)定義一個L×L×L的三維直方圖。設(shè){s,t,q∈G}為分割閾值，用s,t,q對直方圖進行閾值化分割，得到的二值化后的圖像用g′(x,y)表示，其定義為：

(5)

最佳分割閾值(s*,t*,q*)采用三維最小閾值分割方法，其滿足：

(6)

式中W(s,t,q)是最小誤差目標(biāo)函數(shù)：

W(s,t,q)=P0(s,t,q)lnσoiσojσok+

P1(s,t,q)lnσ1iσ1jσ1k-

P0(s,t,q)lnP0(s,t,q)-

P1(s,t,q)lnP1(s,t,q)

(7)

2 實驗結(jié)果與分析

為證明本文方法的有效性，使用Artec Spider 3D掃描儀來獲取Gear和Buddha點云圖，然后使用本文方法和已有方法進行去噪處理，通過對比分析進行驗證。本文算法采用Matlab R2016a實現(xiàn)，實驗環(huán)境為Intel Core i5-2.8 GHz CPU，64位Windows 7操作系統(tǒng)，PC機。

2.1 參數(shù)選擇

多數(shù)投票算法中有5個參數(shù)需要設(shè)定，分別為k1、k2、T1、T2和(s*,t*,q*)。其中k1表示PCA法估計點云法向時鄰域的大小，文獻(xiàn)[12]提出PCA法估計法向時鄰域取值在8～32范圍時較為合適，故本文取k1=10；T1表示根據(jù)曲面變化度進行區(qū)域分類的閾值，實驗過程中取T1=0.02；k2表示多數(shù)投票過程中Q鄰域的選擇，k2值太小將導(dǎo)致難以對模糊點進行準(zhǔn)確識別，k2值太大則鄰域中包含的模糊點過多，處理難度過大。因此，采用k2=30，T2為多數(shù)投票中點的判定閾值，本實驗采用T2=0.25。(s*,t*,q*)是進行閾值處理時的設(shè)定閾值，根據(jù)不同模型所設(shè)定的閾值不同，在處理Buddha模型中采用(48,50,39)，而在處理Gear模型中采用(155,142,138)。

2.2 對比實驗

Gear模型周圍存在很多的尖銳特征，比如齒牙部分和凹槽處，所以點云中包含很多噪聲。Buddha模型主要是凹面部分噪聲較多。采用文獻(xiàn)[6-7，9]和本文方法對模型進行去噪處理，結(jié)果如圖5、6所示。從圖中可以看出，文獻(xiàn)[6]方法去噪的同時將尖銳特征邊緣過度光順，丟失了幾何特征；采用文獻(xiàn)[7]方法處理時，當(dāng)噪聲過大或采樣不足情況下會將較小的特征點也一并去除，導(dǎo)致點云模型中出現(xiàn)孔洞；采用文獻(xiàn)[9]方法主要是尖銳特征附近噪聲去除效果不理想。通過對比實驗發(fā)現(xiàn)，本文方法在去除噪聲同時可以較好地保留尖銳特征。

Fandisk模型由AIM@SHAPE模型庫提供。首先采用Meshlab軟件對模型添加0.05 dB的高斯白噪聲，然后對包含高斯白噪聲的模型進行去噪，結(jié)果如圖7所示。

圖5 Gear模型去噪結(jié)果

圖6 Buddha模型去噪結(jié)果

圖7 包含高斯白噪聲的模型去噪結(jié)果

2.3 實驗結(jié)果分析

為評估處理結(jié)果的性能，本文將處理結(jié)果使用Geomagic軟件進行分析，誤差度量Dmean用來表示處理后點與對應(yīng)真實點之間的平均距離。誤差結(jié)果如表1所示。文獻(xiàn)[6]方法相對其他兩種方法去噪效果較好，但結(jié)果可能會失真。而采用本文方法處理后的點與真實點距離都相對較小。

表1 不同方法去噪誤差比較 Dmean

為對算法的計算效率進行評估，計算每種方法過濾每個模型所用的時間。點的數(shù)量是影響過濾時間的主要因素，本文采用不同點數(shù)的點云進行實驗。表2列出了各種模型點數(shù)目和各種算法消耗的時間。

從表2中可以看出，文獻(xiàn)[6]方法和本文方法耗時都相對較少，但文獻(xiàn)[6]方法在處理過程中易出現(xiàn)過度光順現(xiàn)象。文獻(xiàn)[7]和[9]方法用時較長，且文獻(xiàn)[7]方法尖銳特征保留不完整。

表2 不同方法耗時對比 s

模型點云數(shù)文獻(xiàn)[6]方法文獻(xiàn)[7]方法文獻(xiàn)[9]方法本文方法Buddha839 50969.087.073.066.0Gear2 008 737157.0180.0195.0163.0Fandisk2 5021.52.62.31.8

3 結(jié)束語

將多數(shù)投票法應(yīng)用于散亂點云預(yù)處理過程能實現(xiàn)去除噪聲同時保留尖銳特征的目標(biāo)。利用曲面變化度將散亂點云進行區(qū)域分類，識別特征區(qū)域。多數(shù)投票法可以精確區(qū)分特征區(qū)域的正常點和非正常點，準(zhǔn)確識別非正常點后再使用閾值法進行處理可以較好地實現(xiàn)預(yù)期效果。

本文所提出方法的局限性在于當(dāng)尖銳特征附近噪聲水平過大時，可供選擇的正常點將會減少，從而導(dǎo)致投票結(jié)果可信度降低，因此如何提高方法的魯棒性將是下一步的研究方向。