基于圖割算法的攝影測量點云面向對象分類方法

鄭 特，鄒崢嶸，張云生，杜守基，何 雪

(中南大學 地球科學與信息物理學院，湖南 長沙 410083)

航空傾斜攝影系統為城市生產三維模型提供了新的數據源[1-2]。但現有軟件以生成三維連續三角表面模型為主，缺乏語義信息。因此為了獲得具有語義信息的三維模型以及便于后續建筑物單體化工作，點云分類成為關鍵[3]。本文結合傾斜攝影測量的特點，面向建筑物三維重建的目的，將攝影測量點云分為建筑物屋頂面、立面、植被、地面4類。

相對于Lidar點云，針對攝影測量點云的分類方法較少。其中，RAU J Y等提出一種基于規則的層次語義面向對象點云分類方法[4]，但方法需要較多的閾值以保證分類效果。GERKE M等利用監督分類和非監督分類兩種方法進行傾斜攝影測量點云分類[5]，但實驗涉及的場景比較簡單。

超體素是將點云進行過分割處理后得到的感知上相似的點群，已經廣泛用于生成海量點云數據處理的對象。PAPON J 等考慮點云的空間幾何信息，基于超像素方法SLIC( Simple linear iterative cluster)[6]，提出VCCS(Voxel cloud connectivity segmentation-supervoxels) 超體素生成方法[7]，這種方法較為高效且對于比較密的點云有較好的效果，然而，在處理稀疏點云時效果欠佳。針對有序Lidar點云的結構，SONG S 等提出BESS(Boundary-enhanced supervoxel segmentation)LiDAR點云體素化方法[8]，該方法適用于稀疏點云，但僅限于有序的LiDAR點云。圖割方法是一種非常流行實用的能量優化算法，其通過能量函數最小化獲得分割結果的全局最優，并使得領域內平滑一致[9]。其在計算機視覺等領域[10-12]已經被廣泛的應用，但節點數目過多時，效率較低。

綜上所述，本文提出一種基于圖割算法的攝影測量點云面向對象分類方法。首先基于區域增長方法，提出一種新的點云體素生成算法，將攝影測量點云聚為不同的對象；然后引入圖割算法優化分類獲取鄰域內平滑一致的點云分類結果。

1 點云的體素化

為了生成邊界保持好的點云對象，本文提出一種新的超體素生成方法，流程如圖1所示，主要包括三個步驟：①將點云三維空間分成若干均勻的子空間；②在每個子空間內分別進行幾何信息和顏色信息雙重約束的區域增長；③對于區域增長后產生的碎片簇進行再聚類。

圖1 點云體素化流程

1.1 特征和子空間的生成

本文點云對象生成時使用的特征定義如式(1)所示，包括點的空間坐標x,y,z，LAB空間的顏色信息l,a,b以及點的法向量特征nx,ny,nz。

fi=(xi,yi,zi,nxi,nyi,nzi,li,ai,bi).

(1)

為了生成子空間，根據點云數據坐標的范圍以及給定空間格網數量K，將整個點云數據空間劃分為子空間，然后將每個點根據其坐標分配到對應的子空間中。

1.2 子空間初步聚類

在各子空間內分別進行區域增長聚類。為了避免欠分割，嚴格限制增長條件。

1) 隨機選擇一個未歸簇的點放入點集Pt_seeds。

2) 將Pt_seeds中第一個點標記為P0已歸簇。

3)搜索P0的4鄰域點，記為Px(x=1,2,3,4)。

4) 計算P0和Px之間的法向量差異difn和顏色差異difl，如果P0和Px在同一個子空間內，并且difn和difl分別小于閾值Tn(本文取0.1)和Tl(本文取60)，則將Px放入集合Pt_seeds。

5) 在Pt_seeds中刪除P0，接著重復2), 3), 4)步驟直到Pt_seeds為空。

