點(diǎn)云重建的并行算法

楊 捷，吳素萍

1.寧夏大學(xué) 民族預(yù)科教育學(xué)院，銀川750021

2.寧夏大學(xué) 信息工程學(xué)院，銀川750021

1 引言

基于圖像的三維重建，將拍攝圖片作為基本輸入，經(jīng)過(guò)特征點(diǎn)提取、匹配、面片擴(kuò)展、過(guò)濾、點(diǎn)云重建、表面重建后，生成重建對(duì)象的三維立體模型[1]。

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

針對(duì)三維重建中耗時(shí)較長(zhǎng)、運(yùn)算量較大的點(diǎn)云重建過(guò)程，本文對(duì)該過(guò)程進(jìn)行并行設(shè)計(jì)。在對(duì)點(diǎn)云重建的三個(gè)基本過(guò)程：特征點(diǎn)匹配，面片擴(kuò)展和過(guò)濾進(jìn)行并行性分析的基礎(chǔ)上，給出點(diǎn)云重建過(guò)程在多核CPU、GPU 架構(gòu)、CPU/GPU 異構(gòu)環(huán)境下的并行算法，實(shí)現(xiàn)在保證重建精度的前提下，提高點(diǎn)云重建的效率。

2 點(diǎn)云重建過(guò)程并行性分析

2.1 點(diǎn)云重建過(guò)程

點(diǎn)云重建有兩個(gè)基本階段。第一階段是利用Harris[14]和DoG（Different of Gaussian）算子提取圖像序列的所有特征點(diǎn)，對(duì)特征點(diǎn)進(jìn)行特征點(diǎn)匹配、重建，生成種子點(diǎn)，即稀疏點(diǎn)云。第二階段，種子點(diǎn)被擴(kuò)展和過(guò)濾以獲得密集的空間點(diǎn)云，使得重建對(duì)象的表面信息更加完整?；诿嫫亩嘁晥D三維重建算法[15]，包含特征點(diǎn)匹配、面片擴(kuò)展、過(guò)濾三個(gè)過(guò)程。

2.1.1 特征點(diǎn)匹配

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

生成的有些面片可能包含錯(cuò)誤信息，根據(jù)公式（2）對(duì)面片進(jìn)行優(yōu)化，將不滿足條件的面片所對(duì)應(yīng)的特征點(diǎn)從圖像塊中刪除：

2.1.2 面片擴(kuò)展

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

2.1.3 過(guò)濾

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

2.2 并行性分析

本文對(duì)kermit 數(shù)據(jù)集（9 張、分辨率640×480、.jpg 格式）與hallFeng 數(shù)據(jù)集（61 張、分辨率3 008×20 000、.jpg格式），在CPU平臺(tái)上完成點(diǎn)云重建過(guò)程的多次串行實(shí)驗(yàn)，根據(jù)實(shí)驗(yàn)中點(diǎn)云重建各階段的運(yùn)行時(shí)間、數(shù)據(jù)的相關(guān)性和算法程序的耦合性，進(jìn)行可并行性分析。點(diǎn)云重建算法各階段的串行實(shí)驗(yàn)運(yùn)行時(shí)間統(tǒng)計(jì)如表1。

點(diǎn)云重建過(guò)程中，面片擴(kuò)展和過(guò)濾執(zhí)行三次，過(guò)濾階段在每次迭代中的耗時(shí)均少于27 s，所以表1 中給出的擴(kuò)展過(guò)濾時(shí)間，是面片擴(kuò)展和過(guò)濾兩個(gè)階段消耗的總時(shí)間。特征點(diǎn)匹配和面片擴(kuò)展階段的計(jì)算任務(wù)量大，耗時(shí)占整個(gè)點(diǎn)云重建算法運(yùn)行時(shí)間的8%和90%。

表1 串行實(shí)驗(yàn)的耗時(shí) s

從數(shù)據(jù)相關(guān)性、程序耦合性，分析特征匹配和擴(kuò)展過(guò)濾兩個(gè)階段的可并行性：點(diǎn)云重建算法的特征點(diǎn)匹配和擴(kuò)展階段均具有循環(huán)依賴性，因?yàn)榧螰 中的特征點(diǎn)在每層循環(huán)都參與計(jì)算，而且外層循環(huán)需要等待內(nèi)層循環(huán)處理結(jié)果，有數(shù)據(jù)依賴關(guān)系。

