張學典,方 慧
(上海理工大學 光電信息與計算機工程學院,上海 200093)
三維激光掃描、二維影像的三維重建、三維模型逆向點云獲取點云數(shù)據(jù)的方法不斷發(fā)展,三維成像技術日趨成熟,三維點云運用場景越來越廣泛,如室內(nèi)導航[1]、機器人[2]、自動駕駛[3]、三維重建[4],均需要對點云進行高級處理和分析.最近,學者們發(fā)布了一系列深度學習架構(gòu)應用在點云上的相關研究,主要分為以下三類深度學習方法:基于多視圖的方法、基于體素網(wǎng)格的方法和基于三維幾何數(shù)據(jù)的方法.在多視圖中,Wei等[5]通過將多個視圖視為grpah節(jié)點,在View-GCN中使用了有向圖.然后將由局部圖卷積、非局部消息傳遞和選擇性視圖采樣組成的核心層應用于所構(gòu)建的圖.所有級別的最大集合節(jié)點特征的連接最終用于形成全局形狀描述符,但得到的結(jié)果丟失了大量的空間幾何信息.為了解決點云稀疏、無結(jié)構(gòu)、無序的缺陷,OctNet[6]采用位串表征進行編碼,通過簡單的算法索引每個體素的特征向量,文獻[7-11]也對體素網(wǎng)格進一步改進,但都存在大量的無效、冗余的信息,大大增加了計算量,空間復雜度高.
所以精確地分類和分割點云仍然是一個挑戰(zhàn).已有的PointNet[12]、PointNet++[13]模型均是直接對點云數(shù)據(jù)進行處理,注重獨立提取點云特征而忽略了點之間的幾何關聯(lián),從而丟失了許多局部特征.同樣地,PAConv[14]利用了PointNet++的點云預處理模塊,仍存在局部特征丟失的缺陷.因此,DGCNN[15]和LDGCNN[16]提出了相關的邊卷積來解決這個問題,然而,在實驗過程中發(fā)現(xiàn),這兩種方法仍丟失了邊緣向量.
為了解決這些問題,本文提出了面向三維點云拓撲結(jié)構(gòu)的BallTree動態(tài)圖卷積神經(jīng)網(wǎng)絡,意在探索一種深度學習架構(gòu),以便能夠有效地提取三維點云的拓撲結(jié)構(gòu)信息.由于本文的方法利用balltree[17]圖來尋找鄰點,生成動態(tài)圖,所以稱之為BTDGCNN.為了捕捉特征之間的幾何關聯(lián),本文提出了BAT邊卷積用于捕獲局部幾何結(jié)構(gòu),同時保持不變性.為了提高非結(jié)構(gòu)化點云的處理效率,提出了Bat-Net模塊,實現(xiàn)點云空間對齊.在實驗中,本文在ModelNet40[18]以及ShapeNet[19]兩個公開數(shù)據(jù)集上評估BTDGCNN網(wǎng)絡.實驗結(jié)果表明,本文的方法有效提升了點云分類分割性能,三維點云拓撲結(jié)構(gòu)的信息提取能力得到增強.
PointNet是第1個直接處理原始點云的深度學習網(wǎng)絡,該網(wǎng)絡直接將點云作為輸入,連接逐點特征和聚集的全局特征,以進行逐點預測,進而實現(xiàn)對三維數(shù)據(jù)的分類與分割,但其不能捕捉到由度量空間所產(chǎn)生的局部結(jié)構(gòu),限制了PointNet識別細粒度模式的能力以及對復雜場景的泛化能力.而分層神經(jīng)網(wǎng)絡PointNet++,一種新的集合學習層來自適應地組合多尺度特征,但該網(wǎng)絡的卷積不適用于具有距離度量的無序點集.盡管PCNN[20]應用于點云中的每個點,以學習逐點特征,利用點云中表示的數(shù)據(jù)的空間局部相關性,將三維點云運用到大規(guī)模物體檢測,但固有地缺乏點云拓撲結(jié)構(gòu)信息.而用來恢復拓撲結(jié)構(gòu)的DGCNN和LDGCNN雖然可以豐富點云的表示能力,但在實驗的過程中,丟失了距離向量.
因此,本文提出了一種面向三維點云拓撲結(jié)構(gòu)的BallTree動態(tài)圖卷積神經(jīng)網(wǎng)絡,并不是像PointNet和PointNet++逐點提取點云特征,也與PCNN逐點卷積不同,是結(jié)合DGCNN的邊卷積,同時利用相鄰節(jié)點對之間的邊以及該節(jié)點共同的作用,通過圖神經(jīng)網(wǎng)絡構(gòu)建局部有向圖.與DGCNN不同之處在于,其對每對點進行pairwise的距離計算找出K最近鄰點,所以速度比較慢,無法對高維數(shù)據(jù)進行處理,并且在實驗過程中丟失了距離向量.類似地,楊永濤等利用曲率和立方體素柵格計算點云的距離無法在曲率較小的點云上表現(xiàn).而本文通過balltree在一系列嵌套的超球體上分割數(shù)據(jù),在三維數(shù)據(jù)上表現(xiàn)很高效.此外,本文只利用3個邊卷積層進行點云的分割與分類,實現(xiàn)輕量級網(wǎng)絡,利用PointNet與LDGCNN的分類和分割思路,構(gòu)建了面向三維點云拓撲結(jié)構(gòu)的BallTree動態(tài)圖卷積神經(jīng)網(wǎng)絡(BTDGCNN),在ModelNet40與ShapeNet 數(shù)據(jù)集上表現(xiàn)了較好的分類與分割結(jié)果,提升了三維點云的拓撲結(jié)構(gòu)信息獲取能力.在下文中,將討論相關研究問題及相應的解決方案.
在本節(jié)中,對圖生成、圖特征提取、balltree與Bat-Net、邊卷積模塊以及BTDGCNN架構(gòu)進行詳細闡述.
本文方法中,以一組三維點云作為輸入:
pi={(xi,yi,zi)|i=1,2,…,n)}
(1)
其中,pi是點云中的一個點,由(xi,yi,zi)這3個表示位置信息的坐標組成,i和n分別表示點的索引下標與點個數(shù).
本文主要研究任務為:點云的分類與分割.對于點云分類,本文需要對點云進行處理,通過BTDGCNN模型找到了一個分類函數(shù)fc,從而對整個點云進行分類,將輸入點云轉(zhuǎn)換為每個類別上的概率分布pθ:
pθ=fc({p1,p2,…,pn})
(2)
對于點云分割,每個點都可以歸為一個特定的類別.因此通過BTDGCNN模型找到了一個分割函數(shù)fs,以計算每個點pi的類別的每種類別pθi的概率分布:
{pθi|i=1,2,…,n}={fs(pi)|i=1,2,…,n}
(3)
圖神經(jīng)網(wǎng)絡適用于處理點云,正是因為其可以獨立地在每個節(jié)點上傳播,節(jié)點輸入順序不受影響,并且可以通過提取邊以學習兩節(jié)點之間的依賴信息.為了將圖神經(jīng)網(wǎng)絡應用在點云上,首要的是需將點云轉(zhuǎn)換成有向圖.圖G包括頂點V和邊E:
G=(V,E)
(4)
其中頂點V={1,…,n}和邊E?V×V.
由于會消耗大量內(nèi)存,所以本文不為點云構(gòu)建完全連接的邊,如圖1所示,本文利用balltree圖構(gòu)造一個局部有向圖,
圖1 Balltree圖搜索最近鄰
在該圖中,搜索點p的半徑為r的最近鄰,即滿足‖p-pt‖≤r(其中pt是搜索的目標點),從根節(jié)點p開始從上至下遞歸遍歷每個可能包含最終近鄰的子空間pc,如果子空間的半徑radius(pc)與r之和小于或等于pc中心點center(pc)到目標點p的距離,即(radius(pc)+r)≤‖center(pc)-p‖,就在滿足該條件的子空間樣本點內(nèi)遞歸搜索滿足‖p-d‖≤r的點即為本文所需最近鄰點,對于目標空間(p,r),遍歷搜索所有被該超球體截斷的子超球體內(nèi)的所有子空間,由于子超球體Ⅰ與Ⅱ被p所截,而對于Ⅰ與Ⅱ內(nèi)的子空間,Ⅳ,Ⅷ,Ⅵ,又被p所截,所以接下來就會在Ⅳ,Ⅷ,Ⅵ內(nèi)進行線性搜索,諸如Ⅲ,Ⅴ,Ⅶ這些距離太遠的子空間將被舍去,最終得到最近鄰為[p4,p6],接下來,就可以在歐氏空間和特征空間中構(gòu)造局部圖.其中,Ⅰ~Ⅷ為子空間,p為根節(jié)點,pi(i=1,…,n)為空間中的點.
算法1說明了balltree圖的鄰域搜索神經(jīng)網(wǎng)絡算法,其中pn表示到目前為止找到的一系列可以作為目標點pt的最近鄰點,ds是目標點與之前發(fā)現(xiàn)節(jié)點的最小距離(ds=maxp∈pn|p-pt|),dc表示目標點pt與當前節(jié)點pcn間的距離(dc=max{dR·Parent|pt-center(R)|-radius(R)}),R是整個搜索區(qū),K是限定的列表大小.
算法1.balltree圖鄰域搜索神經(jīng)網(wǎng)絡算法
1.程序開始 搜索(pn,pcn,r,K)
2.如果滿足(dc>=ds∧dc>r)
3. 則返回pn
4.如果pcn是一個葉子節(jié)點
5. 則pout=pn
6.對于?p∈points(pcn),如果滿足(|p-pt| 7. 則將p添加到pout 8.如果滿足(|pout|==K+1) 9. 則從pout移除離它最遠的節(jié)點,并更新ds 10.否則dr=以childr為中心的距離 12.dl=以childl為中心的距離 13.ptemp=pn 14.如果(dr<=radius(childr(pcn))+r) 15. 則ptemp=搜索(pn,childr,r) 16.如果(dl<=radius(childl(pcn))+r) 17. 則pout=搜索(ptemp,childl,r) 為了改進KDtree的二叉樹樹形結(jié)構(gòu),并且沿著笛卡爾坐標進行劃分的低效率,balltree將在一系列嵌套的超球體上分割數(shù)據(jù),使用超球面而不是超矩形劃分區(qū)域.雖然在構(gòu)建數(shù)據(jù)結(jié)構(gòu)的花費上大過于KDtree,但是在三維甚至很高維的數(shù)據(jù)上都表現(xiàn)的很高效.球樹遞歸地將數(shù)據(jù)劃分為由質(zhì)心p和半徑r定義的節(jié)點,使得節(jié)點中的每個點都位于由r和p定義的超球內(nèi).通過使用三角不等式來減少鄰居搜索的候選點數(shù)量.如圖1所示,選擇一個距離當前圓心最遠的觀測點i1,和距離i1最遠的觀測點i2,將圓中所有離這兩個點最近的觀測點都賦給這兩個簇的中心,然后計算每一個簇的中心點和包含所有其所屬觀測點的最小半徑,不斷遞歸得到最近鄰點,最終構(gòu)建balltree. 當使用balltree查詢時,如圖2所示,先自上而下找到包含目標的葉子結(jié)點(p,r),從此結(jié)點中找到離它最近的觀測點,該距離即為最近鄰的距離的上界.檢查它的兄弟結(jié)點中是否包含比這個上界更小的觀測點,方法是:如果目標點距離兄弟結(jié)點的圓心的距離>兄弟節(jié)點所在的圓半徑+前面的上界的值,若滿足上述條件,則這個兄弟結(jié)點不可能包含所要的觀測點.否則,檢查這個兄弟結(jié)點是否包含符合條件的觀測點. 圖2 balltree樹查詢過程 本文設計的Bat-Net變換網(wǎng)絡就是利用balltree圖為每個點云估計特定的矩陣,首先無序點云以n×3矩陣形式輸入到對齊空間,然后利用balltree圖搜索最近鄰,連接每個點的坐標與其最近鄰點之間坐標的半徑r的張量,形成一個3×3的矩陣,最終通過矩陣乘法,產(chǎn)生一個已經(jīng)由Bat-Net變換網(wǎng)絡處理過的n×3的輸入點云(矩陣M),可以偏置點云P: (5) 其中,mij是旋轉(zhuǎn)矩陣中第i和第j列的值,xi,yi,zi是點云P的其中一個點云pi的坐標. 一個C維n點云,P={p1,…,pn}?RC,在最簡單的三維設置中,每個點都包含三維坐標pi={(xi,yi,zi)|i=1,2,…,n)},還可以包括表示顏色、表面法線等附加坐標.在深度神經(jīng)網(wǎng)絡架構(gòu)中,每個后繼層都是在前一層輸出結(jié)果的基礎上進行操作,因此,進一步推廣到一般情境中,C代表給定層的特征維度. 與DGCNN中邊卷積模塊不同的是,本文計算表示局部點云結(jié)構(gòu)的有向圖G,在最簡單的C=3的情況下,構(gòu)造G作為點云P的balltree圖,包括自循環(huán),圖中的每個節(jié)點V也都會指向節(jié)點本身.在第i個頂點處的邊卷積輸出見式(6): p′i=△hθ(pi,pj) (6) 如上所述,定義邊緣特征為eij=hθ(pi,pj),其中hθ:RC×RC→RC′是帶有一組可學習參數(shù)Θ的非線性函數(shù),pi,pj則是有向圖中的兩個節(jié)點.然后,定義邊卷積操作△,通過從每個頂點發(fā)出的所有邊相關聯(lián)的邊特征上應用通道對稱聚集操作來進行定義,p′i表示在第i個頂點處的邊卷積. BAT邊卷積可以很好地獲取輸入點云的局部特征,然而,如果在BTDGCNN中單純地增加BAT邊卷積層數(shù),經(jīng)實驗驗證,并不能提高對點云的分類與分割效果,反而伴隨著BAT邊卷積層數(shù)的增加出現(xiàn)較差的分類與分割效果的現(xiàn)象,該內(nèi)容將會在本文的第4節(jié)實驗中詳細闡明. 本文的BTDGCNN架構(gòu)如圖3所示,可以分為兩部分,即分類和分割,它們共享很大一部分結(jié)構(gòu). 分類部分包括: 1)輸入層:具有n個點的n×3點云模型作為輸入,每個點由坐標組成,還可以有表示顏色、表面法線等附加坐標. 2)Bat-Net轉(zhuǎn)換層:如果點云在經(jīng)歷某些幾何變換后必須是不變的,那么本文期望,輸入點云可以通過Bat-Net轉(zhuǎn)換層學習后的表征對于這些變換是不變的.Tong等[21]利用空間轉(zhuǎn)換器思想,通過采樣和插值來對齊二維圖像,從而將點云對齊到一個規(guī)范空間中,以便于提取特征.本文通過一個Bat-Net小型網(wǎng)絡來預測仿射變換矩陣,并將該變換用于輸入點云坐標.在該網(wǎng)絡中,首先利用balltree圖連接每個點的坐標及其相鄰點之間坐標差的張量,經(jīng)估計后將3×3矩陣將輸入點集對齊到規(guī)范空間,最終輸出一個經(jīng)過對齊空間的n×3點云. 3)BAT邊卷積層:本文的BTDGCNN網(wǎng)絡共有3個BAT邊卷積層,這3個BAT邊卷積層輸入通道數(shù)分別為3、128、128,輸出通道數(shù)分別為128、128、256. 4)最大池化層:該網(wǎng)絡輸出為每個通道的前k個最大值,然后將其一維化,從而得到一維張量(k×1024). 分割部分包括局部特征與全局特征聚合器:點云分類與分割需要結(jié)合局部以及全局特征,本文通過PointNet中的簡單且高效的方式實現(xiàn).如圖3中分割模塊所示,計算點云的全局特征向量后,將全局特征向量與每個點的特征向量連接,然后反饋給每個點特征.接下來,通過這些組合的點特征,提取新的每個點特征,這個新的點特征即為局部和全局信息.依賴這種方式,本文網(wǎng)絡能夠預測每點數(shù)量.本文將會在分割實驗部分進行詳細展示. 圖3 BTDGCNN網(wǎng)絡架構(gòu) 為了驗證BTDGCNN優(yōu)化網(wǎng)絡的可行性和優(yōu)越性,本文選用ModelNet40數(shù)據(jù)集和ShapeNet Parts數(shù)據(jù)集這兩個數(shù)據(jù)集來進行分割與分類實驗驗證.并與其他已有的網(wǎng)絡模型,如PointNet、PointNet++、PCNN、DGCNN、LDGCNN進行性能比較,實驗分為以下4個模塊:點云可視化、點云分類實驗、點云分割實驗、BTDGCNN模型復雜度分析. 本文使用T分布隨機鄰域嵌入(T-SNE)來顯示特征提取器的性能,減少高維特征的維度來可視化特征.如圖4所示,每種顏色代表一個類別,對于不相似的點,用一個較小的距離產(chǎn)生較大的梯度來讓這些點排斥開來,而這種排斥又不會無限大,避免不相似的點距離太遠.通過圖4可以直觀地看到提取特征后的點云分別按照顏色分類并且以較小距離排斥開,比原始點云更具區(qū)分性,顯示了較強的提取拓撲結(jié)構(gòu)信息能力. 圖4 原始點云和特征提取的T-SNE可視化 4.2.1 數(shù) 據(jù) 本文在ModelNet40數(shù)據(jù)集上進行點云分類實驗,包括40類CAD模型,將其中9843個形狀用于訓練,2468個形狀用于測試,在該數(shù)據(jù)集中采樣1024個點,并且預測之前從未見過的形狀的類別.另外,為了提高網(wǎng)絡的泛化能力,對于每一批次的點云模型都需要對其進行旋轉(zhuǎn)操作,隨機縮放點云以及丟棄點云中不需要的點.并且在訓練過程中,通過隨機縮放對象和點的位置來增加數(shù)據(jù). 4.2.2 架 構(gòu) 如圖3中分類網(wǎng)絡所示,本文使用3層BAT邊卷積層來提取點云的幾何特征,基于每個BAT邊卷積層提取的特征進行計算,并將計算得到的新圖用于下一層卷積層.利用MLP得到n×1024的高維特征采樣點,以保證動態(tài)圖更新的同時,可以將語義上特征相近的點聚合,來提取不同層級的點云的局域特征信息.然后,將全局特征與各個BAT邊卷積層中提取的局部特征信息進行拼接,以聚合多尺度要素.通過最大池化操作獲得1×1024的全局特征.最終通過一個3層的MLP將所有特征信息融合,并對高維特征降維,輸出分類分數(shù)p. 4.2.3 訓 練 本文模型進行訓練的實驗參數(shù)設置如表1所示,硬件環(huán)境為dellt640-PowerEdge-T640電腦、英特爾Intel? Xeon(R)Silver 4210 CPU@2.20GHz×40處理器、30.9 GiB運行內(nèi)存. 表1 實驗參數(shù)設置 4.2.4 結(jié) 果 由表2和圖4可知,本文模型在ModelNet40數(shù)據(jù)集上取得了最好的分類結(jié)果.對于相同的輸入點云(1024點),在同一軟硬件環(huán)境下,BTDGCNN的整體分類準確率(OA)為93.6%,相比PointNet高出了4.4個百分點,比PointNet++高出了2.9個百分點,比PCNN高出了1.3個百分點,這充分說明了本文的BTDGCNN網(wǎng)絡可以很好地實現(xiàn)三維點云的分類任務.比DGCNN高出2個百分點,表明網(wǎng)絡深度合適時(本文卷積層為3層),點云分類才能達到最好的效果.比LDGCNN高1.4個百分點,更加展現(xiàn)了本文的BTDGCNN模型在提升網(wǎng)絡精度上的極佳能力. 表2 對于相同的輸入點云(1024點),不同模型在ModelNet40上的分類結(jié)果 通過實驗可以發(fā)現(xiàn),在圖5中,當?shù)螖?shù)增加,模型在ModelNet40數(shù)據(jù)集上分類的精度擬合程度越來越好,可以達到93.6%,但隨著迭代次數(shù)持續(xù)增加,過擬合問題隨之而來,導致模型的泛化能力下降.通過對比實驗發(fā)現(xiàn),當?shù)螖?shù)為250時,模型的分類能力最強,高于其他4類方法. 圖5 分類訓練、測試精度曲線 4.3.1 數(shù) 據(jù) 本文基于ShapeNet Parts數(shù)據(jù)集評估點云分割模型,該數(shù)據(jù)集中共由16881個形狀,包括16個類別以及50個部件,其中16個類分別為飛機(2690個)、背包(76個)、帳篷(55個)、汽車(898個)、椅子(3758個)、電話(69個)、吉他(787個)、小刀(392個)、臺燈(1547個)、手提電腦(451個)、摩托車(202個)、茶杯(184個)、手槍(283個)、火箭(66個)、滑板(152個)、桌子(5271個).此外,在ShapeNet Parts數(shù)據(jù)集上采樣2048個點用于分割實驗. 4.3.2 架 構(gòu) 點云分割架構(gòu)如圖3中分割網(wǎng)絡所示,分割網(wǎng)絡是分類網(wǎng)絡的擴展,本文將各層提取的局部特征與全局特征疊加,并使用MLPs來計算每個點的割分數(shù).最后,在每一層中應用RELU和Batchnorm,以實現(xiàn)對點云的歸一化操作,并且在MLP層后面設置值為0.5的Dropout層,以達到可以比較有效的緩解過擬合的發(fā)生,在一定程度上達到正則化的效果. 4.3.3 訓 練 點云分割實驗的設置采用與分類實驗相同的訓練設置. 4.3.4 結(jié) 果 本文使用所有類的均交并比(mIoU)來對語義分割結(jié)果進行評估,其中,所有類的交并比(IoU)按照下式進行計算: (7) 其中,TP(真正),預測正確,預測結(jié)果是正類,真實是正類;FP(假正),預測錯誤,預測結(jié)果是正類,真實是負類;FN(假負),預測錯誤,預測結(jié)果是負類,真實是正類;TN(真負),預測正確,預測結(jié)果是負類,真實是負類. 將本文的分割結(jié)果與PointNet、PointNet++、PCNN、DGCNN、LDGCNN進行比較,由表3可知,本文的語義分割的平均交并比相比PointNet高出1.7個百分點,比PointNet++高出0.3個百分點,說明本文的BTDGCNN網(wǎng)絡對輸入無序點云進行處理,可以提高網(wǎng)絡整體效率.相比PCNN,DGCNN和LDGCNN均高出0.3個百分點,表明通過3層輕量級BAT邊卷積模塊,可以獲得更佳的點云特征用于分割. 表3 ShapeNet數(shù)據(jù)集上分割的結(jié)果.表中的值是points的mIoU(%) 本文使用ModelNet40分類實驗來比較模型的復雜度,表4表明,相比PointNet++與LDGCNN,本文的BTDGCNN網(wǎng)絡參數(shù)數(shù)量分別多了0.3MB,0.7MB,主要是因為本文相比其增加了Bat-Net輸入點云轉(zhuǎn)換模塊.與PointNet和DGCNN比較,本文提出的網(wǎng)絡參數(shù)數(shù)量分別少了1.7MB,0.06MB,主要在于本文減少了卷積層(本文僅3層BAT邊卷積模塊),最終使得本文的BTDGCNN模型結(jié)果在分類精度上達到了最佳平衡. 表4 不同模型的參數(shù)數(shù)量、轉(zhuǎn)發(fā)時間以及精確度度 針對三維點云在進行分類分割任務時,對拓撲結(jié)構(gòu)信息提取能力弱以及數(shù)據(jù)無序且龐大的缺陷,本文提出了一種面向三維點云拓撲結(jié)構(gòu)的BallTree動態(tài)圖卷積神經(jīng)網(wǎng)絡.通過增加一個Bat-Net轉(zhuǎn)換模塊來對輸入無序點云進行處理,提高網(wǎng)絡整體效率,以及設計3層BAT邊卷積模塊,簡化了網(wǎng)絡的復雜程度,以獲得的更佳的點云特征用于三維點云的分類及分割.在ModelNet與ShapeNet數(shù)據(jù)集上的實驗表明,本文的BTDGCNN網(wǎng)絡已經(jīng)達到了較好的三維點云拓撲結(jié)構(gòu)的信息提取能力.此外,本文還提供了網(wǎng)絡的理論分析以及可視化的分類和分割結(jié)果. 未來,本文將考慮把BTDGCNN網(wǎng)絡應用于更抽象的點云以及實時環(huán)境理解,通過對本文網(wǎng)絡的進一步改進,使其能夠?qū)Ω呔S的點云進行實驗,并且將其適用于現(xiàn)實點云場景的語義分割.2.3 balltree與Bat-Net變換網(wǎng)絡
2.4 BAT邊卷積模塊
3 BTDGCNN架構(gòu)
4 實 驗
4.1 點云可視化
4.2 點云分類實驗
4.3 點云分割實驗
4.4 BTDGCNN復雜度分析
5 結(jié) 論