張樹益，常建華，2*，毛仁祥，李紅旭，張露瑤

(1.南京信息工程大學(xué) 江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心，南京 210044；2.南京信息工程大學(xué) 江蘇省氣象探測與信息處理重點(diǎn)實驗室，南京 210044)

引 言

隨著激光雷達(dá)與微軟Kinect[1-2]設(shè)備的快速普及，3維點(diǎn)云技術(shù)日漸成熟，已經(jīng)廣泛應(yīng)用于3-D打印、自動駕駛、機(jī)器人、自主導(dǎo)航、工程測量、曲面重建等領(lǐng)域。3維點(diǎn)云數(shù)據(jù)處理已經(jīng)成為國內(nèi)外研究重點(diǎn)。點(diǎn)云分割是點(diǎn)云數(shù)據(jù)處理的重要基礎(chǔ)，其目的是對點(diǎn)云數(shù)據(jù)進(jìn)行有效地劃分，將具有相似屬性的點(diǎn)云劃分為同一類。目前點(diǎn)云分割方法主要分為基于邊緣的方法[3-6]、基于區(qū)域生長的方法[7-12]、 基于特征聚類的方法[13-17]以及基于機(jī)器學(xué)習(xí)的方法[18-20]。

基于邊緣分割的算法主要是找出表面特征劇烈變化的點(diǎn)，利用邊緣信息實現(xiàn)點(diǎn)云的劃分。BHANU[5]等人提出一種邊緣檢測算法，通過計算梯度、擬合3維曲線來檢測物體表面單位法向量的變化情況。DING等人[6]依據(jù)k維樹空間拓?fù)浣Y(jié)構(gòu),根據(jù)k鄰域點(diǎn)的法線的夾角閾值進(jìn)行邊界點(diǎn)提取。此類方法原理簡單且速度快，但受噪聲影響較大且無法分割復(fù)雜場景?；趨^(qū)域生長的算法主要研究點(diǎn)云之間的相似性，由初始種子點(diǎn)搜索鄰域，將達(dá)到相似條件的點(diǎn)云劃分為一類。BESL[7]在1988年首次提出區(qū)域增長算法，主要包括兩個步驟：確定種子曲面；根據(jù)相似性進(jìn)行區(qū)域生長。STEIN等人[8]在2014年提出了一種基于凹凸性的點(diǎn)云分割算法，由超體素算法對點(diǎn)云數(shù)據(jù)聚類得到超體數(shù)據(jù)，利用超體之間的凹凸性完成劃分。LIN等人[11]將超體分割問題形式化為一個子集選擇問題。利用各點(diǎn)的局部信息，提出了一種有效優(yōu)化該問題的啟發(fā)式方法。該算法原理簡單高效，可應(yīng)用于大場景分割，然而這類算法存在過分割與欠分割的缺陷?；谔卣骶垲惖姆椒ㄍㄟ^研究點(diǎn)云之間的特征關(guān)系得到點(diǎn)云之間的相似性，并對其進(jìn)行劃分。BIOSCA等人[16]提出使用無監(jiān)督聚類方法和模糊算法來分割地面激光點(diǎn)云數(shù)據(jù)，將模糊算法的參量與聚類方法相結(jié)合，得到良好的分割結(jié)果。雖然這類方法不易受到噪聲干擾，且較為穩(wěn)定，但點(diǎn)云密度的變化對其有明顯的影響。近年來，基于機(jī)器學(xué)習(xí)的分割算法發(fā)展迅速，其基于網(wǎng)絡(luò)學(xué)習(xí)點(diǎn)云數(shù)據(jù)的語義信息或其它的特征進(jìn)行分類。2016年，SHU等人[20]提出一種通過深度學(xué)習(xí)進(jìn)行無監(jiān)督的3-D形狀分割和協(xié)同分割的算法，該算法依賴Princeton分割基準(zhǔn)，可以在COSEG數(shù)據(jù)集上表現(xiàn)出良好的分割性能。盡管基于機(jī)器學(xué)習(xí)的方法可以得到較好的分割結(jié)果，但其需要花費(fèi)大量數(shù)據(jù)以及時間。

