基于改進(jìn)DPC和特征分區(qū)的點(diǎn)云去噪算法

耿 蜜,朱 攀,周興林

(1.武漢科技大學(xué) 冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室,湖北 武漢 430081；2.武漢科技大學(xué) 機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室,湖北 武漢 430081)

1 引 言

隨著三維激光掃描技術(shù)的發(fā)展完善及各種掃描設(shè)備的日益普及,三維點(diǎn)云已經(jīng)成為一種常見的空間三維物體的表示信號(hào)。三維激光掃描因其測(cè)量精度高、數(shù)據(jù)獲取快、適用場(chǎng)合多等諸多優(yōu)勢(shì)被廣泛應(yīng)用于地形勘測(cè)、文物保護(hù)、計(jì)算機(jī)視覺、無人駕駛等各個(gè)領(lǐng)域[1-3],通過對(duì)掃描儀采集到的物體表面信息點(diǎn)云進(jìn)行逆向建模從而實(shí)現(xiàn)物體復(fù)現(xiàn)。然而受限于儀器精度、被測(cè)物件復(fù)雜度、環(huán)境干擾、人為操作誤差等因素,獲取的點(diǎn)云數(shù)據(jù)通常包含著部分噪聲,這些噪聲將嚴(yán)重影響后續(xù)的數(shù)據(jù)處理工作,因此點(diǎn)云去噪工作成為了點(diǎn)云逆向建模中不可或缺的一環(huán)。

點(diǎn)云去噪在近年來一直是一個(gè)備受國(guó)內(nèi)外學(xué)者關(guān)注的研究課題,去噪算法也是種類繁多,各有所長(zhǎng):Fleishman[4]等將圖像雙邊濾波引入點(diǎn)云去噪,通過使用局部鄰域信息對(duì)點(diǎn)進(jìn)行沿法矢方向的偏移實(shí)現(xiàn)了光順效果,但無法處理較大誤差的離群點(diǎn)且易造成過光順。Mattei[5]等受圖像稀疏去噪啟發(fā),通過加權(quán)L1最小化點(diǎn)偏離局部參考平面從而保持點(diǎn)云尖銳特征,去噪性能優(yōu)異但在高噪聲下計(jì)算量顯著增大且法矢方向可能出現(xiàn)錯(cuò)誤。Rakotosaona[6]等提出一種基于深度學(xué)習(xí)的PCN去噪框架,該框架無需預(yù)先設(shè)置參數(shù),通過去除離群點(diǎn)并對(duì)剩余點(diǎn)修正達(dá)到去噪效果,但相應(yīng)地需要成對(duì)的干凈噪聲訓(xùn)練數(shù)據(jù),且噪聲特性與訓(xùn)練數(shù)據(jù)不同時(shí)效果較差。Zeng[7]等利用曲面塊的自相似性,引入低維流形模型并通過圖維拉普拉斯正則化最小化流形維數(shù)達(dá)到去噪效果,但計(jì)算復(fù)雜度較高。Zhou[8]等提出一種非迭代雙閾值去噪方法,對(duì)點(diǎn)云進(jìn)行分層處理,去噪速度快且魯棒性強(qiáng),但特征保持度欠佳。王曉輝[9]等通過點(diǎn)到擬合平面的法向距離對(duì)點(diǎn)進(jìn)行劃分,并分別采用加權(quán)局部最優(yōu)投影和雙邊濾波對(duì)不同區(qū)域點(diǎn)去噪,改善點(diǎn)云分布均勻性的同時(shí)保持了尖銳特征。柳赟[10]等基于主成分分析與曲面擬合原理,通過法矢粗去噪后進(jìn)行曲面擬合,再根據(jù)點(diǎn)到擬合曲面距離精去噪,對(duì)于平坦區(qū)域具有較好的去噪效果。趙夫群[11]等采用層次化的去噪方案,首先基于張量投票完成點(diǎn)云初始去噪,然后通過設(shè)置曲率閾值剔除異常點(diǎn)實(shí)現(xiàn)精細(xì)去噪,該算法復(fù)雜度較低,執(zhí)行效率高。魏碩[12]等通過kd樹求取點(diǎn)云密度并設(shè)置閾值粗去噪,然后融合改進(jìn)DBSCAN和統(tǒng)計(jì)濾波對(duì)數(shù)據(jù)進(jìn)行精細(xì)去噪,性能優(yōu)于傳統(tǒng)的半徑濾波且參數(shù)自適應(yīng)能力強(qiáng)。

