帶顯著性區(qū)域約束的高效視頻全景拼接方法

范菁，吳佳敏，葉陽(yáng)，吳冬艷，王浩

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

摘要：傳統(tǒng)的基于流形的全景拼接技術(shù)在處理包含局部運(yùn)動(dòng)的視頻時(shí)，存在不能保留特定關(guān)鍵區(qū)域的內(nèi)容、表達(dá)視頻運(yùn)動(dòng)信息的能力較差以及實(shí)現(xiàn)速度較慢的問(wèn)題.針對(duì)上述問(wèn)題，提出了一種帶顯著性區(qū)域約束的高效視頻全景拼接方法，該方法在基于流形的視頻拼接的基礎(chǔ)上考慮圖像的特征點(diǎn)，通過(guò)設(shè)定顯著性區(qū)域，生成關(guān)鍵幀帶約束的全景圖；然后對(duì)關(guān)鍵幀全景圖進(jìn)行對(duì)齊及融合，構(gòu)建運(yùn)動(dòng)全景圖；并采用基于CUDA的并行計(jì)算方法進(jìn)行算法加速.實(shí)驗(yàn)結(jié)果表明：該方法不僅可以在全景圖中保留特定對(duì)象某一時(shí)刻的具體形態(tài)，而且可以保留運(yùn)動(dòng)對(duì)象多個(gè)運(yùn)動(dòng)形態(tài)，并且有較快的拼接速度.

關(guān)鍵詞：視頻拼接；流形；特征點(diǎn)；全景圖；對(duì)象約束；CUDA技術(shù)

收稿日期：2015-04-15

基金項(xiàng)目：浙江省重大科技專項(xiàng)項(xiàng)目(2013C01112,2012C01SA160034)；杭州市重大科技創(chuàng)新專項(xiàng)(20132011A16)

作者簡(jiǎn)介：范菁(1969—)，女，浙江杭州人，教授，博士生導(dǎo)師，研究方向?yàn)樘摂M現(xiàn)實(shí)與軟件中間件等，E-mail:fanjing@zjut.edu.cn.

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1006-4303(2015)05-0479-08

Abstract:The traditional panorama stitching technique based on manifold can’t retain the contents of particular key areas in videos. The ability to express the motion information of video is poor and the speed is slow. In order to solve these problems, an efficient panoramic stitching method with significant region constraint is presented. Based on the manifold video stitching and the image feature points, this method will set significant area to generate the panorama with constraint for key frames firstly. Then the panoramas in the key frames are aligned and fused to obtain the motion panorama. The CUDA parallel computing is used to speed up. The experimental results showed that the proposed method can not only retain the specific form of specific object at a certain moment, but also can keep multiple movement patterns of moving objects in the panorama. It can effectively improve the speed of image stitching.

Keywords:video stitching; manifold; feature points; panorama; object constraint; CUDA

An efficient panoramic stitching method with significant region constraint

FAN Jing, WU Jiamin, YE Yang, WU Dongyan, WANG Hao

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

視頻作為影視娛樂(lè)、信息傳播或場(chǎng)景監(jiān)控的載體，已在日常生活和工業(yè)應(yīng)用中發(fā)揮重要的作用.隨著視頻資源數(shù)量的增加和計(jì)算機(jī)技術(shù)的發(fā)展，人們對(duì)視頻分析及處理的要求越來(lái)越高[1].視頻全景拼接技術(shù)通過(guò)對(duì)持續(xù)時(shí)間較長(zhǎng)的視頻提供簡(jiǎn)短的概括性摘要，幫助用戶快速了解視頻的大致內(nèi)容，提高了分析和處理視頻信息的效率.但是在處理包含運(yùn)動(dòng)對(duì)象的視頻時(shí),由于運(yùn)動(dòng)對(duì)象在視頻中的每個(gè)時(shí)刻位置和形態(tài)都不同，簡(jiǎn)單的全景拼接技術(shù)只是將一段視頻拼接成一幅涵蓋場(chǎng)景全貌的高分辨率圖像，無(wú)法保證運(yùn)動(dòng)對(duì)象的完整性，更無(wú)法滿足在全景圖構(gòu)造時(shí)保留特定對(duì)象某一時(shí)刻形態(tài)的需求.

