一種聚類與濾波融合的點(diǎn)云去噪平滑方法

牛曉靜　王美麗　何東健

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

?

一種聚類與濾波融合的點(diǎn)云去噪平滑方法

牛曉靜1王美麗1何東健2*

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

針對采集的原始三維點(diǎn)云數(shù)據(jù)存在噪聲、表面不光滑不利于后期三維重建的問題，提出一種自適應(yīng)密度聚類與雙邊濾波融合的三維點(diǎn)云去噪平滑方法。該方法首先對點(diǎn)云模型進(jìn)行自適應(yīng)密度聚類分析，根據(jù)聚類結(jié)果刪除模型中的噪聲點(diǎn)；然后再計(jì)算采樣點(diǎn)的k鄰域，并求得利用k鄰域構(gòu)造采樣點(diǎn)所在平面的法矢，進(jìn)而得到雙邊濾波因子，以對點(diǎn)云模型進(jìn)行平滑。實(shí)驗(yàn)結(jié)果表明，該算法能有效識別并去除噪聲，并對點(diǎn)云模型進(jìn)行平滑，同時還能保持原始模型的特征信息。

點(diǎn)云去噪自適應(yīng)密度聚類k鄰域雙邊濾波特征保持

0　引　言

虛擬現(xiàn)實(shí)技術(shù)是當(dāng)前及將來影響人們生活的重要技術(shù)之一。隨著計(jì)算機(jī)圖形圖像技術(shù)的發(fā)展，虛擬模型在生活的各個方面有著廣闊的應(yīng)用前景。通過三維掃描儀等設(shè)備獲得真實(shí)世界作物的表面三維點(diǎn)云是一種普遍的三維重建方式。現(xiàn)有的三維掃描儀由于儀器本身的適應(yīng)性、人為因素、環(huán)境因素和測量方法等的影響，采集的三維點(diǎn)云中總包含噪聲，不能精確地表現(xiàn)被測作物的表面信息。三維點(diǎn)云中噪聲點(diǎn)的存在將影響后續(xù)特征點(diǎn)的提取精度和重建三維模型的質(zhì)量，導(dǎo)致重構(gòu)曲線、曲面不光滑，故研究保留尖銳特征的三維點(diǎn)云去噪方法對提高建模質(zhì)量具有重要的意義。

1　相關(guān)工作

近年來，國內(nèi)外學(xué)者們提出了多種點(diǎn)云模型的光順去噪算法，這些算法大多是來自圖像去噪和網(wǎng)格光順?biāo)惴╗1]，且主要與點(diǎn)云的排列形式密切相關(guān)[2]。羅才華等[3]討論了基于八叉樹模型的點(diǎn)云數(shù)據(jù)預(yù)處理方法，該方法對點(diǎn)云數(shù)據(jù)處理有較好的靈活性和適應(yīng)性。黃文明等[4]采用均勻柵格法劃分點(diǎn)云空間，進(jìn)而進(jìn)行散亂點(diǎn)云的簡化。該方法不僅能夠充分保留點(diǎn)云中的幾何特征，而且速度快；但隨著數(shù)據(jù)的增大，不能保持細(xì)小特征的完整性。Xiao等[5]利用kd-tree表示空間點(diǎn)云的拓?fù)潢P(guān)系進(jìn)行點(diǎn)云簡化，該方法有較高的運(yùn)行效率，且可避免漏洞。上述方法證明這三種拓?fù)潢P(guān)系對點(diǎn)云處理是有效的。本文采用八叉樹構(gòu)建點(diǎn)云之間的拓?fù)潢P(guān)系，以提高點(diǎn)云去噪平滑的效率。

