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

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

　在關(guān)鍵幀選取效果不好的情況下，非相鄰關(guān)鍵幀數(shù)量比較多，容易造成匹配誤差增大。為了進(jìn)一步減少關(guān)鍵幀的數(shù)量，減小單映矩陣級(jí)聯(lián)時(shí)造成的誤差，通過(guò)如下比較進(jìn)行運(yùn)算，進(jìn)一步提取關(guān)鍵幀，從而完成關(guān)鍵幀的選取判定。具體步驟為：
　(1)設(shè)定第k幀、第h幀為非相鄰的關(guān)鍵幀，直接計(jì)算兩關(guān)鍵幀單映矩陣Hk，h；
　(2)將單映矩陣級(jí)聯(lián)方法和直接計(jì)算單映矩陣方法計(jì)算出來(lái)的結(jié)果進(jìn)行比較，比較h0、h1、h2、h3、h4、h5、h6、h7值的誤差大小，只要有一項(xiàng)數(shù)值超過(guò)預(yù)定的閾值，則認(rèn)為第h幀的前一項(xiàng)關(guān)鍵幀是須保留的，第k幀和第h幀前一項(xiàng)關(guān)鍵幀作為保留關(guān)鍵幀，兩者之間的其他關(guān)鍵幀可以省略。
2 關(guān)鍵幀的提取方法
2.1 KLT特征點(diǎn)跟蹤算法
　由于視頻序列幀與幀之間的冗余較大，考慮采用KLT特征點(diǎn)跟蹤算法來(lái)實(shí)現(xiàn)關(guān)鍵幀的粗略選取。KLT算法是以待跟蹤窗口在視頻圖像幀間的灰度差平方和作為度量的跟蹤算法[8]。對(duì)于相鄰視頻幀I和視頻幀J中的兩個(gè)窗口，直接的SSD為：

　利用計(jì)算Z的特征值，選取兩個(gè)特征值比較大的點(diǎn)作為跟蹤的特征點(diǎn)，在選定的特征點(diǎn)基礎(chǔ)上再利用Zd=e可以計(jì)算出特征點(diǎn)的漂移。跟蹤停止條件是特征值小于規(guī)定的最小特征值以及迭代次數(shù)超過(guò)設(shè)定次數(shù)。
2.2 SURF特征提取算法
　KLT特征點(diǎn)跟蹤算法有較高的求解效率，但是對(duì)紋理變化復(fù)雜的情況，常由于誤匹配而造成被跟蹤點(diǎn)的丟失。因此，利用上述KLT特征點(diǎn)跟蹤算法提取關(guān)鍵幀后，對(duì)關(guān)鍵幀再利用SURF算法進(jìn)行特征點(diǎn)的提取，為后續(xù)提取最佳關(guān)鍵幀提供有效方法。
　SURF算法利用快速Hessian檢測(cè)算法提取特征點(diǎn)[9]，Hessian矩陣具有良好的計(jì)算時(shí)間和精度表現(xiàn)。
　SURF特征描述子的提取可以分為兩步：(1)根據(jù)特征點(diǎn)周圍的一個(gè)圓形區(qū)域找到特征點(diǎn)的主方向；(2)在選定的主方向上構(gòu)建一個(gè)矩形區(qū)域，并提取所有的特征描述點(diǎn)信息。在主方向上構(gòu)建一個(gè)大小為20δ的窗口(δ表示尺度)，并將該窗口區(qū)域分為4×4的子區(qū)域，對(duì)于每一個(gè)子區(qū)域，分別計(jì)算相對(duì)于主方向的水平和垂直方向Haar小波響應(yīng)，每個(gè)子區(qū)域得到4維向量，因此4×4的子區(qū)域得到64維特征點(diǎn)描述子，它可以擴(kuò)展到128維的特征點(diǎn)描述子，一般采用128維特征點(diǎn)描述子。
3 拼接算法的實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果
3.1 拼接方法的實(shí)現(xiàn)

