一種移動設備視頻全景并行生成技術

摘 要:通過移動攝像機合成視頻全景圖，由于視頻中存在時間冗余以及現有合成技術對大角度旋轉存在失配，提出一種魯棒性較好的視頻全景并行合成方法。該方法首先對選取的關鍵幀采用并行線程提取可重復性特征，并利用特征估計透視運動模型，從而對相鄰關鍵幀進行全局配準;然后對重疊區域進行雙線性融合，以減少視差對重疊場景的影響，同時并行優化提高了視頻全景的合成速度。不同條件下移動合成實驗表明，在大角度移動旋轉以及視差等情況下仍能較好地合成視圖。

關鍵詞:特征提取;視頻全景;全局配準;場景鑲嵌;并行優化

中圖分類號:TP301 文獻標志碼:A

文章編號:1001-3695(2010)03-1167-03

doi:10.3969/j.issn.1001-3695.2010.03.101

Parallel generation for video panorama in mobile environment

HAN Long， GUO Li

(Dept. of Electronic Science Technology， University of Science Technology of China， Hefei 230027， China)

Abstract:Video panorama was generated by moving camera. Because of the temporal redundancy in video and misregistration in the large angle rotation， many existing algorithms perform poorly. To solve these challenging situation，this paper proposed an parallel synthesis approach to generating panorama which used texture feature to select key-frames. This method first extracted repeatable features from the selected key-frames using parallel threads， and then estimated the perspective motion model to align the adjacent key-frames by features.Employed bilinear blending to reduce the parallax effect in the overlapped region. Meanwhile， parallel threads programming improved the synthesis of speed. The experimental results show that the proposed method can effectively synthesize panorama with misregistration and parallax.

Key words:feature extraction; video panorama; global registration; scene mosaic; parallel optimization

視頻全景合成技術一直是圖像處理、計算機視覺和計算機圖形學的活躍研究領域。在圖像和視頻處理中，它能夠提供比普通圖像更廣闊的視野。目前被廣泛應用在視頻會議、航空拍攝、軍事監測以及虛擬視點繪制技術等領域。從原理上可將其分為兩類:一類是直接利用特殊光學設備來采集全景圖像;另一類是由多個普通鏡頭采集多視點的圖像，然后通過算法合成全景。前者使用的設備比較昂貴，而后者必須使用多個普通鏡頭設備采集，它們之間的位置也有一定的約束。本文只采用一個普通鏡頭，通過移動采集視頻序列并自動合成全景視圖，因此具有較大的應用價值。

目前，全景合成技術日趨完善，對相鄰視圖間只有簡單平移的全景合成研究比較成熟。如在條帶全景圖[1]中，所有視頻序列是水平對齊的。由于視差的存在，許多算法會產生鬼影。國內外學者提出了一些消除鬼影的算法，如多視投影法[2]和平面掃描法[3]等，但這些方法運算量比較大，或者需要人工干預。本文提出一種魯棒性較好的自動并行合成視頻全景技術。該方法通過隨機移動攝像頭采集視頻序列，由于視頻序列間冗余的存在，本文采用特征紋理選取關鍵幀;然后利用并行線程調度，對關鍵幀提取可重復性特征，并對相鄰視點進行全局配準。由于采用了并行線程調度，合成全景圖的速度有明顯提高。

1 移動設備視頻全景生成算法

將移動攝像機采集的視頻序列作為輸入，采集時攝像機可隨意緩慢移動，沒有特殊的約束限制，而且也不需要知道攝像機的參數。移動設備視頻全景合成主要由視頻序列關鍵幀選取、提取關鍵幀的可重復性特征并配準、融合視頻序列關鍵幀組成。為了提高生成全景圖的魯棒性，本文利用SIFT算法來提取可重復性特征，同時采用并行線程調度來優化合成的速度。

1.1 視頻序列關鍵幀的選取

對于視頻序列，關鍵幀選取的方法包括特征跟蹤、位移矢量等。考慮到視頻序列之間紋理結構的相似性，本文提出一種基于紋理特征相似性度量來選取關鍵幀。灰度共生矩陣描述了紋理特征在空間上的位置分布特性，同時也反映了圖像亮度變化的統計特性。

