歐氏聚類算法支持下的點云數據分割

陳向陽，楊 洋，向云飛

(1. 南通職業大學建筑工程學院，江蘇 南通 226007； 2. 上海華測導航技術股份有限公司，上海 201702； 3. 河海大學， 江蘇 南京 211100)

歐氏聚類算法支持下的點云數據分割

陳向陽1，楊 洋2，向云飛3

(1. 南通職業大學建筑工程學院，江蘇 南通 226007； 2. 上海華測導航技術股份有限公司，上海 201702； 3. 河海大學， 江蘇 南京 211100)

歐氏聚類算法是多元統計中的一種重要分類方法，可以將其應用于測繪領域中點云數據的分割。本文首先計算點云數據中兩點之間的歐氏距離，將距離小于指定閾值作為分為一類的判定準則；然后迭代計算，直至所有的類間距大于指定閾值，完成歐氏聚類分割。具體步驟為：①利用Octree法建立點云數據拓撲組織結構；②對每個點進行k近鄰搜索，計算該點與k個鄰近點之間的歐氏距離，最小歸為一類；③設置一定的閾值，對步驟②迭代計算，直至所有類與類之間的距離大于指定閾值。試驗證明，歐氏聚類算法對不同測量技術手段獲取的點云數據均具有適用性，可以成功對點云數據進行分割，分割效果良好。

歐氏聚類;點云數據;分割;算法

聚類分析是依據樣品中的個體、對象或主體的特征屬性將它們進行分類，使類別之間的個體具有盡可能高的異質性(heterogeneity)，而處于同一類別內的個體則應具有盡可能高的同質性(homogeneity)。圖1為聚類分析的示意圖[1]。聚類分析的關鍵是樣本之間親疏關系的判定及分類數的確定，對于變量之間的親疏關系可通過變量間的相似系數來判定，對于樣本數據可以通過樣本點間的距離來判定其親疏相對關系。按照分類的對象可以將聚類分析分為Q型聚類和R型聚類，根據分類的方法又可以將聚類分析分為系統聚類(hierarchical clustering)、快速聚類(K-means clustering)、模糊聚類。聚類分析是一種重要的多元統計分類方法，可應用于許多領域[2]。

圖1 聚類分析示意圖

點云分割是根據對象的幾何、紋理等空間特征對點云數據進行分類劃分，使擁有相似特征的點云處于同一劃分區內[3]。目前，許多工程應用的前提是對點云數據的有效分割，在激光遙感學科應用領域，要對地物進行識別、重建，首先要對地物進行分類處理[4]。在逆向工程方面，對零件進行探傷、孔洞修復和三維建模，首先要對零件表面掃描分割，然后才能進行基于三維內容的組合利用等[5]。利用歐氏聚類算法，可以成功地將點云數據分割為不同類別的點，同時具有很好的魯棒性。

1 歐氏聚類分割算法

聚類方法中的每個點都關聯一個特征向量，特征向量包含若干個度量值。點云數據的分割是在特征空間中通過聚類的方法進行[6]。聚類分割的原理為：要考察m個數據點，設m個數據點共組成n類，在m維空間數據中定義某種性質的點與點之間的親疏聚類，然后將具有最小距離的兩類合為一類，并迭代計算類之間的距離，直到所有類別之間的距離大于固定閾值，或類的個數小于指定的個數，完成分割[7]。

距離相似性常用于聚類分析，點間距離遠近可判斷樣本相似性度量，也可反映樣本所屬類型有無差異。距離越近表明相似性越大，屬于一個類型。距離指標可按照數據的性質差別來選用，本文采用歐氏距離作為距離指標[8]。假設每個樣品由p個變量描述，可看作空間的一個點，則n個樣品就是p維空間中的n個點，則第i樣品和第j樣品的距離記為

(1)

2 散亂點云索引方式的選擇

通過立體攝影測量機、機載LiDAR和三維激光掃描儀等三維測量設備獲取點云數據，具有數據量大且分布不均勻的特點。點云數據作為三維領域中重要的數據來源，由海量的離散點構成，呈散亂無序的狀態，并不具備傳統網格數據的幾何拓撲關系[9]。因此，建立離散點之間的拓撲關系是點云數據處理中最為核心的問題，基于此，鄰域關系的快速查找才能得以實現。

