廖昌粟 何東建 王美麗*

1(西北農(nóng)林科技大學信息工程學院 陜西 楊凌 712100)2(西北農(nóng)林科技大學機械與電子工程學院 陜西 楊凌 712100)

一種新的三維點云模型去噪光滑算法研究

廖昌粟1何東建2王美麗1*

1(西北農(nóng)林科技大學信息工程學院 陜西 楊凌 712100)2(西北農(nóng)林科技大學機械與電子工程學院 陜西 楊凌 712100)

提出一種三維點云模型的去噪光滑算法。該算法根據(jù)密度濾波和點法矢量信息對離群噪聲點進行去除；再利用張量投票算法和數(shù)據(jù)點的近鄰點在其最小二乘平面上投影的分布均勻性檢測出模型的邊界特征，并對特征實現(xiàn)加強操作；最后，采用雙邊濾波對模型表面進行光滑。實驗表明，該算法能有效地對模型進行去噪光滑處理，且由于對模型邊界特征進行了保留與加強，從而避免了模型光滑操作對模型特征造成損害的問題。

三維點云 邊界檢測 密度濾波

0 引 言

由三維掃描儀所得到的三維點云模型往往帶有不同程度的噪聲點，這對于點云模型的逆向重建有著不小的影響，所以對模型進行去噪光滑處理顯得十分重要。

通常三維點云模型的噪聲點可分為離群噪聲點(大尺度噪聲點)和模型表面噪聲點(小尺度噪聲點)。對這兩種噪聲的去除方法已經(jīng)有了很多研究。其中較為典型的是利用聚類對噪聲點進行檢測。Wang等[1]引入模糊C均值聚類算法，利用模糊C均值聚類算法對噪聲點進行光滑。Schall等[2]提出了一種基于聚類的mean-shift去噪方法，將每個數(shù)據(jù)點都移動到最大相似位置，從而得到光滑的模型表面。劉大峰等[3]提出了一種魯棒濾波算法，采用核密度估計聚類方法，通過mean-shift迭代將每一個數(shù)據(jù)點“漂移”到核密度估計函數(shù)的局部最大值點，利用該最大值點，可以確定點云的聚類中心和原始曲面，并充分利用了數(shù)據(jù)點的法向量方向。該算法能夠?qū)崿F(xiàn)快速高效的光順去噪。

除了聚類算法之外，統(tǒng)計學方法也經(jīng)常應(yīng)用到點云模型的去噪算法中，Wetzler等[4]將拉普拉斯算子運用到濾波過程中，該方法能夠在去除噪聲點的同時，有效地對模型特征進行保留。Jenke等[5]利用貝葉斯統(tǒng)計法消除點云模型的噪聲點，也得到了較好的效果。劉輝等[6]在點云數(shù)據(jù)的垂直方向和水平方向上分別采用比較相鄰點夾角大小和相鄰點加權(quán)平均的方法去除噪聲點，再利用最小二乘擬合的方法得到去除噪聲點處的三維坐標。Daniels等[7]利用移動最小二乘法(MLS)對三維點云模型進行擬合，能夠取不同的權(quán)函數(shù)以改變擬合曲面的光滑度。

對于點云模型的光滑處理，更為普遍的算法要數(shù)高斯濾波算法，而由其衍生出的雙邊濾波算法在圖形圖像處理方面更是應(yīng)用廣泛。目前，對于傳統(tǒng)的雙邊濾波和高斯濾波也出現(xiàn)了很多改進算法。范涵奇等[8]提出了一種統(tǒng)一的局部高階雙邊濾波算法，該算法引入魯棒統(tǒng)計理論以獲得模型表面的幾何特征，優(yōu)化數(shù)據(jù)點的法向量，對模型進行高階雙邊濾波處理。曹爽等[9]對雙邊濾波算法進行了改進，先利用鄰域點判斷數(shù)據(jù)點是否屬于噪聲點，然后根據(jù)不同尺度的點云集合來確定噪聲點與非噪聲點的雙邊濾波因子，實現(xiàn)了基于特征選擇的雙邊濾波去噪方法。唐杰等[10]提出一種基于CUDA的點云光滑方法，利用高斯加權(quán)的方法計算數(shù)據(jù)點的法矢量，并在光滑過程中加入鄰近點面積影響因子。Wang等[11]擴展了圖像去噪中的non-local技術(shù)，提出一種對于采樣表面的非局部去噪方法。該方法具有較強的魯棒性，與雙邊濾波、均值轉(zhuǎn)移濾波相比，受噪聲點的影響較小，有更好的效果。

