盛仲飆 韓慧妍

摘要：點(diǎn)云分割是根據(jù)空間、幾何和紋理等特征對(duì)點(diǎn)云進(jìn)行劃分，使得同一劃分內(nèi)的點(diǎn)云具有相似的特征。首先對(duì)獲取的散亂點(diǎn)云數(shù)據(jù)進(jìn)行去噪、填補(bǔ)空洞和畸變等預(yù)處理，然后計(jì)算最小包圍立方體分割點(diǎn)云空間并構(gòu)建八叉樹加速鄰域點(diǎn)的搜索，為每個(gè)點(diǎn)構(gòu)造最小二乘鄰域，分析散亂點(diǎn)云數(shù)據(jù)的高斯曲率和平均曲率，再通過區(qū)域生長法得到低噪聲的精確分塊，自適應(yīng)、智能化地對(duì)點(diǎn)云進(jìn)行分塊。經(jīng)實(shí)驗(yàn)驗(yàn)證，該方法可以獲得較好的分割效果。

關(guān)鍵詞：散亂點(diǎn)云；自動(dòng)分割；曲面重構(gòu)

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A

1引言

隨著計(jì)算機(jī)輔助技術(shù)以及三維掃描技術(shù)的發(fā)展，掃描得到真實(shí)物體表面的空間采樣點(diǎn)，即點(diǎn)云數(shù)據(jù)，基于采樣點(diǎn)的三維數(shù)據(jù)模型即點(diǎn)云模型，已經(jīng)逐步應(yīng)用到許多領(lǐng)域中。點(diǎn)云模型是一種利用離散點(diǎn)來描述物體表面信息的CAD模型表示方法[1]。點(diǎn)云模型具有三維表現(xiàn)能強(qiáng)，存儲(chǔ)空間消耗少，模型處理工作量小的特點(diǎn)，因此點(diǎn)云模型更適合表示大規(guī)模數(shù)據(jù)，成為CAD/CG領(lǐng)域較常用的三維物體表示模型之一[2]。

點(diǎn)云數(shù)據(jù)的處理即對(duì)掃描的模型進(jìn)行修改、重用，已經(jīng)成為了一個(gè)重要的問題。點(diǎn)云模型的分割作為三維特征提取和識(shí)別一個(gè)十分重要的步驟，已經(jīng)成為計(jì)算機(jī)圖形學(xué)研究的一個(gè)熱點(diǎn)問題。

2點(diǎn)云分割與點(diǎn)云曲面重構(gòu)

2.1點(diǎn)云分割

點(diǎn)云數(shù)據(jù)的區(qū)域分割是CAD模型重建的基礎(chǔ)。點(diǎn)云數(shù)據(jù)的區(qū)域分割就是將數(shù)據(jù)分割成若干個(gè)互不相交的子集，每個(gè)子集中的數(shù)據(jù)同屬于一個(gè)具有單一特征的曲面。對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行分割，分割的目的是對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行有效的劃分，劃分的結(jié)果是使得每一個(gè)點(diǎn)云子集合中的掃描點(diǎn)均具有相同或相近的屬性[2]，具體說來就是給同一個(gè)表面上的點(diǎn)賦予同一個(gè)標(biāo)記，不同表面的點(diǎn)賦予不同標(biāo)記[3]。區(qū)域生長法的基本思想是考慮激光點(diǎn)極其空間鄰域點(diǎn)之間的關(guān)系，將具有相似性質(zhì)的點(diǎn)集合構(gòu)成區(qū)域。具體實(shí)現(xiàn)為：對(duì)每個(gè)分割的區(qū)域找個(gè)種子點(diǎn)作為生長的起點(diǎn)，再將種子點(diǎn)周圍鄰域中與種子點(diǎn)具有相同或相似性質(zhì)的點(diǎn)合并到種子點(diǎn)所在的區(qū)域中；將這些新的點(diǎn)作為新的種子點(diǎn)繼續(xù)進(jìn)行上面的過程，直到再?zèng)]有滿足條件的點(diǎn)可被包括進(jìn)來。這樣一個(gè)具有某種均勻性的區(qū)域就生長成功了，相鄰區(qū)域有不同的均勻性[4]。

