張 婧，周明全，耿國(guó)華

西北大學(xué) 文化遺產(chǎn)數(shù)字化國(guó)家地方聯(lián)合工程研究中心，西安 710127

1 引言

隨著深度學(xué)習(xí)的發(fā)展，在計(jì)算機(jī)視覺(jué)領(lǐng)域中如何將具有無(wú)序性的點(diǎn)云數(shù)據(jù)表示成深度學(xué)習(xí)網(wǎng)絡(luò)可以接收的有序數(shù)據(jù)結(jié)構(gòu)，用于深度學(xué)習(xí)的訓(xùn)練是亟待解決的問(wèn)題。現(xiàn)階段深度學(xué)習(xí)被廣泛地用于2D 圖像特征提取，并且在大多數(shù)圖像分析和理解任務(wù)中，已經(jīng)證明它們優(yōu)于傳統(tǒng)算法的解決方案。在點(diǎn)云的深度學(xué)習(xí)中，主要的解決方法是將3D模型轉(zhuǎn)換為規(guī)則的2D圖像表示，將用于2D 圖像的深度學(xué)習(xí)方法應(yīng)用于不規(guī)則3D 模型。如何表達(dá)三維模型能夠?qū)崿F(xiàn)點(diǎn)云在深度學(xué)習(xí)中的端到端的輸入而不需要把三維3D數(shù)據(jù)轉(zhuǎn)換為2D圖像，是本文要解決的問(wèn)題。點(diǎn)云數(shù)據(jù)的另一個(gè)特點(diǎn)是海量性，如何對(duì)大規(guī)模的無(wú)序的點(diǎn)云模型進(jìn)行有效的三維表示與管理，為后期模型數(shù)據(jù)的分析提供基礎(chǔ)，是另一個(gè)亟待解決的問(wèn)題。

為解決以上問(wèn)題，本章提出基于八叉樹(shù)和三維K-D樹(shù)的集成索引（OctKD）的點(diǎn)云數(shù)據(jù)表示方法。本文的主要貢獻(xiàn)是：

（1）提出一種深度學(xué)習(xí)卷積神經(jīng)網(wǎng)絡(luò)可以接受的，能夠端到端表示點(diǎn)云模型的OctK數(shù)據(jù)結(jié)構(gòu)。

（2）OctKD 的點(diǎn)云模型表示方法，能夠真實(shí)反映模型本身的細(xì)節(jié)特征。

（3）提出一種新穎的完全在GPU 端以并行方式構(gòu)造八叉樹(shù)的算法，降低了點(diǎn)云模型的構(gòu)造時(shí)間。

（4）針對(duì)點(diǎn)云模型的散亂性，采用三維K-D 樹(shù)索引單個(gè)三維空間點(diǎn)，提高點(diǎn)云檢索效率。

2 相關(guān)研究

