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

(1. 武漢理工大學(xué)資源與環(huán)境工程學(xué)院，湖北 武漢 430079； 2. 中國地質(zhì)大學(xué)，湖北 武漢 430079)

無序三維點(diǎn)云重建技術(shù)研究

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

(1. 武漢理工大學(xué)資源與環(huán)境工程學(xué)院，湖北 武漢 430079； 2. 中國地質(zhì)大學(xué)，湖北 武漢 430079)

如何對海量三維點(diǎn)云數(shù)據(jù)進(jìn)行快速三維重建是三維場景重現(xiàn)中關(guān)鍵的問題。本文從項(xiàng)目出發(fā)，對采集的無序點(diǎn)云提出根據(jù)內(nèi)容進(jìn)行重建，對非關(guān)鍵區(qū)域進(jìn)行數(shù)據(jù)壓縮，將壓縮后的數(shù)據(jù)與關(guān)鍵區(qū)域的數(shù)據(jù)放在一起進(jìn)行三維重建。試驗(yàn)結(jié)果表明，該方法能完整地呈現(xiàn)三維場景中的地物，同時也能減少三維場景重建的時間，可以為類似的三維重建提供一定的參考依據(jù)。

三維場景重建;無序點(diǎn)云;數(shù)據(jù)壓縮;數(shù)據(jù)分類

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

點(diǎn)云按照排列方式的不同可以分為有序點(diǎn)云和無序點(diǎn)云[1]。有序點(diǎn)云的點(diǎn)與點(diǎn)的拓?fù)浣Y(jié)構(gòu)完整，相鄰點(diǎn)之間存在連續(xù)關(guān)系，領(lǐng)域操作高效。無序點(diǎn)云由于點(diǎn)與點(diǎn)之間缺乏拓?fù)潢P(guān)系，因此常采用八叉樹、空間單元格、kd-tree數(shù)對其進(jìn)行管理。本文主要研究無序點(diǎn)云的三維重建，為點(diǎn)云快速重建提供基礎(chǔ)。

一、點(diǎn)云重建國內(nèi)外研究現(xiàn)狀

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

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

逼近法常用的算法有泊松重建、MC重建、EarChipping重建。即通過最優(yōu)化的插值方法，對點(diǎn)云數(shù)據(jù)進(jìn)行處理，進(jìn)而獲得點(diǎn)云模型的近似曲面。

二、三維點(diǎn)云快速重建算法

為了解決現(xiàn)有的Delaunay三角網(wǎng)重建算法中存在的算法效率低下的問題，本文提出并采用根據(jù)內(nèi)容進(jìn)行壓縮的快速Delaunay三角網(wǎng)重建方法。首先根據(jù)研究內(nèi)容對非關(guān)鍵區(qū)域采用包圍盒壓縮算法進(jìn)行點(diǎn)云數(shù)據(jù)壓縮，然后利用貪婪投影三角化算法將壓縮區(qū)域的點(diǎn)云和非壓縮區(qū)域的點(diǎn)云進(jìn)行三維點(diǎn)云重建。

1. 基于包圍盒的點(diǎn)云數(shù)據(jù)壓縮

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

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

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

圖1

2. 試驗(yàn)結(jié)果

(1) 數(shù)據(jù)處理

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

圖2

(2) 數(shù)據(jù)壓縮

PCL提供了兩種點(diǎn)云數(shù)據(jù)管理方式，一種是kd-tree數(shù)據(jù)結(jié)構(gòu)，一種是octree數(shù)據(jù)結(jié)構(gòu)，也稱八叉樹。其中，kd-tree樹用來對點(diǎn)云數(shù)據(jù)進(jìn)行檢索，octree樹在PCL中用于點(diǎn)云數(shù)據(jù)壓縮。因此，本文采用八叉樹對點(diǎn)云數(shù)據(jù)進(jìn)行管理和壓縮。

