結(jié)合超體素與PFCM的點云分割方法

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

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

引 言

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

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

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

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

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

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

PFCM算法的具體流程如下：

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

(2)隨機對點云聚類中心初始化，形成第1代粒子。每個粒子的當前最優(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ōu)于該粒子當前最優(yōu)位置的適應度，則將該粒子的個體最優(yōu)位置更新為當前位置。如果所有粒子中最優(yōu)位置的適應度優(yōu)于當前全局最優(yōu)位置的適應度，則更新全局最優(yōu)位置。

(3)

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

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

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

(4)

pi=pi+vi

(5)

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

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

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

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

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

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

Fig.1 SPFCM algorithm flow chart

2.1 超體素算法處理

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

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

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

(6)

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

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

(7)

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

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

2.2 超體劃分

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

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

(8)

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

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

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

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

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

3.2 實驗對比分析

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

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

Fig.2 Segmentation effect under OSD data set

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

(9)

(10)

(11)

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

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

4 結(jié) 論

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