點(diǎn)云模型目前常用的表示方法有多視圖、體素和點(diǎn)云結(jié)構(gòu)?；谝晥D的表示方法[1-5]首先從具有固定視點(diǎn)的原始對(duì)象獲取2D 視圖，然后將這些視圖作為對(duì)象信息，利用圖像處理中的一些成熟的方法來(lái)處理這些圖像，并從中提取特征?；谝晥D的方法由于其靈活性和良好的性能而引起人們的極大關(guān)注。多視圖卷積神經(jīng)網(wǎng)絡(luò)把三維模型轉(zhuǎn)換為二維圖像，然后應(yīng)用二維卷積網(wǎng)絡(luò)處理，但3D數(shù)據(jù)的計(jì)算量將會(huì)極大的增加，就是所謂的“維數(shù)災(zāi)難”。目前比較常用的是基于體素的表示，Wu 等人[6]提出ShapeNets，是第一個(gè)將卷積神經(jīng)網(wǎng)絡(luò)應(yīng)用于三維表示，將對(duì)象的3D數(shù)據(jù)表示為30×30×30大小的“立體柵格”。Daniel 等人[7]提出 VoxNet，將點(diǎn)云劃分為等間距的3D 體素，并通過(guò)新引入的體素特征編碼層將每個(gè)體素內(nèi)的一組點(diǎn)轉(zhuǎn)換為統(tǒng)一的特征表示，然而這種表示由于數(shù)據(jù)稀疏性和卷積計(jì)算成本的約束，要求其分辨率不能高。Li等人[8]提出一種處理點(diǎn)云數(shù)據(jù)稀疏問(wèn)題的方法，但是這種方法是在稀疏模型上進(jìn)行的，因此還是無(wú)法處理大量點(diǎn)云數(shù)據(jù)。Fang等人[9]和Guo等人[10]提出將三維數(shù)據(jù)轉(zhuǎn)換為向量矩陣，通過(guò)提取特征向量達(dá)到特征提取的目的。Wang等人[11]提出將點(diǎn)云模型八叉樹(shù)表示，該方法將所有三維模型用深度為8的八叉樹(shù)表示，最后葉節(jié)點(diǎn)中的點(diǎn)云用平均法向量表示，這種將點(diǎn)云模型法向量表示的方法，模型表示的精確度不夠。在基于點(diǎn)云的表示方法中，Qi等人[12]設(shè)計(jì)了一種直接消耗點(diǎn)云的新型神經(jīng)網(wǎng)絡(luò)，它保證輸入點(diǎn)的置換不變性，將網(wǎng)絡(luò)命名為PointNet，但是PointNet 網(wǎng)絡(luò)不會(huì)捕獲由度量空間點(diǎn)所引發(fā)的局部結(jié)構(gòu)，從而限制了識(shí)別細(xì)粒度模式的能力以及對(duì)復(fù)雜場(chǎng)景的普遍性，之后Qi等人[13]提出了新的集合學(xué)習(xí)層，以自適應(yīng)地組合來(lái)自多個(gè)尺度的特征，該網(wǎng)絡(luò)命名為PointNet++。山東大學(xué)的Li等人[14]為了讓卷積神經(jīng)網(wǎng)絡(luò)（CNN）更好地處理不規(guī)則和無(wú)序的點(diǎn)云數(shù)據(jù)，提出了PointCNN網(wǎng)絡(luò)。

3 GPU并行生成八叉樹(shù)算法

3.1 算法步驟概述

采用自頂向下的方式逐層并行構(gòu)建八叉樹(shù)，規(guī)定根節(jié)點(diǎn)層為第0層，一棵深度為L(zhǎng)的八叉樹(shù)其層號(hào)最大取值為L(zhǎng)-1，算法流程圖如圖1所示。

圖1 算法流程圖

步驟1將無(wú)組織的點(diǎn)云轉(zhuǎn)換成體素空間。

步驟2在體素空間中對(duì)點(diǎn)云模型進(jìn)行八叉樹(shù)空間剖分，區(qū)分并標(biāo)記空節(jié)點(diǎn)和非空節(jié)點(diǎn)，統(tǒng)計(jì)非空節(jié)點(diǎn)的總數(shù)。

步驟3根據(jù)八叉樹(shù)葉節(jié)點(diǎn)的數(shù)量，為每個(gè)葉節(jié)點(diǎn)開(kāi)辟存儲(chǔ)空間，對(duì)八叉樹(shù)編碼。

步驟4從第0層起，自頂向下逐層構(gòu)建節(jié)點(diǎn)間的關(guān)系，每次只處理一層，對(duì)每層節(jié)點(diǎn)并行處理。

3.2 點(diǎn)云轉(zhuǎn)換成體素空間

初始時(shí)求出點(diǎn)云模型中頂點(diǎn)的最大、最小值頂點(diǎn)(xmax,ymax,zmax)和(xmin,ymin,zmin)。以這兩點(diǎn)為對(duì)角頂點(diǎn)構(gòu)成空間包圍盒，并將其作為數(shù)據(jù)點(diǎn)云拓?fù)潢P(guān)系的根模型。包圍盒沿x、y、z軸的長(zhǎng)度分別為：Lx=|xmax-xmin|、W y=|ymax-ymin|、H z=|zmax-zmin|。在頂點(diǎn)(xmin,ymin,zmin)上固定一坐標(biāo)系，方向與歐氏空間的x、y、z方向相同，坐標(biāo)為整數(shù)坐標(biāo)，構(gòu)成一空間，稱為空間Z3。該空間是3D離散空間，是三維歐氏空間的子空間(Z?R3)，在邏輯上該空間為根節(jié)點(diǎn)。

3.3 八叉樹(shù)空間剖分

