胡文慶， 施 昆，曹 影

(1.昆明理工大學(xué)，云南昆明 650000；2.西南林業(yè)大學(xué)，云南昆明 650000)

?

模糊C-均值聚類對點(diǎn)云數(shù)據(jù)的分割

胡文慶1， 施 昆1，曹 影2

(1.昆明理工大學(xué)，云南昆明 650000；2.西南林業(yè)大學(xué)，云南昆明 650000)

點(diǎn)云數(shù)據(jù)的分割是點(diǎn)云數(shù)據(jù)處理流程中的重要內(nèi)容，同時(shí)也是點(diǎn)云數(shù)據(jù)三維重建的前提和基礎(chǔ)。該研究在模糊C-均值聚類(FCM)算法的基礎(chǔ)上，根據(jù)標(biāo)靶點(diǎn)云和建筑物點(diǎn)云數(shù)據(jù)的不同特征進(jìn)行實(shí)驗(yàn)，通過Matlab對地面雷達(dá)的標(biāo)靶、建筑物點(diǎn)云數(shù)據(jù)進(jìn)行分割，探討模糊C-均值聚類算法對點(diǎn)云數(shù)據(jù)分割的可行性。實(shí)驗(yàn)結(jié)果顯示，通過選擇正確點(diǎn)云數(shù)據(jù)的特征屬性，利用模糊C-均值算法對點(diǎn)云數(shù)據(jù)分割具有一定的可行性。

點(diǎn)云數(shù)據(jù)分割； 特征；模糊C-均值聚類；可行性

地面LiDAR是近年來興起的一種獲取三維數(shù)據(jù)和三維建模的空間信息技術(shù)，利用這種技術(shù)可以同步獲取目標(biāo)范圍的點(diǎn)的集合(點(diǎn)云數(shù)據(jù))，這其中包含著點(diǎn)的反射強(qiáng)度，三維坐標(biāo)，色彩信息等三維立體信息，因地面LiDAR技術(shù)具有快速獲取空間數(shù)據(jù)的優(yōu)點(diǎn)而受到廣泛關(guān)注。在對地面LiDAR點(diǎn)云數(shù)據(jù)的三維重建中，若直接對地面LiDAR點(diǎn)云數(shù)據(jù)進(jìn)行三維重建，則會(huì)增加處理的復(fù)雜度和系統(tǒng)資源的消耗，因此要對點(diǎn)云數(shù)據(jù)進(jìn)行相應(yīng)分割。

點(diǎn)云數(shù)據(jù)分割是點(diǎn)云數(shù)據(jù)的標(biāo)記過程，把屬性相同或者相近、并且空間鄰近的點(diǎn)劃分為一類，最終得到若干個(gè)由屬性相近的點(diǎn)云區(qū)域。點(diǎn)云數(shù)據(jù)分割是點(diǎn)云數(shù)據(jù)幾何特征提取、分析和識(shí)別的基礎(chǔ)，同時(shí)也是對點(diǎn)云數(shù)據(jù)三維重建的重要前提。它可以把復(fù)雜的點(diǎn)云數(shù)據(jù)按照屬性特征進(jìn)行分類，并進(jìn)行組合，降低了三維建模的難度及復(fù)雜度，對其分割的精度也直接影響著后期點(diǎn)云數(shù)據(jù)三維建模的精度。

國內(nèi)外學(xué)者對點(diǎn)云數(shù)據(jù)分割算法進(jìn)行了很多研究，分割算法主要有3類，第一類以點(diǎn)與點(diǎn)之間的幾何關(guān)系作為其閾值條件，以法向、曲率以及曲率的不連續(xù)點(diǎn)作為邊界點(diǎn)的邊界分割。Besl等通過計(jì)算每一個(gè)點(diǎn)的平均曲率和高斯曲率，并根據(jù)它們的符號(hào)將點(diǎn)云初始分割為8種不同的表面類型，然后利用雙變量多項(xiàng)式曲面擬合進(jìn)行區(qū)域增長，實(shí)現(xiàn)點(diǎn)云分割[1]；第二類基于區(qū)域生長的分割，把具有相似局部幾何特征點(diǎn)劃分為同一區(qū)域，這與聚類算法的思想比較相似。柯映林等提出了基于邊的點(diǎn)云區(qū)域分割，他們利用提取的邊特征柵格，通過空間柵格、鄰近的曲率差可以識(shí)別提取的特征柵格，從而實(shí)現(xiàn)空間散亂點(diǎn)的分割[2]；Jiang等提出利用掃描線進(jìn)行平面區(qū)域分割的方法[3]；董明曉等利用點(diǎn)云數(shù)據(jù)曲率的變化來實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)區(qū)域分割[4]；龔友平等利用點(diǎn)云數(shù)據(jù)中的法矢和曲率等信息，實(shí)現(xiàn)了點(diǎn)云數(shù)據(jù)的區(qū)域分割[5]；Ahmad Kamal Aijazi等利用超體素分割方法對城市場景的點(diǎn)云數(shù)據(jù)進(jìn)行了分割[6]。第三類則是通過聚類算法來實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的分割，根據(jù)點(diǎn)云數(shù)據(jù)的特征進(jìn)行識(shí)別，將特征相同的點(diǎn)利用聚類算法分割在一起。Hoffman等根據(jù)方差準(zhǔn)則聚類算法，利用點(diǎn)坐標(biāo)及其相應(yīng)的法向量將點(diǎn)云分割成面片[7]；李海倫等將基于遺傳算法的模糊聚類算法來實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的分割[8]，孫紅巖等利用K-means聚類算法來實(shí)現(xiàn)三維點(diǎn)云模型的分割[9]。

