一種異步執(zhí)行改進(jìn)三維重構(gòu)的并行方法

劉 鎮(zhèn)，孟騰騰，徐克輝

(1.江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 鎮(zhèn)江 212003) (2.中國(guó)船舶重工集團(tuán)有限公司 第七二四研究所， 南京 211153)

隨著虛擬現(xiàn)實(shí)技術(shù)的不斷發(fā)展,人機(jī)交互方式的三維場(chǎng)景擺脫了傳統(tǒng)文本圖像的信息交流方式,虛擬購(gòu)物、虛擬教學(xué)、遠(yuǎn)程可視化等虛擬現(xiàn)實(shí)技術(shù)不斷得到普及[1]．與此同時(shí),可編程圖像處理器GPU編程技術(shù)的成熟,以及其強(qiáng)大的并行計(jì)算和浮點(diǎn)運(yùn)算能力為圖像處理的加速提供了編程基礎(chǔ)．面對(duì)越來(lái)越大的處理規(guī)模,以及越來(lái)越高的用戶體驗(yàn),如何提高實(shí)時(shí)性成為計(jì)算機(jī)圖像系統(tǒng)的研究熱點(diǎn).獲取傳統(tǒng)三維模型需要大量采集數(shù)據(jù)且借助于建模工具.近年來(lái)發(fā)展的結(jié)構(gòu)光法和運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)法(structure from motion, SFM)均可進(jìn)行三維模型重建．結(jié)構(gòu)光法適合于室內(nèi)高精度重建,目前商業(yè)產(chǎn)品比較多,相對(duì)復(fù)雜；SFM方法比結(jié)構(gòu)光方便,但精度差些,其主要用于無(wú)人機(jī)對(duì)大型建筑建模．針對(duì)這一現(xiàn)狀,文中提出了一種基于多目視頻流的并行化三維重構(gòu)方法,該方法中移動(dòng)終端和服務(wù)端異步執(zhí)行,終端對(duì)多目視頻流并行解碼,服務(wù)端對(duì)傳回的關(guān)鍵幀進(jìn)行特征提取、立體匹配,最后,將計(jì)算的視差結(jié)合投影矩陣恢復(fù)三維場(chǎng)景．

1 基于多目視頻流的并行化重構(gòu)方法

分布并行化重構(gòu)方法整體流程如圖1.

圖1 分布并行化重構(gòu)方法整體流程Fig.1 Overall workflow of distributed parallel reconstruction

1.1 終端節(jié)點(diǎn)執(zhí)行碼流解碼

H.264視頻編解碼包括提取層(network abstraction layer, NAL)和解碼層，其串行解碼框架如圖2.

圖2 H.264串行解碼框架Fig.2 Frame of H.264 serial decoding

文中以NVIDIA Jetson-TK1作為終端節(jié)點(diǎn)實(shí)現(xiàn)對(duì)H.264基本檔次碼流的解碼,主要提取視頻這種密集型數(shù)據(jù)結(jié)構(gòu)中的關(guān)鍵幀(I幀)．其解碼策略以CPU為主導(dǎo)進(jìn)行碼流分析、熵解碼與重排序[2],GPU負(fù)責(zé)幀間預(yù)測(cè)、變換解碼和環(huán)路濾波等．圖3給出了CPU、GPU協(xié)同處理示意,即GPU在處理第N幀的模塊時(shí),CPU同時(shí)解析第N+1幀的數(shù)據(jù),充分利用碎片時(shí)間,達(dá)到更高的處理效率,同時(shí)將得到的I幀傳回服務(wù)器端．

圖3 CPU、GPU協(xié)同處理示意Fig.3 CPU, GPU collaborative processing

1.2 服務(wù)器端算法原理及改進(jìn)策略