目前視頻領(lǐng)域比較經(jīng)典并被廣泛使用的方法是基于流形思想的拼接方法[2]，該方法通過(guò)在時(shí)空立體空間下的流形投影，以像素列為基本單位進(jìn)行拼接操作；但是此算法要求視頻幀之間存在對(duì)齊關(guān)系，只適用于內(nèi)容為靜態(tài)場(chǎng)景的視頻對(duì)象.為了適應(yīng)運(yùn)動(dòng)視頻的特性，Zomet等[3-4]針對(duì)基礎(chǔ)算法要借助攝像機(jī)位置的改變來(lái)合成全景圖像的缺點(diǎn)，提出一種適用于多種攝像機(jī)運(yùn)動(dòng)的通用方法，但是影響了算法速度.Rav-acha等[5]針對(duì)隨機(jī)運(yùn)動(dòng)的視頻引入時(shí)空空間概念，但是無(wú)法處理具有結(jié)構(gòu)性運(yùn)動(dòng)的視頻.Wexler等[6]則提出了一種較為完整的基于時(shí)空?qǐng)鼍暗牧餍衅唇铀惴?，不需要?duì)像素列作對(duì)齊操作，也允許視頻場(chǎng)景中包含局部運(yùn)動(dòng)，但是其合成的全景圖并不包含視頻詳細(xì)內(nèi)容，而且處理速度也由于應(yīng)用Dijkstra算法而減慢.張樹(shù)江等[7]改進(jìn)了像素列間距離的定義，提出了一種改進(jìn)的基于流形的全景圖繪制方法，可以構(gòu)建更完整詳細(xì)的全景圖，但同時(shí)也增加了計(jì)算復(fù)雜度.Hu等[8]針對(duì)實(shí)時(shí)交通監(jiān)控視頻，采用基于流形的圖形拼接的算法并改進(jìn)像素列之間的距離計(jì)算，但是算法的適用場(chǎng)景較局限.郭李云等[9]則在場(chǎng)景流形的拼接算法中對(duì)長(zhǎng)視頻采用分段處理的方式，雖然該方法能較快得到質(zhì)量較高的全景圖，但沒(méi)有考慮運(yùn)動(dòng)視頻全景圖的特殊需求.綜上所述，基于流形思想的視頻拼接技術(shù)已經(jīng)有了較深入的研究，但是運(yùn)動(dòng)視頻全景圖的構(gòu)建效果及算法處理速度還有待提高.因此，針對(duì)以上問(wèn)題，筆者提出了一種帶顯著性區(qū)域約束的高效視頻全景拼接方法，該方法在基于流形的視頻拼接的基礎(chǔ)上進(jìn)行視頻顯著性區(qū)域的劃分，形成對(duì)象約束的全景圖，然后通過(guò)對(duì)關(guān)鍵幀的全景圖進(jìn)行圖像融合，形成運(yùn)動(dòng)全景圖，最終實(shí)現(xiàn)了多運(yùn)動(dòng)形態(tài)顯示和特定對(duì)象特定時(shí)刻的具體形態(tài)展現(xiàn).同時(shí)，該方法采用CUDA并行計(jì)算，顯著提升了拼接速度.

1帶顯著性區(qū)域約束的全景拼接技術(shù)

視頻是圖像序列的集合，參照基于時(shí)空?qǐng)鼍暗牧餍衅唇铀惴╗6]，我們將一段視頻的圖像序列投射于三維坐標(biāo)系中，形成一個(gè)時(shí)空立體空間(圖1).此空間中，X軸為圖像的寬度，Y軸為圖像的高度，T軸是視頻圖像的時(shí)間方向，因此單張視頻圖像即可視為一個(gè)二維平面(X—Y)，全部圖像可以對(duì)齊到時(shí)間T軸.

圖1　視頻立體空間 Fig.1　Video stereo space

若要從視頻圖像序列中抽象出一幅場(chǎng)景過(guò)渡自然、無(wú)拼接痕跡的新圖像，就需要從大量的像素列集合中挑選出適合的拼接像素，而如何挑選像素就是一個(gè)尋找貫穿整個(gè)立體空間最佳流形切面(Y—T平面)的問(wèn)題，在時(shí)間軸上獲得的該二維剖面的投影就是視頻的全景圖像，即圖1中邊緣線所標(biāo)出的二維剖面.因此，需要確定流形切面的最優(yōu)性以及尋找這個(gè)最佳剖面.

1.1功能函數(shù)

(1)

(2)

式(2)可簡(jiǎn)化為

(3)

所以，最優(yōu)路徑中各像素列之間的總和可以定義為

(4)

1.2構(gòu)圖過(guò)程

圖2　相鄰結(jié)點(diǎn)的取值范圍 Fig.2　Value range for nearby node

(5)

(B-B′)2)

(6)