6) 重復上述步驟直到所有的點都被歸簇。

1.3 再聚類

為了避免欠分割的發生，使用了多重限制的區域增長，但是同時嚴格的增長限制會不可避免地產生許多的過小簇。在這一步驟中，這些小簇會被根據周圍簇的特征相似程度重新聚類，最終得到邊界表現良好，整體大小均勻的超體素。具體步驟如下：

1) 建立初始簇的鄰域關系。

2) 設置體素包含點數的最小值(本文取20)，將包含點數小于該值的簇記為小簇，選擇一個未被重新歸簇的小簇，記為c0，其8鄰域記為cj(j=1,2,…,8)。

3) 采用式(2)計算c0與鄰域在特征空間上的距離。

d(c0,cj)=

(2)

4) 將c0和與c0特征空間距離最小的簇合并，并將兩者均標為已重歸簇。

5) 重復上述步驟直到所有小簇都被標記為已重歸簇。

6) 將所有簇的狀態重置為未重歸簇，直到小簇的數量不再變化。

2 基于圖割的點云分類

本文將攝影測量點云分為建筑物屋頂、建筑物立面、植被與地面4類，因此首先需要計算能夠區分這四類地物的特征。

2.1 特征計算

本文分類用到的特征如下：

1) 歸一化超綠指數nEGI(Normalized Excessive Green Index)[11]：點的nEGI由式(3)計算。

nEGI=(2G-R-B)/(2G+R+B).

(3)

其中，R，G，B分別為點在RGB顏色空間內的r, g, b值。

2) 離地距離fe：首先基于一種改進的線性預測的濾波策略分離出地面點[13]，將地面點內插生成DEM，然后計算每個點到DEM的距離。

3) 垂直度fv：點的法向量記為np，fv為np和(0，0，1)的夾角歸一化到[0,1]的范圍內的值。

(4)

(5)

計算單點的nEGI，fe,fv特征后，體素的特征由體素內部的單點平均值計算所得。

2.2 基于圖割的點云分類

本文引入圖割算法來考慮鄰域關系以保證鄰域內的一致性。圖割算法基本思想是構建一個權重圖，每一條邊的權表示相應的能量值，然后利用最大流/最小割算法尋找圖的最小割[9]。圖割算法是通過最小化的能量函數為每一個結點賦予一個標記lp。

(6)

本文將點云分成四類，分別為屋頂，立面，植被以及地面，因此，lp∈{roof,facade,vegetation,ground}數據項由式(7)構建。

(7)

平滑項由LAB顏色空間的色差構建，如式(8)所示。

(8)

能量函數構建后，采用最大流/最小割算法[9]進行求解，得到每一個超體素的分類結果。

3 實驗與分析

本文實驗數據采用SWDC-5 系統攝取的貴陽金陽地區的航空傾斜影像，其影像地面分辨率0.1 m。航高在600～1 000 m之間，航帶間間距為500 m， 航帶內間距150 m。選取自動空三以后的的15張影像使用軟件SURE[14]生成密集點云，然后截取兩塊不同區域的點云進行實驗。圖2為實驗采用的兩組數據，點云數量分別為2 793 724和997 400。

圖2 實驗數據

3.1 分類結果

圖3為本文方法的分類結果，其中藍色為屋頂，紅色為建筑物立面，綠色為植被，黑色為地面。

圖3 分類結果

3.2 結果分析

如圖3所示，本文方法對兩組數據都得到了較好的分類結果。為了對結果進一步評價，以手工標記的分類信息作為點云的真實分類屬性進行定量分析。此外，為了進行方法對比，本文還實現了基于單點的圖割分類方法以及基于VCCS體素的圖割分類方法。在特征權重等參數相同情況下，對不同分類方法在Kappa系數、正確率、耗時方面進行了比較，結果如表1和表2所示。由表1和表2可得，與基于單點的圖割分類方法相比，基于VCCS體素的圖割分類算法在效率上有很大優勢，但由于其在攝影測量點云上的不適應，丟失了過多的信息，導致最后分類精度降低。而本文方法在時間消耗上比基于VCCS體素方法略高，但是丟失信息較少，相較于基于單點的分類方法，不僅效率較高，且分類精度也有一定的提高。