在Z3空間中，以深度優(yōu)先的方式遞歸細(xì)分包圍模型的立方體，將外部立方體劃分為相同大小的8 個(gè)子類，每個(gè)子立方體被視為根節(jié)點(diǎn)的8個(gè)葉節(jié)點(diǎn)。當(dāng)立方體被剖分成8個(gè)小的立方體時(shí)，空間物體分別位于這些子立方體的不同部分。若模型的點(diǎn)云在該節(jié)點(diǎn)或者立方體上，則該節(jié)點(diǎn)標(biāo)記為FULL，否則該節(jié)點(diǎn)標(biāo)記為NULL，同時(shí)該節(jié)點(diǎn)無(wú)需進(jìn)行剖分，如公式（1）所示：

在每個(gè)步驟中，對(duì)于當(dāng)前深度l遍歷被三維模型曲面占據(jù)的非空的節(jié)點(diǎn)，并在下一個(gè)l+1 深度將它們分別細(xì)分為8 個(gè)孩子節(jié)點(diǎn)。重復(fù)這個(gè)過(guò)程直到達(dá)到終止條件，終止條件為預(yù)定義深度或者葉子節(jié)點(diǎn)的大小。圖2（a）所示為點(diǎn)云模型的八叉樹(shù)空間剖分，圖2（b）為其對(duì)應(yīng)的八叉樹(shù)表示。分割的每個(gè)單元格的大小為Δx=Lx/l、Δy=Wy/l、Δz=HZ/l，其中l(wèi)為分割的層數(shù)。

圖2 八叉樹(shù)剖分與表示

3.4 改進(jìn)的八叉樹(shù)編碼方式

在本節(jié)中，描述如何從給定的一組點(diǎn)云數(shù)據(jù)集Q={qi|i=0,1,…,N} 構(gòu)建具有最大深度D的八叉樹(shù)O。（1）按照3.2節(jié)中的方式先把點(diǎn)云模型轉(zhuǎn)化為體素空間，并對(duì)體素空間進(jìn)行八叉樹(shù)剖分。（2）按照文獻(xiàn)[11]的思想設(shè)計(jì)八叉樹(shù)的存儲(chǔ)方式，引入一個(gè)索引數(shù)組和哈希函數(shù)用于尋找不同深度的節(jié)點(diǎn)對(duì)應(yīng)關(guān)系以進(jìn)行下采樣，同時(shí)為父節(jié)點(diǎn)的8 個(gè)子節(jié)點(diǎn)構(gòu)造鄰域，用于鄰域快速計(jì)算。

八叉樹(shù)節(jié)點(diǎn)的表示。記錄八叉樹(shù)節(jié)點(diǎn)較復(fù)雜，主要包含三條信息：

（1）向量sl：記錄八叉樹(shù)葉節(jié)點(diǎn)的三維空間坐標(biāo)。

（2）點(diǎn)集t：記錄每個(gè)節(jié)點(diǎn)所封閉的點(diǎn)。

（3）索引p：標(biāo)記父節(jié)點(diǎn)與子節(jié)點(diǎn)，及子節(jié)點(diǎn)之間的鄰域關(guān)系。

向量sl：為了記錄八叉樹(shù)l層的n個(gè)節(jié)點(diǎn)，用一個(gè)維一的 3n長(zhǎng)的字符串key(Ο)=i1j1k1i2j2k2…in jnkn表示。in jnkn可以由任意一點(diǎn)坐標(biāo)計(jì)算所得到，具體計(jì)算方法是已知任意一點(diǎn)P的坐標(biāo)為(x,y,z)，則點(diǎn)P所在的單元格坐標(biāo)為：

in=(x-xmin)/Δx，jn=(y-ymin)/Δy，kn=(z-zmin)/Δz in jnkn即八叉樹(shù)分割中每個(gè)點(diǎn)所在單元格的三維空間坐標(biāo)(i,j,k)，是3D立方體中的單元格的相對(duì)位置。

按照in jnkn升序的方式對(duì)八叉樹(shù)空間的位置排序并將八叉樹(shù)第l層排序好的空間位置存儲(chǔ)在sl向量中。sl之后用于構(gòu)建三維卷積的八叉樹(shù)的鄰域。在實(shí)現(xiàn)中，每個(gè)空間位置存儲(chǔ)在32位整數(shù)中。圖3列舉八叉樹(shù)節(jié)點(diǎn)的二維空間位置，圖4顯示每層對(duì)應(yīng)的排序。

