基于改進SOM-K-Means 算法的三維點云分類

鄔春學，胡真豪

（上海理工大學 光電信息與計算機工程學院，上海 200093）

0 引言

隨著現(xiàn)代科技的逐步發(fā)展，人工智能成了各行各界的熱點話題與研究對象。在人工智能領域中，圖像分類技術［1-2］是一種常見的圖像處理方式。目前，基于對二維圖像的深入研究，已有為數可觀的科研人員都將研究重點轉向了三維圖像的分類，但是由于三維圖像包含的信息比二維圖像更加復雜多樣，這也導致了三維圖像處理過程的時間成本大大增加，同時也給三維點云數據配準技術帶來了不小的挑戰(zhàn)。

當下，有2 類常見的三維圖像分類，分別是：三維幾何變換分類方法和三維點云分類方法。其中，三維點云數據具有無序性和稀疏性的等特點［3］。在傳統(tǒng)的點云分類方法［4-8］中，是利用點云數據的局部屬性來提取人工特征，但是這樣的操作方式使得點云分類的精確度并不高。隨著計算機技術的發(fā)展以及深度學習的興起，越來越多的研究者嘗試將深度神經網絡應用于點云數據的分類中［9-14］，現(xiàn)已取得了令人滿意的結果。

在早期對三維點云數據的研究中，研究人員是將分散在空間中的雜亂的點云數據經過處理轉換為用體素格表示，再通過3 位卷積對處理后的點云數據進行特征提取。2015年，Maturana 等人［15］提出的VoxNet 方法，是將深度學習與圖像分類相結合，并且以分布均勻的體素網格作為輸入。VoxNet 的思想是用均勻分布的體素網格來代替不規(guī)則的點云，每個網格中包含的點的信息都可以用被占的網格信息來代替。VoxNet 的方法雖然能夠解決由于點云自身無序所帶來的問題，但是關于點云自身旋轉變化的問題困擾卻依然存在。此后，大量研究者對體素算法［16-18］進行改進，卻也未能解決計算量龐大的問題。2017年，Klokov 等人［19］提出了Kd-Net 算法，Kd-Net 的思想就是先將整個三維點云數據模型分層，然后對每一層的點云數據進行特征提取，但是采用分層提取的Kd-Net 算法還是存在一定的局限性，對于旋轉變換后的點云模型以及含有較多離群點和噪點的點云數據模型也未能取得較好的優(yōu)化結果。2017年，Qi 等人［20］也提出了經典的深度學習模型PointNet，該模型將點云數據直接作為模型的輸入。算法中，通過對均勻采樣后的點云進行訓練，利用點對稱函數來減少對于點云自身無序性帶來的問題影響，并通過引入三維旋轉矩陣來解決點云自身的旋轉問題。仍需指出，PointNet 算法雖然解決了點云自身的問題，卻也仍然存在不足。原始點云經過均勻采樣后，在降低計算復雜度的同時，卻也丟失了點云的部分，降低了點云分類結果的準確性，且算法僅以三維點云數據的全局特征作為分類標準參考，并沒有針對三維點云中更加多樣化的局部特征進行處理。2018年，仍是由Qi等人［21］針對PointNet 存在的問題，提出了改進完善的PointNet++網絡，采用分組提取特征的方式，只是這種方法并沒有保留點云空間分布的特征，且在處理較大規(guī)模點云數據時會不可避免地增加計算復雜度。2020年，馬京暉等人［22］提出在輸入PointNet 網絡前先進行點云預處理和點云聚類，再并行通過PointNet 網絡，這樣就較好地保留了點云的空間分布特性，但是研究中使用了K-Means 聚類，卻會對初始的聚類中心和分類數目比較敏感，需要提前做出預設，而且針對不同種類模型預設的分類結果數卻都是相同的，對后續(xù)的分類效果影響較大。

綜上，本文在原有的K-Means-PointNet 網絡模型上進行改進優(yōu)化，提出了基于改進SOM-K-Means算法［23-27］的三維點云分類算法，主要研究內容包括：

（1）對原始點云數據進行預處理，對于點云密集區(qū)域進行簡化，去除冗余的點和離群點，減少計算復雜度；對于點云稀疏區(qū)域進行稠密化操作，在稀疏點云中通過插值法進行稠密化操作，使得稀疏的點云能更好地反映點云模型的特征。針對不同密度的點云采用不同的預處理操作都是為了之后能更好地進行點云分類。