在基于三角網(wǎng)格模型的降噪算法研究方面，Yu等[6]提出一種兩階段特征保持網(wǎng)格去噪框架。該方法可以在很好保持曲面網(wǎng)格特征的前提下取出噪聲，但不能精確處理容易被噪聲影響的細(xì)小特征。尹旺中等人[7]對模型中每個三角片的每個頂點(diǎn)分別求出其一鄰域內(nèi)所有三角片與當(dāng)前三角片法矢夾角的變化率，根據(jù)該變化率用拉普拉斯算子對三角片法矢進(jìn)行調(diào)整，進(jìn)而調(diào)整模型中各頂點(diǎn)位置。由于該方法是各向同性的，故存在重要特征模糊現(xiàn)象。張三元等[8]和Zheng等[9]將各向異性思想推廣到三角網(wǎng)格上，提出了各向異性網(wǎng)格光順?biāo)惴ā＿@些算法雖然能夠保持幾何特征，但通常采用高階幾何流，算法復(fù)雜度較高，有些情況下還會造成網(wǎng)格模型的變形和扭曲。Dutta等[10]提出一種改進(jìn)的三維幾何雙邊濾波方法，該算法可以在去除噪聲的同時保持對象的細(xì)節(jié)特征，并且克服了前人方法降低點(diǎn)云密度的缺點(diǎn)。但是該方法不能簡單地推廣到點(diǎn)云模型上。在直接針對點(diǎn)云數(shù)據(jù)的平滑處理方面，劉大峰等[11]提出一種快速去除散亂點(diǎn)云數(shù)據(jù)表面噪聲和離群點(diǎn)的魯棒濾波算法，但當(dāng)每一個點(diǎn)都獨(dú)立收斂于一個似然函數(shù)最大值時，并行問題沒有解決。杜小燕等[1]提出一種特征保持點(diǎn)云模型光順去噪算法，該算法通過調(diào)整采樣點(diǎn)在法向的位置實(shí)現(xiàn)局部的光順去噪，但是沒有涉及到振幅較大的奇異點(diǎn)的自動去除。葛寶臻等[12]提出的基于曲率信息混合分類的特征保持點(diǎn)云平滑算法將平面投影與雙邊濾波算法相結(jié)合，采用主成分分析法對點(diǎn)云的局部曲率特性進(jìn)行評價，可用于高密度點(diǎn)云數(shù)據(jù)的去噪；但該方法計(jì)算效率低。王麗輝等[13]將噪聲分為大尺度和小尺度分步處理，分別用模糊C均值聚類算法和雙邊濾波器對大、小尺度噪聲進(jìn)行光順。該方法計(jì)算效率較高，且避免了過光順問題，但對噪聲敏感會降低聚類結(jié)果的質(zhì)量。Park等人[14]通過近似擬合二次曲面實(shí)現(xiàn)點(diǎn)云的去噪，該方法依賴于魯棒的法向估計(jì)和基于投影的局部曲率，可很好地保持特征，效率也比較高；但是法向估計(jì)由于偏差的干擾可能會不準(zhǔn)確。

針對上述問題，本文提出一種自適應(yīng)密度聚類和雙邊濾波融合的三維點(diǎn)云數(shù)據(jù)去噪光滑算法。該算法對噪聲不敏感，可以去除任意形狀、大小的噪聲，同時也可在保持原始模型特征信息的前提下對模型進(jìn)行平滑。

2　算法描述

2.1自適應(yīng)密度聚類算法

2.1.1密度聚類算法

在獲取的點(diǎn)云數(shù)據(jù)中，除了目標(biāo)點(diǎn)云外，還有一些分布比較稀疏或孤立的噪聲點(diǎn)。而聚類算法可以實(shí)現(xiàn)類內(nèi)個體之間具有較大的相似性，類間個體間具有較大的相異性。在聚類算法中，選擇合適的閾值就可以將目標(biāo)點(diǎn)云分離，因此可以利用聚類方法進(jìn)行噪聲的去除?；诿芏鹊木垲愃惴▽㈩惗x為密度相連的點(diǎn)的最大集合，它本身對噪聲不敏感，能發(fā)現(xiàn)任意形狀、大小的類簇。該算法不依據(jù)距離進(jìn)行分類，克服了基于距離判別準(zhǔn)則只能發(fā)現(xiàn)“類圓形”聚類的限制[15]。故本文利用密度聚類方法對三維點(diǎn)云進(jìn)行聚類，從而在聚類結(jié)果中選擇出目標(biāo)點(diǎn)云主體，進(jìn)而實(shí)現(xiàn)噪聲的去除。