圖3 二維空間中圖像的四叉樹(shù)構(gòu)造

圖4 每層節(jié)點(diǎn)對(duì)應(yīng)的排序

4 構(gòu)建八叉樹(shù)

4.1 構(gòu)建節(jié)點(diǎn)間的鄰接關(guān)系

對(duì)于每個(gè)節(jié)點(diǎn)，需要記錄其父節(jié)點(diǎn)、8個(gè)子節(jié)點(diǎn)，相鄰節(jié)點(diǎn)。在一般的八叉樹(shù)數(shù)據(jù)結(jié)構(gòu)中使用指針來(lái)表示節(jié)點(diǎn)間的相互關(guān)系，但本文中，為了節(jié)省內(nèi)存空間，加速計(jì)算，丟棄從父節(jié)點(diǎn)到子節(jié)點(diǎn)的指針，并引入一個(gè)哈希函數(shù)，用于尋找不同深度的父子節(jié)點(diǎn)間的對(duì)應(yīng)關(guān)系。

在計(jì)算中，需要快速找到相鄰層上八叉樹(shù)上的父子的相鄰關(guān)系。為l層的非空節(jié)點(diǎn)指定一個(gè)索引p，表示它是第l層排序節(jié)點(diǎn)中第p個(gè)非空節(jié)點(diǎn)。對(duì)于空節(jié)點(diǎn)，把它的索引設(shè)置為零。l層的所有索引存儲(chǔ)在索引向量Ll中。圖5 表示二維空間中每個(gè)深度的索引向量。對(duì)于非空節(jié)點(diǎn)，在圖5 中被標(biāo)記成藍(lán)色的節(jié)點(diǎn)，其索引為3(L1[2]=3)，因?yàn)樗堑谝粚拥牡谌齻€(gè)非空的節(jié)點(diǎn)。

圖5 索引向量

4.2 逐層并行構(gòu)造八叉樹(shù)

在確定一個(gè)節(jié)點(diǎn)是非空節(jié)點(diǎn)后，用原子計(jì)數(shù)器為其分配一個(gè)索引，作為節(jié)點(diǎn)在索引向量中的存儲(chǔ)位置。從根節(jié)點(diǎn)開(kāi)始，每次只處理一層，每層節(jié)點(diǎn)并行處理。再處理第l層時(shí)(i＞0)，需要獲取第l-1 層即其父節(jié)點(diǎn)的索引位置，以構(gòu)建父子關(guān)系。

（1）只有第l深度的非空節(jié)點(diǎn)被細(xì)分。

（2）根據(jù)屬性的升序排序節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)的8個(gè)孩子被順序存儲(chǔ)。

（3）父節(jié)點(diǎn)和孩子節(jié)點(diǎn)的屬性向量都遵循相同的順序。如圖5所示，第2層的最后4個(gè)節(jié)點(diǎn)是第1層的第3個(gè)非空節(jié)點(diǎn)創(chuàng)建。

5 點(diǎn)云數(shù)據(jù)組織

文獻(xiàn)[11]提出了既節(jié)省內(nèi)存空間，又可以快速進(jìn)行鄰域搜索的八叉樹(shù)存儲(chǔ)方式，但該方法對(duì)八叉樹(shù)葉子節(jié)點(diǎn)內(nèi)的點(diǎn)云僅做了平均法向量處理，并沒(méi)有提出具體每個(gè)點(diǎn)云的組織方式。針對(duì)該問(wèn)題本文結(jié)合三維K-D 樹(shù)的空間索引單個(gè)三維空間點(diǎn)云，使大規(guī)模點(diǎn)云直接端到端輸入深度學(xué)習(xí)網(wǎng)絡(luò)成為可能。

5.1 基于K-D樹(shù)的點(diǎn)云組織