2.1 Octree和KD-tree

目前，點云空間拓撲關系的建立方式主要有Octree法和KD-tree法。利用Octree法和KD-tree法均可以進行每個激光腳點的k近鄰搜索。KD-tree或k維樹，是一種帶有約束條件的二分查找樹，用來組織表示k維空間中的點集合。KD-tree中用指定維度分開每一級別的所有子節點，樹的每一級在下一個維度分開，所有維度用完后回到第一個維度。通過判斷第一維坐標與根節點的大小來確定點在子樹中的左右位置[10]。樹的每一級在下一個維度分開，所有維度用完后回到第一個維度。對于點云數據來說，通常只在3個維度中進行處理，建立三維KD-tree，圖2為三維KD-tree示意圖。

圖2 三維KD-tree示意圖

Octree結構是對空間實體進行體元剖分，使每個體元具有相同的時空復雜度，對三維空間大小為2n×2n×2n的幾何對象再通過循環遞歸的劃分方法進行剖分，從而構成具有根節點的方向圖[11]。在Octree中，單個葉節點由相同屬性的體元構成；否則要對該體元依次進行遞歸剖分，直到劃分的體元具有相同屬性，對于2n×2n×2n大小的空間最多剖分n次，如圖3所示。

圖3 Octree的構建

2.2 兩種索引方式搜索性能分析

利用C++語言隨機生成樣本點分別為100、1000、10 000的點云數據，利用KD-tree法和Octree法分別對樣本數據中每個點進行k近鄰搜索，并利用C++中計時函數計算程序運行時間。同時，對每個樣本數據中每個點的最近點個數(即k的值)，設置為10、25、50，來測試兩種方法的搜索性能。表1為測試的結果。

表1 程序運行時間

由表1可知，當樣本數據較小時，兩種點云索引方式的搜索性能相當。當樣本數據量變大時，Octree法相對來說有較高的搜索效率。當數據中搜索的每個點的最近鄰點數目(即k的值)變大時，兩種索引方式均需要消耗更多的時間，但Octree法表現出更好的搜索性能。機載LiDAR、激光掃描等三維測量設備獲取的點云數據，數據量往往很大，有必要尋求一種高效率的點云索引機制[12]。基于以上比較，可以利用Octree法來搜索每個點的最近鄰點，進而進行歐氏聚類分割。

3 歐氏聚類分割算法流程

歐氏聚類分割需要將散亂點云模型劃分為更小的部分，這樣處理的時間就會大大縮短。利用Octree法可以將散亂點云進行三維格網的劃分，建立散亂點云之間的拓撲關系。通過建立的八叉樹數據結構，可以對每個激光腳點進行鄰近點的搜索，計算每個點與鄰近點的歐氏距離，將距離最小的歸為一類，再在新類之間進行歐氏距離的計算和迭代，直到指定閾值小于任意兩類之間的歐氏距離或類的個數小于指定數目，歐氏聚類分割完成[13]。具體算法流程如下：

(1) 對輸入的點云數據P建立Octree數據結構。

(2) 建立一個空的聚類集合C和一個隊列Q，Q中的每個點都要執行以下操作。

(3) 對于每個點Pi∈P，執行以下步驟：

a. 將Pi點加入當前的隊列Q。

c. 當隊列Q中列表中所有點執行以上操作，將Q中的點加入到集合C的列表中，并將Q的列表清空。

(4) 當每個點Pi∈P執行以上操作，且Pi均是集合C中的一部分，算法終止。

4 試驗與結果分析

4.1 試驗1

4.1.1 試驗數據介紹

試驗1數據選取利用三維掃描儀對實物掃描獲取的點云數據，該數據包含點460 400個，原始數據如圖4所示。該數據中包含比較明顯的幾個類別，分別有平面、圓柱型、條形等，比較適合進行歐氏聚類分割試驗。

圖4 原始點云數據

4.1.2 點云分割試驗

