海量采樣點(diǎn)集法向聚類并行估計(jì)及增量統(tǒng)一算法*

張 碩，孫殿柱，李延瑞，梁增凱

(1.山東理工大學(xué) 機(jī)械工程學(xué)院，山東 淄博 255049；2.西安交通大學(xué) 機(jī)械工程學(xué)院，西安 711049)

0 引言

近年來，點(diǎn)采樣集合作為一種新的曲面表示方式，受到了廣泛的關(guān)注，與基于網(wǎng)格技術(shù)相比，它無需存儲(chǔ)和維護(hù)全局一致的拓?fù)湫畔?，能?duì)復(fù)雜的三維模型進(jìn)行高效的繪制[1]和靈活的幾何處理，因此在處理復(fù)雜或動(dòng)態(tài)改變形狀的模型時(shí)，具有更高的靈活性。而法向量作為點(diǎn)云的重要屬性之一，其計(jì)算準(zhǔn)確性直接影響到點(diǎn)云模型處理的有效性。如隱式表面重建算法[2-4]，重建結(jié)果的準(zhǔn)確性很大程度上取決于法向計(jì)算的精確性。

目前常用的點(diǎn)云法向估計(jì)算法主要有三種：基于局部表面擬合的算法[5]，基于 Delaunay/Voronoi[6]的算法與基于魯棒性統(tǒng)計(jì)[7]的算法。李寶等[8]對(duì)這三種方法及其改進(jìn)算法[3，9]的原理與關(guān)鍵技術(shù)進(jìn)行了詳細(xì)分析。王醒策等[10]利用改進(jìn)移動(dòng)最小二乘曲面實(shí)現(xiàn)局部曲面擬合，增加法向估計(jì)的準(zhǔn)確性。Alexandre[11]利用卷積神經(jīng)網(wǎng)絡(luò)算法與改進(jìn)的霍夫變換算法提高樣點(diǎn)法向估計(jì)的魯棒性。以上算法雖然能較好的完成法向估計(jì)，但在處理海量采樣點(diǎn)模型時(shí)，計(jì)算量過大，傳統(tǒng)的串行計(jì)算不能滿足計(jì)算能力的要求，因此需要借助于并行計(jì)算的支持。

隨著軟硬件技術(shù)的發(fā)展，并行計(jì)算的門檻不斷降低。在海量點(diǎn)云處理中的應(yīng)用也越來越廣泛。Dey[12]利用八叉樹對(duì)海量點(diǎn)云劃分，并利用并行計(jì)算進(jìn)行Delaunay 剖分。Bolitho等[13]在曲面重建中應(yīng)用并行計(jì)算，充分利用多核處理器的計(jì)算性能與分布式內(nèi)存管理框架，提高了程序執(zhí)行的效率。基于OpenMP 框架的并行分層算法[14]將拓?fù)浣Y(jié)構(gòu)的遍歷過程與層面輪廓的提取過程并行化計(jì)算，取得了接近處理器核心數(shù)目的加速比，分層時(shí)間明顯降低。Boltcheva等[15]將并行計(jì)算用于Voronoi計(jì)算中，算法執(zhí)行效率提高兩個(gè)數(shù)量級(jí)以上。

針對(duì)現(xiàn)有法向估計(jì)算法在進(jìn)行海量點(diǎn)云法向估計(jì)時(shí)效率低下，內(nèi)存消耗大的問題，本文結(jié)合局部平面擬合和并行計(jì)算，提出了一種海量采樣點(diǎn)集法向聚類并行估計(jì)及增量統(tǒng)一算法。即采用空間分解的方法進(jìn)行并行計(jì)算。首先通過聚類算法將海量樣點(diǎn)全集分成多個(gè)點(diǎn)云規(guī)模較小的樣點(diǎn)子集；然后將各樣點(diǎn)子集的法向量估計(jì)過程并行化計(jì)算；最后，選擇初始樣點(diǎn)子集，采用增量算法實(shí)現(xiàn)樣點(diǎn)子集的法向統(tǒng)一。實(shí)驗(yàn)表明，利用該算法對(duì)海量采樣點(diǎn)集進(jìn)行法向估計(jì)，內(nèi)存消耗明顯降低且計(jì)算效率顯著提高。

1 空間劃分

本文采用一種簡(jiǎn)單的聚類方法對(duì)點(diǎn)云P進(jìn)行空間劃分。首先對(duì)點(diǎn)云P建立 kd 樹，從 kd 樹的根結(jié)點(diǎn)開始，選取前l(fā)層結(jié)點(diǎn)作為聚類中心, 記為O；則聚類中心的個(gè)數(shù)為m=2l-1。然后根據(jù)歐氏距離將P中所有樣點(diǎn)分類，得到距離每個(gè)聚類中心最近的點(diǎn)集：

Si=p∈Prpoi,oj<ξ,i≠j.,ξ>0,oi,oj∈O

