馬京暉，潘 巍，王 茹

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

圖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)點(diǎn)，采用分層的思想，利用聚類算法并行特征提取，以避免運(yùn)算復(fù)雜度過大的問題。

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

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

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

圖3 本文算法流程圖

2.2.1 點(diǎn)云預(yù)處理

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

圖4 篩選點(diǎn)云算法流程圖

（1）處理點(diǎn)云集中問題

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

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

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

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

圖5 點(diǎn)云篩選對(duì)比圖

（2）處理點(diǎn)云稀疏問題

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

圖6 稀疏點(diǎn)云示意圖

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

圖7 三角形插值示意圖

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

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

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

2.2.2 基于K-means聚類的三維點(diǎn)云分類

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

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

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

（1）K-means聚類算法

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

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

算法1K-means聚類算法

輸入：聚類個(gè)數(shù)K，點(diǎn)云數(shù)據(jù)

輸出：每個(gè)聚類中所有元素

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

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

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

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

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

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

（2）K值的選擇

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

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

圖11 K-SSE曲線示意圖

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

3 實(shí)驗(yàn)及結(jié)果分析

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

3.1 實(shí)驗(yàn)條件

實(shí)驗(yàn)配置如表1。

表1 實(shí)驗(yàn)配置

3.2 實(shí)驗(yàn)結(jié)果對(duì)比與分析

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

3.2.1 準(zhǔn)確率比較

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

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

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

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

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

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

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

3.2.3 算法用時(shí)比較

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

表3 訓(xùn)練時(shí)間

4 結(jié)束語

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