幾何特征保持的文物點(diǎn)云去噪算法

劉立恒，趙夫群，湯 慧，劉陽(yáng)洋，耿國(guó)華

（1.西安交通大學(xué)電信學(xué)部，西安，710049；2.西安財(cái)經(jīng)大學(xué)信息學(xué)院，西安，710100；3.西安財(cái)經(jīng)大學(xué)實(shí)驗(yàn)實(shí)訓(xùn)教學(xué)中心，西安，710010；4.西北大學(xué)信息科學(xué)與技術(shù)學(xué)院，西安，710127）

引 言

隨著三維激光掃描技術(shù)的日趨成熟和大眾化，點(diǎn)云數(shù)據(jù)采集和預(yù)處理技術(shù)成為越來(lái)越受關(guān)注的研究熱點(diǎn)，已被廣泛應(yīng)用于醫(yī)學(xué)研究、文物數(shù)字化保護(hù)、地形勘探以及地震預(yù)測(cè)等領(lǐng)域[1-4]。在點(diǎn)云數(shù)據(jù)采集時(shí)，受物體本身的構(gòu)造、粗糙程度和紋理以及光線(xiàn)等周?chē)h(huán)境因素的影響，采集的原始點(diǎn)云往往含有大量的噪聲點(diǎn)，這對(duì)后期的點(diǎn)云配準(zhǔn)、融合以及三維重建等具有較大的影響，因此在保持點(diǎn)云的幾何特征的基礎(chǔ)上需要對(duì)其進(jìn)行去噪處理。

點(diǎn)云數(shù)據(jù)去噪的目的是快速有效地刪除噪聲點(diǎn)，同時(shí)保持點(diǎn)云的紋理和邊緣等特征細(xì)節(jié)。近年來(lái)，國(guó)內(nèi)外學(xué)者提出了許多點(diǎn)云去噪算法。如，Ma[5]提出一種基于曲面擬合的去噪算法，具有較好的去噪效果和較低的時(shí)間復(fù)雜度；Wang等[6]提出一種基于Laplace分布的去噪算法，可以有效保留原始數(shù)據(jù)中有用細(xì)節(jié)信息；Cruz等[7]提出一種基于非局域增強(qiáng)卷積神經(jīng)網(wǎng)絡(luò)的去噪算法，通過(guò)結(jié)合卷積神經(jīng)網(wǎng)絡(luò)和非局部濾波器實(shí)現(xiàn)了圖像的有效去噪；Centin等[8]提出一種幾何保真的Signoroni網(wǎng)格去噪算法，該算法不依賴(lài)于點(diǎn)云規(guī)模，對(duì)目標(biāo)應(yīng)用領(lǐng)域具有挑戰(zhàn)性的情況去噪效果良好；Zheng等[9]提出一種基于銳利特征骨架的點(diǎn)云去噪算法，該算法在保持重要幾何特征不變的同時(shí)，能有效濾除噪聲；王曉輝等[10]提出一種基于法向量距離估算的點(diǎn)云去噪算法，該算法采用加權(quán)局部最優(yōu)投影算法對(duì)點(diǎn)云的平滑區(qū)域進(jìn)行去噪，采用雙邊濾波算法對(duì)點(diǎn)云的尖銳區(qū)域進(jìn)行濾波去噪，可以有效保持尖銳區(qū)域內(nèi)的幾何特征。以上這些算法均實(shí)現(xiàn)了點(diǎn)云數(shù)據(jù)的有效去噪，但對(duì)大尺度噪聲和外點(diǎn)含量較高的復(fù)雜文物點(diǎn)云模型的去噪效果不佳。

針對(duì)文物點(diǎn)云數(shù)據(jù)模型，本文提出一種幾何特征保持的去噪算法。對(duì)于大尺度噪聲，即懸浮在主體點(diǎn)云周?chē)移x主體點(diǎn)云的稀疏點(diǎn)，以及距離主體點(diǎn)云中心較遠(yuǎn)且小而密集的點(diǎn)，首先根據(jù)點(diǎn)云密度將點(diǎn)云進(jìn)行柵格化劃分，并確定每個(gè)點(diǎn)所在的柵格位置以及每個(gè)柵格中的點(diǎn)數(shù)，然后判斷柵格內(nèi)的點(diǎn)數(shù)及其周?chē)鷸鸥駜?nèi)點(diǎn)數(shù)的情況，刪除大尺度噪聲；對(duì)于小尺度噪聲，即混合在主體點(diǎn)云中的噪聲點(diǎn)，采用一種基于曲率因子和密度因子的特征加權(quán)模糊C均值聚類(lèi)（Fuzzy C-means clustering,FCM）算法進(jìn)行刪除，從而實(shí)現(xiàn)點(diǎn)云的最終精確去噪處理。

1 基于柵格的大尺度噪聲刪除

