張曉帥，華順剛

（大連理工大學(xué)機(jī)械工程學(xué)院，遼寧大連 116024）

0 引言

點云數(shù)據(jù)的表面重建是在已有點云數(shù)據(jù)的基礎(chǔ)上還原空間點的幾何拓?fù)浣Y(jié)構(gòu)，恢復(fù)物體模型的表面形狀[1]。點云表面重建技術(shù)已經(jīng)被廣泛應(yīng)用于制造業(yè)、醫(yī)療、文物保護(hù)以及地形測量等領(lǐng)域。隨著技術(shù)手段的進(jìn)步，獲取的點云數(shù)據(jù)量越來越大，如何準(zhǔn)確快速地處理這些數(shù)據(jù)，成為目前的緊要問題。

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

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

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

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

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

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

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

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

在求取出K鄰域點集及其擬合平面后，應(yīng)將這些點投影到擬合的二維平面上，對投影點進(jìn)行二維的Delaunay三角網(wǎng)格化，最后將網(wǎng)格拓?fù)湫畔⑦€原到三維空間中，生成空間網(wǎng)格模型，如圖1所示。

圖1 空間點的投影及其網(wǎng)格拓?fù)潢P(guān)系映射

1.3 投影法存在問題

平面投影的方法對于比較平滑的表面具有良好的重建效果，但有些情況下，投影生成的網(wǎng)格投射回三維空間時會發(fā)生失真。如圖2所示，由于點云在空間中的密度分布不均勻?qū)е轮貥?gòu)過程中產(chǎn)生孔洞；由于投影重疊產(chǎn)生的錯誤拓?fù)潢P(guān)系等等。

圖2 重建失真實例

為了避免基于投影的方法生成的網(wǎng)格映射回三維平面后發(fā)生嚴(yán)重失真，需要對點集的離散度進(jìn)行判斷，符合離散度要求的用平面投影來重建，不符合要求則采用區(qū)域生長法重建。

2 平面投影與區(qū)域生長相結(jié)合

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

2.1 局部點集的離散度判斷

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

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

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

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

2.2 區(qū)域生長算法改進(jìn)

區(qū)域生長算法是從現(xiàn)有三角形的某一條邊出發(fā)，基于某些優(yōu)化判定準(zhǔn)則，不斷選擇新的點與其構(gòu)成新三角形，直到遍歷所有點。常用的候選點篩選原則有最小內(nèi)角最大原則、最大邊長限制等。

為了提高重建后表面的質(zhì)量，避免產(chǎn)生孔洞和錯誤的拓?fù)潢P(guān)系，本文對區(qū)域生長算法進(jìn)行如下改進(jìn)。

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

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

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

3 實驗結(jié)果及分析

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

4 結(jié)束語

本文算法結(jié)合了平面投影重建速度快和區(qū)域生長法準(zhǔn)確度高的優(yōu)點，把符合離散度條件的局部點集投影到二維平面上進(jìn)行重建，降低了表面重建的復(fù)雜度，提高了表面重建的速度。用改進(jìn)的區(qū)域生長法重建細(xì)節(jié)特征比較復(fù)雜、曲率變化比較大的部分，保證了重建表面的準(zhǔn)確度。由于在區(qū)域生長算法中使用了擬合平面上空外接圓原則和分階段重建的策略，避免了產(chǎn)生孔洞和錯誤的拓?fù)潢P(guān)系，保證了重建表面的完整性，提高了對點云模型的適應(yīng)性。

圖6 重建實例