（2）對于預處理后的點云數據輸入到SOM-KMeans 算法模型，由SOM 神經網絡先進行粗聚類，得出輸入點云數據的分類數和初始聚類中心，再用K-Means 聚類進行精細化聚類。

（3）為了能夠完整保留三維點云數據的特性，采用并行方式將點云輸入PointNet 網絡進行特征提取。這種并行輸入的方式也有利于減少算法的時間。

1 網絡結構介紹

1.1 PointNet 結構介紹

PointNet 算法是將原始點云經過均勻采樣，將采樣后得到的所有點云數據作為算法的輸入，輸入的點云數據第一步操作時與空間變換旋轉矩陣TNet相乘來對齊點云數據，以此來處理點云自身無序的問題。然后將輸入的點云數據交給感知機，在由感知機提取多次特征后，就將與一個空間變換旋轉矩陣T-Net相乘來對提取到的點云特征進行第二次的對齊。緊接著，整合感知機在各個維度上提取到的點云特征，由最大池化操作來得到點云的全局特征。最后，將全局特征通過mlp 來預測分類任務最后的分類數k，這里k是最后一層的輸出數量，代表分類的個數，每個類別會對應于點云的分類得分。

對于PointNet 網絡的優(yōu)點，文中可做重點闡述如下：

（1）對原始點云數據進行處理，保留了原始點云的空間結構特征。

（2）通過學習到的T -Net空間變換矩陣來對齊點云，解決了點云自身旋轉的問題，并且通過添加損失函數來保證點云的完整性以及對齊后點云的優(yōu)越性。

（3）卷積神經網絡在提取了每個維度的點云特征后，通過最大池化層將特征整合成點云的全局特征，這就有效地解決了點云自身無序的問題。雖然在提取特征時進行了降維操作，但是在整合后依舊保留了原有的特征。

不僅如此，PointNet 網絡除了表現(xiàn)出更多優(yōu)點外，同時卻也存在著不足：保留了局部特征、卻未做有效利用，僅以全局特征作為分類參考，缺少局部特征的參考，降低了點云數據分類的準確性。

故而，研究團隊就在此基礎上進行了二次優(yōu)化，提出了PointNet++網絡，解決了忽略局部特征的問題，但是由于局部特征是PointNet++網絡在將點云分層后才提取的特征，而點云數據分層操作卻增加了計算復雜度，從而增加了算法運行時間。這里給出了PointNet 算法流程的設計步驟，順次表述如下。

輸入一個N×3 的2D 張量

輸出最后的分類結果

步驟1將輸入的點云數據通過一個T-Net學習到的旋轉矩陣來對齊點云。

步驟2將對齊后的點云經過最大池化操作進行特征提取。

步驟3使用T-Net對提取到的特征進行對齊。

步驟4將對齊后的特征進行最大池化。

步驟5將全局特征通過最大池化預測最后分類數；將局部特征和全局特征串聯(lián)，通過最大池化得到每個數據點的分類結果。

1.2 本文算法結構研究

本文提出的算法考慮到PointNet 網絡自身原有的優(yōu)勢并將其保留，保留空間旋轉變換矩陣T-Net來解決點云自身旋轉不變性的問題，保留最大池化層將各維度特征整合為全局特征的優(yōu)勢，在此基礎上將聚類算法與點云特征相結合，減少運算量，加快運算速度。

首先對原始的點云數據進行預處理操作，將離群點和噪點剔除，將稠密點稀疏化，稀疏點云插值，將預處理過后的點云數據輸入到SOM 神經網絡中進行聚類，輸出分類種數以及粗糙的分類結果。將輸出的分類數目作為k值，執(zhí)行K-Means 算法進行聚類，并對分類后的點云數據進行點云提取，多個類的點云同時進行特征提取，由于此過程為并行運算，并不會額外增加算法的運算量。此后通過最大池化層將提取到的點云特征進行整合，最后將整合的點云特征輸入全連接網絡，得到分類類別。