大尺度噪聲包含兩部分：一部分是那些懸浮在主體點(diǎn)云周?chē)移x主體點(diǎn)云的稀疏點(diǎn)；另一部分是距離主體點(diǎn)云中心較遠(yuǎn)且小而密集的點(diǎn)。對(duì)于大尺度噪聲，這里采用柵格劃分的方式進(jìn)行刪除。

1.1 柵格劃分

對(duì)于點(diǎn)云P，其大尺度噪聲采用柵格劃分的方式刪除。首先，將點(diǎn)云P中所有數(shù)據(jù)點(diǎn)的三維坐標(biāo)點(diǎn)存到一個(gè)一維數(shù)組中，并構(gòu)造一個(gè)與坐標(biāo)軸平行的長(zhǎng)方體包圍盒，確保包圍到點(diǎn)云的所有數(shù)據(jù)點(diǎn)。假設(shè)該長(zhǎng)方體包圍盒中點(diǎn)的最大和最小坐標(biāo)分別為{xmax,ymax,zmax}和{xmin,ymin,zmin}，長(zhǎng)方體柵格的長(zhǎng)度為L(zhǎng)。

然后，根據(jù)數(shù)據(jù)點(diǎn)的密度將長(zhǎng)方體包圍盒劃分成多個(gè)小立方體柵格，如圖1所示。那么小立方體柵格在x,y,z軸3個(gè)方向的個(gè)數(shù)Sumx,Sumy,Sumz為

對(duì)于點(diǎn)云P中的某一確定點(diǎn)其中表示點(diǎn)pi的三維坐標(biāo)，那么點(diǎn)pi所在小立方體柵格在x,y,z軸3個(gè)方向的索引號(hào)為

圖1 柵格劃分示意圖Fig.1 Grid division diagram

1.2 大尺度噪聲刪除

基于以上柵格劃分結(jié)果，接下來(lái)判斷每個(gè)柵格內(nèi)的數(shù)據(jù)點(diǎn)數(shù)以刪除大尺度噪聲，具體步驟如下：

步驟1假設(shè)柵格化后點(diǎn)云P的小立方體柵格總數(shù)為Sum個(gè)，柵格的集合為R={R1,R2,…,RSum}，其中Sum=Sumx×Sumy×Sumz，并定義柵格內(nèi)點(diǎn)數(shù)大于給定閾值的柵格為有點(diǎn)柵格，點(diǎn)數(shù)小于等于給定閾值的柵格為無(wú)點(diǎn)柵格；

步驟2取第i個(gè)小立方體柵格Ri，i=1,2,…,Sum，并判斷該柵格內(nèi)的數(shù)據(jù)點(diǎn)數(shù)，如果Ri為無(wú)點(diǎn)柵格，則根據(jù)柵格內(nèi)點(diǎn)的索引號(hào)刪除Ri內(nèi)的所有數(shù)據(jù)點(diǎn)，這些刪除的點(diǎn)就是懸浮在點(diǎn)云周?chē)纳y稀疏的大尺度噪聲點(diǎn)；

步驟3如果柵格Ri為有點(diǎn)柵格，則以Ri為中心查看其周?chē)男×⒎襟w柵格內(nèi)的數(shù)據(jù)點(diǎn)數(shù)；

步驟4繼續(xù)依次把周?chē)挠悬c(diǎn)柵格作為中心，查看其周?chē)鷸鸥?，直到查看完所有柵格為止，如此就找出了與柵格Ri屬于同一片點(diǎn)云的所有相鄰柵格；

步驟5取下一個(gè)與Ri不屬于同一片點(diǎn)云的柵格Rj,j=1,2,…,Sum,j≠i，重復(fù)步驟2～4的過(guò)程，即可找到與柵格Rj屬于同一片點(diǎn)云的所有相鄰柵格；

步驟6繼續(xù)取下一個(gè)與Ri和Rj都不屬于同一片點(diǎn)云的柵格Rk,k=1,2,…,Sum,k≠j≠i，重復(fù)步驟2～4的過(guò)程，一直執(zhí)行，直到將所有柵格都劃分到相應(yīng)的某片點(diǎn)云中為止，如此就將點(diǎn)云P劃分成s片點(diǎn)云 {P1,P2,…,Ps}；

步驟7計(jì)算每一片點(diǎn)云中有點(diǎn)柵格的數(shù)目，從而可以從s片點(diǎn)云中找出含有的有點(diǎn)柵格數(shù)目最多的那一片點(diǎn)云，那么該片點(diǎn)云即為主體點(diǎn)云，其余的點(diǎn)云均為距離主體點(diǎn)云中心較遠(yuǎn)且小而密集的大尺度噪聲點(diǎn)，需將其刪除掉。