從近年來點(diǎn)云去噪方法的發(fā)展趨勢(shì)不難看出,單種去噪方法難以滿足復(fù)雜的去噪環(huán)境需求,融合型去噪方案更具普適性,因此本文提出了一種綜合性的去噪方案,通過對(duì)點(diǎn)云噪聲進(jìn)行分尺度、分區(qū)域地去除,從而實(shí)現(xiàn)對(duì)包含混合噪聲的點(diǎn)云數(shù)據(jù)的適應(yīng)性。

2 算法描述

本文首先通過改進(jìn)的密度峰值聚類去除大尺度噪聲,得到粗去噪數(shù)據(jù)后根據(jù)點(diǎn)的曲率等信息進(jìn)行特征判斷分區(qū),對(duì)不同區(qū)域的點(diǎn)云采取相應(yīng)的去噪算法,具體的去噪流程如圖1所示。

圖1 去噪算法流程圖Fig.1 Denoising algorithm flow chart

2.1 密度峰值聚類算法相關(guān)概念

2.1.1局部密度ρi

局部密度是指點(diǎn)pi在以dc為半徑的圓內(nèi)的鄰域點(diǎn)個(gè)數(shù),即:

(1)

2.1.2 最鄰高密度點(diǎn)距離δi

該距離為點(diǎn)pi與局部密度大于它的點(diǎn)的最小距離,即:

(2)

2.1.3 兩個(gè)假設(shè)

DPC(Clustering by fast search and find of density peaks)算法[13]認(rèn)為:聚類中心周圍的鄰域點(diǎn)的局部密度較小；聚類中心與局部密度較大的點(diǎn)的距離較遠(yuǎn)。

2.1.4 改進(jìn)的DPC算法

DPC算法基于歐氏距離及密度對(duì)數(shù)據(jù)進(jìn)行分類,不僅可以完成任意形狀任意維數(shù)數(shù)據(jù)的聚類,同時(shí)能夠發(fā)現(xiàn)并剔除異常點(diǎn),但需要計(jì)算任意兩點(diǎn)間距離,計(jì)算開銷較大,且聚類中心需要通過觀察pi及δi的決策圖進(jìn)行人工選取,提高了算法的冗余度。

為了克服DPC算法的不足,本文對(duì)數(shù)據(jù)進(jìn)行分組降低數(shù)據(jù)量從而提高運(yùn)行效率,在此基礎(chǔ)上引入文獻(xiàn)[14]中簇中心權(quán)值γi,從而實(shí)現(xiàn)簇中心點(diǎn)的自動(dòng)選取。

改進(jìn)后的DPC去噪具體步驟如下:

(1)首先對(duì)原始點(diǎn)云數(shù)據(jù)進(jìn)行分組,根據(jù)樣本數(shù)N確定分組數(shù)n,由表1可以得出:為保證最佳運(yùn)行效率,n取[N/1000],然后對(duì)分組后各組數(shù)據(jù)進(jìn)行步驟(2)～(6)處理。

表1 不同分組數(shù)下DPC算法運(yùn)行時(shí)間Tab.1 Running time of DPC algorithm under different number of packets

(2).計(jì)算各點(diǎn)間距離并作升序排列,截?cái)嗑嚯xdc取前2%處數(shù)值并計(jì)算各點(diǎn)的ρi和δi。

(3).對(duì)ρi和δi作降序排列,根據(jù)噪聲高低設(shè)置噪點(diǎn)判斷閾值s,將δi位于前s%且ρi位于后s%的點(diǎn)標(biāo)記為噪點(diǎn)。對(duì)bunny點(diǎn)云添加信噪比RSN為10 dB的隨機(jī)噪聲并在不同s值下利用改進(jìn)的DPC進(jìn)行去噪,結(jié)果如圖2所示,可以看出:當(dāng)s為95時(shí),仍殘留著部分噪聲點(diǎn)；而當(dāng)s=75時(shí),部分邊緣也被當(dāng)作噪聲去除；s=85時(shí)去噪效果較好。因此通常情況下s取值應(yīng)略小于(100-RSN)。

