點云重建的并行算法

楊 捷，吳素萍

1.寧夏大學 民族預科教育學院，銀川750021

2.寧夏大學 信息工程學院，銀川750021

1 引言

基于圖像的三維重建，將拍攝圖片作為基本輸入，經過特征點提取、匹配、面片擴展、過濾、點云重建、表面重建后，生成重建對象的三維立體模型[1]。

基于圖像的三維重建的重建精度越高，重建模型越完整[2]。為了提高重建精度，需增加輸入圖像的數量，但同時又會增加三維重建的耗時[3]。近年來，解決這一問題以提高重建效率是計算機視覺領域研究人員關注的焦點[4]。提高解決問題的效率，主要有兩種：軟件加速和硬件加速[5]。軟件加速是指通過優化算法以提高解決問題的效率。硬件加速利用硬件資源，例如多核CPU、GPU和CPU/GPU異構環境。目前，許多問題的解決方案都采用了標準的統一方法，但并不是所有問題都適合采用軟件加速。并行計算不僅允許多個處理器單元每單位時間完成多個指令和數據流的計算，而且還將計算能力從單個處理器擴展到多個處理器，以獲得更高的計算性能。計算機視覺領域和圖形圖像處理使用GPU 的計算性能來解決問題中的由大型計算引起的高時間消耗[6-13]。文獻[6]利用GPU 實現了MSR 算法的并行化，顯著提高了多尺度高斯濾波、對數空間差和動態范圍壓縮的計算速度。文獻[8]采用GPU 通用高性能編程技術，實現了一種加速圖像匹配算法的新方法。在文獻[9]中，利用GPU 并行架構將虛實交互并行化，采用CUDA 編程模型完成相交判斷、體素狀態壓縮、三角網格化、紋理映射的并行計算，提高實時三維重建效率。文獻[10]中Kang給出一種漸進式的三維重建算法，對系統中耗時最長的SIFT特征檢測和稠密光流的計算，采用CUDA 架構進行并行化處理。文獻[13]通過CPU 和GPU的協同處理提高了行人檢測的檢測率和時間比。

針對三維重建中耗時較長、運算量較大的點云重建過程，本文對該過程進行并行設計。在對點云重建的三個基本過程：特征點匹配，面片擴展和過濾進行并行性分析的基礎上，給出點云重建過程在多核CPU、GPU 架構、CPU/GPU 異構環境下的并行算法，實現在保證重建精度的前提下，提高點云重建的效率。

2 點云重建過程并行性分析

2.1 點云重建過程

點云重建有兩個基本階段。第一階段是利用Harris[14]和DoG（Different of Gaussian）算子提取圖像序列的所有特征點，對特征點進行特征點匹配、重建，生成種子點，即稀疏點云。第二階段，種子點被擴展和過濾以獲得密集的空間點云，使得重建對象的表面信息更加完整。基于面片的多視圖三維重建算法[15]，包含特征點匹配、面片擴展、過濾三個過程。

2.1.1 特征點匹配

從圖像提取出的特征點，對于一幅圖像Ii中的任一特征點f，根據計算公式（1）的值，在其他圖像中收集相同類型（Harris 或DoG）的特征點f′,加入集合F。使用特征點對(f,f′)，通過三角測量法[16]獲得三維坐標點。根據與相機光學中心O(Ii)的距離，對三維坐標點進行升序排序，并且以三維坐標點為潛在的面片中心，有序地生成面片：

生成的有些面片可能包含錯誤信息，根據公式（2）對面片進行優化，將不滿足條件的面片所對應的特征點從圖像塊中刪除：

2.1.2 面片擴展

對于種子面片p，判斷存儲面片p 的圖像塊中是否已經存在一個面片p′，且滿足近鄰關系公式（4）。若不存在，則確定該圖像塊可擴展，并加入到圖像塊集C(p)中。將圖像塊集C(p)中的每一個圖像塊Ci(x,y)，擴展生成新的面片[17]：

2.1.3 過濾