以上提到的所有方法，對于點云模型的去噪光滑過程都有一定的幫助，但是在模型進行光滑處理的同時，都會對模型的特征造成一定的損害。因此，本文提出一種能夠?qū)c云模型特征進行保留和加強的去噪光滑算法。實驗結(jié)果表明，本文算法能夠在去除點云模型兩類噪聲點的同時，保留和加強模型的邊界特征。

1 算法總體描述

針對點云模型不同的兩類噪聲點，本文采用不同的方法將其去除，且為了避免光滑算法對模型特征的損害，在對點云模型表面進行光滑處理之前，先保留點云模型的特征并將其適當加強，從而可以避免出現(xiàn)“過光滑”的現(xiàn)象。本文算法可分為三個部分：a) 離群噪聲點的去除；b) 點云模型特征邊界的檢測與加強；c) 點云模型的表面光滑。

2 離群噪聲點的去除

離群噪聲點相對于模型的特征數(shù)據(jù)點來說，有一個很顯著的特點，即離群噪聲部分的點云密度通常要小于模型特征部分的點云密度。(如圖1所示，右邊線圈出的為離群噪聲部分；左邊線圈出的為模型特征部分)利用這一特點即可分離出離群噪聲點。

圖1 離群噪聲部分與模型特征部分的對比示意圖

本文算法利用上述特性，并在此基礎(chǔ)上根據(jù)點云模型整體的密度信息，實現(xiàn)密度濾波閾值的自動生成，使得算法具有自適應(yīng)性。再根據(jù)數(shù)據(jù)點的法矢量信息，進一步區(qū)分離群噪聲點和模型特征點，減少密度濾波對模型特征的損害。

2.1 密度濾波

要計算點云模型某部分的數(shù)據(jù)點密度，則需要定義一個基本的空間單元，再根據(jù)單元中數(shù)據(jù)點的數(shù)量進行密度的計算。在本文中，設(shè)點云模型集合為N，點云模型的數(shù)據(jù)點的總數(shù)量為Num，pi={pi|pi∈N,i=1,2,…,Num}，以數(shù)據(jù)點pi為中心，建立以d為半徑的空間包圍球SV(如圖2所示)，搜索得到該包圍球SV內(nèi)的數(shù)據(jù)點數(shù)量Pnum。設(shè)一密度閾值為dv，若：

dv>Pnum/d

(1)

則將點pi作為離群噪聲點的備選點。

圖2 空間包圍球SV示意圖

上述計算方法雖然簡單，但是，不同的點云模型，其數(shù)據(jù)點坐標值之間往往相差較大，所以使得空間包圍球SV的半徑d值變得不好選擇。針對此問題，本文根據(jù)模型總體的密度信息計算得到d的值。

利用模型的點云坐標信息，可以得到模型的空間最小包圍立方體V，設(shè)該立方體V的邊長為l，令：

d=0.1×l

(2)

本文提出一個“滿密度”的概念，如圖2所示，搜索點pi的n個最鄰近點，若n個鄰近點均在以d為半徑的包圍球內(nèi)，則稱點pi為“滿密度”點。計算點云模型中的“滿密度”點的個數(shù)，設(shè)為CNum，若：

CNum>rate×Num

(3)

則令：

d=dp×d

(4)

其中，rate與dp均為比例系數(shù)，取0～1。重復上述式(3)、式(4)的計算，直到“滿密度”點的個數(shù)CNum不滿足式(3)，此時d的值即為該模型包圍球SV的適宜半徑值。在上述計算過程中，比例系數(shù)rate表示直接被認定為模型特征點的數(shù)量與模型數(shù)據(jù)點總數(shù)量的比值，直接被認定為特征點的數(shù)據(jù)點不再進行式(1)的判斷，所以式(3)的意義在于控制密度濾波的濾波程度。比例系數(shù)dp表示每次半徑d縮小的程度，當半徑d縮小，即數(shù)據(jù)點的包圍球SV縮小時，在其包圍球中能夠搜索到的數(shù)據(jù)點則減少，從而“滿密度點”的數(shù)量也會減少。重復上述計算，即可得到要求的濾波程度，以及合適的球半徑d值。