圖2 閾值s取不同值下DPC算法粗去噪效果Fig.2 Coarse denoising effect of DPC algorithm with different threshold s

(5)將剩余各點(diǎn)分配到距離它最近的局部密度比它高的點(diǎn)所屬的簇。

(6)各點(diǎn)分配完成后對(duì)各簇包含點(diǎn)數(shù)進(jìn)行判斷,設(shè)定閾值nmin,通常取nmin為25～30,將點(diǎn)數(shù)量小于nmin的簇標(biāo)記為群聚噪點(diǎn)。

(7)去除各組標(biāo)記噪點(diǎn)后合并數(shù)據(jù),得到粗去噪數(shù)據(jù)。

2.2 點(diǎn)云法矢及曲率估算

在對(duì)原始點(diǎn)云數(shù)據(jù)進(jìn)行大尺度去噪后,我們需要進(jìn)一步去除距離點(diǎn)云主體較近的小尺度噪聲,然而這些噪點(diǎn)難以僅僅通過點(diǎn)的三維坐標(biāo)信息進(jìn)行區(qū)分,因此需要通過估算點(diǎn)的法矢及曲率作為點(diǎn)的信息補(bǔ)充。

2.2.1 點(diǎn)云法矢估算

本文采用常用的主成元分析法(PCA)進(jìn)行法矢估計(jì),給定粗去噪后的點(diǎn)集P={pi,i∈1,2,…,n},pi∈R3中的點(diǎn)pi及其k鄰域N(pi)={pj,j∈1,2,…,k},pj∈P,得到點(diǎn)pi的協(xié)方差矩陣C(pi):

(3)

2.2.2 法矢方向調(diào)整

通常情況下由PCA得到的點(diǎn)的法矢會(huì)零散地指向點(diǎn)云主體的不同側(cè),這會(huì)嚴(yán)重影響后續(xù)去噪的準(zhǔn)確性,因此需要對(duì)法矢方向進(jìn)行一致性調(diào)整。而目前常用的最小生成樹法效率低下,難以應(yīng)用于數(shù)據(jù)量較大的點(diǎn)云數(shù)據(jù),因此本文提出一種基于鄰域傳播的法矢修正法,相較于傳統(tǒng)的最小樹生成法,降低了調(diào)整時(shí)的搜索范圍且逐步增加傳播點(diǎn)個(gè)數(shù),極大地提高了法矢調(diào)整的效率,主要流程如圖3所示。

圖3 法矢方向一致性調(diào)整流程圖Fig.3 Flow chart of normal vector direction consistency adjustment

首先選取法矢?jìng)鞑テ鹗键c(diǎn),這里選取z軸坐標(biāo)最大的點(diǎn)作為起始點(diǎn),依據(jù)其法向量n與[0,0,1]的內(nèi)積大于0進(jìn)行方向調(diào)整；確定起始點(diǎn)后按照上圖流程依次對(duì)其鄰域各點(diǎn)法矢進(jìn)行調(diào)整,調(diào)整基于相鄰點(diǎn)法矢夾角小于90°這一規(guī)則進(jìn)行,至此完成一次調(diào)整循環(huán),隨后更新法矢?jìng)鞑c(diǎn),再次循環(huán)直到所有點(diǎn)調(diào)整完畢。

2.2.3 點(diǎn)云曲率估算

由特征矩陣C得到的特征值λ1代表著法矢α1的偏移量,即數(shù)據(jù)點(diǎn)相對(duì)其切平面的偏移程度,因此引入曲面變分[15]r近似代替曲率R來表征局部區(qū)域的幾何特征,其表達(dá)式為:

(4)

2.3 小尺度噪聲去除

為了在保證特征信息損失較小的前提下去除小尺度噪聲,需要對(duì)點(diǎn)云進(jìn)行特征判斷分區(qū),對(duì)不同區(qū)域點(diǎn)云采用不同的去噪算法以達(dá)到最佳去噪效果。

本文基于點(diǎn)曲率及其標(biāo)準(zhǔn)差對(duì)點(diǎn)云進(jìn)行特征劃分,已知點(diǎn)pi的曲率為Ri,其鄰域內(nèi)的平均曲率為:

鄰域點(diǎn)曲率標(biāo)準(zhǔn)差為:

