葉珉?yún)?花向紅

(1.佛山市城市規(guī)劃勘測設(shè)計研究院,廣東佛山 528000; 2.武漢大學(xué)測繪學(xué)院,湖北武漢 430079)

顧及激光反射率的點(diǎn)云數(shù)據(jù)分割算法研究

葉珉?yún)??,花向紅2

(1.佛山市城市規(guī)劃勘測設(shè)計研究院,廣東佛山 528000; 2.武漢大學(xué)測繪學(xué)院,湖北武漢 430079)

點(diǎn)云數(shù)據(jù)分割是三維模型重建的關(guān)鍵環(huán)節(jié),傳統(tǒng)的基于模糊C均值聚類(FCM)的點(diǎn)云數(shù)據(jù)分割算法在規(guī)則物體細(xì)節(jié)的分割上具有一定的局限性。針對此問題,在傳統(tǒng)算法的基礎(chǔ)上,增加了激光反射率信息,提出了顧及激光反射率的分割算法。通過實(shí)例驗證,該算法具有較高的可行性和普遍適用性,分類結(jié)果較為可靠。

點(diǎn)云數(shù)據(jù);分割算法;激光反射率;FCM;三維模型

1 引 言

三維激光掃描技術(shù)以其數(shù)據(jù)獲取速度快、實(shí)時性強(qiáng)、精度高及全天候工作等優(yōu)點(diǎn)被廣泛應(yīng)用于逆向工程、數(shù)字城市及變形監(jiān)測等領(lǐng)域,利用它可以對實(shí)物進(jìn)行數(shù)字化,快速獲取物體表面大量點(diǎn)的三維坐標(biāo)、激光反射強(qiáng)度及顏色信息等,稱為點(diǎn)云數(shù)據(jù)。對點(diǎn)云數(shù)據(jù)的分割是三維模型重建的基礎(chǔ),也是關(guān)鍵環(huán)節(jié),分割的結(jié)果和效率直接決定了后續(xù)應(yīng)用的難度,具有重要的研究意義[1]。點(diǎn)云分割是指將三維空間中的點(diǎn)劃分成若干個互不相交的子集的過程,經(jīng)過分割后,具有相似屬性的點(diǎn)歸為一類,得到一系列我們感興趣的對象,如建筑、植被、街道等[2]。

目前,點(diǎn)云分割算法主要有以下三種:基于邊檢測的分割算法、基于區(qū)域增長的分割算法及基于聚類的分割算法[3]?；谶厵z測的分割算法根據(jù)點(diǎn)云的局部幾何特征在點(diǎn)集中檢測邊界點(diǎn),通過邊界點(diǎn)的連接形成邊界線將整個點(diǎn)云分割成多個獨(dú)立的子點(diǎn)云,由于對邊界的確定只用到邊界的局部數(shù)據(jù),使得該算法易受到測量噪聲的影響?；趨^(qū)域增長的分割算法根據(jù)給定的相似性準(zhǔn)則,以一個選定的種子點(diǎn)向外延伸,同時判斷周圍的點(diǎn)是否滿足同一準(zhǔn)則,合乎準(zhǔn)則的點(diǎn)被加入到同一區(qū)域中,直至其周圍鄰域不包含連續(xù)的點(diǎn)集為止。與基于邊檢測的算法相比,該算法容易實(shí)現(xiàn)而且計算速度快,受噪聲的干擾也較小,但種子點(diǎn)選擇的好壞對分割效果有很大的影響,如何得到一致的分割結(jié)果依然是一個有待解決的問題[4]?；诰垲惖姆指钏惴ǜ鶕?jù)“物以類聚”的原則對數(shù)據(jù)進(jìn)行分割,屬于同一表面的點(diǎn)云數(shù)據(jù)具有某種相似的特征屬性(如法向量、曲率等)。該算法無需選擇種子點(diǎn),且具有較強(qiáng)的抗噪能力,在機(jī)載或地面激光掃描點(diǎn)云的分割實(shí)例中,已顯示出了它的健壯性[1],其中基于模糊C均值聚類(Fuzzy C-Means algorithm,FCM)的分割算法[4,5]已經(jīng)較為成熟,被廣泛應(yīng)用于點(diǎn)云數(shù)據(jù)中建筑物、街道與植被之間的分割。目前基于FCM的分割算法主要是借助點(diǎn)云的位置信息、幾何信息如法向量或曲率等特征屬性進(jìn)行數(shù)據(jù)分割,對于屬性信息差別較大的數(shù)據(jù)能夠獲得較為理想的結(jié)果,但對于比較規(guī)則的物體,如在三維城市建模中,建筑物外觀細(xì)節(jié)的分割卻具有較大的局限性。

針對上述問題,在現(xiàn)有算法的基礎(chǔ)上,提出一種顧及激光反射率的點(diǎn)云數(shù)據(jù)分割算法,并通過實(shí)例分析,驗證該算法的可行性。

2 點(diǎn)云數(shù)據(jù)分割算法