通過(guò)以上步驟即可實(shí)現(xiàn)點(diǎn)云中的大尺度噪聲刪除，然后采用特征加權(quán)FCM算法刪除點(diǎn)云中的小尺度噪聲。

2 基于特征加權(quán)FCM的小尺度噪聲刪除

小尺度噪聲主要是指混合在主體點(diǎn)云中的噪聲點(diǎn)，該噪聲的存在會(huì)干擾三維模型重建曲面的光滑性，使重建的三維模型存在一定程度的失真。假設(shè)刪除大尺度噪聲后的點(diǎn)云為P′，然后采用特征加權(quán)FCM算法對(duì)其進(jìn)行小尺度去噪。該特征加權(quán)FCM算法通過(guò)在目標(biāo)函數(shù)中引入曲率因子和密度因子來(lái)實(shí)現(xiàn)點(diǎn)云小尺度噪聲的刪除。

2.1 FCM算法

FCM算法由Ruspini于1970年首次提出[11]，該算法利用隸屬度確定每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)類(lèi)別的程度。FCM把包含n個(gè)l維向量的集合分為m組，每組對(duì)應(yīng)一個(gè)聚類(lèi)中心O={o1,o2,…,om}，計(jì)算每個(gè)聚類(lèi)中心oj,j=1,2,…,m，使得目標(biāo)函數(shù)F達(dá)到最小。目標(biāo)函數(shù)F的定義式為

式中：U為隸屬度矩陣；μij∈U表示每個(gè)向量屬于各個(gè)聚類(lèi)分組的程度，并且滿(mǎn)足；t表示模糊控制參數(shù)表示向量和聚類(lèi)中心oj的Euclid距離，定義式為

2.2 特征加權(quán)FCM算法

特征加權(quán)FCM算法通過(guò)在FCM算法中加入曲率因子和密度因子實(shí)現(xiàn)聚類(lèi)[12]。對(duì)點(diǎn)云P′中的任意一個(gè)數(shù)據(jù)點(diǎn)表示點(diǎn)的三維坐標(biāo)，定義其 曲率因 子αHi為

式中Hi表示點(diǎn)的平均曲率，1≤i≤n。

平均曲率Hi的定義式為

式中λ0,λ1,λ2表示點(diǎn)的k鄰域點(diǎn)集構(gòu)造的關(guān)于點(diǎn)的3×3協(xié)方差矩陣C的特征值，并且λ0≤λ1≤λ2，協(xié)方差矩陣表示點(diǎn)及其k鄰域點(diǎn)的質(zhì)心。

曲率因子αHi表示點(diǎn)的平均曲率Hi對(duì)聚類(lèi)的影響程度。Hi的值越小，αHi的值也就越小，點(diǎn)pi′包含的特征也就越?。籋i的值越大，αHi的值也就越大，點(diǎn)包含的特征也就越大。

定義密度因子αρi為

式中1≤i≤n。

基于該特征加權(quán)FCM算法，對(duì)點(diǎn)云P′的小尺度噪聲進(jìn)行刪除的具體步驟如下：

步驟1對(duì)點(diǎn)云P′中的任意一點(diǎn)采用特征加權(quán)FCM算法對(duì)其r包圍球內(nèi)的點(diǎn)進(jìn)行聚類(lèi)，并統(tǒng)計(jì)其r包圍球內(nèi)近鄰點(diǎn)的個(gè)數(shù)，r的取值與柵格劃分的數(shù)目有關(guān)。

步驟2判斷點(diǎn)的r包圍球內(nèi)近鄰點(diǎn)數(shù)目，若大于給定閾值，則將點(diǎn)移動(dòng)，若小于等于給定閾值，則點(diǎn)p′i為噪聲點(diǎn)，將其刪除。其中表示聚類(lèi)中心oj相對(duì)于隸屬度μij的加權(quán)平均值，定義式為

步驟3取下一個(gè)未聚類(lèi)過(guò)的點(diǎn)，重復(fù)執(zhí)行步驟1～2，直到點(diǎn)云P′中的所有點(diǎn)都判斷完為止，從而實(shí)現(xiàn)點(diǎn)云P′的小尺度噪聲刪除。

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

實(shí)驗(yàn)硬件環(huán)境配置為CPU為Intel(R)Core(TM)i5-4950，主頻3.30 GHz,內(nèi)存為8.00 GB。實(shí)驗(yàn)數(shù)據(jù)采用西北大學(xué)可視化技術(shù)研究所提供的文物碎片點(diǎn)云數(shù)據(jù)模型，該數(shù)據(jù)利用加拿大手持式Handyscan3D激光掃描儀獲取，用于實(shí)驗(yàn)測(cè)試的3個(gè)文物碎片點(diǎn)云數(shù)據(jù)模型如圖2所示。

圖2 去噪前的文物碎片點(diǎn)云模型Fig.2 Point cloud models of cultural relics fragments before denoising

