基于KFCM的三維點云精簡算法

林 楷，王威娜,2*

(1.吉林化工學院 信息與控制工程學院，吉林 吉林 132022；2.吉林化工學院 理學院，吉林 吉林 132022)

近年來，隨著計算機視覺相關產業的蓬勃發展，三維點云重構逐漸被應用在自動駕駛[1]、智能工業[2]、文物修復[3]等各個領域.在點云信息的獲取過程中，傳統的點云采集設備采用非接觸的方式以激光雷達、TOF相機等對現實世界中的物理模型進行掃描，不可避免地產生大量的噪音、冗余信息點，對后續點云重構步驟產生較大影響.因此，選擇合適的算法對點云進行預處理顯得尤為重要.

在精簡算法的研究中，較為主流的是包圍盒法、均勻采樣法和曲率采樣法.Lee等[4]利用形態算子與點云結構相結合將點云進行精簡化處理，結果保證了初始信息點的基本結構特征，但此方法在遇到具有干擾的噪聲數據集時，魯棒性較低，易造成輸出點云的特征缺失.Wang等[5]通過處理均勻采樣點云數據來精簡點云模型，在不同數據集上取得了良好的結果，但當點云數據特征不夠明顯或點云數據較為稀疏時會產生點云空洞.王玉國等[6]將點云的曲率信息作為保留點云的約束條件，根據曲率變化程度的不同對不同密度的點云數據進行保留，此算法缺陷在于對點云的細節保留度不足，且曲率計算造成了算法較高的時間復雜度.

針對上述精簡算法出現的問題，本文提出一種基于核模糊C均值(Kernel Fuzzy C Means,KFCM)的點云精簡算法.將模糊聚類的思想與點云精簡相融合，利用三維點云數據作為輸入樣本，通過迭代求解樣本數據集的聚類中心，并以此聚類中心描述點云結構.在此基礎上，算法可通過調節聚類個數靈活輸出不同精簡程度的點云信息，以適應后續配準工作的需求.該算法實現原理簡單，在良好保留點云細節特征的同時達到簡化點云的目的，提升后續點云的配準效率.

1 核模糊C均值算法

KFCM[7]是一種改進的模糊C均值(Fuzzy C Means,FCM)聚類算法.FCM[8]聚類模型可被描述為以下步驟：(1) 給定初始隸屬度矩陣；(2) 更新模糊聚類中心；(3) 更新隸屬度矩陣.循環執行上述步驟(2)和(3)，直至利用加權誤差平方和構造的目標函數收斂，輸出最終的聚類中心，完成聚類任務.

KFCM通過核函數將原始空間中的點映射到特征空間中，算法首先設數據集X∈Rs，定義其到特征空間的映射為：

f(x)=y.

(1)

G(x,x′)=G(y,y′)=〈f(x),f(x′)〉.

(2)

其中x、x′∈X為s維向量；G為計算兩者的歐式內積，進而通過核函數定義FCM中的距離函數，定義目標函數如下：

(3)

其中H代表范數的處理方式；K(xj,vi)代表高斯徑向基函數，其形式表示為：

(4)

U=[uij]代表隸屬度矩陣；V=[vi]為聚類中心，其更新方式為：

(5)

(6)

式中，m為模糊指數；xj為聚類信息點.循環執行上述步驟直至目標函數達到收斂，聚類的過程如圖1所示.

圖1 聚類示意圖

在聚類分配過程中，可利用之前獲得的聚類信息將數據進行聚類分配，待分配數據可根據第s-1次聚類分配獲得其對應的聚類中心.在得到分配區域后，通過隸屬度矩陣估計數據點對應的新的聚類中心，即可得到s次迭代所需的隸屬度矩陣，進而更新聚類分配.在分配的過程中，同一數據點可能在不同迭代次數時被分配于不同的聚類中心，隨著目標函數的逐漸收斂，其函數值逐漸減小，直至聚類過程結束.

2 基于 KFCM算法的點云精簡方法

2.1 基于 KFCM算法的點云精簡方法

提出的基于KFCM的點云精簡算法首先將未精簡的點云數據作為輸入樣本，通過核函數將初始點云數據集在特征空間中進行描述，利用線性函數對稠密點云數據進行劃分.聚類分配的步驟中，聚類中心構成的點云信息可對整體點云信息進行描述，通過本次迭代的聚類中心計算下次迭代所需隸屬度矩陣，最后將聚類中心作為輸出點集樣本數據，算法流程如圖2所示.

圖2 算法流程圖

