鄰域自適應(yīng)的三維點云濾波算法

吳俊威，焦吾振，鄭河榮

(浙江工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，杭州 310023)

1 引 言

近年來，利用三維激光掃描儀獲取物體表面三維坐標并進行處理成為智能制造的趨勢所字.對于這些得到離散三維點云集合，需要通過去噪、網(wǎng)格化才能成為工程上有意義的三維數(shù)據(jù)[1].因此，如何有效地對三維點云數(shù)據(jù)進行處理，得到高質(zhì)量數(shù)據(jù)以及網(wǎng)格化后處理是一個非常重要的問題.這也是圖形學(xué)的一個長期研究熱點.

對于三維掃描數(shù)據(jù)，由于用戶、設(shè)備和掃描環(huán)境等各種因素的影響，三維點云數(shù)據(jù)不僅包含大量的噪點和離群點(外點)[2].因此，需要對原始掃描數(shù)據(jù)進行濾波操作，去除這些噪點和外點.在三維重建過程中，點云濾波算法扮演著一個十分基礎(chǔ)但關(guān)鍵的角色.否則由于點云噪聲的存在，三維掃描點云網(wǎng)格化處理以及逆向工程應(yīng)用會出現(xiàn)許多問題.例如重建網(wǎng)格會導(dǎo)致拓撲連接錯誤.對于點云濾波，目前最為典型的做法把網(wǎng)格濾波算法擴展到點云濾波.因此研究人員針對點云建立拓撲結(jié)構(gòu)，通常做法是給點云建立八叉樹或者kd-tree，使點云擁有和網(wǎng)格相似的鄰域關(guān)系結(jié)構(gòu).在現(xiàn)有研究中，網(wǎng)格濾波算法中拓展推出了很多點云濾波算法，如常見的拉普拉斯濾波，雙邊濾波等.但是網(wǎng)格濾波算法應(yīng)用于點云濾波，需要考慮的問題是如何更好地保持精度、維持細小特征.特別是在工業(yè)領(lǐng)域應(yīng)用中，因為去噪過程要求更高的精度保持，濾波算法難度也大大增加.已有研究人員在精度維持方面也提出了一些改進.在一個集成點云處理的方法中，Ohtake等人[3]，在防止點云濾波收縮中提出一個用二次誤差計算濾波偏差的方法來進行去噪.Schall等人[4]在此基礎(chǔ)上提出基于核聚類的方法，首先為每一個點定義一個局部似然函數(shù)，然后定義模型整體的似然函數(shù)，應(yīng)用類似梯度下降法，把每一個采樣點迭代到似然函數(shù)最大的位置.Kalogerakis等人[5]提出了一個魯棒的統(tǒng)計學(xué)點云濾波框架，他們用一個迭代的最小二乘方法來估計每個采樣點的曲率并分配不同的權(quán)重，利用這曲率和權(quán)重進行修正法線，進而進行保特征濾波.另外，基于點鄰域的雙邊濾波算法[6]，其利用采樣點周圍點的距離以及采樣點和周圍點的相似性把圖像雙邊濾波推廣到三維點云和網(wǎng)格濾波中.Lipman等人[7]提出局部最優(yōu)投影(LOP)算法，該算法用點云中的一個子集去投影到原始點云中，得到一個去噪后的原始點云的子集，里面有兩個懲罰函數(shù)一個控制平滑力度，另一個控制點的分布是否均勻，該算法可以很好的去除高噪聲.Huang等人[8]在局部最優(yōu)投影的基礎(chǔ)上根據(jù)不同位置的點云密度提出加權(quán)局部最優(yōu)投影(WLOP)算法，后面Huang等人[9]又在此基礎(chǔ)上提出增采樣，提高在特征邊緣的恢復(fù)能力，也取得了不錯的效果.基于擬合曲面的移動最小二乘方法(Moving least squares，MLS)[10，11]濾波算法中，利用采樣點鄰域構(gòu)建移動最小二乘曲面來擬合真實表面，也取得了不錯的濾波結(jié)果.之后針對稀疏采樣和尖銳特征丟失的問題又提出了魯棒性隱式移動最小二乘法(Robust Implicit Moving least squares，RIMLS)[12].字典學(xué)習[13]算法被用到點云濾波和表面重建中也取得了很好的濾波效果.陳永輝等人[14]提出了一種利用高斯映射劃分特征點，引入法向量權(quán)重，實現(xiàn)特征保持的均勻采樣算法.陳佳舟等人[15]提出了重投影剔除和基于空間剖分的擴散聚類算法的濾波思路.王勇等人[16]提出了一種多分辨率配準點的ICP算法，在精度和速度上有較大提高，隨后王勇等人[17]在此算法基礎(chǔ)上進行了改進，在粗配準階段采用歐式距離約束和RANSAC 算法進行外地點剔除，保證良好的濾波效果.