上述的密度濾波的算法過程可以總結(jié)為：a) 利用式(2)得出球半徑d的初始值；b) 設(shè)定數(shù)據(jù)點pi的鄰近點搜索個數(shù)n，搜索其n個鄰近點，檢測是否均在其以d為半徑的包圍球內(nèi)，由此得出模型“滿密度”點的個數(shù)CNum；c) 判斷CNum是否滿足式(3)，若不滿足，則可得到半徑d的值；若滿足，則利用式(4)得出半徑d的值，并重復b)、c)的過程。d) 設(shè)定密度閾值dv，利用式(1)，判斷數(shù)據(jù)點pi是否為離群噪聲點的備選點。

在此算法的步驟d)中，由于不同點云模型所對應(yīng)的球半徑d值之間差異很大，密度閾值dv的值并不方便直接設(shè)定。為了縮小dv的取值范圍，本文利用點云個數(shù)的比較來代替密度之間的直接比較，令：

dv=dnum/d

(5)

則式(1)可替換為：

dnum

(6)

其中dnum為一個自然數(shù)，由于Pnum不大于鄰近點搜索個數(shù)n，所以dnum的取值范圍為0～n，由此可以將dnum代替密度閾值dv，使得閾值的取值限定在一個較小范圍內(nèi)。

2.2 密度濾波的改進

2.1節(jié)中的算法只考慮了點云模型的密度信息，這樣可能會在去噪過程中出現(xiàn)如圖3所示的情況。由于圖3中的杯子點云模型某些特征部分的點云密度過小，使得在去除了離群噪聲點的同時，該部分的特征點也被去除了，損害了模型的特征。

圖3 密度濾波對密度過小模型的處理結(jié)果

為了避免這種情況的發(fā)生，本文算法根據(jù)模型數(shù)據(jù)點的法矢量的方向信息對噪聲點和模型特征點進行進一步的判斷。由于離群噪聲點相對于模型特征點的分布更沒有規(guī)律性，所以只需要判斷數(shù)據(jù)點法矢量的一致性即可分辨出噪聲點和模型特征點。

設(shè)定一個方差閾值Sv，為使該閾值的取值縮小到一個較小范圍內(nèi)，先對集合NN中所有的法矢量進行單位化，再利用：

(7)

(8)

即可得到方差值s，其中n為集合NN的元素個數(shù)。若：

s

(9)

則表示數(shù)據(jù)點pi為模型特征點而非離群噪聲點。其中Sv的取值范圍為0～0.5。

如圖4所示，利用上述方法，可以一定程度上避免由于點云模型本身局部特征點密度過小而造成的特征被損害的問題。

圖4 增加法矢量方差判斷的密度濾波處理結(jié)果

3 模型特征邊界的檢測與加強

三維點云模型的特征提取是三維重建工程中非常重要的一環(huán)，目前已經(jīng)有了很多這方面的研究。Pang等[12]提出了一種基于模型局部表面適應(yīng)方法，能夠有效地檢測模型的尖銳特征和平滑特征，并且適用于不同密度特征的檢測。Altantsetseg等[13]利用截斷的傅里葉級數(shù)對特征點進行檢測，利用拉普拉斯濾波算法對模型進行光滑操作。該方法能有效地避免噪聲點干擾。Mérigot等[14]提出了一種基于泰森多邊形的算法，該算法能對模型的分段光滑表面進行主曲率，尖銳特征，法矢量進行有效計算的方法，該方法對于噪聲點也有一定的容錯性。Fleishman等[15]基于魯棒的統(tǒng)計模型，對噪聲點進行去除。利用移動最小二乘法重建分段光滑平面。該方法能夠有效地檢測模型的尖銳特征。Park等[16]對張量投票算法進行了改進，提出多尺度張量投票算法，該方法對噪聲有一定的抵御作用。

本文采用文獻[16]中提到的張量投票算法，并且結(jié)合數(shù)據(jù)點鄰近點在其最小二乘平面上的分布均勻性，對模型的邊界特征進行檢測。

3.1 張量投票算法