該研究利用模糊C-均值(Fuzzy C-Mean，F(xiàn)CM)聚類方法，并選擇點(diǎn)云數(shù)據(jù)的不同特征，包括坐標(biāo)特征，坐標(biāo)與反射率組合特征為基礎(chǔ)來對點(diǎn)云數(shù)據(jù)進(jìn)行分割。

1 模糊C-均值算法介紹

模糊C-均值算法是基于劃分的聚類算法，其基本思想是利用對象之間的相似性來實(shí)現(xiàn)目標(biāo)對象的聚類[10]。模糊C-均值算法最早是由E.Ruspini的硬聚類算法導(dǎo)出，后來由J.C.Dunn等將硬聚類算法進(jìn)行優(yōu)化、拓展，形成了模糊C-均值算法(FCM)。它是根據(jù)最小二乘的原理，通過迭代法對目標(biāo)函數(shù)進(jìn)行優(yōu)化來獲得對數(shù)據(jù)的有效劃分。

假如待分割對象是數(shù)據(jù)集X={x1,x2,…,xn}，每個(gè)分割對象中的點(diǎn)有m個(gè)特征屬性，這些特征屬性包括反射值、坐標(biāo)、顏色信息等。假設(shè)X中樣本xk對第i類的隸屬度函數(shù)為uik(o≤uik≤1)。模糊C-均值聚類中要求所有樣本點(diǎn)對于各個(gè)類的隸屬度滿足下式：

(1)

式中，C分類數(shù)。

模糊C-均值聚類算法目標(biāo)函數(shù)的一般表述為:

(2)

(3)

式中，V為第i類聚類中心。A是對稱正定矩陣，當(dāng)A是單位矩陣I時(shí)，dik則為歐氏距離，當(dāng)A不是單位矩陣I時(shí)，則為馬氏距離(Mahalanobis)。Wm的值在一定條件下反映了聚類的緊致度，當(dāng)聚類的緊致度越大時(shí)，則Wm的值越小。

法進(jìn)行求解，可以得到隸屬矩陣(4)及聚類中心(5)：

(4)

(5)

如果分類數(shù)C、數(shù)據(jù)集X及加權(quán)指數(shù)m是已知，則可以根據(jù)公式(4)、(5)來確定最佳模糊劃分矩陣以及聚類中心。利用反復(fù)迭代進(jìn)行計(jì)算，當(dāng)算法收斂后，倘若滿足下式：

μik=max{μ1k,μ2k,…,μCk}

(6)

則xk屬于第i類。

2 基于FCM的點(diǎn)云數(shù)據(jù)分割

2.1 實(shí)驗(yàn)數(shù)據(jù)簡介 此次實(shí)驗(yàn)所獲取的點(diǎn)云數(shù)據(jù)是由徠卡HDS3000采集，所獲取的點(diǎn)云數(shù)據(jù)見圖1。

2.2 實(shí)驗(yàn)結(jié)果與分析 通過利用Matlab對模糊C-均值聚類算法進(jìn)行編程實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的分割。利用選擇點(diǎn)云數(shù)據(jù)的不同特征屬性，研究模糊C-均值聚類對點(diǎn)云數(shù)據(jù)的分割效果。圖2為FCM對點(diǎn)云數(shù)據(jù)進(jìn)行分割的流程圖，取dik為歐氏距離，加權(quán)指數(shù)m=2。

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

圖2 FCM算法流程

2.2.1 以點(diǎn)的坐標(biāo)作為特征所得的聚類效果。通過不同的顏色信息來反映模糊C-均值聚類對點(diǎn)云數(shù)據(jù)分割的效果，實(shí)驗(yàn)結(jié)果見圖3。

從圖3可以看出，如果只是選擇點(diǎn)的坐標(biāo)作為特征，不論C選取為何值，都無法通過模糊C-均值聚類對點(diǎn)云數(shù)據(jù)進(jìn)行正確的分割。

2.2.2 以點(diǎn)的坐標(biāo)和反射率作為特征的聚類結(jié)果。以點(diǎn)的坐標(biāo)和反射率作為特征進(jìn)行聚類，實(shí)驗(yàn)結(jié)果見圖4。

