優(yōu)化球查詢算法的點云分割

王愛兵，楊曉文，韓 燮，郭新東，彭志斌，郭子軍，賈彩琴

(中北大學(xué) 大數(shù)據(jù)學(xué)院，山西 太原 030051)

0 引 言

3D傳感器技術(shù)[1]的發(fā)展使得人們能夠方便地獲取大規(guī)模點云數(shù)據(jù)。例如，激光雷達傳感器每秒鐘可以產(chǎn)生數(shù)百萬個點，提供所需物體的點云數(shù)據(jù)。點云數(shù)據(jù)作為一種3D數(shù)據(jù)表達形式已成為眾多科學(xué)鄰域諸如計算機視覺[2]、自動駕駛[3]和機器人領(lǐng)域[4]的重要數(shù)據(jù)資料，是許多場景理解相關(guān)應(yīng)用程序的首選格式，為三維場景分割、多元化視覺、卡通制作、三維模型構(gòu)建和大眾傳播工具應(yīng)用提供多方面的用途。在三維場景分割中，典型的卷積架構(gòu)需要高度規(guī)則的輸入數(shù)據(jù)格式，如2D圖像或3D體素的格式，以便執(zhí)行權(quán)重共享和其他內(nèi)核優(yōu)化，然而2D圖像丟失了現(xiàn)實世界中兩個或多個物體之間的深度信息和相對位置，使得它不適合深度和定位信息的應(yīng)用；3D體素模型[5]是一組將點云轉(zhuǎn)移到空間量化的體素網(wǎng)格并使用體積卷積在網(wǎng)格空間中執(zhí)行計算的模型，利用網(wǎng)格作為數(shù)據(jù)結(jié)構(gòu)化方法，將點與網(wǎng)格中的位置相關(guān)聯(lián)，3D卷積核從相鄰體素收集信息。盡管網(wǎng)格數(shù)據(jù)結(jié)構(gòu)是有效的，但仍需要高體素分辨率來保持?jǐn)?shù)據(jù)的粒度。由于計算和內(nèi)存使用量隨體素分辨率呈三次方增長，因此處理大型點云的成本很高。此外，由于大多數(shù)體素結(jié)構(gòu)中大約90%的體素是沒有點云的，因此不處理任何信息但可能會消耗大量的計算能力。這種數(shù)據(jù)表示會使結(jié)果數(shù)據(jù)量變得不必要的龐大，同時還會引入量化噪聲，影響數(shù)據(jù)模型的魯棒性。

點云數(shù)據(jù)處理的另一類模型是基于點的模型。與體素模型相比，它將原始幾何信息保留在3D空間中，避免了點云數(shù)據(jù)體素化過程中的特征損失。例如，2017年Charles團隊提出了點云分類和分割網(wǎng)絡(luò)PointNet[6]，它直接處理點云數(shù)據(jù)，無需量化，利用多層感知器(Multilayer Perceptron，MLP)[7]提取全局特征向量，并利用對稱函數(shù)解決無序的問題，取得了不錯的目標(biāo)識別效果和較高的分割精度。然而該網(wǎng)絡(luò)只能學(xué)習(xí)到點云全局特征，不能捕捉由點所在的度量空間引起的局部結(jié)構(gòu)，限制了識別細粒度模式的能力和對復(fù)雜場景的概括能力，因此該網(wǎng)絡(luò)對于場景細節(jié)的分割精度欠佳。2020年J.Zhao提出了一種基于改進PointNet的端到端自動分割方法[8]，根據(jù)不同室內(nèi)結(jié)構(gòu)元素強度差異較大的特點，將3D坐標(biāo)、顏色和強度的點云信息輸入到點的特征空間中，提高了對墻、門等結(jié)構(gòu)元素的分割精度。2020年東華大學(xué)劉訓(xùn)華提出對圖像和激光雷達點云數(shù)據(jù)進行3D目標(biāo)檢測的改進F-PointNet[9]，使用寬閾值掩模處理，增加注意力機制并更換損失函數(shù)為Focal Loss可以獲得較優(yōu)的結(jié)果，但準(zhǔn)確率還有提升的空間。