式中，rpoi,oj=poi-poj表示樣點(diǎn)p與oi,oj的歐氏距離差，ξ為分界閾值，控制分界帶的寬度。ξ越大，分界帶的寬度越大。當(dāng)0

(a)原始點(diǎn)云模型 (b)空間劃分結(jié)果示意圖

(c)ξ = 50 (d)ξ = 100圖1 空間劃分示意圖

2 法向估計(jì)

經(jīng)空間劃分后形成的樣點(diǎn)子集Si相互獨(dú)立，具有高度并行性,可采用并行化的框架對(duì)樣點(diǎn)子集進(jìn)行法向并行估計(jì)。對(duì)每個(gè)樣點(diǎn)子集Si派生出一個(gè)線程，同時(shí)進(jìn)行法向估計(jì)計(jì)算。法向并行估計(jì)流程如圖2所示：

圖2 法向并行估計(jì)流程

由法向并行估計(jì)流程可知，利用局部平面擬合算法對(duì)子集Si進(jìn)行法向并行估計(jì)。將Si作為獨(dú)立計(jì)算單元，對(duì)p∈Si的k鄰域集合進(jìn)行局部平面擬合，并將該平面的法向量np作為p的法向量。

(a)k近鄰示意圖 (b)法向量示意圖圖3 法向估計(jì)示意圖

如圖3所示，np的準(zhǔn)確性取決于k鄰域集合是否能更準(zhǔn)確的反映樣點(diǎn)p周圍采樣面的形狀信息。設(shè)λp表示樣點(diǎn)p∈Si的k近鄰集合，若p為非分界樣點(diǎn)，即p位于Si內(nèi)部，則λp分布于p周圍，近似高斯分布；λp能很好的反映p周圍區(qū)域的形狀，因此，可利用該鄰域擬合平面的法向量代表p的法向量。若p為邊界樣點(diǎn)，即p∈Uij,則λp的分布偏向于一側(cè)，無法準(zhǔn)確反映實(shí)物表面目標(biāo)樣點(diǎn)周圍區(qū)域的形狀，增大法向估計(jì)誤差。因此，對(duì)于分界樣點(diǎn)p∈Uij，可在P中搜索p的k近鄰集合λp，并以λp作為p周圍區(qū)域的樣本計(jì)算法向量。

經(jīng)上述計(jì)算得到的法向量具有二義性，即只得到了法向量所在的直線，而沒有確定法向量的朝向。利用 Hoppe的法向統(tǒng)一算法實(shí)現(xiàn)樣點(diǎn)子集內(nèi)部法向的統(tǒng)一。

3 法向統(tǒng)一

經(jīng)法向估計(jì)后的樣點(diǎn)子集內(nèi)部的法向朝向一致，但不同樣點(diǎn)子集的法向量朝向不一，無法判斷各子集的法向量指向模型的內(nèi)部還是外部，導(dǎo)致樣點(diǎn)全集的法向朝向不一。

采用增量算法對(duì)各樣點(diǎn)子集間進(jìn)行法向統(tǒng)一。首先選擇Si作為初始樣點(diǎn)子集T,如圖4b中亮灰色區(qū)域所示。然后在已完成統(tǒng)一的集合T的基礎(chǔ)上利用分界樣點(diǎn)的特性，查詢子集Sj與T的位置關(guān)系，即判斷Sj是否與T相鄰接。若Sj與T相鄰接，將Sj并入集合T，此時(shí)Sj與T的分界樣點(diǎn)退化成T的內(nèi)部樣點(diǎn)，Sj中的部分分界樣點(diǎn)更新成T的分界樣點(diǎn)。從Sj與T的分界樣點(diǎn)集合中任選一點(diǎn)p，若np∈Sj·np∈T<0，說明Sj與T中樣點(diǎn)法向量的朝向不同，則翻轉(zhuǎn)Sj內(nèi)的法向量，使集合T中樣點(diǎn)的法向量始終保持一致，這一計(jì)算過程可表示為一個(gè)迭代的計(jì)算過程，直到S中所有子集全部并入T中, 則停止計(jì)算。法向統(tǒng)一過程如圖4所示。

(a)未統(tǒng)一法向示意圖 (b)選取初始樣點(diǎn)子集

(c)選取增量子集 (d)完全統(tǒng)一示意圖圖4 法向統(tǒng)一過程示意圖(淺灰色區(qū)域表示為統(tǒng)一的樣點(diǎn)子集，亮灰色區(qū)域表示統(tǒng)一后的樣點(diǎn)子集,黑色區(qū)域表示樣點(diǎn)子集的分界樣點(diǎn))

4 實(shí)驗(yàn)與分析

為驗(yàn)證本文所提出算法的法向估計(jì)效果，在硬件配置為 HPxw8600 Workstation(4 ×2.5GHz, 4.0GB DDR2 內(nèi)存)，操作系統(tǒng)為 GNU/Linux 的測(cè)試環(huán)境中，并行框架采用 OpenMP, 版本為 4.5。CGAL 版本為 4.10。應(yīng)用 CGAL中的法向估計(jì)模塊。分別利用法向并行估計(jì)算法與串行算法對(duì)不同規(guī)模的數(shù)據(jù)進(jìn)行測(cè)試。