為了提高服務(wù)端重構(gòu)效率，文中采用CUDA(compute unified device architecture)加速尺度不變特征變換(scale invariant feeature transform，SIFT)方法.該方法充分利用CUDA合理分配主機(jī)和設(shè)備端的資源;在解決CPU和GPU數(shù)據(jù)傳輸延遲問(wèn)題中,引入了動(dòng)態(tài)CPU+GPU的類多級(jí)流水線調(diào)整策略,充分利用了CUDA架構(gòu)特點(diǎn),提高整體計(jì)算性能．

1.2.1 尺度不變空間特征點(diǎn)檢測(cè)

高斯差分尺度空間[3-4]的構(gòu)建、局部特征點(diǎn)檢測(cè)、定位特征點(diǎn)主方向和生成特征描述符為SIFT算法的4大步驟．

對(duì)輸入每一幀視頻圖像序列I(x,y),進(jìn)行高斯濾波,則有：

L(x,y,σ)=G(x,y,σ)*I(x,y)

(1)

式中:符號(hào)*為卷積;G(x,y,σ)為尺度可變高斯函數(shù).

(2)

式中:(x,y)為空間坐標(biāo),代表圖像的像素位置；σ為尺度空間因子．對(duì)不同的尺度高斯差分核構(gòu)建高斯差分尺度空間(difference of Gaussian,DOG),計(jì)算公式為:

D(x,y,σ)=L(x,y,kσ)-L(x,y,σ)

(3)

式中，系數(shù)k決定了高斯組中尺度層的數(shù)目.將DOG空間中的26個(gè)的像素點(diǎn)(上下及相鄰區(qū)域)作為候選點(diǎn),并在候選點(diǎn)處展開(kāi)泰勒公式,計(jì)算為:

(4)

式中，v=(xyσ)T.由上式解得亞像素及亞尺度的精確坐標(biāo)為:

(5)

(6)

式中，Tr(MHes)和Det(MHes)分別為該矩陣的幾何行列式和與矩陣特征值相關(guān)的閾值．此外,為使特征點(diǎn)具有旋轉(zhuǎn)不變性,為每一個(gè)特征點(diǎn)再計(jì)算一定領(lǐng)域內(nèi)所有像素點(diǎn)的梯度,并統(tǒng)計(jì)梯度方向直方圖,峰值為其主方向．最后,為了增強(qiáng)匹配的穩(wěn)健性[5-6],以特征點(diǎn)為中心，16×16像素區(qū)域內(nèi)的主方向?yàn)榉较蛄窟M(jìn)行分格梯度直方圖統(tǒng)計(jì)及高斯加權(quán),形成128維的特征描述符,接著通過(guò)比較兩兩之間的歐式距離獲取匹配的特征點(diǎn)對(duì)．

1.2.2 基于CUDA的SIFT算法的改進(jìn)策略

文中采用基于CUDA并行化方法加速的SIFT算法.在SIFT特征提取模塊中,比較耗時(shí)的模塊為建立高斯差分金字塔、定位特征點(diǎn)、確定關(guān)鍵點(diǎn)主方向．如圖4,文中采用CUDA統(tǒng)一計(jì)算架構(gòu)方法把邏輯性比較強(qiáng),計(jì)算量比較小的計(jì)算高期核函數(shù)放在CPU主機(jī)端,而把周期性的建立高斯差分金字塔、計(jì)算極植點(diǎn)，提取主方向放在GPU設(shè)備端．

圖5給出整體結(jié)構(gòu)示意圖，具體步驟：① 主機(jī)端(CPU端)進(jìn)行圖像輸入、圖像初始化、高斯核函數(shù)計(jì)算,同時(shí)將計(jì)算結(jié)果傳到設(shè)備端；② 設(shè)備端(GPU端)將CPU端得到的卷積模板傳入其常量存儲(chǔ)區(qū),建立高斯金字塔,之后傳回CPU端,同時(shí)將相鄰圖像層之間相減得到差分金字塔；③ 在差分空間中進(jìn)行特征點(diǎn)檢測(cè),將得到的尺度和位置信息載入GPU端,GPU端進(jìn)行精確定位關(guān)鍵點(diǎn),根據(jù)高斯權(quán)函數(shù)提取關(guān)鍵點(diǎn)主方向,然后再將關(guān)鍵點(diǎn)的信息傳回CPU端；④ CPU端以特征點(diǎn)為中心,主方向?yàn)榉ㄏ蛄?進(jìn)行分格梯度直方圖統(tǒng)計(jì)及高斯加權(quán),形成128維的特征描述符．