通過(guò)八叉樹(shù)剖分后的點(diǎn)云數(shù)據(jù)被分到若干個(gè)規(guī)則節(jié)點(diǎn)中，其二維平面結(jié)構(gòu)如圖6所示。這種方法采用規(guī)則格網(wǎng)剖分，易于實(shí)現(xiàn)，具有較好的可操作性，在點(diǎn)云數(shù)據(jù)的空間分布比較均勻的，且數(shù)據(jù)量不是很大時(shí)也可以達(dá)到快速檢索的目的，但是當(dāng)海量數(shù)據(jù)，且點(diǎn)云數(shù)據(jù)的空間分布不均勻（如存在局部點(diǎn)云密集）時(shí)，這種單一組織方式存在的弊端就會(huì)顯現(xiàn)。比如葉子節(jié)點(diǎn)中點(diǎn)云數(shù)據(jù)量的不均衡，在數(shù)據(jù)密集的葉節(jié)點(diǎn)中進(jìn)行坐標(biāo)點(diǎn)的二次查詢?nèi)匀皇呛芎臅r(shí)，難以提高點(diǎn)云數(shù)據(jù)的檢索效率。如果大量增加八叉樹(shù)的深度，不僅會(huì)給數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)帶來(lái)困難，也會(huì)造成大量“無(wú)點(diǎn)”空間的浪費(fèi)，降低檢索效率[15]。

今年云南省局部地區(qū)，在授粉階段成片發(fā)生高溫?zé)岷?，造成缺粒減產(chǎn)，產(chǎn)量可能降低30%-50%。主要原因是開(kāi)花抽絲期間，當(dāng)溫度高于32-35℃，空氣濕度低于30%，田間水量低于70%，雄穗開(kāi)花的時(shí)間會(huì)顯著縮短。因高溫干旱，花粉粒在1-2 h內(nèi)失水干枯，喪失發(fā)芽能力，花絲延期抽出，造成花期不遇；或花絲過(guò)早枯萎，嚴(yán)重影響授粉結(jié)實(shí)，形成禿尖、缺粒，產(chǎn)量降低。如能及時(shí)澆水，改善田間小氣候，可減輕高溫干旱的影響。

圖6 點(diǎn)云數(shù)據(jù)的規(guī)則間組織二維結(jié)構(gòu)示意圖

基于此，文中對(duì)存儲(chǔ)于葉子節(jié)點(diǎn)中的點(diǎn)云數(shù)據(jù)采用K-D 樹(shù)進(jìn)行二次組織。要求存入的數(shù)據(jù)能夠按照一定的規(guī)則進(jìn)行排序，并且按照此規(guī)則進(jìn)行的排序結(jié)果必須遵循兩個(gè)原則：

（1）唯一性。即坐標(biāo)不同的三維點(diǎn)坐標(biāo)的排序結(jié)果一定不同。

（2）傳遞性。如果Pn1＞Pn2,Pn2＞Pn3,則Pn1＞Pn3(Pn3為三維坐標(biāo)點(diǎn)）。

在每個(gè)八叉樹(shù)葉子節(jié)點(diǎn)內(nèi)構(gòu)建K-D樹(shù)的步驟為：

（1）將八叉樹(shù)葉子節(jié)點(diǎn)作為K-D 樹(shù)的根節(jié)點(diǎn)，該節(jié)點(diǎn)內(nèi)包含的點(diǎn){P}作為預(yù)分割點(diǎn)集。

（2）將葉節(jié)點(diǎn)進(jìn)行“分維”處理，在一維空間中進(jìn)行排序操作。首先將坐標(biāo)點(diǎn)投影到x軸上進(jìn)行比較，如果相同，再投影到y(tǒng)軸上比較，依次拓展到z軸進(jìn)行判斷。對(duì)于任意兩個(gè)點(diǎn)Pn1和Pn2，其對(duì)應(yīng)的坐標(biāo)點(diǎn)為(x1,y1,z1)和 (x2,y2,z2)，那么

if(x1≠x2)，以x軸為法向平面將點(diǎn)集{P}分割為2 個(gè)集合，設(shè)P1為左集合，P2為右集合。

if(x1=x2)and(y1≠y2)，以y軸為法向平面將點(diǎn)集{P}分割為2個(gè)集合，設(shè)P1為左集合，P2為右集合。

if(x1=x2)and(y1=y2)and(z1≠z2)，以z軸為法向平面將點(diǎn)集{P}分割為2個(gè)集合，設(shè)P1為左集合，P2為右集合。

（3）更新點(diǎn)集{P}，在P1和P2中分別執(zhí)行構(gòu)建K-D樹(shù)。

5.2 點(diǎn)云數(shù)據(jù)組織結(jié)構(gòu)設(shè)計(jì)

通過(guò)上述分析，三維點(diǎn)數(shù)據(jù)以坐標(biāo)為關(guān)鍵字直接存儲(chǔ)在K-D樹(shù)中，而K-D樹(shù)作為二級(jí)組織結(jié)構(gòu)關(guān)聯(lián)存儲(chǔ)于空間八叉樹(shù)的葉子節(jié)點(diǎn)中。這種結(jié)構(gòu)的內(nèi)存實(shí)現(xiàn)比較容易（其數(shù)據(jù)結(jié)構(gòu)如圖7所示）。

圖7 點(diǎn)云數(shù)據(jù)組織的結(jié)構(gòu)圖

6 實(shí)驗(yàn)結(jié)果與分析

6.1 實(shí)驗(yàn)環(huán)境

算 法 在 一 臺(tái) Intel Core i7，3.30 GHz 的 CPU 和GeForce GTX 1080 的GPU（8 GB顯存）的臺(tái)式機(jī)上完成點(diǎn)云模型的表示。本文使用Visual studio 2013環(huán)境下進(jìn)行CPU 編程，使用OpenGL 進(jìn)行GPU 編程，并使用OpenGL實(shí)現(xiàn)三維模型加載表示。

6.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)以在兵馬俑一號(hào)坑第三次發(fā)掘中掃描的模型數(shù)據(jù)為例，這些模型經(jīng)過(guò)除噪，孔洞修復(fù)后的點(diǎn)云模型如圖8 所示，（a）為 10 號(hào)坑 4 號(hào)俑（G10-4）的手，（b）為9號(hào)坑3號(hào)俑（G9-3）的頭，（c）為9號(hào)坑7號(hào)俑（G9-7）的腿。