針對(duì)點(diǎn)云重建計(jì)算量大的部分及數(shù)據(jù)相關(guān)性，并行實(shí)現(xiàn)的部分主要包括以下四部分：

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

（2）三角定位獲得三維坐標(biāo)點(diǎn)。根據(jù)投影關(guān)系，恢復(fù)特征點(diǎn)對(duì)中的匹配點(diǎn)在三維場(chǎng)景中的對(duì)應(yīng)點(diǎn)。計(jì)算過(guò)程需要基于特征點(diǎn)匹配，利用已知的攝像機(jī)內(nèi)參求解基礎(chǔ)矩陣和本質(zhì)矩陣。

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

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

3 點(diǎn)云重建的并行算法

3.1 基于多核CPU的并行設(shè)計(jì)

基于多核CPU 的并行設(shè)計(jì)（圖1），采用OpenMP 的fork/join 模型，將特征點(diǎn)匹配和面片擴(kuò)展階段耗時(shí)較長(zhǎng)的計(jì)算任務(wù)，轉(zhuǎn)換成并行執(zhí)行區(qū)域。算法執(zhí)行過(guò)程中，主線程執(zhí)行到并行區(qū)域，CPU派生出多線程協(xié)助主線程共同完成計(jì)算，直到并行區(qū)域執(zhí)行完畢，派生線程被掛起，控制流再次回到主線程手中。

線程的派生-會(huì)合操作帶來(lái)的額外開(kāi)銷，實(shí)際上要比并行算法所能節(jié)省的時(shí)間大。為了減少派生、會(huì)和次數(shù)的開(kāi)銷，將多個(gè)計(jì)算任務(wù)的并行域合并，對(duì)算法需要迭代執(zhí)行部分采用循環(huán)級(jí)并行；對(duì)并行區(qū)域內(nèi)或循環(huán)迭代中不需要多線程執(zhí)行的語(yǔ)句，進(jìn)行標(biāo)記，通過(guò)減少派生會(huì)合次數(shù)，降低系統(tǒng)開(kāi)銷。

對(duì)于線程間的同步問(wèn)題，在并行域間添加barrier同步語(yǔ)句，以確保按照原來(lái)并行域的順序執(zhí)行：

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

圖1 基于多核CPU的并行設(shè)計(jì)

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

（3）當(dāng)并行域的執(zhí)行沒(méi)有數(shù)據(jù)依賴性時(shí)，不需要線程之間的同步，使用nowait子句顯式聲明程序。

3.2 基于CUDA的并行設(shè)計(jì)

基于CUDA的并行算法，對(duì)不存在相關(guān)性的數(shù)據(jù)處理，充分利用SIMT 特性進(jìn)行高性能并行處理，執(zhí)行數(shù)據(jù)的寬度作為硬件細(xì)節(jié)被隱藏起來(lái)，硬件可以自適應(yīng)地調(diào)整執(zhí)行寬度。將特征點(diǎn)匹配與面片擴(kuò)展過(guò)程分別劃分為一個(gè)個(gè)子任務(wù)，定義全局函數(shù)（NeighborRadiuscuda、collectCandidatescuda、initialMatchSubcuda）完成各子任務(wù)的并行計(jì)算。

NeighborRadiuskernel（）//判斷近鄰關(guān)系

{if 滿足以下兩個(gè)約束

a.面片不是面片的近鄰

b.圖像塊不存在深度不連續(xù)}

collectCandidateskernel（）

{并行計(jì)算特征點(diǎn)的NCC值，收集與其相匹配的點(diǎn)

并行計(jì)算匹配點(diǎn)的三維坐標(biāo)}

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

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

Refine c(p)and n(p)；

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

If | V*(p)|≥γ

addPatch//生成面片

removePatch//移除所有特征點(diǎn)}

設(shè)備端分配內(nèi)存時(shí)，算法根據(jù)圖像數(shù)據(jù)集的大小進(jìn)行動(dòng)態(tài)分配。在點(diǎn)云重建過(guò)程中，面片擴(kuò)展是特征匹配的后續(xù)步驟，因此特征匹配階段生成的patch數(shù)組，與面片擴(kuò)展階段生成的密集點(diǎn)云共享同一內(nèi)存空間。在執(zhí)行內(nèi)核函數(shù)時(shí)，并行算法給圖像的每個(gè)像素分配一個(gè)處理線程，來(lái)提高指令流效率。

