基于SURF和改進RANSAC的視頻拼接算法

陳雪濤，穆春陽，馬　行（北方民族大學(xué)信息與通信研究所，寧夏銀川　750021）

?

基于SURF和改進RANSAC的視頻拼接算法

陳雪濤，穆春陽，馬行
（北方民族大學(xué)信息與通信研究所，寧夏銀川750021）

摘要：在傳統(tǒng)的視頻拼接算法中，配準的誤差和運動的物體都會使拼接結(jié)果產(chǎn)生鬼影，而復(fù)雜的融合算法又難以滿足實時性要求。針對上述問題，以平行光軸且光心位于同一水平基線位置的雙目相機采集的視頻圖像為研究對象，提出一種基于限定區(qū)域和SURF算法的視頻拼接方法。針對采集到的具有20%～30%重疊感興趣區(qū)域（ROI）的視頻圖像，每24幀設(shè)置一個關(guān)鍵幀，僅對關(guān)鍵幀的ROI區(qū)域采用SURF算法尋找特征匹配點對。然后采用改進的RANSAC算法篩選單應(yīng)性變換矩陣H，對非關(guān)鍵幀直接采用此單應(yīng)性變換矩陣H進行圖像融合。實驗結(jié)果表明，采用關(guān)鍵幀計算特征點的方式得到的視頻拼接效果能夠很好地消除鬼影，同時也能夠保證視頻融合的實時性。

關(guān)鍵詞：視頻拼接；ROI；關(guān)鍵幀；RANSAC

0　引　言

人們獲取信息的方式多種多樣，例如通過觸覺、視覺、嗅覺和聽力等，其中視覺是最直接也是最廣泛的獲取信息的方式之一。在現(xiàn)代社會中，人們通過視覺獲取大量有用信息。由于人的視角或者機器的視角范圍有限，因此，對多個視頻進行拼接并形成大視角范圍的圖[1]，這有著非常重大的研究意義。視頻拼接技術(shù)在許多方面有著重要的應(yīng)用，例如環(huán)境監(jiān)測[2]、監(jiān)控系統(tǒng)[3]和生物工程[4]等。

當(dāng)前視頻拼接的方法多種多樣，文獻[5]采用一種改進的快速檢測Harris算子，結(jié)合捆綁調(diào)整進行全局調(diào)整方法，能夠得到很好的拼接效果。文獻[6]提出了基于圖像分塊和鄰近角點剔除策略的自適應(yīng)Harris角點檢測算法，該算法能很好地適應(yīng)圖像拼接。文獻[7]對圖像進行SIFT特征提取并進行粗匹配，再用RANSAC方法剔除誤匹配點獲得變換單應(yīng)陣，最后用查表法投影圖像，最終實現(xiàn)融合拼接。文獻[8]在SIFT提取不變特征向量過程中加入Harris算子，運用KLT跟蹤算法，精確特征點的位置，提高了圖像拼接的穩(wěn)健性和快速性。文獻[9]提出基于SURF和動態(tài)ROI方法的視頻圖像快速拼接方法，獲得較清晰的寬敞景視頻?；谝陨纤幸曨l拼接方法，有的算法比較復(fù)雜，運算量巨大，會消耗大量時間，不利于實時視頻拼接；有的算法拼接效果不是很理想，會產(chǎn)生明顯的鬼影，影響了拼接效果。針對上述2個問題，在SURF算法的基礎(chǔ)上，提出了改進的拼接算法，最終效果比較理想。

1　視頻拼接算法分析

在這里，首先設(shè)定平行光軸且光心位于同一水平基線位置的雙目相機采集到圖像的重疊部分在20%～30%之間。由于人眼的視覺暫留現(xiàn)象這里引入關(guān)鍵幀，既每24幀視頻設(shè)置一個關(guān)鍵幀，關(guān)鍵幀和非關(guān)鍵幀采取不同的算法步驟。整個算法流程可分為A、B、C和D四個部分，如圖1所示。

圖1　視頻拼接算法流程框圖

