面向地形構建的點云孔洞修補

武警工程大學研究生管理大隊 柳方明 張洪彪 李俊利

面向地形構建的點云孔洞修補

武警工程大學研究生管理大隊 柳方明 張洪彪 李俊利

由于三維激光掃描儀在獲取點云數據時，受設備自身、環境、目標物表面結構等復雜因素影響，其獲取的點云數據往往存在局部孔洞，這對精確重建地形帶來了巨大的挑戰。本文針對真實地形點云數據存在的孔洞，結合Delaunay三角剖分與Loop細分算法，解決了地形孔洞難以修補這一難題。該算法首先連接距離最近的兩點，根據Delaunay三角形外接圓特性，以外接圓半徑增長的方式搜索三角形第3點，構建種子三角形。隨后對新生成邊重復采用外接圓半徑增長的方式構建新三角形，從而對所有散亂點云建立三角網拓撲結構，再以Loop細分的方式實現點云孔洞的修補，經算例驗證，本文算法可用于實際地形孔洞修補。

三角剖分；Loop細分；孔洞修補

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

1 三角剖分算法

散亂點云的分布反映地形表面整體形態，對其三角剖分是構建數據點拓撲關系，實現地形重建，揭示地形表面形態特征的一個關鍵環節。三角剖分后，每個三角形單元都代表地形很小的一個部分，相互鄰接的三角形網則整體反映地形表面模型。本文對Delaunay三角剖分算法研究，通過改進一種原有的三角形生長算法[6]，利用三角形外接圓半徑增長的方式重新構建三角網格。

在Delaunay三角剖分一般有以下幾個特點：

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

（2）任意一個三角形的外接圓不包含其他任何頂點，且盡量保證形成的三角形周長最小；

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

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

2 Loop細分

細分的方法適應于任意拓撲結構的曲面，并且不影響原始曲面形態。在對散亂點云三角剖分形成三角網格后，對部分大于三角形平均周長的三角形（下文稱之為大三角形）進行Loop細分，細分后大三角形的每條邊產生一個內部點，原本的大三角形的頂點也會生成新頂點而有微小的位移[7]。Loop細分的主要思想如下：

圖1 新頂點生成規則

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

STEP1：計算三角網格中三角形的平均周長，遍歷三角網格，根據三角形周長與平均周長的相比結果，一般孔洞區域越大則選取的比例略大，本文選擇的是對相比結果超過1.2倍的三角形進行細分；

STEP2：對需要細分的三角形，計算三角形每條邊的新生成點，計算三角形三個頂點的新生成點；

STEP3：互相連接新生成點，組成新的三角網格，算法結束。

3 試驗結果

以西安理工大學徑流沖刷實驗所獲取的細溝點云數據為孔洞修補算例。如圖2所示，地形中原有數據7000個點，孔洞修補后共12684個點，新增5684個點。為了便于觀察孔洞修補效果，在Arcgis10.2軟件中將地形數據中的孔洞標記出來。（a）為細溝的原始點云數據圖，（b）為孔洞修補后導出的點云數據圖。

圖2 細溝孔洞修補

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

[2]代世威．地面三維激光點云數據質量分析與評價[D]．西安:長安大學,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]王茹．古建筑數字化及三維建模關鍵技術研究[D]．西安:西北大學,2010．

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

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

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