散亂點云分割技術研究與實現

盛仲飆 韓慧妍

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

關鍵詞：散亂點云；自動分割；曲面重構

中圖分類號：TP391文獻標識碼：A

1引言

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

點云數據的處理即對掃描的模型進行修改、重用，已經成為了一個重要的問題。點云模型的分割作為三維特征提取和識別一個十分重要的步驟，已經成為計算機圖形學研究的一個熱點問題。

2點云分割與點云曲面重構

2.1點云分割

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

2.2點云曲面重構

使用貪婪三角化算法來進行散亂點云的曲面重構。貪婪三角化算法原理是處理一系列可以使網格“生長擴大”的點（邊緣點），延伸這些點直到所有符合幾何正確性和拓撲正確性的點都被連上。該算法的三角化過程是局部進行的，首先沿著一個點的法線將該點投影到局部二維坐標平面內并連接其他懸空點，然后再進行下一點。

將三維點通過法線投影到某一平面，然后對投影得到的點云作平面內的三角化，從而得到各點的連接關系。在平面區域三角化的過程中用到了基于Delaunay的空間區域增長算法，該方法通過選取一個樣本三角片作為初始曲面，不斷擴張曲面邊界，最后形成一張完整的三角網格曲面。最后根據投影點云的連接關系確定各原始三維點間的拓撲連接，所得三角網即為重建得到的曲面模型。

計算技術與自動化2016年3月

第35卷第1期盛仲飆等：散亂點云分割技術研究與實現

3點云分割與重建過程

3.1區域生長分割法

種子區域的生長首先從最大的標記區域開始，目的是避免區域重疊，形成較少的分割、較大的區域。為最大化拓撲臨近點且讓這些點被唯一曲面緊密地逼近，在每次循環得最后，比較當前區域點的數目R新和先前的數目R舊。如果R新>R舊，就能發現一個比先前更多點的曲面，因此存儲當前區域點和當前控制點，然后擬合一個新的曲面以提高對該區域的近似度。擬合新的曲面后，清空區域中所有的點并重新開始從種子區域生長。如果新區域沒有老區域更大，R新R舊，那么區域生長終止，存儲該區域點和控制點（屬于R舊）。

3.2kdtree的K鄰域獲取

在進行散亂點云分割之前，采用合適的數據結構來提高鄰域搜索效率十分關鍵。獲取鄰域結構可采用Kdtree來實現。Kdtree或者K維樹是計算機科學中使用的一種數據結構，用來組織表示K維空間中點集合。它是一種帶有其他約束條件的二分查找樹。kdtree對于區間和近鄰搜索十分有用。我們為了達到目的，通常只在三個維度中進行處理，因此所有的kdtree都將是三維kdtree。kdtree的每一級在指定維度上分開所有的子節點。在樹的根部所有子節點是以第一個指定的維度上被分開（也就是說，如果第一維坐標小于根節點的點它將分在左邊的子樹中，如果大于根節點的點它將分在右邊的子樹中）。樹的每一級都在下一個維度上分開，所有其他的維度用完之后就回到第一個維度。建立kdtree最高效的方法是，像快速分類一樣使用分割法，把指定維度的值放在根上，在該維度上包含較小數值的在左子樹，較大的在右子樹。然后分別在左邊和右邊的子樹上重復這個過程。直到準備分類的最后一個樹僅僅由一個元素組成。

3.3曲率的計算

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

2Khn=limdiam（A）→0

SymbolQC@ AA式（3-1）

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

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

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

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

式中：αij、βij分別為連接頂點Pi和Pj邊的對角。

高斯曲率的離散表達式如式3-3所示

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

θj為Pi的鄰域內與頂點Pj連接的邊的夾角。

3.4八叉樹

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

3.5實驗測試

1）打開和關閉文件

使用QT文件對話框選擇點云數據格式的文件，然后從PCD文件中讀取點云數據。從磁盤上加載PointCloud數據（假設要讀取的文件已經被創建）到二進制存儲塊中。或者讀取PointCloud2存儲塊。由于點云的動態性質，以二進制塊來讀取，然后轉換成要使用的表示方式更好。把二進制塊讀取并轉換到模板化的PointCloud格式里，使用PCL點云庫中的一種點類型作為存儲點的類型。

2）可視化點云

可視化（Visualization）是利用計算機圖形學和圖像處理技術，將數據轉換成圖形或圖像在屏幕上顯示出來，并進行交互處理的理論、方法和技術。本設計利用PCL中pcl_visualization庫提供了可視化相關的數據結構和組件來可視化其他模塊的算法處理后的結果。

3）分割測試

本次測試主要選取房檐模型進行測試。測試分為分割測試和曲面重構測試。房檐模型的數據規模為80000個點，其模型如圖3.1所示。

分割時，標注分割結果的顏色是隨機產生的。由于分割時設定的參數較多，所以在此只對曲率閾值做測試，在其余條件不變的情況下，測試曲率閾值分別為0.5，1.0，1.5時的情況。

（4）曲面重構測試

由于房檐模型本身形狀規則，點比較集中，重構后的效果比較好，有層次感。

4結束語

本文基于QT，實現了PCL庫中點云文件的打開與關閉；區域生長分割，并且在點云分塊的基礎上實現了曲面重構。點云分割主要采用區域生長法，點云重構使用貪婪三角法。對于平面圖像分割及重構效果良好。

參考文獻

[1]孫金虎.點云模型分割與融合關鍵技術研究[D].南京：南京航空航天大學，2013（3）：16-25.

[2]匡小蘭.基于建筑物的著色點云平面區域分割研究[D].株洲：湖南工業大學，2011.

[3]歐新良，匡小蘭，倪問尹.三維散亂點云分割技術綜述[J].湖南工業大學學報，2010，24（5）：45-49.

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

[5]馬符訊，林歡，徐楠.散亂點云數據的可視化探究[J].科技創新導報，2013，（10）：89-95.

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

[7]石玉.基于VTK的可視化技術研究與實現[D].西安：西安建筑科技大學，2009.

[8]胡懷宇，崔漢國，代星.基于區域生長法的散亂點云分區方法[J].計算機應用，2009，（10）：32-37.

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

[10]袁占斌，聶玉峰，歐陽潔.平面自動布點及Delaunay三角形網格生成[J].計算機工程與應用.2009，（17）：60-64.

[11]董明曉.曲面重構中點云數據的區域分割研究[J].中國圖像圖形學報，2005，10（5）：575-578.

[12]柯映林.基于邊特征的點云數據區域分割[J].浙江大學學報，2005，39（3）：377-395.

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

[14]匡小蘭，歐新良，倪問尹.散亂點云數據區域分割綜述[J].長沙大學學報，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]龔友平，金濤，童水光.點云數據區域分割方法[J].工程圖學學報，2006，（4）：28-33.

第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016endprint