無序三維點云重建技術研究

龔 珍，胡友健，董 恒，黎 華

(1. 武漢理工大學資源與環境工程學院，湖北 武漢 430079； 2. 中國地質大學，湖北 武漢 430079)

無序三維點云重建技術研究

龔 珍1,2，胡友健2，董 恒1，黎 華1

(1. 武漢理工大學資源與環境工程學院，湖北 武漢 430079； 2. 中國地質大學，湖北 武漢 430079)

如何對海量三維點云數據進行快速三維重建是三維場景重現中關鍵的問題。本文從項目出發，對采集的無序點云提出根據內容進行重建，對非關鍵區域進行數據壓縮，將壓縮后的數據與關鍵區域的數據放在一起進行三維重建。試驗結果表明，該方法能完整地呈現三維場景中的地物，同時也能減少三維場景重建的時間，可以為類似的三維重建提供一定的參考依據。

三維場景重建;無序點云;數據壓縮;數據分類

三維激光測量技術是一種快速、準確獲取真實地物空間信息的技術。采用三維激光掃描儀對被測量地物進行掃描，操作簡單且精度高。由于獲取的三維點云數據量龐大、散亂，如何組織這些點云數據，使得其通過計算機虛擬地呈現出來，成為空間信息處理、計算機圖形學、計算機視覺等領域研究的熱點。

點云按照排列方式的不同可以分為有序點云和無序點云[1]。有序點云的點與點的拓撲結構完整，相鄰點之間存在連續關系，領域操作高效。無序點云由于點與點之間缺乏拓撲關系，因此常采用八叉樹、空間單元格、kd-tree數對其進行管理。本文主要研究無序點云的三維重建，為點云快速重建提供基礎。

一、點云重建國內外研究現狀

根據重建曲面和數據點云之間的關系可將曲面重建分為兩大類：插值法和逼近法。前者得到的曲面重建完全通過原始數據點，而后者則是通過分片線性曲面或其他形式的曲面類逼近原始數據點，從而得到的是重建曲面是原始點集的一個逼近。

插值法常用的算法有Delaunay三角網重構法[2-3]，該方法將三維點云數據的空間坐標投影到二維平面上，然后針對二維投影平面進行缺失補充，將投影的二維平面三角網格化，再利用反向映射的思想得到三維網格重建模型，最后完成點云數據的重建。由于該算法需要構造三角網格，因此具有很好的網絡拓撲結構，然而在兩次投影轉化計算過程中存在維數的壓縮，這樣很可能導致點云數據空間深度信息的改變或丟失，這種兩次轉化投影的方式很難處理封閉或點云模型表面被遮擋的情況。后來在點云重建方面也出現了基于Delaunay空間區域增長方法的改進算法，即選取一個三角面片作為種子面片，在保證拓撲結構正確和幾何結構正確的前提下，對種子面片進行擴張，最后形成完整三角網格曲面，改進算法有最小內角最大等優秀特性，但對于點云，當數據中的三維點進行三角網格剖分的時間復雜度較大，如果點云數據達到千百萬數量級，Delaunay三角網格剖分算法的點云數據重建時間過長，因此此方法并不適合大規模點云數據的重建操作[4]。

逼近法常用的算法有泊松重建、MC重建、EarChipping重建。即通過最優化的插值方法，對點云數據進行處理，進而獲得點云模型的近似曲面。

二、三維點云快速重建算法

為了解決現有的Delaunay三角網重建算法中存在的算法效率低下的問題，本文提出并采用根據內容進行壓縮的快速Delaunay三角網重建方法。首先根據研究內容對非關鍵區域采用包圍盒壓縮算法進行點云數據壓縮，然后利用貪婪投影三角化算法將壓縮區域的點云和非壓縮區域的點云進行三維點云重建。

1. 基于包圍盒的點云數據壓縮