密度聚類的步驟如下(如圖1所示)：

1) 給定初始半徑e和最小鄰域數(shù)MinPts，并賦類號ClusterID為1；

2) 從待分類集合D中讀出一個未標(biāo)記的對象P，并查找D中關(guān)于e和MinPts的從P密度可達(dá)的所有對象；

3) 若P是核心對象(P的e鄰域內(nèi)至少包含MinPts個點(diǎn))，則對象P的類號賦值為ClusterID；如果P是一個邊界點(diǎn)(P不是核心點(diǎn)，但落在某個核心點(diǎn)的e鄰域內(nèi))，則對象P的類號賦值為0，并轉(zhuǎn)步驟2)；

4) 搜索所有與對象P密度可達(dá)的對象，將其類號賦值為ClusterID；從對象P密度可達(dá)的對象開始繼續(xù)搜索，直至無對象為止，將所有密度可達(dá)的對象賦值為ClusterID，ClusterID加1，并轉(zhuǎn)步驟2)；

5) 若待分類集合D中有未標(biāo)記的對象，轉(zhuǎn)步驟2)；

6) 判斷能否分離目標(biāo)點(diǎn)云，若能分離，則停止聚類；否則根據(jù)需要重新選擇新的初始半徑e和最小鄰域數(shù)MinPts進(jìn)行聚類。

圖1　自適應(yīng)密度聚類算法流程圖

2.1.2自適應(yīng)參數(shù)調(diào)整

在上述密度聚類步驟中，初始半徑e和最小鄰域數(shù)MinPts均為自定義參數(shù)。參數(shù)初始值設(shè)置好后，需要根據(jù)聚類效果不斷調(diào)整這兩個參數(shù)以獲得最好的聚類效果，比較耗時。為了解決這一問題，本文提出一種自適應(yīng)參數(shù)計(jì)算方法。

首先，根據(jù)式(1)計(jì)算任意兩點(diǎn)之間的歐式距離。

(1)

然后根據(jù)式(2)-式(3)求得dist(i,j)的最大值maxdist和最小值mindist，進(jìn)而根據(jù)式(4)求得距離間隔distrange。