圖2 優(yōu)化前的訪存模式

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

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

（1）將數(shù)據(jù)從設(shè)備存儲(chǔ)器加載到共享存儲(chǔ)器中。

（2）同步操作，使每個(gè)線程能夠安全地讀取其他線程寫(xiě)入的數(shù)據(jù)。

（3）在共享存儲(chǔ)器內(nèi)處理數(shù)據(jù)。

（4）再次同步以確保計(jì)算結(jié)果更新共享存儲(chǔ)器。

（5）將結(jié)果寫(xiě)回設(shè)備存儲(chǔ)器。

3.3 基于OpenCL的并行設(shè)計(jì)

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

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

在GPU 端，Kernel 函數(shù)在執(zhí)行過(guò)程中，對(duì)Global Memory的訪問(wèn)過(guò)于頻繁，會(huì)導(dǎo)致一定的性能損失，并影響Kernel 函數(shù)的執(zhí)行效率，而訪問(wèn)Local Memory 速度比較快。因此在Group 間相互交換數(shù)據(jù)、Kernel 函數(shù)需要保存輸出的數(shù)據(jù)時(shí)，將Group 中的共享數(shù)據(jù)寫(xiě)回Local Memory，在需要數(shù)據(jù)時(shí)直接讀取數(shù)據(jù)。

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

圖3 優(yōu)化后的訪存模式

3.4 基于CPU/GPU異構(gòu)環(huán)境的并行設(shè)計(jì)

基于CPU/GPU 的異構(gòu)計(jì)算是將GPU 作為傳統(tǒng)計(jì)算機(jī)系統(tǒng)加速組件的補(bǔ)充，配合CPU 共同承擔(dān)計(jì)算任務(wù)，有效提高任務(wù)的計(jì)算效率和系統(tǒng)的處理能力。在對(duì)點(diǎn)云重建進(jìn)行并行分析的基礎(chǔ)上，劃分計(jì)算任務(wù)分配給CPU和GPU，并優(yōu)化基于CPU/GPU異構(gòu)環(huán)境的并行設(shè)計(jì)。

為實(shí)現(xiàn)CPU 和GPU 負(fù)載平衡，CPU 負(fù)責(zé)動(dòng)態(tài)劃分任務(wù)、分配數(shù)據(jù)、執(zhí)行某些計(jì)算任務(wù)以及從GPU 讀取計(jì)算結(jié)果，GPU主要執(zhí)行點(diǎn)云重建的并行計(jì)算任務(wù)。優(yōu)化GPU 線程劃分，使GPU 能夠?qū)崿F(xiàn)更高的計(jì)算速度，從而提高整體系統(tǒng)性能。本文在實(shí)驗(yàn)平臺(tái)1 上，完成了基于OpenMP，OpenCL 和CUDA 架構(gòu)的點(diǎn)云重建并行算法的系列實(shí)驗(yàn)。計(jì)算任務(wù)根據(jù)統(tǒng)計(jì)計(jì)算的加速比進(jìn)行劃分：

（1）基于OpenMP、OpenCL 和CUDA 架構(gòu)，特征點(diǎn)匹配過(guò)程的執(zhí)行時(shí)間分別為：

（2）根據(jù)公式（6），計(jì)算任務(wù)劃分的邊界值：

在本文中，點(diǎn)云重建的混合并行實(shí)驗(yàn)是在兩種CPU/GPU 異 構(gòu) 環(huán) 境 中 完 成 的：OpenMP+OpenCL 和OpenMP+CUDA。在特定環(huán)境中將T1替換為相應(yīng)的GPU架構(gòu)下的執(zhí)行時(shí)間。

（3）根據(jù)邊界值B，劃分任務(wù)分配給CPU 和GPU。多核CPU 利用多線程，對(duì)區(qū)間[1:B]的數(shù)據(jù)完成并行處理；GPU并行計(jì)算處理[B:N]區(qū)間內(nèi)的數(shù)據(jù)。

劃分面片擴(kuò)展階段的計(jì)算任務(wù)，計(jì)算邊界值B是根據(jù)面片擴(kuò)展基于OpenMP、OpenCL 和CUDA 架構(gòu)的執(zhí)行時(shí)間：Texpandmp、Texpandcl、Texpandcuda，具體步驟與特征點(diǎn)匹配的任務(wù)劃分步驟一致。

