基于OPTICS聚類和改進(jìn)雙邊濾波的點云去噪方法

鐘志鵬，張建州，梁彪

（1.四川大學(xué)計算機(jī)學(xué)院，成都 610065；2.東方電機(jī)有限公司焊接分廠，德陽 618000）

0 引言

獲取真實世界物體的三維幾何是計算機(jī)視覺和圖形研究中的一個長期課題[1]。隨著低成本、高分辨率三維掃描儀的商業(yè)化，三維點云數(shù)據(jù)的獲取變得比較容易[2]。然而，由于傳感器的限制，采集裝置的固有噪聲，場景中的表面或人工制品的反射特性等儀器自身因素、環(huán)境因素、人為因素，采集的點云數(shù)據(jù)不可避免地含有噪聲。因此，有必要對原始點云進(jìn)行去噪處理，以獲得適合于進(jìn)一步處理的精確點云[3]。好的去噪算法有以下幾個特征（1）在有效去噪的同時能保持點云模型的特征；（2）抑制模型的體積和外形變化；（3）算法復(fù)雜度低；（4）具有較強(qiáng)的魯棒性。

目前，國內(nèi)外有許多學(xué)者對點云去噪提出了各種方法，Taubin[4]將圖像Laplace濾波引入到網(wǎng)格模型去噪中，提出了基于信號處理的三角網(wǎng)格去噪方法，對于數(shù)據(jù)點密度不均勻的點云，容易造成數(shù)據(jù)點向密集處漂移；Fleishman等人[5，6]將圖像雙邊濾波引入三維點云去噪，提出基于雙邊濾波的各向異性保特征去噪算法，算法簡單且去噪速度較快，但對于大噪聲容易造成過光順、細(xì)節(jié)特征丟失；Desbrun等人[7]將基于偏微分方程技術(shù)運用到曲面處理上，提出了基于平均曲率流的三角網(wǎng)格光順去噪算法，但會使點集的采樣率變壞；王麗輝等人[8]結(jié)合模糊C均值和雙邊濾波進(jìn)行點云去噪，該方法對不同尺度的噪聲進(jìn)行分步處理，得到了較好的效果，但對噪聲敏感，會影響聚類結(jié)果；曹爽等人[9]利用鄰域點將點分為特征點和非特征點，分別計算雙邊濾波因子進(jìn)行去噪，有效保持了被掃描物體的特征，但特征選擇時間較長；袁華等人[10]、李鵬飛等人[11]、李仁忠等人[12]和趙揚(yáng)[13]都將噪聲細(xì)分為大尺度和小尺度噪聲，用統(tǒng)計濾波和半徑濾波相結(jié)合去除大噪聲，袁華、李仁忠和趙揚(yáng)用改進(jìn)雙邊濾波去除小噪聲，李鵬飛用快速雙邊濾波去除小噪聲，但噪聲點去除效率不是很高；許龍等人[14]提出了基于模糊C均值和均值濾波的點云去噪算法，用模糊C均值聚類算法去除大噪聲，用均值濾波去除小噪聲，較好地保持了邊界特征，但聚類結(jié)果也對噪聲敏感。

盡管噪聲點是隨機(jī)產(chǎn)生的，但根據(jù)其分布可以將其分為大尺度噪聲和小尺度噪聲，大尺度噪聲即離群噪聲，這部分噪聲離點云主體較遠(yuǎn)，小尺度噪聲即點云模型表面噪聲，這部分噪聲離點云主體較近。針對不同尺度的噪聲，為了在有效去除噪聲的同時保留點云特征，本文提出一種基于OPTICS聚類和改進(jìn)雙邊濾波的點云去噪算法，首先用OPTICS聚類算法去除大尺度噪聲，然后用改進(jìn)的雙邊濾波算法去除小尺度噪聲。

1 基于OPTICS聚類的去噪

聚類算法使得類內(nèi)的數(shù)據(jù)對象相似性盡可能大，類間的數(shù)據(jù)對象的差異性也盡可能大，所以可用其將點云主體和噪聲有效地區(qū)分開?；诿芏染垲惖姆椒ɡ妹芏榷皇蔷嚯x進(jìn)行聚類，能發(fā)現(xiàn)形狀不規(guī)則的聚類，這對具有噪聲的數(shù)據(jù)十分重要。這類算法用點鄰域內(nèi)的鄰居點數(shù)來衡量該點所在空間的密度，如果它的密度大于給定閾值，則將其加入到相近的聚類中。其中 OPTICS（Ordering Points to Identify the Clus?tering Structure）是一種典型的基于密度聚類的方法[15]，它是對 DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法[16]的改進(jìn)，該算法對輸入?yún)?shù)鄰域半徑ε不再敏感，只要確定了鄰域最少點數(shù)MinPts，鄰域半徑ε的改變不會影響得到的有序?qū)ο罅斜?，并且能夠通過得到的有序?qū)ο罅斜韥慝@得不同密度的聚類。由于OPTICS算法不需要初始定義聚類數(shù)目、對噪聲不敏感、對輸入?yún)?shù)不敏感、能夠識別噪聲點，使得其非常適合處理點云模型中的噪聲。