面片擴展階段，通過深度測試的面片，也可能由于匹配錯誤，并沒有添加到集合V*(p)中，而是直接替換掉V*(p)，進而使得面片相關聯的可見信息不一致。為確保生成面片的準確性，根據公式（5）判斷是否滿足可見光一致性，剔除幾何一致性和灰度一致性較差的異常面片[18]：

2.2 并行性分析

本文對kermit 數據集（9 張、分辨率640×480、.jpg 格式）與hallFeng 數據集（61 張、分辨率3 008×20 000、.jpg格式），在CPU平臺上完成點云重建過程的多次串行實驗，根據實驗中點云重建各階段的運行時間、數據的相關性和算法程序的耦合性，進行可并行性分析。點云重建算法各階段的串行實驗運行時間統計如表1。

點云重建過程中，面片擴展和過濾執行三次，過濾階段在每次迭代中的耗時均少于27 s，所以表1 中給出的擴展過濾時間，是面片擴展和過濾兩個階段消耗的總時間。特征點匹配和面片擴展階段的計算任務量大，耗時占整個點云重建算法運行時間的8%和90%。

表1 串行實驗的耗時 s

從數據相關性、程序耦合性，分析特征匹配和擴展過濾兩個階段的可并行性：點云重建算法的特征點匹配和擴展階段均具有循環依賴性，因為集合F 中的特征點在每層循環都參與計算，而且外層循環需要等待內層循環處理結果，有數據依賴關系。

針對點云重建計算量大的部分及數據相關性，并行實現的部分主要包括以下四部分：

（1）計算特征點的NCC系數。對提取出的Harris和DoG 特征點，利用公式（1）計算NCC（Normalized Cross Correlation，歸一化互相關）系數[19]，在其他圖像上收集相同類型的特征點，獲得一組匹配的點對，并加入集合F。

（2）三角定位獲得三維坐標點。根據投影關系，恢復特征點對中的匹配點在三維場景中的對應點。計算過程需要基于特征點匹配，利用已知的攝像機內參求解基礎矩陣和本質矩陣。

（3）計算面片的光度差函數值。①在面片p上覆蓋一個μ×μ的網格；②將網格投影到圖像上，并通過雙線性插值對像素顏色值q(p,I1)進行采樣；③計算I 減去q(p,I1)和q(p,I2)的NCC 值。面片是計算過程的基本單位。

（4）判斷近鄰關系。利用公式（4），判斷圖像塊Ci(x′,y′)對應的面片p′，與面片p 是否滿足近鄰關系。若滿足，則從集合C(p)中刪除圖像塊Ci(x′,y′)。面片是判斷近鄰關系的基本單位。

3 點云重建的并行算法

3.1 基于多核CPU的并行設計

基于多核CPU 的并行設計（圖1），采用OpenMP 的fork/join 模型，將特征點匹配和面片擴展階段耗時較長的計算任務，轉換成并行執行區域。算法執行過程中，主線程執行到并行區域，CPU派生出多線程協助主線程共同完成計算，直到并行區域執行完畢，派生線程被掛起，控制流再次回到主線程手中。

線程的派生-會合操作帶來的額外開銷，實際上要比并行算法所能節省的時間大。為了減少派生、會和次數的開銷，將多個計算任務的并行域合并，對算法需要迭代執行部分采用循環級并行；對并行區域內或循環迭代中不需要多線程執行的語句，進行標記，通過減少派生會合次數，降低系統開銷。

對于線程間的同步問題，在并行域間添加barrier同步語句，以確保按照原來并行域的順序執行：

（1）在并行域之前或并行域之后，如果存在串行域，則不添加barrier同步。

圖1 基于多核CPU的并行設計

（2）合并并行域時，在它們之間添加barrier同步。

（3）當并行域的執行沒有數據依賴性時，不需要線程之間的同步，使用nowait子句顯式聲明程序。

3.2 基于CUDA的并行設計

基于CUDA的并行算法，對不存在相關性的數據處理，充分利用SIMT 特性進行高性能并行處理，執行數據的寬度作為硬件細節被隱藏起來，硬件可以自適應地調整執行寬度。將特征點匹配與面片擴展過程分別劃分為一個個子任務，定義全局函數（NeighborRadiuscuda、collectCandidatescuda、initialMatchSubcuda）完成各子任務的并行計算。