改進后的算法克服了原PointNet 網絡忽略局部特征的問題，有效利用了局部特征，大大提高了目標點云分類的準確性。由于局部特征提取的過程為并行計算，所以不額外增加算法運算時間，在運算時間上優(yōu)于PointNet++網絡。本文算法流程如圖1 所示。

圖1 本文算法流程圖Fig.1 The flow chart of the algorithm in this paper

1.2.1 點云數據預處理

原始的點云數據集中點云數據是雜亂的，是分布不均勻的，因此對點云數據進行預處理操作是有必要的。PointNet 網絡模型采用了均勻采樣的方式，忽略點云數據的不規(guī)則性，有可能降低最后的分類結果準確率。為了能夠避免這一可能，本文借鑒數據分析的方法，在預處理階段對不同密度狀態(tài)下的點云進行不同的預處理操作，當點云數據在一個區(qū)域內過于密集時，就刪減冗余的點云來降低點云密度，縮短運算時間；當局部點云數據過于稀疏時則進行三維點云稠密重建，通過點云插值以保證局部點云形態(tài)的完整性，提高分類的精度。本文預處理的設計流程如圖2 所示。

圖2 點云篩選流程圖Fig.2 Flow chart of point cloud screening

1.2.1.1 部分點云高度集中

對于點云密集區(qū)域，為了將冗余的點云數據去除，采用等間隔的采樣方法，計算采樣后的點云數據量，判斷是否超過目標閾值T0。由于本文改進的算法將與PointNet 算法進行比較驗證，可將目標閾值T0與PointNet 網絡保持一致，設置為2 048。

當采樣后的點云數量大于T0時，計算當前點云數量與T0之間的差值，并且計算當前點云（xs，ys，zs）與其他點云之間的距離，計算距離時采用的距離為歐氏距離D1，對此可表示為：

假設點云中的點為圓心，R為半徑劃分區(qū)域，按照點云區(qū)域內點云數量的大小進行排序，將包含最大數量的點云區(qū)域與差值進行比較，若不小于差值，則從點云中刪除差值大小的點云，保留其他的點云；若小于差值則不對當前點云進行操作，然后重復以上操作，直到點云數量等于閾值T0。

通過此方法可以有效地減少原始點云數據中的冗余點云，實驗室效果如圖3 所示。圖3（a）是原始的點云，點云數為19 686；圖3（b）是經過處理后的點云圖，點云數為2 048。由圖3 可知，此方法可以有效剔除點云集中區(qū)域內的冗余點云，且保持點云原有的三維形態(tài)。

圖3 點云篩選對比圖Fig.3 Point cloud screening comparison chart

1.2.1.2 部分點云區(qū)域稀疏

稀疏性是點云自身無法避免的缺陷，如圖4 所示。由于數據集中所包含的點云數量過少，即便可以保持三維點云的外觀形態(tài)，但是過于稀少的點云不利于后續(xù)的點云分類操作。

圖4 稀疏點云示意圖Fig.4 Schematic diagram of sparse point cloud

為了后續(xù)點云分類的正確性，需要對稀疏點云進行插值重建，既保持原始三維點云的外觀形態(tài)，又確保有足夠的點云數據用于點云分類操作，本文使用的插值重建方法是三角形內部插值法，三角形內部線性插值示意如圖5 所示。

圖5 三角形內部線性插值示意圖Fig.5 Schematic diagram of internal linear interpolation in the triangle

假設三角形的3 個定點分別為P1，P2，P3，在三角形內部插入點P，并且存在3 個自由度，即u＝使得：

其中，u+v+w＝1。

稀疏點云重建實驗的結果如圖6 所示，對稀疏的點云進行空間插值重建，使點云盡可能地在點云空間中均勻分布。圖6 的實驗結果表明，該方法可以有效地克服點云稀疏導致三維點云外輪廓模糊的缺點，促使點云在點云空間中實現(xiàn)均勻分布，有利于后續(xù)點云分類計算。

圖6 稀疏點云插值后的結果示意圖Fig.6 Schematic diagram of results after sparse point cloud interpolation

1.2.2 基于SOM-K-Means 聚類的三維點云分類

本文在對原始點云進行預處理后，將處理后的點云數據進行SOM-K-Means 聚類運算，目的是通過聚類算法將點云先做粗分類，同時將點云數據自身的局部特征加以有效合理的利用，同時也避免了PointNet++網絡將點云特征進行分層提取所帶來的增加時間復雜度的問題。本文提出的點云分類網絡，如圖7 所示。

