一種改進的表面重建算法及其并行化研究

王元+曹靜+婁澤坤

摘 要： 對于泊松三維表面重建中估算指示函數出現誤差的情況，引入屏蔽因子并使用線性插值的方法糾正誤差。該方法在等值面提取時使用的索引表查找法存在二義性的問題，需使用漸近線方法來解決。改進算法需要較大的存儲空間來存儲頂點信息和法向量以及較長的時間來運算，因而引入了CUDA架構的并行化計算來提高運行效率。

關鍵詞： 多視圖三維重建； 泊松表面重建； 二義性； CUDA架構

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2017）05-17-03

An improved 3D surface reconstruction method and it's parallelization

Wang Yuan， Cao Jing， Lou Zekun

（School of Computer and Information Engineering， Henan University， Kaifeng， Henan 475000， China）

Abstract： In this thesis the shielding factor is introduced to solve the problem of errors of indication function to estimate the indicator function in the Poisson surface reconstruction algorithm. In the part of isosurface extraction in surface reconstruction， the triangulation process is performed by searching the index table. But this method will lead to ambiguity， so an asymptotic method is used to avoid it. This surface reconstruction algorithm will improve the holes and depressions problems of complex objects. At the same time， it leads to larger storage space to store vertex and normal vectors， and a longer time to process data. Therefore， CUDA architecture and parallelization are introduced to solve the problem of efficiency.

Key words： multi view 3D reconstruction； Poisson surface reconstruction； ambiguity； CUDA architecture

0 引言

2006年，Michael Kazhdan等人提出了泊松表面重建算法[1]，但泊松表面重建本身存在諸多缺陷。如該算法在矯正指示函數的時候使用的是一次性全局的偏移[2]。若在實際的實現過程中出現計算指示函數不可避免的誤差，此時再用一次性全局偏移的方法估算指示函數則會出現重建結果誤差較大的情況[3]；另外等值面提取部分用移動立方體算法，該算法通過索引表查找各個體素內三角面片的連接模式確定等值面的分布方式，但是索引表算法會產生連接二義性問題。

鑒于第一個問題，最主要的突破口是找到一個合適的全局偏移量來解指示函數的近似解，本文嘗試使用顯性插值方法對樣本點進行插值計算。對于存在連接二義性的情況，改進方法是漸近線算法。同時對改進之后算法的效率提升問題引入支持計算統一設備架構（CUDA），采用GPU并行計算，其存儲器帶寬和并行處理能力有CPU處理無法逾越的優勢。

1 引入屏蔽因子和漸近線算法的表面重建

1.1 引入屏蔽因子

在泊松方程的求解過程中[5]，對于目的有向點集求解尺度指示函數，使尺度函數的梯度與有向點集形成最佳逼近即尺度函數最小化問題

在此，本文給定帶權重的點集，為尺度函數最小化增加一些約束重新計算樣本點函數，見公式⑵：

其中Area（S）是要重建的表面區域，α是一個權值，用來衡量擬合梯度和擬合值，也可叫做屏蔽因子，w（p）是樣本點權重，在該算法實現中，根據局部采樣密度估計得到表面區域，每個樣本點的權重w（p）設置為1。上述公式簡化為公式⑶：

表示單位體素在函數空間上的表示形式，這個值是由采樣點的函數加權和得到的，見公式⑷：

公式⑷將梯度約束和離散點約束值整合進空間域，隨即指示函數的方程最小化為或者。

此時，若指示函數滿足，則此等式就是屏蔽泊松方程。

通過引入屏蔽因子解屏蔽泊松方程的方法，使用顯性插值計算，解決一次性全局估算指示函數誤差較大的情況。

1.2 使用漸進性方法解決二義性

移動立方體算法提供了以查找索引表的方式確定體素內等值面的連接方式，但這種方法也過于依賴直觀的構造，忽略了構造三角面片時可能存在的二義性問題。如圖1，在立方體體素的某一等值面上若出現對角線的兩端同時為+，另一對角線兩端同時為-的情況時，不同的連接方式會構造不同的結果，如圖1。

對于存在連接二義性的情況改進方法是漸近線算法，通過邊界面與等值面相交的理論得知，二者相交的結果是一對雙曲線，計算雙曲線的漸近線，通過雙曲線、雙曲線的漸近線與體素邊界面三種體元的位置關系來判斷是否產生二義性，對于有面二義性的情況，做漸近線處理判別方法，作圖2（h）和（i）：

當頂點為+和頂點為-分別出現在一對對角線兩端時出現連接二義性，此時若漸近線交點為+如圖2（h），則漸近線交點和B點D點處于同一區域，此時等值點M1和M2連接，M3和M4連接；若漸近線交點為-如圖2（i），則漸近線交點和A點C點處于同一區域，此時等值點M1和M3連接，M2和M4連接。

2 關于改進表面重建算法的GPU并行優化

從CUDA架構可知，CUDA并行算法的設計需要程序的數據相互獨立，在實現的過程中需要處理若干相互不相干的子問題[4]，這些子問題被分割放置在每一個kernel函數中同時執行，對于八叉樹結構每個深度層次上的數據計算可用CUDA架構并行化處理，可根據串行程序中耗時不同設計并行算法。

根據程序耗時分析，設計數據離散化八叉樹生成部分進行GPU并行計算[6-7]。