根據點云中點的分布特點，可將點云分為有序點云和散亂點云。對于有序點云的數據壓縮，常用的采樣方法有均勻采樣法、倍率縮減法、柵格法、等量縮減法、最小包圍盒區域法、等分密度法等。散亂點云數據壓縮中，常用的方法有隨機采樣法、最短距離法、包圍盒法、均勻格網法、三角網格法、曲率采樣法等[5-10]。

目前，針對點云的壓縮大致可以分為3類：基于概率的數據精簡(隨機采樣法)、基于格網的數據精簡法(包圍盒法、均勻格網法等)和基于曲率的數據精簡法(最短距離法、曲率采樣法)[5]。

包圍盒重心法是點云處理中較為常見的方法，其核心思想是用包圍盒中點云的重心來代替點云中的點實現數據精簡。其實現方法為：首先采用一個最小外包長方體來約束點云，然后將長方體根據一定的數量或大小分割成若干個小立方體包圍盒，最后選取小包圍盒中離點集的重心點最近的點作為特征點，即每個包圍盒中最多只保留一個數據點。算法流程如圖1所示。

圖1

2. 試驗結果

(1) 數據處理

由于現有的數據格式(*.ply,*.stl,*.obj,*.x3d)格式不支持PCL庫，PCD格式能支持PCL數據庫引進的n維點類型機制處理中的某些擴展，因此，需要將采集到的數據按照PCD格式進行轉化，PCD格式如圖2所示。其中，version表示PCD文件版本，fields表示一個點可以有的每一個維度和字段的名字，size表示每一個維度的大小，type表示每一個維度的類型，count表示每一個維度包含的元素數目，width表示點云數據集的寬度，height表示點云數據集的高度，viewpoint表示數據集中點云獲取的視點，data表示存儲的點云的數據類型。

圖2

(2) 數據壓縮

PCL提供了兩種點云數據管理方式，一種是kd-tree數據結構，一種是octree數據結構，也稱八叉樹。其中，kd-tree樹用來對點云數據進行檢索，octree樹在PCL中用于點云數據壓縮。因此，本文采用八叉樹對點云數據進行管理和壓縮。

對采集到的點云數采用八叉樹進行數據管理，構造點云數據的最小空間包圍盒，并把它作為數據點云拓撲關系的根模型；再將外界立方體分割成大小系統的8個子柵格，每個子柵格均視為根節點的子節點；如此遞歸分割，直到最小子柵格的邊長等于給定的點距，將點云空間劃分成為2的冪次方個子柵格。

由于PCL庫中提供了十幾個基于八叉樹(octree)的點云高效管理、檢索、空間處理算法庫，因此，本文用采集到的數據點將數據分為變形區和非變形區，將非變形區的數據采用八叉樹進行組織，在此基礎上采用基于最小包圍盒的方式對數據進行壓縮，壓縮前后的效果如圖3、圖4所示。圖3中數據的壓縮比為0.25%，數據點為2928；圖4中數據的壓縮比為4.5%，數據點為52 374。

圖4

三、場景重建

為了減少海量點云數據的三角網生成時間，本文將非變形區域的數據和變形區域的數據融合在一起進行三角網重建，貪婪三角網算法原理處理一系列可以使網格“生長擴大”的點，延伸這些點直到所有符合幾何正確性和拓撲性的點都參與構網。其具體做法是將點云投影到某一局部二維坐標平面內，再在坐標平面內進行平面內的三角化，根據平面內的拓撲連接關系獲得一個三角網格模型。基于上述思想，本文將壓縮后的非變形區域點云和變形區域點云放在一起進行三角網重建，其中變形區域觀測點為12 470 691個。

在圖5中的程序參數設置如下：

連接點之間的最大距離設置為300，gp3.setSearchRadius(300);

樣本點搜索其鄰近點的最遠距離為40，gp3.serMu(40);

三角化后得到的三角形最小角度為10°，gp3.setMinimumAngle(10);

三角化后得到的三角形最大角度為120°，gp3.setMaxmumAngle(120);

