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

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

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

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

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

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

多頻相移;k均值聚類; 雙邊濾波; 點(diǎn)云; 曲率

0 引 言

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

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

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

1 三維點(diǎn)云去噪算法

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

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

(1)

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

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

1.2.1 孤立噪聲點(diǎn)剔除

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

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

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

(2)

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

dis(pi,pj)=

(3)

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

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

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

(4)

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

(5)

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

Q=Din(k)/Dout(k)

(6)

1.3 基于密度k-means大尺度噪聲點(diǎn)去除算法

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

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

(7)

3)由式(4)、式(5)、式(6)計(jì)算評(píng)價(jià)函數(shù)Qm。

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

(8)

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

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

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

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

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

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

(9)

a=

(10)

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

(11)

(12)

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與對(duì)比分析

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

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

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

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

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

圖2 不同去噪算法玉佩點(diǎn)云對(duì)比圖Fig 2 Comparison diagram of points cloud by different denoising algorithms

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

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

4 結(jié) 論

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

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

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

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

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

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

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

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

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

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

[16] 王 勇，唐 靖，饒勤菲，等.一種新的散亂點(diǎn)云快速去噪算法[J].計(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

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

TP 391.4

A

1000—9787(2016)07—0147—03

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