胡文慶， 施 昆，曹 影

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

?

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

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

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

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

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

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

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

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

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

1 模糊C-均值算法介紹

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

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

(1)

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

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

(2)

(3)

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

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

(4)

(5)

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

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

(6)

則xk屬于第i類。

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

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

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

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

圖2 FCM算法流程

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

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

2.2.2 以點的坐標和反射率作為特征的聚類結(jié)果。以點的坐標和反射率作為特征進行聚類，實驗結(jié)果見圖4。

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

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

圖4 以點的坐標和反射率為特征的分割結(jié)果

3 結(jié)語

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

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

[2] 柯映林,單東日.基于邊特征的點云數(shù)據(jù)區(qū)域分割[J].浙江大學學報：工學版，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] 董明曉，鄭康平，許伯彥.一種點云數(shù)據(jù)的區(qū)域分割方法[J].機械設(shè)計，2004，21(10)：38-40.

[5] 龔友平，金濤，童水光.點云數(shù)據(jù)區(qū)域分割方法[J].工程圖學學報，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)用遺傳模糊聚類實現(xiàn)點云數(shù)據(jù)區(qū)域分割[J].計算機應(yīng)用研究，2012，29(5)：1974-1976.

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

[10] 高新波.模糊聚類分析及其應(yīng)用[J].西安：西安電子科技大學出版社，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