當某一待選點的法線方向偏離某一樣本點超過45°時，該點不連接到樣本點上，gp3.setMaximumSurfaceAngle(45);

樣本可搜索的領域個數為100個，gp3.setMaximumNearestneighbors(100)。

效果如圖5所示。

在圖6中的程序參數設置如下：

連接點之間的最大距離設置為300，gp3.setSearchRadius(300);

樣本點搜索其鄰近點的最遠距離為60，gp3.serMu(60);

圖5

三角化后得到的三角形最小角度為10°，gp3.setMinimumAngle(10);

三角化后得到的三角形最大角度為120°，gp3.setMaxmumAngle(120);

當某一待選點的法線方向偏離某一樣本點超過45°時，該點不連接到樣本點上，gp3.setMaximumSurfaceAngle(45);

樣本可搜索的領域個數為100個，gp3.setMaximumNearestneighbors(100)。

效果如圖6所示。

圖6

四、結束語

由于三維激光點云能夠便捷、高效地獲取數據，因此具有廣闊的應用前景[11-12]。由于在掃描過程中，有些區域反射率太低，使得該區域的數據無法獲取，導致在三角網重建過程中出現了空洞。本文主要是根據項目需要對三維點云數據的壓縮方式進行了研究，利用PCD格式支持數據擴展的優勢，提出根據內容來對點云進行壓縮，采用貪婪三角網算法對壓縮之后的無向點云進行重建。試驗結果證明該方法可行，這為三維點云的重建提供了新的思路。

[1] 樊宇，王宇楠.三維激光掃描點云數據預處理技術研究[J].科技創新導報，2011(32):27-28.

[2] 呂瓊瓊.激光雷達點云數據的三維建模技術[D].北京：北京交通大學, 2009.

[3] 梁群仙，許宏麗.一種基于點云數據的快速曲面重構方法[J].計算機工程學報(圖形圖像處理)，2013,39(2):238-240.

[4] 梁錫坤.B 樣條類曲線曲面理論及其應用研究[D].合肥：合肥工業大學,2003.

[5] 喜文飛.激光點云數據壓縮的精簡研究[D].昆明:昆明理工大學,2012.

[6] 趙儉輝，龍成江，丁乙華，等.一種基于立方體小柵格的K鄰域快速搜索算法[J].武漢大學學報(信息科學版),2009(5):615-618.

[7] 劉越華，廖文和，劉浩.逆向工程中散亂點云的K鄰域搜索算法研究[J].機械設計與制造,2012(3):256-258.

[8] 孟娜.基于激光掃描點云的數據處理技術研究[D].濟南：山東大學,2011.

[9] 黃文明，肖朝霞，溫佩芝，等.保留邊界的點云簡化方法[J].計算機應用,2010(2):348-350.

[10] 楊楠，校江超，王明海.利用點云數據的法矢及曲率估算[J].現代制造工程,2010(7):35-37.

[11] 盧小平，王宇飛，杜耀剛，等.利用點云構建隧道斷面的形變監測方法[J].測繪通報，2016(1):80-83.

[12] 李珵, 盧小平, 朱寧寧, 等.基于激光點云的隧道斷面連續提取與形變分析方法[J].測繪學報，2015,44(9):1056-1062.

ResearchonDisorder3DPointCloudsReconstructionTechnology

GONG Zhen，HU Youjian，DONG Heng,LI Hua

龔珍，胡友健，董恒,等.無序三維點云重建技術研究[J].測繪通報，2016(9)：17-19.

10.13474/j.cnki.11-2246.2016.0283.

P237

B

0494-0911(2016)09-0017-03

2015-12-10；

2016-06-20

國家自然科學基金青年基金(41301588); 湖北省自然科學基金(2014CFB858);武漢理工大學校級教研項目(w2015105)；武漢理工大學國家大學生創新訓練項目(2016215)

龔 珍(1981—)，女，博士生，研究方向為三維點云變形監測研究。E-mail：doudouzhen@126.com

董 恒