求解最短路徑采用的是Dijkstra算法.經(jīng)典的Dijkstra算法主要用來(lái)求解單源、無(wú)負(fù)權(quán)的最短路徑，其時(shí)間復(fù)雜度為O(V×V+E)，V為結(jié)點(diǎn)數(shù)，E為邊數(shù).假定源節(jié)點(diǎn)為s，不包括源結(jié)點(diǎn)的結(jié)點(diǎn)集合為V.搜索算法的基本思想是：先設(shè)定源節(jié)點(diǎn)到V中所有結(jié)點(diǎn)的長(zhǎng)度為無(wú)窮大，即Initial過(guò)程；然后每次從集合V中取出當(dāng)前情況下到源節(jié)點(diǎn)s的最短結(jié)點(diǎn)u，即ExtractMin過(guò)程；最后對(duì)u的相關(guān)邊進(jìn)行松弛更新，即Relax過(guò)程[10].

1.3對(duì)象約束的全景拼接

對(duì)于不存在局部運(yùn)動(dòng)的視頻，每一幀圖像中顯著對(duì)象本身不會(huì)發(fā)生變化，因此利用功能函數(shù)及構(gòu)圖過(guò)程的思路尋找到時(shí)空立體空間的下一條最優(yōu)路徑就可以實(shí)現(xiàn)簡(jiǎn)單的全景圖拼接；但是，若視頻存在局部運(yùn)動(dòng)的對(duì)象，根據(jù)以上方法則無(wú)法在全景圖中包含運(yùn)動(dòng)對(duì)象的某一刻形態(tài).針對(duì)以上問(wèn)題，考慮存在局部運(yùn)動(dòng)的視頻全景拼接，提出一種對(duì)象約束的全景拼接思想.

由于存在局部運(yùn)動(dòng)的對(duì)象是肉眼馬上能感知到的，所以我們對(duì)視頻幀的重要度定義可以增加一個(gè)顯著性判定標(biāo)準(zhǔn)：是否存在運(yùn)動(dòng)的對(duì)象，包含運(yùn)動(dòng)對(duì)象的區(qū)域可以定義為視頻幀的顯著性區(qū)域.然后，用戶指定全景圖中包含哪一幀的顯著性區(qū)域，通過(guò)這種對(duì)象約束生成帶約束的全景圖.

在獲取顯著性區(qū)域的過(guò)程中，首先采用光流法[8]來(lái)提取視頻中的運(yùn)動(dòng)對(duì)象.光流法能實(shí)現(xiàn)復(fù)雜運(yùn)動(dòng)目標(biāo)的檢測(cè)和跟蹤，而且克服光亮度變化的影響[11].在得到每幀圖像的光流場(chǎng)信息后，把該運(yùn)動(dòng)信息按式(7)轉(zhuǎn)換成光流信息可視化圖.

(7)

其中：vx為x方向的速度；vy為y方向的速度.

對(duì)光流信息可視化圖進(jìn)行二值化和形態(tài)學(xué)操作，找出圖中灰度值出現(xiàn)0值的最左邊的像素和最右邊的像素，并對(duì)其x軸上的位置進(jìn)行記錄：左邊位置記為左邊界left_x，右邊位置設(shè)為右邊界right_x.最后，將left_x～right_x區(qū)域范圍內(nèi)的圖像置為顯著性區(qū)域；圖3中框標(biāo)記為視頻圖像的顯著性區(qū)域.

圖3　視頻圖像顯著性區(qū)域 Fig.3　The significant area of a video image

從左邊界left到右邊界right的區(qū)域中的每一列像素可作為帶約束的最短路徑中的必經(jīng)結(jié)點(diǎn).該區(qū)域中的所有必經(jīng)結(jié)點(diǎn)構(gòu)成一段必經(jīng)路徑.從源節(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最終路徑中，需要包含這一段路徑.那么最終的最短路徑可以分成3部分：1) 從源結(jié)點(diǎn)到left的最短路徑；2) 必經(jīng)路徑；3) 從right到目標(biāo)結(jié)點(diǎn)的最短路徑.這三部分最短路徑組成的路徑，即為符合實(shí)際情況的最短路徑，公式可定義為

Pmin=P(s,l)+P(l,r)+P(r,f)

(8)

其中：P表示路徑；Pmin為最終的最短路徑；s為源節(jié)點(diǎn)；l為左邊界；r為右邊界；f為目標(biāo)結(jié)點(diǎn).

根據(jù)以上思路分別對(duì)兩段運(yùn)動(dòng)視頻mashu.avi和jieli.avi進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖4，5所示.圖4(a)和圖5(a)分別為兩段視頻中的部分原始幀；圖4(b)和圖5(b)為不帶約束的視頻全景圖拼接圖；圖4(c)為保留圖4(a)中mashu.avi視頻序列第4張圖片中馬的動(dòng)作生成的帶約束的全景拼接圖；圖5(c)為保留jieli.avi視頻序列的第1張圖片中運(yùn)動(dòng)員的動(dòng)作生成的帶約束的全景拼接圖.

圖4　mashu.avi視頻的拼接結(jié)果 Fig.4　Video panorama stitching results of mashu.avi

