模糊C-均值聚類對點云數據的分割

胡文慶， 施 昆，曹 影

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

?

模糊C-均值聚類對點云數據的分割

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

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

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

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

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

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

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

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

1 模糊C-均值算法介紹

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

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

(1)

式中，C分類數。

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

(2)

(3)

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

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

(4)

(5)

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

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

(6)

則xk屬于第i類。

2 基于FCM的點云數據分割

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

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

圖1 原始點云數據

圖2 FCM算法流程

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

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

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

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

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

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

3 結語

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

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

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

[5] 龔友平，金濤，童水光.點云數據區域分割方法[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] 李海倫,黎榮,丁國富，等.應用遺傳模糊聚類實現點云數據區域分割[J].計算機應用研究，2012，29(5)：1974-1976.

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

[10] 高新波.模糊聚類分析及其應用[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技術。

2015-04-24

S 127

A

0517-6611(2015)17-353-04