采用密度k-means和改進雙邊濾波的點云自適應去噪算法*

郭 進, 陳小寧, 呂峻閩, 徐鴻雁

(西南財經大學 天府學院 信息技術中心,四川 綿陽 621000)

采用密度k-means和改進雙邊濾波的點云自適應去噪算法*

郭 進, 陳小寧, 呂峻閩, 徐鴻雁

(西南財經大學 天府學院 信息技術中心,四川 綿陽 621000)

采用相移結構光測量系統得到的三維點云，不可避免存在噪聲。通過密度k均值(k-means)聚類算法將點云分為大尺度噪聲點和小尺度噪聲點，設定鄰域大小以及點的數量來去除孤立噪聲點；使用類內距離和類間距離的比值作為評價函數,得到最佳聚類數去除小片噪聲點云；對于混雜在真實點云中的小尺度噪聲點，采用魯棒性更強的改進型雙邊濾波器進行點云光順。實驗驗證表明:采用基于密度k-means和改進雙邊濾波結合的點云去噪算法可以有效去除各類噪聲點，保持點云特征，相比平均曲率算法和基于特征選擇的雙邊濾波算法，去噪效率分別提高了24 %和16 %。

多頻相移;k均值聚類; 雙邊濾波; 點云; 曲率

0 引 言

計算機視覺在逆向工程、工業檢測等領域中得到廣泛應用，獲取高精度點云模型成為研究熱點[1]。獲得三維點云數據的方式主要有激光和結構光測量，激光測量采用線掃描，得到噪聲較大的散亂點云；結構光測量采用面掃描，從格雷碼加相移，到基于時間相位的多頻相移[2]，得到有序點云，但也會引入噪聲。

基于相移結構光的測量系統在獲取點云過程中，會出現各種噪聲點，大尺度噪聲點表現為離散顆粒噪聲點，或者小片解相位誤差點云[3]；小尺度噪聲夾雜在真實點云當中，因為投影儀Gamma畸變[4]，以及測量系統的非線性誤差[5]而產生。學者們研究了例如卡爾曼濾波，Mean-Shift[6]等，蘇志勛[7]采用基于法向修正的中值濾波，但法向修正會出現誤差而影響迭代計算；肖春霞等人[8]實現基于平均曲率流的去噪，但屬于同性算法，不能很好地區分是高頻特征還是噪聲。去噪的同時要防止因算法導致細節過度丟失，學者們研究了基于各向異性的算法。范涵奇[9]通過魯棒統計理論計算點云表面幾何特征，在曲率空間對點云進行濾波，但對顆粒噪聲點識別不理想；宋陽等人[10]將C均值聚類和雙邊濾波相結合，達到了不錯的效果；葛寶臻[11]將平面投影與雙邊濾波結合實現點云自適應去噪，但在頂點曲率估計上有誤差；曹爽[12]采用基于特征選擇的雙邊濾波去噪，采用不同濾波因子去噪，但特征選擇過程時間較長。

各向異性算法得到了很大的改進，但很多無法有效識別噪聲類型。為了更好地識別噪聲類型，對尖銳的噪聲進行去除，保留點云特征，本文提出基于密度k-means和改進雙邊濾波的點云自適應去噪，針對大尺度噪聲點和小片噪聲點云，采用基于密度的k-means算法，通過設定鄰域以及計算該鄰域內點云數量來排除孤立點；采用類內和類間距離的比值作評價函數，確定最佳聚類數，設定閾值來排除小片噪聲點。針對小尺度噪聲點，采用改進型的雙邊濾波器進行各向異性平滑去噪，提高了去燥效率。

1 三維點云去噪算法

1.1 傳統k-means聚類原理

根據k-means聚類原理來排除大尺度噪聲點中的顆粒點和小片點云，從n個點的數據集{p1,p2,p3,…，pn}中，找出k個聚類中心{a1,a2,a3,…，ak}簇，使聚類后的每片對象具有很高相似度。開始從n個待聚類的對象中隨機選擇k個作為初始值，再根據所有對象離每個聚類中心的距離分配到最近的中心，計算新聚類中心簇的質心，取平均距離，進行迭代，直到目標函數收斂后實現聚類