　按照上述所述，拼接的具體實(shí)現(xiàn)步驟如下：
　(1)為了選取關(guān)鍵幀子序列，使全景圖內(nèi)容豐富，第一幀和最后一幀為必選關(guān)鍵幀，選取第一幀視頻序列關(guān)鍵幀為基準(zhǔn)幀，提取基準(zhǔn)幀的特征點(diǎn)。
　(2)利用KLT算法進(jìn)行特征點(diǎn)的提取并跟蹤，從而確定粗略的關(guān)鍵幀，具體如下：
?、偌僭O(shè)選取的特征點(diǎn)個(gè)數(shù)為N，比例因子為α，對(duì)視頻序列經(jīng)過(guò)特征點(diǎn)跟蹤，當(dāng)特征點(diǎn)個(gè)數(shù)減至αN時(shí)，停止跟蹤，選取當(dāng)前幀為關(guān)鍵幀，并作為后續(xù)跟蹤的基準(zhǔn)幀；
　②重復(fù)上述過(guò)程，直至視頻序列跟蹤完畢，最后獲取粗略視頻關(guān)鍵幀，對(duì)原始視頻幀圖像進(jìn)行跟蹤，計(jì)算量較大，為減少計(jì)算量，利用高斯圖像金字塔，并通過(guò)插值獲取原始視頻幀中特征點(diǎn)[10]。
　(3)利用SURF算法對(duì)關(guān)鍵幀提取特征點(diǎn)，采用最近鄰距離比進(jìn)行特征點(diǎn)匹配，并利用幀間單映矩陣模型和關(guān)鍵幀選取判定方法進(jìn)行優(yōu)化的關(guān)鍵幀選擇。具體如下：
　①利用SURF特征點(diǎn)提取算法對(duì)步驟(2)選定的關(guān)鍵幀進(jìn)行特征提?。?br /> ?、趯?duì)相鄰關(guān)鍵幀利用幀間單映矩陣模型進(jìn)行匹配計(jì)算。為了使單映矩陣H的估計(jì)準(zhǔn)確，利用RANSAC魯棒估計(jì)方法得到相鄰關(guān)鍵幀之間單映矩陣H的估計(jì)，具體步驟為：
　(a)隨機(jī)抽取n≥4對(duì)匹配特征點(diǎn)來(lái)估計(jì)矩陣H的參數(shù)；
　(b)對(duì)于步驟(2)中的每一對(duì)匹配點(diǎn)，計(jì)算對(duì)單映矩陣H的擬合誤差；
　(c)設(shè)定一個(gè)門限值，若擬合誤差小于此門限值，表示匹配點(diǎn)對(duì)是一致點(diǎn)，并統(tǒng)計(jì)一致點(diǎn)的數(shù)目；
　(d)重復(fù)步驟(a)~(c)，直到所有的一致點(diǎn)集中至少有一個(gè)有效表征集的概率大于一定的數(shù)值為止；
　(e)選擇具有最大一致點(diǎn)集的單映矩陣H。
　③對(duì)非相鄰關(guān)鍵幀利用單映矩陣的級(jí)聯(lián)性進(jìn)行計(jì)算，利用關(guān)鍵幀選取判定方法進(jìn)一步得到選定關(guān)鍵幀。
　(4)將步驟(3)選定的關(guān)鍵幀作為最終拼接的關(guān)鍵幀，利用單映矩陣級(jí)聯(lián)和加權(quán)融合算法完成視頻序列的拼接。
3.2 實(shí)現(xiàn)結(jié)果
　實(shí)驗(yàn)采用自拍的兩段視頻，利用上述方法完成了視頻序列的拼接，效果比較好。
　圖2所示是將拍攝的一段200幀的視頻利用上述方法獲取的最終關(guān)鍵幀，其拼接效果圖如圖3所示，剪切處理后的視頻序列拼接最終效果圖如圖4所示。
　圖5是自拍的一段350幀的視頻，利用上述算法獲取的關(guān)鍵幀，視頻拼接效果圖如圖6所示，剪切處理后視頻序列最終拼接效果圖如圖7所示。

　本文采用了一種新的視頻序列拼接方法，利用KLT特征點(diǎn)跟蹤算法實(shí)現(xiàn)粗略關(guān)鍵幀的選取，再次利用SURF特征點(diǎn)提取算法結(jié)合最近鄰距離比匹配方法、關(guān)鍵幀判定準(zhǔn)則，對(duì)關(guān)鍵幀進(jìn)行進(jìn)一步提取，并利用RANSAC估計(jì)算法對(duì)單映矩陣進(jìn)行求精，通過(guò)級(jí)聯(lián)單映矩陣和加權(quán)融合算法實(shí)現(xiàn)視頻序列拼接，取得了較好效果。
參考文獻(xiàn)
[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] 劉永，王貴錦，姚安邦，等.基于自適應(yīng)幀采樣的視頻拼接[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，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.