但是已有研究點云濾波算法會出現(xiàn)收縮，從而影響重建精度.因此論文提出了魯棒性的鄰域自適應(yīng)的混合點云采樣濾波算法，旨在提高點云濾波精度.算法首先對特征處鄰域均值濾波點云數(shù)據(jù)中插入對應(yīng)原始點，提高采樣密度同時保留原始點云特征信息；然后算法通過法向夾角和曲率約束定義自適應(yīng)鄰域保持局部特征；最后為采樣點定義一個似然函數(shù)求解得到濾波位置.實驗部分表明，本文算法在保證濾波效果的同時提高了點云濾波精度.

2 點云濾波收縮問題分析

對于點云濾波，由于原始點云存在較大噪聲，從而導(dǎo)致濾波結(jié)果不夠光滑[3].因此，研究人員為了提高濾波結(jié)果的平滑性，對原始點云(特別是尖銳特征處)進行重新采樣[4].雖然這種處理方法對濾波的平滑性有較好提高，并且使用重采樣恢復(fù)，較好的保留了平滑后的尖銳特征.但是，因為這種算法將原始點云使用均值點來進行取代，導(dǎo)致了濾波結(jié)果出現(xiàn)收縮問題.收縮是指算法在濾波過程中對原始點云進行重采樣等操作所導(dǎo)致的測量精度下降問題.因此，如何在保持尖銳特征和平滑性的同時，更好地避免收縮現(xiàn)象是濾波算法需要考慮的問題.

圖1 原始點和均值點Fig.1 Original point and mean point

為了更好地理解收縮問題，圖1中給出了三維原始點和濾波均值點的示意圖.從濾波知識可以知道，均值點相對于原始點云數(shù)據(jù)，可以獲得更好的平滑效果.但是從圖1(c)中可以看到均值點本身已經(jīng)在特征處偏移了實際點云位置，利用均值點濾波丟失了原始點云信息，尤其在特征處收縮嚴重，無法很好的還原掃描物體的真實曲面.

圖2 均值點云濾波收縮問題Fig.2 Mean point cloud filtering shrinkage problem

為了進一步分析濾波過程中的收縮問題，圖2給出了三維掃描數(shù)據(jù)的濾波前后的二維截面誤差對比圖.二維截面圖中，線1表示原始點云，線2表示濾波結(jié)果.可以發(fā)現(xiàn)，實際三維掃描數(shù)據(jù)實驗結(jié)果在均值點濾波后，曲線位置發(fā)生了明顯的偏移誤差.其中在頂部出現(xiàn)明顯的凸起，而在根部又逆向凹陷，出現(xiàn)了逆向收縮的現(xiàn)象.無法滿足逆向工程要求.

3 自適應(yīng)濾波鄰域選擇