每一個三維空間中的點坐標都能表示成一個3×3的對稱半正定矩陣，利用文獻[16]中對張量投票算法的描述，設(shè)模型中的某數(shù)據(jù)點pi和其鄰近點集合N，則pi所對應(yīng)的張量投票矩陣為Ti，且：

(10)

(11)

(12)

設(shè)一閾值ω+，若ωi>ω+，則數(shù)據(jù)點pi為模型的特征邊界點。

利用文獻[16]中的方法，如圖5所示，可以得到模型的邊界特征。但該方法存在一個問題，便是只能夠保留模型密閉部分的邊界特征，模型非密閉部分的邊界特征無法取得。

圖5 張量投票算法對模型邊界特征的提取效果圖

3.2 點云模型非密閉部分邊界特征的檢測

針對張量投票算法只能保留模型非密閉部分邊界特征的缺陷，本文根據(jù)數(shù)據(jù)點的鄰近點在其最小二乘平面上的投影分布均勻性，判斷數(shù)據(jù)點是否為模型非密閉部分的邊界特征點。

點云模型非密閉部分的邊界點與非邊界點在其最小二乘平面上的投影分布有著較為明顯的區(qū)別，如圖6所示。邊界點的近鄰點通常分布不均勻，而非邊界點的近鄰點分布較為均勻。利用這一分布上的區(qū)別，可以區(qū)分模型非密閉部分的邊界點和非邊界點。

圖6 點云模型非密閉部分邊界點與非邊界點在其最小二乘平面上的投影分布圖

|bNum-aNum|/n>thre

(13)

則表示數(shù)據(jù)點pi為邊界點，否則其為非邊界點。其中thre為一大于0的比例系數(shù)，可以控制邊界保留的程度。

如圖7所示，利用該方法，可以得到點云模型非密閉部分的邊界特征。

圖7 模型非密閉部分邊界特征的提取效果圖

如圖8所示，將該方法與3.1節(jié)中的張量投票算法相結(jié)合，即可得到點云模型的所有邊界特征，包括其密閉部分邊界特征和非密閉部分邊界特征。

圖8 模型綜合邊界特征的提取效果圖

3.3 特征邊界的加強

獲取點云模型的邊界特征之后，為了提高后期模型重建工作的精確性，常常需要對點云模型的特征邊界進行加強操作。本文采用簡單的插點法對模型的特征簡介進行加強，即在某特征點與其最近特征點中間插入新的數(shù)據(jù)點。如圖9所示，此方法雖然簡單，但可能會引起誤差點的增多。

圖9 特征邊界加強效果圖

因此本算法規(guī)定，只有當兩特征點之間的距離小于空間包圍球SV的半徑值d時，才進行插點操作。結(jié)果如圖10所示?？梢砸欢ǔ潭壬辖鉀Q誤差點增多的問題。

圖10 帶判斷的特征邊界加強效果圖

4 模型表面的光滑處理

對于點云模型表面的光滑處理，在上文中已經(jīng)提到了很多，雖然其對模型均有損害，可能產(chǎn)生“過光滑”現(xiàn)象，但是由于本文算法保留了模型的邊界特征，所以像均值濾波、中值濾波、高斯濾波、雙邊濾波等方法，均可以運用到本方法中，對模型表面進行光滑處理，且不會對模型的特征邊界造成損害。

本文采用雙邊濾波對點云模型表面進行光滑處理。雙邊濾波算法具有非迭代、局部、實現(xiàn)簡單等特點，利用文獻[17]：

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

其中，N(pi)表示數(shù)據(jù)點pi的鄰近點集合，pj為數(shù)據(jù)點pi的鄰近點，k為鄰近搜索數(shù)據(jù)點個數(shù)，n為模型數(shù)據(jù)點總數(shù)，l為用戶自定義閾值，取值范圍一般為{1/16 1/8 1/4 1/2 1 2 4 8 16}[18]。利用上述方法可以快速確定雙邊濾波算法中σc和σs兩參數(shù)的值。

5 實驗結(jié)果

本文所有算法均在IntelCOREi5-3210M、2.50GHz處理器，4.00GB內(nèi)存的環(huán)境下實現(xiàn)和運行。