針對以上算法的不足，作者提出一種結(jié)合超體素與粒子群優(yōu)化模糊C均值(particle swarm optimization fuzzyC-means,PFCM)的聚類分割算法。該算法去除點(diǎn)云平面，由超體素算法生成超體。為便于后續(xù)的劃分，計算得到點(diǎn)云的快速點(diǎn)特征直方圖(fast point feature histogram,FPFH)，F(xiàn)PFH是點(diǎn)特征直方圖在速度上的優(yōu)化擴(kuò)展，其考慮局部范圍內(nèi)所有點(diǎn)之間的位置影響和法線關(guān)系。FPFH是描述局部范圍內(nèi)數(shù)據(jù)的幾何特征，具有位置信息不變性的特點(diǎn)。采用PFCM算法對超體進(jìn)行初步劃分，對獨(dú)立的物體組合分類結(jié)果。根據(jù)距離、曲率以及FPFH特征對粘連的點(diǎn)云進(jìn)行再劃分，彌補(bǔ)了PFCM算法對堆疊物體無法分割以及較大物體過分割的缺陷。本文中算法不僅能分割出獨(dú)立簡單的物體，對于復(fù)雜場景也有較好的表現(xiàn)。

1 粒子群優(yōu)化的模糊C均值聚類算法

模糊C均值(fuzzyC-means，F(xiàn)CM)聚類算法與k均值聚類算法類似，是一種基于劃分的聚類算法。該算法的核心思想是將具有相似屬性的點(diǎn)云劃分為一類，使被劃分到一類的點(diǎn)云之間的相似度最大，不同類之間的相似度最小。不同于與其它硬性劃分算法，F(xiàn)CM算法是模糊劃分，其并不會明確規(guī)定一個點(diǎn)一定屬于某一類。在實際聚類中，存在無法清晰地劃分出這些點(diǎn)屬于某一類的情況，因此FCM算法引入隸屬度對點(diǎn)云進(jìn)行模糊劃分，用隸屬度描述點(diǎn)云屬于不同類的不確定性，能夠客觀地反映現(xiàn)實情況,但該算法采用爬山法在局部空間內(nèi)尋找最優(yōu)解，容易陷入局部最優(yōu)，并且受初始點(diǎn)和噪聲點(diǎn)的影響較大。針對以上缺陷，采用粒子群優(yōu)化(particle swarm optimization，PSO)算法對其進(jìn)行優(yōu)化。PSO算法來源于對鳥類(魚類)捕食模型的研究，與遺傳算法相同，是一種基于群體迭代的算法。該算法使用粒子在解空間中追隨最優(yōu)粒子進(jìn)行搜索，具有參量少、操作簡單等優(yōu)勢。將兩種算法結(jié)合，可以避免FCM算法陷入局部最優(yōu)，并且分割速度更快、效率更高。

定義一個1維c列行向量A={a1,a2,…,ac}表示聚類中心，即一個粒子。其中ai表示第i類聚類。最終希望求得A的最優(yōu)解。

PFCM算法的具體流程如下：

(1)給定各個參量，包括點(diǎn)云的類別數(shù)c、算法的模糊指數(shù)m、種群規(guī)模n、學(xué)習(xí)因子e1和e2、慣性權(quán)重w以及迭代次數(shù)b。

(2)隨機(jī)對點(diǎn)云聚類中心初始化，形成第1代粒子。每個粒子的當(dāng)前最優(yōu)位置用pbest表示，種群的最優(yōu)位置用gbest表示。

(3)按照下式計算每個聚類中心的隸屬度Wij:

(1)

式中,d為歐氏距離,i為1～n的正整數(shù)，代表第i個聚類中心，j為1～c的正整數(shù)，代表第j個類，k為j中的一個數(shù)字。更新W(b)為W(b+1)。

(4)由步驟(3)得到的W(b+1)計算出c個聚類中心A(b+1)，其具體計算如下式所示,pi表示第i個粒子的位置。

(2)

(5)按照下式計算每個粒子的適應(yīng)度，如果當(dāng)前粒子的適應(yīng)度優(yōu)于該粒子當(dāng)前最優(yōu)位置的適應(yīng)度，則將該粒子的個體最優(yōu)位置更新為當(dāng)前位置。如果所有粒子中最優(yōu)位置的適應(yīng)度優(yōu)于當(dāng)前全局最優(yōu)位置的適應(yīng)度，則更新全局最優(yōu)位置。

