基于GPU的視頻流拼接算法研究

張 燕，趙新?tīng)N，譚同德

（鄭州大學(xué) 信息工程學(xué)院，河南 鄭州450001）

0 引 言

由于單個(gè)攝像機(jī)表達(dá)的場(chǎng)景區(qū)域信息有限，而高清攝像機(jī)因價(jià)格昂貴又得不到普及，使得視頻流拼接具有重要的實(shí)用價(jià)值。視頻流拼接就是利用視頻流拼接技術(shù)將幾段有公共視野的視頻流拼接為一整段視野范圍更廣的全景視頻流。視頻流拼接因其觀賞直觀性已經(jīng)應(yīng)用于視頻點(diǎn)播、視頻會(huì)議和三維視頻等多個(gè)領(lǐng)域［1］。當(dāng)前已出現(xiàn)多種視頻流拼接方法，David Lowe于1999年提出并于2004年進(jìn)行更深入發(fā)展和完善的局部特征描述子SIFT因其對(duì)平移、旋轉(zhuǎn)、光照、尺度等具有較好的魯棒性而得到廣泛應(yīng)用［2］，該算法能實(shí)現(xiàn)較好的拼接效果，缺點(diǎn)是算法復(fù)雜、計(jì)算量龐大，計(jì)算的復(fù)雜度過(guò)高就難以滿足實(shí)時(shí)性需求，從而限制了其廣泛應(yīng)用。

近幾年來(lái)，處理器領(lǐng)域最重要的變化之一就是圖形處理器GPU的運(yùn)算性能的倍速增長(zhǎng)，其浮點(diǎn)運(yùn)算能力已經(jīng)大大超越了通用處理器。使用GPU對(duì)傳統(tǒng)的通用計(jì)算和圖像處理算法進(jìn)行并行加速成為近年來(lái)兩個(gè)新的熱點(diǎn)研究領(lǐng)域。基于GPU的視頻流拼接算法將視頻流拼接的關(guān)鍵技術(shù) （圖像特征提取與特征匹配）在GPU上進(jìn)行加速，大大提高了算法的執(zhí)行速度，滿足了系統(tǒng)實(shí)時(shí)性的要求。本文還通過(guò)實(shí)驗(yàn)對(duì)傳統(tǒng)的基于CPU實(shí)現(xiàn)的視頻流拼接算法和基于GPU實(shí)現(xiàn)的視頻流拼接算法［3］進(jìn)行了分析和對(duì)比。

1 基于GPU的視頻流拼接總體設(shè)計(jì)

視頻流的拼接總體上分為視頻采集、幀圖像提取、幀圖像拼接3個(gè)過(guò)程，其中幀圖像拼接又分為幀圖像特征提取和特征匹配兩個(gè)子過(guò)程。幀圖像拼接是影響視頻流拼接實(shí)時(shí)性的關(guān)鍵步驟，而幀圖像特征提取和特征匹配又是影響幀圖像拼接速度的關(guān)鍵步驟，所以在GPU上實(shí)現(xiàn)視頻流拼接算法，需將算法的不同計(jì)算步驟映射到不同的片段程序上，對(duì)于每一步計(jì)算，適當(dāng)?shù)钠纬绦驎?huì)與片段處理器綁定，然后調(diào)用相應(yīng)的渲染操作達(dá)到加速的目的。然而全部算法在GPU上執(zhí)行并不能達(dá)到最好的效率，因?yàn)镃PU與GPU的結(jié)構(gòu)不同，CPU的設(shè)計(jì)是使更多的晶體管用于數(shù)據(jù)緩存和流控制，所以CPU擅長(zhǎng)的像操作系統(tǒng)、系統(tǒng)軟件和通用應(yīng)用程序這類(lèi)擁有復(fù)雜調(diào)度指令、分支、循環(huán)、邏輯判斷及執(zhí)行的程序任務(wù)；而GPU大量的晶體管用于數(shù)據(jù)處理，所以GPU擅長(zhǎng)處理圖形類(lèi)矩陣運(yùn)算或是非圖形類(lèi)的高度并行數(shù)值計(jì)算。集成CPU和GPU的體系結(jié)構(gòu)不僅使它們可以繼續(xù)在各自擅長(zhǎng)的領(lǐng)域發(fā)揮作用和減小在傳輸帶寬上的花銷(xiāo)，還可以使運(yùn)行任務(wù)之間的分割、調(diào)配以及硬件資源的利用更加合理。例如讓CPU更多的資源用于緩存或控制，GPU更多的資源則用于處理通用計(jì)算。經(jīng)分析，基于GPU實(shí)現(xiàn)視頻流拼接總體設(shè)計(jì)圖如圖1所示。