對采集到的點(diǎn)云數(shù)采用八叉樹進(jìn)行數(shù)據(jù)管理，構(gòu)造點(diǎn)云數(shù)據(jù)的最小空間包圍盒，并把它作為數(shù)據(jù)點(diǎn)云拓?fù)潢P(guān)系的根模型；再將外界立方體分割成大小系統(tǒng)的8個子?xùn)鸥?，每個子?xùn)鸥窬暈楦?jié)點(diǎn)的子節(jié)點(diǎn)；如此遞歸分割，直到最小子?xùn)鸥竦倪呴L等于給定的點(diǎn)距，將點(diǎn)云空間劃分成為2的冪次方個子?xùn)鸥瘛?/p>

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

圖4

三、場景重建

為了減少海量點(diǎn)云數(shù)據(jù)的三角網(wǎng)生成時間，本文將非變形區(qū)域的數(shù)據(jù)和變形區(qū)域的數(shù)據(jù)融合在一起進(jìn)行三角網(wǎng)重建，貪婪三角網(wǎng)算法原理處理一系列可以使網(wǎng)格“生長擴(kuò)大”的點(diǎn)，延伸這些點(diǎn)直到所有符合幾何正確性和拓?fù)湫缘狞c(diǎn)都參與構(gòu)網(wǎng)。其具體做法是將點(diǎn)云投影到某一局部二維坐標(biāo)平面內(nèi)，再在坐標(biāo)平面內(nèi)進(jìn)行平面內(nèi)的三角化，根據(jù)平面內(nèi)的拓?fù)溥B接關(guān)系獲得一個三角網(wǎng)格模型?；谏鲜鏊枷?，本文將壓縮后的非變形區(qū)域點(diǎn)云和變形區(qū)域點(diǎn)云放在一起進(jìn)行三角網(wǎng)重建，其中變形區(qū)域觀測點(diǎn)為12 470 691個。

在圖5中的程序參數(shù)設(shè)置如下：

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

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

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

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

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

樣本可搜索的領(lǐng)域個數(shù)為100個，gp3.setMaximumNearestneighbors(100)。

效果如圖5所示。

在圖6中的程序參數(shù)設(shè)置如下：

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

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

圖5

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

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

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

樣本可搜索的領(lǐng)域個數(shù)為100個，gp3.setMaximumNearestneighbors(100)。

效果如圖6所示。

圖6

四、結(jié)束語

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

[1] 樊宇，王宇楠.三維激光掃描點(diǎn)云數(shù)據(jù)預(yù)處理技術(shù)研究[J].科技創(chuàng)新導(dǎo)報(bào)，2011(32):27-28.

[2] 呂瓊瓊.激光雷達(dá)點(diǎn)云數(shù)據(jù)的三維建模技術(shù)[D].北京：北京交通大學(xué), 2009.

[3] 梁群仙，許宏麗.一種基于點(diǎn)云數(shù)據(jù)的快速曲面重構(gòu)方法[J].計(jì)算機(jī)工程學(xué)報(bào)(圖形圖像處理)，2013,39(2):238-240.

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

[5] 喜文飛.激光點(diǎn)云數(shù)據(jù)壓縮的精簡研究[D].昆明:昆明理工大學(xué),2012.

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

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

[8] 孟娜.基于激光掃描點(diǎn)云的數(shù)據(jù)處理技術(shù)研究[D].濟(jì)南：山東大學(xué),2011.

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

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

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

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

ResearchonDisorder3DPointCloudsReconstructionTechnology

GONG Zhen，HU Youjian，DONG Heng,LI Hua

龔珍，胡友健，董恒,等.無序三維點(diǎn)云重建技術(shù)研究[J].測繪通報(bào)，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

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

龔 珍(1981—)，女，博士生，研究方向?yàn)槿S點(diǎn)云變形監(jiān)測研究。E-mail：doudouzhen@126.com

董 恒