基于K-means聚類的三維點云分類

馬京暉，潘 巍，王 茹

首都師范大學 信息工程學院，北京 100048

1 引言

圖像分類是人工智能里常見的圖像處理，在模式識別領域也至關重要[1]。隨著深度學習的發展，對圖像的分類也從二維圖像轉移到了三維圖像，但由于三維圖像受到分辨率和計算成本的影響，提高分類準確率仍然具有很大的難度。

三維圖像的分類一般分為三維幾何變換分類和三維點云分類等，其中以點云分類最為常見。點云數據作為基礎的三維模型，其特點是具有稀疏性和無序性[2]。傳統點云分類[3-6]的方法是利用點云的部分屬性進行手工提取特征，但方法精度不高，且耗時長。隨著深度學習的興起，人們利用深度神經網絡對點云數據進行分類，減少了工作量，并取得更好的效果。早期的點云分類是將不規則分布的點云數據轉化為規則分布的體素表示，并在體素中使用三維卷積進行特征提取。2015年，Maturana D等人提出的VoxNet[7]是最早在體素網格輸入的情況下在物體分類任務上取得優異表現的深度學習方法。VoxNet 采用概率占用網格的方法，其中的每個體素都包含了該體素在空間中被占用的概率。這種方法解決了點云的無序性，但對點云旋轉不魯棒且計算量龐大。此后，體素算法[8-10]不斷改進，但仍存在運算復雜度高的問題。2015 年，Chen X 等人提出3Dop 算法[11]，將點云數據投影到透視圖中，然后應用基于二維圖像的技術提取特征，該方法由于點云數據的稀疏性，使得投影到透視圖上的點云數不均，分類準確率有待提高。2017年，Klokov R等人提出Kd-Net算法[12]，采用分層特征提取，新結構根據Kd 樹對點云進行細分并乘法變換。但Kd-Net 算法有一些限制，對旋轉和噪聲同樣很敏感。2017 年，Qi 等人提出直接處理點云數據的深度學習模型PointNet[13]。該算法基于均勻采樣的點云進行訓練，利用空間變換矩陣T-Net解決了點云旋轉問題，通過maxpooling 解決點云無序性問題。但PointNet 算法的缺點是均勻采樣點云會降低點云分類的準確率，且算法只考慮了全局特征，沒有處理局部特征提取。2018年，該團隊針對此問題，又提出了PointNet++網絡[14]，構建了類金字塔特征聚合方案，但分組提取特征并沒有體現點云的空間分布，且處理大規模點云數據時會造成計算量龐大。

綜上，本文在原始的Pointnet網絡模型上進行改進，提出了一種基于K-means 聚類的三維點云分類算法。該算法首先通過點云采樣對原始點云數據進行預處理，保留關鍵點云。當點云數據密集時，去除冗余部分以方便提高后續處理速度；當點云數據稀疏時則進行三角形插值操作，以便更好地描述物體輪廓，提高分類精度。然后，針對PointNet 沒有考慮局部特征問題，先對點云數據進行K-means 聚類操作，之后并行通過PointNet 網絡進行特征提取，該方法可體現點云空間中的分布的特性。本文算法在ModelNet10/40 數據集[15]上進行實驗，結果表明，本文改進的PointNet 網絡不僅同時超越了PointNet及PointNet++算法，相對于VoxNet和Kd-Net算法也有很好的性能，且減少了訓練時間。

2 網絡結構介紹

2.1 PointNet結構介紹

PointNet 算法分類結構如圖1 所示，輸入均勻采樣后的n個點，通過空間變換矩陣T-Net，對齊輸入點云，進行規范化處理。然后通過感知機進行點云的特征提取，升維到64，同樣經過T-Net網絡，對齊輸入特征。隨后再次特征提取，之后通過最大池化層對信息進行融合生成全局特征。最后，點云生成的1 024 維特征通過感知機進行學習，k是最后一層的輸出數量，代表分類的類別，每個類別會對應對于點云的分類得分。

PointNet算法的優點：

（1）以原始點云直接作為輸入，保留了點云的空間特征；

（2）通過T-Net網絡解決了旋轉問題，用損失函數來對旋轉矩陣進行調整，并把輸入點云數據旋轉到一個更有利于分類的角度；

（3）通過maxpooling 解決點云無序性問題，神經網絡對每個點進行了一定程度的特征提取之后，maxpooling可以對整體點云提取出全局特征，在降低維度的同時保留顯著的特征。

但PointNet只考慮了全局特征，沒有處理局部特征提取，降低了分類的準確性。PointNet++網絡在其基礎上進行分層提取，解決了局部特征的問題，其分類結構流程圖如圖2所示。由圖可知，進行多次特征提取會導致計算量龐大、運行時間過長。

圖2 PointNet++結構流程圖

圖1 PointNet網絡結構

2.2 本文算法結構介紹