圖1 基于GPU的視頻流拼接總體設(shè)計(jì)

2 視頻采集與幀圖像提取

視頻采集是視頻流拼接的第一步，也是非常重要的一步，是利用DV （digital video camera，數(shù)碼錄像機(jī)）采集幾段具有公共視野的視頻流。具體采集過(guò)程如下［4］：將DV固定在操作臺(tái)上，調(diào)整位置及方向使它們有部分公共視野，然后勻速推動(dòng)操作臺(tái)，這樣就可以采集到具有相鄰場(chǎng)景的視頻流 （圖2為采集兩段視頻流）。

圖2 兩段視頻流采集

采集到視頻后，我們通過(guò)程序?qū)崿F(xiàn)幀圖像的提?。?］，即每隔一段時(shí)間或每隔幾幀提取一幀作為關(guān)鍵幀，這樣就可以得到一系列的幀圖像序列。

3 基于GPU的SIFT特征提取

GPU在處理算法密集、計(jì)算高度并行、控制簡(jiǎn)單和算法分多個(gè)階段等這類(lèi)需要時(shí)性能遠(yuǎn)超過(guò)CPU，所以為了在GPU上加速SIFT算法執(zhí)行，需根據(jù)GPU的特點(diǎn)優(yōu)化修改標(biāo)準(zhǔn)的David Lowe的SIFT算法的各個(gè)步驟使其順利進(jìn)入GPU的圖形管道，進(jìn)而充分發(fā)揮GPU的并行處理能力［5］。因此，研究的重點(diǎn)是如何重新構(gòu)造SIFT算法的各個(gè)階段使其適應(yīng)GPU的紋理格式。基于GPU的SIFT算法將算法中的多個(gè)步驟用GPU并行來(lái)計(jì)算，算法流程圖如圖3所示。

圖3 基于GPU的SIFT特征提取

3.1 紋理存儲(chǔ)設(shè)計(jì)和尺度空間生成

RGBA紋理格式是GPU的物理存儲(chǔ)結(jié)構(gòu)，它包含R、G、B、A這4個(gè)顏色通道分量 （如圖4所示），其中每個(gè)通道占一個(gè)數(shù)據(jù)存儲(chǔ)空間。在使用RGBA紋理存儲(chǔ)時(shí)，每個(gè)紋理可以保存4個(gè)數(shù)值，這樣GPU既可以通過(guò)GPU上片段處理器的數(shù)量實(shí)現(xiàn)紋理間并行處理，還可以將紋理中的4個(gè)顏色通道分量作為一個(gè)向量進(jìn)行并行處理。在基于GPU的SIFT特征提取中，我們將特征提取模塊的數(shù)據(jù)存儲(chǔ)設(shè)計(jì)為RGBA紋理格式，即將幀圖像的灰度值、DOG值、梯度幅值和方向依次存入R通道、G通道、B通道和A通道中。

圖4 RGBA紋理格式

構(gòu)建尺度空間分兩個(gè)階段：

第一階段：構(gòu)建高斯尺度空間

（1）高斯濾波：同組中每一層圖像是下一層圖像的模糊結(jié)果。

（2）圖像亞采樣：將上一組中某一層的圖像進(jìn)行亞采樣作為下一組圖像的第一層。

其中高斯濾波是高斯尺度空間構(gòu)建中最耗時(shí)的運(yùn)算步驟，根據(jù)高斯卷積的可分離性，我們將高斯濾波也分為兩個(gè)階段，用水平方向和垂直方向的一維濾波來(lái)代替二維的高斯濾波。

