牛曉靜　王美麗　何東健

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

?

一種聚類與濾波融合的點云去噪平滑方法

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

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

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

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

0　引　言

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

1　相關(guān)工作

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

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

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

2　算法描述

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

2.1.1密度聚類算法

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

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

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

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

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

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

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

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

圖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ù)式(1)計算任意兩點之間的歐式距離。

(1)

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

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

(2)

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

(3)

distrange=maxdist-mindist

(4)

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

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

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

(5)

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

pNumi=count{dist(i,j)

(6)

那么：

pNum=count{pNumi≥MinPts|0≤i

(7)

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

2.2雙邊濾波方法

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

2.2.1法矢估計

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

2.2.2雙邊濾波因子

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

定義：

(8)

(9)

式中：N(qi)—數(shù)據(jù)點qi的鄰域。用標準高斯濾波進行平滑濾波，定義為：

(10)

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

(11)

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

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

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

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

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

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

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

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

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

3　實驗結(jié)果及分析

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

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

圖2　西紅柿點云模型處理效果

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

圖3　原始玉米點云　　圖4　玉米點云本文算法去噪光滑效果

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

圖5　原始玉米植株點云重建效果和局部放大效果

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

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

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

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

圖8　樹點云模型處理效果

圖9　小麥點云模型處理效果

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

表1　各點云模型去噪和平滑時間

4　結(jié)　語

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

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

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

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

[4] 黃文明,彭希為,溫佩芝,等.保留幾何特征的散亂點云簡化方法[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].機械科學(xué)與技術(shù),2006,25(4):410-414.

[8] 張三元,李強,張引.一種保持特征的三角網(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] 劉大峰,廖文和,戴寧,等.散亂點云去噪算法的研究與實現(xiàn)[J].東南大學(xué)學(xué)報:自然科學(xué)版,2007,37(6):1108-1112.

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

[13] 王麗輝,袁保宗.魯棒的模C均值和點云雙邊濾波去噪[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ù)分布點云去噪中的應(yīng)用[J].地理空間信息,2011,9(6):101-104.

[16] 劉彬,李夢瑞,林洪彬,等.基于正交投影約束的點模型去噪[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] 許斌,李忠科,呂培軍,等.基于特征的點云精確配準算法[J].計算機應(yīng)用與軟件,2013,30(11):112-114,122.

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

[20] 孫正林.三維激光掃描點云數(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ā)展計劃項目(2013AA 102304)；第56批中國博士后科學(xué)基金項目(2014M562457)。牛曉靜，碩士生，主研領(lǐng)域：計算機圖形學(xué)，圖像處理。王美麗，講師。何東健，教授。

TP3

A

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