一種視頻序列拼接的新方法*

謝紹霞 ，郭三華 ，初 玲 ，曹立娟 ，王萬君

(1.煙臺汽車工程職業學院 汽車工程系，山東 煙臺 265500；2.煙臺汽車工程職業學院 電子工程系，山東 煙臺 265500；3.煙臺汽車工程職業學院 科研處，山東 煙臺 265500)

圖像拼接是構建高分辨率大場景的關鍵技術，在虛擬現實場景表達、計算機視覺、全景圖繪制中有著重要應用，也是計算機圖形學領域中研究熱點[1]。視頻序列拼接是由多幀視頻序列拼接而成的完整全景圖像，在視頻監控、醫學圖像處理、遙感圖像處理等方面得到廣泛應用[2]。

在視頻序列的拼接中，相鄰幀間重疊部分較大，若每相鄰幀都做一次拼接，不僅耗費大量時間，而且隨著所需拼接幀數量增多，匹配誤差會增大，造成拼接效果不佳。利用關鍵幀拼接表示整個視頻序列拼接成為有效的方法。參考文獻[3]提出SIFT結合Kalman跟蹤算法進行關鍵幀的提取及拼接的實現，由于視頻序列幀數量較大，而SIFT算法本身復雜，SIFT對每一幀都進行處理，累積造成運算時間比較長。參考文獻[4]提出利用分層式自適應幀采樣的視頻拼接，但這種方法的計算量大，算法限制條件較多，容易導致拼接失敗。參考文獻[5]提出采用四叉樹方式來解決重疊區域大小確定問題，但是沒有從根本上解決大量視頻序列拼接時匹配誤差增大的問題。針對以上問題，提出了一種新的視頻序列拼接算法，可以有效提取關鍵幀，利用關鍵幀拼接表示整個視頻序列拼接，從而節省視頻拼接時間。首先，利用KLT算法對視頻序列中每幀特征點進行提取，并通過特征點的跟蹤實現進行關鍵幀粗略選取。其次，在選取的關鍵幀中利用SURF算法進行紋理特征提取，并利用最近鄰距離比進行特征點匹配[6]，通過估計算法求精單映矩陣，結合關鍵幀選取判定尋找最佳關鍵幀。最后，通過RANSAC級聯單映矩陣和加權融合算法實現拼接，取得較好效果。

1 幀間的單映變換矩陣及關鍵幀選取判定

單映矩陣變換是一種常用的幀間變換模型，主要適用于任意場景空間攝像機為旋轉或者縮放運動，或者空間為平面場景和任意攝像機的運動。單映矩陣變換表示為：

對于相鄰的關鍵幀，可以直接采用上述幀間變換模型，但是對于非相鄰的關鍵幀，可以利用單映矩陣的級聯性質，得到非相鄰關鍵幀之間的單映變換矩陣。

假設第k幀、第h幀為非相鄰的關鍵幀，以第 k幀作為參考幀，第h幀為目標幀，利用單映矩陣的級聯性質，可以得到兩非相鄰關鍵幀的單映變換矩陣：

其 中 ，Hh，tHt，n…Hm，lHl，k分 別 是 第 k 幀 、 第 h 幀 之 間 的 相鄰關鍵幀的單映變換矩陣，如圖1所示。

圖1 單映矩陣的級聯示意圖

在關鍵幀選取效果不好的情況下，非相鄰關鍵幀數量比較多，容易造成匹配誤差增大。為了進一步減少關鍵幀的數量，減小單映矩陣級聯時造成的誤差，通過如下比較進行運算，進一步提取關鍵幀，從而完成關鍵幀的選取判定。具體步驟為：

(1)設定第k幀、第h幀為非相鄰的關鍵幀，直接計算兩關鍵幀單映矩陣 Hk，h；

(2)將單映矩陣級聯方法和直接計算單映矩陣方法計算出來的結果進行比較，比較 h0、h1、h2、h3、h4、h5、h6、h7值的誤差大小，只要有一項數值超過預定的閾值，則認為第h幀的前一項關鍵幀是須保留的，第k幀和第h幀前一項關鍵幀作為保留關鍵幀，兩者之間的其他關鍵幀可以省略。

2 關鍵幀的提取方法

2.1 KLT特征點跟蹤算法

由于視頻序列幀與幀之間的冗余較大，考慮采用KLT特征點跟蹤算法來實現關鍵幀的粗略選取。KLT算法是以待跟蹤窗口在視頻圖像幀間的灰度差平方和作為度量的跟蹤算法[8]。對于相鄰視頻幀I和視頻幀J中的兩個窗口，直接的SSD為：

其 中 ，X=[x，y]T，d=[dx，dy]T， 窗 函 數 W(x，y)通 常 是 常 數1，對圖像J進行泰勒公式展開，可以近似得出如下公式：

為了求SSD最小值，則有：

為得到偏移量d，令偏分方程為零，得：

2.2 SURF特征提取算法

KLT特征點跟蹤算法有較高的求解效率，但是對紋理變化復雜的情況，常由于誤匹配而造成被跟蹤點的丟失。因此，利用上述KLT特征點跟蹤算法提取關鍵幀后，對關鍵幀再利用SURF算法進行特征點的提取，為后續提取最佳關鍵幀提供有效方法。

SURF算法利用快速Hessian檢測算法提取特征點[9]，Hessian矩陣具有良好的計算時間和精度表現。

SURF特征描述子的提取可以分為兩步：(1)根據特征點周圍的一個圓形區域找到特征點的主方向；(2)在選定的主方向上構建一個矩形區域，并提取所有的特征描述點信息。在主方向上構建一個大小為20σ的窗口(σ表示尺度)，并將該窗口區域分為4×4的子區域，對于每一個子區域，分別計算相對于主方向的水平和垂直方向Haar小波響應，每個子區域得到 4維向量，因此 4×4的子區域得到64維特征點描述子，它可以擴展到128維的特征點描述子，一般采用128維特征點描述子。