1.1 OP TICS算法的有關(guān)概念

假設(shè)數(shù)據(jù)集合為X={x1,x2,…,x3}，鄰域半徑為ε，鄰域最少點數(shù)為MinPts：

定義1：ε鄰域：設(shè)x∈X，x的ε鄰域為：

定義2：密度：設(shè)x∈X，x的密度為：

定義 3：核心點：設(shè)x∈X，如果ρ(x)≥MinPts，則x為X的核心點。

定義 4：直接密度可達(dá)：設(shè)x,y∈X，如果x∈Nε(y)且ρ(y)≥MinPts（即x為y的ε鄰域且y為核心點），則x是從y直接密度可達(dá)的。

定義5：核心距離：設(shè)x∈X，稱使得x成為核心點的最小鄰域半徑為x的核心距離，數(shù)學(xué)定義為：

定義5：可達(dá)距離：設(shè)x,y∈X，y關(guān)于x的可達(dá)距離定義為：

1.2 OPTICS 算法去噪步驟

圖1 OPTICS算法去噪流程圖

圖1為將OPTICS算法應(yīng)用到點云去噪的基本步驟，具體如下：

（1）初始化：輸入點云得到點集Points，給定鄰域半徑ε和鄰域最少點數(shù)MinPts，創(chuàng)建兩個隊列：有序隊列（核心點及其直接密度可達(dá)點）和結(jié)果隊列（樣本點輸出次序）。

（2）如果點集Points中所有點都已處理，則跳轉(zhuǎn)到（4）。否則從中點集Points取一個未處理（即不在結(jié)果隊列）的核心點，將其放入結(jié)果隊列，將其未在結(jié)果隊列的直接密度可達(dá)點放入有序隊列并按可達(dá)距離升序排列。

（3）如果有序隊列為空，則跳轉(zhuǎn)到步驟（2）。否則從有序隊列中取出第一個點放入結(jié)果隊列，并執(zhí)行以下操作：

（3.1）如果該點非核心點，則跳轉(zhuǎn)到步驟（3）。否則找到其所有直接密度可達(dá)點。

（3.2）如果該點所有直接密度可達(dá)點都已處理（即在結(jié)果隊列），則跳轉(zhuǎn)到步驟（3），否則取其中一點，執(zhí)行下一步。

（3.3）如果該直接密度可達(dá)點已在有序隊列，且此新的可達(dá)距離比舊的小，則用新的可達(dá)距離取代舊的，并重新排列有序隊列，跳轉(zhuǎn)到步驟（3.2）。

（3.4）如果該直接密度可達(dá)點不在有序隊列，則插入該點，并重新排列有序隊列，跳轉(zhuǎn)到步驟（3.2）。

（4）得到有序?qū)ο罅斜恚唇Y(jié)果隊列），給定鄰域半徑ε?（ε?≤ε）。

（5）遍歷所有點，去除可達(dá)距離和核心距離都大于ε?的噪聲點。

1.3 參數(shù)選擇

在上述去噪步驟中，需要給定的參數(shù)有鄰域半徑ε、ε?，鄰域最少點數(shù)MinPts。由于確定了鄰域最少點數(shù)MinPts，鄰域半徑ε的改變不會影響得到的有序?qū)ο罅斜?，本實驗中ε取MAX。MinPts的選取有一個指導(dǎo)性原則，即MinPts≥dim+1，其中dim表示數(shù)據(jù)的維度。根據(jù)實驗，MinPts取4或5即可得到良好的效果。對于ε?，計算每個點對應(yīng)的第k個最近鄰域的距離并降序排序，將這個排序圖中第一個谷值點對應(yīng)的k距離值設(shè)為ε?，并可適當(dāng)修改此值以獲得實驗數(shù)據(jù)的最佳效果。在ε取MAX的情況下，點的核心距離也是點對應(yīng)的第k（=MinPts）個最近鄰域距離，所以在實驗中可直接通過核心距離求得，節(jié)省了開銷。

2 基于改進(jìn)的雙邊濾波算法去噪

經(jīng)過基于OPTICS聚類的去噪后，大尺度噪聲被去除，但點云模型表面仍有一些小尺度噪聲。雙邊濾波算法[17]簡單高效，對邊緣特征有良好的保持效果，對小尺度噪聲有較好的去除效果，所以本文采用雙邊濾波算法對小尺度噪聲進(jìn)行平滑去噪。雙邊濾波算法以當(dāng)前點的鄰域點的加權(quán)平均值來修正當(dāng)前點的位置，從而達(dá)到濾波的效果。

2.1 傳統(tǒng)雙邊濾波算法