針對該問題，Charles團隊借鑒CNN[10]多層感受野的思想對PointNet進行改進，提出了PointNet++[11]，它在整個點云局部采樣并劃定范圍，用PointNet進行特征提取，并以此方式多次迭代提取，將特征提取集中到少數(shù)點上，而每個點都包含上一層點通過PointNet提取出的局部特征?；诖?，PointNet++將局部區(qū)域劃分為多個分區(qū)，每個分區(qū)被定義為底層歐氏空間中的一個查詢球，其參數(shù)包括球心位置和距離。為了均勻覆蓋整個集合，球心通過最遠點采樣算法(farthest point sampling，F(xiàn)PS)[12]從輸入點集中選擇，對于密度不均勻的點云數(shù)據(jù)，球形鄰域范圍內(nèi)局部特征點的選取是具有挑戰(zhàn)性的。實驗結(jié)果表明，采用K-近鄰算法[13]對球鄰域中局部特征點的選取做進一步的優(yōu)化，將優(yōu)化后的算法應(yīng)用到PointNet++分割網(wǎng)絡(luò)，豐富了網(wǎng)絡(luò)的局部特征表征能力，強化了細節(jié)特征的表達效果。2020年上海理工大學(xué)孫紅提出融合MKF的PointNet++優(yōu)化算法[14]，采用基于深度學(xué)習(xí)的方法處理點云數(shù)據(jù),實現(xiàn)障礙物體的識別分類和環(huán)境的局部分割，在點云低密度的環(huán)境下仍有良好的效果，但MKF PointNet++算法在每一分層結(jié)構(gòu)中都需要判斷是否滿足點云密度需求，如果不滿足需要重新進行采樣，這樣會大大增加算法的時間。2021年武漢大學(xué)陳陽提出了一種改進的PointNet++網(wǎng)絡(luò)結(jié)構(gòu)[15]，該結(jié)構(gòu)將單個點的特征和全局特征集中在質(zhì)心點上，以便于分類。這些改進PointNet++網(wǎng)絡(luò)結(jié)構(gòu)的出現(xiàn)為之后基于深度學(xué)習(xí)的點云分割方法指引了方向，具有重要的理論研究價值。

該文在PointNet++研究的基礎(chǔ)上，引入K-近鄰優(yōu)化球查詢算法，選取球鄰域中特征聯(lián)系更為緊密的點作為局部特征提取點，加強了局部特征的表達效果。

1 優(yōu)化球查詢算法

1.1 球查詢算法

PointNet++采用球查詢作為點集重疊劃分的方法。球查詢算法首先獲取局部鄰域中重要中心點作為球心，為盡可能覆蓋局部鄰域中的所有點，PointNet++采用最遠點采樣的方法。最遠點采樣方法作為點云數(shù)據(jù)處理常用的采樣方法之一，它的核心思想是：首先在輸入的點云數(shù)據(jù)集中隨機抽取一個數(shù)據(jù)點作為起始點，將起始點歸入采樣點集合，計算所有點到起始點的歐氏距離，從中選擇距離最大值對應(yīng)的點歸入采樣點集合，依次迭代，直至達到所需數(shù)量要求。

將最遠點采樣獲取到的點設(shè)為球心劃定球形鄰域N，在球形鄰域中實施球查詢算法，選取球形鄰域的半徑r以及選取的特征點數(shù)m，用公式(1)表示為：

q(r,m)={‖s-s0‖≤r,count(s)≤m,

?s∈N}

(1)

其中，count(s)≤m表示在球鄰域中選取前m個距離小于半徑r的點。在分割網(wǎng)絡(luò)中，記錄球鄰域中的點到中心點的歐氏距離，找到所有距離小于r的點，將這些點根據(jù)數(shù)據(jù)輸入時的索引下標(biāo)排序，選取前m個點作為局部特征提取點。對于特征點m的選取，存在以下兩種情況：

(1)如圖1所示，在球形鄰域a中，當(dāng)與球形鄰域中心點距離小于r的點不足m個時，將索引下標(biāo)最小的點復(fù)制多次，湊足m個點進行局部特征提??；