通過實驗統計結果表明，對于紋理特征的多個統計量，筆者只采用二階矩、熵、對比度和局部平穩性這四個紋理特征來選取關鍵幀。由這四個統計量特征構造的紋理特征向量足以估計相鄰視頻幀間的冗余度，其特征紋理向量定義如下:

V=[f1 f2 f3 f4](1)

其中:f1=L-1i=0L-1j=0[Pδ(i， j)]2為二階矩，它反映了圖像灰度分布均勻性;f2=-

L-1i=0L-1j=0{Pδ(i， j)log[Pδ(i， j)]}為熵，用來描述圖像所具有的信息量，代表了整個圖像區域內灰度變化的復雜度;f3=L-1n=0n2{L-1i=0L-1j=0Pδ(i， j)}，|i-j|=n為對比度，可以理解為紋理的清晰程度;f4=L-1i=0L-1j=011+(i-j)2Pδ(i， j)為局部平穩性，該值描述了圖像的局部紋理特征的平穩程度，而Pδ(i， j)為灰度共生矩陣。對視頻序列計算紋理特征向量Vi(i=1，2，…，N)，N為視頻序列總數。通過比較視頻序列紋理特征向量的相似度來選取關鍵幀，其表達式如下:

d(i， j)=Ni=1，j=2|Vi-Vj|≥T(2)

其中:i， j(i≠j)為視頻序列號;T是相似性度量的閾值。當d(i， j)≥T時，選取當前幀為關鍵幀，重復上述過程直到處理完所有視頻序列，閾值的選取根據不同的場景而定。

1.2 關鍵幀的特征提取和配準

在移動攝像機拍攝中，當相鄰關鍵幀的特征點得到后，首先用平面透視運動模型[4]來估計關鍵幀間的幾何關系。該模型使用透視矩陣將關鍵幀視圖投影到同一平面上，則有

x′y′1=Hi， j×xy1=h0 h1 h2

h3 h4 h5

h6 h7 1×xy1(3)

其中:(x，y，1)T和(x′，y′，1)T分別為相鄰兩關鍵幀視圖的齊次坐標。為了估計矩陣Hi， j中的八個參數，需要四對匹配點，從相鄰視點的粗匹配后的特征點中隨機抽取四對特征點對{(x1，y1)，(x2，y2)，(x3，y3)，(x4，y4)}和{(x′1，y′1)，(x′2，y′2)，(x′3，y′3)，(x′4，y′4)}，如下式:



x1y11000-x′1x1-x′1y1

000x1y11-y′1x1-y′1y1

x2y21000-x′2x2-x′2y2

000x2y21-y′2x2-y′2y2

x3y31000-x′3x3-x′3y3

000x3y31-y′3x3-y′3y3

x4y41000-x′4x4-x′4y4

000x4y41-y′4x4-y′4y4×h0h1h2h3h4h5h6h7=x′1y′1

x′2

y′2

x′3

y′3

x′4

y′4(4)

由于攝像機鏡頭的畸變、視差和噪聲等因素的影響，本文采用SIFT算法[5，6]對關鍵幀提取特征點及初匹配。該算法得到的特征點具有尺度不變性，能夠適應存在視角變化較大和視差等視頻序列，有效地克服了輸入序列中的噪聲干擾。

首先對輸入視頻關鍵幀I(x，y)進行高斯濾波，則有

L(x，y，σ)=G(x，y，σ)×I(x，y)(5)

其中:G(x，y，σ)=(1/(2πσ2))e-(x2+y2)/(2σ2)。對不同尺度的高斯核差分構成高斯差分空間(difference-of-Gaussian， DoG)為

D(x，y，σ)=L(x，y，kσ)-L(x，y，σ)(6)

其次，將DoG空間中26個鄰域(上下尺度各9個鄰域，本尺度8個鄰域)的極值點作為候選點，并在候選點處泰勒展開，得到

D(v)=D+(DT/v)v+(1/2)vT(2D/v2)v(7)

