法向約束的點(diǎn)云數(shù)據(jù)泊松表面重建算法

魯猛勝 姚 劍 董賽云

1武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢，430079

三維點(diǎn)云表面重建是對三維激光掃描儀等測量設(shè)備得到的物體表面點(diǎn)云數(shù)據(jù)進(jìn)行三維建模的過程，在逆向工程、數(shù)字保護(hù)、工業(yè)檢測、增強(qiáng)現(xiàn)實(shí)、智慧城市等領(lǐng)域［1-3］，對三維物體表達(dá)模型的需求不斷增加。由于點(diǎn)云會存在噪聲、分布不均勻和局部數(shù)據(jù)缺失等問題，因此需要恰當(dāng)?shù)臄?shù)學(xué)模型和高效的算法來提高重建精度和減少運(yùn)算復(fù)雜度。

目前點(diǎn)云表面重建方法主要分為基于計算幾何［4］和基于隱函數(shù)擬合［5］兩種方法，相較前者基于隱函數(shù)擬合的方法能對含有噪聲的非均勻點(diǎn)云數(shù)據(jù)進(jìn)行高魯棒性的網(wǎng)格化處理。常見的隱函數(shù)擬合方法有基于徑向基函數(shù)［6］、基于符號距離函數(shù)［7，8］和基于指示函數(shù)［9-11］的表面重建方法。

泊松重建算法是基于指示函數(shù)的表面重建方法，它綜合了全局和局部擬合的優(yōu)點(diǎn)，通過局部基函數(shù)的層次構(gòu)造，在整體上進(jìn)行一致性的誤差分配，從而轉(zhuǎn)化為泊松空間問題進(jìn)行求解。該方法能得到較為平滑的表面模型，對噪聲有一定的容忍度，是表面重建領(lǐng)域的主流方法。但由于其依賴于準(zhǔn)確的法向，而且未充分利用點(diǎn)云的結(jié)構(gòu)信息，導(dǎo)致重建得到的表面與真實(shí)情況有一定的偏離。

本文在屏蔽泊松重建算法的基礎(chǔ)上，充分利用法向信息，針對性約束法向不準(zhǔn)確的區(qū)域，將法向準(zhǔn)確度分別定位到屏蔽泊松方程中的采樣點(diǎn)權(quán)重分配和多重網(wǎng)格求解的八叉樹節(jié)點(diǎn)擴(kuò)展中，最終既能保持模型的顯著細(xì)節(jié)，又提高了重建表面的準(zhǔn)確度，同時也減少了內(nèi)存開銷。

1 法向約束的屏蔽泊松重建

法向約束的泊松重建算法流程如圖1所示。

圖1 算法流程圖Fig.1 Flow Chart of Algorithm

首先針對點(diǎn)云進(jìn)行法向估計，初始法向通過主成分分析法進(jìn)行估計，最終法向則通過文獻(xiàn)［12］中的自適應(yīng)鄰域法向迭代估計法獲取，兩者偏差值在高斯分布下的區(qū)間置信度即為法向準(zhǔn)確度。然后結(jié)合法向準(zhǔn)確度調(diào)整屏蔽泊松方程中的采樣點(diǎn)權(quán)重，在各個分辨率下均得到更好的位置約束。同時在多重網(wǎng)格求解時，針對性地約束具有不準(zhǔn)確法向的點(diǎn)云格網(wǎng)的八叉樹擴(kuò)展。最后求解屏蔽泊松方程，并利用移動立方體算法提取等值面，生成更為貼合的表面模型。

1.1 法向估計和置信度計算

在理想情況下，點(diǎn)云重建表面光滑，可以通過平面來擬合點(diǎn)的局部信息，因此利用主成分分析（principal component analysis，PCA）方法可以準(zhǔn)確得到法向n a。給定點(diǎn)云任意一點(diǎn)p，其k鄰域點(diǎn)集N b(p)={p1，p2，...，p k}，則根據(jù)鄰域擬合的平面可以表示為：

式中，n a為歸一化后的擬合平面H的法向量；d表示點(diǎn)p到擬合平面H的距離。通過對式（1）構(gòu)成的協(xié)方差矩陣進(jìn)行特征值分解，所求取的最小特征值λmin對應(yīng)的特征向量vmin也就是擬合平面的法向量，即n a=vmin。

