魯猛勝 姚 劍 董賽云

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

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

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

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

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

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

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

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

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

1.1 法向估計和置信度計算

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

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

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

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

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

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

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

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

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

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

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

1.3 法向約束的八叉樹擴展

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 性能評價指標

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

2.4 結(jié)果與分析

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

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

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

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

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

3 結(jié)束語

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