圖8 碎片的原始點(diǎn)云模型

6.3 實(shí)驗(yàn)分析

實(shí)驗(yàn)1 實(shí)驗(yàn)結(jié)果的可視化

利用本文提出的構(gòu)造八叉樹(shù)的算法對(duì)圖8 中的模型分別進(jìn)行八叉樹(shù)剖分，點(diǎn)云模型經(jīng)過(guò)八叉樹(shù)剖分（深度分別為5和7）后的可視化圖如圖9至圖11所示。

圖9 G10-4俑手的可視化表達(dá)

圖10 G9-3俑頭的可視化表達(dá)

實(shí)驗(yàn)2 與已有方法比較

圖11 G9-7俑腿的可視化表達(dá)

圖12 為將文獻(xiàn)[11]的點(diǎn)云模型八叉樹(shù)表示與本文點(diǎn)云模型八叉樹(shù)表示方法的比較，其中（a）為G9-3俑頭的原始模型，含有46 919 個(gè)點(diǎn)云，（b）為使用文獻(xiàn)[11]將點(diǎn)云模型用八叉樹(shù)方法表示，（c）為使用本文提出算法將點(diǎn)云模型用八叉樹(shù)方法表示。比較圖（b）和圖（c）可以明顯地看出本文提出的算法將點(diǎn)云模型八叉樹(shù)表示后保留了傭頭的眉毛、眼睛、鼻子和嘴巴等細(xì)節(jié)，而文獻(xiàn)[11]提出的八叉樹(shù)體表示方法模型的細(xì)節(jié)特征表示模糊。這是因?yàn)楸疚牡姆椒ㄔ趯⒛Ｐ桶瞬鏄?shù)化后點(diǎn)云模型使用K-D樹(shù)的方法進(jìn)行了組織，能夠真實(shí)表達(dá)模型特征，如圖（c）所示，而文獻(xiàn)[11]將葉節(jié)點(diǎn)中的點(diǎn)云用平均法向量表示，所以文獻(xiàn)[11]中看到的特征是平均法向量特征，如圖（b）所示。

圖12 文獻(xiàn)[11]與本文點(diǎn)云模型八叉樹(shù)表示方法的比較

表1展示了G9-3俑頭的原始模型（含有46 919個(gè)點(diǎn)云），分別在CPU 端使用文獻(xiàn)[11]的方法構(gòu)建八叉樹(shù)所耗費(fèi)的時(shí)間與在CPU端使用本文的算法構(gòu)建八叉樹(shù)所耗費(fèi)的時(shí)間。其中CPU端采用傳統(tǒng)的遞歸分割根節(jié)點(diǎn)的方法構(gòu)建八叉樹(shù)，八叉樹(shù)的深度為5、6 和7。通過(guò)比較可知，本文所提出的GPU并行構(gòu)建八叉樹(shù)的方法，較傳統(tǒng)的CPU 算法速度可以提高一個(gè)數(shù)量級(jí)，且構(gòu)造八叉樹(shù)的深度越大加速比越高。