圖5　jieli.avi視頻的拼接結(jié)果 Fig.5　Video panorama stitching results of jieli.avi

基于以上思路，我們也可以對(duì)其他幀的顯著性區(qū)域進(jìn)行檢測(cè)并標(biāo)記，然后在全景圖中保留該部分顯著性區(qū)域.實(shí)驗(yàn)結(jié)果表明：采用該算法能夠獲得單獨(dú)的不同姿勢(shì)的全景圖.但該算法有一個(gè)不足之處，就是在全景圖中不能詳細(xì)顯示運(yùn)動(dòng)對(duì)象的運(yùn)動(dòng)狀態(tài)，即同時(shí)保留多個(gè)姿勢(shì)實(shí)現(xiàn)包含多對(duì)象的全景圖，這就是我們下面要研究的問(wèn)題.

1.4多形態(tài)運(yùn)動(dòng)對(duì)象的全景圖生成方法

為了使全景圖能夠完全顯示運(yùn)動(dòng)對(duì)象在視頻中的概況，可以采用一種基于流形的視頻拼接和基于特征點(diǎn)圖像拼接相結(jié)合的方法來(lái)構(gòu)造最終的運(yùn)動(dòng)全景圖，最終在全景圖中保留運(yùn)動(dòng)對(duì)象不同時(shí)刻的多個(gè)形態(tài).該方法的主要思想是：先根據(jù)光流法提取視頻中的若干關(guān)鍵幀，然后以關(guān)鍵幀圖像中的顯著性區(qū)域作為約束對(duì)象分別實(shí)現(xiàn)基于內(nèi)容的全景拼接圖像，再結(jié)合圖像分割算法將各張全景拼接圖融合到一起，最終實(shí)現(xiàn)包含多運(yùn)動(dòng)對(duì)象的全景拼接圖.運(yùn)動(dòng)全景圖的拼接主要有兩個(gè)步驟：1) 關(guān)鍵幀的提取與圖像序列對(duì)齊；2) 運(yùn)動(dòng)全景圖的融合.

1.4.1關(guān)鍵幀的提取與圖像序列對(duì)齊

由于處理的對(duì)象是攝像機(jī)平面運(yùn)動(dòng)狀態(tài)下拍攝的存在局部運(yùn)動(dòng)的視頻，方法的目的是要捕捉對(duì)象的全局性運(yùn)動(dòng)，所以可以利用基于運(yùn)動(dòng)分析的方法[12]提取關(guān)鍵幀.首先，快速提取光流信息[8]；然后利用光流信息分析計(jì)算運(yùn)動(dòng)量，選取運(yùn)動(dòng)量達(dá)到局部最小值的點(diǎn)作為關(guān)鍵幀.各關(guān)鍵幀中的運(yùn)動(dòng)對(duì)象構(gòu)成的運(yùn)動(dòng)軌跡大致涵蓋了視頻中的主要運(yùn)動(dòng)信息，本方法把關(guān)鍵幀中的運(yùn)動(dòng)對(duì)象定義為顯著運(yùn)動(dòng)對(duì)象，擬對(duì)視頻的顯著運(yùn)動(dòng)對(duì)象進(jìn)行檢測(cè)與提取，然后把這些對(duì)象作為約束條件分別進(jìn)行全景圖拼接.

在確定參考幀后，需要對(duì)圖像序列作對(duì)齊操作.本方法實(shí)現(xiàn)時(shí)選擇無(wú)約束條件的拼接圖作為參考幀，然后對(duì)其他帶約束條件的全景圖作對(duì)齊變換，把它們?nèi)繉?duì)齊到參考幀坐標(biāo)系中.待變換的圖像需要與參考幀圖像找到對(duì)應(yīng)關(guān)系，才能進(jìn)行對(duì)齊變換.兩者之間的對(duì)應(yīng)關(guān)系可以用單應(yīng)矩陣來(lái)表示.求解單應(yīng)矩陣的過(guò)程如下：1) 檢測(cè)圖像的局部特征；2) 為每個(gè)特征提取特征描述符；3) 根據(jù)特征描述符進(jìn)行特征點(diǎn)匹配；4) 利用RANSAC方法求出單應(yīng)矩陣.

接下來(lái)，對(duì)每幀圖像進(jìn)行Harris特征提取，把待對(duì)齊的圖像與參考幀圖像的特征點(diǎn)進(jìn)行匹配，建立對(duì)應(yīng)關(guān)系，可用公式表示為

ui=Hijuj

(9)

其中：Hij記為單應(yīng)矩陣；ui和uj分別為特征點(diǎn)在圖像中的具體位置(x,y坐標(biāo)).