NeighborRadiuskernel（）//判斷近鄰關系

{if 滿足以下兩個約束

a.面片不是面片的近鄰

b.圖像塊不存在深度不連續}

collectCandidateskernel（）

{并行計算特征點的NCC值，收集與其相匹配的點

并行計算匹配點的三維坐標}

initialMatchSubkernel（）//通 過initial V(p),V*(p)；refine c(p),n(p)；update V(p),V*(p)三步生成一個patch

{Initialize V(p)and V*(p)；

Refine c(p)and n(p)；

Update V(p)and V*(p)；

If | V*(p)|≥γ

addPatch//生成面片

removePatch//移除所有特征點}

設備端分配內存時，算法根據圖像數據集的大小進行動態分配。在點云重建過程中，面片擴展是特征匹配的后續步驟，因此特征匹配階段生成的patch數組，與面片擴展階段生成的密集點云共享同一內存空間。在執行內核函數時，并行算法給圖像的每個像素分配一個處理線程，來提高指令流效率。

圖2 優化前的訪存模式

在設置block 的大小時，需要考慮SM 的資源，比如shared memory、registers 等，并不是線程的數量越多，SM 的處理效率就會越高。如果block的大小過大，可能會使block 中的線程能分配到的存儲資源更少，而且受訪問約束會影響，只激活被允許訪問的線程，其他線程不能進行任何指令的操作，反而降低了SM 的效率。block中的線程是以warp為單位劃分為組，每個block中的線程數應是32的倍數。由于每個warp中是按順序執行，因此要求每個線程中不能有過多的資源需求和復雜的循環。本文實驗的顯卡是NVIDIA GeForce GT 630M，根據點云重建算法的復雜性，以32 個并行線程為單位劃分，可以方便線程的調度。

點云重建將從圖像集中提取特征點，通過特征點匹配生成稀疏點云，進一步擴展和過濾生成重建對象的密集點云。此過程中的中間數據量大，需要在主機存儲器和設備存儲器之間傳輸數據。通過共享內存和緩存來最大限度地使用片上存儲器，以減少全局存儲器和設備之間的數據傳輸。并行算法優化，塊內線程將從設備存儲器中取回的數據存儲在共享存儲器中，提高處理效率。具體操作如下：

（1）將數據從設備存儲器加載到共享存儲器中。

（2）同步操作，使每個線程能夠安全地讀取其他線程寫入的數據。

（3）在共享存儲器內處理數據。

（4）再次同步以確保計算結果更新共享存儲器。

（5）將結果寫回設備存儲器。

3.3 基于OpenCL的并行設計

基于OpenCL 的并行算法，采用的執行模型：CPU端的主程序和GPU 端的執行程序Kernel。CPU 端的程序主要設置Kernel 執行的上下文、工作空間NDRange、傳遞參數值、執行Kernel等。GPU端完成Kernel程序的并行和優化。

在CPU 端，對于工作空間NDRange大小的劃分，嘗試8×8和16×16兩種大小的線程組劃分方式。由于線程在GPU 上以wavefront 為單位并行執行，一個wavefront中的所有線程，并行執行GPU 發出每條指令，因此最終選擇16×16 大小的線程組，以使得硬件性能更好地發揮出來。在同一個工作組內，使用barrier 函數，實現一個工作組中的不同工作項之間的同步。

在GPU 端，Kernel 函數在執行過程中，對Global Memory的訪問過于頻繁，會導致一定的性能損失，并影響Kernel 函數的執行效率，而訪問Local Memory 速度比較快。因此在Group 間相互交換數據、Kernel 函數需要保存輸出的數據時，將Group 中的共享數據寫回Local Memory，在需要數據時直接讀取數據。

在并行算法設計中，將數組分成多個區間，每個區間中的幾個連續元素交由一個線程計算處理。如圖2、圖3 所示，在面片擴展階段，將特征點匹配生成的patch數組中的面片，依據是否滿足某一判定條件，擴展出它們的相鄰面片，線程讀取patch數組元素時，依次讀取連續的幾個元素。例如當Thread0訪問pat ch[0]的元素時，Thread1則在訪問patch[(patch lenth/get global size(0))]的 元 素 ， Thread2 在 訪 問patch[2×(patch lenth/get globalsize(0))]的元素。但是該訪存模式破壞了數據訪問局部性要求，內存讀取的速度緩慢。針對這個問題，利用數據讀取的局部性要求，在Thread 需要對稀疏點云patch 數組進行讀寫時，使Thread0 訪 問 patch[0]時 ，Thread1 訪 問patch[1],…,ThreadN-1 訪問patch[n-1]，內存讀取速度得到顯著提高。

圖3 優化后的訪存模式

3.4 基于CPU/GPU異構環境的并行設計

基于CPU/GPU 的異構計算是將GPU 作為傳統計算機系統加速組件的補充，配合CPU 共同承擔計算任務，有效提高任務的計算效率和系統的處理能力。在對點云重建進行并行分析的基礎上，劃分計算任務分配給CPU和GPU，并優化基于CPU/GPU異構環境的并行設計。

為實現CPU 和GPU 負載平衡，CPU 負責動態劃分任務、分配數據、執行某些計算任務以及從GPU 讀取計算結果，GPU主要執行點云重建的并行計算任務。優化GPU 線程劃分，使GPU 能夠實現更高的計算速度，從而提高整體系統性能。本文在實驗平臺1 上，完成了基于OpenMP，OpenCL 和CUDA 架構的點云重建并行算法的系列實驗。計算任務根據統計計算的加速比進行劃分：

（1）基于OpenMP、OpenCL 和CUDA 架構，特征點匹配過程的執行時間分別為：

（2）根據公式（6），計算任務劃分的邊界值：

在本文中，點云重建的混合并行實驗是在兩種CPU/GPU 異 構 環 境 中 完 成 的：OpenMP+OpenCL 和OpenMP+CUDA。在特定環境中將T1替換為相應的GPU架構下的執行時間。

（3）根據邊界值B，劃分任務分配給CPU 和GPU。多核CPU 利用多線程，對區間[1:B]的數據完成并行處理；GPU并行計算處理[B:N]區間內的數據。

劃分面片擴展階段的計算任務，計算邊界值B是根據面片擴展基于OpenMP、OpenCL 和CUDA 架構的執行時間：Texpandmp、Texpandcl、Texpandcuda，具體步驟與特征點匹配的任務劃分步驟一致。

4 實驗及結果分析

4.1 實驗環境

4.1.1 硬件環境

實驗平臺1（雙核四線程）

CPU：Intel?_CoreTM_i5-3210M_CPU_@_2.50 GHz，顯卡：NVIDIA GeForce GT 630M。

實驗平臺2（四核四線程）

CPU：Intel?Q9400 @ 2.67 GHz，顯卡：NVIDIA GeForce GTX 260。

實驗平臺3（六核十二線程）

CPU：Intel?Xeo?CPU E5-2620 0 @ 2.00 GHz，顯卡：NVIDIA Quadro K2000。

4.1.2 軟件環境

系統：Windows 8，開發平臺：Visual Studio 2010+CUDA Toolkit 5.0+OpenCL1.1。

4.2 并行效率分析

在多核CPU、GPU 架構、CPU/GPU 異構環境，分別完成點云重建并行算法實驗，并與串行算法進行比較。統計各階段的耗時（包括任務分配時間和數據通信時間），如表2。

根據表2 計算各個環境下并行點云重建過程所獲得的加速比，繪制圖4。基于OpenMP+OpenCL 環境的并行算法，整個過程獲得了5.27 的加速比，其中特征點匹配階段獲得了3.27 的加速比，面片擴展階段獲得了6.93 的加速比。基于OpenMP+CUDA 環境下的并行算法，整個過程獲得了5.53的加速比，其中特征點匹配階段獲得了3.45的加速比，面片擴展階段獲得7.14的加速比。

圖4 并行算法獲得加速比對比圖

擴展階段所獲得的加速比，相比較于多核CPU 提升了3.5 倍，相對于GPU 架構下的并行提升了3 個加速比，說明并行設計充分利用了CPU 和GPU 的資源。特征匹配階段的加速比得到提升的幅度不大，相比較于面片擴展階段，特征匹配階段的數據量小、計算任務少，沒能充分利用GPU的資源。

4.3 擴展性分析

對點云重建并行的擴展性分析，本文從數據規模擴展性和實驗平臺擴展性進行分析。

對于數據規模的擴展性，從hallFeng 數據集中分別選取21 張、41 張和61 張圖像組成不同規模大小的數據集。在實驗平臺1 分別基于多核CPU、GPU 架構和CPU/GPU 異構環境，對不同規模大小數據集進行實驗，統計出各階段的執行時間如表3。

表3 數據規模的擴展性能分析

根據表3 計算各個環境下并行后獲得的加速比，繪制圖5，可以看出隨著數據集規模大小的增加，點云重建在不同并行環境下的并行算法，獲得的加速比也在增大。在多核CPU 環境，點云重建并行算法受數據相關和緊耦合的同步關系約束，加速比得到小幅度的提升。在GPU 架構和CPU/GPU 異構環境下，隨著數據集規模從21 張圖像增加到61 張圖像，算法獲得的加速比也在不斷增加。

對于在實驗平臺上的擴展性分析，本文對hallFeng數據集（61張圖像），在實驗平臺1、實驗平臺2和實驗平臺3上分別進行實驗，統計各階段的執行時間如表4。

結合表4 和圖6，可以看出隨著實驗平臺線程數和核數的擴展，基于多核CPU、GPU 架構和CPU/GPU 異構環境的并行算法，獲得的加速比均得到顯著提升。基于CPU/GPU 異構環境的并行，利用GPU 的計算性能和CPU 資源，六核十二線程環境下（實驗平臺3）相對于四核八線程環境（實驗平臺2），加速比提高了2.9，相對于雙核四線程環境（實驗平臺1）加速比提高了4.11。

4.4 重建精度分析

在保證重建精度的前提下，通過并行設計提高點云重建的效率，才具有意義。從圖片集提取出的特征點，經過點云重建過程生成重建對象的稠密點云，本文分別統計基于多核CPU、GPU 架構和CPU/GPU 異構環境下，統計出點云重建生成的稠密點云數量如表5。

分析表5，基于OpenCL 架構，kermit 數據集最終生成了10 184 個點，丟失了1 個點，相比較于在CPU 上獲得的數量，重建精度仍達到99.99%。hallFeng 數據集，基于CUDA 架構最終生成452 391 個點，重建精度在丟失了2 個點后仍達到了99.99%。基于CPU/GPU 異構環境，kermit 數據集和hallFeng 數據集分別生成10 185 和452 393個點，重建對象獲得好的完整性。

5 結束語

點云重建對特征點提取出的初始特征點，進行特征點匹配、面片擴展和過濾后生成對象的稠密點云，是三維重建中非常關鍵的環節。針對三維重建的數據量、計算量大、耗時長問題，本文提出點云重建并行算法。基于多核CPU、GPU 架構和CPU/GPU 異構環境，分別提出點云重建過程的并行算法，并對并行設計進行優化。針對kermit 和hallFeng 數據集的點云重建，并行算法的整體性能相比較于串行算法獲得不同幅度的提升，同時還保證了重建精度。在不同實驗平臺上，對點云重建過程進行并行實驗，加速比隨著實驗平臺CPU 核數的擴增和GPU 性能的擴展，得到顯著的提升；對不同規模大小的數據集的并行實驗，加速比隨著數據集規模的增大而增大。

圖5 數據規模的擴展性能分析

表4 實驗平臺的擴展性能分析

圖6 實驗平臺的擴展性能分析

表5 點云重建算法的精度分析

通過對實驗結果的重建效率、重建精度和擴展性能分析，點云重建的并行算法，在保證重建精度的條件下，取得了較好的加速比，并且并行算法具有實驗平臺和數據規模的可擴展性。基于CPU/GPU 異構環境的并行算法，充分利用了CPU 資源，GPU 的計算性能也得到進一步發揮。但是還需要更深入、充分挖掘點云重建的可并行性，進一步優化并行設計，并在基于多CPU和多GPU集群環境下，對點云重建算法進行并行設計。