本文算法保留了PointNet算法的T-Net網絡和最大池化的優點，采用分層的思想，利用聚類算法并行特征提取，以避免運算復雜度過大的問題。

首先對點云數據進行預處理，減少后續計算量。在PointNet 網絡的基礎上增添了K-means 聚類分析算法，對預處理后的點云數據進行K-means聚類處理，聚類為K個不同的類，分別進行PointNet 網絡的特征提取，過程為并行運算關系，不增加PointNet網絡的計算量。通過maxpooling全局特征處理，最后通過全連接網絡得到分類類別。

改進后的PointNet 網絡模型提取了點云的局部特征，克服了原始網絡細節的錯誤，提高了分類的準確性。由于過程中并行進行特征提取，因此避免了PointNet++網絡多次提取特征的問題，在保證準確率的基礎上，大大降低訓練時間。

本文算法流程圖如圖3所示。

圖3 本文算法流程圖

2.2.1 點云預處理

原始數據集中點云數據存在疏密不均勻的現象，因此要對點云進行預處理。PointNet 算法是對點云進行均值采樣處理，這樣可能會造成點云分類的準確率下降。為了更好地處理數據，本文算法預處理采用不同方法：當點云數據過于密集時，去除冗余部分以減少點云數量，加快運行時間。當點云數據過于稀疏時則進行插值處理，提高分類精度。具體流程圖如圖4所示。

圖4 篩選點云算法流程圖

（1）處理點云集中問題

首先對點云數據進行等間隔采樣，去除冗余的點云數據，然后判斷點云數量是否大于T1。由于對比Point-Net算法網絡，因此閾值T1設置為2 048。

當隔采樣后的點云數量大于閾值T1時，計算當前點云數量與閾值的差值，并依次計算當前點云(xs,ys,zs)到其他點云的距離，這里采用歐式距離D1，公式（1）為：

假設半徑為R，按照半徑內點云數量排序，最大數量與差值進行比較，若大于等于差值，則去除差值個數的點云，保留其他點云；若小于則保留當前點，去除半徑內全部點云，然后再進行以上操作，直至等于閾值輸出處理后的數據。

該方法可以去除冗余的點云數據，對于密度高的地方適當減少，實驗示例如圖5 所示，圖5（a）為原始點云圖，點云數為90 714，圖5（b）為篩選后點云圖，點云為2 048。此方法可以大大減少點云密集部分，且保持原來的形態。

圖5 點云篩選對比圖

（2）處理點云稀疏問題

點云數據具有稀疏性，在數據集中有點云數據過于稀疏的情況，如圖6所示，點云數量過于稀少，無法進行分類。

圖6 稀疏點云示意圖

為了更加準確地進行分類，需要對原始點云數據進行插值，本文采用三角形內部線性插值，示意圖如圖7所示。

圖7 三角形插值示意圖

假設三角形頂點為P1,P2,P3，在三角形內部插值點P，存在三個自由度，即使得：

其中u+v+w=1。實驗的結果如圖8 所示，對稀疏的點云進行了插值，點云分布均勻。實驗表明該方法可以彌補點云稀疏的缺點，使點云均勻分布。

圖8 稀疏點云插值后結果示意圖

2.2.2 基于K-means聚類的三維點云分類

為了解決PointNet算法沒有局部特征提取的問題，本文在點云預處理環節之后，對點云進行了K-means聚類，使得通過聚類的結果更有效地利用點云的局部特征，同時可以解決PointNet++網絡對點云分層次提取特征時重疊的問題，從而提高分類的準確率?；贙-means聚類算法的點云分類網絡如圖9所示。

圖9 基于K-means聚類算法的點云分類網絡

圖9 中網絡輸入預處理后的2 048 個點，通過K-means 聚類算法，將點云數據分為K類，每類點云數不同，根據K-means 算法每類的點云數不會相差很大，不會影響后續的計算。然后并行通過PointNet 網絡進行特征提取，體現局部構造。通過最大池化層對信息進行融合生成全局特征，通過感知機進行學習，輸出分類類別s。

（1）K-means聚類算法

K-means 算法是一種十分經典的迭代求解的聚類分析算法[16]，通過隨機產生K個對象作為初始的聚類中心，然后計算每一個對象和各個聚類中心之間的距離，把它分配給距離最近的聚類中心。每輪聚類結束后，會根據聚類新的對象而重新計算聚類中心，直到聚類中心不再變化為止。

三維的K-means聚類算法，輸入點云數據{p1,p2,…,pn}，對于點云數據pi(1 ≤i≤n)，用 {μ1,μ2,…,μk}分別表示K個聚類中心，用{c(1),c(2),…,c(k)}來存儲與第i個點云數據最近的聚類中心的索引。算法步驟如下所示：

算法1K-means聚類算法

輸入：聚類個數K，點云數據

輸出：每個聚類中所有元素

步驟1隨機產生K個種子，且保證種子不重疊。