采用提出的幾何特征保持的點(diǎn)云去噪算法，首先通過(guò)對(duì)點(diǎn)云進(jìn)行柵格化劃分刪除大尺度噪聲，然后采用特征加權(quán)FCM算法刪除小尺度噪聲，從而實(shí)現(xiàn)文物碎片點(diǎn)云的最終去噪。對(duì)于圖2的文物碎片，分別采用本文提出的該幾何特征保持的點(diǎn)云去噪算法、FCM算法[11]、文獻(xiàn)[13]算法以及文獻(xiàn)[14]算法進(jìn)行去噪，4種算法對(duì)碎片1、碎片2和碎片3的去噪結(jié)果分別如圖3—5和表1所示。

圖3 碎片1的去噪結(jié)果Fig.3 Denoising results of fragment 1

圖4 碎片2的去噪結(jié)果Fig.4 Denoising results of fragment 2

圖5 碎片3的去噪結(jié)果Fig.5 Denoising results of fragment 3

由圖3—5和表1可見(jiàn)，該幾何特征保持的去噪算法在有效刪除大尺度和小尺度噪聲的同時(shí)，可以較好地保持文物點(diǎn)云模型的細(xì)節(jié)特征，具有最低的誤差和耗時(shí)。與FCM算法相比，本文算法的平均誤差降低了約50%，耗時(shí)降低了約32%；與文獻(xiàn)[13]算法相比，本文算法的平均誤差降低了約44%，耗時(shí)降低了約25%；與文獻(xiàn)[14]算法相比，本文算法的平均誤差降低了約34%，耗時(shí)降低了約15%。

這是由于FCM算法是一種目標(biāo)函數(shù)基于Euclid距離的模糊聚類(lèi)算法，對(duì)滿(mǎn)足正態(tài)分布的點(diǎn)云數(shù)據(jù)具有很好的聚類(lèi)效果，但是聚類(lèi)中心的初始化對(duì)聚類(lèi)效果有很大的影響，其時(shí)間復(fù)雜度為O(nm2)，n表示點(diǎn)云中點(diǎn)的數(shù)目，m表示聚類(lèi)數(shù)；文獻(xiàn)[13]定義了消除幾何不連續(xù)點(diǎn)近距離誤差和長(zhǎng)距離測(cè)量誤差，實(shí)現(xiàn)了點(diǎn)云數(shù)據(jù)的有效去噪，但是該算法對(duì)文物點(diǎn)云的輪廓邊緣的保持效果不佳，其時(shí)間復(fù)雜度為O(n2)；文獻(xiàn)[14]是一種基于距離變化、點(diǎn)云強(qiáng)度和密度信息的去噪算法，對(duì)密集噪聲具有較好的去噪效果，但是對(duì)文物碎塊點(diǎn)云的離散稀疏噪聲刪除效果不佳，其時(shí)間復(fù)雜度為O(nm)；而本文算法采用柵格劃分的方式刪除大尺度噪聲，采用特征加權(quán)FCM算法刪除小尺度噪聲，不僅可以有效剔除懸浮在主體點(diǎn)云周?chē)移x主體點(diǎn)云的稀疏點(diǎn)，以及距離主體點(diǎn)云中心較遠(yuǎn)且小而密集的點(diǎn)，而且對(duì)混合在主體點(diǎn)云中的噪聲點(diǎn)也有良好的刪除效果，其時(shí)間復(fù)雜度為O(nlog2n)。因此可以證明，本文基于幾何特征保持的點(diǎn)云去噪算法是一種更加有效的文物點(diǎn)云模型去噪方法。

表1 不同去噪算法的運(yùn)行結(jié)果Table 1 Running results of different denoising algorithms

4 結(jié)束語(yǔ)

針對(duì)文物點(diǎn)云數(shù)據(jù)中復(fù)雜噪聲難以去除的問(wèn)題，提出一種保持幾何特征的去噪算法。首先通過(guò)柵格劃分刪除大尺度噪聲，然后采用特征加權(quán)FCM算法刪除小尺度噪聲，從而達(dá)到保留文物點(diǎn)云模型中細(xì)節(jié)特征的目的。實(shí)驗(yàn)通過(guò)對(duì)文物碎塊點(diǎn)云數(shù)據(jù)去噪來(lái)驗(yàn)證所提算法，結(jié)果表明本文算法可以在保持文物點(diǎn)云模型的尖銳幾何特征的同時(shí)，有效刪除噪聲點(diǎn)，為后期文物的虛擬復(fù)原提供了可靠的數(shù)據(jù)源。但是由于文物碎塊點(diǎn)云數(shù)據(jù)量大小不一，采集環(huán)境差異也較大，因此設(shè)計(jì)通用高效的文物點(diǎn)云去噪算法是下一步研究重點(diǎn)。