武警工程大學(xué)研究生管理大隊(duì) 柳方明 張洪彪 李俊利

面向地形構(gòu)建的點(diǎn)云孔洞修補(bǔ)

武警工程大學(xué)研究生管理大隊(duì) 柳方明 張洪彪 李俊利

由于三維激光掃描儀在獲取點(diǎn)云數(shù)據(jù)時，受設(shè)備自身、環(huán)境、目標(biāo)物表面結(jié)構(gòu)等復(fù)雜因素影響，其獲取的點(diǎn)云數(shù)據(jù)往往存在局部孔洞，這對精確重建地形帶來了巨大的挑戰(zhàn)。本文針對真實(shí)地形點(diǎn)云數(shù)據(jù)存在的孔洞，結(jié)合Delaunay三角剖分與Loop細(xì)分算法，解決了地形孔洞難以修補(bǔ)這一難題。該算法首先連接距離最近的兩點(diǎn)，根據(jù)Delaunay三角形外接圓特性，以外接圓半徑增長的方式搜索三角形第3點(diǎn)，構(gòu)建種子三角形。隨后對新生成邊重復(fù)采用外接圓半徑增長的方式構(gòu)建新三角形，從而對所有散亂點(diǎn)云建立三角網(wǎng)拓?fù)浣Y(jié)構(gòu)，再以Loop細(xì)分的方式實(shí)現(xiàn)點(diǎn)云孔洞的修補(bǔ)，經(jīng)算例驗(yàn)證，本文算法可用于實(shí)際地形孔洞修補(bǔ)。

三角剖分；Loop細(xì)分；孔洞修補(bǔ)

三維建模是計算機(jī)研究的熱點(diǎn)之一，隨著三維激光掃描儀的更新?lián)Q代，三維激光掃描技術(shù)已經(jīng)可以全天候、高效率、高精度的獲取實(shí)體重建所需要的原始點(diǎn)云數(shù)據(jù)[1,2]。近年來，隨著國內(nèi)外學(xué)者對點(diǎn)云三維建模研究的不斷深入，在取得不少科研成果的同時，點(diǎn)云三維建模技術(shù)也開始廣泛應(yīng)用于逆向工程、醫(yī)療、古文物重建、工業(yè)鍛造、城市主體三維場景建模、地形侵蝕監(jiān)測等多個領(lǐng)域[3-5]。在逆向工程中，高精度的三維建?？梢钥s短生產(chǎn)周期，并提高產(chǎn)品生產(chǎn)效率；在醫(yī)療領(lǐng)域里，高精度掃描的點(diǎn)云數(shù)據(jù)經(jīng)建模后可進(jìn)行臉部、牙齒、耳朵等的畸形矯正；在文物保護(hù)領(lǐng)域，對具有上千年歷史的古文物的原型數(shù)字存儲、復(fù)原中，三維激光掃描儀也有非接觸、高精度等不可替代的優(yōu)勢。中華文化博大精深，古文物數(shù)不勝數(shù)，無數(shù)奇珍異寶，直接暴露在空氣中展覽，難免會對文物造成不可修復(fù)的損傷。實(shí)物重建后，利用3D打印技術(shù)，既起到保護(hù)文物的作用，亦可為游客展現(xiàn)中華瑰寶；而在城市規(guī)劃中，三維激光掃描技術(shù)可以提供良好的數(shù)據(jù)保證。在對實(shí)際地形進(jìn)行三維建模時，由于三維激光掃描儀在獲取點(diǎn)云數(shù)據(jù)時，受設(shè)備自身、環(huán)境、目標(biāo)物表面結(jié)構(gòu)等復(fù)雜因素影響，其獲取的點(diǎn)云數(shù)據(jù)往往存在局部孔洞。目前，由于點(diǎn)云數(shù)據(jù)處理難度大，技術(shù)門檻高，加之地形的不規(guī)則性，導(dǎo)致國內(nèi)對地形孔洞修補(bǔ)的進(jìn)程極度緩慢。而孔洞的存在嚴(yán)重影響了地形重建精度，本文結(jié)合Delaunay三角剖分與Loop細(xì)分，成功的的解決了這一難題，恢復(fù)了局部缺失的地形數(shù)據(jù)。

1 三角剖分算法

散亂點(diǎn)云的分布反映地形表面整體形態(tài)，對其三角剖分是構(gòu)建數(shù)據(jù)點(diǎn)拓?fù)潢P(guān)系，實(shí)現(xiàn)地形重建，揭示地形表面形態(tài)特征的一個關(guān)鍵環(huán)節(jié)。三角剖分后，每個三角形單元都代表地形很小的一個部分，相互鄰接的三角形網(wǎng)則整體反映地形表面模型。本文對Delaunay三角剖分算法研究，通過改進(jìn)一種原有的三角形生長算法[6]，利用三角形外接圓半徑增長的方式重新構(gòu)建三角網(wǎng)格。