由于CPU和GPU端進(jìn)行數(shù)據(jù)傳遞比較耗時(shí)，采用類多級(jí)流水線和共享內(nèi)存復(fù)用的方法來(lái)提高計(jì)算效率．

1.2.3 GPU端流水線調(diào)整策略

上述方法在計(jì)算任務(wù)分配過(guò)程中,充分利用了GPU優(yōu)勢(shì),但CPU與GPU之間頻繁的內(nèi)存拷貝造成一定時(shí)間延遲,文中采用核函數(shù)異步執(zhí)行的類CPU多級(jí)流水線方式提高計(jì)算效率．因?yàn)槊總€(gè)流內(nèi)數(shù)據(jù)傳輸是按一定順序執(zhí)行的,而在CUDA統(tǒng)一計(jì)算架構(gòu)下,流之間可以異步執(zhí)行,文中將任務(wù)分成4個(gè)階段,充分利用流之間異步執(zhí)行特性,按類CPU多級(jí)流水線方式執(zhí)行4個(gè)核函數(shù),這一方法解決了數(shù)據(jù)拷貝造成的傳輸延遲問(wèn)題．

1.3 特征匹配及三維場(chǎng)景恢復(fù)

上述SIFT算法輸出的匹配關(guān)系存在部分出錯(cuò)率,且非常耗時(shí),文中采用CUDA架構(gòu)并行化近似最鄰近特征匹配方法，將計(jì)算得到的視差，結(jié)合投影矩陣恢復(fù)三維場(chǎng)景．

1.3.1 基于CUDA架構(gòu)改進(jìn)近似最鄰近特征匹配算法

對(duì)SIFT算法得到的兩組128維的特征描述符V1、V2分別建立KD樹(shù),傳統(tǒng)的KD樹(shù)數(shù)據(jù)結(jié)構(gòu)搜索效果很差,需要多次對(duì)其進(jìn)行平衡．即在構(gòu)建KD樹(shù),選擇超平面時(shí),取方差最大的維度,同時(shí)在中位數(shù)處進(jìn)行分割．為了提高計(jì)算性能,最鄰近特征匹配算法并不尋找嚴(yán)格最鄰近,而是在KD樹(shù)上尋找近似最鄰近(approximate nearest neighbor, ANN)特征點(diǎn)．匹配是否被采納采用一個(gè)優(yōu)先序列查找ANN，取代傳統(tǒng)的閥值限定,最后通過(guò)第一、二的距離比來(lái)確定是否采納．同時(shí)V1，V2必須同時(shí)互為ANN,匹配V1,V2才被采納[7-8]．

紅黑樹(shù)是一種自平衡二叉樹(shù),并已廣泛應(yīng)用于基于搜索的程序中[9-12]，包括文本挖掘和核苷酸序列匹配．對(duì)于包含n個(gè)節(jié)點(diǎn)的樹(shù)形結(jié)構(gòu),其查詢、插入和刪除等操作的平均時(shí)間復(fù)雜度為O(lgn)．文中方法的具體步驟如下:

(1) 在CPU端,構(gòu)建包含紅黑樹(shù)特性的KD樹(shù)數(shù)據(jù)結(jié)構(gòu),并完成數(shù)據(jù)初始化,GPU負(fù)責(zé)查找兩個(gè)最鄰近特征;同時(shí),每一個(gè)線程負(fù)責(zé)一維的特征描述符匹配,則每個(gè)線柱塊可以負(fù)責(zé)128維的特征描述符匹配,邊緣不足128的進(jìn)行補(bǔ)零操作,以減少判斷開(kāi)銷．在計(jì)算最鄰近特征時(shí),使用歐式距離比較相似度,假設(shè)兩個(gè)特征點(diǎn)用向量a,b表示,則向量a,b的歐式距離為每一維度差值的平方和的平方根,計(jì)算公式如式(7);同時(shí),圖6為GPU并行計(jì)算Li的過(guò)程,即首先將特征信息發(fā)送到GPU顯存中,隨后生成若干GPU線程負(fù)責(zé)相應(yīng)像素的并行計(jì)算．