(1)

式中 Wn為數據集{p1,p2,p3,…，pn}中所有對象與它所在的聚類中心的平方誤差之和，ai為聚類中心的均值，pj為每個聚類中的對象。

1.2 密度k-means點云聚類中心數確定

1.2.1 孤立噪聲點剔除

定義P={p1,p2,p3,…，pn},P∈R3為三維空間的點云集，n為點云總個數，密度為pi的鄰域內點的數量。定義鄰域為以pi為中心，半徑為E的三維球體

Z(pi)={pi∈P|0≤dis(pi,pj)≤E,

i=1,2,…,n,j=1,2,…，n}

(2)

式中dis(pi,pj)為鄰域內兩個點的歐氏距離

dis(pi,pj)=

(3)

通過經驗值確定半徑E，以及鄰域最少三維點個數minp，求點云集中每個三維點的密度，根據minp值判斷哪些是顆粒噪聲點ns，哪些是集合點np，將顆粒點從樣本中刪除，實現大尺度噪聲點剔除，數據集減少為n-ns。再遍歷三維點數據，根據標記判斷三維點pi是否有相同的集合點，如果有則只保留一個作為集合點，并標記重復個數為nc，再將np-nc作為初始聚類的樣本個數值m。

1.2.2 類內和類間距離比值的判斷準則

采用類內和類間距離比值作為評價準則。定義類內距離Din(k)為每個三維點到同一個簇中其它三維點的平均距離的最小值。而整個點云的類內距離為所有簇中類內距離最大值

(4)

定義類間距離Dout(k)為不同聚類中心簇的最近兩個三維點的距離

(5)

評價函數定義如下，比值越小說明聚類效果越好

Q=Din(k)/Dout(k)

(6)

1.3 基于密度k-means大尺度噪聲點去除算法

1)按照1.2節的方法首先確定點云初始聚類個數m=np-nc，聚類中心ai(i=1,2,…,m)，排除顆粒噪聲點。

2)計算三維點與各個聚類中心簇的距離，按照距離最近原則進行聚類，更新新簇質心

(7)

3)由式(4)、式(5)、式(6)計算評價函數Qm。

4)合并類間距離最近的兩個點云簇，標記新簇和新簇質心

(8)

5)重復步驟(2)～(4)，直至m=1。

6)查找步驟(1)～(5)過程中計算的Qm，確定最佳聚類數，選擇最小的Qm，從m個點云簇中，判斷每個點云個數是否都不小于minp，若是則m為最佳聚類數k，若不是則舍棄該Qm，再重復步驟(6)。

7)得到了最佳聚類數，再根據設定的噪聲點閾值數去除小片噪聲點。

1.4 改進型雙邊濾波的小尺度噪聲點去噪

1.4.1 傳統雙邊濾波點云去噪模型

傳統雙邊濾波器首先估計點云法向和曲率，再根據濾波因子計算三維點的偏移量，移動各點到新的位置。雙邊濾波定義為

(9)

a=

(10)

式中 N為pi的鄰域，Wc為pi到鄰域的光順濾波因子，Ws為pi到鄰域在法向上的特征保持因子，ni和nj為pi和pj的法相量

(11)

(12)

式中 σc和σs為高斯參數，σc為控制光順程度，σs為控制特征保持程度。使用雙邊濾波算法實現對點云中小尺度噪聲點的各向異性去噪，有效去噪的同時達到很好地保留特征效果。

1.4.2 改進型雙邊濾波點云去噪

本文對傳統雙邊濾波因子進行改進，采用法向夾角的余弦值作為特征保持因子，在鄰域內采樣點的法向變化能夠反映特征變化，點云特征變化大的地方，曲率變化大，對應法向變化也大；特征變化小的地方，比較平坦，曲率變化小，對應法向變化也小，因此，采用法向夾角作為特征保持因子能夠在特征變化大的地方凸顯出來。

1)當鄰域點與當前計算的點的法向夾角在0°～90°的時候，其余弦值隨夾角變大而變小，雙邊濾波器的特征保持權值也隨夾角變大而減小。

2)當鄰域點與當前計算的點的法向夾角大于90°時，認為該點對當前點不再有影響，令特征保持權值為0。