從圖4可以看出，當(dāng)以點(diǎn)的坐標(biāo)和反射率作為特征時(shí)，模糊C-均值聚類的分割結(jié)果則很明顯。相比于只選擇點(diǎn)的坐標(biāo)為特征的分割結(jié)果，其分割效果要好很多。對于標(biāo)靶點(diǎn)云數(shù)據(jù)，在選取適當(dāng)?shù)姆诸悩銫和反射率，利用FCM聚類對其進(jìn)行分割；而對于建筑物點(diǎn)云，建筑物的墻面、門和窗戶能較好的分割出來，但在樹木和建筑物相參雜的部分，其分割的效果較差。

通過模糊C-均值聚類對地面LiDAR點(diǎn)云數(shù)據(jù)的分割實(shí)驗(yàn)可知，在選擇合適的特征和參數(shù)時(shí)，對點(diǎn)云數(shù)據(jù)的分割還是有較好的可行性。但如何提高分割的精度、如何選擇合適的特征參數(shù)還需要進(jìn)一步的研究。

圖4 以點(diǎn)的坐標(biāo)和反射率為特征的分割結(jié)果

3 結(jié)語

隨著激光掃技術(shù)的發(fā)展，其應(yīng)用也滲透到城市規(guī)劃、監(jiān)測、軍事等各個(gè)領(lǐng)域，而如何提取、分析和識(shí)別其獲取大量的實(shí)時(shí)、動(dòng)態(tài)、高精度的點(diǎn)云數(shù)據(jù)，也將是研究的重要部分。該研究基于模糊C-均值聚類算法，選擇合適特征參數(shù)，有效地對點(diǎn)云數(shù)據(jù)進(jìn)行了分割，證明其可行性。為提高點(diǎn)云分割的效果和精度，則需要選擇合適的特征，確定算法中的關(guān)鍵參數(shù)。如何選擇更合適的特征、確定算法中的關(guān)鍵參數(shù)和改進(jìn)算法來使得點(diǎn)云分割更加自動(dòng)、精度更高，是今后通過模糊C-聚類對點(diǎn)云數(shù)據(jù)進(jìn)行分割的重要研究內(nèi)容。

[1] BESL P J，JAIN R C.Segmentation through variable-order surface fitting[J].PAMI,1988,10(2):167-192.

[2] 柯映林,單東日.基于邊特征的點(diǎn)云數(shù)據(jù)區(qū)域分割[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2005,39(3):377-380，396.

[3] JIANG X Y，BUNKE H，MEIER U.Fast range image segmentation using high-level segmentation primitives[C]//Proc.of the 3rdIEEE workshop on applications of computer vision.Washington,DC,USA:IEEE Computer Society,1996.

[4] 董明曉，鄭康平，許伯彥.一種點(diǎn)云數(shù)據(jù)的區(qū)域分割方法[J].機(jī)械設(shè)計(jì)，2004，21(10)：38-40.

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

[6] AIJAZI A K,CHECCHIN P,TRASSOUDAINE L T.Segmentation based classifi cation of 3D urban point clouds:A Super-Voxel based approach with evaluation[J].Remote Sens,2013,5(4):1624-1650.

[7] HOFFMAN R，JAIN A K．Segmentation and classification of range images[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1987，9(5):608-620.

[8] 李海倫,黎榮,丁國富，等.應(yīng)用遺傳模糊聚類實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)區(qū)域分割[J].計(jì)算機(jī)應(yīng)用研究，2012，29(5)：1974-1976.

[9] 孫紅巖，孫曉鵬，李華.基于K-means聚類方法的三維點(diǎn)云模型分割[J].計(jì)算機(jī)工程與應(yīng)用，2006(10)：42-45.

[10] 高新波.模糊聚類分析及其應(yīng)用[J].西安：西安電子科技大學(xué)出版社，2004.

Segmentation of Point Cloud Data with Fuzzy C-means Clustering

HU Wen-qing1, SHI Kun1, CAO Ying2

(1. Kunming University of Science and Technology, Kunming, Yunnan 650000; 2. Southwest Forestry University, Kunming, Yunnan 650000)

Point cloud data segmentation is an important part of the point cloud data processing flow, but also the premise and basis of three-dimensional reconstruction of point cloud data. Based on the fuzzy C- means clustering (FCM) algorithm, according to different characteristics of the target point cloud and building point cloud data, the target of the ground radar and buildings point cloud data was segmented with Matlab, the feasibility of fuzzy C- means clustering algorithm to segment the point cloud data was explored. The experimental results show that, by choosing the correct feature point cloud data, using the fuzzy C- mean algorithm has certain feasibility of point cloud data segmentation.

Point cloud data segmentation; Feature; Fuzzy C- means clustering; Feasibility

胡文慶(1991- )，男，江西撫州人，碩士研究生，研究方向：3S技術(shù)。

2015-04-24

S 127

A

0517-6611(2015)17-353-04