馬京暉，潘 巍，王 茹

首都師范大學(xué) 信息工程學(xué)院，北京 100048

1 引言

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

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

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

2 網(wǎng)絡(luò)結(jié)構(gòu)介紹

2.1 PointNet結(jié)構(gòu)介紹

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

PointNet算法的優(yōu)點：

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

（2）通過T-Net網(wǎng)絡(luò)解決了旋轉(zhuǎn)問題，用損失函數(shù)來對旋轉(zhuǎn)矩陣進行調(diào)整，并把輸入點云數(shù)據(jù)旋轉(zhuǎn)到一個更有利于分類的角度；

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

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

圖2 PointNet++結(jié)構(gòu)流程圖

圖1 PointNet網(wǎng)絡(luò)結(jié)構(gòu)

2.2 本文算法結(jié)構(gòu)介紹

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

首先對點云數(shù)據(jù)進行預(yù)處理，減少后續(xù)計算量。在PointNet 網(wǎng)絡(luò)的基礎(chǔ)上增添了K-means 聚類分析算法，對預(yù)處理后的點云數(shù)據(jù)進行K-means聚類處理，聚類為K個不同的類，分別進行PointNet 網(wǎng)絡(luò)的特征提取，過程為并行運算關(guān)系，不增加PointNet網(wǎng)絡(luò)的計算量。通過maxpooling全局特征處理，最后通過全連接網(wǎng)絡(luò)得到分類類別。

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

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

圖3 本文算法流程圖

2.2.1 點云預(yù)處理

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

圖4 篩選點云算法流程圖

（1）處理點云集中問題

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

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

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

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

圖5 點云篩選對比圖

（2）處理點云稀疏問題

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

圖6 稀疏點云示意圖

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

圖7 三角形插值示意圖

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

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

圖8 稀疏點云插值后結(jié)果示意圖

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

為了解決PointNet算法沒有局部特征提取的問題，本文在點云預(yù)處理環(huán)節(jié)之后，對點云進行了K-means聚類，使得通過聚類的結(jié)果更有效地利用點云的局部特征，同時可以解決PointNet++網(wǎng)絡(luò)對點云分層次提取特征時重疊的問題，從而提高分類的準(zhǔn)確率。基于K-means聚類算法的點云分類網(wǎng)絡(luò)如圖9所示。

圖9 基于K-means聚類算法的點云分類網(wǎng)絡(luò)

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

（1）K-means聚類算法

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

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

算法1K-means聚類算法

輸入：聚類個數(shù)K，點云數(shù)據(jù)

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

步驟1隨機產(chǎn)生K個種子，且保證種子不重疊。

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

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

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

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

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

（2）K值的選擇

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

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

圖11 K-SSE曲線示意圖

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

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

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

3.1 實驗條件

實驗配置如表1。

表1 實驗配置

3.2 實驗結(jié)果對比與分析

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

3.2.1 準(zhǔn)確率比較

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

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

表2 分類準(zhǔn)確率

3.2.2 改變K值準(zhǔn)確率比較

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

圖12 不同K 值下分類準(zhǔn)確率的影響

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

3.2.3 算法用時比較

本文在ModelNet40 數(shù)據(jù)集下對比四種算法的訓(xùn)練時間，來衡量算法的計算成本，結(jié)果如表3 所示?？梢园l(fā)現(xiàn)本文算法在PointNet 算法上改進，且并行通過PointNet 網(wǎng)絡(luò)不影響訓(xùn)練時間，因此時間與PointNet 接近。避免PointNet++和Kd-Net 算法多次分層導(dǎo)致的計算量龐大且模型訓(xùn)練時間過長，證明本文算法有效地減少了計算量。

表3 訓(xùn)練時間

4 結(jié)束語

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