對(duì)于圖像I（x，y）與gx，y（t）進(jìn)行卷積操作，得到下一層圖像L （x，y），其中g(shù)x，y（t）代表先進(jìn)行水平方向?yàn)V波，后進(jìn)行垂直方向的濾波。

經(jīng)過(guò)兩次濾波處理后，得到下一層的高斯灰度圖，將灰度值存入紋理單元R通道，采用這種方式，節(jié)省了大量的紋理存取時(shí)間。

第二階段：構(gòu)建DOG尺度空間

將高斯尺度空間中相鄰尺度的高斯灰度圖相減即可得到DOG尺度空間，將得到的DOG值放入紋理單元的G通道。

3.2 局部極值點(diǎn)檢測(cè)和梯度計(jì)算

GPU的動(dòng)態(tài)分支用于極值點(diǎn)檢測(cè)的全過(guò)程，判斷一個(gè)像素在DOG尺度空間是否是極值點(diǎn)分四步實(shí)現(xiàn)：

（1）根據(jù)像素點(diǎn)的亮度差閾值排除約50%的非極值點(diǎn)。

（2）將剩余的可能極值點(diǎn)與同尺度的8個(gè)相鄰像素進(jìn)行比較。

（3）將剩余的約0.6%可能極值點(diǎn)與相鄰尺度的18個(gè)鄰近像素進(jìn)行比較。

（4）去除邊緣和噪聲影響。

利用動(dòng)態(tài)分支節(jié)省了不必要的計(jì)算，提高了GPU的效能。另外將圖像灰度、梯度和DOG值保存在RGBA紋理中，極值點(diǎn)檢測(cè)就是在向量?jī)?nèi)部進(jìn)行比較計(jì)算，而向量?jī)?nèi)部運(yùn)算是相對(duì)省時(shí)的。獲取的穩(wěn)定的特征點(diǎn)如圖5所示，紅點(diǎn)代表特征點(diǎn)。檢測(cè)特征點(diǎn)的同時(shí)還可以進(jìn)行梯度幅值和方向計(jì)算，首先取出紋理R通道中存放的圖像灰度值，然后計(jì)算梯度，最后將計(jì)算得到的梯度幅值與方向分別存入紋理單元B通道和A通道。

圖5 穩(wěn)定的特征點(diǎn)

由于CPU與GPU之間進(jìn)行數(shù)據(jù)通信開(kāi)銷(xiāo)很大，因此，特征點(diǎn)列表的生成也同樣在GPU上進(jìn)行，生成的特征點(diǎn)列表存儲(chǔ)在紋理中。在這里我們利用GPU的數(shù)據(jù)流縮減方法生成特征點(diǎn)列表。

3.3 特征點(diǎn)方向及特征向量

得到特征點(diǎn)以后，我們要為每個(gè)特征點(diǎn)指定一個(gè)主方向，使其具備旋轉(zhuǎn)不變性?；贕PU的特征點(diǎn)方向計(jì)算與傳統(tǒng)的SIFT算法類(lèi)似，仍然采用梯度方向直方圖統(tǒng)計(jì)法來(lái)確定特征點(diǎn)的方向，即統(tǒng)計(jì)以特征點(diǎn)為原點(diǎn)一定區(qū)域內(nèi)的鄰域圖像像素的梯度方向分布特征，并用方向直方圖表示，檢測(cè)方向直方圖的最高峰值點(diǎn)作為該特征點(diǎn)的主方向。在這里我們?cè)贕PU端生成方向直方圖來(lái)統(tǒng)計(jì)特征點(diǎn)鄰域像素的梯度方向，然后將方向直方圖回讀到CPU端，在CPU端檢測(cè)方向直方圖的最高峰值來(lái)確定特征點(diǎn)的方向 （如圖6所示）。每個(gè)特征點(diǎn)將得到一個(gè)或一個(gè)以上的方向，從而得到帶有特征點(diǎn)坐標(biāo)和方向的特征點(diǎn)列表。

圖6 特征點(diǎn)方向