(3)

式中,Q為常數(shù)；W為(1)式中每個聚類中心的隸屬度；A為(2)式中更新的聚類中心；J用來評判聚類效果的好壞，J越小，f(pi)越大，表明聚類效果越好。

(6)根據(jù)下面的公式對每個粒子的速度vi與位置pi進(jìn)行更新。

vi=wvi+e1R(pbest-pi)+e2R(gbest-pi)

(4)

pi=pi+vi

(5)

式中,R()表示隨機(jī)函數(shù)；vi表示為第i個粒子的速度。

(7)如果迭代次數(shù)超過設(shè)定的最大迭代次數(shù)，則停止迭代，否則轉(zhuǎn)步驟(3)，繼續(xù)迭代，直到終止。

PSO算法通過粒子在解空間中追隨最優(yōu)粒子進(jìn)行搜索，避免了FCM算法陷入局部最優(yōu)的問題。然而FCM的中心點(diǎn)是加權(quán)計算出來的，其只適用于均勻分布的點(diǎn)云，因此對于堆疊的物體，其不能準(zhǔn)確分割，會將其混淆。且對于過大物體，會造成不合理的過分割現(xiàn)象。

2 結(jié)合超體素與PFCM的點(diǎn)云分割算法

針對PFCM算法存在的問題，作者提出了一種結(jié)合超體素與粒子群優(yōu)化模糊聚類的點(diǎn)云分割算法(supervoxel particle swarm optimization fuzzyC-means,SPFCM)。該算法對粘連點(diǎn)云進(jìn)行了再劃分，解決了PFCM算法對于堆疊物體無法準(zhǔn)確分割，以及對較大物體造成不合理的過分割現(xiàn)象。再劃分操作增加了一定的計算量，所以在此基礎(chǔ)上，結(jié)合了超體素算法，將獲得的超體素作為后續(xù)劃分的輸入數(shù)據(jù)，來達(dá)到降低計算復(fù)雜度、去除噪聲和雜點(diǎn)、提高分割精度的目的。

SPFCM算法首先利用超體素算法，根據(jù)點(diǎn)云的空間距離、曲率特征以及FPFH特征共37維特征劃分點(diǎn)云得到超體。在后續(xù)的劃分中使用PFCM算法對超體進(jìn)行初劃分，對粘連點(diǎn)云根據(jù)歐氏距離、曲率方差、法向量夾角以及FPFH的特征均差值進(jìn)行再劃分，算法流程圖如圖1所示。圖中，D為中心點(diǎn)特征距離。

Fig.1 SPFCM algorithm flow chart

2.1 超體素算法處理

獲得點(diǎn)云后，由于點(diǎn)云的平面會干擾超體素算法分割點(diǎn)云的準(zhǔn)確性，因此，需要消除點(diǎn)云平面。作者使用隨機(jī)采樣一致性算法檢測并去除平面，該算法由3個點(diǎn)確定1個平面，并檢測該平面的點(diǎn)云數(shù)量。循環(huán)以上步驟，把點(diǎn)云數(shù)量最多的平面當(dāng)做整個點(diǎn)云的平面，并去除該平面。使用超體素算法分割去除平面后的點(diǎn)云，超體素算法的目的不是準(zhǔn)確地分割點(diǎn)云，而是對點(diǎn)云實行過分割，利用點(diǎn)云的空間距離、曲率特征以及FPFH特征共37維特征來衡量點(diǎn)云之間的相似性，并將相似的點(diǎn)云進(jìn)行聚類。本質(zhì)上這種方法是對局部點(diǎn)云的一種總結(jié)，點(diǎn)云相似的部分會被自動的分割成一塊，有利于后續(xù)識別工作，能夠降低計算復(fù)雜度，去除噪聲且提高分割精度。由于點(diǎn)云與圖像不同，其不存在像素鄰接關(guān)系，因此，在使用超體素算法之前，利用八叉樹對點(diǎn)云進(jìn)行體素化處理。

超體素算法具體步驟如下所示：

