PointPCA:一種三維空間點(diǎn)云的特征提取算法

摘要：點(diǎn)云是一個(gè)龐大點(diǎn)的集合而且擁有重要的幾何結(jié)構(gòu)。由于其龐大的數(shù)據(jù)量，不可避免地就會(huì)在某些區(qū)域內(nèi)出現(xiàn)一些相似點(diǎn)，這就使得在進(jìn)行特征提取時(shí)提取到一些重復(fù)的信息，造成計(jì)算冗余，降低訓(xùn)練的準(zhǔn)確率。針對(duì)上述問題，提出了一種新的神經(jīng)網(wǎng)絡(luò)——PointPCA，可以有效地解決上述問題；在PointPCA中，總共分為三個(gè)模塊：a）采樣模塊，提出了一種average point sampling（APS）采樣方法，可以有效地規(guī)避一些相似的點(diǎn)，得到一組近似代表這組點(diǎn)云的新的點(diǎn)集；b）特征提取模塊，采用分組中的思想，對(duì)這組新的點(diǎn)的集合進(jìn)行多尺度空間特征提取；c）拼接模塊，將每一尺度提取的特征向量拼接到一起組合為一個(gè)特征向量。經(jīng)過實(shí)驗(yàn)表明，PointPCA比PointNet在準(zhǔn)確率方面提升了4.6%，比PointNet++提升了1.1%；而且在mIoU評(píng)估測(cè)試中也有不錯(cuò)的效果。

關(guān)鍵詞：PointPCA；average point sampling；多尺度空間特征提取；特征向量

中圖分類號(hào)：TP391.41文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2023）01-049-0294-05

doi：10.19734/j.issn.1001-3695.2022.03.0214

PointPCA：feature extraction algorithm for 3D point cloud

Ji Yulin，Zhong Jiandan，Li Yingxiang，F(xiàn)u Junjie，Liu Jiawei

（Chengdu University of Information Engineering，Chengdu 610200，China）

Abstract：Point clouds are a large collection of points and have important geometric structures.Due to its large amount of data，it is unavoidable that some similar points will appear in some areas，which makes the feature extraction to extract some duplicate information，resulting in redundancy of calculation，and reducing the accuracy of training.To solve these problems，

this paper proposed a new neural network—PointPCA，which could effectively solve the above problems.In PointPCA，there were three modules：a）sampling module.It proposed an average point sampling （APS） sampling method，which could effectively avoid some similar points and get a new set of points that approximate this set of point clouds.b）feature extraction module.It used the idea of grouping to extraction

multi-scale spatial feature for the set of new points.c）stitching module.It stitched the feature vectors extracted at each scale into one feature vector.Experiments show that the accuracy of PointPCA is 4.6% higher than that of PointNet and 1.1% higher than that of PointNet++.It also works well in mIoU assessment tests.

Key words：PointPCA；average point sampling；multi-scale spatial feature extraction；feature vector

近年來，隨著SLAM（simultaneous localization and mapping）、Kinect以及激光掃描等技術(shù)日漸成熟，三維點(diǎn)云的數(shù)據(jù)量也迅速增長(zhǎng)，如何描述三維空間中點(diǎn)云數(shù)據(jù)的高層語義理解也越來越受到關(guān)注。三維點(diǎn)云的語義分割是一種典型的計(jì)算機(jī)視覺問題，是指將一些原始三維點(diǎn)云數(shù)據(jù)作為輸入并通過一系列技術(shù)操作轉(zhuǎn)換為具有突出顯示的感興趣區(qū)域的掩模，在自動(dòng)駕駛、導(dǎo)航定位、智慧城市等領(lǐng)域成為研究的熱點(diǎn)［1～9］，具有廣泛的應(yīng)用前景。

PointNet［10］是一項(xiàng)直接處理三維點(diǎn)云的開創(chuàng)性工作，其基本思想是學(xué)習(xí)每個(gè)點(diǎn)的空間特征，利用這些學(xué)習(xí)到的特征進(jìn)行分類分割任務(wù)。由于PointNet僅僅是針對(duì)每個(gè)點(diǎn)的表征，對(duì)局部結(jié)構(gòu)信息整合能力太弱而且直接由Max-Pooling獲得，所以無論是對(duì)分類還是分割任務(wù)，都會(huì)造成巨大的信息損失，在此基礎(chǔ)上提出了PointNet++［11］。PointNet++的基本思想是在PointNet的基礎(chǔ)上增加了鄰域信息的提取，并且利用最遠(yuǎn)點(diǎn)采樣的方法對(duì)點(diǎn)云進(jìn)行采樣，這樣極大程度上改善了PointNet存在的局部信息整合力弱和信息損失嚴(yán)重等問題。雖然PointNet++解決了很多問題，但是在PointNet++中所采用的最遠(yuǎn)點(diǎn)采樣的方法計(jì)算量遠(yuǎn)大于隨機(jī)采樣，使得PointNet++訓(xùn)練時(shí)間過長(zhǎng)、計(jì)算量過大。針對(duì)PointNet++存在的問題，提出了PointCNN［12］和PointWeb［13］等解決方案。本文在PointNet++的基礎(chǔ)上提出了一種新的解決方案——PointPCA。

1算法模型