圖7 基于SOM-K-Means 聚類的三維點云分類Fig.7 Classification of 3D point cloud based on SOM-K-Means clustering

圖7中，網絡輸入為原始點云經過預處理后的2 048個點，在這2 048個點上使用本文設計的SOMK-Means 聚類算法，目的是將這些點劃分為K個不同的類別，且這K個類中每個類別都包含著不等的點云個數，但是這些類別中的點云個數的差距并不大，因為過大的點云數量差距會對后續(xù)的計算結果產生較大的影響。然后將這K個類的點云數據并行輸入到PointNet 網絡中進行每個類的特征提取。最后利用最大池化層將由這K個類中提取到的點云特征進行融合生成全局特征，并將生成的包含局部特征的全局特征輸入到感知機中進行分類學習，輸出運行的分類結果、即分類類別數s。

1.2.2.1 K-Means 算法

在數據分析領域中，K-Means 聚類算法是一種常見的算法，該算法可以將數據進行快速有效的粗分類。K-Means 算法的本質就是在所有數據點中隨機選擇k個點作為初始的簇中心點，再對其余樣本點到這些簇中心點的距離進行計算，將距離同一個簇中心點較近的點都分配到一個簇中，每分配一個樣本點，簇中心點都會根據簇中現(xiàn)有的所有點再做一次重新計算。向簇中分配樣本點會一直持續(xù)到沒有剩余的樣本點可供分配，此時簇中心點的位置將不會再發(fā)生變化。

該算法的優(yōu)點是算法簡單、收斂速度快。缺點是對初始的聚類中心比較敏感，對于預估合適的k值是非常困難的。

1.2.2.2 SOM 算法

自組織映射（SOM）算法是一種高維可視化的無監(jiān)督學習的聚類算法。SOM 神經網絡是由輸入層和競爭層組成，需要最終聚集的不同類在競爭層中表現(xiàn)為一個個的節(jié)點。競爭學習是SOM 網絡采用的訓練網絡的方式，每個輸入的樣例在競爭層都會與本身相似度最高的節(jié)點進行匹配，并將這個匹配度最高的節(jié)點稱為該輸入樣例的激活節(jié)點。接下來會更新激活節(jié)點的參數，并且和激活節(jié)點相鄰近的點也會根據其與激活節(jié)點的歐氏距離來對參數進行適當更新。

該算法的優(yōu)點是，不需要提前預設分類數便可以進行自動聚類，并且容錯性高，對異常值和噪聲不敏感。缺點是，在訓練神經元時會出現(xiàn)個別神經元始終不能勝出、成為節(jié)點的情況，導致分類結果的準確性降低，并且SOM 神經網絡收斂效率較低。

1.2.2.3 SOM-K-Means 模型算法

結合SOM 算法和K-Means 算法的優(yōu)缺點，研究者提出了將二者結合的構想并加以實現(xiàn)。由于SOM 算法并不需要提前預設分類數，但是在網絡收斂時表現(xiàn)不理想；而K-Means 算法收斂速度快，但是初始聚類中心和k值很難提前預估。因此本文采用SOM-K-Means 算法、就是SOM 的優(yōu)化算法，既解決了SOM 神經網絡收斂效率低、分類結果不準確的問題，又克服了K-Means 聚類中心和k值的預設問題。SOM-K-Means 算法步驟具體如下。

輸入點云數據

輸出聚類結果

步驟1將點云數據輸入到SOM 神經網絡中進行聚類，輸出分類數目以及初步分類結果。

步驟2將步驟1 中得到的初期分類結果作為k值，在預處理過后的點云數據中隨機選擇k個點作為初始的簇中心點，再利用K-Means 算法進行聚類。

SOM-K-Means 聚類算法的結果經過可視化操作后如圖8 所示。

圖8 聚類可視化結果及其對應SSE 曲線Fig.8 Clustering visualization results and the corresponding SSE curves

1.2.2.4k值的驗證

手肘法是用來判斷K-Means 算法是否合理的方法之一，計算簇中所有的點到該簇中心點的距離和、即SSE值，可以畫出k -SSE曲線，在折線圖中找到所畫曲線的拐點。一般來說，曲線拐點就是K-Means算法的最佳k值，SSE結果示意見圖8。此處需用到的數學公式為：