其中:v=(x，y，σ)T。由上式解得關鍵點亞像素及亞尺度的精確坐標為=(2D-1/v2)×(DT/v)，并對該處的DoG函數D()進行閾值限定，以消除對比度較低的不穩健點。

再次，構造關鍵點周圍高斯差分圖像的Hessian矩陣MHes，并利用該矩陣的跡和行列式近似估計該處的曲率比，以消除過強的邊緣響應，其公式如下

MHes=Dxx DxyDxy Dyy，Tr(MHes)Det(MHes)<(1+r)2r

(8)

其中:Tr(MHes)和Det(MHes)分別為Hessian矩陣的跡和行列式;r為與矩陣特征值相關的閾值，本文取r為10。

為了使特征點具有旋轉不變性，對每個特征點再計算一定鄰域內所有像素的梯度，對梯度模賦予高斯權重并統計梯度方向直方圖，以決定該特征點的主方向。

最后，對以特征點為中心、主方向為法方向的16×16像素區域再進行高斯加權及分格梯度直方圖統計，形成128維的特征描述符。該特征描述符具有平移、旋轉、尺度不變性，通過比較兩兩之間的歐氏距離獲得初匹配的特征點對。

由于SIFT只是部分具有仿射不變性，故存在一些誤匹配。本文采用RANSAC算法[7]進一步剔除誤匹配點對，即隨機抽取四對匹配點計算一個初始矩陣，再用該矩陣去度量其余特征點的匹配程度，則有

x′ny′n1-Hi， j×xnyn1<θ(9)

其中:θ是區分內點和外點的容限。本文設置θ=0.8。通過迭代得到滿足最大匹配點集的矩陣Hi， j，該最大匹配點集為排除誤匹配后的特征點集。

為了滿足所有關鍵幀的配準精度，這里利用全局配準來實現。設定N為視頻序列的總數，n是選取的關鍵幀數目，則有H1，i=H1，2×H2，3×…×Hi-1，i。其中:i是關鍵幀的標號，且i≤n。這樣，就可以得到一組透視變換矩陣，如下式:

H1，2=H1，2

H1，3=H1，2×H2，3

…

H1，n=H1，2×H2，3×…×Hn-1，n(10)

由于SIFT提取的特征點魯棒性好，則透視變換矩陣組可以實現全局配準。

1.3 關鍵幀間的融合

考慮到視差的影響，同時為了滿足實時處理的要求，本文采用迭代雙線性加權融合算法[8]對關鍵幀進行融合，具體實現過程如下:

a)將關鍵幀1置于預先定義好的一個背景圖中，如圖1所示，構造一個大小為M×M的背景圖。

b)將關鍵幀i(初始值i=2)通過轉換矩陣H1，i變換到背景圖中，同時求出關鍵幀i的四個頂點在背景圖中的新坐標。其中:1，2，3，…，n是關鍵幀的標號，且i≤n。

c)關鍵幀1和關鍵幀i的非重疊區域的像素值不變，直接添加到背景圖中，重疊區域對R、G、B三個分量分別根據加權法來求得新像素的值，其表達式如下:

Inew=αα+βI1+βα+βIi(11)

其中:Inew是融合后的新像素值;α，β分別表示重疊區域中的點到關鍵幀1的左邊界的距離和關鍵幀i的右邊界距離。

d)求包圍盒的大小，即包圍盒在背景圖中的四個頂點坐標，圖1中黑色虛線所示。判斷i≤n是否成立，如果成立，i=i+1，轉到步驟b)繼續執行;否則，結束融合循環。

2 視頻全景并行合成的實現

為了提高視頻序列全景圖像合成的速度，可考慮并行線程調度來優化。目前，多核CPU已經開始在市場上出現，并成為今后市場的主流，因此充分利用并行線程編程變得尤為重要。

2.1 并行實現的原理

在移動設備環境下，對視頻全景合成任務分解成若干個小的任務，再將這些任務分配到不同的線程上，以獲得多線程并行處理，如圖2所示。

