基于點云增強的網(wǎng)格化優(yōu)化算法

楊雨航,楊耀權(quán),劉宏飛

(華北電力大學(xué)(保定)控制與計算機學(xué)院,河北 保定 071003)

0 引 言

近年來，利用目標(biāo)三維點云或者目標(biāo)多序列圖像重建三維模型的技術(shù)在軍事偵察、地形建模、工業(yè)自動化等領(lǐng)域蓬勃發(fā)展。如何重建出更為真實的目標(biāo)三維模型是逆向工程中的關(guān)鍵問題之一，其中，點云網(wǎng)格化重建是逆向工程的關(guān)鍵一步。

目前，常用的網(wǎng)格化重建算法主要分為3種方式[1-3]：1)基于隱式曲面重建的泊松重建算法，該算法采用隱性擬合的方式，融合了全局與局部方法的優(yōu)點，能有效平滑散亂點云中存在的噪聲并且重建出的模型具有水密性的封閉特性，缺點是容易過渡平滑目標(biāo)模型的細(xì)節(jié)特征；2)基于Delaunay三角剖分的曲面重建算法，該算法雖然重建出的模型細(xì)節(jié)特征保留較為完整，但耗時較長且不適合處理非均勻點云數(shù)據(jù)；3)基于參數(shù)曲面重建的算法，該算法可以處理非均勻點云數(shù)據(jù)同時重建模型較為平滑，但不適合處理散亂點云以及含有噪聲的點云數(shù)據(jù)[4-6]。

相比之下，傳統(tǒng)泊松算法雖然有著通過融合全局與局部方法而免去點云分割和拼接過程的優(yōu)點，但也存在錯誤連接點云孔洞區(qū)域和法線方向不一致等不足，因此，近年來大批科研工作者針對傳統(tǒng)泊松算法做了大量的優(yōu)化研究[7-10]。黃明偉等人[11]提出了將高斯濾波引入點云數(shù)據(jù)的等值面向量場估計之中以改進(jìn)泊松重建算法，成功提高了重建模型的精確性與完整性。高鋒等人[12]利用加權(quán)主成分分析法結(jié)合移動最小二乘法(MLS)對點云法向進(jìn)行優(yōu)化，同時改進(jìn)了Dual Contouring提取等值面的算法，有效減少了重建模型孔洞和偽封閉曲面的出現(xiàn)數(shù)量，但是重建效率并未得到很好的改善。黃礦裕等人[13]提出了對三維點云進(jìn)行空間劃分進(jìn)行體素標(biāo)記，對不同標(biāo)記的體素采用不同的處理方法以實現(xiàn)法線定向，成功提高了重建的準(zhǔn)確性。劉濤等人[14]利用雙三次樣條插值方程擬合曲面，成功修復(fù)重建模型的孔洞，提高了重建精度，但是其引入了最小二乘法，該算法雖然平滑了噪聲但可能會使某些細(xì)節(jié)信息丟失。孫殿柱等人[15]提出了一種基于局部泊松曲面重建的點云剛性配準(zhǔn)方法，顯著提高了配準(zhǔn)過程收斂的穩(wěn)定性。吳婧等人[16]對原始點云進(jìn)行光順濾波和法向估計等處理，提高了重建模型的精度。鄭蓉珍等人[17]提出了一種混合高斯/泊松最大似然函數(shù)下的錐形束計算機斷層掃描成像的圖像重建方法，成功實現(xiàn)了在噪聲環(huán)境下也具有較好的圖像重建質(zhì)量?？祩骼热薣18]提出了一種基于MLS結(jié)合體素化網(wǎng)格模型實現(xiàn)重采樣的算法，在保持局部細(xì)節(jié)的基礎(chǔ)上提高了重建模型表面的光滑性。付永健等人[19]提出了一種應(yīng)用馬氏距離加權(quán)的點云法向估算與一致性調(diào)整算法，有效抑制了外圍點的影像，提高了重建效率。姜淑鳳等人[20]提出了一種基于B樣條曲面過渡/微調(diào)精簡算法，提高了重建精度。李宗春等人[21]提出了一種凸顯點云尖銳特征的點線面遞進(jìn)式曲面重建算法，提高了尖銳特征曲面重建的準(zhǔn)確性。龐正雅等人[22]提出了利用統(tǒng)計濾波對點云簡化去噪，再選擇初始點進(jìn)行區(qū)域增長，最后完成網(wǎng)格化，成功降低了重建所用的時間。