步驟2根據公式（3），計算點云到K個種子的距離，選取距離最近的種子代表類：

步驟3根據公式（4），重新計算該類的種子中心：

步驟4遍歷所有點云，重復步驟2、步驟3，直至種子中心不再變化。

K-means 聚類算法可視化結果如圖10 所示。本例中，K-means 聚類算法選取K=5，將點云數據分為5類，后續將并行通過PointNet結構提取特征。

圖10 K-means聚類可視化結果，本例為5類

（2）K值的選擇

K-means算法中對K值的選擇使用“手肘法”[17]，通過計算SSE值可以畫出K-SSE曲線，找到拐點確定最佳K值，示意圖如圖11所示。SSE值的計算方式就是每個聚類的點到它們質心的距離的平方。

隨著K值的增大，樣本劃分會更加精細，每個簇的聚合程度會逐漸提高，那么誤差平方和SSE自然會逐漸變小。當K值小于真實聚類數時，由于K值的增大會大幅增加每個簇的聚合程度，故SSE的下降幅度會很大，而當K值到達真實聚類數時，再增加K值所得到的聚合程度回報會迅速變小，所以SSE的下降幅度會驟減，然后隨著K值的繼續增大而趨于平緩。找出下降途中的拐點，即可確定K值。本例中，拐點為K=4時是本數據集最佳的K值選擇。

圖11 K-SSE曲線示意圖

本文算法由于點云數據量大，沒有使用手肘法快速找到最優K值，但實驗中對比了不同K值對三維點云分類的影響，具體情況將在3.2.2節中進行分析。

3 實驗及結果分析

為了評估算法的分類效果，本文在ModelNet10/ModelNet40 數據集上分別進行了訓練和測試。Model-Net40 數據集包括了用三角形網絡表示的12 311 個CAD 模型，其中有9 843 個訓練數據和2 468 個測試數據。同樣，ModelNet10 有2 468 個訓練樣本和909 個測試樣本。原始ModelNet 數據集提供了代表的CAD 模型的頂點和面。

3.1 實驗條件

實驗配置如表1。

表1 實驗配置

3.2 實驗結果對比與分析

在ModelNet 數據集上以相同的條件進行實驗，記錄不同算法的運行結果和時間，進行比較和分析，本文算法準確率為平均準確率mAP。

3.2.1 準確率比較

本文將模型在ModelNet10/ModelNet40數據集上的分類準確率與前文提及的VoxNet、PointNet、PointNet++和Kd-Net四種模型進行對比，結果如表2所示。

可以發現，與其他四種分類模型相比，本文在輸入點云數上除與PointNet 算法均值采樣后點云數據相同外，輸入點云數量少于其他算法，大大減少了計算量。本文方法1是將點云預處理后數據直接輸入PointNet網絡，在ModelNet10/40數據集上分類準確率相對提升，說明預處理的插值處理，可以提高分類精度。方法2是點云預處理后進行K-means 聚類處理，并行通過PointNet網絡進行特征提取，其分類準確率都高于其他四種算法，在ModelNet40數據集上基于K-means聚類的三維點云分類算法模型比PointNet 高3.4%，比PointNet++高0.7%。對比方法1 和2 可看出，本文算法點云預處理是減少點云數量，提高運算速率，對準確率的影響不大，主要是K-means聚類分析影響最終的分類準確率。

表2 分類準確率

3.2.2 改變K值準確率比較

為了測試K值不同對模型分類結果的影響，本文在ModelNet10/40 數據集下對比了不同K值下算法的分類準確率，在實驗中K值的選擇從2 到6，結果如圖12所示。

圖12 不同K 值下分類準確率的影響

由圖12 可知，隨著K值的增大，準確率在提高，可以看出ModelNet10 和ModelNet40 的整體趨勢一致，在數據集中當K=5 時準確率最高，之后隨著K值增大準確率開始下降。但對于不同的數據集本實驗還不能自適應K值。

3.2.3 算法用時比較

本文在ModelNet40 數據集下對比四種算法的訓練時間，來衡量算法的計算成本，結果如表3 所示。可以發現本文算法在PointNet 算法上改進，且并行通過PointNet 網絡不影響訓練時間，因此時間與PointNet 接近。避免PointNet++和Kd-Net 算法多次分層導致的計算量龐大且模型訓練時間過長，證明本文算法有效地減少了計算量。

表3 訓練時間

4 結束語

本文設計并實現了一種基于K-means 聚類的三維點云分類算法模型，該算法在PointNet 算法基礎上改進，在原始點云上進行預處理，然后通過K-means 聚類算法，更有效地利用點云的局部特征，且并行通過PointNet 網絡也不影響訓練時間。在ModelNet10/ModelNet40 數據集上分類準確率達到94.2%和92.6%，并且訓練時間減少，分類效果優于其他模型。通過改變K值發現ModelNet數據集下當K=5 時效果最好。