2.1 傳統(tǒng)算法

傳統(tǒng)的基于FCM的點(diǎn)云數(shù)據(jù)分割算法根據(jù)點(diǎn)云的位置信息、幾何信息等特征屬性,通過引入隸屬度矩陣表示屬于不同類別的程度對數(shù)據(jù)進(jìn)行分割,其基本思想是:首先初始化分類,之后通過反復(fù)迭代運(yùn)算,考察每個樣本的分類是否正確。若不正確,就要不斷地計算類心和調(diào)整各樣本的類別,直到使得以非相似性(或距離)為指標(biāo)的目標(biāo)函數(shù)達(dá)到最小。最后如果相鄰兩次的聚類中心沒有任何變化,說明樣本調(diào)整結(jié)束,目標(biāo)函數(shù)已經(jīng)收斂,算法結(jié)束。模糊C均值聚類算法能夠使得各類本身盡可能的緊湊,而各類之間盡可能的分開。

設(shè)樣本集X={X1,X2,…,Xn},n為樣本集中元素個數(shù),觀測樣本Xi具有m維特征屬性{xi1,xi2,…, xim},其中包括點(diǎn)云位置信息即x、y、z坐標(biāo)、幾何信息如法向量或曲率等。

式中,k為聚類數(shù),滿足2≤k≤n;d(Xj,Ci)=‖Xj-Ci‖2為樣本Xj和聚類中心Ci的歐幾里得距離的平方;M為模糊度,一般M=2時算法最優(yōu)[6];uij表示第j個樣本和第i個聚類中心的隸屬度,uij∈[0,1],且滿足以下條件:

給定聚類數(shù)k及閾值ε,算法的具體計算步驟如下:

(1)初始化聚類中心Ci,i=1,2,…,k;

(2)計算隸屬度矩陣;

(3)根據(jù)式(1)計算目標(biāo)函數(shù),如果其小于給定的閾值ε,則算法停止;

(4)循環(huán)(2)到(3)步直到每個聚類不再發(fā)生變化為止。

2.2 本文算法

掃描獲得的點(diǎn)云數(shù)據(jù)中包含了三維坐標(biāo)、激光反射率及顏色等屬性信息,現(xiàn)有的算法更多的是借助點(diǎn)云的幾何信息,從空間相似性上對數(shù)據(jù)進(jìn)行分割,沒有很好地利用激光反射率等特征屬性。由于僅根據(jù)空間相似性,對于屬性信息差別較大的數(shù)據(jù),傳統(tǒng)算法能夠獲得較為理想的分割結(jié)果,但對于比較規(guī)則或變化起伏不大的物體,卻具有較大的局限性。

激光反射率是掃描目標(biāo)對儀器激光束的反射回波的光功率[7],包含了目標(biāo)表面的特征信息。一般情況下,同類型的地物具有近似的反射率特征,因此可以利用激光反射率作為點(diǎn)云分割的一個判別依據(jù)。在傳統(tǒng)的基于FCM的點(diǎn)云數(shù)據(jù)分割算法的基礎(chǔ)上,在觀測數(shù)據(jù)的特征屬性{xi1,xi2,…,xim}中增加反射率信息,形成本文提出的顧及激光反射率的分割算法,其目標(biāo)函數(shù)和計算步驟同2.1中一致。

3 實(shí)例分析

3.1 實(shí)例一

使用三維激光掃描儀獲取一點(diǎn)云數(shù)據(jù),分別使用傳統(tǒng)方法和本文方法進(jìn)行數(shù)據(jù)分割,不同類別的點(diǎn)云使用不同顏色標(biāo)出,結(jié)果如圖1與圖2所示:

圖1 傳統(tǒng)算法分割結(jié)果

圖2 本文算法分割結(jié)果

圖1 、圖2中,紅色數(shù)據(jù)為建筑物屋頂,藍(lán)色數(shù)據(jù)為周邊的樹木,由兩圖可以看出,兩種地物被很好地分割成了兩類。相比于樹木,建筑物比較規(guī)則,曲率等空間特性變化較小,兩者屬性信息相差較大,因此兩種算法都能獲得很好的分割結(jié)果。

對于建筑、植被、街道等地物,彼此之間的空間位置、幾何特性等屬性信息相差較大,而傳統(tǒng)算法和本文算法都顧及了數(shù)據(jù)的位置、曲率等信息,因此,兩種算法都能夠有效地將它們分割開來,獲得較好的聚類結(jié)果。

3.2 實(shí)例二

使用三維激光掃描儀獲取一建筑物立面數(shù)據(jù),分別使用傳統(tǒng)方法和本文方法進(jìn)行數(shù)據(jù)分割,不同類別的點(diǎn)云使用不同顏色標(biāo)出,結(jié)果如圖3與圖4所示:

由于建筑物外觀比較規(guī)則,曲率等特性變化不大,而傳統(tǒng)算法僅依據(jù)空間屬性進(jìn)行分割,因此圖3中數(shù)據(jù)被簡單地平均分割成兩部分。而由圖4可以看出,由于增加了激光反射率信息,本文算法能夠正確地將窗戶(黃色)與墻壁(藍(lán)色)分割開來,雖然兩者都為規(guī)則平面,空間相似性較大,但兩者材質(zhì)決定了兩者具有不同的反射特性,因此獲得了理想的分割結(jié)果。

圖3 傳統(tǒng)算法分割結(jié)果

圖4 本文算法分割結(jié)果

對于空間屬性信息差別較小的地物分割,如建筑物外觀細(xì)節(jié)的分割、不同材質(zhì)路面的分割等,僅根據(jù)空間信息進(jìn)行聚類的傳統(tǒng)算法不能獲得較為理想的結(jié)果;而本文算法在空間信息的基礎(chǔ)上,增加了激光反射率信息,能夠較好地將不同類型的地物區(qū)分開來,獲得較為正確的分割結(jié)果,具有較高的可行性。

由上述兩個實(shí)例可以看出,本文算法同時顧及了空間屬性信息與反射率信息,對于任何類型的數(shù)據(jù)都能獲取較好的分割結(jié)果,具有較高的可行性和普遍適用性。

4 結(jié) 語

在傳統(tǒng)的基于FCM的點(diǎn)云數(shù)據(jù)分割算法的基礎(chǔ)上,增加了反射率信息,作為點(diǎn)云數(shù)據(jù)分割的一個判別依據(jù),提出了顧及激光反射率的分割算法。實(shí)例結(jié)果表明,對于空間位置、幾何特性等屬性信息相差較大的物體,傳統(tǒng)算法和本文算法都能夠獲得較好的聚類結(jié)果;而對于空間屬性信息差別較小的地物分割,僅根據(jù)空間信息進(jìn)行聚類的傳統(tǒng)算法不能獲得較為理想的結(jié)果,由于不同類型的地物具有不同的反射率特征,本文算法在空間信息的基礎(chǔ)上,增加了激光反射率信息,能夠較好地將不同類型的地物區(qū)分開來,獲得較為正確的分割結(jié)果,該算法具有較高的可行性和普遍適用性,分類結(jié)果較為可靠。

[1] 劉進(jìn),武仲科,周明全.點(diǎn)云模型分割及應(yīng)用技術(shù)綜述[J].計算機(jī)科學(xué),2010,38(4):21～24.

[2] Pu Shi,Vosselman G.Automatic extraction of building features from terrestrial laser scanning[C]//International Archives of Photogrammetry,Remote Sensing and Spatial Information Science,2006,36.

[3] 喻亮.基于車載激光掃描數(shù)據(jù)的地物分類和快速建模技術(shù)研究[D].武漢:武漢大學(xué),2011.

[4] Biosca J M,Lerma J L.Unsupervised robust planar segmentation of terrestrial laser scanner point clouds based on fuzzy clustering methods[J].ISPRS Journal of Photogrammetry and Remote Sensing,2008,63(1):84～98.

[5] Jiangtong Zhao,Deren Li,Yanmin Wang.Ancient Architecture Point Cloud Data Segmentation Based on Modified Fuzzy C-Means Clustering Algorithm[J].Proceedings of SPIEICEODPA 2008,Wuhan,China,2008,12.

[6] J.C.Bezdek,R.Hathaway et al.Convergence theory for fuzzy c-means:counter examples and repairs[C]//IEEE, Trans,PAMI,1987,17(5):873～877.

[7] Pfeifer N,Dorninger P,Haring A,et al.Investigating terrestrial laser scanning intensity data:quality and functional relations[C]//Proceedings of the VIII Conference on Optical 3D Measurement Technology,Zurich,2007:328～337.

[8] 楊榮華.地面三維激光掃描點(diǎn)云角度分辨率與數(shù)據(jù)處理模型研究[D].武漢:武漢大學(xué),2011.

Research on Segmentation Algorithm considering Laser Reflectance for Point Cloud Data

Ye Minlv1,Hua Xianghong2
(1.Foshan Urban Planning Design and Surveying Research Institute,Foshan 528000,China; 2.School of Geodesy and Geomatics,Wuhan University,Wuhan 430079,China)

Segmentation algorithm for point cloud data is the key to the reconstruction of 3D model,the traditional segmentation algorithm based on fuzzy c-means algorithm has limitation on the segmentation of the regular object’s details.For this problem,on the basis of the traditional algorithm,the thesis adds the laser reflectance information to the algorithm and proposes a new segmentation algorithm considering laser reflectance.Verified by the examples,it is indicating that the new segmentation algorithm is more feasible and effective,its results are more reliable.

point cloud data;segmentation algorithm;laser reflectance;fuzzy c-means algorithm;3D model

1672-8262(2014)06-21-03

P234.4

B

2014—09—10

葉珉?yún)?1989—),男,助理工程師,主要研究方向為三維激光掃描技術(shù)。

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