表1 八叉樹(shù)生成算法在CPU和GPU上耗時(shí)對(duì)比

實(shí)驗(yàn)3 點(diǎn)云查找耗時(shí)分析

為了驗(yàn)證八叉樹(shù)與K-D樹(shù)混合的索引效率，本實(shí)驗(yàn)利用圖8 的點(diǎn)云模型，其中俑手含有16 274 個(gè)點(diǎn)云，俑頭含有46 916 個(gè)點(diǎn)云，俑腿含有226 792 個(gè)點(diǎn)云。分別利用改進(jìn)八叉樹(shù)，K-D樹(shù)和改進(jìn)八叉樹(shù)與K-D樹(shù)的混合索引對(duì)點(diǎn)云進(jìn)行組織，并對(duì)指定的同一個(gè)點(diǎn)進(jìn)行查詢，查詢的時(shí)間統(tǒng)計(jì)如表2所示，從表中可以看出利用單一的八叉樹(shù)進(jìn)行點(diǎn)云的查找的時(shí)消耗時(shí)間最多，這是由于隨著八叉樹(shù)深度的變大，導(dǎo)致了查詢的效率明顯下降。而K-D樹(shù)組織的點(diǎn)云明顯可以改善查詢的效率，但是隨著點(diǎn)云數(shù)量的增大其效率降低相對(duì)也比較明顯。而利用混合結(jié)構(gòu)的索引方式可以大大地改善查詢點(diǎn)的效率，非常有利于對(duì)點(diǎn)云數(shù)據(jù)的分析、可視化與交互。

表2 三種不同的算法點(diǎn)云查找耗時(shí)對(duì)比表

實(shí)驗(yàn)4 OctKD混合索引在深度學(xué)習(xí)中的應(yīng)用

將本文提出的OctKD混合索引結(jié)構(gòu)應(yīng)用于文獻(xiàn)[11]提出的三維模型分割的卷積神經(jīng)網(wǎng)絡(luò)。文獻(xiàn)[11]提出的深度分割網(wǎng)絡(luò)為：

其中Ul表示為convolution+BN+Relu+pooling，DUl表示為unpooling+deconvolution+BN+Relu，d為八叉樹(shù)的深度。圖13為將OctKD混合索引結(jié)構(gòu)應(yīng)用于深度網(wǎng)絡(luò)所得到的特征提取圖和模型分割圖。黃色、綠色、紫色來(lái)表示該碎塊被分割出的不同面，紅色表示粗分割線，桔黃色表示精細(xì)分割結(jié)果。

圖13 OctKD在深度學(xué)習(xí)中的應(yīng)用

7 結(jié)束語(yǔ)

對(duì)于機(jī)器學(xué)習(xí)任務(wù)，模型表示是至關(guān)重要的一步。發(fā)現(xiàn)和表達(dá)原始數(shù)據(jù)的能力是決定算法整體性能的重要因素。因此，本章的目標(biāo)是尋找能夠代表3D 對(duì)象而且能夠用于深度學(xué)習(xí)的表達(dá)方式。針對(duì)海量散亂點(diǎn)云數(shù)據(jù)不能直接輸入深度學(xué)習(xí)網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)的問(wèn)題，提出基于八叉樹(shù)和三維K-D 樹(shù)的集成索引（OctKD）的點(diǎn)云數(shù)據(jù)的表示方法。該方法即克服傳統(tǒng)八叉樹(shù)編碼浪費(fèi)空間的問(wèn)題，又實(shí)現(xiàn)層與層之間以及八叉樹(shù)節(jié)點(diǎn)的鄰域信息之間的快速訪問(wèn)。實(shí)驗(yàn)表明這種新的點(diǎn)云模型的OctKD數(shù)據(jù)結(jié)構(gòu)優(yōu)化模型在卷積神經(jīng)網(wǎng)絡(luò)上的訓(xùn)練，是一種深度學(xué)習(xí)能夠處理點(diǎn)云數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。最后按層構(gòu)造八叉樹(shù)，在同一層上的所有八叉樹(shù)節(jié)點(diǎn)并行處理的，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)在GPU上的并行處理。