如圖1所示，該算法主要由采樣模塊、特征提取模塊和拼接模塊三個(gè)模塊組成。a）采樣模塊，本文提出了一種新的采樣方法APS來解決最遠(yuǎn)點(diǎn)采樣和隨機(jī)采樣在計(jì)算時(shí)間和點(diǎn)的覆蓋率上存在的不足，并針對(duì)這些采樣方法設(shè)置了對(duì)比實(shí)驗(yàn)來證明APS在計(jì)算時(shí)間和點(diǎn)的覆蓋率上存在優(yōu)勢(shì)；b）特征提取模塊，利用分組采樣的思想對(duì)采樣的點(diǎn)進(jìn)行多尺度特征提取；c）拼接模塊，將多個(gè)尺度的特征向量進(jìn)行特征拼接，拼接為一個(gè)特征向量，輸入到全連接層。實(shí)驗(yàn)表明， PointPCA能夠高效、穩(wěn)健地學(xué)習(xí)三維點(diǎn)云的特征，特別是在具有挑戰(zhàn)性的3D點(diǎn)云基準(zhǔn)測(cè)試中獲得了明顯優(yōu)于最新技術(shù)的結(jié)果。

圖1網(wǎng)絡(luò)模型算法框架

Fig.1Algorithm block of network model

1.1采樣模塊

采樣是指從一個(gè)連續(xù)的空間中得到一個(gè)離散點(diǎn)集的過程，而本文算法的目標(biāo)則是從離散的三維點(diǎn)云中經(jīng)過某種算法得到一個(gè)新的點(diǎn)云，替代原有的點(diǎn)云。從數(shù)學(xué)形式上講，一般情況下，可以將點(diǎn)云中的數(shù)據(jù)看成一個(gè)無序點(diǎn)集{x1，x2，…，xn}，其中xi∈Rd，定義一個(gè)集合函數(shù)F：x→R，使無序點(diǎn)集映射到空間向量中，通過某種算法G，對(duì)無序點(diǎn)集{x1，x2，…，xn}進(jìn)行采樣，得到一組新的點(diǎn)集{xi，xi+1，…，xi+m}（其中xi，xi+1，…，xi+m∈{x1，x2，…，xn}）。目的就是在保留原有向量特征的情況下，盡可能地減少點(diǎn)的數(shù)量。

首先假設(shè)原始點(diǎn)云為n個(gè)m維矩陣，即

X=x11…x1m

xn1…xnmn×m（1）

為了便于后續(xù)計(jì)算，先進(jìn)行零均值化，即

X=x11-u1…x1m-um

xn1-un…xnm-umn×m（2）

其中：uj=1n∑nj=1xji表示列向量的均值；采樣的目標(biāo)是從原始的輸入點(diǎn)云中找到每個(gè)點(diǎn)與其他點(diǎn)之間的聯(lián)系，進(jìn)而在選擇質(zhì)點(diǎn)時(shí)過濾掉相似的點(diǎn)，可避免提取重復(fù)的信息同時(shí)避免計(jì)算冗余。通常尋找每個(gè)點(diǎn)與其他點(diǎn)之間的關(guān)系，首先會(huì)想到矩陣的協(xié)方差。如式（3）所示，計(jì)算原始輸入點(diǎn)云的協(xié)方差。

C=1nXTX=Cov（x1，x1）…Cov（x1，xk）

Cov（xk，x1）…Cov（xk，xk）（3）

從式（3）可知矩陣對(duì)角線上的兩個(gè)元素分別是兩個(gè)向量的方差和協(xié)方差，兩者統(tǒng)一到一個(gè)矩陣。

依據(jù)上述推導(dǎo)發(fā)現(xiàn)，要達(dá)到想要的效果，等價(jià)于將協(xié)方差矩陣對(duì)角化：即除對(duì)角線外的其他元素化為0，并且在對(duì)角線上將元素按大小從上到下排列，以此達(dá)到優(yōu)化目的。進(jìn)一步看原矩陣與基變換后矩陣協(xié)方差矩陣的關(guān)系：設(shè)原始數(shù)據(jù)矩陣X對(duì)應(yīng)的協(xié)方差矩陣為C，而P是一組按行組成的矩陣，設(shè)Y=PX，則Y為X對(duì)P做基變換后的數(shù)據(jù)。設(shè)Y的協(xié)方差矩陣為D，推導(dǎo)一下D與C的關(guān)系：

D=1nYYT=1n（PX）（PX）T=P（1nXXT）PT=PCPT（4）

由式（4）可知，要找出能讓原始協(xié)方差矩陣對(duì)角化的P。即采樣的目的變成了尋找一個(gè)矩陣P，滿足PCPT是一個(gè)對(duì)角矩陣，并且對(duì)角元素按從大到小依次排列，那么P的前K行就是要尋找的基，用P的前K行組成的矩陣乘以X就使得X從N維降到了K維，并滿足上述優(yōu)化條件。推導(dǎo)到現(xiàn)在為止，所有的焦點(diǎn)都聚焦在了協(xié)方差矩陣對(duì)角化問題上，由于協(xié)方差矩陣C是一個(gè)是對(duì)稱矩陣，根據(jù)對(duì)稱矩陣的性質(zhì)：

a）實(shí)對(duì)稱矩陣不同特征值對(duì)應(yīng)的特征向量必然正交。

b）設(shè)特征向量λ重?cái)?shù)為r，則必然存在r個(gè)線性無關(guān)的特征向量對(duì)應(yīng)于λ，因此可以將這r個(gè)特征向量單位正交化。