通過VoxelGrid濾波器對點云進行下采樣。VoxelGrid濾波器通過輸入的點云數據創建一個三維體素柵格，然后在每個體素(即三維立方體)內用體素中所有點的重心來近似顯示體素內的其他點。利用VoxelGrid濾波器對點云數據進行采樣，可保持點云的形狀特征不受點數量的減少而改變，大大提高了歐氏聚類的效率。聚類分割的結果如圖5、圖6所示。

圖5 分割出的其他類別

圖6 分割出的平面類別

由以上可知，歐氏聚類分割可以成功對三維掃描儀掃描實體的數據進行分割，分割出來的實體具有較相似的類別屬性。

4.2 試驗2

4.2.1 試驗數據介紹

圖7 試驗區數據

4.2.2 面片提取試驗

(1) 對試驗數據的點云密度分布進行統計，圖8為點云密度分布圖。從圖8可以看出，深色區域為地面點和近地面點的密度分布，由橫軸可知，地面點和近地面點的高程集中在882～894 m之間。

圖8 試驗區的點云密度分布

利用直通濾波器對試驗數據在指定的維度(z軸)上進行濾波，設置濾波的z軸的范圍為882～894 m，將在該區間的所有點去除。通過這一操作，對點云數據進行了一個簡單的濾波，初步去除了地面點和近地面點，大大減小了面片提取程序的計算工作量。圖9為經過直通濾波器進行處理的試驗數據，處理后的點云數據去除了大部分的地面點和近地面點，其中包含181 534個點。

圖9 簡單濾波后的試驗區點云數據

(2) 通過VoxelGrid濾波器對點云進行下采樣。VoxelGrid濾波器對經過簡單過濾后的點云數據創建一個三維體素柵格，由于點云密度為10個/m2，可以設置三維體素體積為0.5 m×0.5 m×0.5 m，在每個體素(即三維立方體)內用體素中所有點的重心來近似顯示體素內的其他點。經過VoxelGrid濾波器下采樣后,試驗區的點云數據中包含134 318個點。圖10為下采樣前后點云密度分布圖，圖10(a)為下采樣前，圖10(b)為下采樣后，通過對比前后點云密度分布可以看出，下采樣前后保持了點云的形狀態特征，只是減小了相應區域的點云密度。

圖10 下采樣前后點云密度分布

(3) 將檢測的平面利用歐氏聚類的方法，設置聚類點之間的容差為0.8 m，每類點最少個數為500個，通過迭代判定，可以將少量、離散的激光腳點去除，從而得到建筑物頂部面片。在CloudCompare中將經過處理的平面模型疊加到一起，得到試驗區域所有建筑物頂部面片，圖11為對試驗區域提取的建筑物頂部面片。

由圖11可知，利用歐氏聚類算法可以較成功地提取出試驗區域的建筑物頂部面片，提取的建筑物頂部的面片比較完整，去除了一些附屬物的激光腳點，用該種方法進行建筑物頂部面片的提取，自動化程度較高。

5 結 語

聚類分析是多元統計中一個重要的分析方法，也是一種分類技術，雖然與多元統計的其他方法相比，還比較粗糙，理論上還不完善，但是應用方面取得了很大的成功，與回歸分析、判別分析一起被稱為多元統計分析的3大方法。聚類分析可以直接比較各事物之間的性質，將性質相近的歸為一類，將性質差別較大的歸為不同的類[14]。聚類分析應用非常廣泛，經常應用于數學、物理、經濟分析等方面。

目前，通過機載LiDAR、激光掃描、立體攝影機等三維測量設備獲取的點云數據由大量的離散點組成，點云分割是點云處理的一個重要的方面[15]。通過將聚類分析運用到點云處理，可以很好地進行點云分割。通過對大量離散點建立拓撲組織結構，搜尋每個的k近鄰點，計算當前點與鄰近點的歐氏距離，將距離最小的歸為一類，迭代計算，直到類與類之間的距離大于一定的閾值，完成歐氏聚類分割[16]。通過本文的兩個試驗證明，無論是機載LiDAR技術獲取的大面積的點云數據，還是利用三維激光掃描儀獲得的小區域的點云數據，利用聚類分析均能夠對點云數據進行有效分割，分割效果良好。

圖11 試驗區建筑物頂部面片

[1] 龔書林.三維激光點云處理軟件的若干關鍵技術[J]. 測繪通報，2014(6):135-136.