圖1中：A部分主要是獲取視頻文件并且設(shè)置一些參數(shù)；B部分是對關(guān)鍵幀在重疊區(qū)域的ROI中用SURF算法生成特征描述算子，從而生成匹配點對；C部分是用改進的RANSAC算法篩選匹配點對并生成最終的變換矩陣H；D部分是圖像幀的融合形成拼接圖像。

當(dāng)獲取雙目相機采集到的視頻數(shù)據(jù)之后，對于第一幀視頻，在前面限定的ROI區(qū)域內(nèi)，利用SURF算法找出兩幀的特征匹配點對，再利用改進的RANSAC算法篩選出單應(yīng)性變換矩陣H，之后在變換矩陣H基礎(chǔ)上利用融合算法拼接兩幀圖像形成拼接圖，而對于非關(guān)鍵幀，在此直接采用前面利用SURF算法對關(guān)鍵幀處理后生成的變換矩陣H來融合。

1.1SURF算法分析

SURF算法由Herbert Bay等提出的具有尺度和旋轉(zhuǎn)不變性的算法[10]，其具體步驟如下：

（1）Hessian矩陣（SURF算法的核心），設(shè)圖像像素為I(x，y)，則H矩陣可表示為：

式中：Lxx，Lyy和Lxy分別是圖像在x方向、y方向和xy方向的二階高斯濾波。通常Hessian矩陣的特征值用H矩陣的近似判別式表示為：

式中，α為權(quán)系數(shù)，這里根據(jù)計算取α=0.9，可以根據(jù)此特征值的符號將所有點分類。

（2）利用Hessian矩陣公式計算兩幀圖像中的限定區(qū)域ROI中所有點的特征值。在不同尺度空間下的高斯濾波圖像中，將像素點I(x，y)的特征值與三維空間下該點周圍及上下兩層共26個點的特征值進行比較，把其中最大值或者最小值保留下來，作為一個特征點。

（3）根據(jù)特征點的Harr小波特性，統(tǒng)計出每一個特征點的主方向。以特征點I(x，y)為中心，以6s（s為特征點所在的尺度）為半徑，統(tǒng)計出圓中60°扇形區(qū)域的所有特征點的Harr小波特征總和，然后以一定角度旋轉(zhuǎn)，遍歷整個圓形區(qū)域，把最后得到的Harr小波特征總和最大值的扇形區(qū)域的方向作為特征點I(x，y)的主方向。

（4）在前述基礎(chǔ)上構(gòu)建特征描述算子。以特征點I(x，y)為中心，以上一步求出的主方向為方向，構(gòu)建一個邊長為20s（s為特征點所在的尺度）的正方形區(qū)域，并把該正方形均分成16個小區(qū)域，并統(tǒng)計每一個小區(qū)域中25個像素點的Harr小波特征，分別求出水平方向、垂直方向、水平方向絕對值、垂直方向絕對值之和，由此可以生成一個64維的特征向量描述子。

（5）最后，生成了每幀圖像ROI區(qū)域的所有特征點描述算子的兩個集合，A和B，可以尋找出特征匹配對。這里采用歐式距離法，即選取集合A中的一個特征向量，采用遍歷法，利用式（3）計算其與集合B中距離最近的兩個點，如果次近距離除以最近距離小于一定閾值，則判定為匹配點對：

式中：n=64；xi1表示第一個點的第i維坐標；xi2表示第二個點的第i維坐標。

1.2改進的RANSAC算法介紹

計算出所有匹配點對后，采用改進的RANSAC算法計算仿射變換矩陣H，詳細步驟如流程圖2所示。

改進的RANSAC算法流程可分為A，B兩部分，A部分是在上面SURF算子粗匹配的點對中依順序選取一匹配點對，把匹配對中特征點主方向和長度都匹配的點保留下來，而不符合的匹配點對都舍棄，直到檢測完所有特征點匹配對。假設(shè)(Pi，Qi)是一對匹配對，Pi和Qi分別表示兩幀圖中的對應(yīng)特征點，Pdx和Pdy分別表示Pi點Harr小波響應(yīng)在水平和垂直方向上的矢量分量，Pθ表示Pi點的方向角，則Pθ表示為：

