顧及激光反射率的點云數據分割算法研究

葉珉呂,花向紅

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

顧及激光反射率的點云數據分割算法研究

葉珉呂1?,花向紅2

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

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

點云數據;分割算法;激光反射率;FCM;三維模型

1 引 言

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

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

針對上述問題,在現有算法的基礎上,提出一種顧及激光反射率的點云數據分割算法,并通過實例分析,驗證該算法的可行性。

2 點云數據分割算法

2.1 傳統算法

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

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

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

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

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

(2)計算隸屬度矩陣;

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

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

2.2 本文算法

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

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

3 實例分析

3.1 實例一

使用三維激光掃描儀獲取一點云數據,分別使用傳統方法和本文方法進行數據分割,不同類別的點云使用不同顏色標出,結果如圖1與圖2所示:

圖1 傳統算法分割結果

圖2 本文算法分割結果

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

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

3.2 實例二

使用三維激光掃描儀獲取一建筑物立面數據,分別使用傳統方法和本文方法進行數據分割,不同類別的點云使用不同顏色標出,結果如圖3與圖4所示:

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

圖3 傳統算法分割結果

圖4 本文算法分割結果

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

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

4 結 語

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

[1] 劉進,武仲科,周明全.點云模型分割及應用技術綜述[J].計算機科學,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] 喻亮.基于車載激光掃描數據的地物分類和快速建模技術研究[D].武漢:武漢大學,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] 楊榮華.地面三維激光掃描點云角度分辨率與數據處理模型研究[D].武漢:武漢大學,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

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

國家自然科學基金(41174010)