張曉帥，華順剛

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

0 引言

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

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

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

1 基于平面投影的點(diǎn)云表面重建

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

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

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

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

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

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

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

1.3 投影法存在問題

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

圖2 重建失真實(shí)例

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

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

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

2.1 局部點(diǎn)集的離散度判斷

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

圖3 局部點(diǎn)集在擬合平面附近的分布情況

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

圖4 符合離散度要求的點(diǎn)集重建后的表面

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

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

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

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

圖5 局部點(diǎn)集及其在擬合平面上的投影

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

3 實(shí)驗(yàn)結(jié)果及分析

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

4 結(jié)束語

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

圖6 重建實(shí)例