利用PCA方法估計的初始法向n a在表面光滑處較準(zhǔn)確，而應(yīng)用到相對銳利區(qū)域，鄰域特征由于具有各向同性而不顯著。按照文獻(xiàn)［12］針對尖銳特征的法向估計方法的原理，將其運(yùn)用到最終法向的估計上，即：

式中，w n(n b)表示法向偏差的高斯權(quán)重表示第t次迭代點(diǎn)p i的殘差，所求得最小特征值對應(yīng)的特征向量即為每次迭代的法向。

自適應(yīng)法向迭代估計的最終法向n b更為精準(zhǔn)，點(diǎn)p的初始和最終法向之間的夾角θ可以反應(yīng)真實(shí)模型曲面的曲率，隨著θ的增大，擬合表面的法向越來越不穩(wěn)定，即該區(qū)域更有可能是雜亂的表面。通過計算所有點(diǎn)云的θ值得到均值μ和方差σ2，在高斯分布下根據(jù)每個樣本點(diǎn)所在分布區(qū)間，確定每個點(diǎn)最終的置信度αi，即點(diǎn)云的法向準(zhǔn)確度。

1.2 法向約束的采樣點(diǎn)權(quán)重分配

原始泊松重建直接尋求向量場到指示函數(shù)梯度場的最佳近似，會導(dǎo)致所求得的表面模型有一個全局性的偏移，而屏蔽泊松算法則通過添加位置約束以使所有采樣點(diǎn)的誤差得到修正：

式中，λ為屏蔽因子，權(quán)衡梯度約束和位置約束的比重；Area(S)表示采樣點(diǎn)附近的重建表面區(qū)域；τ(p)表示鄰域點(diǎn)的權(quán)重，在屏蔽泊松算法中所有樣本點(diǎn)的權(quán)重都為1。

然而屏蔽泊松算法對所有樣本點(diǎn)取相同權(quán)重，使法向不準(zhǔn)確的樣本點(diǎn)也能施加足夠的位置約束，從而導(dǎo)致各分辨率下的求解都不精確。如圖2所示，在離散化過程中，需要進(jìn)行由粗到細(xì)的求解，對應(yīng)逐漸加深的八叉樹。在每個分辨率下，各網(wǎng)格的估計結(jié)果通過計算落入該網(wǎng)格的所有樣本點(diǎn)的數(shù)量和平均位置得到，即分層聚類。顯然當(dāng)樣本點(diǎn)法向不可靠時，引入同樣的權(quán)重會導(dǎo)致各粒度下的估計結(jié)果都存在一定的偏離。因此通過對樣本點(diǎn)p i根據(jù)法向置信度來分配權(quán)重，以求取各粒度下的更為精確的解，即：

圖2 不同分辨率下的權(quán)重分配Fig.2 Weight Distribution at Different Resolutions

式中，φ為歸一化參數(shù)。

1.3 法向約束的八叉樹擴(kuò)展

在屏蔽泊松算法中，給定最大深度D，如圖3所示，自適應(yīng)的八叉樹僅在有樣本點(diǎn)的區(qū)域細(xì)分。在進(jìn)行多重網(wǎng)格求解時，每個深度都有對應(yīng)的B樣條基函數(shù)簇，分別對應(yīng)所在深度的八叉樹節(jié)點(diǎn)，顯然B樣條函數(shù)并非都能在每一層上完全充滿整個函數(shù)空間，而且也存在兩兩非正交，這樣父節(jié)點(diǎn)的B樣條函數(shù)不僅僅來自于它的所有子節(jié)點(diǎn)，因此需要特別存儲上一層的結(jié)果。為了解決這一問題，屏蔽泊松算法對原始八叉樹進(jìn)行擴(kuò)展，即對B樣條函數(shù)空間進(jìn)行擴(kuò)充［14］。如圖3（a）所示，對于深度為d的節(jié)點(diǎn)，它的上一層d-1中相互非正交的基函數(shù)也必須存在，如圖3（b）所示，紅色點(diǎn)的深度為d，則需要在粗粒度上添加新的八叉樹節(jié)點(diǎn)，得到圖3（c）的結(jié)果。