最后，根據(jù)單應(yīng)矩陣對(duì)圖像進(jìn)行仿射變換，把其他帶約束條件的全景圖像對(duì)齊到參考幀坐標(biāo)系中.

1.4.2運(yùn)動(dòng)全景圖的融合

在根據(jù)Harris角點(diǎn)特征匹配的基礎(chǔ)上對(duì)齊各張全景圖像后，可直接進(jìn)行運(yùn)動(dòng)全景圖的融合，得到包含多個(gè)運(yùn)動(dòng)信息的全景圖.但是，直接融合的圖像中運(yùn)動(dòng)對(duì)象明暗不一，部分圖像細(xì)節(jié)丟失，顯著對(duì)象信息不突出[13].所以，為了解決上述問(wèn)題，我們采用圖像摳像技術(shù)預(yù)先對(duì)帶約束的全景圖像實(shí)現(xiàn)前景運(yùn)動(dòng)對(duì)象的提取，得到相應(yīng)的前景控制圖(mask圖)，再進(jìn)一步實(shí)現(xiàn)圖像融合.

首先，對(duì)帶約束的全景圖像作處理以實(shí)現(xiàn)全景圖像的前/背景分割[14].該方法利用簡(jiǎn)單的人機(jī)交互，用戶只需在前景對(duì)象以及背景對(duì)象上各取幾個(gè)點(diǎn)作為樣本輸入，就可以實(shí)現(xiàn)理想的前/背景分割.此外，引入非局部區(qū)域的k近鄰區(qū)域來(lái)代替原有的局部線性窗口區(qū)域，不需要建立局部的線性色彩模型，也不要進(jìn)行復(fù)雜的抽樣策略，大大提高了算法的實(shí)現(xiàn)效率.與此同時(shí)，該方法對(duì)于前景對(duì)象的細(xì)節(jié)處理也非常到位，能夠提取出較為細(xì)致的前景對(duì)象.

然后，結(jié)合預(yù)生成的mask圖，利用加權(quán)平均算法來(lái)實(shí)現(xiàn)圖像融合.不同全景圖運(yùn)動(dòng)對(duì)象有可能出現(xiàn)重疊的現(xiàn)象，其權(quán)重的大小根據(jù)時(shí)間的先后原則來(lái)確定.假定無(wú)約束條件的全景圖像的像素值記為pm(i,j)，其他各張帶約束條件的全景圖像的像素值記為pi(i,j).兩張圖像的融合方法為

(10)

其中pn(i,j)為新生成的圖像.如果時(shí)間上較早發(fā)生的運(yùn)動(dòng)形態(tài)，設(shè)置較大的權(quán)重值，然后根據(jù)時(shí)間順序依次遞減.本方法在實(shí)現(xiàn)時(shí)，設(shè)置α1=0.9，α2=0.8.

根據(jù)以上算法分別對(duì)mashu.avi和jieli.avi視頻進(jìn)行了運(yùn)動(dòng)全景圖合成，結(jié)果如圖6所示.在全景圖中，我們采用連續(xù)的透明度表示運(yùn)動(dòng)的發(fā)生時(shí)間，透明度越大則表示發(fā)生時(shí)間越早，通過(guò)該形式就可以間接表現(xiàn)出對(duì)象的運(yùn)動(dòng)軌跡.

圖6　運(yùn)動(dòng)全景圖效果 Fig.6　Motion panorama stitching image

通過(guò)實(shí)驗(yàn)效果分析發(fā)現(xiàn)：該方法在一定程度上達(dá)到了用戶想要在全景圖中看到運(yùn)動(dòng)對(duì)象的運(yùn)動(dòng)信息的期望，但是，其實(shí)現(xiàn)速度還是相對(duì)較慢.因此，可以基于CUDA并行計(jì)算方法實(shí)現(xiàn)算法加速優(yōu)化.

2基于CUDA的全景拼接圖的加速與優(yōu)化

視頻全景拼接過(guò)程中，視頻幀的分辨率以及幀數(shù)的多少是影響拼接速度的主要因素.基于流形的拼接算法主要包括鄰接矩陣的構(gòu)建和尋找最短路徑，因此CUDA上的加速與優(yōu)化也從這兩部分展開(kāi).

2.1鄰接矩陣的構(gòu)建

鄰接矩陣的構(gòu)建主要包含鄰接結(jié)點(diǎn)的確定和權(quán)重的設(shè)定，相鄰兩個(gè)結(jié)點(diǎn)所在像素列之間的顏色差值決定了連接邊的權(quán)重值D(V,V′).鄰接矩陣的賦值需要遍歷每個(gè)結(jié)點(diǎn)，然后計(jì)算每個(gè)結(jié)點(diǎn)與其鄰接結(jié)點(diǎn)之間的權(quán)重值.結(jié)點(diǎn)數(shù)目越多，計(jì)算越慢.但該計(jì)算過(guò)程的邏輯是很簡(jiǎn)單的，而且每相鄰兩個(gè)結(jié)點(diǎn)之間的計(jì)算與其他結(jié)點(diǎn)之間也相互獨(dú)立.因此，該過(guò)程可以通過(guò)GPU的多線程來(lái)對(duì)其優(yōu)化.

