張 燕，趙新燦，譚同德

（鄭州大學 信息工程學院，河南 鄭州450001）

0 引 言

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

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

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

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

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

2 視頻采集與幀圖像提取

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

圖2 兩段視頻流采集

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

3 基于GPU的SIFT特征提取

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

圖3 基于GPU的SIFT特征提取

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

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

圖4 RGBA紋理格式

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

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

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

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

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

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

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

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

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

3.2 局部極值點檢測和梯度計算

GPU的動態(tài)分支用于極值點檢測的全過程，判斷一個像素在DOG尺度空間是否是極值點分四步實現(xiàn)：

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

（2）將剩余的可能極值點與同尺度的8個相鄰像素進行比較。

（3）將剩余的約0.6%可能極值點與相鄰尺度的18個鄰近像素進行比較。

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

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

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

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

3.3 特征點方向及特征向量

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

圖6 特征點方向

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

圖7 SIFT特征向量生成

基于GPU的SIFT特征向量生成，這個操作不同于前面進行的操作，因為輸入一個元素 （特征點）卻輸出128個元素。即使使用多目標渲染，這個操作也不能一起執(zhí)行，因為不可能將一個直方圖分開計算。特征向量的生成全部在GPU上進行計算不能夠達到最好的效率，因此我們將特征向量的生成分割在GPU與CPU之間，重采樣特征點的梯度向量塊，在GPU端對其高斯加權(quán)，然后將加權(quán)后的梯度向量塊回讀到CPU端，在CPU端計算特征向量。

4 基于GPU的SIFT特征匹配

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

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

圖8 SIFT特征向量的匹配

5 基于GPU的視頻流拼接

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

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

5.2 算法性能及其分析

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

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

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

6 結(jié)束語

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

［1］WANG Xiaoqiang，CHEN Linqiang，LIANG Xu.Method of real time automatic video stitching［J］.Computer Engineering，2011，37 （5）：291－292 （in Chinese）. ［王小強，陳臨強，梁旭.實時全自動視頻拼接方法 ［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］.計算機工程與應(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)，王宗敏.基于特征點的視頻流拼接幀選擇優(yōu)化算法 ［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］.合肥：中國科學技術(shù)大學，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)鍵點的增強現(xiàn)實初始化算法［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）. ［袁修國，彭國華，王琳.基于GPU的變型SIFT算子實時圖像配準［J］.計算機科學，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）.［何揚，汪曉娥.一種改進的SIFT特征匹配算法及其實現(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ù)字圖像處理算法典型實例 ［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）.［汪道寅，胡訪宇.基于改進SIFT算法的視頻序列圖像配準 ［J］.無線電工程，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）.［錢悅.圖形處理器 CUDA 編程模型的應(yīng)用研究 ［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）.［田文，徐帆，王宏遠，等.基于CUDA的尺度不變特征變換快速算法 ［J］.計算機工程，2010，36 （8）：219－221.］