采用密度k-means和改進(jìn)雙邊濾波的點云自適應(yīng)去噪算法*

郭 進(jìn), 陳小寧, 呂峻閩, 徐鴻雁

(西南財經(jīng)大學(xué) 天府學(xué)院 信息技術(shù)中心,四川 綿陽 621000)

采用密度k-means和改進(jìn)雙邊濾波的點云自適應(yīng)去噪算法*

郭 進(jìn), 陳小寧, 呂峻閩, 徐鴻雁

(西南財經(jīng)大學(xué) 天府學(xué)院 信息技術(shù)中心,四川 綿陽 621000)

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

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

0 引 言

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

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

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

1 三維點云去噪算法

1.1 傳統(tǒng)k-means聚類原理

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

(1)

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

1.2 密度k-means點云聚類中心數(shù)確定

1.2.1 孤立噪聲點剔除

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

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

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

(2)

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

dis(pi,pj)=

(3)

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

1.2.2 類內(nèi)和類間距離比值的判斷準(zhǔn)則

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

(4)

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

(5)

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

Q=Din(k)/Dout(k)

(6)

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

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

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

(7)

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

4)合并類間距離最近的兩個點云簇，標(biāo)記新簇和新簇質(zhì)心

(8)

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

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

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

1.4 改進(jìn)型雙邊濾波的小尺度噪聲點去噪

1.4.1 傳統(tǒng)雙邊濾波點云去噪模型

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

(9)

a=

(10)

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

(11)

(12)

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

1.4.2 改進(jìn)型雙邊濾波點云去噪

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

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

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

2 本文算法優(yōu)點

本文算法主要實現(xiàn)了點云分類去噪，優(yōu)點表現(xiàn)為:

1)根據(jù)相移光柵匹配的原理快速建立點云拓?fù)浣Y(jié)構(gòu)。由極幾何約束和相位約束實現(xiàn)縱向和橫向的匹配，實現(xiàn)三維點與圖像點的映射。由此建立三維點云數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)的效率將大大提高，是k-d樹，八叉樹等算法無法相比的。

2)實現(xiàn)噪聲點的分類處理，將噪聲點區(qū)分為大尺度和小尺度，大尺度噪聲點分為了孤立噪聲和小片噪聲。從噪聲來源上進(jìn)行區(qū)分，針對不同原因產(chǎn)生的噪聲進(jìn)行不同的處理，很好實現(xiàn)點云去噪的自適應(yīng)處理。

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

3 實驗結(jié)果與對比分析

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

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

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

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

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

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

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

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

4 結(jié) 論

本文分析了結(jié)構(gòu)光測量系統(tǒng)的誤差和噪聲的來源，將噪聲點分為大尺度的孤立噪聲點和小片噪聲點，以及摻雜

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

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

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

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

[3] 吳蜀予，楊宜民，鐘震宇，等.光柵投影測量系統(tǒng)中的相位誤差校正算法[J].光學(xué)學(xué)報，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] 蘇志勛，栗志揚(yáng)，王小超.基于法向修正及中值濾波的點云平滑[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，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].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2009，21(6):812-818.

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

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

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

[13] 張 琳，陳 燕，汲 業(yè)，等.一種基于密度的K-means算法研究[J].計算機(jī)應(yīng)用研究，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算法最佳聚類數(shù)確定方法[J].計算機(jī)應(yīng)用，2010，30(8):1995-1998.

[16] 王 勇，唐 靖，饒勤菲，等.一種新的散亂點云快速去噪算法[J].計算機(jī)應(yīng)用與軟件，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

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