輸出后的點集極大地減少了原點樣本的數據量，達到了優化后續配準算法輸入信息的目的.在此基礎上，將模糊聚類中心個數h為精簡后三維點云數據量的描述符，利用保留點與初始信息點個數的比值表示精簡率，即可通過調節h的數值對精簡后點云疏密程度進行控制，以適應后續配準工作的需求.

綜上所述，基于KFCM的三維點云精簡算法具體執行步驟為：

步驟1：利用徑向基函數將三維點云數據映射到高維空間；

步驟2：提供聚類個數，初始化隸屬度矩陣；

步驟3：根據數據分布情況進行聚類劃分，獲得初始聚類中心

(7)

式中Pij用于描述第i個點集中第j個信息點；uij表示其信息點的隸屬度矩陣；m為模糊系數，默認參數值為2；

步驟4：更新隸屬度矩陣

(8)

步驟5：循環更新聚類中心與隸屬度矩陣，直至迭代達到預設次數，將聚類中心作為精簡后數據輸出.

2.2 多視角三維點云配準

三維點云的配準是指將不同視角的三維點云數據利用剛性參數變換使其同步至同一坐標系下的更新過程，三維點云配準示意圖如圖3所示.

圖3 三維配準示意圖

Zhu等[9]利用聚類思想描述三維點云模型從而恢復對齊的三維點云結構，算法首先給定初始變換參數，再利用下采樣對三維點云數據進行精簡處理，通過K均值聚類選出聚類中心.將整體點云對齊到由聚類中心組成的分辨率較低的模型上，利用此對應關系進行點云的旋轉與平移變換，以求在迭代更新聚類中心的同時優化剛性變換參數，具體執行步驟如下：

步驟1：更新聚類.

a.設聚類數為K，對精簡后點云進行隨機采樣，選出K個聚類中心{v1,v2,…,vK}；

b.根據歐氏距離最短的原則將每個點分配到相應類中；

c.更新聚類中心：

(9)

其中Qij為點Pij的類標；N為信息點個數；M為點集個數.

步驟2：更新剛性變換參數(R,t).

a.計算第i個視圖的剛性變換參數(R,t):

(10)

在剛性變換參數的求解過程中，采用奇異值分解(SVD)[10]方法，求解源點云與目標點云的加權中心，在去中心化操作后計算其協方差矩陣W，奇異值分解此矩陣即可得到U、V兩個酉矩陣，則旋轉矩陣R可被表示為：

R=UVT.

(11)

再據此估計平移向量t的具體數值.

b.利用求得的R、t對各個視圖進行變換：

(12)

基于K均值聚類的三維點云配準方法在進行源點云與目標點云的特征提取過程中較為簡單地利用下采樣對不同視角點云進行預處理，在一定程度上降低了算法的魯棒性.實驗過程中，利用基于K均值聚類的三維點云配準方法對本文提出的算法進行了驗證，實驗表明通過基于KFCM的三維點云精簡算法對原始稠密三維點云數據進行預處理，可減少噪聲與冗余信息對配準算法的影響、彌補K均值聚類對噪聲敏感的不足，提升了算法的準確性.

3 實驗結果與分析

為驗證算法有效性，實驗具體分為兩部分：(1)不同參數下的點云精簡測試；(2)與后續配準算法的適用性實驗.實驗設備為64位Windows操作系統，CPU頻率為2.40GHz，運行內存為8GB的電腦，使用的編程軟件為Matlab.使用數據集分別為ModeNet40[11]以及斯坦福大學數據庫[12].

3.1 不同參數下的點云精簡測試

為驗證KFCM的點云精簡方法的有效性，首先對Airplane模型進行精簡實驗，實驗將初始點云利用不同精簡參數處理后結果如圖4所示.

圖4 不同精簡參數下的Airplane模型

實驗結果顯示，輸出點云樣本數據隨著精簡參數h的增加而逐漸減小，但精度與特征信息并未損失.由此可通過改變聚類的參數用以控制精簡后信息點的密度，靈活調節三維點云的精簡率.

與此同時為驗證算法在處理含噪點云時的濾波效果與精簡后點云保留程度，對Flowerpot模型進行測試，在原模型中添加2%的隨機噪聲，實驗中遺傳算法的步長設置為20，結果如圖5所示.

圖5 不同精簡參數下的Flowerpot模型

結果表明在精簡比率為12.5%與5%的情況下，算法有效地將含噪點云去除了所有噪聲點，并有效地對原點集進行了稀疏，點云部位輪廓清晰.模型預處理前點云稠密，經過算法精簡處理后各部位細節明顯，很好地保留了原模型的特征.