但是假定紅色點(diǎn)的法向置信度αi＜δ（δ為閾值），則應(yīng)該排除對該點(diǎn)處的擬合，即不需要對它所在的八叉樹節(jié)點(diǎn)進(jìn)行向上擴(kuò)展，即得到圖3（d）所示的結(jié)果，這樣既可避免過擬合，又將節(jié)省內(nèi)存開銷和運(yùn)行時間。應(yīng)當(dāng)注意到圖3（d）中的效果是理想化的，因為該區(qū)域的部分八叉樹單元可能還受其他樣本點(diǎn)的影響而得到擴(kuò)展，但針對法向置信度小于閾值的若干樣本點(diǎn)，仍然能在一定程度上避免全部擴(kuò)展。

圖3多重網(wǎng)格和八叉樹擴(kuò)展Fig.3 Multigrid and Octree Enrichment

2 表面重建結(jié)果與分析

2.1 數(shù)據(jù)集

為了驗證算法的適用性和有效性，本文采用具有不同特點(diǎn)的多種數(shù)據(jù)集進(jìn)行對比實(shí)驗，主要包括以下3種：

1）斯坦福三維掃描數(shù)據(jù)集（以下稱Stanford），點(diǎn)云較為均勻，包含Buddha、Lucy和Bunny等；

2）EPFL多視圖密集重建數(shù)據(jù)集（以下稱EPFL），其模型存在較多數(shù)據(jù)缺失，包含Eagle、Monkeys、Paderwski等；

3）文獻(xiàn)［13］提供的存在非均勻采樣、噪聲和誤匹配等多種掃描誤差的數(shù)據(jù)集（以下稱Berger），主要包含有Daratech、Quasimodo、Dancing Children等模型。

2.2 實(shí)驗參數(shù)和邊界條件

本文主要與原始泊松算法和屏蔽泊松算法進(jìn)行比較，其中參數(shù)按照算法作者建議的進(jìn)行設(shè)置，如原始泊松算法屏蔽因子λ=0，屏蔽泊松算法中λ=4等。本文算法參數(shù)均與屏蔽泊松算法保持一致，而法向迭代估計具有參數(shù)自適應(yīng)性，法向置信度能適應(yīng)不同點(diǎn)云數(shù)據(jù)的法向偏差分布，而針對八叉樹擴(kuò)展的置信度閾值δ也均取最好結(jié)果。

狄里克萊條件和諾依曼條件分別是針對邊界和邊界梯度的約束，而后者在測繪遙感和計算機(jī)視覺領(lǐng)域運(yùn)用更為廣泛，因此結(jié)合采用的數(shù)據(jù)集，進(jìn)行的實(shí)驗均采用諾依曼邊界條件約束［15］，然而應(yīng)當(dāng)注意到當(dāng)存在數(shù)據(jù)缺失時的情況。圖4為EPFL數(shù)據(jù)集中Eagle模型的結(jié)果，圖4（b）、4（c）、4（d）的上下子圖分別為狄里克萊和諾依曼條件約束，諾依曼邊界條件會對該數(shù)據(jù)缺失區(qū)域缺乏限制而生成偽曲面，但本文算法由于針對性約束法向不準(zhǔn)確樣本點(diǎn)，因而取得了更好的重建效果。

圖4 邊界條件對比結(jié)果圖Fig.4 Comparison Result with Different Boundaries

2.3 性能評價指標(biāo)

本文主要通過兩種指標(biāo)來進(jìn)行評價：①樣本點(diǎn)到重建表面距離的均方根誤差（root mean squared error，RMSE）；②重建表面到數(shù)據(jù)集提供的真實(shí)參照表面的豪斯多夫距離（Hausdorff distance，HD）。

2.4 結(jié)果與分析

本文的所有實(shí)驗均在配置為2.3 GHz的四核Intel Core i5 CPU和16GB RAM的計算機(jī)上進(jìn)行，并采用OpenMP進(jìn)行并行加速處理。

