鄭一帆 ，鄭茜穎 ，程樹英

（1.福州大學 物理與信息工程學院，福建 福州 350108；2.微納器件與太陽能電池研究所，福建 福州 350108）

0 引 言

近年來，得益于激光雷達、RGB-D雙目相機和TOF（Time of Flight）相機的不斷發(fā)展，點云在自動駕駛[1]、虛擬現(xiàn)實[2]、3D打印[3]等領域廣泛運用。但是受到儀器精度、人為操作擾動和復雜環(huán)境等因素影響，采集得到的點云數(shù)據(jù)往往會出現(xiàn)噪聲點和離群點，并且存在數(shù)據(jù)冗余和不均勻等缺點。這些缺點會造成之后的重建過程耗費大量時間，重建模型出現(xiàn)輪廓不清晰和細節(jié)特征丟失，造成模型魯棒性不足。因此，需要在三維重建前對點云數(shù)據(jù)進行去噪處理。

國內(nèi)外研究人員一直對各種點云去噪技術加以改進和完善，傳統(tǒng)的點云去噪方法主要有基于統(tǒng)計學的方法、基于投影的方法以及基于過濾器的方法。早期點云去噪方法以基于統(tǒng)計學方法為主，如SCHALL等[4]使用局部定義的核函數(shù)為含有噪聲的點云定義全局的概率分布函數(shù)，然后求其函數(shù)最大值從而實現(xiàn)去噪。而后點云去噪方向逐步以基于投影和基于過濾器方法為主，如有基于雙邊過濾器[5-6]和基于鄰域濾波器[7]的去噪算法。近年來，深度學習逐漸興起，不少研究人員開發(fā)了基于深度學習的算法。YU等[8]制定一個基于邊緣感知的框架，在上采樣的同時恢復點云坐標，得到坐標與邊緣的距離，利用邊緣感知損失函數(shù)實現(xiàn)點云去噪。CHEN等[9]提出一種能夠推理點云拓撲關系的自動編碼器網(wǎng)絡結構，利用無監(jiān)督學習得到原始點云。PISTILLI等[10]的卷積神經(jīng)網(wǎng)絡通過點的高維特征表示之間的相似性動態(tài)構建鄰域圖來提升點云表面法線的質量，從而實現(xiàn)去噪。CATTAI等[11]利用局部諧波角濾波器的研究成果，提出了視覺驅動點云去噪算法（Visually Driven Point Cloud Denoising Algorithm，VIPDA），通過對點云進行諧波角度分析，使點云頂點相關聯(lián)從而剔除噪聲點。CHEN等[12]受到幾何統(tǒng)計的啟發(fā)，定義一個旋轉不變的高度圖補丁，將非局部相似的補丁的高度圖打包成一個（Height-Map Patch，HMP）矩陣，然后利用一個低秩恢復模型過濾噪聲。以上算法雖然能夠在一定程度上去除點云噪聲，但是尖銳特征區(qū)域容易出現(xiàn)模糊，造成之后重建模型失真。為了解決上述問題，本文提出一種旨在去除噪聲點云的同時保持特征的點云去噪算法。該算法利用八叉樹進行遞歸劃分，得到點云之間的拓撲關系，同時加速點云的鄰域搜索速度；然后在點云鄰域的基礎上利用主成分分析法（Principal Component Analysis，PCA）估算點云法向量，使用最小生成樹解決點云法向不一致問題；最后依據(jù)雙邊濾波器能夠保持特征的特點，將其與加權局部最優(yōu)算法結合，從而實現(xiàn)點云去噪同時保持細節(jié)特征。

1 本文方法

1.1 基于八叉樹的鄰域搜索

一般情況下，三維掃描設備采集得到的原始點云數(shù)據(jù)只包含xyz空間坐標，并且點云之間散亂無序，不存在拓撲關系。本文使用八叉樹來建立點云的拓撲結構，加速點云的鄰域搜索。八叉樹是一種描述三維空間的樹狀數(shù)據(jù)結構，其遞歸劃分的過程是在開始鄰域搜索時先假設一個搜索半徑或者閾值，最開始的父節(jié)點代表一個標準正方體，一般以點云的最小包圍盒大小作為標準正方體的體積，然后對父節(jié)點進行遞歸劃分，又劃分為8個相同大小的小正方體代表子節(jié)點。如果子節(jié)點的點云數(shù)量大于設定的一個閾值，則每個子節(jié)點繼續(xù)向下劃分為8個小正方體，直到點云數(shù)量小于閾值則遞歸劃分結束，其過程如圖1所示。圖2為斯坦福Dragon模型建立八叉樹的具體過程。該過程體現(xiàn)了八叉樹進行鄰域搜索時不需要遍歷整個點云集的優(yōu)點，只需要在部分空間中進行搜索，因此大大加快了點云鄰域搜索速度，提高了算法運算效率。