2 本文算法優點

本文算法主要實現了點云分類去噪，優點表現為:

1)根據相移光柵匹配的原理快速建立點云拓撲結構。由極幾何約束和相位約束實現縱向和橫向的匹配，實現三維點與圖像點的映射。由此建立三維點云數據拓撲結構的效率將大大提高，是k-d樹，八叉樹等算法無法相比的。

2)實現噪聲點的分類處理，將噪聲點區分為大尺度和小尺度，大尺度噪聲點分為了孤立噪聲和小片噪聲。從噪聲來源上進行區分，針對不同原因產生的噪聲進行不同的處理，很好實現點云去噪的自適應處理。

3)采用改進雙邊濾波使得特征保持權重因子被限定在一個更加合理的范圍，能夠增強特征保持性，再計算其多個鄰域點法向夾角的時候，隱式的引入了多個濾波平面，也能夠增強數據點的抗噪性能，改善濾波效果。

3 實驗結果與對比分析

為了驗證實驗結果，選用加噪的平面點云進行實驗，驗證算法有效性，再選擇牙模和掛墜的點云數據進行對比實驗，驗證算法的效率。

圖1 去除大尺度噪聲點效果圖Fig 1 Effect diagram of removing large scale noise point

采用本文算法對加了噪聲的平面點云進行去噪處理，圖1(a)為含大量顆粒噪聲點的大尺度噪聲點云，圖1(b)為采用密度k-means處理后的點云，大尺度的噪聲點已經全部清除。

為了進一步驗證算法的有效性，選取了噪聲點較多的掛墜玉佩點云(噪聲點數為2 000)以及特征較多的義齒牙模點云，將本文算法和平均曲率流，基于特征選擇的雙邊濾波算法進行對比實驗。

圖2(a)～圖2(d)為經過不同去噪算法處理后的效果圖，圖2(a)為原始點云，噪聲分布在點云的周圍，圖2(b)為采用平均曲率流去噪后得到的點云，僅能去除一些顆粒噪聲點，對小片噪聲點處理效果不佳，圖2(c)為基于特征選擇的雙邊濾波去噪算法得到的點云，距離較近的小片噪聲點云無法剔除，圖2(d)為本文算法，噪聲點去除效果較好。從表1可以看出，針對該點云數據，平均曲率流算法的去噪效率為70 %，基于特征選擇的雙邊濾波為78%，而本文的去噪效率為94 %，大大降低了噪聲點。

圖2 不同去噪算法玉佩點云對比圖Fig 2 Comparison diagram of points cloud by different denoising algorithms

點云模型玉佩點云(噪聲點2000)玉佩三角面個數去噪點點云去噪效率/%原始點云14834229265700平均曲率146936290824140670特征選擇雙邊濾波146770289914157278本文算法146457289831188594

通過對特征比較豐富的義齒模型進行對比實驗，觀察點云曲率變化較大的地方經過不同去噪算法處理后特征保持效果。圖3(a)為原始點云，直接三角化后牙齒特征放大圖示，圖中可以看出該牙齒部分噪聲較多，圖3(b)為經過平均曲率流算法處理后的點云牙齒三角化放大圖示，相比圖3(a)去噪效果明顯，但在牙齒的曲率變化比較大的地方，丟失了細節。圖3(c)為雙邊濾波算法處理后牙齒三角化放大圖示，相對于圖3(a)去噪效果也較明顯，相對于圖3(b)特征保持較好。圖3(d)為本文算法采用的改進型雙邊濾波，相對于圖3(a)達到了更好的去噪效果，相對于圖3(b)和圖3(d)又更好保持了點云特征，尤其是曲率變化較大的細節。

4 結 論

本文分析了結構光測量系統的誤差和噪聲的來源，將噪聲點分為大尺度的孤立噪聲點和小片噪聲點，以及摻雜

圖3 不同去噪算法義齒點云三角面對比圖Fig 3 Comparison diagram of denture points cloud by different denoising algorithms