因此，基于上述一系列學(xué)者的研究基礎(chǔ)以及算法中依然存在的一些問題，本文提出一種基于點云增強的網(wǎng)格化優(yōu)化算法。首先通過統(tǒng)計濾波對點云進(jìn)行降噪，再通過體素濾波進(jìn)行適當(dāng)點云降采樣，同時利用雙三次樣條插值進(jìn)行點云孔洞修復(fù)，然后將移動最小二乘法誤差函數(shù)引入到點云法向計算中以優(yōu)化點云法向量的質(zhì)量。經(jīng)過實驗驗證，本優(yōu)化算法較傳統(tǒng)泊松重建算法耗時更短，同時提高了重建模型的準(zhǔn)確度。

1 基本原理

點云的獲取主要分為2種方式：1)利用市面上的非接觸式三維激光掃描儀，這類方式能直接獲取目標(biāo)高精度的三維點云數(shù)據(jù)；2)通過目標(biāo)多幅圖像獲取點云數(shù)據(jù)[23]。

泊松重建是在2006年由Kazhdan等人提出的網(wǎng)格重建方法。其核心思想是指點云代表了目標(biāo)表面的位置，對應(yīng)的法向量代表了表面的內(nèi)外朝向，這樣就可以隱式地擬合一個由重建目標(biāo)派生而來的可以進(jìn)行平滑表面估計的指示函數(shù)。給定一個區(qū)域M，其邊界為?M，指示函數(shù)χM定義如下：

(1)

其中，x表示空間某一點的位置。這樣就把重建點云表面的問題轉(zhuǎn)變?yōu)橹亟ㄖ甘竞瘮?shù)χM的問題。

傳統(tǒng)泊松重建的流程[17-23]如圖1所示。

圖1 傳統(tǒng)泊松重建流程

其基本思路是：

1)定義八叉樹。使用八叉樹結(jié)構(gòu)存儲點集，深度表示為D。

2)設(shè)置函數(shù)空間。給定八叉樹的深度為D，基函數(shù)F為：

(2)

其中，*n表示n次卷積。這樣，八叉樹上的某一節(jié)點o相對應(yīng)的函數(shù)Fo即可定義為：

(3)

(4)

(5)

(6)

Δχ=

(7)

∑o‖〈Δχ,Fo〉-〈2=

∑o′‖∑oxo〈ΔFo,Fo′〉-〈2

(8)

2)提取等值面。先估計采樣點的位置，然后將其平均值用于等值面提取，為得到較好的重構(gòu)表面，需要選擇合適的閾值，然后用移動立方體算法(Marching Cubes，MC)得到等值面，最終獲得重建后的模型。

本文提出的基于點云增強的網(wǎng)格化優(yōu)化算法基本思路為：針對點云進(jìn)行適當(dāng)?shù)念A(yù)處理操作，因為不論用何種方式獲取點云，都避免不了噪聲的出現(xiàn)，因此通過統(tǒng)計濾波實現(xiàn)對明顯離群點的剔除；由于傳統(tǒng)網(wǎng)格化重建算法隨著點云數(shù)據(jù)的擴大，重建時間也將越來越長，為了降低重建所用時間，通過體素濾波選擇適當(dāng)體素大小，在不丟失細(xì)節(jié)的基礎(chǔ)上對初始點云進(jìn)行降采樣；針對點云數(shù)據(jù)存在孔洞的問題，采用雙三次樣條插值修復(fù)孔洞，提高重建質(zhì)量；之后，由于傳統(tǒng)泊松重建算法采用的主成分分析法在估計點云法向量時存在法向方向不一致的問題，因此采用將移動最小二乘法誤差函數(shù)引入到點云法向計算的方式對算法進(jìn)行優(yōu)化。最終優(yōu)化后的網(wǎng)格化重建算法較傳統(tǒng)重建算法提高了重建效率和準(zhǔn)確度，優(yōu)化后的網(wǎng)格化重建流程如圖2所示。