傳統(tǒng)雙邊濾波的表達(dá)式為：

其中，為濾波后的點，pi為原數(shù)據(jù)點，α為雙邊

濾波因子，n為點pi的法矢。α的表達(dá)式為：

Ws的表達(dá)式為：

其中，σc和σs為高斯濾波參數(shù)。σc為點pi到其鄰域點的距離對點的影響因子，用來控制平滑程度。σc為點pi到其鄰域點的距離在其法向上的投影對點pi的影響因子，用來控制特征保持程度。通?？梢杂脭?shù)據(jù)點pi的鄰域半徑來表示σc，用數(shù)據(jù)點pi的鄰域點標(biāo)準(zhǔn)差來表示σc。確定σc后，σc的不同取值會影響點云數(shù)據(jù)模型的平滑效果。

2.2 改進(jìn)的雙邊濾波算法去噪

雙邊濾波因子受點局部鄰域特征信息的影響較大，為了提高其保特征性與穩(wěn)健性，對傳統(tǒng)雙邊濾波因子進(jìn)行改進(jìn)。改進(jìn)后的雙邊濾波因子為：

其中各項參數(shù)含義均與2.1小節(jié)中相同。

改進(jìn)的雙邊濾波算法去噪的基本步驟如下：

（1）對每個點pi，計算它的k個最近鄰域點N(pi)。

（2）對每個點pi，在k鄰域的基礎(chǔ)上通過主成分分析法（PCA）來獲得點pi的法矢，并進(jìn)行法向一致性調(diào)整。

（3）對每個近鄰點pi，計算平滑濾波權(quán)函數(shù)的參數(shù)和特征保持權(quán)函數(shù)的參數(shù)

（4）按照式（7）和式（8）計算出平滑濾波權(quán)函數(shù)Wc(x)和特征保持權(quán)函數(shù)WS(y)。

（5）將Wc(x)和WS(y)代入式（9）求出改進(jìn)雙邊濾波因子α′的值。

（6）通過式（5）計算使用改進(jìn)雙邊濾波后的點的位置，將點pi移動到新的位置處。

（7）遍歷完所有點后，得到平滑去噪后的新點云模型，算法終止。

3 實驗結(jié)果

本文實驗均通過VS2013、PCL點云庫和MATLAB實現(xiàn)。為了驗證本文算法的有效性，選取了經(jīng)典的Stanford bunny點云模型以及Laurana點云模型來進(jìn)行實驗，在原始點云中隨機(jī)選取了一定數(shù)量的點，在它們的法線方向上增加了噪聲點，噪聲模型如下：

其中，為濾波后的點，pi為原數(shù)據(jù)點，β為隨機(jī)數(shù)，ni為點pi的法矢。此外，還將本文算法與常用的三維點云去噪算法統(tǒng)計濾波、半徑濾波和統(tǒng)計濾波結(jié)合半徑濾波進(jìn)行了比較。

圖2 不同去噪方法Stanford bunny點云模型的去噪效果圖

圖3不同去噪方法Laurana點云模型的去噪效果圖

圖2 、圖3分別是不同去噪方法對Stanford bunny點云模型和Laurana點云模型的去噪效果圖。從圖2（f）、圖3（f）可以看到點云周圍的大尺度噪聲被去除了，并且較好地保留了點云特征，說明本文算法能有效去除大尺度噪聲。通過比較圖 2（f）與圖 2（c）（d）（e）、圖 3（f）與圖 3（c）（d）（e）可知本文算法去除的大尺度噪聲數(shù)多于統(tǒng)計濾波、半徑濾波和二者結(jié)合濾波。通過對比圖 2（f）與圖 2（g）、圖 3（f）與圖 3（g）可以看到點云周圍的小尺度噪聲被去除了，從對比局部放大的圖2（h）與圖 2（i）、圖 3（h）與圖 3（i）更能清晰地看到去除和平滑的效果，同時也很好地保留了點云特征，說明改進(jìn)雙邊濾波能夠有效去除和平滑小尺度噪聲。

表1為不同去噪方法的去噪效果數(shù)據(jù)對比，通過具體數(shù)值更能得知本文算法能有效去除噪聲，且效率較高。

表1 不同去噪方法去噪效果對比

4 結(jié)語

本文將利用OPTICS聚類去除大尺度噪聲的優(yōu)勢和改進(jìn)雙邊濾波去除小尺度噪聲的優(yōu)勢，將二者相結(jié)合用于點云去噪，并將該方法與常用的點云去噪方法統(tǒng)計濾波、半徑濾波、統(tǒng)計濾波結(jié)合半徑濾波進(jìn)行了對比分析。通過使用Stanford bunny點云模型以及Lau?rana點云模型進(jìn)行實驗，證明了本文方法對點云去噪是有效的，且能較好地保留點云的特征。通過對比實驗證明了本文方法提高了準(zhǔn)確性。