圖1 八叉樹遞歸劃分過程

圖2 Dragon模型劃分過程

1.2 PCA估算點云法向量

法向量是點云不可缺少的重要信息。點云法向量一般采用主成分分析法[13]（Principal Component Analysis，PCA）來估算。PCA用于法向量估計時，只能得到大致的點云法向量，對于點云法向量方向是否一致無法進行確定。因此，首先進行法向量方向的判斷。設兩個相鄰點的法矢向量為ni和nj，若ni與nj是平行的，則ni·nj=±1；如果ni·nj＞0，則表示ni與nj之間法向量方向相同；如果ni·nj＜0，則表示ni和nj之間法向量方向相反，需要使用奇偶圖或者最小生成樹法（Minimal Spanning Tree，MST）實現(xiàn)法向一致性。本文使用最小生成樹法實現(xiàn)法矢方向一致。首先構造點云的黎曼圖，任意確定一個點的法向量，沿此點的法向量方向進行傳播，然后根據(jù)點云法向量之間點積的值進行判斷，如果點積值為負則將其法向翻轉，重復遍歷，直到所有點的法向量方向被調整為一致。

1.3 改進的局部最優(yōu)投影算法

1.3.1 LOP算法和WLOP算法

為了解決點云噪聲和分布不均的問題，LIPMAN[14]等基于L1中值問題提出了一種不受點云參數(shù)影響的去噪算法，即局部最優(yōu)投影算法（Local Optimal Projection，LOP）。該算法的核心思想是將目標點云Q={qi}i∈I?R3投影到原始點云P={pj}j∈J?R3上，從而得到不含噪聲的點云Q。具體算法如下。

對原始點云P={pj}j∈J?R3，LOP以任意點集開始，將X(0)投影到P上，進行能量方程的優(yōu)化：

式中：E1(X,P,C)項中的θ(r)是快速遞減的空間加權函數(shù)，作用是促使投影點盡可能逼近采樣表面；E2(X,C)項中的η(r)是遞減的懲罰函數(shù)，目的是使投影點保持均勻分布；E2(X,C)項中的λi′的作用是平衡E1(X,P,C)和E2(X,C)兩項函數(shù)。當λi′參數(shù)設置得較小時，目標點云Q可以很好地逼近原始點云P，但是點云均勻性較差，當λi′參數(shù)設置得較大，則E1(X,P,C)項作用被削弱，可以得到均勻分布的目標點云Q，但是無法逼近原始點云P，達不到去噪效果。由此可見，LOP算法對初始點云P的采樣點分布有很強的依賴性。因此，HUANG等[15]提出加權局部最佳投影（Weighted LOP，WLOP）。在LOP基礎上，WLOP進行了兩處修改：首先在E1(X,P,C)項加入了全局密度vj，在E2(X,C)項中加入全局密度wik，解決了LOP算法依賴于采樣點導致的分布不均；其次，WLOP算法將懲罰項函數(shù)改為η(r)=-r，使函數(shù)可以收斂。WLOP算法具體方程如下：

1.3.2 雙邊加權的WLOP算法

盡管WLOP算法生成的點云分布更加均勻，但是由于沒有考慮到尖銳特征，會導致結果中的尖銳特征丟失。而雙邊濾波器對尖銳特征有很好的保持效果。因此，本文從中得到啟發(fā)，將雙邊濾波器與WLOP相結合。按照雙邊濾波器的公式：

式中：ni是PCA求得的法向量，β是雙邊濾波因子。在E1(X,P,C)項里加入雙邊濾波器，同時保持E2(X,C)項不變，得到一個去除噪聲同時保留尖銳特征的點云算法。算法具體如下：

式中：θ1(x)是特征保留權重函數(shù)，目的是保持點云的尖銳特征。將公式迭代后得到：

式（14）的結果即為去噪后的點云。

2 實驗結果

