法向約束的點云數據泊松表面重建算法

魯猛勝 姚 劍 董賽云

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

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

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

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

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

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

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

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

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

1.1 法向估計和置信度計算

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

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

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

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

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

1.2 法向約束的采樣點權重分配

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

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

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

圖2 不同分辨率下的權重分配Fig.2 Weight Distribution at Different Resolutions

式中，φ為歸一化參數。

1.3 法向約束的八叉樹擴展

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

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

圖3多重網格和八叉樹擴展Fig.3 Multigrid and Octree Enrichment

2 表面重建結果與分析

2.1 數據集

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

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

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

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

2.2 實驗參數和邊界條件

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

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

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

2.3 性能評價指標

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

2.4 結果與分析

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

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

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

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

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

表1 不同數據集模型下的定量對比結果Tab.1 Quantitative Comparison Results Under Different Datasets Models

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

3 結束語

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