圖2 優(yōu)化后的網(wǎng)格化重建流程圖

1.1 點云濾波

不論是采用三維激光掃描儀或者是基于圖像獲取的點云，由于設(shè)備、人員、外部條件等各方面因素，獲取的點云數(shù)據(jù)中不可避免的摻雜著噪聲點與離群點，嚴(yán)重影響重建的效率與精度，因此本文采用統(tǒng)計濾波實現(xiàn)明顯離群噪點的剔除。因離群點的主要特征是在空間中稀疏分布，則可以定義某處點云如果小于某個密度則代表點云無效，具體思想是計算點云中每個點與其最近鄰的K個點的平均距離，則所有點的平均距離應(yīng)滿足高斯分布，這樣就可以根據(jù)均值μ和標(biāo)準(zhǔn)差σ確定一個距離閾值，當(dāng)某一點的平均距離大于這個閾值時，則判定該點為離群點并剔除，算法具體步驟如下：

1)遍歷點云S并計算每個點pi與其最近鄰的K個點的平均距離di。

2)計算平均距離di的均值μ和標(biāo)準(zhǔn)差σ。

3)定義距離閾值為dmax=μ+α×σ，其中，α為比例系數(shù)，它取決于鄰近點的數(shù)目。

4)遍歷點云剔除平均距離di大于dmax的點。

因為傳統(tǒng)曲面重建算法隨著點云規(guī)模的擴大，重建時間也隨之增加，為了在最大限度地在保留原始點云幾何信息的同時提高重建效率，采用體素濾波對點云進(jìn)行降采樣。其主要思想是在點云數(shù)據(jù)所在三維空間創(chuàng)建一個體素柵格，使用AABB包圍盒將點云數(shù)據(jù)體素化，對于柵格內(nèi)的每一個體素，體素中的點將由體素內(nèi)包括的所有點的重心近似代替，最終由所有體素的重心構(gòu)成濾波后的點云，實現(xiàn)點云的降采樣。通過調(diào)整包圍盒的大小可以控制體素的大小，進(jìn)而控制降采樣的程度，同時，體素濾波也在一定程度上去除了噪聲點及離群點。

1.2 孔洞修復(fù)

傳統(tǒng)泊松曲面重建的一大弊端就是易把孔洞區(qū)域錯誤連接，產(chǎn)生冗余面片,影響重建效果，眾所周知，曲面可由二元函數(shù)表示，故本文針對這一弊端采用雙三次樣條插值函數(shù)對孔洞進(jìn)行修復(fù)，以提高點云質(zhì)量。

由于雙三次樣條函數(shù)是2個一元三次樣條函數(shù)的直積，在x軸方向上分割Δx的三次樣條函數(shù)的全體構(gòu)成一個(m+3)維的線性空間S(x,Δx)，在y軸方向上分割Δy的三次樣條函數(shù)的全體構(gòu)成一個(n+3)維的線性空間S(y,Δy)。則將定義域R分割為Δ=Δx?Δy后，雙三次樣條函數(shù)的全體構(gòu)成一個(m+3)×(n+3)維的線性空間S(x,y,Δ)，即：

S(x,y,Δ)=S(x,Δx)?S(y,Δy)

(9)

(10)

(11)

這樣，S(x,y,Δ)中任一雙三次樣條函數(shù)都可表示為：

(12)

其中，αk,l為待定系數(shù)。由于采樣點被分割成m×n個子矩形網(wǎng)格，故根據(jù)矩形4條邊界上所有節(jié)點的一階法向偏導(dǎo)數(shù)以及4個角點的二階混合偏導(dǎo)數(shù)結(jié)合插值條件S(xi,yj)就能算出待定系數(shù)αk,l，進(jìn)而得出插值表達(dá)式和插值結(jié)果。

經(jīng)過上述插值操作之后，形成了一部分新的采樣點，使得點云孔洞在一定程度上得以修復(fù)，提高了重建模型的準(zhǔn)確度。

1.3 法向估算優(yōu)化