4 實(shí)驗(yàn)及結(jié)果分析

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

4.1.1 硬件環(huán)境

實(shí)驗(yàn)平臺(tái)1（雙核四線程）

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

實(shí)驗(yàn)平臺(tái)2（四核四線程）

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

實(shí)驗(yàn)平臺(tái)3（六核十二線程）

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

4.1.2 軟件環(huán)境

系統(tǒng)：Windows 8，開(kāi)發(fā)平臺(tái)：Visual Studio 2010+CUDA Toolkit 5.0+OpenCL1.1。

4.2 并行效率分析

在多核CPU、GPU 架構(gòu)、CPU/GPU 異構(gòu)環(huán)境，分別完成點(diǎn)云重建并行算法實(shí)驗(yàn)，并與串行算法進(jìn)行比較。統(tǒng)計(jì)各階段的耗時(shí)（包括任務(wù)分配時(shí)間和數(shù)據(jù)通信時(shí)間），如表2。

根據(jù)表2 計(jì)算各個(gè)環(huán)境下并行點(diǎn)云重建過(guò)程所獲得的加速比，繪制圖4?；贠penMP+OpenCL 環(huán)境的并行算法，整個(gè)過(guò)程獲得了5.27 的加速比，其中特征點(diǎn)匹配階段獲得了3.27 的加速比，面片擴(kuò)展階段獲得了6.93 的加速比。基于OpenMP+CUDA 環(huán)境下的并行算法，整個(gè)過(guò)程獲得了5.53的加速比，其中特征點(diǎn)匹配階段獲得了3.45的加速比，面片擴(kuò)展階段獲得7.14的加速比。

圖4 并行算法獲得加速比對(duì)比圖

擴(kuò)展階段所獲得的加速比，相比較于多核CPU 提升了3.5 倍，相對(duì)于GPU 架構(gòu)下的并行提升了3 個(gè)加速比，說(shuō)明并行設(shè)計(jì)充分利用了CPU 和GPU 的資源。特征匹配階段的加速比得到提升的幅度不大，相比較于面片擴(kuò)展階段，特征匹配階段的數(shù)據(jù)量小、計(jì)算任務(wù)少，沒(méi)能充分利用GPU的資源。

4.3 擴(kuò)展性分析

對(duì)點(diǎn)云重建并行的擴(kuò)展性分析，本文從數(shù)據(jù)規(guī)模擴(kuò)展性和實(shí)驗(yàn)平臺(tái)擴(kuò)展性進(jìn)行分析。

對(duì)于數(shù)據(jù)規(guī)模的擴(kuò)展性，從hallFeng 數(shù)據(jù)集中分別選取21 張、41 張和61 張圖像組成不同規(guī)模大小的數(shù)據(jù)集。在實(shí)驗(yàn)平臺(tái)1 分別基于多核CPU、GPU 架構(gòu)和CPU/GPU 異構(gòu)環(huán)境，對(duì)不同規(guī)模大小數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，統(tǒng)計(jì)出各階段的執(zhí)行時(shí)間如表3。

表3 數(shù)據(jù)規(guī)模的擴(kuò)展性能分析

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

對(duì)于在實(shí)驗(yàn)平臺(tái)上的擴(kuò)展性分析，本文對(duì)hallFeng數(shù)據(jù)集（61張圖像），在實(shí)驗(yàn)平臺(tái)1、實(shí)驗(yàn)平臺(tái)2和實(shí)驗(yàn)平臺(tái)3上分別進(jìn)行實(shí)驗(yàn)，統(tǒng)計(jì)各階段的執(zhí)行時(shí)間如表4。

結(jié)合表4 和圖6，可以看出隨著實(shí)驗(yàn)平臺(tái)線程數(shù)和核數(shù)的擴(kuò)展，基于多核CPU、GPU 架構(gòu)和CPU/GPU 異構(gòu)環(huán)境的并行算法，獲得的加速比均得到顯著提升?；贑PU/GPU 異構(gòu)環(huán)境的并行，利用GPU 的計(jì)算性能和CPU 資源，六核十二線程環(huán)境下（實(shí)驗(yàn)平臺(tái)3）相對(duì)于四核八線程環(huán)境（實(shí)驗(yàn)平臺(tái)2），加速比提高了2.9，相對(duì)于雙核四線程環(huán)境（實(shí)驗(yàn)平臺(tái)1）加速比提高了4.11。