在Delaunay三角剖分一般有以下幾個特點(diǎn)：

（1）建立的三角網(wǎng)格具有唯一性，散亂點(diǎn)集中任意四點(diǎn)不可能共圓；

（2）任意一個三角形的外接圓不包含其他任何頂點(diǎn)，且盡量保證形成的三角形周長最?。?/p>

（3）任何一個三角形的內(nèi)角盡量保持均衡，接近等邊三角形。

根據(jù)特點(diǎn)2，本文利用外接圓半徑增長的方式搜索第3點(diǎn)。該算法的具體思路如下：在散亂點(diǎn)集中，任取一點(diǎn)S，在其余點(diǎn)中搜索距離S最近的一點(diǎn)R，連接SR，確定SR的中垂線EF，交SR于點(diǎn)P。由數(shù)學(xué)原理可知，SR的外接圓圓心必位于SR的中垂線上，隨著圓心位置的變化，半徑的增加，必然存在第3點(diǎn)A滿足共圓條件且圓內(nèi)部無其他頂點(diǎn)，即點(diǎn)A滿足Delaunay三角形條件。

2 Loop細(xì)分

細(xì)分的方法適應(yīng)于任意拓?fù)浣Y(jié)構(gòu)的曲面，并且不影響原始曲面形態(tài)。在對散亂點(diǎn)云三角剖分形成三角網(wǎng)格后，對部分大于三角形平均周長的三角形（下文稱之為大三角形）進(jìn)行Loop細(xì)分，細(xì)分后大三角形的每條邊產(chǎn)生一個內(nèi)部點(diǎn)，原本的大三角形的頂點(diǎn)也會生成新頂點(diǎn)而有微小的位移[7]。Loop細(xì)分的主要思想如下：

圖1 新頂點(diǎn)生成規(guī)則

Loop細(xì)分完畢后，每個新生成的點(diǎn)與周圍的點(diǎn)互相連接，形成新邊，完成大三角形細(xì)分。大三角形Loop細(xì)分算法具體步驟如下：

STEP1：計算三角網(wǎng)格中三角形的平均周長，遍歷三角網(wǎng)格，根據(jù)三角形周長與平均周長的相比結(jié)果，一般孔洞區(qū)域越大則選取的比例略大，本文選擇的是對相比結(jié)果超過1.2倍的三角形進(jìn)行細(xì)分；

STEP2：對需要細(xì)分的三角形，計算三角形每條邊的新生成點(diǎn)，計算三角形三個頂點(diǎn)的新生成點(diǎn)；

STEP3：互相連接新生成點(diǎn)，組成新的三角網(wǎng)格，算法結(jié)束。

3 試驗(yàn)結(jié)果

以西安理工大學(xué)徑流沖刷實(shí)驗(yàn)所獲取的細(xì)溝點(diǎn)云數(shù)據(jù)為孔洞修補(bǔ)算例。如圖2所示，地形中原有數(shù)據(jù)7000個點(diǎn)，孔洞修補(bǔ)后共12684個點(diǎn)，新增5684個點(diǎn)。為了便于觀察孔洞修補(bǔ)效果，在Arcgis10.2軟件中將地形數(shù)據(jù)中的孔洞標(biāo)記出來。（a）為細(xì)溝的原始點(diǎn)云數(shù)據(jù)圖，（b）為孔洞修補(bǔ)后導(dǎo)出的點(diǎn)云數(shù)據(jù)圖。

圖2 細(xì)溝孔洞修補(bǔ)

[1]賀巖,雷琳君,臧華國等．地基全視景三維成像激光掃描儀[J]．紅外,2012(02):13-16．

[2]代世威．地面三維激光點(diǎn)云數(shù)據(jù)質(zhì)量分析與評價[D]．西安:長安大學(xué),2013．

[3]OHTAKE Y,BELYAEV A,SEIDEL H-P．A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions[C]．Shape Modeling International,2003．IEEE,2003:153-161．

[4]王茹．古建筑數(shù)字化及三維建模關(guān)鍵技術(shù)研究[D]．西安:西北大學(xué),2010．

[5]張棟．基于LIDAR數(shù)據(jù)和航空影像的城市房屋三維重建[D]．武漢:武漢大學(xué),2005．

[6]蔣紅斐,涂鵬,李國忠．基于生長算法構(gòu)建Delaunay三角網(wǎng)的研究[J]．公路交通科技,2004(12):38-41．

[7]LOOP C．Smooth subdivision surfaces based on triangles[D]．Utah:University of Utah,1987．