為了驗證本文去噪算法的有效性，選用斯坦福大學的Dragon和Blade模型進行對比實驗，在Windows 10平臺上基于Visual Studio 2015軟件和CGAL庫實現(xiàn)本文算法。實驗第一部分是在相同高斯噪聲下對Dragon模型使用不同算法進行實驗，第二部分是在不同強度高斯噪聲下對Blade模型使用本文算法進行實驗。

2.1 相同高斯噪聲下不同算法的比較

使用PCL（Point Cloud Library）軟件對Dragon點云模型增添15 dB噪聲，然后分別用WLOP算法、RMLS算法、雙邊濾波算法和本文算法進行處理，結果如圖3（b）、圖3（c）、圖3（d）、圖3（e）所示。圖3（a）為原始Dragon模型的重建結果。圖3（b）為WLOP算法處理后的重建模型，對比圖3（a）可以看出Dragon模型的頭部、足部和尾部細節(jié)丟失較多。WLOP算法無法保持Dragon模型的尖銳特征，無法很好地還原原始模型。圖3（c）為RMLS算法處理后的重建模型，對比圖3（a）可以看出RMLS算法重建效果較差，Dragon模型的軀干、足部等出現(xiàn)了較大的缺失。圖3（d）是雙邊濾波算法處理后的重建模型，雖然保留了Dragon模型的大部分細節(jié)和輪廓，但是重建模型中出現(xiàn)了部分空洞，并且模型光順度不佳。圖3（e）為本文算法處理后的重建模型，對比圖3（a）可以看出本文算法基本還原了原始模型，同時比較圖3（b）、圖3（c）、圖3（d）模型，也很好地保留了模型的頭部、背部和足部細節(jié)信息，同時解決了模型缺失問題。

圖3 相同噪聲下不同算法的結果

圖4（a）、圖4（b）、圖4（c）分別為WLOP算法、雙邊濾波算法、本文算法模型與原始Dragon模型的偏差比較結果。從圖4各子圖右邊的色譜直方圖可以看出，WLOP算法與原始模型偏差最大，最大偏差為0.010 2 mm；本文算法偏差最小，最大偏差僅0.009 0 mm。

圖4 不同算法的偏差圖

表1為3種不同算法處理后的誤差比較，對比可以看出本文算法誤差最小，最大程度地還原了原始模型。

表1 不同算法的誤差比較

2.2 不同強度噪聲下去噪算法的對比

為了驗證不同強度高斯噪聲下本文算法的效果，選用斯坦福的Blade模型進行實驗。對原始的Blade模型添加信噪比SNR=10 dB、SNR=20 dB、SNR=30 dB的高斯噪聲，結果如圖5（c）、圖6（c）、圖7（c）所示。

圖5 10 dB噪聲下本文算法的結果

圖6 20 dB噪聲下本文算法的結果

圖7 30 dB噪聲下本文算法的結果

通過對比原始Blade模型可以看出，本文算法在不同噪聲下均具有較好的去噪和細節(jié)特征保持。利用Geomagic Studio 2013軟件進行模型偏差分析，結果如圖8（a）、圖8（b）、圖8（c）所示。從偏差分析圖可以看出，本文算法處理后的模型與原始模型整體偏差較小，誤差保持在合理范圍內(nèi)，說明本文算法具有較好的魯棒性。

圖8 不同噪聲下本文算法的偏差分析

表2為添加3種不同噪聲后經(jīng)過本文算法處理的Blade模型的偏差數(shù)據(jù)。對比可以看出，10 dB噪聲時最大偏差、平均偏差和標準偏差都是最大的，但是仍然保持在合理范圍內(nèi)。30 dB噪聲時最大偏差、平均偏差和標準偏差最小，說明算法去噪效果好，同時也保留了模型原始的細節(jié)特征。

表2 不同強度噪聲下Blade模型的偏差分析

3 結 語

本文提出了一種保持細節(jié)特征的點云去噪算法。該算法利用八叉樹加速了算法處理速度，同時通過改進的局部最優(yōu)投影算法實現(xiàn)對點云的去噪和均勻化，以提高點云模型的精度。實驗結果比對和偏差分析表明，該算法能夠很好地去除點云數(shù)據(jù)中的噪點，保留模型原始的細節(jié)特征，在噪聲強度較大的情況下也能夠保持較小的誤差，使模型具有很好的魯棒性。