對于點云濾波，需要建立拓撲關(guān)系用于鄰域點選擇.目前，點云拓撲通常采用kd-tree結(jié)構(gòu).但是kd-tree一個主要問題是只考慮點云的距離.這個問題會導(dǎo)致在曲率特征變化的地方，不同曲率和法向差別較大的點會相互影響，造成精度誤差.圖3中點1為濾波點，圈內(nèi)區(qū)域點為kd-tree搜索到的鄰域點，可以看到不同曲率和法線的點被同時選中，造成濾波后精度損失.

為了進一步分析濾波誤差，論文進行實際三維掃描數(shù)據(jù)實驗對比.實驗結(jié)果可以知道僅僅采用距離定義鄰域進行點云濾波，會出現(xiàn)在曲率變化明顯的部分相互影響嚴重，根部由于低曲率平面和高曲率加強筋部分相互影響，造成了中部凸起和平面凹陷的問題，凸起部分達到0.14mm，平面凹陷部分達到0.05mm.

圖 3 kd-tree鄰域選擇Fig.3 kd-tree neighborhood selection

針對這一問題，算法在進行鄰域計算的時候，首先進行合理鄰域的選擇.論文算法受到文獻[18]的啟發(fā)，自適應(yīng)選擇鄰域，用式(1)來確定：

(1)

這里0≤T≤1是一個用戶自己設(shè)定的法向閾值，試驗中一般選取0.5.這里可以看到計算過程中，如果兩個點的法線相差很大，超過了閾值，則可以認為在計算中舍棄了該點，不加入計算.在應(yīng)用PCA分析中可以很容易獲得該點的曲率信息，因此為了防止在計算高曲率點被低曲率點影響，低曲率點被高曲率點影響，對精度造成損失，我們用類似的方法去除曲率差別很大的點.

4 似然估計

在上述混合點云和自適應(yīng)鄰域條件下，算法采用似然函數(shù)計算濾波采樣點的真實位置.算法首先為每一個采樣點向量pi定義一個局部似然函數(shù)Li.Li由點pi所在鄰域{PSi}中任意點向量psj到該鄰域的最小二乘擬合平面距離的平方所確定.

首先根據(jù)式(2)通過計算帶有權(quán)重的協(xié)方差矩陣來獲得最小二乘擬合平面Ci.

(2)

然后采用公式(3) 計算點pi到最小二乘擬合平面距離的平方確定局部似然函數(shù)Li.

Li=Φi(pi-ci)[h2-[(pi-ci)·ni]2]

(3)

其中，h為鄰域搜索半徑，Φ為高斯函數(shù)，ni為法向.

似然函數(shù)L反映了點是采樣表面的似然性，根據(jù)所有采樣點pi的局部似然函數(shù)Li來確定.

(4)

在本文中我們定義wi的值為上節(jié)的曲率法線約束值.

在定義了似然函數(shù)后，我們對于公式(4)該點云模型的似然函數(shù)，采用梯度下降的方法，把所有采樣點迭代到其最大似然值的位置.其濾波迭代序列為：

(5)

(6)

5 實驗結(jié)果分析

為了進一步驗證論文算法的有效性，本節(jié)和相關(guān)算法進行比較.這些相關(guān)算法包括在點云濾波里面使用最為廣泛的雙邊濾波采樣[6]；以及Huang等[9]人提出的用于邊緣特征維持的增采樣策略；Schall等[4]人所采用的不考慮領(lǐng)域自適應(yīng)處理的似然函數(shù)估計算法.

本文通過在主頻2.7GHz、內(nèi)存32G的Intel i7 DELL圖形工作站進行數(shù)據(jù)處理來驗證論文算法的有效性.首先，采用HScan330手持三維激光掃描儀獲取模型點云數(shù)據(jù)完成數(shù)據(jù)采集，然后應(yīng)用本文算法、文獻[4]算法、文獻[6]算法和文獻[9]算法進行點云濾波去噪，最后把濾波后的點云數(shù)據(jù)與原始未濾波點云數(shù)據(jù)進行精度對比，精度對比采用Geomagic Qualify 2013軟件平臺進行比對檢測，精度比較采用軟件定義的四元素法(D、Dx、Dy、Dz)：測量總誤差(D)、測量X方向誤差(Dx)、測量Y方向誤差(Dy)、測量Z方向誤差(Dz)，表中給出了圖4中標注誤差數(shù)值.

