摘  要： 提出了一種基于視頻序列拼接的新方法。首先，利用KLT算法對視頻序列中特征點進行提取和跟蹤，實現關鍵幀粗略選取；其次，在選取的關鍵幀中利用SURF算法進行特征提取，利用最近鄰距離比進行特征點匹配，通過RANSAC估計算法求精單映矩陣，并結合關鍵幀選取判定尋找最佳關鍵幀；最后，利用級聯單映矩陣和加權融合算法實現視頻序列拼接。實驗驗證了該方法的有效性。
關鍵詞： KLT算法；關鍵幀；SURF算法；單映矩陣

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

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

　利用計算Z的特征值，選取兩個特征值比較大的點作為跟蹤的特征點，在選定的特征點基礎上再利用Zd=e可以計算出特征點的漂移。跟蹤停止條件是特征值小于規定的最小特征值以及迭代次數超過設定次數。
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所示。

　本文采用了一種新的視頻序列拼接方法，利用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， Microsoft Research， 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 S N， FRAHM J M， POLLEFEYS M， et al. Feature tracking and matching in video using programmable graphics hardware[J]. Machine Vision and Applications， 2007， 22(1)： 207-217.