則定義特征判斷值e:

(5)

2.3.1 平坦區(qū)域噪聲去除

針對(duì)平坦區(qū)域點(diǎn)云,使用基于平面擬合的去噪方法較為合適,通過計(jì)算各點(diǎn)到擬合平面距離并設(shè)定閾值剔除噪聲。因此選擇兼顧自變量與因變量誤差的正交整體最小二乘法[16]進(jìn)行平面擬合,具體步驟如下:

(1)建立擬合平面模型

(6)

(2)由式(3)的協(xié)方差矩陣C特征分解求得的特征值λ1對(duì)應(yīng)的特征向量α1即為a,b,c的值。

(3)計(jì)算點(diǎn)到擬合平面距離di

(7)

(4)根據(jù)儀器精度ε設(shè)置距離閾值dmax,當(dāng)di>dmax時(shí),將該點(diǎn)作為噪點(diǎn)刪除,反之保留。

2.3.2 特征區(qū)域噪聲修正

在特征區(qū)域,選擇特征保持效果較好的雙邊濾波[4]并加以改進(jìn),通過為高斯濾波參數(shù)添加特征權(quán)實(shí)現(xiàn)參數(shù)自適應(yīng)選擇。該方法利用點(diǎn)鄰域信息對(duì)數(shù)據(jù)點(diǎn)云進(jìn)行法矢方向的移動(dòng)從而修正點(diǎn)坐標(biāo)位置達(dá)到光順效果,在雙邊濾波中:

p′=p+α·n

(8)

其中,α為雙邊濾波因子;根據(jù)α及法矢n對(duì)原始坐標(biāo)p進(jìn)行調(diào)整得到新的坐標(biāo)p′,α的計(jì)算公式如下:

(9)

(10)

(11)

其中,k為采樣點(diǎn)p鄰域中點(diǎn)個(gè)數(shù);pi為鄰域點(diǎn);ωc,ωs分別為光順濾波權(quán)函數(shù)和特征保持權(quán)函數(shù),控制兩個(gè)函數(shù)大小的參數(shù)σc和σs分別對(duì)應(yīng)著雙邊濾波的光順程度和特征保持度,通常情況下,σc取鄰域半徑:

σc=max‖p-pi‖

(12)

當(dāng)σc確定后,σs的取值對(duì)平滑效果影響較大,σs越大,代表p的法向修正距離越大,平滑程度越大,因此令:

σs=t·σc

(13)

(14)

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

本文選取特征豐富的bunny點(diǎn)云和以平面為主的block點(diǎn)云進(jìn)行去噪實(shí)驗(yàn),并將實(shí)驗(yàn)結(jié)果與通過正交整體最小二乘法和雙邊濾波去噪后的效果進(jìn)行對(duì)比。圖4、5分別為bunny和block兩個(gè)點(diǎn)云模型在不同算法下的去噪效果圖。對(duì)于特征較多的bunny點(diǎn)云模型,從圖4(b)可以看出,僅采用正交整體最小二乘法去噪后雖然整體平滑程度提高,但特征細(xì)節(jié)損失較為嚴(yán)重,在圖4(c)中,僅使用雙邊濾波去噪后,光順度有一定程度提高,特征保持效果也較好,但無法去除遠(yuǎn)離主體的大尺度噪聲且噪聲污染嚴(yán)重區(qū)域整體光順度較差,而圖4(d)中采用本文算法去噪后,可以看到模型整體無明顯噪聲,模型表面輪廓特征清晰,光順度也較好。對(duì)以平面為主的block點(diǎn)云模型,圖5(b)中,僅采用正交整體最小二乘法去噪后,光順效果好,僅在邊緣尖銳處有部分損失,圖5(c)中雙邊濾波去噪同樣無法去除大尺度噪聲,且光順效果較差,圖5(d)中本文算法去噪后,模型光順效果較好且尖銳特征得到保留,僅在噪聲污染嚴(yán)重處有小幅波紋。

圖4 不同去噪算法下bunny點(diǎn)云去噪重構(gòu)模型效果對(duì)比圖Fig.4 Comparison of the rabbit point cloud denoising reconstruction model under different denoising algorithms

圖5 不同去噪算法下block點(diǎn)云去噪重構(gòu)模型效果對(duì)比圖Fig.5 Comparison of the block point cloud denoising reconstruction model under different denoising algorithms