由上面兩條實(shí)對(duì)稱矩陣的性質(zhì)可知，一個(gè)n行n列的實(shí)對(duì)稱矩陣一定可以找到n個(gè)單位正交特征向量，設(shè)這n個(gè)特征向量，按列組成矩陣為E=（e1，e2，…，en）；則協(xié)方差矩陣C有如下結(jié)論：

ETCE=Λ=γ1…0

0…γn（5）

其中：Λ為對(duì)角矩陣，其對(duì)角元素為各特征向量對(duì)應(yīng)的特征值（可能有重復(fù)）。到這里，已經(jīng)找到所需矩陣P：P=ETP=ET。P是協(xié)方差矩陣的特征向量單位化后按行排列出的矩陣，其中每一行都是C的一個(gè)特征向量，而且得到了協(xié)方差矩陣的特征值。采樣的目標(biāo)是將原始的輸入點(diǎn)云中的每一個(gè)點(diǎn)給定一個(gè)特定的順序，本文的想法是計(jì)算信息貢獻(xiàn)率bj，如式（6）所示。協(xié)方差矩陣中存在相等的特征值，認(rèn)為它對(duì)整個(gè)點(diǎn)云的信息貢獻(xiàn)率是相等的，在進(jìn)行采樣時(shí)可以只保留一個(gè)值；剩下的點(diǎn)云，根據(jù)采樣點(diǎn)的需要，從剩下的點(diǎn)中抽取。

特征值γj的信息貢獻(xiàn)率bj=γj∑km=1γm（6）

APS是指從這組有序的點(diǎn)集中等差抽取一組點(diǎn)，如圖2所示，根據(jù)需要的采樣數(shù)，等間隔地從這組有序的點(diǎn)集中抽取一組點(diǎn)。

APS算法框架如圖3所示。首先對(duì)原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理；計(jì)算其相關(guān)系數(shù)矩陣；然后根據(jù)得到的相關(guān)系數(shù)矩陣計(jì)算其特征值和特征向量；再計(jì)算特征值的信息貢獻(xiàn)率，按照信息貢獻(xiàn)率從大到小順序進(jìn)行排列，并從中等差抽取一定的點(diǎn)，拼接起來得到采樣點(diǎn)。

1.2PointPCA網(wǎng)絡(luò)

PointPCA網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示，首先，將對(duì)點(diǎn)集進(jìn)行采樣，采樣后得到點(diǎn)，取具體的訓(xùn)練數(shù)據(jù)，即ModelNet40的每個(gè)訓(xùn)練集和數(shù)據(jù)集都是10 000點(diǎn)，對(duì)10 000點(diǎn)進(jìn)行一次排序（注意這里只能進(jìn)行一次排序），然后分別為這些排序的點(diǎn)選擇1 024點(diǎn)、512點(diǎn)和256點(diǎn)；然后對(duì)這些點(diǎn)進(jìn)行分組和點(diǎn)網(wǎng)操作，并在實(shí)際訓(xùn)練中對(duì)中間采樣、分組和點(diǎn)網(wǎng)層進(jìn)行三次劃分。最后，從這三個(gè)采樣點(diǎn)獲得的信息被縫合并輸入到全連接層進(jìn)行分類。PointPCA網(wǎng)絡(luò)一共分為采樣模塊、特征提取模塊和拼接模塊三大部分。其中特征提取模塊構(gòu)建了一個(gè)分層特征提取網(wǎng)絡(luò)，該特征提取網(wǎng)絡(luò)由采樣層、分組層和PointNet層三個(gè)關(guān)鍵層組成。采樣層從輸入點(diǎn)選擇一組點(diǎn)，定義局部區(qū)域的質(zhì)心；然后，分組層通過查找質(zhì)心周圍的“相鄰”點(diǎn)來構(gòu)造局部區(qū)域集；PointNet層將局部區(qū)域編碼為特征向量。這種分層網(wǎng)絡(luò)可以很好地提取特征而且訓(xùn)練效果也很不錯(cuò)，但是由于采樣層采用的是最遠(yuǎn)點(diǎn)采樣，所以在每一次采樣的時(shí)候都需要進(jìn)行一次計(jì)算來選取質(zhì)心，這就加大了計(jì)算冗余，顯然不符合設(shè)計(jì)的需求。為此在PointNet++［2］分層網(wǎng)絡(luò)的基礎(chǔ)上進(jìn)行了優(yōu)化。下面將著重介紹優(yōu)化后的分層特征提取網(wǎng)絡(luò)。

本文的分層特征提取網(wǎng)絡(luò)依然采用PointNet++中三個(gè)關(guān)鍵的層：采樣層、分組層和PointNet層。如圖4所示，采樣層利用主成分均勻采樣方法對(duì)所有點(diǎn)進(jìn)行排序，從所得的排序點(diǎn)中選擇一組點(diǎn)，作為局部區(qū)域的質(zhì)心；然后分組層通過查找質(zhì)心周圍 “相鄰”的點(diǎn)來構(gòu)造局部區(qū)域的點(diǎn)的集合；最后PointNet層將局部區(qū)域編碼為特征向量。下面將單獨(dú)介紹每一個(gè)關(guān)鍵層的具體作用。