如圖11和圖12分別為規(guī)則模型和非規(guī)則模型的離群噪聲點去除效果圖，表1中的零件模型與玉米葉模型所對應(yīng)的數(shù)據(jù)分別為該模型去噪處理時所涉及到閾值的值，dnum為2.1節(jié)中提到的自然數(shù)，所有實驗中鄰近搜索點數(shù)n均為10，比例系數(shù)rate為0.5。由處理結(jié)果可知，本文提出的離群去噪算法對于這兩類模型的離群噪聲的去除都有很好的效果。

圖11 規(guī)則模型的離群去噪處理結(jié)果示意圖

圖12 不規(guī)則模型的離群去噪處理結(jié)果

模型號dnum零件模型3玉米葉模型5花瓣模型13

如圖13中的花瓣模型為帶有大片連續(xù)噪聲的不規(guī)則模型。其中(b)為dnum等于1時的離群去噪結(jié)果，可以看出，此時的處理結(jié)果中還帶有部分的噪聲點；(c)為dnum等于3時的結(jié)果，此時的花瓣模型中離群噪聲點已經(jīng)全部去除。由此可見，對于帶有大片連續(xù)噪聲模型噪聲點的去除可以通過調(diào)整dnum的值，以達到滿意的處理效果。

圖13 不規(guī)則模型的連續(xù)離群噪聲點去噪處理結(jié)果

因此，閾值dnum對于帶有大片連續(xù)噪聲的不規(guī)則模型的處理結(jié)果影響較大，可以利用它調(diào)整不同模型的離群去噪程度。

圖14為本文算法對于帶有兩種噪聲點(離群噪聲點和模型表面噪聲點)的模型的總體處理結(jié)果，以及文獻[17]的處理結(jié)果。由圖14(a)和(b)對比可知，算法對模型的離群噪聲點有很好的去除效果；該人頭模型的主要特征為人頭的五官部分，由(c)和(d)的結(jié)果可知，算法對其特征部分進行了較好的保留；由(e)和(b)的處理結(jié)果可知，算法對模型模型的表面進行了良好的光滑處理。由(e)和(f)對比可知，兩種方法都能夠較好地對模型的離群噪聲點進行去除和模型表面進行光滑。綜上所述，本文算法對于這兩種噪聲點都有很好的去除作用。

圖14 本文算法總體處理結(jié)果

圖15中(a)為本文算法對人頭模型去噪光滑處理后，表面生成的結(jié)果，(b)為文獻[17]的處理結(jié)果。本文算法由于進行了模型特征邊界的保留，因此，所得到的結(jié)果保留了更多模型原本的特征；而文獻[17]僅對離群噪聲點進行去除和模型表面進行光滑操作，因此，模型容易出現(xiàn)過度光滑的現(xiàn)象。

圖15 本算法與文獻[17]處理結(jié)果對比

6 結(jié) 語

本文提出了一種新的針對三維點云模型的去噪光滑算法。該算法分為三個部分，其中具有自適應(yīng)性的離群去噪算法對于模型的離群噪聲點有很好的去除效果；模型邊界特征的保留算法能夠同時保留模型密閉部分和非密閉部分的特征；對雙邊濾波算法的閾值選取進行了一定的改進，能夠更加容易獲取合適的閾值。算法在去除點云模型兩種噪聲點的同時，能較好地保留模型的邊界特征，一定程度上解決雙邊濾波、高斯濾波、均值濾波等光滑算法對模型產(chǎn)生“過光滑”的問題。本算法適用于各類三維點云模型，且均能達到較好的效果。

由于文中邊界保留方法的抗噪性還不夠強，當模型表面的噪聲點過多時，會影響本文算法對模型邊界特征的提取結(jié)果，這個部分將作為后續(xù)工作中研究的重點。

[1]WangL,YuanB,MiaoZ.EllipsoidCriterionandFuzzyCMeansAlgorithmfor3DPointCloudDataDenoising[C]//Proceedingsofthe2008CongressonImageandSignalProcessing,2008,2:361-365.

[2]SchallO,BelyaevA,SeidelHP.RobustFilteringofNoisyScatteredPointData[C]//ProceedingsoftheSecondEurographics/IEEEVGTCConferenceonPoint-BasedGraphics,2005:71-77.

[3] 劉大峰,廖文和,戴寧,等.散亂點云去噪算法的研究與實現(xiàn)[J].東南大學學報(自然科學版),2007,37(6):1108-1112.