特征點Pi方向矢量的長度Plength表示為公式（5）：

同理，Qdx和Qdy分別表示Qi點Harr小波響應(yīng)在水平和垂直方向上的矢量分量，Qθ表示Qi點的方向角，則有Qθ表示為公式（6）：

特征點Qi方向矢量的長度Qlength表示為：

當(dāng)兩個特征點的方向角之差的絕對值|Pθ- Qθ|小于某一設(shè)定閾值ε，且特征點方向矢量長度之差的絕對值|Plength- Qlength|小于某一設(shè)定閾值δ時，保留這對匹配對，否則舍棄匹配對。

圖2　改進的RANSAC算法流程圖

接下來在B部分中，從篩選后留下的匹配點對中隨機抽取4個匹配點對，把這些特征匹配點對代入變換模型計算出仿射變換矩陣H，這里在齊次坐標系下兩幅圖像之間的變換模型可以用下式來表示：

式中：（x′，y′）∈I1和(x，y)∈I2（I1，I2分別表示圖像1和圖像2）；h1，h2，h4和h5是旋轉(zhuǎn)和尺度變換因子；h3是水平位移因子；h6是垂直位移因子；h7，h8是水平和垂直方向的變形量。重復(fù)此步中的B部分N次，找出滿足迭代計算矩陣最多的特征匹配對，利用這些特征匹配對計算出最終的仿射變換矩陣H。此改進的RANSAC算法能夠去除大部分外點，保留下來的內(nèi)點比例進一步提高，最終計算出穩(wěn)定的H矩陣，很好地消除了拼接鬼影。

1.3圖像的融合

當(dāng)計算出正確的仿射變換矩陣H后，參考圖像幀位置不變，對待匹配圖像用矩陣H進行相應(yīng)的變換。通常，融合方法有平均值法、加權(quán)均值法和最大值法等，此文采用漸入漸出加權(quán)均值法，具體融合方法用公式（9）表示：

式中：I(x，y)表示融合后的幀圖像像素點；I1(x，y)和I2(x，y)分別表示待拼接的幀圖像像素點；w1和w2表示重疊區(qū)域?qū)?yīng)像素點的權(quán)值，且有w1+ w2=1，0≤w1≤1，0≤w2≤1。假設(shè)兩幀圖像重疊區(qū)域的寬度為L，重疊區(qū)域左邊界起始位置為Xstart，則w1可表示為：

即待拼接圖像I1(x，y)中的像素點的權(quán)重與當(dāng)前處理點距重疊區(qū)域左邊界的距離成反比。

2　實驗結(jié)果及分析

實驗的測試平臺為CPU Intel?Core（TM）4 i5?3470 CPU@ 3.20 GHz，內(nèi)存8 GB，軟件開發(fā)環(huán)境為Qt+OpenCV 2.4，采用的源視頻分辨率為480×360。經(jīng)過實驗，把一般的SURF+傳統(tǒng)RANSAC算法（以下稱為算法一）和本文所采取的SURF+改進RANSAC算法（以下稱為算法二）進行了比較，結(jié)果如下所述。

本實驗選取兩段視頻作為分析對象，統(tǒng)計了視頻一和視頻二采用傳統(tǒng)算法一和本文算法二所找到的匹配點對數(shù)（如圖3所示）和拼接一幀關(guān)鍵幀圖像所耗費時間總和（如圖4所示）。圖3（a）、（b）兩圖分別是視頻序列一和視頻序列二的前400幀中關(guān)鍵幀的配對數(shù)統(tǒng)計結(jié)果圖。由圖3可知采用本文算法二找到的匹配對數(shù)比采用傳統(tǒng)算法一找到的匹配對數(shù)有所減少，說明本文算法能夠剔除部分傳統(tǒng)算法中的誤匹配點對數(shù)，有助于提高計算H矩陣的精度，同時也能夠減少改進RANSAC篩選H矩陣所消耗的時間。

圖3　視頻序列關(guān)鍵幀配對數(shù)目統(tǒng)計圖