本文算法所涉及到的主要參數(shù)l，ξ，k，其中l(wèi)控制聚類簇的數(shù)目，l越大，則空間劃分的簇?cái)?shù)越多。從kd樹的根結(jié)點(diǎn)開始，選取的前l(fā)層結(jié)點(diǎn)作為聚類中心，則聚類中心的個(gè)數(shù)為:m=2l-1。l越大，法向估計(jì)時(shí)間縮短，但聚類時(shí)間增加，且l>7程序執(zhí)行時(shí)間收斂。經(jīng)大量實(shí)驗(yàn)驗(yàn)證，當(dāng)5

表1 串行計(jì)算與并行計(jì)算時(shí)間對(duì)比

觀察dragon模型(58M)在實(shí)驗(yàn)過程中的內(nèi)存與CPU的使用狀況。如圖5所示，折線圖表示程序運(yùn)行過程中內(nèi)存的使用情況：oa1，oa2段為數(shù)據(jù)讀入階段，內(nèi)存消耗無明顯差別。a1b1段為空間劃分階段，因此，在此階段內(nèi)存消耗大于串行算法。b1c1段為法向并行估計(jì)階段，其中，內(nèi)存消耗量呈現(xiàn)無規(guī)律性波動(dòng)，這是因?yàn)橛?jì)算機(jī)在進(jìn)行并行估計(jì)過程中，計(jì)算中的樣點(diǎn)子集的規(guī)模存在差異及線程切換產(chǎn)生的波動(dòng)。c1d1段與d1e1段分別為寫入文件階段與內(nèi)存釋放階段，內(nèi)存消耗基本維持不變。在串行計(jì)算內(nèi)存消耗過程中，a2b2為法向估計(jì)階段，內(nèi)存消耗量有所增加，但增加的速度較緩慢。b2c2段為法向統(tǒng)一階段，無向圖的構(gòu)建與最小生成樹的生成消耗大量?jī)?nèi)存，因此，在此階段，內(nèi)存消耗量急劇增加，內(nèi)存消耗峰值約為 53%。

圖5 串行計(jì)算與并行計(jì)算內(nèi)存消耗與CPU使用率對(duì)比圖

如圖5中柱狀數(shù)據(jù)顯示，在t=100s時(shí)對(duì)并行算法中的CPU進(jìn)行監(jiān)控，其中，4個(gè)核心的負(fù)載均接近最大值，處于平衡狀態(tài)，在96%～99%范圍內(nèi)波動(dòng)。在t=300s是對(duì)串行算法中的CPU測(cè)得數(shù)據(jù)中，其中，僅有1個(gè)核心的負(fù)載達(dá)到峰值，參與程序執(zhí)行過程。

為驗(yàn)證不同算法對(duì)該模型的法向估計(jì)效果，以不同算法所得法向信息作為輸入，并利用文獻(xiàn)[15]中的 poisson算法對(duì)該模型進(jìn)行曲面重建，依據(jù)重建效果判斷法向估計(jì)結(jié)果的準(zhǔn)確性。重建結(jié)果如圖6所示。對(duì)局部尖銳區(qū)域進(jìn)行放大顯示，從圖中可看出，采用法向并行估計(jì)與串行估計(jì)所得結(jié)果無明顯差距。

(a)串行計(jì)算 (b)并行計(jì)算圖6 dragon采樣數(shù)據(jù)與不同算法所得法向的 曲面重建效果

5 結(jié)論

本文利用聚類算法將海量采樣點(diǎn)集分解成多個(gè)樣點(diǎn)子集，利用并行計(jì)算進(jìn)行各樣點(diǎn)子集的法向估計(jì)，并采用增量算法完成樣點(diǎn)子集間的法向統(tǒng)一，提出一種海量采樣點(diǎn)集法向聚類并行估計(jì)及增量統(tǒng)一算法。主要有以下特點(diǎn)：

(1) 應(yīng)用并行法向估計(jì)算法能充分利用多核處理器的計(jì)算優(yōu)勢(shì)，顯著降低采樣點(diǎn)集法向估計(jì)時(shí)間。

(2) 對(duì)分解后的樣點(diǎn)子集得計(jì)算實(shí)現(xiàn)并行化，有效提高程序執(zhí)行過程中的內(nèi)存利用率，減少空間復(fù)雜度，可以處理更大規(guī)模的點(diǎn)云數(shù)據(jù)。

(3) 將并行計(jì)算應(yīng)用于海量點(diǎn)云的法向估計(jì)，保證了對(duì)采樣點(diǎn)集法向估計(jì)的準(zhǔn)確性不低于現(xiàn)有算法，但無明顯提高，后續(xù)工作可嘗試改進(jìn)法向估計(jì)算法，以此實(shí)現(xiàn)法向的正確估計(jì)。