(1)定義向量F={x,y,z,s,H1,H2,H3,…,H33}表示37維特征，其中x,y,z表示點(diǎn)云的空間坐標(biāo)，s表示點(diǎn)云的曲率，H為點(diǎn)云的快速直方圖。FPFH是PFH在速度上的優(yōu)化擴(kuò)展，具有姿態(tài)不變性的局部幾何特征，其計算過程為：計算中心點(diǎn)O與其鄰域點(diǎn)Ok法線之間的角度值表示法線偏差，從而得到簡化的點(diǎn)特征直方圖(simplified point feature histogram，SPFH),再查找中心點(diǎn)的所有鄰域點(diǎn)的鄰域范圍并計算出其鄰域范圍內(nèi)的SPFH，由此可以計算出中心點(diǎn)的FPFH，其計算如下式所示：

(6)

式中，H表示FPFH,H′表示SPFH。

(2)得到以上特征后，計算出中心點(diǎn)的特征距離，如下式所示：

(7)

式中,Ds為空間距離；ws為Ds的權(quán)重；Dc為體素之間的曲率變化值；wc為Dc的權(quán)重；Dh為FPFH的空間距離；wh為Dh的權(quán)重,Rs為空間分辨率。

(3)以超體素中心向外進(jìn)行迭代，利用(7)式計算出鄰近體素與超體素中心的特征距離，如果特征距離較小，則證明它們之間是相似的，標(biāo)記該體素屬于此超體素，直到達(dá)到每個超體素的搜索體積的邊緣或者沒有其它鄰近點(diǎn)可以遍歷。

2.2 超體劃分

得到超體后，使用PFCM算法對點(diǎn)云進(jìn)行初步劃分，與一般處理流程不同，本文中PFCM算法劃分的對象是超體素算法生成的超體，根據(jù)超體間的相似性對其進(jìn)行劃分。具體劃分原理已經(jīng)介紹，不再闡述。

由于PFCM算法對堆疊的物體無法準(zhǔn)確分割，所以需要再劃分。若聚類中心距離小于設(shè)定的閾值，則將它們劃分為同一類，組合分類結(jié)果后加入完成組。若聚類中心距離大于閾值，則需要判斷點(diǎn)云是否粘連。對于沒有任何連通點(diǎn)、完全無關(guān)聯(lián)的點(diǎn)云，將其劃分為一類，并加入到完成組。對于粘連的點(diǎn)云，首先將其合并，以便于再劃分，根據(jù)法向量夾角、FPFH、距離尋找物體頂點(diǎn)的超體，若頂點(diǎn)超體滿足同類條件，則將其加入完成組，否則加入未完成組，其判斷條件如下式所示：

(8)

式中,d為歐氏距離,d′為超體中心點(diǎn)與相鄰超體最近點(diǎn)的歐氏距離,S為曲率方差,θ為法向量夾角,Δ為FPFH的特征均差值。

所有頂點(diǎn)的超體劃分結(jié)束后，根據(jù)特征尋找這些頂點(diǎn)下面的中間超體，并根據(jù)(8)式判斷這些中間超體是否和已經(jīng)劃分完的頂點(diǎn)超體屬于同類，如果滿足同類條件，則把中間超體加入完成組，并組合成同一類輸出，不滿足同類條件則把中間超體加入剩余組，再檢測剩余組是否為空，如果為空則結(jié)束分割，否則循環(huán)以上步驟，直到迭代次數(shù)達(dá)到閾值。整個流程的原理是模仿人類的認(rèn)知方式，由頂點(diǎn)開始劃分，再根據(jù)其它點(diǎn)云和頂點(diǎn)的關(guān)系進(jìn)行劃分組合。

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)集

本文中使用的數(shù)據(jù)均來自于object segmentation database(OSD-v0.2)數(shù)據(jù)集。該數(shù)據(jù)集是由RICHTSFELD等人[21]在2012年建立的一個用于對室內(nèi)場景點(diǎn)云進(jìn)行分割的一個數(shù)據(jù)集。該數(shù)據(jù)集的每組數(shù)據(jù)都是通過對桌面上雜亂無章的物體進(jìn)行掃描獲得的，共有107組數(shù)據(jù)，其中學(xué)習(xí)組43組，測試組64組，測試組中數(shù)據(jù)從復(fù)雜程度上分為簡單的單個盒子測試、堆疊箱子測試、遮擋物體測試、對象測試、混合對象測試以及復(fù)雜場景測試6個難度等級的測試組。