為了評估本文算法的準(zhǔn)確性，選取具有不同特點(diǎn)的數(shù)據(jù)集中的9個模型對本文算法進(jìn)行了RMSE和HD的準(zhǔn)確率對比評價，所有的重建深度均為10，得到如表1所示的結(jié)果。其中兩種評價指標(biāo)下的每行數(shù)據(jù)均通過與最大值作比較而得到歸一化處理，值越小表示越準(zhǔn)確，最好的結(jié)果在表1中通過加粗顯示。另外由于EPFL數(shù)據(jù)集提供的參照重建表面也是通過屏蔽泊松算法獲取，因此不進(jìn)行對照，其HD一欄為空。從表1中可以看到，本文算法在不同類型的數(shù)據(jù)集上有一定程度的精度提升，其中HD值在Stanford和Berger數(shù)據(jù)集的5個模型中，均取得了最優(yōu)結(jié)果，而Bunny模型也表現(xiàn)出相近的精度，但本文算法的RMSE值在所有的模型中不甚突出。這是由于屏蔽泊松算法更依賴于位置約束，從而使點(diǎn)云更加貼近生成的表面模型，但由于噪聲、數(shù)據(jù)缺失、誤匹配的存在，會導(dǎo)致估計的法向不準(zhǔn)確，從而生成的表面在這些區(qū)域過度擬合，因此屏蔽泊松算法的HD值相對較高，如圖5所示的Dancing Children模型。

圖5 Dancing Children模型的重建結(jié)果對比圖Fig.5 Comparison Result of Reconstruction Surface on Dancing Children

由表1觀察到在EPFL數(shù)據(jù)集的Eagle、Monkeys和Paderwski這3個模型中，屏蔽泊松算法表現(xiàn)出最差的結(jié)果，主要是因為它們均存在著較多的數(shù)據(jù)缺失（見圖4），導(dǎo)致屏蔽泊松算法生成了大量偽曲面。而本文算法則對此進(jìn)行針對性地約束，根據(jù)法向置信度給予權(quán)重分配，減弱了邊緣噪點(diǎn)的影響，得到更低的RMSE值。

本文算法的運(yùn)行效率測試對比如表2所示，對Berger數(shù)據(jù)集中存在較多噪聲和數(shù)據(jù)缺失的Monkeys模型進(jìn)行實(shí)驗，重建深度均為11，分別比較了不同置信度閾值參數(shù)δ的結(jié)果，并與原始泊松和屏蔽泊松算法作對比，與表1中一樣，這里RMSE也作了歸一化處理。從表2中可以看到，本文算法在不同閾值參數(shù)下，其運(yùn)行時間和內(nèi)存開銷均有一定程度的減少，并隨著閾值δ的下降而逐漸降低，可以證明本文算法能有效抑制不準(zhǔn)確法向樣本點(diǎn)的八叉樹擴(kuò)展，提高運(yùn)行效率。應(yīng)當(dāng)注意到以原始泊松算法作對比，在該模型上屏蔽泊松算法有更多的偽曲面生成，而本文算法的δ的選取也應(yīng)當(dāng)考慮準(zhǔn)確擬合的效果。

表1 不同數(shù)據(jù)集模型下的定量對比結(jié)果Tab.1 Quantitative Comparison Results Under Different Datasets Models

表2 Monkeys模型上的運(yùn)行效率對比結(jié)果Tab.2 Results about Computational Efficiency on Monkeys Model

3 結(jié)束語

本文從屏蔽泊松方程在法向不準(zhǔn)確區(qū)域約束不足的角度出發(fā)進(jìn)行改進(jìn)，充分利用點(diǎn)云的法向信息針對性約束不準(zhǔn)確樣本點(diǎn)，通過利用PCA算法和自適應(yīng)法向迭代估計法確定初始和最終法向，以評價法向置信度，并將該約束分別引入到位置約束的權(quán)重分配和多重網(wǎng)格求解時的八叉樹擴(kuò)展中，以減弱或消除不可靠樣本點(diǎn)擬合效果。在3種不同特點(diǎn)的數(shù)據(jù)集上進(jìn)行的實(shí)驗結(jié)果表明，本文算法在大多數(shù)模型上均取得了更精確的重建結(jié)果，而且也在一定程度上減少了運(yùn)行時間和內(nèi)存開銷。