傳統(tǒng)泊松表面重建，點云法向計算的準(zhǔn)確性直接影響重建模型的質(zhì)量，而傳統(tǒng)的法向計算方法大都使用主成分分析法(PCA)，然而此算法易受噪聲等因素干擾而產(chǎn)生誤差，因此本文通過加入MLS優(yōu)化誤差函數(shù)，以計算出更加精準(zhǔn)的法向量。具體算法步驟如下：

1)使用八叉樹得到點p的最近鄰pn,n=1,2,…,n。

3)計算點p對應(yīng)的協(xié)方差矩陣C，算出對應(yīng)的特征值與特征向量，協(xié)方差矩陣C的計算表達(dá)式為：

(13)

4)對得出的法向量進(jìn)行方向一致性處理，已知視點ν，若方程滿足ni·(ν-pi)>0，則法線ni方向無需調(diào)整，否則，該法向量取反方向。

5)引入的MLS優(yōu)化誤差函數(shù)式為：

(14)

其中，α取輸入點p處的加權(quán)法向量，θ(‖p-pi‖)定義為：

(15)

其中，h為高斯函數(shù)影響因子。利用上述誤差函數(shù)式對求得的法向量進(jìn)行誤差分析，將誤差大于一定閾值的法向量予以去除。

2 實驗結(jié)果與分析

為了驗證所提出算法的可行性和有效性，本文采用已有的rabbit、dragon等點云模型作為驗證對象。實驗運行環(huán)境為:Intel(R)Core(TM)i7-8750H,CPU@2.20 GHz 2.21 GHz，運行內(nèi)存為16 GB，實驗平臺為Visual Stduio 2017以及PCL點云庫版本為1.9.1。

本文在傳統(tǒng)網(wǎng)格化重建算法的基礎(chǔ)上對點云數(shù)據(jù)進(jìn)行預(yù)處理，通過對dragon點云模型的對比實驗，可以明顯看出，在保證不丟失細(xì)節(jié)特征的基礎(chǔ)上，點云數(shù)量在一定程度上得以減少，使后續(xù)重建效率得以提升。圖3顯示了dragon點云模型預(yù)處理前后的點云對比情況。其中，預(yù)處理前dragon點云整體如圖3(a)所示，預(yù)處理前dragon點云局部如圖3(b)所示，預(yù)處理后dragon點云整體如圖3(c)所示，預(yù)處理后dragon點云局部如圖3(d)所示。同時，表1記錄了預(yù)處理前后不同點云的數(shù)量變化，通過觀察可以得出點云密集程度有所降低但細(xì)節(jié)特征保存完整。

(a)預(yù)處理前dragon點云整體

表1 不同點云預(yù)處理前后點云數(shù)量對比

圖4顯示了不同算法的法向估計效果圖。其中，圖4(a)為預(yù)處理后的rabbit點云，因傳統(tǒng)泊松算法和貪婪投影三角算法所用法向估計的方法相同，故圖4(b)為2種傳統(tǒng)算法的法向估計效果圖，圖4(c)為文獻(xiàn)[9]算法的法向估計效果圖，圖4(d)為本文優(yōu)化算法的法向估計效果圖。由于法向量應(yīng)垂直于其所在位置的表面，若不垂直即為錯誤，反之正確。不難看出，由于噪點的干擾，傳統(tǒng)算法的方向一致性較差，特別是角點與邊緣部分，相比之下，在對初始點云進(jìn)行適當(dāng)處理之后，文獻(xiàn)[9]算法雖在角點與邊緣部分的法向一致性有所改善但方向錯誤的法線仍明顯多于本文算法，因此本文算法為后期表面重建提供了更為精確的法線從而提高了重建精度。

(a)預(yù)處理后的rabbit點云

表2記錄了傳統(tǒng)泊松重建算法、文獻(xiàn)[9]算法、貪婪投影三角重建算法以及本文提出的優(yōu)化重建算法重建各類模型所用總時間。從表2容易看出，文獻(xiàn)[9]算法相較于與傳統(tǒng)重建算法所用時間有所減少，本文算法相比之下重建效率進(jìn)一步提升，但相較于貪婪投影三角重建算法區(qū)域增長的更快速，本文算法引入了誤差函數(shù)來優(yōu)化法向計算，因此耗時較長。