2.2點(diǎn)云曲面重構(gòu)

使用貪婪三角化算法來進(jìn)行散亂點(diǎn)云的曲面重構(gòu)。貪婪三角化算法原理是處理一系列可以使網(wǎng)格“生長擴(kuò)大”的點(diǎn)（邊緣點(diǎn)），延伸這些點(diǎn)直到所有符合幾何正確性和拓?fù)湔_性的點(diǎn)都被連上。該算法的三角化過程是局部進(jìn)行的，首先沿著一個(gè)點(diǎn)的法線將該點(diǎn)投影到局部二維坐標(biāo)平面內(nèi)并連接其他懸空點(diǎn)，然后再進(jìn)行下一點(diǎn)。

將三維點(diǎn)通過法線投影到某一平面，然后對(duì)投影得到的點(diǎn)云作平面內(nèi)的三角化，從而得到各點(diǎn)的連接關(guān)系。在平面區(qū)域三角化的過程中用到了基于Delaunay的空間區(qū)域增長算法，該方法通過選取一個(gè)樣本三角片作為初始曲面，不斷擴(kuò)張曲面邊界，最后形成一張完整的三角網(wǎng)格曲面。最后根據(jù)投影點(diǎn)云的連接關(guān)系確定各原始三維點(diǎn)間的拓?fù)溥B接，所得三角網(wǎng)即為重建得到的曲面模型。

計(jì)算技術(shù)與自動(dòng)化2016年3月

第35卷第1期盛仲飆等：散亂點(diǎn)云分割技術(shù)研究與實(shí)現(xiàn)

3點(diǎn)云分割與重建過程

3.1區(qū)域生長分割法

種子區(qū)域的生長首先從最大的標(biāo)記區(qū)域開始，目的是避免區(qū)域重疊，形成較少的分割、較大的區(qū)域。為最大化拓?fù)渑R近點(diǎn)且讓這些點(diǎn)被唯一曲面緊密地逼近，在每次循環(huán)得最后，比較當(dāng)前區(qū)域點(diǎn)的數(shù)目R新和先前的數(shù)目R舊。如果R新>R舊，就能發(fā)現(xiàn)一個(gè)比先前更多點(diǎn)的曲面，因此存儲(chǔ)當(dāng)前區(qū)域點(diǎn)和當(dāng)前控制點(diǎn)，然后擬合一個(gè)新的曲面以提高對(duì)該區(qū)域的近似度。擬合新的曲面后，清空區(qū)域中所有的點(diǎn)并重新開始從種子區(qū)域生長。如果新區(qū)域沒有老區(qū)域更大，R新R舊，那么區(qū)域生長終止，存儲(chǔ)該區(qū)域點(diǎn)和控制點(diǎn)（屬于R舊）。

3.2kdtree的K鄰域獲取

在進(jìn)行散亂點(diǎn)云分割之前，采用合適的數(shù)據(jù)結(jié)構(gòu)來提高鄰域搜索效率十分關(guān)鍵。獲取鄰域結(jié)構(gòu)可采用Kdtree來實(shí)現(xiàn)。Kdtree或者K維樹是計(jì)算機(jī)科學(xué)中使用的一種數(shù)據(jù)結(jié)構(gòu)，用來組織表示K維空間中點(diǎn)集合。它是一種帶有其他約束條件的二分查找樹。kdtree對(duì)于區(qū)間和近鄰搜索十分有用。我們?yōu)榱诉_(dá)到目的，通常只在三個(gè)維度中進(jìn)行處理，因此所有的kdtree都將是三維kdtree。kdtree的每一級(jí)在指定維度上分開所有的子節(jié)點(diǎn)。在樹的根部所有子節(jié)點(diǎn)是以第一個(gè)指定的維度上被分開（也就是說，如果第一維坐標(biāo)小于根節(jié)點(diǎn)的點(diǎn)它將分在左邊的子樹中，如果大于根節(jié)點(diǎn)的點(diǎn)它將分在右邊的子樹中）。樹的每一級(jí)都在下一個(gè)維度上分開，所有其他的維度用完之后就回到第一個(gè)維度。建立kdtree最高效的方法是，像快速分類一樣使用分割法，把指定維度的值放在根上，在該維度上包含較小數(shù)值的在左子樹，較大的在右子樹。然后分別在左邊和右邊的子樹上重復(fù)這個(gè)過程。直到準(zhǔn)備分類的最后一個(gè)樹僅僅由一個(gè)元素組成。