maxdist=Max{dist(i,j)|0≤i

(2)

mindist=Min{dist(i,j)|0≤i

(3)

distrange=maxdist-mindist

(4)

其中，n表示點(diǎn)的數(shù)目。

將距離間隔等距分為十段，統(tǒng)計(jì)dist(i,j)在每段范圍內(nèi)的頻數(shù) ，初始半徑e的值即為erang所在分段的中值。erang的計(jì)算公式如式(5)所示。

erang=Max{pk|0≤k<10}

(5)

初始半徑e確定后，根據(jù)e逐步增大最小鄰域數(shù)目MinPts，計(jì)算鄰域超過最小鄰域數(shù)目的點(diǎn)的數(shù)目pNum(計(jì)算公式如式(7)所示)。隨著最小鄰域數(shù)目的增加，pNum會逐漸減少并趨于穩(wěn)定，選擇拐點(diǎn)所在的最小鄰域數(shù)目作為MinPts。其中，對于任意給定點(diǎn)p的鄰域點(diǎn)數(shù)目pNumi的計(jì)算如式(6)所示。

pNumi=count{dist(i,j)

(6)

那么：

pNum=count{pNumi≥MinPts|0≤i

(7)

通過該方法可以實(shí)現(xiàn)初始半徑和最小鄰域數(shù)的自動選擇，進(jìn)而避免這兩個參數(shù)的反復(fù)設(shè)置。

2.2雙邊濾波方法

利用自適應(yīng)密度聚類方法去除噪聲后，模型的表面仍然不是很光滑。為了保證后期三維重建效果，本文用雙邊濾波方法對點(diǎn)云模型進(jìn)行平滑。該方法的關(guān)鍵是法矢的估計(jì)和雙邊濾波因子的計(jì)算。

2.2.1法矢估計(jì)

設(shè)點(diǎn)云模型中所有點(diǎn)的集合為cloud，則與點(diǎn)p距離最近的k個點(diǎn)為p的k鄰域，記為N(p)，那么點(diǎn)云k近鄰的搜索就轉(zhuǎn)換為八叉樹近鄰的搜索。根據(jù)點(diǎn)云中每個點(diǎn)的空間位置，通過深度優(yōu)先遍歷找到每個點(diǎn)所在的葉子節(jié)點(diǎn)，通過搜索相鄰節(jié)點(diǎn)獲得每個點(diǎn)的k近鄰。然后通過最小二乘法[16-18]在N(p)內(nèi)構(gòu)造點(diǎn)p在N(p)上的切平面，記作T(p)。對于點(diǎn)云中的任意一點(diǎn)，其方向矢量等價于該點(diǎn)與其鄰域的最小二乘擬合平面的法向量[19]，所以T(p)的單位法矢即為點(diǎn)p處的單位法矢。

2.2.2雙邊濾波因子

雙邊濾波方法是一種保邊去噪的方法，首先用于消除圖像噪聲。在本文算法中，將雙邊濾波方法[20]用于三維點(diǎn)云數(shù)據(jù)的平滑中，在保持模型邊界的前提下，對模型表面進(jìn)行平滑。

定義：

(8)

(9)

式中：N(qi)—數(shù)據(jù)點(diǎn)qi的鄰域。用標(biāo)準(zhǔn)高斯濾波進(jìn)行平滑濾波，定義為：

(10)

特征保持權(quán)重函數(shù)類似于平滑濾波，定義為：

(11)

2.3自適應(yīng)密度聚類與雙邊濾波融合方法

將雙邊濾波用于經(jīng)自適應(yīng)密度聚類算法去噪后新數(shù)據(jù)點(diǎn)的平滑，算法步驟如下：

1) 對于每一個數(shù)據(jù)點(diǎn)qi，求出它的m個近鄰點(diǎn)kij，j=1,2,…,m;

2) 對于每個鄰近點(diǎn)，求出平滑濾波函數(shù)的參數(shù)x=‖qi-kij‖和特征保持權(quán)重函數(shù)的參數(shù)y=，其中x為點(diǎn)qi到鄰近點(diǎn)kij的距離，y為點(diǎn)qi與鄰近點(diǎn)的距離向量qi-kij與該點(diǎn)法向的內(nèi)積；

3) 按照式(10)和式(11)計(jì)算出平滑濾波函數(shù)Wc(x)和特征保持權(quán)重函數(shù)Ws(y)；

4) 將Wc(x)和Ws(y)代入式(9)，計(jì)算出雙邊濾波因子；

5) 根據(jù)式(8)計(jì)算得到濾波后的新數(shù)據(jù)點(diǎn)；

6) 所有數(shù)據(jù)點(diǎn)均更新后，程序結(jié)束。

雙邊濾波方法在平滑模型時考慮了鄰域點(diǎn)的影響，避免了過平滑現(xiàn)象的發(fā)生。

3　實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證本文算法的有效性，在Win 7平臺(CPU主頻3.20 GHz，內(nèi)存8 GB)上，基于Visual Studio 2010和OpenGL實(shí)現(xiàn)本文算法。使用西紅柿、玉米植株、樹和小麥點(diǎn)云模型對本文算法進(jìn)行驗(yàn)證。本文使用的模型均由scanstation 2激光掃描儀獲得。下述實(shí)驗(yàn)中，k鄰域的數(shù)目均為7。