在點云當中的小尺度噪聲。提出了基于密度k-means和改進雙邊濾波相結合的點云去噪算法，針對大尺度點云，采用基于密度k-means聚類算法剔除，使用改進型雙邊濾波器對小尺度噪聲點進行去噪，在去噪平滑的同時較好保留了點云特征。相比平均曲率算法和基于特征選擇的雙邊濾波算法實驗證明去噪效率大大提高，可以有效提高去噪準確度。

[1] 張曉娟，李忠科，王先澤，等.基于特征點和改進ICP的三維點云數據配準算法[J].傳感器與微系統，2012，31(9)：116-122.

[2] 黃亞楠，婁小平.基于多頻外差原理的相位校正及匹配方法研究[J].應用光學，2014，2(2):237-241.

[3] 吳蜀予，楊宜民，鐘震宇，等.光柵投影測量系統中的相位誤差校正算法[J].光學學報，2014，7(7):123-128.

[4] Li Zhongwei,Fu You.Gamma-distorted fringe image modeling and accurate gamma correction for fast phase measuring profilo-metry[J].Optics Letters,2011,36(2):154-156.

[5] Xu Ying,Ekstrand Laura,Dai Junfei.Phase error compensation for three-dimensional shape measurement with projector defocu-sing[J].Appl Opt,2011,50(17):2578-2581.

[6] Song J.Two-stage point-sampled model denoising by robust ellipsoid criterion and mean shift[C]∥2013 Int’l Conf on Intelligent System Design and Engineering Applications,Hong Kong:IEEE,2013:1581-1584.

[7] 蘇志勛，栗志揚，王小超.基于法向修正及中值濾波的點云平滑[J].計算機輔助設計與圖形學學報，2010，22(11):1892-1898.

[8] Xiao Chunxia,Miao Yongwei,Liu Shu,et al.A dynamic balanced flow for filtering point-sampled geometry[J].The Visual Compu-ter,2006,22(3):210-219.

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

[10] 宋 陽，李昌華，馬宗方，等.應用于三維點云數據去噪的改進C均值算法[J].計算機工程與應用，2015，51(12):1-4.

[11] 葛寶臻，項 晨，田慶國.基于曲率特征混合分類的高密度點云去噪方法[J].納米技術與精密工程，2012，10(1):64-67.

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

[13] 張 琳，陳 燕，汲 業，等.一種基于密度的K-means算法研究[J].計算機應用研究，2011，28(11):4071-4073.

[14] Fu Desheng,Zhou C.Improvedk-means algorithm and its implementation based on density[J].Journal of Computer Applications,2011,31(2):432-434.

[15] 周世兵，徐振源，唐旭清.K-means算法最佳聚類數確定方法[J].計算機應用，2010，30(8):1995-1998.

[16] 王 勇，唐 靖，饒勤菲，等.一種新的散亂點云快速去噪算法[J].計算機應用與軟件，2015,23(7):74-78.

Points cloud self-adaptive denoising algorithm based on densityk-means and improved bilateral fitering*

GUO Jin, CHEN Xiao-ning, Lü Jun-min, XU Hong-yan

(Tian Fu College of Southwestern University of Finance and Economic,Mianyang 621000,China)

3D points cloud gained by using phase-shift measurement system unavoidably has noise.Cloud-point is divided into large scale noise points and small scale noise points by densityk-means clustering algorithm,isolated noise points is removed by setting neighbourhood size and quantity of points;take ratio of intraclass distance and between-class distance as evaluation function obtain the optimal number of clusters to remove little noise points cloud.Using stronger robustness improved bilateral filterer for points cloud.Experiment shows that point clouds de-noising algorithm combines densityk-means and improved bilateral filtering can effectively remove noises point,maintain point cloud features.Compared to mean curvature algorithm and the bilateral filtering algorithm based on feature selection,the de-noising efficiency are improved around 24 % and 16 %.

multiple frequency phase-shift;k-means clustering; bilateral filtering; points cloud; curvity

10.13873/J.1000—9787(2016)07—0147—03

2016—05—06

四川省教育廳一般項目(15ZB0475,13ZB0377)

TP 391.4

A

1000—9787(2016)07—0147—03

郭 進(1982-)，男，四川郫縣人，碩士，講師，從事機器視覺、數字圖像處理、三維光學測量方面工作。