(7)

(2) 在每個(gè)連接點(diǎn)集的每個(gè)圖像點(diǎn)和它的第一圖像點(diǎn)之間建立聯(lián)系．紅黑樹(shù)的鍵被設(shè)置為連接點(diǎn)集的第一圖像點(diǎn);當(dāng)圖像點(diǎn)不是第一個(gè)連接點(diǎn)時(shí),

是不能在鍵值中被找到的．

(3) 創(chuàng)建連接點(diǎn)集中每個(gè)圖像點(diǎn)和第一個(gè)像素點(diǎn)之間的關(guān)系．加載每個(gè)被構(gòu)建的連接點(diǎn)并保存到密鑰文件．創(chuàng)建這種密鑰文件之后,如果兩個(gè)匹配的圖像點(diǎn)不是兩個(gè)連接點(diǎn)集的第一個(gè)像素點(diǎn),可以很容易地通過(guò)密鑰文件的幫助,搜索其匹配的像素點(diǎn)．

通過(guò)分析上述匹配改進(jìn)策略及快速查找方法,可總結(jié)出基于CUDA的并行最鄰近特征匹配算法.偽代碼為．

圖6 計(jì)算特征點(diǎn)歐式距離的GPU資源劃分Fig.6 GPU resources division of computing the key point Euclidean distance

(4) 在上述密鑰交換方法中,在確定一個(gè)新的可用連接點(diǎn)集合是否應(yīng)與現(xiàn)有的連接點(diǎn)集進(jìn)行組合時(shí),只需要搜索紅黑樹(shù)而不是所有的密鑰集合之間的鍵值圖像點(diǎn),搜索成本低且有效．此外,該方法只加載必要的候選連接點(diǎn)集并始終立即釋放不必要的點(diǎn)集;因此,它可以保證在增加所限定的樹(shù)中節(jié)點(diǎn)的數(shù)目和多連接點(diǎn)集時(shí)不增加搜索的運(yùn)行時(shí)間．因此,在不違反內(nèi)存容量處理時(shí),這種方法也是可行和有效的．

1.3.2 由投影矩陣恢復(fù)三維場(chǎng)景

(8)

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

文中使用NVIDIA Jetson-TK1嵌入式開(kāi)發(fā)組件作為移動(dòng)終端實(shí)驗(yàn)節(jié)點(diǎn),該設(shè)備具有4核ARM Cortex-A15 CPU、包含192個(gè)CUDA核心的Kepler GPU、2GB運(yùn)行內(nèi)存、8路信號(hào)輸入接口.服務(wù)器端設(shè)備如下：Intel(R) Core(TM) i7-4770 3.40GHz CPU,NVIDIA Tesla K20c GPU、16GB內(nèi)存,系統(tǒng)環(huán)境為Ubuntu14.04和CUDA6.5開(kāi)發(fā)平臺(tái)．

實(shí)驗(yàn)一，使用微軟Kinect傳感器和文中方法分別對(duì)室內(nèi)場(chǎng)景建模,對(duì)比實(shí)驗(yàn)結(jié)果如圖7,實(shí)驗(yàn)表明文中方法在精度上基本滿足要求.

圖7 建模結(jié)果對(duì)比Fig.7 Comparison of modeling results

多目并行化重構(gòu)方法對(duì)單一場(chǎng)景多角度重構(gòu)結(jié)果較理想,在進(jìn)行實(shí)時(shí)場(chǎng)景重構(gòu)時(shí),能夠基本滿足及時(shí)性,但由于實(shí)驗(yàn)采用雙目結(jié)構(gòu),實(shí)驗(yàn)結(jié)果存在部分陰影現(xiàn)象．