圖4（a）、（b）中兩圖分別表示視頻序列一和視頻序列二的前400幀中關(guān)鍵幀的拼接耗時統(tǒng)計圖，從圖4中可以看出拼接一幀關(guān)鍵幀，算法二耗時更少，經(jīng)計算，算法二的平均效率為算法一的1.5～2倍，本文算法在耗時性能上相比算法一來說有所提高，這有助于提高實時視頻拼接的性能。一融合的效果，可以看到明顯的模糊重影；而圖7（b）中黑色方框圈出的重疊區(qū)域部分是使用本文算法二融合的效果圖，對比來看，其中黑色圈出的部分算法二的融合效果明顯好于算法一。

圖7　視頻序列一拼接效果圖

圖4　視頻序列關(guān)鍵幀耗時統(tǒng)計

本文只對關(guān)鍵幀進行特征點匹配，隨機選擇了視頻一中的2個關(guān)鍵幀和視頻二中的2個關(guān)鍵幀進行分析，根據(jù)本文改進后的RANSAC算法處理之后找到的精確匹配點對，如圖5（a）、圖5（b）所示，兩圖分別是視頻序列一第1幀和第264幀的匹配對圖，圖6（a）、圖6（b）兩圖分別是第1幀和第432幀的匹配對圖，從圖6中可以看出在設(shè)定的ROI區(qū)域內(nèi)，即圖6中黑色方框區(qū)域內(nèi)，經(jīng)篩選后的匹配對效果不錯；同時經(jīng)過大量實驗證明，本文算法找到的特征點匹配對效果優(yōu)于一般算法。

圖5　視頻序列一第1幀和264幀匹配圖

圖6　視頻序列二第1幀和432幀匹配圖

下面分別隨機選取兩個視頻序列中的一幀圖像進行分析，圖7（a）、（b）分別是使用傳統(tǒng)算法一和本文算法二對視頻序列一中第72幀拼接后的效果圖，其中圖7（a）中黑色方框圈出的重疊區(qū)域部分為使用算法

圖8（a）、（b）分別是使用傳統(tǒng)算法一和本文算法二對視頻序列二的第1幀拼接后的效果圖，可以明顯看出圖8（a）中黑色方框圈出的大樹部分比較模糊，這是拼接重影；而圖8（b）是使用本文算法二對視頻序列二拼接后的效果圖，其中黑色方框圈出的部分比圖8（a）中對應(yīng)的部分效果要好，因此可以斷定本文算法在消除重影方面要優(yōu)于一般的算法。

圖8　視頻序列二拼接效果圖

同時，本文統(tǒng)計了使用算法二時視頻序列一中前144幀中關(guān)鍵幀和非關(guān)鍵幀的耗時，具體如表1所示。

表1　關(guān)鍵幀和非關(guān)鍵幀的拼接耗時統(tǒng)計　s

由表1可知，共統(tǒng)計了N=144幀的耗時情況，其中6個關(guān)鍵幀的總耗時T0=1.917 2 s；138個非關(guān)鍵幀的總耗時T1=4.169 2 s，所以總耗時T= T0+ T1=6.086 4 s，平均每一幀約耗時Tm=T/ N =0.042 26 s，而一般視頻播放速率在24幀以上，也即每一幀需要用時在0.041 667 s左右，所以根據(jù)本文統(tǒng)計的視頻幀耗時時間，基本吻合，滿足實時性要求。

3　結(jié)　論

本文基于限定重疊ROI區(qū)域，提出了基于SURF算法的改進方法，利用改進的RANSAC算法，快速地找到了ROI區(qū)域中的匹配點對，節(jié)省了大量的匹配時間，同時和傳統(tǒng)的方法相比較，本文算法在消除鬼影方面有了較大進步，能夠很好地去除鬼影。再者，采用了關(guān)鍵幀技術(shù)，對關(guān)鍵幀和非關(guān)鍵幀采取了不同的算法步驟，避免了每一幀都進行特征點匹配而產(chǎn)生的時間冗余，大大的提高了實時性，所以本文采取的方法對視頻拼接技術(shù)的研究及應(yīng)用有一定的參考價值。