在實驗中，為了更直觀地描述算法對三維點云模型整體結構的細節保留程度，表1給出了Airplane及Flowerpot模型在精簡率為12.5%情況下的精簡誤差與下采樣精簡方法的精度對比.實驗以不同鄰域劃分范圍的平均法向量作為衡量標準，表中x_normal、y_normal、z_normal分別表示模型在x、y、z軸方向的平均法向量誤差，其中最優結果已用黑體標出.

表1 精度誤差對比

由表1可知，提出的算法在不同鄰域覆蓋情況下的不同方向法向量誤差較低，相比于下采樣精簡方法，基于KFCM的點云精簡算法在各方向上點云結構信息保存良好，具有更高的準確性，并給出在不同精簡參數下，Airplane模型保持率與點云平均密度變化的對照表2.

表2 平均密度對照表

如表2所示，在聚類參數由1至90的變化過程中，三維點云數據保持率不斷降低，實驗點云模型逐漸稀疏，點云間的平均間距隨之增加.由此可見，在算法的實現過程中，可通過調節精簡參數h以靈活控制輸出點云的疏密程度.

3.2 精簡后配準結果測試

為驗證精簡后的點云數據對后續配準任務的適用性，利用基于K均值聚類的點云配準方法與ICP[13]算法對其進行測試，并給出待配準點云的具體信息，如表3所示.

表3 待配準點云信息

3.2.1 基于K均值聚類的點云配準方法

在驗證過程中，實驗選取Bunny、Buddha模型進行效果測試，在給定初始變換矩陣后，使用基于KFCM算法的點云精簡方法的輸出結果作為初始聚類中心的描述符，實驗中迭代次數設置為200，算法運行迭代次數小于預設次數之前，不斷迭代，直至收斂.圖6和圖7為Bunny、Buddha模型經過KFCM精簡后利用基于K均值聚類的點云配準方法配準前后的對比圖.

圖6 Bunny配準結果

圖7 Buddha配準結果

如圖6和7所示，精簡后的多站點云配準效果良好，經配準的點云邊緣清晰、特征部位明顯.Buddha截面圖可見佛像的身體與底座部位未對齊的部分經剛性變換后得到了完美的還原，初始點云截面圖層次較為混亂，配準處理后的佛像模型邊界平滑、結構保存良好.Bunny中雙耳、腹部以及背部未對齊的部分配準精確.截面圖可見模型軀體重影部分配準效果明顯.由此可見，基于 KFCM算法的點云精簡方法可較好地適應基于聚類的三維點云模型精確配準任務需求，算法可移植性較高.

3.2.2 ICP配準效果測試

在ICP配準效果測試實驗中，選取精簡率為12.5%的Guitar以及Flowerpot模型進行適應性測試，在給定初始的變換矩陣后，進行最近點迭代估計，圖8和圖9給出配準中的運行時間、迭代次數與配準誤差.

迭代次數n圖8 Guitar ICP配準結果

圖9 Flowerpot ICP配準結果

如圖8和圖9所示，針對不同模型，精簡后的三維點云數據可良好地適應迭代最近點算法的處理步驟，在給定初始誤差的情況下可對原模型進行精確的配準處理.待配準Guitar模型得到較好的擬合，Flowerpot模型配準后邊緣整齊、細節特征配準精確，迭代均方根誤均小于0.05 m.在點云結構保存方面：迭代最近點算法是基于點云特征的精配準算法，迭代收斂次數在一定程度上反映了點云模型對整體結構的描述程度，兩模型5～10次迭代后即可達到收斂，可見基于 KFCM算法的點云精簡方法可較好地保持源點云的細節特征.在時效性方面：經過精簡后的點云數據處理速度較快,算法耗時不足0.1 s.

綜上所述，本文提出的基于 KFCM算法的點云精簡方法能較好地處理點云精簡任務，在便捷調節點云精簡率的同時，具有良好的特征保留性能，提升了后續點云處理任務的效率，故此方法具有較高的實際應用價值.

4 結 論

基于核模糊C均值聚類的思想提出一種針對冗余點云的精簡方法，在處理數據量較大的稠密點云數據時具有良好的性能，該方法可在減少點云數據量的同時對模型的細節特征進行保留，且可通過聚類參數h對輸出點云的分辨率進行調節.實驗結果表明，利用基于K均值聚類算法的點云配準方法與ICP配準算法對精簡后的點云進行配準測試時，精簡后的點云數據可提升配準效率，且得到的點云模型清晰、邊緣光滑、數據點分布均勻.綜上所述，提出算法具有較高的實際應用價值.

本文算法雖然可以有效地處理三維點云數據的精簡與去噪任務，但存在著聚類參數的選擇不夠系統、收斂條件設置不夠精確等問題，如何系統地選取聚類數量以精確地設置收斂條件將是未來研究的重點.