表1 數據一不同分類方法結果比較

表2 數據二不同分類方法結果比較

4 結束語

本文基于區域增長分割思想，針對質量相對較差的攝影測量點云提出一種新的點云超體素生成方法。然后引入圖割算法，將不同的超體素作為圖割算法中的結點，通過能量函數最小化得到點云的分類結果。使用兩組攝影測量點云數據進行實驗，正確率分別為87.3%和88.7%，比基于單點的分類方法分別提高2%和2.6%，而且實驗結果證明：本文方法在效率上比基于單點的分類方法要高，相比于常用的VCCS體素生成算法，本文提出的超體素生成方法雖然在效率上稍微低一些，但從分類精度角度上更適合攝影測量點云的分類。后續工作將進一步使用分類得到點云進行建筑物以及植被的三維重建，以形成具有語義信息的三維實景模型。

[1] 周曉敏,孟曉林,張雪萍,等.傾斜攝影測量的城市真三維模型構建方法[J].測繪科學,2016,41(9):159-163.

[2] 王卿,郭增長,李豪,等.多角度傾斜攝影系統三維量測方法研究[J].測繪工程,2014,23(3):10-14.

[3] 周行行,鄒崢嶸,張云生,等.顧及幾何及顏色信息的傾斜影像立面點云提取[J].國土資源遙感,2016,28(4):43-48.

[4] RAU J Y,JHAN J P,HSU Y C.Analysis of Oblique Aerial Images for Land Cover and Point Cloud Classification in an Urban Environment[J].IEEE Transactions on Geoscience & Remote Sensing,2015,53(3):1304-1319.

[5] GERKE M,XIAO J.Supervised and Unsupervised MRF Based 3D Scene Classification in Multiple View Airborne Oblique Images[C]// Isprs Conference; Cmrt13 - City Models,Roads and Traffic.2013:25-30.

[6] ACHANTA R,SHAJI A,SMITH K,et al.SLIC Superpixels Compared to State-of-the-art Superpixel Methods.[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2012,34(11):2274-2282.

[7] PAPON J,ABRAMOV A,SCHOELER M,et al.Voxel Cloud Connectivity Segmentation - Supervoxels for Point Clouds[C]// IEEE Conference on Computer Vision and Pattern Recognition.IEEE Computer Society,2013:2027-2034.

[8] SONG S,LEE H,JO S.Boundary-enhanced Supervoxel Segmentation for Sparse Outdoor LiDAR Data[J].Electronics Letters,2014,50(25):1917-1919.

[9] BOYKOV Y,VEKSLER O,ZABIH R.Fast Approximate Energy Minimization via Graph Cuts[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2001,23(11):1222-1239.

[10] GOLOVINSKIY A,FUNKHOUSER T.Min-cut Based Segmentation of Point Clouds[C]// IEEE,International Conference on Computer Vision Workshops.2009:39-46.

[11] QIN R.An Object-Based Hierarchical Method for Change Detection Using Unmanned Aerial Vehicle Images[J].Remote Sensing,2014,6(9):7911-7932.

[12] 袁紅星,吳少群,朱仁祥,等.多尺度圖割曲面重建算法[J].計算機應用研究,2013,30(6):1871-1873.

[13] 張靖,張曉君.江萬壽,等.一種改進的線性預測濾波算法[J].國土資源遙感,2011,23(1):52-56.

[14] ROTHERMEL M,WENZEL K,FRITSCH D,et al.SURE:Photogrammetric Surface Reconstruction from Imagery[C]//Proceedings LC3D Workshop,Berlin.2012,8.