圖4 鈑金件掃描比對結(jié)果Fig.4 Sheet metal scan comparison results

首先我們對工業(yè)常見鈑金件(見圖4)進行掃描濾波處理，各算法在去除噪聲點，平滑方面都取得了滿意的結(jié)果.然而通過分析濾波后與原始點云進行精度對比的色譜圖數(shù)據(jù)(見表1)可以明顯看出，文獻[6]算法和文獻[9]算法已經(jīng)明顯可以看出收縮，無法適用于逆向工程，而本文算法和文獻[4]精度都保持在0.04mm以內(nèi)，效果較好接下來我們又掃描了汽車輪轂(見圖5)進行濾波測試和精度對比.從表2的濾波結(jié)果看出雙邊濾波中去除噪聲點和精度保持方面都沒能達到令人滿意的結(jié)果.而本文算法在濾除噪聲點和文獻[4]保持一致的情況下，保持了較好的進度，都基本保持在0.04mm以內(nèi).濾波結(jié)果甚至可以應(yīng)用于工業(yè)逆向工程和檢測等高精度領(lǐng)域.

表1 圖中標注3點的鈑金件不同誤差(D、Dx、Dy、Dz)Table 1 Different errors of sheet metal parts marked with 3 points in the figure(D、Dx、Dy、Dz)

最后，對工業(yè)零件中常見的加強筋(見圖6)進行測試.通常情況下，圓弧角越小，濾波后點云精度丟失越多.我們選擇距離2mm的加強筋進行更加嚴苛的精度測試.從表3可以看出雙邊濾波已經(jīng)達到0.20mm，無法被工業(yè)逆向檢測所接受.而在此種更小的圓弧角情況下，文獻[4]算法的精度丟失也達到了0.08mm，本文算法的在混合點云增采樣基礎(chǔ)上，加入曲率約束和法線約束后精度丟失依舊可以保持在0.05mm以內(nèi)的誤差范圍，在不犧牲濾波效果的前提下，對精度有了更好的保持.

表2 圖中標注3點的輪轂不同誤差(D、Dx、Dy、Dz)Table 2 Different wheel hub errors marked with 3 points(D，Dx，Dy，Dz)

表4的精度對比中可以看出，本文算法在實驗結(jié)果中精度保持表現(xiàn)最好，都能保持在0.05mm以內(nèi)，可以應(yīng)用于工業(yè)逆向造型和檢測.

圖6 加強筋掃描比對結(jié)果Fig.6 Stiffener scan comparison results

表3 圖中標注3點的發(fā)動機蓋不同誤差(D、Dx、Dy、Dz)Table 3 Different errors of the hood marked with 3 points in the figure(D，Dx，Dy，Dz)

表4 精度比較Table 4 Precision comparison

6 結(jié) 論

論文提出了一種保精度的混合點云濾波算法，在濾波效果得到保證的情況下，對點云濾波的精度保持進行了提高.該算法不僅在工業(yè)檢測和逆向工程中可廣泛應(yīng)用，而且對三維掃描后處理的發(fā)展和應(yīng)用有積極的意義.

對于點云濾波，影響精度的另外一個主要原因是法向估計.已有研究搜索采樣點周圍的鄰域點，進行平面擬合，計算該平面的法向量作為該點的法向量.這種方法會導(dǎo)致高噪聲點云數(shù)據(jù)出現(xiàn)明顯誤差，進而降低濾波精度.在后續(xù)工作，論文將考慮研究更為穩(wěn)定可靠的法向計算方法，提高算法準確率.