在實(shí)驗(yàn)過程中，我們還對Laplace平滑算法和本文算法進(jìn)行了比較測試，主要在平滑效果上進(jìn)行比較。在用scanstation 2掃描的點(diǎn)云模型中存在很多噪聲點(diǎn)，如圖2中(a)所示的西紅柿原始點(diǎn)云模型。(b)是經(jīng)過本文算法去噪平滑后的點(diǎn)云效果(與原圖相比經(jīng)過旋轉(zhuǎn))，(c)是使用本文算法去噪后，再使用Laplace平滑方法獲得的效果，(d)-(f)分別是西紅柿點(diǎn)云去噪前、本文算法去噪平滑后和Laplace平滑后的重建效果。

圖2　西紅柿點(diǎn)云模型處理效果

使用本文提出的方法對玉米植株點(diǎn)云(如圖3所示)進(jìn)行去噪光滑的效果如圖4所示。

圖3　原始玉米點(diǎn)云　　圖4　玉米點(diǎn)云本文算法去噪光滑效果

圖5-圖7分別表示玉米原始點(diǎn)云、本文算法去噪平滑后和Laplace平滑后點(diǎn)云的重建效果和局部放大效果。

圖5　原始玉米植株點(diǎn)云重建效果和局部放大效果

圖6　玉米點(diǎn)云本文算法去噪光滑后的重建效果和局部放大效果

圖7　Laplace平滑后重建效果和局部放大效果

在圖2的(e)和(f)中，重建效果的差距并不明顯。但是從圖5-圖7的局部放大效果圖中可以發(fā)現(xiàn)，未經(jīng)去噪處理的點(diǎn)云模型中由于噪聲點(diǎn)的存在，使重建的表面不光滑，部分有凸起。點(diǎn)云去噪后，經(jīng)Laplace平滑方法處理過的點(diǎn)云模型中仍然存在部分小的凸起，表面也不是很光滑；而經(jīng)過本文算法去噪光滑的模型，重建效果要比Laplace平滑后的重建效果好。

利用本文提出的方法對樹和小麥的點(diǎn)云模型進(jìn)行處理的效果分別如圖8和圖9所示。

圖8　樹點(diǎn)云模型處理效果

圖9　小麥點(diǎn)云模型處理效果

表1為各模型去噪前后的點(diǎn)數(shù)和去噪平滑所用時間。在雙邊濾波平滑過程中，雖然避免了迭代計(jì)算，但是隨著數(shù)據(jù)量的增大，消耗時間仍較長。

表1　各點(diǎn)云模型去噪和平滑時間

4　結(jié)　語

本文提出了一種自適應(yīng)密度聚類與雙邊濾波融合的三維點(diǎn)云數(shù)據(jù)去噪平滑算法。通過密度聚類算法，可以有效去除模型中的噪聲點(diǎn)，而通過雙邊濾波方法可以實(shí)現(xiàn)點(diǎn)云平滑效果。本文提出的方法不需要迭代計(jì)算。實(shí)驗(yàn)結(jié)果表明，本文算法可以在保持模型特征的前提下有效去除三維點(diǎn)云數(shù)據(jù)中的噪聲，為后期三維點(diǎn)云分割及重建效果與質(zhì)量提供基礎(chǔ)。目前本文算法在近鄰搜索中耗時比較長，下一步的工作需要結(jié)合GPU編程進(jìn)一步提高算法的效率。

[1] 杜小燕,姜曉峰,郝傳剛,等.點(diǎn)云模型的雙邊濾波去噪算法[J].計(jì)算機(jī)應(yīng)用與軟件,2010,27(7):245-246,264.

[2] 樊宇,王宇楠.三維激光掃描點(diǎn)云數(shù)據(jù)預(yù)處理技術(shù)研究[J].科技創(chuàng)新導(dǎo)報,2011(32):27-28.

[3] 羅才華,周燕.基于八叉樹模型的三維點(diǎn)云數(shù)據(jù)預(yù)處理研究[J].福建電腦,2008,24(12):81-82.

[4] 黃文明,彭希為,溫佩芝,等.保留幾何特征的散亂點(diǎn)云簡化方法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(28):168-170,186.