(2)在球形鄰域b中，當(dāng)與球形鄰域中心點距離小于r的點超過m個時，根據(jù)索引下標(biāo)對其切片，選取索引下標(biāo)最小的前m個點提取局部特征。

圖1 球查詢算法示意圖

球查詢對于m個特征點的選取通過索引下標(biāo)排序，具有隨機性，沒有選取距離球形鄰域中心點最近的m個點提取特征，因此獲取到的局部特征表征能力較差，導(dǎo)致網(wǎng)絡(luò)的分割精度仍存在較大的提升空間。為了豐富局部特征的表征能力，提高分割精度，采用K-近鄰優(yōu)化球查詢算法。

1.2 K-近鄰優(yōu)化球查詢算法

K-近鄰算法是一種出現(xiàn)較早的經(jīng)典機器學(xué)習(xí)算法。該算法的核心思想是：在給定的樣本特征空間中，如果待預(yù)測樣本附近的k個樣本多數(shù)屬于某一個樣本類別，則該樣本也屬于該類別。該算法不需要初始訓(xùn)練，僅僅在待預(yù)測樣本分類時進行預(yù)測，如此可以減少模型訓(xùn)練的開銷，是一種惰性學(xué)習(xí)算法，也是分類數(shù)據(jù)簡單并且有效的算法，算法中k值的選擇、距離度量和分類決策規(guī)則是K-近鄰算法的三要素。

為合理優(yōu)化球查詢算法，將K-近鄰中的k值作為待測特征點的個數(shù)m，設(shè)置球鄰域中的特征點與中心點距離升序排序函數(shù)K(s)，K-近鄰優(yōu)化后的球查詢算法用公式(2)表示為：

q(r,k)={‖s-s0‖≤r,count(K(s))≤k,

?s∈N}

(2)

其中，K(s)表示對球鄰域的點與中心點的距離進行升序排序，從距離小于r的點選取前k個點作為局部特征的提取點，對于特征點k的選取，存在以下兩種情況：

(1)當(dāng)球鄰域中與中心點距離小于r的點不足k個時，將距離中心點最近的點復(fù)制多次，湊足k個，提取局部特征。

(2)當(dāng)球鄰域中與中心點的距離小于r的點超過k個時，選取距離最小的前k個點提取局部特征。

將K-近鄰優(yōu)化的球查詢算法應(yīng)用于PointNet++分割網(wǎng)絡(luò)并進行對比實驗，驗證算法的有效性。

2 優(yōu)化球查詢算法應(yīng)用于PointNet++網(wǎng)絡(luò)

PointNet網(wǎng)絡(luò)模型將所有特征點最大池化為一個全局特征，整個網(wǎng)絡(luò)模型沒有考慮局部特征的提取，因此該網(wǎng)絡(luò)模型對于局部鄰域點云特征的描述能力較弱，在分類或單個物體的分割中，缺少的局部特征可以通過中心化物體的坐標(biāo)軸緩解，但在場景分割中，由于缺乏局部特征細節(jié)描述能力，導(dǎo)致點云數(shù)據(jù)的分割效果較差。

PointNet++通過引入了多尺度分組和多分辨率分組對局部區(qū)域采用PointNet提取局部區(qū)域的全局特征作為局部特征，最后將不同尺度的特征拼接起來。由于多尺度分組的方法計算量大，PointNet++采用了多分辨率的方法。如圖2(a)所示，外圍圓代表局部區(qū)域，在局部區(qū)域中采用最遠點采樣的方法獲取多個重要的中心點s0。將K-近鄰優(yōu)化的球查詢算法應(yīng)用到局部特征點選取，以中心點s0為球心，r為半徑劃定球形鄰域，根據(jù)特征點距離中心點的距離，選取最近的k個點提取其局部鄰域特征，當(dāng)某球形鄰域中的點少于k個，則復(fù)制最近的點進行特征提取。如圖2(b)所示，將提取到的局部特征再次提取并與包圍這幾個交叉球形鄰域的局部區(qū)域的局部特征連接形成多分辨率局部特征。