3.2 實驗對比分析

為了驗證本算法的有效性以及分割的效率，將本文中的算法與PFCM算法、局部凸鏈接打包(locally convex connected patches,LCCP)算法[8]以及改進(jìn)的區(qū)域生長算法(region growth，RG)[9]進(jìn)行對比。

如圖2可知，PFCM算法分割獨(dú)立的物體，其分割效果尚可，但對堆疊或者結(jié)構(gòu)復(fù)雜的物體分割效果較差，容易混淆物體，產(chǎn)生過分割與欠分割現(xiàn)象，并且當(dāng)物體體積較大時，容易將物體分為兩類。例如在對第1組數(shù)據(jù)進(jìn)行分割時，PFCM算法產(chǎn)生了混淆現(xiàn)象，其分割出的單個物體包含其它物體的點(diǎn)云，將同一個物體分為多個物體，由此可見PFCM算法對堆疊物體、較大物體不能有效地分割。LCCP算法是基于凹凸性對點(diǎn)云進(jìn)行分割，其對于均勻平滑的區(qū)域有著良好的表現(xiàn)，然而分割線性目標(biāo)時會出現(xiàn)過分割現(xiàn)象，例如第1組數(shù)據(jù)以及第3組數(shù)據(jù)出現(xiàn)了此現(xiàn)象。RG算法基于曲率以及法向量對點(diǎn)云進(jìn)行劃分，存在著過分割與欠分割的現(xiàn)象。本文中的算法不僅能夠較好地分割出獨(dú)立的物體，而且對堆疊的物體也能進(jìn)行有效分割，可以避免對多個堆疊物體分割時產(chǎn)生的混淆現(xiàn)象。

Fig.2 Segmentation effect under OSD data set

為了更加客觀地評估，本文中使用了準(zhǔn)確率P、查全率R以及綜合了P與R的F評分，其具體計算如下所示：

(9)

(10)

(11)

式中,T表示算法分割正確的數(shù)據(jù),U是算法未分割出正確的數(shù)據(jù),V是算法未分割出錯誤的數(shù)據(jù)。

本文中抽取了10組數(shù)據(jù)進(jìn)行對比，結(jié)果如圖3所示。由圖中可以看出,相較于其它3種算法，本文中的算法波動較小，魯棒性較好。為了更加直觀地突出本文中的算法的優(yōu)越性，利用OSD-v0.2數(shù)據(jù)集評估本文中的算法、PFCM算法、LCCP算法以及RG算法的性能，其結(jié)果如表1所示。由于本文中算法解決了PFCM算法對堆疊物體以及復(fù)雜形狀物體無法分割的問題，因此在準(zhǔn)確率和查全率方面有了大幅度提升，準(zhǔn)確率為86%，查全率為83%，相較于未改進(jìn)的PFCM算法，分別提升了22%和16%。與近期提出的LCCP

Fig.3 Comparison of accuracy of different groups of data

Table 1 Comparison of the four algorithms on the OSD-v0.2 data set

算法和RG算法相比，準(zhǔn)確率和查全率至少提升了12%和8%。

4 結(jié) 論

針對PFCM算法對堆疊物體無法劃分，較大體積物體容易劃分為兩類的問題，結(jié)合超體素算法提出了SPFCM算法，對粘連的物體進(jìn)行再劃分，克服了PFCM算法的缺陷，并保留了PFCM算法參量少、操作簡單的優(yōu)點(diǎn)。該算法不僅能夠準(zhǔn)確地分割簡單的物體，在面對復(fù)雜物體時，也有著良好的表現(xiàn)。同時該算法很好地平衡了準(zhǔn)確率與速度。在OSD-v0.2數(shù)據(jù)集上與PFCM算法、LCCP算法以及RG算法進(jìn)行對比，實驗結(jié)果表明，本文中的算法的分割準(zhǔn)確率遠(yuǎn)高于PFCM算法，提高了22%，相較于LCCP算法以及RG算法在有著更快速度的同時，準(zhǔn)確率至少提高了12%。