特征點(diǎn)計(jì)算完成后，我們需要一組具有獨(dú)特性、唯一性的向量來(lái)描述這個(gè)特征點(diǎn)，該向量將作為目標(biāo)匹配的依據(jù)。特征向量的計(jì)算與計(jì)算特征點(diǎn)方向相似，都是統(tǒng)計(jì)特征點(diǎn)一定區(qū)域內(nèi)對(duì)其有貢獻(xiàn)的像素點(diǎn)，只不過(guò)這些像素點(diǎn)指定的方向是一致的。通過(guò)對(duì)特征點(diǎn)一定領(lǐng)域區(qū)域進(jìn)行分塊，如圖7所示，鄰域區(qū)域被均勻的分成了16塊，每塊大小為4像素×4像素，然后計(jì)算每個(gè)塊的方向直方圖，，每個(gè)塊與8個(gè)方向相關(guān)聯(lián)，加起來(lái)是一個(gè)128維的輸出向量，如圖7所示。

圖7 SIFT特征向量生成

基于GPU的SIFT特征向量生成，這個(gè)操作不同于前面進(jìn)行的操作，因?yàn)檩斎胍粋€(gè)元素 （特征點(diǎn)）卻輸出128個(gè)元素。即使使用多目標(biāo)渲染，這個(gè)操作也不能一起執(zhí)行，因?yàn)椴豢赡軐⒁粋€(gè)直方圖分開(kāi)計(jì)算。特征向量的生成全部在GPU上進(jìn)行計(jì)算不能夠達(dá)到最好的效率，因此我們將特征向量的生成分割在GPU與CPU之間，重采樣特征點(diǎn)的梯度向量塊，在GPU端對(duì)其高斯加權(quán)，然后將加權(quán)后的梯度向量塊回讀到CPU端，在CPU端計(jì)算特征向量。

4 基于GPU的SIFT特征匹配

特征匹配是利用相關(guān)函數(shù) （一般是各種距離函數(shù)）來(lái)評(píng)價(jià)兩幅圖像特征點(diǎn)鄰域的相似性以確定對(duì)應(yīng)點(diǎn)，而特征向量表示的就是特征點(diǎn)的鄰域信息，所以比較特征向量的相似性即可得到潛在的匹配點(diǎn)。在實(shí)際應(yīng)用中，我們用歐式距離作為特征向量的相似性度量，對(duì)于兩幅幀圖像，分別計(jì)算特征點(diǎn)及特征向量，利用K－D樹(shù)進(jìn)行優(yōu)先搜索，找到每個(gè)特征點(diǎn)的兩個(gè)最鄰近特征點(diǎn)，計(jì)算該特征點(diǎn)到兩個(gè)鄰近特征點(diǎn)的歐式距離，如果最近的距離與次近的距離的比值小于我們?cè)O(shè)定的比例閾值，則接受這對(duì)匹配的特征點(diǎn)，其中D為長(zhǎng)度為N的特征向量V1與V2的歐式距離。

基于GPU的SIFT特征匹配中，K－D樹(shù)搜索和相應(yīng)的特征向量相減都可以在GPU上并行執(zhí)行。這樣可以大大提高計(jì)算速度。最后用經(jīng)典的去外點(diǎn)算法隨機(jī)抽樣算法去除錯(cuò)誤匹配，得到穩(wěn)定的正確的特征點(diǎn)匹配對(duì) （如圖8所示）。

圖8 SIFT特征向量的匹配

5 基于GPU的視頻流拼接

5.1 全景圖拼接的實(shí)現(xiàn)

圖像拼接是將一組重疊圖像進(jìn)行拼接構(gòu)建一幅無(wú)縫的、高清晰的、視野開(kāi)闊的全景圖。圖像配準(zhǔn)是圖像拼接中的關(guān)鍵技術(shù)，視頻流的拼接效果也取決于每幀幀圖像的快速配準(zhǔn)，而圖像配準(zhǔn)的關(guān)鍵和核心又是幀圖像的快速特征提取和匹配。傳統(tǒng)基于CPU的視頻流拼接過(guò)程中幀圖像配準(zhǔn)階段花費(fèi)的時(shí)間較長(zhǎng)，顯然不能達(dá)到實(shí)時(shí)穩(wěn)定拼接的效果，而基于GPU的視頻流拼接則很好的解決了這個(gè)問(wèn)題，實(shí)現(xiàn)了視頻流的快速穩(wěn)定拼接。拼接效果如下：圖9為4幅原始幀圖像，圖10為圖像拼接的全景圖。