[4]WetzlerA,RosmanG,KimmelR.Patch-spaceBeltramidenoisingof3Dpointclouds[C]//2012IEEE27thConventionofElectricalandElectronicsEngineersinIsrael,2012:1-5.

[5]JenkeP,WandM,BokelohM,etal.Bayesianpointcloudreconstruction[J].ComputerGraphicsForum,2006,25(3):379-388.

[6] 劉輝,王伯雄,任懷藝,等.基于三維重建數(shù)據(jù)的雙向點云去噪方法研究[J].電子測量與儀器學報,2013,27(1):1-7.

[7]DanielsJI,HaLK,OchottaT,etal.RobustSmoothFeatureExtractionfromPointClouds[C]//ProceedingsoftheIEEEInternationalConferenceonShapeModelingandApplications,2007:123-136.

[8] 范涵奇,苗蘭芳,張鑫,等.魯棒的高階雙邊濾波去噪算法[J].計算機輔助設(shè)計與圖形學學報,2009,21(6):812-818.

[9] 曹爽,岳建平,馬文.基于特征選擇的雙邊濾波點云去噪算法[J].東南大學學報(自然科學版),2013,43(S2):351-354.

[10] 唐杰,徐波,宮中樑,等.一種基于CUDA的三維點云快速光順算法[J].系統(tǒng)仿真學報,2012,24(8):1633-1637,1642.

[11]WangR,ChenW,ZhangS,etal.Similarity-baseddenoisingofpoint-sampledsurfaces[J].JournalofZhejiangUniversity-SCIENCEA,2008,9(6):807-815.

[12]PangXF,PangMY,SongZ.ExtractingFeatureCurvesonPointSets[J].InternationalJournalofInformationEngineeringandElectronicBusiness,2011,3(3):1-7.

[13]AltantsetsegE,MurakiY,MatsuyamaK,etal.FeaturelineextractionfromunorganizednoisypointcloudsusingtruncatedFourierseries[J].TheVisualComputer,2013,29(6):617-626.

[14]MérigotQ,OvsjanikovM,GuibasL.RobustVoronoi-basedCurvatureandFeatureEstimation[C]//2009SIAM/ACMJointConferenceonGeometricandPhysicalModeling,2009:1-12.

[15]FleishmanS,Cohen-OrD,SilvaCT.RobustMovingLeast-squaresFittingwithSharpFeatures[J].ACMTransactionsonGraphics(TOG),2005,24(3):544-552.

[16]ParkMK,LeeSJ,LeeKH.Multi-scaletensorvotingforfeatureextractionfromunstructuredpointclouds[J].GraphicalModels,2012,74(4):197-208.

[17] 王麗輝,袁保宗.魯棒的模糊C均值和點云雙邊濾波去噪[J].北京交通大學學報,2008,32(2):18-21.

[18] 張毅,劉旭敏,隋穎,等.基于k-近鄰點云去噪算法的改進與研究[J].計算機應(yīng)用,2009,29(4):1011-1014.

RESEARCH ON A NEW DENOISING ALGORITHM FOR 3D POINT CLOUD MODEL

Liao Changsu1He Dongjian2Wang Meili1*

1(CollegeofInformationEngineering,NorthwestA&FUniversity,Yangling712100,Shaanxi,China)2(MechanicalandElectronicEngineering,NorthwestA&FUniversity,Yangling712100,Shaanxi,China)

This paper proposes a denoising algorithm for 3D cloud model. The algorithm removes outlier noise point based on density filtering and vector information of points. Then, the boundary feature of the model is detected by the tensor voting algorithm and the uniformity of the projection of the nearest neighbors of the data points on the least squares plane, and the features can be enhanced. Finally, the model surface is smoothed by bilateral filtering. The experimental results show that the algorithm can effectively smooth the model and preserve and strengthen the boundary feature of the model to avoid the problem that the smooth operation of the model damages the model features.

3D point cloud Boundary detection Density filtering

2016-01-27。國家高技術(shù)研究發(fā)展計劃項目(2013AA102304)子課題；第56批中國博士后基金項目。廖昌粟，本科生，主研領(lǐng)域：圖形圖像處理。何東健，教授。王美麗，副教授。

TP317.4

A

10.3969/j.issn.1000-386x.2017.04.048