圖8（a）～（d）中，k -SSE曲線的橫軸為目標聚類數，縱軸為各簇內點到簇中心的距離和。點云數據的分類準確度與聚類數是強相關的，也就是說結果類別越多，點云數據的分類準確度就越高。當預測的k值小于實際的最佳分類數時，SSE的曲線形狀相對陡峭；當預測的k值大于實際的最佳分類數時，SSE的曲線形狀相對平緩，而在陡峭與平緩之間的拐點對應的k值就是該樣本數據最佳的分類數。以Car 模型驗證k值舉例說明，本例中手肘肘部對應的k值為6。對本例數據單獨采用K-Means算法進行聚類，并畫出k -SSE曲線，由圖8（c）可以清晰地看到，當k＝6時，該點為曲線的拐點，即經過SOM 神經網絡得出的分類數是有實際意義的。

2 實驗及結果分析

為了對本文算法的分類效果做出評估，選用和馬京暉團隊［22］相同的數據集進行實驗，用于訓練與測試的數據集來自于公開的數據集ModelNet10 和ModelNet40。

2.1 實驗條件

實驗設備及軟件環(huán)境見表1。

表1 實驗配置Tab.1 Experimental configuration

2.2 實驗結果對比分析

本文將運用相同的數據集，并在相同的條件下開展實驗，對不同算法的分類準確率和算法的運行時間進行記錄，再進行對比分析。

2.2.1 準確率比較

本文將模型在相同數據集上的分類準確率與之前的研究者使用的方法進行對比，結果見表2。從表2 記錄的實驗數據中可以看出，本文算法通過原始點數據的預處理，減少了作為輸入的點云數量，減少了算法的運算復雜度，有效降低了計算量。K-Means-PointNet方法是將k設定為統(tǒng)一的固定值進行聚類，再進行特征提取，試驗結果表明本文算法在ModelNet10／40 數據集上對于三維點云分類任務能有效地提高分類準確度，說明對于原始點云的預處理和預處理后的點云數據率先進行聚類，將有助于提升點云分類任務的精度。本文的方法是不固定每個點云數據的分類數，并由SOM 神經網絡分析得出適合輸入點云的分類數后再進行K-means 聚類精化，將聚類后的點云數據并行通過PointNet 網絡，對每個簇中的點云實現(xiàn)提取特征，相比于其他算法，本文提出算法的準確度要更高。將本文算法與K-Means-PointNet算法進行對比可以看出，本文提出由SOM 神經網絡計算出合適的分類數比預先設定k值對分類精度的細化，能夠取得更好的結果。

表2 分類準確率Tab.2 Classification accuracy

2.2.2 算法用時比較

本文在數據集ModelNet40 上通過對比5 種算法訓練網絡分別需要的時間，來預估每種算法的計算時間成本，結果見表3。

表3 訓練時間Tab.3 Training time

通過表3 中的數據可以得出，本文算法在K-Means-PointNet的基礎上進行改進，但是將點云數據并行通過PointNet 網絡并不影響訓練時間，因此本文中提及的網絡的訓練時間與PointNet 接近。避免了PointNet++和Kd-Net 算法多次分層導致計算量龐大、且模型訓練時間過長的問題。同時，還避免了K-Means-PointNet對k值和初始中心的敏感帶來的計算量龐大、訓練時間增加的問題，證明本文的改進算法能有效地減少計算量。

3 結束語

本文提出的算法是在K-Means-PointNet 網絡的基礎上實現(xiàn)了改進，對原始點云數據進行關鍵的預處理，而后為了充分利用點云的局部特偵，采用SOM-K-Means 算法將點云進行分類處理，相比于分層提取點云，多個類別的點云并行提取點云特征也不會顯著增加其運算時間，所以本文算法在保證運算時間的前提下，有效提高了算法在ModelNet10／40 數據集上分類任務的準確度，仿真實驗運行后得到的準確度分別為94.8%和93.1%。研究可知，在同等條件下，本文算法的準確度要高于其他算法模型，與原有的K-Means-PointNet 網絡相比也有著一定的優(yōu)化和提升。