[2] 譚凱，程效軍. 激光強度值改正模型與點云分類精度[J]. 同濟大學學報(自然科學版),2014,42(1)：131-135.

[3] 李娜，馬一薇，楊洋，等. 利用 RANSAC算法對建筑物立面進行點云分割[J]. 測繪科學，2011,36(5)：144-145.

[4] 王書民，李文寧，張愛武. 采用模糊C 均值方法進行激光點云分類[J]. 測繪通報，2016(10):21-24.

[5] 郭波，黃先鋒，張帆，等. 顧及空間上下文關系的JointBoost點云分類及特征降維[J]. 測繪學報，2013,42(5)：715-721.

[6] 程曉光，黃先鋒，張帆. 機載LiDAR數據的城區樹木點提取方法[J]. 測繪科學，2014,39(3):52-56.

[7] 蔡來良,吳侃，張舒. 點云平面擬合在三維激光掃描儀變形監測中的應用[J]. 測繪科學，2010,35(5):231-232.

[8] 姜如波. 基于三維激光掃描技術的建筑物模型重建[J]. 測繪通報，2013(S1)：113-116.

[9] 朱慶偉，馬宇佼. 基于三維激光掃描儀的建筑物建模應用研究[J]. 地理與地理信息科學，2014,30(6)：31-35.

[10] 李峰，崔希民，袁德寶，等.機載LiDAR點云城市建筑物面片的提取研究[J]. 大地測量學與地球動力學，2013，33(2)：124-127.

[11] 張玉方，程新文，歐陽平，等.機載LiDAR數據處理及其應用綜述[J]. 工程地球物理學報，2008，5(1)：119-124.

[12] MUJA M. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration[C]∥International Conference on Computer Vision Theory and Applications．Lisbon:VISAPP，2009．

[13] 于海洋，余鵬磊，謝秋平，等.機載LiDAR數據建筑物頂面點云分割方法研究[J]. 測繪通報，2014(6):20-23.

[14] PAULY M，GROSS M，KOBBELT L． Efficient Simpli-fication of Point Sampled Surfaces[C]∥IEEE Visualization． Washington D.C: IEEE Computer Society Press，2002: 163-170．

[15] 羅勝，姜挺,王鑫，等.原始機載LiDAR點云中建筑物激光點的自動提取[J]. 測繪科學技術學報，2013，30(3)：269-273.

[16] 黃先鋒，李卉，王瀟，等.機載LIDAR數據濾波方法評述[J]. 測繪學報，2009，38(5)：466-469.

MeasurementofPointCloudDataSegmentationBasedonEuclideanClusteringAlgorithm

CHEN Xiangyang1,YANG Yang2,XIANG Yunfei3

(1. Vocational College of Nantong, Nantong 226007, China; 2. Shanghai Huace Navigation Technology Ltd., Shanghai 201702, China; 3. Hohai University, Nanjing 211100, China)

Euclidean clustering algorithm is an important classification method of multivariate statistical analysis. It can be applied to the segmentation of point cloud in survey field. Euclidean clustering algorithm firstly calculates the Euclidean distance between two points. The points’ distance which are less than a specified threshold are divided into a kind. Until all kinds of distance are greater than the specified threshold, it completes Euclidean clustering segmentation. Specific steps are as follows: ① using Octree method set up topology structure of point cloud data; ② for each point conduct K-nearest neighbor search, calculating the Euclidean distance between point and K neighboring points, the minimum is regard as one kind; ③ set a certain threshold, the iterative calculation ② steps until all distances between the classes are greater than the specified threshold. Experiments show that Euclidean clustering algorithm is available to point cloud data obtained from different measuring means. It can successfuly segment point cloud data and the effect is good.

Euclidean clustering;point cloud data;segmentation;algorithm

陳向陽，楊洋，向云飛.歐氏聚類算法支持下的點云數據分割[J].測繪通報，2017(11)：27-31.

10.13474/j.cnki.11-2246.2017.0342.

P23

A

0494-0911(2017)11-0027-05

2017-07-26

國家自然科學基金(41174002)

陳向陽(1975—)，男，碩士，講師，從事測量工程、衛星定位技術應用研究及數據處理。E-mail:470306595@qq.com