假定視頻大小為640×480×50，結(jié)點(diǎn)個(gè)數(shù)即為640×50.視頻的鄰接點(diǎn)在幀間的轉(zhuǎn)變范圍和像素列在相鄰幀上的x范圍分別為xrange=[1，2，…，10],trange=[0,1]，那么圖像的鄰接結(jié)點(diǎn)可取當(dāng)前幀的下一像素列，以及下一幀圖像對(duì)應(yīng)位置的像素列到下10個(gè)像素列.為方便計(jì)算，把每個(gè)像素點(diǎn)定義成一個(gè)結(jié)構(gòu)struct mpixel {intr; intg; intb;}，該結(jié)構(gòu)中包含了像素點(diǎn)的rgb信息.

然后，開(kāi)辟顯存空間來(lái)存放計(jì)算結(jié)果.數(shù)組result用來(lái)存放每個(gè)線程的計(jì)算結(jié)果，定義其大小為640×480×50×11.用數(shù)組dis來(lái)存放每個(gè)結(jié)點(diǎn)與其11個(gè)鄰接結(jié)點(diǎn)之間的距離，定義其大小為640×50×11.視頻信息所需存儲(chǔ)超過(guò)顯存連續(xù)可開(kāi)辟的最大空間時(shí)，可采用分塊傳輸與計(jì)算.

大小為640×480×50的視頻，可有640×50個(gè)結(jié)點(diǎn)并行計(jì)算權(quán)重.開(kāi)辟640×50個(gè)block，每個(gè)block的工作是計(jì)算當(dāng)前結(jié)點(diǎn)的鄰接信息.再給每個(gè)block開(kāi)辟480個(gè)線程，每個(gè)線程對(duì)應(yīng)一個(gè)像素點(diǎn).獨(dú)立計(jì)算當(dāng)前像素與其他11個(gè)相鄰像素之間的顏色距離，該計(jì)算過(guò)程見(jiàn)圖7.

圖7　CUDA的并行結(jié)構(gòu) Fig.7　Parallel structure of CUDA

根據(jù)內(nèi)建函數(shù)變量blockIdx.x，blockIdx.y獲取block在網(wǎng)格grid中的索引號(hào)bid_in_grid，變量threadIdx.x獲取線程thread在網(wǎng)格中的索引號(hào)tid_in_grid.計(jì)算完每個(gè)結(jié)點(diǎn)的鄰接信息之后，需要對(duì)block中的所有線程進(jìn)行累加獲取一整個(gè)像素列的顏色距離.可用公式表示為

(11)

每個(gè)線程都有11個(gè)鄰接信息，每個(gè)鄰接信息都要進(jìn)行累加計(jì)算，該累加過(guò)程可讓11個(gè)線程并行計(jì)算，每個(gè)線程進(jìn)行累加計(jì)算時(shí)，可通過(guò)歸約算法進(jìn)一步提高計(jì)算效率.

2.2最短路徑搜索算法的并行計(jì)算

影響拼接速度的另外一大關(guān)鍵就是最短路徑的查找，Dijkstra算法的主要步驟Initial，ExtractMin和Relax都可以通過(guò)CUDA來(lái)加速實(shí)現(xiàn)，其具體的算法步驟如下：

在ExtractMin部分，可利用Reduction來(lái)加速，其算法復(fù)雜度為O(logn).在CUDAC平臺(tái)中有一個(gè)模板庫(kù)Trust，它封裝實(shí)現(xiàn)了并行計(jì)算的函數(shù)接口，Reduction就是其中的并行計(jì)算方法.Reduction算法利用二分法來(lái)將一組數(shù)據(jù)轉(zhuǎn)換成某個(gè)要求的數(shù)值，比如，可以利用該算法實(shí)現(xiàn)最小值的查找.

Relax部分的主要工作是判斷是否需要更新最小值.若是d[u]+c(u,v)