5.2 算法性能及其分析

本文的實(shí)驗(yàn)平臺(tái)為64位Windows XP操作系統(tǒng)，NVIDIA GeForce 6600GT著色器，編譯器平臺(tái)為Microsoft VS2005。實(shí)驗(yàn)中將視頻流拼接算法中的圖像配準(zhǔn)SIFT算法的參數(shù)設(shè)置為：第一組圖像大小均為512＊384，組數(shù)為6，每組層數(shù)為3；第二組中圖像大小均為1024＊972，組數(shù)為6，每組層數(shù)為3。標(biāo)準(zhǔn)的視頻流拼接算法與基于GPU的視頻流拼接算法的運(yùn)算時(shí)間及性能分析，對(duì)比數(shù)據(jù)如表1所示。

表1 兩種方法數(shù)據(jù)對(duì)比

由表1數(shù)據(jù)可知，對(duì)同一幅圖像，GPU實(shí)現(xiàn)在特征提取和特征匹配兩個(gè)階段的處理速度上得到大幅度提升，當(dāng)圖像越大越復(fù)雜時(shí)獲得的這種加速比就越大，這使得視頻流拼接過(guò)程中幀圖像的處理速度得到加速，每秒處理的幀圖像數(shù)大幅增加，從而使得視頻流拼接的實(shí)時(shí)性得以提升。

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

本文利用圖形處理器GPU實(shí)現(xiàn)了標(biāo)準(zhǔn)的視頻流拼接算法，提高了系統(tǒng)的實(shí)時(shí)性并拓寬了算法的應(yīng)用范圍。算法利用CPU和GPU混合模式共同實(shí)現(xiàn)，怎樣達(dá)到一種最優(yōu)的計(jì)算分配方式是下一步研究方向。下一步主要嘗試?yán)肗VIDIA的統(tǒng)一設(shè)備架構(gòu) （compute unified device architecture，CUDA）來(lái)快速實(shí)現(xiàn)視頻流拼接算法，因?yàn)镃UDA提供了更直觀的編程模型和優(yōu)化原則，基于CUDA的算法實(shí)現(xiàn)充分運(yùn)用了GPU的并行計(jì)算能力，可以使視頻流拼接算法在實(shí)時(shí)性方面有更大的提升。

［1］WANG Xiaoqiang，CHEN Linqiang，LIANG Xu.Method of real time automatic video stitching［J］.Computer Engineering，2011，37 （5）：291－292 （in Chinese）. ［王小強(qiáng)，陳臨強(qiáng)，梁旭.實(shí)時(shí)全自動(dòng)視頻拼接方法 ［J］.計(jì)算機(jī)工程，2011，37（5）：291－292.］

［2］ZHANG Chaowei，ZHOU Yan，WANG Yaokang，et al.Method of videos stitch with SIFT feature tracking and matching based ［J］.Computer Engineering and Applications，2008，44（10）：169－172 （in Chinese）.［張朝偉，周焰，王耀康，等.基于SIFT特征跟蹤匹配的視頻拼接方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44 （10）：169－172.］

［3］WANG Rui，LIANG Hua，CAI Xuanping.Study of SIFT feature extraction algorithm based on GPU ［J］. Modern Electronic Technology，2010，33 （15）：41－43 （in Chinese）. ［王瑞，梁華，蔡宣平.基于GPU的SIFT特征提取算法研究 ［J］.現(xiàn)代電子技術(shù)，2010，33 （15）：41－43.］

［4］WANG Tiejian，ZHAO Hongling，WANG Zongmin.Optimized frame selection algorithm for video stitching based on feature points ［J］.Computer Applications，2009，29 （3）：2112－2115（in Chinese）.［王鐵建，趙紅領(lǐng)，王宗敏.基于特征點(diǎn)的視頻流拼接幀選擇優(yōu)化算法 ［J］.計(jì)算機(jī)應(yīng)用，2009，29 （3）：2112－2115.］