3.3曲率的計(jì)算

曲面中某一點(diǎn)P的平均曲率Kh由公式3-1決定

2Khn=limdiam（A）→0

SymbolQC@ AA式（3-1）

式中：n為法向量；A為P周圍一個(gè)無限小區(qū)域，diam（A）為這個(gè)區(qū)域的直徑，

SymbolQC@ 表示關(guān)于點(diǎn)P的的梯度算子。把式3-1離散化，得到點(diǎn)Pi的平均曲率計(jì)算公式如式3-2所示：

Kh（Pi）=14Amix∑j∈N（i）（cotαij+

cotβij）（Pi-Pj）×n式（3-2）

式中：αij、βij分別為連接頂點(diǎn)Pi和Pj邊的對(duì)角。

高斯曲率的離散表達(dá)式如式3-3所示

Kg（Pi）=1Amix（2π-∑j∈N（i）θj）式（3-3）endprint

θj為Pi的鄰域內(nèi)與頂點(diǎn)Pj連接的邊的夾角。

3.4八叉樹

八叉樹結(jié)構(gòu)通過對(duì)三維空間的幾何實(shí)體進(jìn)行體元剖分，每個(gè)體元具有相同的時(shí)間和空間復(fù)雜度，通過循環(huán)遞歸的劃分方法對(duì)大小為2n*2n*2n的三維空間的幾何對(duì)象進(jìn)行剖分，從而構(gòu)成一個(gè)具有根節(jié)點(diǎn)的方向圖。在八叉樹結(jié)構(gòu)中如果被劃分的體元具有相同的屬性，則該體元構(gòu)成一個(gè)葉節(jié)點(diǎn)；否則繼續(xù)把該體元剖分成8個(gè)子立方體，依次遞歸剖分，對(duì)于2n*2n*2n大小的空間對(duì)象，最多剖分n次。

3.5實(shí)驗(yàn)測試

1）打開和關(guān)閉文件

使用QT文件對(duì)話框選擇點(diǎn)云數(shù)據(jù)格式的文件，然后從PCD文件中讀取點(diǎn)云數(shù)據(jù)。從磁盤上加載PointCloud數(shù)據(jù)（假設(shè)要讀取的文件已經(jīng)被創(chuàng)建）到二進(jìn)制存儲(chǔ)塊中?；蛘咦x取PointCloud2存儲(chǔ)塊。由于點(diǎn)云的動(dòng)態(tài)性質(zhì)，以二進(jìn)制塊來讀取，然后轉(zhuǎn)換成要使用的表示方式更好。把二進(jìn)制塊讀取并轉(zhuǎn)換到模板化的PointCloud格式里，使用PCL點(diǎn)云庫中的一種點(diǎn)類型作為存儲(chǔ)點(diǎn)的類型。

2）可視化點(diǎn)云

可視化（Visualization）是利用計(jì)算機(jī)圖形學(xué)和圖像處理技術(shù)，將數(shù)據(jù)轉(zhuǎn)換成圖形或圖像在屏幕上顯示出來，并進(jìn)行交互處理的理論、方法和技術(shù)。本設(shè)計(jì)利用PCL中pcl_visualization庫提供了可視化相關(guān)的數(shù)據(jù)結(jié)構(gòu)和組件來可視化其他模塊的算法處理后的結(jié)果。

3）分割測試

本次測試主要選取房檐模型進(jìn)行測試。測試分為分割測試和曲面重構(gòu)測試。房檐模型的數(shù)據(jù)規(guī)模為80000個(gè)點(diǎn)，其模型如圖3.1所示。

分割時(shí)，標(biāo)注分割結(jié)果的顏色是隨機(jī)產(chǎn)生的。由于分割時(shí)設(shè)定的參數(shù)較多，所以在此只對(duì)曲率閾值做測試，在其余條件不變的情況下，測試曲率閾值分別為0.5，1.0，1.5時(shí)的情況。

