結合平面投影與區域生長的點云表面重建

張曉帥，華順剛

（大連理工大學機械工程學院，遼寧大連 116024）

0 引言

點云數據的表面重建是在已有點云數據的基礎上還原空間點的幾何拓撲結構，恢復物體模型的表面形狀[1]。點云表面重建技術已經被廣泛應用于制造業、醫療、文物保護以及地形測量等領域。隨著技術手段的進步，獲取的點云數據量越來越大，如何準確快速地處理這些數據，成為目前的緊要問題。

目前，表面重建的算法主要有Kazhdan[2]和劉濤等[3]提出的泊松算法；Kuo[4]和薄志成等[5]提出的區域生長法；Edelsbrunner等[6]提出的四面體法；Gopiy[7]和李鳳霞等[8]提出的平面投影方法等。

本文提出一種平面投影與區域生長相結合的散亂點云曲面重建方法。通過局部點云離散度計算，自適應地選擇不同的重建方法，提高了重建效率，減少了重建時間。

1 基于平面投影的點云表面重建

基于平面投影的點云重建是利用空間點云的局部平面性，將局部點集投影到二維平面上，再用平面三角剖分的算法生成三角形，最后將生成的三角關系還原回三維空間。該方法包括求取K鄰域、平面擬合、平面投影、Delaunay三角剖分等幾個步驟。

1.1 求取K鄰域及其平面擬合

在對三維點云進行投影之前，要先獲取目標點的K個近鄰點，如果用遍歷點集的方法來尋找，會導致搜索時間過長。本文采用包圍盒法來加快尋找速度，其原理是先將空間劃分成許多個小柵格，并為其編號。求中心點的K個臨近點時，先在中心點所在的柵格內進行搜索，若得不到K個臨近點，則進一步搜索臨近的柵格[9]。

求得K鄰域點集后，需要利用點集擬合一個二維平面，將空間點集投影到該平面上。本文采用最小二乘法來進行平面擬合。設其平面方程為z=ax+by+c，利用最小二乘法可以求解出平面參數。

1.2 二維平面投影及三角剖分

在求取出K鄰域點集及其擬合平面后，應將這些點投影到擬合的二維平面上，對投影點進行二維的Delaunay三角網格化，最后將網格拓撲信息還原到三維空間中，生成空間網格模型，如圖1所示。

圖1 空間點的投影及其網格拓撲關系映射

1.3 投影法存在問題

平面投影的方法對于比較平滑的表面具有良好的重建效果，但有些情況下，投影生成的網格投射回三維空間時會發生失真。如圖2所示，由于點云在空間中的密度分布不均勻導致重構過程中產生孔洞；由于投影重疊產生的錯誤拓撲關系等等。

圖2 重建失真實例

為了避免基于投影的方法生成的網格映射回三維平面后發生嚴重失真，需要對點集的離散度進行判斷，符合離散度要求的用平面投影來重建，不符合要求則采用區域生長法重建。

2 平面投影與區域生長相結合

本文利用局部點集的離散度來確定其重建方法，即通過偏移局部點集的擬合平面來生成兩個平行平面，如果所有點都在兩個平行平面之內，說明該部分點集離散度較小，可以用平面投影的方法重建該部分點集。如果存在某些點處于兩個平行平面之外，則說明該區域的點集離散度過大，若用平面投影重建該部分點集，會產生較大的失真，應采用區域生長法進行空間三角形剖分。區域生長法在重建表面時，可利用各種原則來對第三點進行過濾，比較精確地還原模型的表面。

2.1 局部點集的離散度判斷

判斷點集離散度的上、下界面由擬合平面偏移得到，如圖3所示。偏移量m用m=±β×dˉ來求解，dˉ為中心點與周圍連接點距離的平均值；β是一個系數，可以通過其來調整偏移量的大小。實驗證明，β取40%可以得到比較好的效果。如果存在某些點處于上、下界之外，則說明該區域的點集離散度不符合條件。

圖3 局部點集在擬合平面附近的分布情況

實驗表明，使用平面投影的方法可完成60%～70%的點云表面重建，如圖4所示。這樣，較平滑的部分已經重建完成，對于剩下的部分采用區域生長法進行重建。

圖4 符合離散度要求的點集重建后的表面

2.2 區域生長算法改進

區域生長算法是從現有三角形的某一條邊出發，基于某些優化判定準則，不斷選擇新的點與其構成新三角形，直到遍歷所有點。常用的候選點篩選原則有最小內角最大原則、最大邊長限制等。

為了提高重建后表面的質量，避免產生孔洞和錯誤的拓撲關系，本文對區域生長算法進行如下改進。

（1）增加擬合平面上空外接圓原則。利用候選點集與生長邊的兩個端點擬合一個平面，將這些點投影到擬合平面上，判斷每一個候選點與生長邊組成的三角形的外接圓應是否包含其他點，若包含其他點，則從候選點集中刪去該點。如圖5所示，當候選點C與生長邊AB處于不同的表面時，其在擬合平面上的投影點所形成的三角形的外接圓會包含點D，因此應當在候選點集中去除點C，該方法可以防止出現錯誤的拓撲連接。

圖5 局部點集及其在擬合平面上的投影

（2）分階段進行重建。區域生長算法進行重建時，若最大邊長和最小內角閾值過大，會容易生成錯誤的拓撲連接，降低模型表面的精確度；若閾值過小，則在點云稀疏的地方會因找不到滿足條件的候選點而產生孔洞。因此本文的重建過程分兩個階段，第一階段選取較小的閾值來保證重建表面的質量，然后選取較大的閾值進行第二次重建，以填補網格的孔洞。

3 實驗結果及分析

為了驗證提出算法的有效性，在Win7環境下用C++編寫程序，使用OpenGL圖形庫對點云和網格進行渲染，使用MFC框架實現可視化界面。實驗計算機配置為Intel（R）Core（TM） i5-4590 3.30 GHz CPU，8 G運行內存。表面重建的實例如圖6所示。本文的算法在龍的嘴巴處可以很好地將上下頜分離開，點云比較稀疏的貓鼻子部分也沒有孔洞出現。本文算法的細節部分處理得比較好，對于點云密度分布不均的區域也能夠比較準確地進行表面重建。

4 結束語

本文算法結合了平面投影重建速度快和區域生長法準確度高的優點，把符合離散度條件的局部點集投影到二維平面上進行重建，降低了表面重建的復雜度，提高了表面重建的速度。用改進的區域生長法重建細節特征比較復雜、曲率變化比較大的部分，保證了重建表面的準確度。由于在區域生長算法中使用了擬合平面上空外接圓原則和分階段重建的策略，避免了產生孔洞和錯誤的拓撲關系，保證了重建表面的完整性，提高了對點云模型的適應性。

圖6 重建實例