［5］WU Changchang. SIFTGPU ［CP／OL］. ［2007－02－11］.http：／／www.cs.unc.edu／～ccwu／siftgpu／.

［6］Sinha S，F(xiàn)rahm J.GPU－based video feature tracking and matching ［C］.Workshop on EDGE，2006.

［7］Heymann S.SIFT implementation and optimization for generalpurpose GPU ［C］.Proceedings of the 15th WSCG，2007.

［8］Cornelis N，Van Gool L.Fast scale invariant feature detection and matching on programmable graphics hardware ［C］.Workshop on CVPR，2008.

［9］Bay H，Tuytelaars T，Van Gool L.SURF：Speeded up robust features ［C］.European Conference on Computer Vision pages，2006：404－417.

［10］Sinha S，F(xiàn)rahm J.Feature tracking and matching in video using programmable graphics hardware［J］.Machine Vision and Applications，2011，22（1）：207－217.

［11］ZHENG Mai，GUO Li.Research of multi－view panoramic video technology based on webcams［D］.Anhui：University of Science and Technology of China，2009：54－65 （in Chinese）.［鄭邁，郭立.基于網(wǎng)絡(luò)攝像頭的多視全景視頻技術(shù)研究 ［D］.合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2009：54－65.］

［12］CHEN Jing，WANG Yongtian，LIU Yue，et al.System initialization algorithm based on SIFT key points for markerless augmented reality applications ［J］.Infrared and Laser Engineering，2007，36 （6）：949－953 （in Chinese）. ［陳靖，王涌天，劉越，等.基于SIFT關(guān)鍵點(diǎn)的增強(qiáng)現(xiàn)實(shí)初始化算法［J］.紅外與激光工程，2007，36 （6）：949－953.］

［13］YUAN Xiuguo，PENG Guohua，WANG Lin.GPU－based real time image registration with variant SIFT ［J］.Computer Science，2011，38 （3）：300－303 （in Chinese）. ［袁修國(guó)，彭國(guó)華，王琳.基于GPU的變型SIFT算子實(shí)時(shí)圖像配準(zhǔn)［J］.計(jì)算機(jī)科學(xué)，2011，38 （3）：300－303.］

［14］HE Yang，WANG Xiaoe.An improved SIFT feature matching algorithm and its realization ［J］.Silicon Valley，2011，10 （6）：92－93（in Chinese）.［何揚(yáng)，汪曉娥.一種改進(jìn)的SIFT特征匹配算法及其實(shí)現(xiàn) ［J］.硅谷，2011，10 （6）：92－93.］

［15］ZHAO Chunjiang.Typical examples of digital image processing algorithms with C＃ ［M］.Beijing：Posts ＆ Telecom Press，2009：21－248 （in Chinese）.［趙春江.C＃數(shù)字圖像處理算法典型實(shí)例 ［M］.北京：人民郵電出版社，2009：21－248.］

［16］WANG Daoyin，HU Fangyu，Video sequence image registration based on improved scale－invariant feature transform algorithm［J］.Radio Engineering of China，2011，41 （2）：16－18（in Chinese）.［汪道寅，胡訪宇.基于改進(jìn)SIFT算法的視頻序列圖像配準(zhǔn) ［J］.無(wú)線電工程，2011，41 （2）：16－18.］

［17］QIAN Yue.Compute unified device architecture on graphics processors［J］.Computer ＆ Digital Engineering，2008，36（12）：177－180 （in Chinese）.［錢(qián)悅.圖形處理器 CUDA 編程模型的應(yīng)用研究 ［J］.計(jì)算機(jī)與數(shù)字工程，2008，36（12）：177－180.］

［18］TIAN Wen，XU Fan，WANG Hongyuan，et al.Fast scale invariant feature transform algorithm based on CUDA.Computer Engineering，2010，36 （8）：219－221 （in Chinese）.［田文，徐帆，王宏遠(yuǎn)，等.基于CUDA的尺度不變特征變換快速算法 ［J］.計(jì)算機(jī)工程，2010，36 （8）：219－221.］