其中:T1，T2，…，Tn是關鍵幀特征提取的任務;T1，2，T2，3，…，Tn-1，n是相鄰關鍵幀特征點配準的任務;Td是所有關鍵幀融合的任務。圖2中，任務T1，T2，…，Tn并行執行，任務T1，2，T2，3，…，Tn-1，n也并行執行，但需要等待T1，T2，…，Tn執行完后;最后執行任務Td，這些小任務之間可以完全獨立運行，并且存在相互依賴關系。其中各個任務也可以進行數據分解來優化。

2.2 并行實現算法

本文所使用的硬件平臺是Intel的雙核CPU的PC機，軟件平臺是Intel開發的并行計算集成工具包，并在Visual Studio 2005環境下對OpenMP多線程編程[9，10]進行配置。

在視頻序列全景視圖合成過程中，由于SIFT特征點提取復雜度比較高，對SIFT算法進一步多線程調度實現。整個視頻全景視圖并行合成的偽代碼如下:

//視頻序列中的第一幀為基準幀

并行多線程實現對基準幀的SIFT特征提取;

for all frames // 對所有移動拍攝的視頻幀

{//并行實現紋理特征選取關鍵幀;

if(是否為關鍵幀)

{#pragma omp critical

記錄關鍵幀的標號;

}

并行多線程實現對關鍵幀的SIFT特征提取;

#pragma omp parallel for

for all pixels // 相鄰兩關鍵幀中特征點像素

{//利用并行線程調度實現

完成關鍵幀間的配準;

視頻關鍵幀之間的融合;

}

}

SIFT算法并行實現的偽代碼如下:

//并行多線程實現對關鍵幀的SIFT特征提取

for all octaves //假設有n個尺度組

{建立n個棧用于存放尺度組中的特征;

for all scales //一個尺度組中有m個尺度空間

{構建DoG空間;

#pragma omp parallel for//并行檢測特征點

for all pixels //對尺度組中的像素

{if (是否為關鍵點)

#pragma omp critical

添加新增的關鍵特征點入棧;

}

}

降采樣尺度組(Octave);

}

#pragma omp parallel for

for all pixels //像素指關鍵點棧中的像素

{//提取特征信息，即128維特征向量

定位特征點方向;

生成特征點描述符;

}

對于并行實現來說，主要解決的是線程調度問題。在出現數據競爭時，利用線程同步機制控制線程的執行順序，從而保證執行結果的確定性。在利用OpenMP實現中，一般利用critical、lock和barrier實現線程同步。在本文SIFT并行優化算法中，所有線程把生成的特征點壓入共享棧時必然會產生競爭。這里，本文利用臨界區(critical)對產生數據競爭的內存進行保護，以保證壓入共享棧中的特征點的正確性，同時消除了訪問共享內存的錯誤率。另外，對于定位特征點方向和生成特征點描述符、實現相鄰幀像素配準和融合等操作，由于是采用循環結構，為此利用parallel循環優化來完成。在整個程序實現過程中，對矩陣的操作和對圖像的降采樣都進行并行任務分配優化。

下面對并行多線程調度的時間復雜度進行分析。如當用多線程調度完成SIFT特征點提取入棧時，提取的特征點個數為N，則串行計算時間復雜度為O(N)，并行時間復雜度為O(log N)，加速比S=O(N/log N)。

3 實驗結果

為了更好地說明并行線程調度優化的效果，以只有兩幅關鍵幀來舉例說明，其中關鍵幀尺寸為240×320。整個視頻全景合成算法偽代碼的實驗結果如表1所示。其中:t表示一個單位時間。從表中可以看出，并行后的可重復的SIFT特征提取所消耗的時間明顯減少。通過統計運行的結果，優化后的總時間比優化前近乎均減少了50%左右，其加速比平均都可到達2倍以上。

圖3(a)是對室外場景移動攝像機合成的全景圖，拍攝中攝像機按一定角度旋轉并移動，獲取22幀視頻序列。利用本文提出的方法，通過紋理特征相似度量選取關鍵幀。設定一個閾值T，其取值根據不同的場景而定，這里取T=0.2。以第一幀為基準幀，然后計算后續幀與基準幀的紋理特征相似性系數，關鍵幀的數目為6，如表2所示。