（4）曲面重構(gòu)測試

由于房檐模型本身形狀規(guī)則，點(diǎn)比較集中，重構(gòu)后的效果比較好，有層次感。

4結(jié)束語

本文基于QT，實(shí)現(xiàn)了PCL庫中點(diǎn)云文件的打開與關(guān)閉；區(qū)域生長分割，并且在點(diǎn)云分塊的基礎(chǔ)上實(shí)現(xiàn)了曲面重構(gòu)。點(diǎn)云分割主要采用區(qū)域生長法，點(diǎn)云重構(gòu)使用貪婪三角法。對(duì)于平面圖像分割及重構(gòu)效果良好。

參考文獻(xiàn)

[1]孫金虎.點(diǎn)云模型分割與融合關(guān)鍵技術(shù)研究[D].南京：南京航空航天大學(xué)，2013（3）：16-25.

[2]匡小蘭.基于建筑物的著色點(diǎn)云平面區(qū)域分割研究[D].株洲：湖南工業(yè)大學(xué)，2011.

[3]歐新良，匡小蘭，倪問尹.三維散亂點(diǎn)云分割技術(shù)綜述[J].湖南工業(yè)大學(xué)學(xué)報(bào)，2010，24（5）：45-49.

[4]徐文學(xué).地面三維激光掃描數(shù)據(jù)分割方法研究[D].濟(jì)南：山東科技大學(xué)，2009.

[5]馬符訊，林歡，徐楠.散亂點(diǎn)云數(shù)據(jù)的可視化探究[J].科技創(chuàng)新導(dǎo)報(bào)，2013，（10）：89-95.

[6]布蘭切特，薩摩菲爾德.C++GUIQT4編程[M].北京：電子工業(yè)出版社，2013.

[7]石玉.基于VTK的可視化技術(shù)研究與實(shí)現(xiàn)[D].西安：西安建筑科技大學(xué)，2009.

[8]胡懷宇，崔漢國，代星.基于區(qū)域生長法的散亂點(diǎn)云分區(qū)方法[J].計(jì)算機(jī)應(yīng)用，2009，（10）：32-37.

[9]朱德海，郭浩，蘇偉.點(diǎn)云庫PCL學(xué)習(xí)教程[M].北京：北京航空航天大學(xué)出版社，2012（10）：376-381.

[10]袁占斌，聶玉峰，歐陽潔.平面自動(dòng)布點(diǎn)及Delaunay三角形網(wǎng)格生成[J].計(jì)算機(jī)工程與應(yīng)用.2009，（17）：60-64.

[11]董明曉.曲面重構(gòu)中點(diǎn)云數(shù)據(jù)的區(qū)域分割研究[J].中國圖像圖形學(xué)報(bào)，2005，10（5）：575-578.

[12]柯映林.基于邊特征的點(diǎn)云數(shù)據(jù)區(qū)域分割[J].浙江大學(xué)學(xué)報(bào)，2005，39（3）：377-395.

[13]馬符訊，那地曼·艾尼瓦爾，林歡.散亂點(diǎn)云數(shù)據(jù)的分割方法探究[J].測繪與空間地理信息，2014，37（10）：148-151.

[14]匡小蘭，歐新良，倪問尹.散亂點(diǎn)云數(shù)據(jù)區(qū)域分割綜述[J].長沙大學(xué)學(xué)報(bào)，2010（9）：68-70.

[15]YAMAZAKII，NATARAJANV，BaiZ，etal.SegmentingPointSets[J].Proc，IEEEIntl.Conf.ShapeModelingandApplications（SMI），2006（6）：4-13.

[16]BESLP，JAINR.SegmentationandClassificationofRangeImages[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，1987，（05）：608-620.

[17]龔友平，金濤，童水光.點(diǎn)云數(shù)據(jù)區(qū)域分割方法[J].工程圖學(xué)學(xué)報(bào)，2006，（4）：28-33.

第35卷第1期2016年3月計(jì)算技術(shù)與自動(dòng)化ComputingTechnologyandAutomationVol35，No1Mar.2016第35卷第1期2016年3月計(jì)算技術(shù)與自動(dòng)化ComputingTechnologyandAutomationVol35，No1Mar.2016endprint