實(shí)驗(yàn)二，對(duì)標(biāo)準(zhǔn)圖Tsukuba的RGB彩色圖像進(jìn)行了三維重構(gòu),實(shí)驗(yàn)結(jié)果如圖8,實(shí)驗(yàn)結(jié)果表明,在得到多角度高清圖像時(shí),文中方法精度相比實(shí)驗(yàn)一的重構(gòu)結(jié)果有明顯提升．

圖8 多角度下標(biāo)準(zhǔn)圖Tsukuba的建模結(jié)果Fig.8 Modeling results of the standard chart Tsukuba under multiple angles

實(shí)驗(yàn)三，將文中方法和文獻(xiàn)[5]中GPU加速SIFT算法方法進(jìn)行對(duì)比實(shí)驗(yàn).圖9為對(duì)標(biāo)準(zhǔn)圖beaver的特征提取對(duì)比實(shí)驗(yàn).表1為對(duì)比實(shí)驗(yàn)結(jié)果.

表1 文中方法和文獻(xiàn)[5]中GPU加速SIFT算法性能對(duì)比Table 1 Comparison of GPU accelerated SIFT algorithm performance between the proposed method and the literature 5′s method

表2 標(biāo)準(zhǔn)圖Cones、Teddy、Tsukuba 及 Venus的CUDA加速匹配算法性能對(duì)比Table 2 Comparison of accelerated matching algorithm using standardFigure Cones, Teddy, Tsukuba and Venus

實(shí)驗(yàn)結(jié)果表明文中SIFT特征提取方法和文獻(xiàn)[16]中方法及文獻(xiàn)[5]中GPU加速方法三者檢測(cè)精度相當(dāng),但與文獻(xiàn)[5]中方法相比，實(shí)現(xiàn)了約1.7的加速比．此外并行化方法不僅提高視頻數(shù)據(jù)流的處理速度,像素越高的圖像加速效果越明顯,同時(shí)終端節(jié)點(diǎn)采用了多目視頻源的并行解碼策略,減少了數(shù)據(jù)傳輸量,從而降低網(wǎng)絡(luò)帶寬的需求,由此改善了高清圖像重構(gòu)的及時(shí)性．表2為文中方法和文獻(xiàn)[8]中方法對(duì)標(biāo)準(zhǔn)圖Cones、Teddy、Tsukuba及 Venus進(jìn)行特征匹配的對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)數(shù)據(jù)表明文中方法在CUDA架構(gòu)下提升約7.1的加速比．

圖9 實(shí)驗(yàn)結(jié)果對(duì)比Fig.9 Comparison of result

3 結(jié)論

文中提出一種異步執(zhí)行改進(jìn)三維重建的并行方法,該方法的并行化思想體現(xiàn)在兩個(gè)層面:宏觀層面是對(duì)服務(wù)端和終端相結(jié)合的任務(wù)級(jí)的并行化；微觀層面是基于CUDA平臺(tái)的編程體系結(jié)構(gòu),對(duì)各算法程序中能夠并發(fā)執(zhí)行的指令進(jìn)行線程級(jí)的并行化．相關(guān)對(duì)比實(shí)驗(yàn)驗(yàn)證了三維重構(gòu)各個(gè)子模塊的并行加速效率．由實(shí)驗(yàn)數(shù)據(jù)可以看出文中并行方法有效提高了重建加速比．但也存在許多不足之處,因?yàn)槲闹兄饕槍?duì)復(fù)雜環(huán)境中的實(shí)時(shí)繪制方法進(jìn)行改進(jìn),就實(shí)時(shí)三維點(diǎn)云的后期處理,并沒(méi)有作深入討論,所以文中方法僅適用于精度要求不是很高的快速建模場(chǎng)景．因此,以后將針對(duì)稠密點(diǎn)云的構(gòu)建方法作更深入研究．