3 拼接算法的實現及實驗結果

3.1 拼接方法的實現

按照上述所述，拼接的具體實現步驟如下：

(1)為了選取關鍵幀子序列，使全景圖內容豐富，第一幀和最后一幀為必選關鍵幀，選取第一幀視頻序列關鍵幀為基準幀，提取基準幀的特征點。

(2)利用KLT算法進行特征點的提取并跟蹤，從而確定粗略的關鍵幀，具體如下：

①假設選取的特征點個數為N，比例因子為α，對視頻序列經過特征點跟蹤，當特征點個數減至αN時，停止跟蹤，選取當前幀為關鍵幀，并作為后續跟蹤的基準幀；

②重復上述過程，直至視頻序列跟蹤完畢，最后獲取粗略視頻關鍵幀，對原始視頻幀圖像進行跟蹤，計算量較大，為減少計算量，利用高斯圖像金字塔，并通過插值獲取原始視頻幀中特征點[10]。

會議要求，要運用互聯網推動“三農”工作的創新，要把農業農村電子商務放在更廣闊的視野，深入謀劃、精心組織，要加強頂層設計，加大政策支持，做好宣傳引導，推動農業農村電子商務跨越發展。

(3)利用SURF算法對關鍵幀提取特征點，采用最近鄰距離比進行特征點匹配，并利用幀間單映矩陣模型和關鍵幀選取判定方法進行優化的關鍵幀選擇。具體如下：

①利用SURF特征點提取算法對步驟 (2)選定的關鍵幀進行特征提取；

②對相鄰關鍵幀利用幀間單映矩陣模型進行匹配計算。為了使單映矩陣H的估計準確，利用RANSAC魯棒估計方法得到相鄰關鍵幀之間單映矩陣H的估計，具體步驟為：

(a)隨機抽取n≥4對匹配特征點來估計矩陣H的參數；

(b)對于步驟(2)中的每一對匹配點，計算對單映矩陣H的擬合誤差；

(c)設定一個門限值，若擬合誤差小于此門限值，表示匹配點對是一致點，并統計一致點的數目；

(d)重復步驟(a)～(c)，直到所有的一致點集中至少有一個有效表征集的概率大于一定的數值為止；

(e)選擇具有最大一致點集的單映矩陣H。

③對非相鄰關鍵幀利用單映矩陣的級聯性進行計算，利用關鍵幀選取判定方法進一步得到選定關鍵幀。

(4)將步驟(3)選定的關鍵幀作為最終拼接的關鍵幀，利用單映矩陣級聯和加權融合算法完成視頻序列的拼接。

3.2 實現結果

實驗采用自拍的兩段視頻，利用上述方法完成了視頻序列的拼接，效果比較好。

圖2所示是將拍攝的一段200幀的視頻利用上述方法獲取的最終關鍵幀，其拼接效果圖如圖3所示，剪切處理后的視頻序列拼接最終效果圖如圖4所示。

圖5是自拍的一段350幀的視頻，利用上述算法獲取的關鍵幀，視頻拼接效果圖如圖6所示，剪切處理后視頻序列最終拼接效果圖如圖7所示。

圖2 獲取視頻序列關鍵幀

圖3 關鍵幀表示的視頻序列拼接

圖4 關鍵幀表示的視頻序列最終拼接效果

圖5 獲取視頻序列關鍵幀

圖6 關鍵幀視頻序列拼接圖

圖7 關鍵幀表示的視頻序列最終拼接效果

本文采用了一種新的視頻序列拼接方法，利用KLT特征點跟蹤算法實現粗略關鍵幀的選取，再次利用SURF特征點提取算法結合最近鄰距離比匹配方法、關鍵幀判定準則，對關鍵幀進行進一步提取，并利用RANSAC估計算法對單映矩陣進行求精，通過級聯單映矩陣和加權融合算法實現視頻序列拼接，取得了較好效果。

[1]KIM D H， YOON Y I， CHOI J S.An efficient method to build panoramic image mosaics[J].Pattern Recognition Letters，2003，24(1)： 2421–2429.

[2]SHUM H Y，SZELISKI R.Panoramic image mosaics[R].TechnicalReport， MSR-TR-97-23， MicrosoftResearch，Redmong， WA， USA， 1997：1-3.

[3]FADAEIESLAM M J， FATHY M， SORYANI M.Key frames selections into panoramic mosaics[C].Proceedings of the 7th International Joint Conference on Information， Communication and signal， Macau， 2009.

[4]劉永，王貴錦，姚安邦，等.基于自適應幀采樣的視頻拼接[J].清華大學學報(自然科學版)，2010，50(1)：108-112.

[5]BABU D R R，RAVISHANKAR M.Automatic seamless image mosaicing：an approach based on quad-tree technique[C].Proceedings of the World Congress on Engineering，University of Oxford， UK， 2010，London，UK.

[6]LOWE D G.Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision，2004，60(2)：91-110.

[7]HARTLEY R，AISSENRMAN A.Multiple view geometry in computer version[M].Cambridge， UK： Cambridge University Press，2000.

[8]TOMASI J S C.Good features to track[C].IEEE Computer Society Conference on Computer Vision and Pattern Recognition， Seattle， WA， USA，1994：593-600.

[9]BAY H， TUYTELAARS T， GOOL L V.SURF：speed up robust features[J].Computer Science， 2006，3951(1)：404-417.

[10]SINHA SN， FRAHM JM， POLLEFEYSM， etal.Feature tracking and matching in video using programmable graphics hardware[J].Machine Vision and Applications，2007， 22(1)： 207-217.