4.4 重建精度分析

在保證重建精度的前提下，通過(guò)并行設(shè)計(jì)提高點(diǎn)云重建的效率，才具有意義。從圖片集提取出的特征點(diǎn)，經(jīng)過(guò)點(diǎn)云重建過(guò)程生成重建對(duì)象的稠密點(diǎn)云，本文分別統(tǒng)計(jì)基于多核CPU、GPU 架構(gòu)和CPU/GPU 異構(gòu)環(huán)境下，統(tǒng)計(jì)出點(diǎn)云重建生成的稠密點(diǎn)云數(shù)量如表5。

分析表5，基于OpenCL 架構(gòu)，kermit 數(shù)據(jù)集最終生成了10 184 個(gè)點(diǎn)，丟失了1 個(gè)點(diǎn)，相比較于在CPU 上獲得的數(shù)量，重建精度仍達(dá)到99.99%。hallFeng 數(shù)據(jù)集，基于CUDA 架構(gòu)最終生成452 391 個(gè)點(diǎn)，重建精度在丟失了2 個(gè)點(diǎn)后仍達(dá)到了99.99%?；贑PU/GPU 異構(gòu)環(huán)境，kermit 數(shù)據(jù)集和hallFeng 數(shù)據(jù)集分別生成10 185 和452 393個(gè)點(diǎn)，重建對(duì)象獲得好的完整性。

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

點(diǎn)云重建對(duì)特征點(diǎn)提取出的初始特征點(diǎn)，進(jìn)行特征點(diǎn)匹配、面片擴(kuò)展和過(guò)濾后生成對(duì)象的稠密點(diǎn)云，是三維重建中非常關(guān)鍵的環(huán)節(jié)。針對(duì)三維重建的數(shù)據(jù)量、計(jì)算量大、耗時(shí)長(zhǎng)問(wèn)題，本文提出點(diǎn)云重建并行算法?；诙嗪薈PU、GPU 架構(gòu)和CPU/GPU 異構(gòu)環(huán)境，分別提出點(diǎn)云重建過(guò)程的并行算法，并對(duì)并行設(shè)計(jì)進(jìn)行優(yōu)化。針對(duì)kermit 和hallFeng 數(shù)據(jù)集的點(diǎn)云重建，并行算法的整體性能相比較于串行算法獲得不同幅度的提升，同時(shí)還保證了重建精度。在不同實(shí)驗(yàn)平臺(tái)上，對(duì)點(diǎn)云重建過(guò)程進(jìn)行并行實(shí)驗(yàn)，加速比隨著實(shí)驗(yàn)平臺(tái)CPU 核數(shù)的擴(kuò)增和GPU 性能的擴(kuò)展，得到顯著的提升；對(duì)不同規(guī)模大小的數(shù)據(jù)集的并行實(shí)驗(yàn)，加速比隨著數(shù)據(jù)集規(guī)模的增大而增大。

圖5 數(shù)據(jù)規(guī)模的擴(kuò)展性能分析

表4 實(shí)驗(yàn)平臺(tái)的擴(kuò)展性能分析

圖6 實(shí)驗(yàn)平臺(tái)的擴(kuò)展性能分析

表5 點(diǎn)云重建算法的精度分析

通過(guò)對(duì)實(shí)驗(yàn)結(jié)果的重建效率、重建精度和擴(kuò)展性能分析，點(diǎn)云重建的并行算法，在保證重建精度的條件下，取得了較好的加速比，并且并行算法具有實(shí)驗(yàn)平臺(tái)和數(shù)據(jù)規(guī)模的可擴(kuò)展性?；贑PU/GPU 異構(gòu)環(huán)境的并行算法，充分利用了CPU 資源，GPU 的計(jì)算性能也得到進(jìn)一步發(fā)揮。但是還需要更深入、充分挖掘點(diǎn)云重建的可并行性，進(jìn)一步優(yōu)化并行設(shè)計(jì)，并在基于多CPU和多GPU集群環(huán)境下，對(duì)點(diǎn)云重建算法進(jìn)行并行設(shè)計(jì)。