圖2 局部鄰域多分辨率特征提取示意圖

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

3.1 實驗一

將斯坦福大學(xué)開發(fā)的帶有像素級語義標(biāo)注的語義數(shù)據(jù)集S3DIS[16]輸入優(yōu)化球查詢算法的分割網(wǎng)絡(luò)和原分割網(wǎng)絡(luò)進行對比。實驗是在處理器為Intel(R) Core(TM)i7-9700 CPU @3.00 GHz，內(nèi)存為64 GB，顯卡為TITAN RTX的工作站上完成的。

S3DIS數(shù)據(jù)集由6個大型室內(nèi)區(qū)域組成，總共包括544個房間，超過了2.15億個點，包括辦公區(qū)域、教育和展覽空間，以及會議室、個人辦公室、衛(wèi)生間、開放空間、大堂、樓梯和走廊。每個點包含坐標(biāo)信息XYZ、歸一化坐標(biāo)和顏色信息RGB，同時還附加了所屬的13個語義標(biāo)簽類別信息(桌子、椅子、沙發(fā)、書架和木板等)。

S3DIS數(shù)據(jù)集常用的數(shù)據(jù)形式有三種：原數(shù)據(jù)集、Stanford3dDataset_v1.2_Aligned_Version和indoor3d_sem_seg_hdf5_data。該文選取indoor3d_sem_seg_hdf5_data作為研究對象，該數(shù)據(jù)集格式是對原始數(shù)據(jù)場景的切割，把大場景切割成1mx1m的block，完整數(shù)據(jù)集被切割成了23 585個block,每個block是4 096個點,每個點對應(yīng)9個維度，具體表達為{X,Y,Z,R,G,B,X0,Y0,Z0}。其中X,Y,Z為目標(biāo)物表面點云的空間坐標(biāo)信息，是用來描述點云信息必不可少的特征，R,G,B為目標(biāo)物體影像在點云上的顏色紋理映射，X0,Y0,Z0為輸入點云的歸一化坐標(biāo)。

為了驗證K-近鄰優(yōu)化球查詢算法k值對分割結(jié)果的影響，將每個block的4 096個點作為一個局部領(lǐng)域樣本數(shù)N，設(shè)置訓(xùn)練次數(shù)epoch為300，鄰域點數(shù)k分別取64、128、256、512、1 024情況下，獲取場景分割mIoU的評估結(jié)果。如圖3所示，經(jīng)過多次實驗得出，當(dāng)k為512時得到了較好的分割評估結(jié)果。

圖3 原網(wǎng)絡(luò)與優(yōu)化球查詢算法網(wǎng)絡(luò)分割精度對比

如圖4所示，為驗證優(yōu)化球查詢算法的PointNet++分割網(wǎng)絡(luò)可以獲得比原分割網(wǎng)絡(luò)更高的交并比，同時為去除偶然性將k為512的優(yōu)化球查詢分割網(wǎng)絡(luò)與原分割網(wǎng)路執(zhí)行三次對比實驗。將優(yōu)化球查詢算法PointNet++分割網(wǎng)絡(luò)得出的訓(xùn)練結(jié)果命名為improve ball query1、improve ball query2和improve ball query3；另外ball query1、ball query2和ball query3為原PointNet++分割網(wǎng)絡(luò)的三次訓(xùn)練結(jié)果。三次對比實驗均證實采用優(yōu)化球查詢算法具有更加豐富的局部特征表征能力。

圖4 原網(wǎng)絡(luò)與優(yōu)化球查詢算法網(wǎng)絡(luò)分割精度對比

為進一步驗證優(yōu)化算法的魯棒性，從三次實驗結(jié)果中選取improve ball query1與原網(wǎng)絡(luò)實驗結(jié)果ball query1損失函數(shù)(loss function)[17]進行對比。在機器學(xué)習(xí)中，損失函數(shù)是用來估量模型的預(yù)測值f(x)與真實值Y的不一致程度，損失函數(shù)越小，一般代表模型的魯棒性越好。如圖5所示，優(yōu)化球查詢算法PointNet++分割網(wǎng)絡(luò)的實驗結(jié)果improve ball query1在相同訓(xùn)練次數(shù)的情況下?lián)p失函數(shù)低于原分割網(wǎng)絡(luò)結(jié)果ball query1。

