陳向陽(yáng)，楊 洋，向云飛

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

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

陳向陽(yáng)1，楊 洋2，向云飛3

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

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

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

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

圖1 聚類分析示意圖

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

1 歐氏聚類分割算法

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

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

(1)

2 散亂點(diǎn)云索引方式的選擇

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

2.1 Octree和KD-tree

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

圖2 三維KD-tree示意圖

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

圖3 Octree的構(gòu)建

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

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

表1 程序運(yùn)行時(shí)間

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

3 歐氏聚類分割算法流程

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

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

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

(3) 對(duì)于每個(gè)點(diǎn)Pi∈P，執(zhí)行以下步驟：

a. 將Pi點(diǎn)加入當(dāng)前的隊(duì)列Q。

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

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

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

4.1 試驗(yàn)1

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

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

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

4.1.2 點(diǎn)云分割試驗(yàn)

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

圖5 分割出的其他類別

圖6 分割出的平面類別

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

4.2 試驗(yàn)2

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

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

4.2.2 面片提取試驗(yàn)

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

圖8 試驗(yàn)區(qū)的點(diǎn)云密度分布

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

圖9 簡(jiǎn)單濾波后的試驗(yàn)區(qū)點(diǎn)云數(shù)據(jù)

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

圖10 下采樣前后點(diǎn)云密度分布

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

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

5 結(jié) 語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

[11] 張玉方，程新文，歐陽(yáng)平，等.機(jī)載LiDAR數(shù)據(jù)處理及其應(yīng)用綜述[J]. 工程地球物理學(xué)報(bào)，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ù)建筑物頂面點(diǎn)云分割方法研究[J]. 測(cè)繪通報(bào)，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點(diǎn)云中建筑物激光點(diǎn)的自動(dòng)提取[J]. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2013，30(3)：269-273.

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

陳向陽(yáng)，楊洋，向云飛.歐氏聚類算法支持下的點(diǎn)云數(shù)據(jù)分割[J].測(cè)繪通報(bào)，2017(11)：27-31.

10.13474/j.cnki.11-2246.2017.0342.

P23

A

0494-0911(2017)11-0027-05

2017-07-26

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

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