表1 優化前后的對比

關鍵幀尺寸優化前用時(t)優化后用時(t)第一幀SIFT135.7

第二幀SIFT135.7

特征點匹配1.81

變換矩陣0.20.1

關鍵幀融合10.5

總時間2913

表2 關鍵幀間的相似性系數

相鄰關鍵幀相似性系數

第1與8幀0.276 219

第8與13幀0.271 007

第13與15幀0.214 597

第15與18幀0.277 904

第18與22幀0.246 947

圖3(b)是對室內環境進行拍攝合成的結果。本文所采用的方法能夠自動完成關鍵幀的特征點提取和配準之間并行線程調度，從而快速得到視頻序列全景圖像;同時，利用了關鍵幀之間的全局配準，合成的準確度較高。

下面對本文提出的方法和其他方法進行了對比。高空移動攝像機拍攝15幀連續視頻序列，實驗結果如圖4所示。

圖4(a)是本文的算法，關鍵幀數目為4;(b)是用基于區域特征的方法[11]進行了實驗，關鍵幀數目為7。基于區域特征拼接的方法魯棒性較差，在融合時容易產生明顯的分界線;本文所采用的方法幾乎看不出有分界線，而且對視頻序列的旋轉具有較強的適應性，同時用較少的關鍵幀就可以得到全景圖像，合成速度較快。

4 結束語

對于移動攝像機捕獲的視頻，本文提出了一種魯棒性較好的視頻全景圖并行合成技術。由于視頻序列之間存在冗余，首先采用紋理特征相似度來選取關鍵幀，利用并行線程調度提取可重復性特征;然后通過匹配特征估計平面透視運動模型，對輸入的關鍵幀進行配準。整個合成全景圖是通過并行線程調度來完成的。實驗結果證明，當相鄰關鍵幀存在一定視差時仍能較好地合成視圖。對優化前后進行了對比，并行優化消耗時間大約減少了50%左右，加速比均達到2倍以上。同時，與其他方法進行了比較，本文的方法魯棒性好，全景合成結果幾乎可以實現無縫合成，計算復雜度也有所降低。

參考文獻:

[1]

ZHENG Jiang-yu.Digital route panoramas[J].IEEE Multi-media，2003，10(3):57-67.

[2]ZELNIK-MANOR L，PETERS G，PERONA P.Squaring the circle in panoramas[C]//Proc of the 10th IEEE International Conference on Computer Vision. Pasadena， CA: IEEE Press，2005:1291-1299.

[3]KANG S B，SZELISKI R，UYTTENDAELE M.Seamless stitching using multi-perspective plane sweep，MSR-TR-2004-48[R].[S.l.]:Microsoft，2004.

[4]SZELISKI R.Video mosaics for virtual environments[J].Computer Graphics and Applications，1996，16(2):22-30.

[5]LOWE D.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60(2):90-110.

[6]WINDER S A，BROWN M. Learning local image descriptor[C]//Proc of the IEEE Conference on Computer Vision and Pattern Recognition.[S.l.]:INSPEC，2007:1-8.

[7]FORSYTH D A，PONCE J.計算機視覺:一種現代方法[M]. 林學閻，王宏，譯.北京:電子工業出版社，2004.

[8]CHEN Hui，ZHAO Bin，LIU Yue.A video mosaic algorithm for compressed video[C]//Proc of the 2nd Workshop on DMAMH.Washington DC:IEEE Computer Society，2007:370-377.

[9]AKHTER S，ROBERTS J.多核程序設計技術[M].北京:電子工業出版社，2007:140-160.

[10]ZHANG Qi，CHEN Yu-rong，ZHANG Yi-min.SIFT implementation and optimization for multi-core systems[C]//Proc of the 36th International Conference on Parallel Processing.Xi’an:[s.n.]，2007:1139-1146.

[11]冷曉艷，薛模根，韓裕生，等.基于區域特征與灰度交叉相關的序列圖像拼接[J].紅外與激光工程，2005，34(5):602-605.