[5] Xiao Z X,Huang W M.Kd-tree based non-uniform simplification of 3D point cloud[C]//Genetic and Evolutionary Computing,WGEC’09,3rd International Conference on.IEEE,2009:339-342.

[6] Yu J Z,Wei M Q,Qin J,et al.Feature-preserving mesh denoising via normal guided quadric error metrics[J].Optics and Lasers in Engineering,2014,62:57-68.

[7] 尹旺中,周來水,神會存,等.基于三角片法矢調(diào)整的三角網(wǎng)格模型光順[J].機(jī)械科學(xué)與技術(shù),2006,25(4):410-414.

[8] 張三元,李強(qiáng),張引.一種保持特征的三角網(wǎng)格去噪方法[J].中國科技論文在線,2010,5(2):129-132.

[9] Zheng Y Y,Fu H B,Au O K,et al.Bilateral normal filtering for mesh denoising[J].Visualization and Computer Graphics,IEEE Transactions on,2011,17(10):1521-1530.

[10] Dutta S,Banerjee S,Biswas P K,et al.Mesh denoising by improved 3D geometric bilateral filter[C]//Computer Vision,Pattern Recognition,Image Processing and Graphics (NCVPRIPG),2013 Fourth National Conference on.IEEE,2013:1-4.

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

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

[13] 王麗輝,袁保宗.魯棒的模C均值和點(diǎn)云雙邊濾波去噪[J].北京交通大學(xué)學(xué)報:自然科學(xué)版,2008,32(2):18-21.

[14] Park M K,Lee S J,Jang I Y,et al.Feature-aware filtering for point-set surface denoising[J].Computers and Graphics,2013,37(6):589-595.

[15] 張巧英,陳浩,朱爽.密度聚類算法在連續(xù)分布點(diǎn)云去噪中的應(yīng)用[J].地理空間信息,2011,9(6):101-104.

[16] 劉彬,李夢瑞,林洪彬,等.基于正交投影約束的點(diǎn)模型去噪[J].計(jì)算機(jī)工程,2012,38(20):264-267,271.

[17] Zhang L,Gu T Q,Zhao J,et al.An adaptive moving total least squares method for curve fitting[J].Measurement,2014,49:107-112.

[18] 許斌,李忠科,呂培軍,等.基于特征的點(diǎn)云精確配準(zhǔn)算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(11):112-114,122.

[19] 楊現(xiàn)輝,王惠南.ICP算法在3D點(diǎn)云配準(zhǔn)中的應(yīng)用研究[J].計(jì)算機(jī)仿真,2010,27(8):235-238.

[20] 孫正林.三維激光掃描點(diǎn)云數(shù)據(jù)濾波方法研究[D].長沙:中南大學(xué),2011.

A POINT CLOUD DENOISING AND SMOOTHING METHOD BASED ON FUSION OF CLUSTERING AND FILTERING

Niu Xiaojing1Wang Meili1He Dongjian2*

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

The original three-dimensional point cloud data collected has the problems of noise and unsmooth surface which is not conductive to three-dimensional post-reconstruction. In view of this, this paper presents a three-dimensional point cloud denoising and smoothing method, it is based on the fusion of adaptive density clustering algorithm and bilateral filtering. First, the method applies adaptive density clustering analysis on the point cloud model, and erases the noise points in the model according to clustering result. Then, it calculates the k neighbourhood of sampling point, and calculates the normal vector of the plane where the k neighbourhood is used to construct sampling points, and further obtains the bilateral filtering factor so as to smooth the point cloud model. Experimental results show that the proposed algorithm can identify and remove noise effectively and smoothes the point cloud model. At the same time, it can well keep characteristic information of the original model.

Point cloud denoisingAdaptive density clusteringK neighbourhoodBilateral filteringFeature preserving

2015-06-18。國家高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目(2013AA 102304)；第56批中國博士后科學(xué)基金項(xiàng)目(2014M562457)。牛曉靜，碩士生，主研領(lǐng)域：計(jì)算機(jī)圖形學(xué)，圖像處理。王美麗，講師。何東健，教授。

TP3

A

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