參考文獻

[1]ZENG Lin，DENG Dexiang，CHEN Xi，et al. A self?adaptive and real?time panoramic video mosaicing system [J]. Journal of computers，2012，7（1）：218?225.

[2]ZHU Zhigang，RISEMAN E M. HANSON A R，et al. An effi?cient method for geo?referenced video mosaicking for environ?mental monitoring [J]. Machine vision and applications，2005，16（4）：203?216.

[3]GUO K Y，YE S，JIANG H M，et al. An algorithm based on SURF for surveillance video mosaicing [J]. Advanced materials research，2011，267：746?751.

[4]VAN REIN H，SCHOEMAN D S，BROWN C J，et al. Develop?ment of low?cost image mosaics of hard?bottom sessile commu?nities using SCUBA：comparisons of optical media and of proxy measures of community structure [J]. Journal of Marine Biological Association of United Kingdom，2012，92（01）：49?62.

[5]王小強，陳臨強，梁旭.實時全自動視頻拼接方法[J].計算機工程，2011，37（5）：291?292.

[6]趙萬金，龔聲蓉，劉純平，等.一種自適應(yīng)的Harris角點檢測算法[J].計算機工程，2008，34（10）：212?214.

[7]劉暢，金立左，費樹岷，等.固定多攝像頭的視頻拼接技術(shù)[J].數(shù)據(jù)采集與處理，2014，29（1）：126?133.

[8]尚明姝.基于改進SIFT特征匹配的快速圖像拼接算法[J].微電子學(xué)與計算機，2014，31（1）：64?67.

[9]首照宇，歐陽寧，張華俊，等.基于SURF和動態(tài)ROI的實時視頻拼接[J].計算機工程與設(shè)計，2013，34（3）：998?1003.

[10]BAY Herbert. Speeded?up robust features（SURF）[J]. Com?puter vision and image understanding，2008，110（3）：346?359.

[11]宋翔.基于Director的動畫創(chuàng)作技術(shù)研究[J].現(xiàn)代電子技術(shù)， 2011，34（8）:108?110.

Video stitching algorithm based on SURF and improved RANSAC

CHEN Xuetao，MU Chunyang，MA Xing
（Institute of Information and Communication Technology，Beifang University of Nationalities，Yinchuan 750021，China）

Abstract：In the traditional video stitching，the calibration error and the motion of an object may cause the ghost shadows in stitching results. In addition，the complex fusion algorithm can’t meet the real?time requirement. In order to solve the above problems，the video images acquired by binocular camera that has a parallel optical axis and its optic center is at the same hori?zontal baseline are studied，and a new method of real?time video stitching based on limited region and SURF algorithm is put for?ward in this paper. A key frame is set per 24 frames for the video images with 20%～30% overlap area in ROI area. the SURF al?gorithm is used to look for the feature matching point pairs in the ROI overlap area of key frame only. The homography transfor?mation matrix H is selected with the improved RANSAC algorithm，and then the image fusion is executed for non?key frames by using the transformation matrix H directly. The experiment results show that the video stitching algorithm proposed in this paper can eliminate the ghost shadows well，also can ensure the real?time performance of video.

Keywords：video stitching；ROI；key?frame；RANSAC

中圖分類號：TN911.72?34

文獻標識碼：A

文章編號：1004?373X（2016）10?0044?05

doi：10.16652/j.issn.1004?373x.2016.10.012

收稿日期：2015?09?19

基金項目：國家自然科學(xué)基金項目（61162005，61163002）；機器人技術(shù)與系統(tǒng)國家重點實驗室開放研究基金課題（SKLRS?2013?MS?05）

作者簡介：陳雪濤（1987—），男，河南信陽人，碩士。研究方向為信號檢測與信息處理。穆春陽（1975—），男，黑龍江人，副教授，博士。研究方向為嵌入式系統(tǒng)與智能控制。馬行（1980—），女，寧夏銀川人，副教授，博士。研究方向為視頻圖像處理。