綜合圖4、5的結(jié)果對(duì)比可以看出,正交整體最小二乘法對(duì)于平面光順效果較好,但特征保持不佳,雙邊濾波則受大尺度噪聲影響較大,而本文算法能夠同時(shí)處理大小尺度噪聲,針對(duì)各類點(diǎn)云模型均能兼顧光順及特征保持效果,具有良好的適應(yīng)性。

為了進(jìn)一步衡量本文算法的去噪性能,還需要引入多種定量評(píng)價(jià)指標(biāo)驗(yàn)證算法的可行性。點(diǎn)的坐標(biāo)誤差可以直接反映去噪效果的好壞,而在特征保持度上,本文引入信息熵[17]作為評(píng)判標(biāo)準(zhǔn),點(diǎn)的信息熵取決于所在區(qū)域的無序程度,因此可以用于描述點(diǎn)的特征豐富度。去噪時(shí)間則決定著算法的運(yùn)行效率,因此本文通過最大誤差、平均誤差、點(diǎn)平均信息熵、去噪時(shí)間這四個(gè)評(píng)價(jià)指標(biāo)來對(duì)去噪結(jié)果進(jìn)行更加客觀的分析。平均信息熵的計(jì)算公式為:

(15)

(16)

(17)

(18)

不同去噪算法下計(jì)算結(jié)果如表2所示。

表2 不同去噪算法客觀評(píng)價(jià)對(duì)比Tab.2 Objective evaluation and comparison of different denoising algorithms

從表2可以看出,本文算法對(duì)兩組點(diǎn)云去噪后的最大誤差與平均誤差均小于另兩種算法,即整體去噪效果優(yōu)于另外二者。在平均信息熵上,對(duì)于特征豐富的bunny點(diǎn)云,本文算法去噪后的結(jié)果高于另外兩種算法,說明特征信息保留越完整；對(duì)于以平面為主的block點(diǎn)云,本文算法去噪結(jié)果低于另外二者,說明整體光順效果越佳。而在去噪時(shí)間上,由于本文算法步驟較多,參數(shù)需要自適應(yīng)調(diào)整,因此運(yùn)行時(shí)間較另外二者有所增加,但運(yùn)行效率基本能夠滿足日常需求。

為了驗(yàn)證本文算法的可行性,通過對(duì)block點(diǎn)云添加不同強(qiáng)度的高斯噪聲并使用本文算法進(jìn)行去噪,結(jié)果如圖6所示。

圖6 不同強(qiáng)度高斯噪聲下本文算法去噪效果Fig.6 Denoising effect of the algorithm of this paper under different intensities of Gaussian noise

由圖6可以看出,本文算法在面對(duì)不同強(qiáng)度的噪聲時(shí)均能取得較好的光順效果,結(jié)合前面的去噪性能對(duì)比可以得出,本文算法整體優(yōu)于單獨(dú)使用正交整體最小二乘法和雙邊濾波,且具有良好的適用性。

4 結(jié) 論

針對(duì)三維點(diǎn)云數(shù)據(jù)后處理過程中的去噪問題,本文提出了一種融合型算法,首先通過改進(jìn)的DPC去除遠(yuǎn)離點(diǎn)云主體的大尺度噪聲,減小了后續(xù)點(diǎn)云k鄰域及法矢、曲率等信息估算的誤差,同時(shí)基于鄰域傳播的法矢方向調(diào)整方案使得法矢方向調(diào)整時(shí)間大大縮短。在對(duì)點(diǎn)云進(jìn)行特征分區(qū)后,對(duì)不同區(qū)域點(diǎn)云分別采用適用于平面的正交整體最小二乘法和傾向于保留特征的改進(jìn)的雙邊濾波進(jìn)行去噪以到達(dá)最佳效果。從實(shí)驗(yàn)結(jié)果可以看出:本文算法在面對(duì)不同點(diǎn)云模型與不同強(qiáng)度噪聲時(shí),均能得到較好的去噪效果,具有一定的的普適性,且去噪性能相較于單獨(dú)使用正交整體最小二乘法或雙邊濾波均有一定的提升。后續(xù)工作中如何提高算法運(yùn)行效率將是下一步工作的重點(diǎn)。