a）采樣層。給定輸入點(diǎn){x1，x2，…，xn}，使用主成分均勻采樣來選擇點(diǎn){xi}的子集，即從這個(gè)給定順序的點(diǎn)集中找到一組最具代表性質(zhì)的點(diǎn)來表示原始的無序點(diǎn)集。與隨機(jī)抽樣相比，在質(zhì)心數(shù)相同的情況下，該方法對(duì)整個(gè)點(diǎn)集具有更好的覆蓋率；與最遠(yuǎn)點(diǎn)采樣相比，該方法可以減少計(jì)算量、降低計(jì)算冗余。

b）分組層。這里的分組層與PointNet++中的分組層沒有太大差異，該層的輸入是一個(gè)大小為N×（d+C）的點(diǎn)集和一組大小為N′×d的質(zhì)心的坐標(biāo)。輸出是一組大小為N′×K×（d+C）的點(diǎn)集，其中每組對(duì)應(yīng)于一個(gè)局部區(qū)域，是質(zhì)心點(diǎn)鄰域中的點(diǎn)數(shù)，這在不同的組中有所不同，但后續(xù)的PointNet層能夠?qū)㈧`活數(shù)量的點(diǎn)轉(zhuǎn)換為固定長(zhǎng)度的局部區(qū)域特征向量。

c）PointNet層。這里的PointNet層仍然采用的是PointNet++中的PointNet層，在該層中，輸入是數(shù)據(jù)大小為N′×K×（d+C）的點(diǎn)的局部區(qū)域。輸出中的每個(gè)局部區(qū)域由其質(zhì)心和對(duì)質(zhì)心鄰域進(jìn)行編碼的局部特征提取，輸出數(shù)據(jù)大小為N′×（d+C′）。其目的是將提取到特征進(jìn)行max pooling操作，方便后續(xù)連接全連接層。

2實(shí)驗(yàn)

2.1采樣方法分析

在這一節(jié)中主要做了兩個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)1將APS采樣與隨機(jī)采樣、最遠(yuǎn)點(diǎn)采樣在計(jì)算時(shí)間和點(diǎn)的覆蓋率上從理論和實(shí)驗(yàn)兩個(gè)方面進(jìn)行對(duì)比分析；實(shí)驗(yàn)2借助PointNet++網(wǎng)絡(luò)模型提供詳細(xì)的實(shí)驗(yàn)進(jìn)一步驗(yàn)證APS采樣算法與最遠(yuǎn)點(diǎn)采樣算法的優(yōu)劣。

實(shí)驗(yàn)1分別從隨機(jī)采樣、最遠(yuǎn)點(diǎn)采樣和APS采樣中各自選取了1 024、512、128、64和32個(gè)點(diǎn)。如圖5～7所示，不難看出當(dāng)選取1 024和512個(gè)點(diǎn)的時(shí)候，隨機(jī)采樣、最遠(yuǎn)點(diǎn)采樣和主成分分析方法采樣依然能夠可以識(shí)別這是一把椅子，但是當(dāng)繼續(xù)減少采樣點(diǎn)數(shù)量時(shí)，比如減少到128、64個(gè)點(diǎn)甚至更少的時(shí)候，隨機(jī)采樣幾乎無法識(shí)別點(diǎn)云所表示的是什么，更不夸張地說32個(gè)點(diǎn)時(shí)只能知道這是一團(tuán)點(diǎn)；反觀最遠(yuǎn)點(diǎn)采樣和APS在128和64個(gè)點(diǎn)的時(shí)候依然能夠辨識(shí)出這是一把椅子，當(dāng)點(diǎn)數(shù)縮減至32個(gè)點(diǎn)時(shí)，只有椅子的輪廓。

眾所周知，隨機(jī)采樣就是按隨機(jī)性原則，從總體單位中抽取部分單位作為樣本，就是從輸入點(diǎn){x1，x2，…，xn}中隨機(jī)選擇一部分點(diǎn){xi，xi+1，…，xi+m}（其中xi，xi+m∈{x1，x2，…，xn}），說明采樣點(diǎn)的選擇具有隨機(jī)性，當(dāng)采樣點(diǎn)數(shù)量選擇較多時(shí)，就會(huì)非常接近輸入點(diǎn)；但是隨著采樣點(diǎn)的數(shù)量逐漸降低，加之采樣點(diǎn)具有隨機(jī)性，就會(huì)逐漸偏離輸入點(diǎn)，甚至完全無法識(shí)別。這就印證了為什么隨機(jī)采樣在選擇1 024、512和128個(gè)點(diǎn)的時(shí)候可以辨識(shí)出這是一把椅子，而在選擇64和32個(gè)點(diǎn)時(shí)卻難以辨認(rèn)，甚至完全認(rèn)不出，只知道這是一堆點(diǎn)。

最遠(yuǎn)點(diǎn)采樣為什么在點(diǎn)數(shù)較少的時(shí)候仍然可以辨識(shí)？這與最遠(yuǎn)點(diǎn)采樣的原理有關(guān)，其原理是首先從輸入點(diǎn)集{x1，x2，…，xn}中隨機(jī)選出一個(gè)點(diǎn){xi}（其中xi∈{x1，x2，…，xn}），然后從剩余點(diǎn)中選擇一個(gè)距離xi最遠(yuǎn)的點(diǎn)xm，之后再從輸入點(diǎn)集中選擇一個(gè)距離已經(jīng)經(jīng)過最遠(yuǎn)點(diǎn)采樣得到的點(diǎn)（即xi和xm）的最遠(yuǎn)的一個(gè)點(diǎn)，最后重復(fù)以上操作，直到選出所需要的所有點(diǎn)。這也就很好地說明為什么在選擇128、64和32個(gè)點(diǎn)時(shí)也可以大致辨認(rèn)出這是一把椅子。明顯區(qū)別于隨機(jī)采樣。

對(duì)于本文提出的APS采樣，在選擇減少點(diǎn)的時(shí)候仍可達(dá)到與最遠(yuǎn)點(diǎn)采樣一樣的效果，甚至還比最遠(yuǎn)點(diǎn)采樣效果要好一些，這與APS采樣算法的原理密不可分，在這里就不過多贅述，具體可以看上文。接下來從計(jì)算復(fù)雜度上說一下這四種采樣方法。隨機(jī)采樣方法的計(jì)算復(fù)雜度是這四種方法中最低的，計(jì)算復(fù)雜度為O（N），因其計(jì)算量與輸入點(diǎn)云的總點(diǎn)數(shù)無關(guān)，只與降采樣后的點(diǎn)數(shù)K有關(guān)，即常數(shù)時(shí)間復(fù)雜度；最遠(yuǎn)點(diǎn)采樣的計(jì)算復(fù)雜度是這四種采樣方法中最高的，其計(jì)算復(fù)雜度是O（N2），計(jì)算量與輸入點(diǎn)云的點(diǎn)數(shù)呈平方相關(guān)，隨著輸入點(diǎn)的數(shù)量逐漸增大，其計(jì)算復(fù)雜度也會(huì)稱平方式增加。而APS采樣介于這兩者之間，APS采樣只需要將每一個(gè)輸入點(diǎn)過濾一遍，將相似的點(diǎn)聚在一起，并給出一個(gè)順序，因而，其計(jì)算復(fù)雜度只與輸入點(diǎn)的個(gè)數(shù)N有關(guān)，與輸入點(diǎn)的個(gè)數(shù)N呈正比，故其計(jì)算復(fù)雜度為O（N）。通過以上在點(diǎn)的覆蓋率和計(jì)算復(fù)雜度上分析，APS采樣方法在點(diǎn)的覆蓋率和計(jì)算復(fù)雜度上都有明顯的優(yōu)勢(shì)。其比隨機(jī)采樣在點(diǎn)的覆蓋率上存在明顯的優(yōu)勢(shì)，和最遠(yuǎn)點(diǎn)采樣基本沒有太大的差距；又在計(jì)算復(fù)雜度上比最遠(yuǎn)點(diǎn)采樣存在優(yōu)勢(shì)，訓(xùn)練時(shí)間縮短近一半。

為了進(jìn)一步證實(shí)APS采樣在計(jì)算復(fù)雜度和采樣點(diǎn)的覆蓋率上與最遠(yuǎn)點(diǎn)采樣相比存在優(yōu)勢(shì)。在實(shí)驗(yàn)2中，選取國際上比較認(rèn)可的ModelNet40（包含40個(gè)類別的CAD模型（主要是人造的），9 843個(gè)形狀用于訓(xùn)練，2 468個(gè)形狀用于測(cè)試）數(shù)據(jù)集作為這次的實(shí)驗(yàn)主要訓(xùn)練和測(cè)試的數(shù)據(jù)集。在這一次的實(shí)驗(yàn)中，分為三個(gè)步驟：a）用PointNet++網(wǎng)絡(luò)模型對(duì)ModelNet40數(shù)據(jù)集進(jìn)行訓(xùn)練（PointNet++中用到的采樣方法為最遠(yuǎn)點(diǎn)采樣），記錄下訓(xùn)練結(jié)果準(zhǔn)確率達(dá)到90%的時(shí)間和最終的準(zhǔn)確率；b）在保持其他條件不變的情況下，將PointNet++所有用到最遠(yuǎn)點(diǎn)采樣算法的地方全部替換為APS采樣，記錄訓(xùn)練結(jié)果準(zhǔn)確率達(dá)到90%的時(shí)間和最終的準(zhǔn)確率；c）對(duì)比這兩組數(shù)據(jù)分析APS采樣和最遠(yuǎn)點(diǎn)采樣在計(jì)算復(fù)雜度和點(diǎn)的覆蓋率的優(yōu)劣性。

如圖8所示，可以清楚地看到在訓(xùn)練準(zhǔn)確率都達(dá)到90%以上的時(shí)候，APS采樣要比最遠(yuǎn)點(diǎn)采樣在計(jì)算機(jī)相同的配置下，訓(xùn)練時(shí)間減少了很多，并且意外地發(fā)現(xiàn)用APS采樣僅僅訓(xùn)練了兩個(gè)batch就達(dá)到了90%。這也從側(cè)面反映出APS采樣的計(jì)算復(fù)雜度要比最遠(yuǎn)點(diǎn)采樣小。在同樣的條件下APS采樣要比最遠(yuǎn)點(diǎn)采樣優(yōu)先達(dá)到90%以上的準(zhǔn)確率，而且最終訓(xùn)練結(jié)果的準(zhǔn)確率都接近90.7%，跟PointNet++訓(xùn)練的結(jié)果非常接近。綜上可知，APS采樣在計(jì)算量上要低于最遠(yuǎn)點(diǎn)采樣，而且在覆蓋率也相差無幾。

通過這兩個(gè)實(shí)驗(yàn)不難看出，APS采樣方法比最遠(yuǎn)點(diǎn)采樣和隨機(jī)采樣都有著明顯的優(yōu)勢(shì)，隨機(jī)采樣雖然在時(shí)間上具有一定的優(yōu)勢(shì)，但是在點(diǎn)的覆蓋率上明顯弱于APS采樣和最遠(yuǎn)點(diǎn)采樣，隨著采樣點(diǎn)數(shù)目的減少，對(duì)三維點(diǎn)云的辨識(shí)度也越來越低；最遠(yuǎn)點(diǎn)采樣雖然在點(diǎn)的覆蓋率上和APS采樣相差無幾，但是最遠(yuǎn)點(diǎn)采樣會(huì)隨著采樣點(diǎn)數(shù)量的增加計(jì)算時(shí)間也呈幾何倍數(shù)增加，雖然APS采樣也會(huì)隨著采樣數(shù)量的增加而增加，但是APS采樣是線性增加，因?yàn)锳PS采樣僅僅需要對(duì)所有點(diǎn)進(jìn)行一次排序即可。

2.2mIoU分析

零件分割是一項(xiàng)具有挑戰(zhàn)性的細(xì)粒度三維識(shí)別任務(wù)。給定3D掃描或網(wǎng)格模型，任務(wù)是為每個(gè)點(diǎn)或面指定零件類別標(biāo)簽（例如椅子腿、杯柄）。本文對(duì)ShapeNet零件數(shù)據(jù)集進(jìn)行了評(píng)估，該數(shù)據(jù)集包含16個(gè)類別的16 881個(gè)形狀，共有50個(gè)零件進(jìn)行了注釋。評(píng)估指標(biāo)是mIoU的分?jǐn)?shù)。

在本節(jié)中，將分割版本的多尺度點(diǎn)網(wǎng)（表1的修改版本，分割網(wǎng)絡(luò)）與多種方法進(jìn)行比較，這些方法都利用了逐點(diǎn)幾何特征和形狀之間的對(duì)應(yīng)關(guān)系。在表1中，展示了每個(gè)類別和平均IoU（%）分?jǐn)?shù)。不難發(fā)現(xiàn)平均mIoU相比于其他方法改善了很多。

2.3網(wǎng)絡(luò)模型分析

這一小節(jié)中利用兩組對(duì)比實(shí)驗(yàn)展示模型優(yōu)勢(shì)。第一組實(shí)驗(yàn)是對(duì)比了當(dāng)前比較主流的一些網(wǎng)絡(luò)模型的在訓(xùn)練模型時(shí)保留的最好的模型的準(zhǔn)確率；第二組實(shí)驗(yàn)時(shí)在保持采樣算法不變的情況下，對(duì)比PointNet++網(wǎng)絡(luò)模型和PointPCA網(wǎng)絡(luò)模型在訓(xùn)練時(shí)間的情況。在所有的實(shí)驗(yàn)中，選擇了國際上比較認(rèn)可的ModelNet40（包含40個(gè)類別的CAD模型（主要是人造的），9 843個(gè)形狀用于訓(xùn)練，2 468個(gè)形狀用于測(cè)試）數(shù)據(jù)集作為這次的實(shí)驗(yàn)主要訓(xùn)練和測(cè)試的數(shù)據(jù)集。

a）第一組實(shí)驗(yàn)。如表1所示，列舉了很多現(xiàn)在比較主流的關(guān)于點(diǎn)云分類方面的算法（例如：PointNet、MVCNN、PointNet++、SO-Net、PAT等），由表2不難看出， PointPCA算法在準(zhǔn)確率方面有著一定的優(yōu)勢(shì)，比點(diǎn)云分類的PointNet要高出2.9%的準(zhǔn)確率，比優(yōu)化版的PointNet++高出1.1%的準(zhǔn)確率。雖然提升只有幾個(gè)百分點(diǎn)，但是對(duì)于模型算法，越是達(dá)到90%以上的準(zhǔn)確率，對(duì)于提升就越困難，百分之零點(diǎn)幾的提升對(duì)性能也是質(zhì)的飛躍，而且從之后的其他算法也不難看出，其提升也停留在幾個(gè)百分點(diǎn)上。所以這對(duì)于PointPCA算法來說，也具有很好的意義。從計(jì)算時(shí)間的角度上分析，這里僅比較了PointNet++和PointPCA算法，如表3所示， PointPCA算法在訓(xùn)練時(shí)長(zhǎng)上要優(yōu)于PointNet++算法，主要的原因是網(wǎng)絡(luò)結(jié)構(gòu)和采樣算法，APS采樣算法只在一開始的時(shí)候就對(duì)所有的點(diǎn)進(jìn)行了排序和分類，僅就進(jìn)行一次這很重要，而最遠(yuǎn)點(diǎn)采樣算法的復(fù)雜度是O（N2），與點(diǎn)數(shù)呈平方關(guān)系，很大程度上限制了計(jì)算時(shí)間、提升了計(jì)算法復(fù)雜度；而且PointPCA網(wǎng)絡(luò)結(jié)構(gòu)中可以對(duì)排序的點(diǎn)集重復(fù)使用，也在一定程度上降低了計(jì)算的時(shí)間，避免了點(diǎn)集進(jìn)行多次排序。另外還發(fā)現(xiàn)了一個(gè)比較有趣的事情，那就是PointPCA網(wǎng)絡(luò)在訓(xùn)練的一開始就非常接近90%的準(zhǔn)確率，猜測(cè)這是因?yàn)锳PS采樣算法在選取采樣點(diǎn)時(shí)存在著特殊的關(guān)系，導(dǎo)致選取的采樣點(diǎn)的特征跟三維點(diǎn)云所表示的物體的特征非常接近。

b）第二組實(shí)驗(yàn)。PointPCA網(wǎng)絡(luò)模型中的APS采樣算法替換為最遠(yuǎn)點(diǎn)采樣，與PointPCA算法進(jìn)行對(duì)比，在準(zhǔn)確率和計(jì)算時(shí)間上進(jìn)行比較。如表3所示，表中第2列比較了PointNet++和Point PCA方法達(dá)到90%精度所需的時(shí)間，第3列比較了這三種算法產(chǎn)生最佳模型所需的時(shí)間，第4列比較了最佳模型的準(zhǔn)確性。表3記錄了出現(xiàn)最好模型的時(shí)間，以及出現(xiàn)最好模型的準(zhǔn)確率。這里所有的時(shí)間都是一個(gè)粗略的數(shù)字，而不是一個(gè)特定的時(shí)間，不同機(jī)器之間可能會(huì)有不同程度的差別。從表中不難發(fā)現(xiàn)，網(wǎng)絡(luò)模型在一定程度上有一定的優(yōu)勢(shì)；從時(shí)間的角度上分析，采用APS采樣方法出現(xiàn)最優(yōu)模型的時(shí)間要比采用最遠(yuǎn)點(diǎn)采樣算法要早一些，進(jìn)一步印證了APS采樣方法在計(jì)算時(shí)間上具有一定的優(yōu)勢(shì)。

2.4結(jié)論

本文提出了PointPCA，其為一種用于處理度量空間中點(diǎn)云的卷積神經(jīng)網(wǎng)絡(luò)算法。為減少計(jì)算冗余，降低采樣到重復(fù)點(diǎn)的概率，本文提出了新的采樣方法APS。為了可以提取到輸入點(diǎn)云更多的特征信息，采用了一種多尺度的分層卷積神經(jīng)網(wǎng)絡(luò)提取點(diǎn)云的特征信息，將每一個(gè)尺度提取到的特征信息拼接整合到一起。從實(shí)驗(yàn)結(jié)果也不難看出，網(wǎng)絡(luò)在準(zhǔn)確率、mIoU和效率方面都有著明顯的優(yōu)勢(shì)。

3結(jié)束語

本文提出的PointPCA網(wǎng)絡(luò)模型以及配合使用APS算法，在準(zhǔn)確率和訓(xùn)練時(shí)長(zhǎng)上都存在一定的優(yōu)勢(shì)。首先，分析了PointNet和PointNet++的優(yōu)勢(shì)以及這種網(wǎng)絡(luò)模型存在的問題。然后，從中分析出最遠(yuǎn)點(diǎn)采樣是導(dǎo)致計(jì)算量增加的重要原因；最后設(shè)計(jì)了APS采樣算法來代替最遠(yuǎn)點(diǎn)采樣，解決了計(jì)算時(shí)間過長(zhǎng)的問題；不僅如此，本文還在PointNet++網(wǎng)絡(luò)模型的基礎(chǔ)上對(duì)其進(jìn)行了優(yōu)化，使其在提取特征時(shí)可以更充分地提取到三維點(diǎn)云的特征信息，并在PointNet++準(zhǔn)確率為90.7%的基礎(chǔ)上提升了1.1%的準(zhǔn)確率，達(dá)到了91.8%的準(zhǔn)確率，超越了很多關(guān)于三維點(diǎn)云的網(wǎng)絡(luò)模型。為了進(jìn)一步證實(shí)算法的優(yōu)越性，從計(jì)算時(shí)間、采樣方法、訓(xùn)練的準(zhǔn)確率等方面都設(shè)置了實(shí)驗(yàn)，來證明算法確實(shí)存在一定的可行性和優(yōu)勢(shì)。

參考文獻(xiàn)：

［1］Zhang Feihu，F(xiàn)ang Jin，Wah B，et al.Deep fusionnet for point cloud semantic segmentation［C］//Proc of the 16th European Conference on Computer Vision.Berlin：Springer，2020：644-663.

［2］Ma Yanni，Guo Yulan，Liu Hao，et al.Global context reasoning for semantic segmentation of 3D point clouds［C］//Proc of IEEE/CVF Winter Conference on Applications of Computer Vision.Piscataway，NJ：IEEE Press，2020：2931-2940.

［3］Zhao Na，Chua T S，Lee G H.Few-shot 3D point cloud semantic segmentation［C］//Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2021：8873-8882.

［4］Gul S，F(xiàn)ulaly M S，Khan M S，et al.Clustering of spatial cues by semantic segmentation for anechoic binaural source separation［J］.Applied Acoustics，2021，171：107566.

［5］Benini S，Khan K，Leonardi R，et al.FASSEG：a face semantic segmentation repository for face image analysis［J］.Data in Brief，2019，24：103881.

［6］Wu Yichen，Rivenson Y，Zhang Y，et al.Extended depth-of-field in holographic imaging using deep-learning-based autofocusing and phase recovery［J］.Computer Vision and Pattern Recognition，2018，5（6）：704-710.

［7］李強(qiáng)，高保祿，竇明亮.基于多重特征匹配的點(diǎn)云配準(zhǔn)算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2020，37（2）：588-592.（Li Qiang，Gao Baolu，Dou Mingliang.Point cloud registration algorithm based on multiple-feature matching［J］.Application Research of Computers，2020，37（2）：588-592.）

［8］張京軍，鄭燦，高瑞貞.學(xué)習(xí)點(diǎn)云鄰域信息的三維物體形狀補(bǔ)全 ［J］.計(jì)算機(jī)應(yīng)用研究，2022，39（5）：1586-1589.（Zhang Jingjun，Zheng Can，Gao Ruizhen.3D object shape completion under learning point cloud neighborhood information［J］.Application Research of Computers，2022，39（5）：1586-1589.）

［9］魏天琪，鄭雄勝.基于深度學(xué)習(xí)的三維點(diǎn)云分類方法研究［J］.計(jì)算機(jī)應(yīng)用研究，2022，39（5）：1289-1296.（Wei Tianqi，Zheng Xiongsheng.Research of deep learning-based classification methods for 3D point cloud ［J］.Application Research of Computers，2022，39（5）：1289-1296.）

［10］Qi C R，Su Hao，Mo Kaikun，et al.PointNet：deep learning on point sets for 3D classification and segmentation［C］//Proc of IEEE Confe-rence on Computer Vision and Pattern Recognition.Washington DC：IEEE Computer Society，2017：652-660.

［11］Qi C R，Yi Li，Su Hao，et al.PointNet++：deep hierarchical feature learning on point sets in a metric space［C］//Proc of Annual Confe-rence on Neural Information Processing Systems.Red Hook：Curran Associates，2017：5099-5108.

［12］Zhao Hengshuang，Jiang Li，F(xiàn)u C W，et al.PointWeb：enhancing local neighborhood features for point cloud processing［C］//Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition.Pisca-taway，NJ：IEEE Press，2019：5560-5568.

［13］Li Yangyan，Bu Rui，Chen Baoquan，et al.PointCNN：convolution on x-transformed points［C］//Proc of Annual Conference on Neural Information Processing Systems.Montreal：Curran Associates Inc.，2018：828-838.

［14］Klokov R，Lempitsky V.Escape from cells：deep Kd-networks for the recognition of 3D point cloud models［C］//Proc of IEEE International Conference on Computer Vision.Piscataway，NJ：IEEE Press，2017：863-872.

［15］Tchapmi L P，Choy C B，Armeni I，et al.SegCloud：semantic segmentation of 3D point clouds［C］//Proc of International Conference on 3D Vision.2017：537-547.

［16］Liu Fangyu，Li Shuaipeng，Zhang Liqiang，et al.3DCNN-DQN-RNN：a deep reinforcement learning framework for semantic parsing of large- scale 3D point clouds［C］//Proc of IEEE International Conference on Computer Vision.Washington DC：IEEE Computer Society，2017：5678-5687.

［17］Su Hang，Maji S，Kalogerakis E，et al.Multi-view convolutional neural networks for 3D shape recognition［C］//Proc of IEEE International Conference on Computer Vision.Washington DC：IEEE Computer Society，2015：945-953.

［18］Li Jiaxin，Chen B M，Lee G H.SO-Net：self-organizing network for point cloud analysis［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Washington DC：IEEE Computer Society，2018：9397-9406.

［19］Te Gusi，Hu Wei，Guo Zongming，et al.RGCNN：regularized graph CNN for point cloud segmentation［C］//Proc of the 26th ACM International Conference on Multimedia.New York：ACM Press，2018：746-754.

［20］Yang Jiancheng，Zhang Qiang，Ni Bingbing，et al.Modeling point clouds with self-attention and gumbel subset sampling［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Pisca-taway，NJ：IEEE Press，2019：3323-3332.

［21］Wang Chu，Samari B，Siddiqi K.Local spectral graph convolution for point set feature learning［C］//Proc of the 15th European Conference on Computer Vision.Berlin：Springer，2018：56-71.

收稿日期：2022-03-15；修回日期：2022-06-21

作者簡(jiǎn)介：季鈺林（1995-），男，山東人，碩士研究生，主要研究方向?yàn)橹悄軋D像處理、人工智能、通信與信息系統(tǒng)（416954129@qq.com）；鐘劍丹（1985-），男，講師，博士后研究員，主要研究方向?yàn)槿斯ぶ悄芘c圖像處理；李英祥（1972-），男，教授，主要研究方向?yàn)檫吘売?jì)算、人工智能、SOC與片上系統(tǒng)、通信終端、物聯(lián)網(wǎng)技術(shù)、微弱信號(hào)處理等；傅俊杰（1996-），男，湖南人，碩士研究生，主要研究方向?yàn)橹悄軋D像處理、人工智能、通信與信息系統(tǒng)；劉家威（1995-），男，四川人，碩士研究生，主要研究方向?yàn)橹悄軋D像處理、人工智能、嵌入式系統(tǒng)與物聯(lián)網(wǎng)技術(shù)．