表2 不同算法重建時間對比

圖5顯示了4種不同算法對不同點云模型的重建效果對比。其中，圖5(a)為傳統(tǒng)泊松算法重建效果圖，圖5(b)為文獻(xiàn)[9]算法重建效果圖，圖5(c)為貪婪投影三角重建效果圖，圖5(d)為本文優(yōu)化算法重建效果圖。不難看出，傳統(tǒng)泊松重建容易生成冗余面片，誤差較大；文獻(xiàn)[9]算法相較于傳統(tǒng)泊松算法，細(xì)節(jié)特征更明顯，表面更光滑，但未解決冗余面片的問題；貪婪投影三角重建算法雖細(xì)節(jié)豐富，但孔洞問題較為嚴(yán)重；本文算法相比之下，表面細(xì)節(jié)較為豐富，一定程度上解決了孔洞和冗余面片的問題。

(a)傳統(tǒng)泊松算法重建

圖6所示的是本文算法對不同點云的網(wǎng)格化重建結(jié)果，其中，圖6(a)為horse重建效果圖，圖6(b)為hand重建效果圖，圖6(c)為happy buddha重建效果圖。不難看出，本文算法重建模型表面光滑且細(xì)節(jié)較為豐富，視覺上與實際三維模型更接近，同時也驗證了本文算法的通用性。

(a)horse重建模型

根據(jù)2個定量分析精度評價指標(biāo)，對4種不同重建算法的重建結(jié)果進(jìn)行定量精度評價。本文所用模型均為網(wǎng)上開源模型，其初始點云和模型都存在，即存在初始的比較對象。將重建模型與初始模型進(jìn)行比較時，如果坐標(biāo)系不同，需要首先將2個模型對齊到同一世界坐標(biāo)系下，然后采用ICP算法精配準(zhǔn)2個點云，此時認(rèn)為2個模型基本已經(jīng)對齊。之后計算其中一個點云中任意一點到另一個點云的最近臨點距離或者最近臨面片的距離，一般將所有點的的距離的方差、均值、最大值、最小值作為精度的考量，將匹配點與所有點的比值作為準(zhǔn)確度的考量?？紤]初始點云數(shù)據(jù)的存在不完整性等問題，故在評價時會將5%的最近鄰的異常值濾除，評價結(jié)果如表3和表4所示。貪婪投影三角重建算法面片數(shù)量約為傳統(tǒng)泊松算法的2.2倍，模型準(zhǔn)確度提升到90.56%；本文算法與文獻(xiàn)[9]算法和傳統(tǒng)泊松重建算法相比，面片數(shù)量有了一定提升，同時本文算法的精度比文獻(xiàn)[9]算法提高了0.1 mm，比傳統(tǒng)泊松重建算法提高了0.2 mm，模型準(zhǔn)確度提升到92.74%，可以得出，本文優(yōu)化算法提高了準(zhǔn)確度。

表3 不同算法重建模型面片數(shù)量對比

表4 不同算法重建精度評價對比

3 結(jié)束語

本文提出了一種基于點云增強的網(wǎng)格化重建優(yōu)化算法，使得重建效率和重建準(zhǔn)確度在一定程度上得以提高。本文利用統(tǒng)計濾波對初始點云進(jìn)行降噪處理，同時通過體素濾波進(jìn)行適當(dāng)點云降采樣，使得點云數(shù)量在一定程度上適當(dāng)減少，再利用雙三次樣條插值對點云孔洞進(jìn)行修復(fù)，使得孔洞區(qū)域得到較好的改善，然后利用MLS誤差函數(shù)優(yōu)化點云法向量的質(zhì)量降低了冗余面片出現(xiàn)的可能。但本文算法中，濾波參數(shù)以及法線計算中涉及的參數(shù)需要經(jīng)過多次調(diào)試才能確定合適的值，并且無法對表面模型進(jìn)行細(xì)微的調(diào)整，因此，如何在進(jìn)一步提升重建效率和準(zhǔn)確度的基礎(chǔ)上，找到某一可控參數(shù)來調(diào)整表面細(xì)節(jié)是今后努力研究的方向。