2.1 包圍盒的并行計算

包圍盒，可作為八叉樹的根節點，計算各個樣本點的相對位置。在我們的并行設計算法中，處理并行計算包圍盒用的是CUDPP的方法，CUDPP是一種強大的數據并行CUDA庫。

CUDPP的具體調用過程如下。

⑴ 初始化，調用cudppCreate實例化一個CUDPP，生成一個CUDPPManager對象，將其地址返回給theCudpp。

⑵ 為主機端和設備端使用函數分配存儲空間，對主機端所要輸入參數集賦值。

⑶ 將數據從主機端復制到設備端指定的存儲空間，使用cudaMemcpy2D（）函數進行主機端與設備端之間的二維數據傳輸。數據傳輸方向是主機端到設備端，cudaMemcpyHostToDevice（）。

⑷ 生成“CUDPP計劃”。CUDPP計劃是CUDPP方法中特有的一部分內容，具體做法是定義一個CUDPPHandle，生成一個cudppPlan將句柄賦值給scanPlan。

⑸ 執行原語。

在CUDPP計劃配置參數完成之后即要開始執行這一過程的kernel函數。最后，用cudaThreadSynchronize（）函數同步處理。

⑹ 將輸出數據復制到主機端。繼續由主機端執行邏輯控制。依然使用函數cudaMemcpy2D（）進行拷貝，數據傳輸方向是設備端到主機端cudaMemcpyDeviceToHost（）。

⑺ 所有處理完成之后釋放所分配的存儲空間。

2.2 生成鍵值序列及鍵值排序并行算法設計

鍵值序列在樹形數據結構中表節點的權值，也代表了多維空間中數據的表達方式，計算鍵值序列的基礎是計算莫頓碼（Morton碼）[8]。

在八叉樹的數據結構中給定一個采樣點p，在d層（1<=d<=D）計算p的鍵值序列xyz，以及為鍵值序列排序。分別計算鍵值xd、yd、zd，定義Cdx為d-1層包含p點的節點Od-1的形心，p.x為采樣點p相對于形心的位置，若p.x位于節點Od-1的x軸平分線的左側，x鍵值為0，否則為1；y鍵值和z鍵值也以同樣的方法計算。

如此，深度為D的八叉樹鍵值序列表示為x1y1z1x2y2z2…xDyDzD，意義為從根節點到當前節點的路徑。但由于輸入點云數據是亂序的，由此生成的每個節點的鍵值序列也有可能是亂序的，還需對鍵值序列進行排序，可以使用CUDPP庫sort方法處理所生成的鍵值序列。

2.3 生成節點數組并生成完整八叉樹結構

由于八叉樹結構的每一個節點都有0個孩子節點或7個孩子節點，因此需要對生成的惟一節點數組補全剩余的7個節點數組信息。首先需要計算其余7個節點數組的起始索引地址，使用scan算法并行計算前綴求和的方法在上一個節點數組地址基礎上計算鄰接的節點數組地址，得到完整的八叉樹節點數組地址。

3 仿真結果

實驗所需輸入點云數據是所參與項目中使用的古建筑點云數據集jyd.ply。

使用改進過的表面重建算法，生成結果與原始算法結果對比截圖如圖3。

圖3左為jyd原始表面重建算法的重建結果，圖3右為本章改進算法的重建結果，從圖中可看出屋脊邊緣部分的孔洞問題得到解決。

分別使用這兩組數據串行計算和并行計算實驗三次，結果如表1。

根據表格中數據可知jyd三次的加速比分別為6.05、5.98、5.78，平均為5.93。

4 結論

通過引入屏蔽因子使用顯性插值方法對樣本點進行插值計算，避免了一次性全局偏移的方法估算指示函數出現重建結果誤差較大的情況，通過引入漸近線構造等值線正確連接方式的方法，避免了移動立方體算法中三角化過程可能出現的面二義性問題。實驗結果證明，改進的表面重建算法，可改善模型表面空洞問題。

同時并行算法設計方案實驗結果證明GPU并行算法提高了原有表面重建算法的執行效率。

參考文獻（References）：

[1] Lin Y， Chen C， Song M， et al. Dual-RBF based surface reconstruction[J]. The Visual Computer，2009.25（5-7）：599-607

[2] Li X， Wan W， Cheng X， et al. An improved poisson surface reconstruction algorithm[C]. International Conference on. IEEE，2010：1134-1138

[3] Yin C， Gang D， Zhi-quan C， et al. An algorithm of CUDA-based Poisson surface reconstruction[C]. Audio Language and Image Processing （ICALIP）， 2010 International Conference on，2010：203-207

[4] Zhou K， Gong M， Huang X， et al. Data-parallel octrees for surface reconstruction[J]. Visualization and Computer Graphics， IEEE Transactions on，2011.17（5）：669-681

[5] 陳建華，趙飛，葛永斌.求解3維泊松方程的一種新方法[J].江西師范大學學報（自然科學版），2013.4：411-415

[6] 游安軍編著.電路數學[M].北京電子工業出版社，2014.

[7] 蔣建剛.薛定諤和泊松方程有限元法求解[D].廣東工業大學碩士學位論文，2014.

[8] 楊宇，闞凌雁，于佳，等.基于激光掃描的人臉三維重建方法[J].紅外與激光工程，2014.12：3946-3950