陳向陽，楊 洋，向云飛

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

歐氏聚類算法支持下的點云數(shù)據(jù)分割

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

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

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

歐氏聚類;點云數(shù)據(jù);分割;算法

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

圖1 聚類分析示意圖

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

1 歐氏聚類分割算法

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

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

(1)

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

通過立體攝影測量機(jī)、機(jī)載LiDAR和三維激光掃描儀等三維測量設(shè)備獲取點云數(shù)據(jù)，具有數(shù)據(jù)量大且分布不均勻的特點。點云數(shù)據(jù)作為三維領(lǐng)域中重要的數(shù)據(jù)來源，由海量的離散點構(gòu)成，呈散亂無序的狀態(tài)，并不具備傳統(tǒng)網(wǎng)格數(shù)據(jù)的幾何拓?fù)潢P(guān)系[9]。因此，建立離散點之間的拓?fù)潢P(guān)系是點云數(shù)據(jù)處理中最為核心的問題，基于此，鄰域關(guān)系的快速查找才能得以實現(xiàn)。

2.1 Octree和KD-tree

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

圖2 三維KD-tree示意圖

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

圖3 Octree的構(gòu)建

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

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

表1 程序運行時間

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

3 歐氏聚類分割算法流程

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

(1) 對輸入的點云數(shù)據(jù)P建立Octree數(shù)據(jù)結(jié)構(gòu)。

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

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

a. 將Pi點加入當(dāng)前的隊列Q。

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

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

4 試驗與結(jié)果分析

4.1 試驗1

4.1.1 試驗數(shù)據(jù)介紹

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

圖4 原始點云數(shù)據(jù)

4.1.2 點云分割試驗

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

圖5 分割出的其他類別

圖6 分割出的平面類別

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

4.2 試驗2

4.2.1 試驗數(shù)據(jù)介紹

圖7 試驗區(qū)數(shù)據(jù)

4.2.2 面片提取試驗

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

圖8 試驗區(qū)的點云密度分布

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

圖9 簡單濾波后的試驗區(qū)點云數(shù)據(jù)

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

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

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

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

5 結(jié) 語

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

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

圖11 試驗區(qū)建筑物頂部面片

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

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

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

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

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

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

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

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

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

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

[11] 張玉方，程新文，歐陽平，等.機(jī)載LiDAR數(shù)據(jù)處理及其應(yīng)用綜述[J]. 工程地球物理學(xué)報，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] 于海洋，余鵬磊，謝秋平，等.機(jī)載LiDAR數(shù)據(jù)建筑物頂面點云分割方法研究[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] 羅勝，姜挺,王鑫，等.原始機(jī)載LiDAR點云中建筑物激光點的自動提取[J]. 測繪科學(xué)技術(shù)學(xué)報，2013，30(3)：269-273.

[16] 黃先鋒，李卉，王瀟，等.機(jī)載LIDAR數(shù)據(jù)濾波方法評述[J]. 測繪學(xué)報，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

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

10.13474/j.cnki.11-2246.2017.0342.

P23

A

0494-0911(2017)11-0027-05

2017-07-26

國家自然科學(xué)基金(41174002)

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