若每個(gè)結(jié)點(diǎn)的鄰接結(jié)點(diǎn)個(gè)數(shù)很少，該并行算法將不能體現(xiàn)并行的優(yōu)勢(shì)，反而會(huì)因線程的頻繁調(diào)度反而會(huì)影響程序執(zhí)行的效率.最短路徑搜索的并行計(jì)算采用Δ-Stepping算法[15]實(shí)現(xiàn)，該算法是Dijkstra的最優(yōu)改進(jìn)算法.Δ-Stepping算法是一種基于桶并行Dijkstra算法，它用多個(gè)桶Buckets來(lái)保存結(jié)點(diǎn)，每個(gè)桶中保存的結(jié)點(diǎn)個(gè)數(shù)與Δ的大小密切相關(guān).在桶B[i]中保存的結(jié)點(diǎn)為{v∈V且tent(v)∈[i×Δ,(i+1)×Δ}，V表示結(jié)點(diǎn)集合，tent(v)表示從源結(jié)點(diǎn)到結(jié)點(diǎn)v的累積權(quán)重值.其中Δ的取值有三種選擇：權(quán)重中值、權(quán)重平均值、最大權(quán)重值除以節(jié)點(diǎn)出度最大值的商，這里采用第三種方法.

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

筆者在CPU為Intel(R)Core(TM)2DuoCPUE8300@2.83GHz2.83GHz、內(nèi)存為2 048MB(DDR2SDRAM)、顯卡為NVIDIAGeforceGTX580且安裝MicrosoftWindows7操作系統(tǒng)的機(jī)器上實(shí)現(xiàn)了算法代碼.此外，為了比較不同算法在處理效率上的差異，除了在VS2008平臺(tái)上結(jié)合OPENCV開(kāi)發(fā)庫(kù)和CUDA開(kāi)發(fā)庫(kù)，實(shí)現(xiàn)了基于CUDA的并行優(yōu)化方法，還在MATLAB平臺(tái)上實(shí)現(xiàn)了基于流形的視頻拼接方法和基于高斯金字塔結(jié)構(gòu)的視頻拼接串行優(yōu)化方法.

對(duì)兩段視頻friend.avi和hanbing.avi分別采用CUDA加速下的帶顯著性區(qū)域約束的視頻圖像拼接方法、基于高斯金字塔結(jié)構(gòu)的串行優(yōu)化拼接方法和直接拼接方法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖8，9所示.三種方法都可以通過(guò)保留某一幀圖像中的顯著性區(qū)域或者固定區(qū)域，生成帶約束的全景圖；但是，對(duì)于包含局部運(yùn)動(dòng)的視頻，帶顯著性區(qū)域約束的視頻圖像拼接方法還可以生成運(yùn)動(dòng)全景圖，在全景圖中以時(shí)間順序突顯出對(duì)象的運(yùn)動(dòng)軌跡，如圖8(c)和圖9(c)所示.三種方法進(jìn)行帶約束的視頻拼接時(shí)，在不同幀數(shù)情況下實(shí)現(xiàn)的時(shí)間如表1所示.

圖8　friend.avi視頻全景圖拼接結(jié)果 Fig.8　Panorama stitching reults of friend.avi

實(shí)驗(yàn)結(jié)果表明：三種方法均可以生成帶約束的視頻全景拼接圖，該全景圖可以保留指定時(shí)刻的運(yùn)動(dòng)對(duì)象形態(tài)，在實(shí)際應(yīng)用過(guò)程中，能夠滿足用戶需求；而筆者提出的方法還可以生成運(yùn)動(dòng)全景圖，該全景圖保留了多個(gè)時(shí)刻的運(yùn)動(dòng)對(duì)象形態(tài)，有助于用戶通過(guò)全景圖獲取視頻中運(yùn)動(dòng)對(duì)象的形態(tài)變化情況，對(duì)于了解視頻詳細(xì)內(nèi)容有更大的幫助.因此，提出的方法更適合實(shí)際應(yīng)用.

圖9　hanbing.avi視頻全景圖拼接結(jié)果 Fig.9　Panorama stitching results of hanbing.avi

視頻名稱視頻大小帶顯著性區(qū)域約束的視頻圖像拼接/s定義鄰接矩陣搜索最短路徑總時(shí)間基于高斯金字塔結(jié)構(gòu)的串行優(yōu)化拼接/s第4層第3層第2層第1層總時(shí)間直接拼接總時(shí)間/sfriend.avi720×480×50720×480×100720×480×150720×480×2001.8563.7445.6007.6347.70318.15527.68736.8919.55921.89933.28744.52522342347812182227659314739821181802865828901165hanbing.avi640×360×50640×360×100640×360×150640×360×2001.2942.5893.8695.1466.22012.49119.07424.8937.51415.08022.94330.0391112123479101341556374506777932615367941055

雖然三種方法都可生成帶約束的全景圖，但是其拼接速度有很大的差異.基于高斯金字塔結(jié)構(gòu)的串行優(yōu)化拼接方法比直接拼接的方法在實(shí)現(xiàn)速度上有很大提高；而采用CUDA并行加速的帶顯著性區(qū)域約束的視頻圖像拼接方法在處理時(shí)間上明顯快于其余兩種方法；因此，我們提出的帶顯著性區(qū)域約束的視頻圖像拼接方法在采用CUDA并行計(jì)算方法后，有明顯的加速效果，可以應(yīng)用于分辨率更高、時(shí)間更長(zhǎng)的視頻，進(jìn)一步擴(kuò)展了方法的適用性.

4結(jié)論

筆者從視頻內(nèi)容出發(fā)，提出了一種帶顯著性區(qū)域約束的高效視頻圖像拼接方法.采用基于時(shí)空空間的流形拼接算法，把視頻拼接問(wèn)題劃歸為圖論問(wèn)題，滿足了用戶希望保留某一幀圖像中的顯著性區(qū)域或者固定區(qū)域的需求.同時(shí)對(duì)于包含局部運(yùn)動(dòng)的視頻，先通過(guò)基于光流場(chǎng)的方法實(shí)現(xiàn)關(guān)鍵幀的提取，然后對(duì)關(guān)鍵幀中的顯著對(duì)象進(jìn)行提取并作為約束對(duì)象分別實(shí)現(xiàn)帶約束的全景拼接圖.最后，提出了基于CUDA并行的優(yōu)化方法，改善了在處理時(shí)間較長(zhǎng)、分辨率較高的視頻時(shí)拼接速度較慢的問(wèn)題.實(shí)驗(yàn)結(jié)果表明基于顯著性約束的視頻圖像拼接方法生成的運(yùn)動(dòng)視頻全景圖像拼接結(jié)果能夠滿足實(shí)際應(yīng)用需求，產(chǎn)生的多運(yùn)動(dòng)形態(tài)全景圖能夠幫助用戶更好地理解運(yùn)動(dòng)視頻全貌，而CUDA加速方法的應(yīng)用進(jìn)一步提高了拼接速度，使圖像拼接技術(shù)可以適用于更高清、時(shí)間更長(zhǎng)的視頻.

參考文獻(xiàn)：

[1]鄭莉莉,黃鮮萍,梁榮華.基于支持向量機(jī)的人體姿態(tài)識(shí)別[J].浙江工業(yè)大學(xué)學(xué)報(bào),2012,40(6):670-675.

[2]PELEG S, HERMAN J. Panoramic mosaics by manifold projection[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Juan: IEEE,1997:338-343.

[3]ZOMET A, PELEG S. Efficient super-resolution and applications to mosaics[C]//International Conference on Pattern Recognition. Barcelona: IEEE,2000:579-583.

[4]PELEG S, ROUSSO B, RAV-ACHA A, et al. Mosaicing on adaptive manifolds[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(10):1144-1154.

[5]RAV-ACHA A, SHOR Y, PELEG S. Mosaicing with parallax using time warping[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. New York: IEEE,2004:164-164.

[6]WEXLER Y, SIMAKOV D. Space-time scene manifolds[C]//10th IEEE International Conference on Computer Vision (ICCV 2005). Beijing: IEEE,2005:858-863.

[7]張樹(shù)江,邢慧,顏景龍，等.一種改進(jìn)型視頻全景圖流形繪制方法[J].光子學(xué)報(bào),2007,36(s1):299-302.

[8]HU F, LI T, GENG Z. Constraints-based graph embedding optimal surveillance-video mosaicing[C]//Asian Conference on Pattern Recognition. Beijing: IEEE,2011:311-315.

[9]郭李云,歐陽(yáng)寧,莫建文.長(zhǎng)視頻序列拼接[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(14):183-185+195.

[10]張美玉,簡(jiǎn)睜峰,侯向輝，等.Dijkstra算法在多約束農(nóng)產(chǎn)品配送最優(yōu)路徑中的研究應(yīng)用[J].浙江工業(yè)大學(xué)學(xué)報(bào),2012,40(3):321-325.

[11]彭宏,韓露莎,王輝，等.基于小波變換與多幀平均法融合的背景提取[J].浙江工業(yè)大學(xué)學(xué)報(bào),2013,41(2):228-231.

[12]LIU C. Beyond pixels: exploring new representations and applications for motion analysis[D]. Boston: Massachusetts Institute of Technology,2009.

[13]TANG C K, LI D, CHEN Q. KNN matting[C]//IEEE Conference on Computer Vision and Pattern Recognition. Providence: IEEE,2012:869-876.

[14]WOLF W. Key frame selection by motion analysis[C]//IEEE International Conference on Acoustics, Speech and Signal Processing. Atlanta: IEEE,1996:1228-1231.

[15]MEYER U, SANDERS P. Δ-stepping: a parallelizable shortest path algorithm[J]. Journal of Algorithms,2003,49(1):114-152.

(責(zé)任編輯：劉巖)