圖5 原網(wǎng)絡(luò)與優(yōu)化球查詢算法網(wǎng)絡(luò)損失函數(shù)對比

優(yōu)化球查詢算法的PointNet++分割網(wǎng)絡(luò)雖然在分割精度和損失函數(shù)上取得了不錯的成效，但在每次球查詢時需要對球鄰域中的特征點根據(jù)歐氏距離進行排序，因此相比于原分割網(wǎng)絡(luò)時間復(fù)雜度更高。如圖6所示，優(yōu)化球查詢算法PointNet++分割網(wǎng)絡(luò)的實驗結(jié)果improve ball query1比原網(wǎng)絡(luò)實驗結(jié)果ball query1在相同訓(xùn)練批次的情況下所需時間更多。

圖6 原網(wǎng)絡(luò)與優(yōu)化球查詢算法網(wǎng)絡(luò)訓(xùn)練所需時間對比

選取S3DIS數(shù)據(jù)集Area_5，將優(yōu)化球查詢算法PointNet++分割網(wǎng)絡(luò)在測試時所需時間與原分割網(wǎng)絡(luò)進行對比，如圖7所示，優(yōu)化球查詢算法PointNet++分割網(wǎng)絡(luò)實驗結(jié)果improve ball query與原網(wǎng)絡(luò)測試結(jié)果ball query在相同測試數(shù)據(jù)集的情況下，所需時間相差很小。

圖7 原網(wǎng)絡(luò)與優(yōu)化球查詢算法網(wǎng)絡(luò)

3.2 實驗二

將優(yōu)化球查詢算法后的分割網(wǎng)絡(luò)應(yīng)用到ShapeNetPart數(shù)據(jù)集[18]作為可視化分割樣本與原網(wǎng)絡(luò)對比。ShapeNet是普林斯頓大學(xué)、斯坦福大學(xué)進行計算機圖形學(xué)[19]，計算機視覺，機器人技術(shù)和其他相關(guān)學(xué)科的研究開發(fā)的數(shù)據(jù)集。它由16種對象類型的16 881個計算機輔助設(shè)計模型組成，對象中的每個點對應(yīng)一個零件標(biāo)簽，共有50個類別，每個對象類型有2到6個零件類別。從每個3D模型中抽取1 024個點進行訓(xùn)練和測試。

如圖8所示，左邊為點云數(shù)據(jù)對應(yīng)的圖像類型，中間為原PointNet++對點云數(shù)據(jù)的可視化分割結(jié)果，右邊為優(yōu)化球查詢算法后PointNet++分割網(wǎng)絡(luò)獲取的可視化分割結(jié)果，框選部分為原分割網(wǎng)絡(luò)與優(yōu)化球查詢算法分割網(wǎng)絡(luò)可視化結(jié)果對比區(qū)域。實驗結(jié)果表明，優(yōu)化后的球查詢算法更易捕捉精細幾何結(jié)構(gòu)的局部特征，強化了局部特征的表征能力，對細節(jié)特征的表達展示了更好的效果。

圖8 ShapeNetPart可視化分割結(jié)果

4 結(jié)束語

采用K-近鄰優(yōu)化球查詢算法，選取球鄰域中特征聯(lián)系更為緊密的點作為局部特征提取點，加強了局部特征的表達效果。將優(yōu)化后的球查詢算法應(yīng)用于PointNet++分割網(wǎng)絡(luò)，通過多次實驗表明優(yōu)化后球查詢算法更加豐富了網(wǎng)絡(luò)局部特征的表征能力，強化了細節(jié)特征的表達效果，獲得了更高的分割精度；但是增加了球鄰域選取局部特征點的時間復(fù)雜度，因此在豐富局部特征表征能力的情況下，降低算法的時間復(fù)雜度是需要進一步研究的內(nèi)容。