基于范數優化路徑的視頻穩像算法

石春雷，楊文佳，黃培康

（1．光學輻射重點實驗室，北京100854；2．北京環境特性研究所，北京100854；3．電磁散射重點實驗室，北京100854）

基于范數優化路徑的視頻穩像算法

石春雷1，2，楊文佳2，黃培康3

（1．光學輻射重點實驗室，北京100854；2．北京環境特性研究所，北京100854；3．電磁散射重點實驗室，北京100854）

針對運動相機中視頻的隨機抖動和低頻晃動問題，提出了一種基于范數優化路徑的視頻穩像算法。該算法在特征點粗匹配之后引入概率進化抽樣一致性算法剔除誤匹配點，避免了局部運動對全局運動估計的影響，然后在定制的L1范數約束下構建相機的最優化運動路徑，最后利用新的路徑進行運動矯正獲取穩定的視頻圖像序列，實驗結果驗證了算法的有效性。

視頻穩像；概率進化抽樣；L1范數優化；相機運動路徑

0 引 言

視頻穩像技術廣泛應用于飛行器光電制導系統、視頻偵察系統、車載觀瞄系統以及無人車輛導航系統等，是目標檢測與跟蹤、光電精確制導的關鍵預處理技術。面對信息豐富的視頻序列，人們首先希望獲取的視頻能夠清晰穩定，然而攝像機載體的不規則運動，會使拍攝的視頻產生不穩定現象。因此，對于這種攝像載體存在不規則運動的視頻序列，如何在不同的環境下消除其隨機抖動干擾成為國內外學者研究的熱點。經典的二維穩像算法［1］，如塊匹配、空域灰度相關以及特征匹配等方法，均采用變換模型來描述幀間關系，具有魯棒性和速度快的優點，但是由于其運動模型本身受到約束，所以往往無法很好地解決存在旋轉或者前景運動目標的視頻抖動場景。三維視頻穩像通過運動模型技術［2］重構場景和相機運動的三維模型，然后在新的、平滑的三維相機運動軌跡上構建出新的圖像，能夠獲得更好的穩像效果，但是出現的新問題在于運動模型太復雜而難以保證魯棒性和實時性。因為視頻并不都具有足夠的運動信息而允許三維重建，在某些場景下并不具有魯棒性和一般性。例如文獻［3－4］都需要對攝像機進行標定。文獻［5］在統一的優化框架內使用多元的、稀疏的運動模型擬合原始運動軌跡，包括顯著點、模糊和剪切窗的約束。除了在二維或者三維運動模型上描述相機軌跡外，文獻［6］中使用特征點軌跡描述相機運動軌跡。該類方法首先抽取每幀圖像的特征點，關聯相鄰幀之間的特征點，建立特征點軌跡。優化的目標是平滑幀序列內每一條特征軌跡。文獻［7］通過添加、聯系、傳播和剪枝等步驟獲得特征軌跡，平滑軌跡則采用優化每一條特征軌跡的二次梯度的方法。這種方法的缺點在于建立特征軌跡和平滑軌跡都采用優化的方法，費時、魯棒性低，而且對每一條特征軌跡進行優化很多時候無解。文獻［8］通過頻域與空域處理相結合的方法能夠實時、高精度地穩定大運動偏移圖像序列，但是該方法仍難以很好地解決視頻中的低頻晃動問題。

本文吸取了二維和三維穩像算法的優點，提出了一種基于范數優化路徑的視頻穩像算法。通過特征點的匹配和概率進化抽樣一致性算法（probability evolution sample consensus，PESAC）剪枝構建二維運動模型，在定制化L1范數約束下獲取新的攝像機運動軌跡，并進行運動矯正，獲取穩定的視頻圖像序列。

1 特征點匹配

1．1 誤匹配點消除

通過匹配相鄰幀之間的尺度不變特征變換匹配（scale invariant feature transform，SIFT）算法來計算二維運動模型。首先利用SIFT算法［9－10］在尺度空間進行特征檢測，并確定特征點的位置和特征點所處的尺度，然后使用特征點鄰域梯度的主方向作為該特征點的方向特征，以獲取算子對尺度和方向的不變性。利用SIFT算法從圖像中提取出的特征可用于同一個物體或場景的可靠匹配，對圖像尺度和旋轉具有不變性，對光照變化、噪聲以及仿射變換都具有很好的魯棒性。區分SIFT特征點對的內點和外點一般采用隨機抽樣一致性（random sample consensus，RANSAC）算法［11－12］。RANSAC是一種根據樣本數據集合估算符合大部分樣本數據的數學模型的算法。該算法的主要思想是通過多次的采樣求解符合樣本的數學模型參數，從中選取最符合整個樣本數據集合的模型作為最佳模型，而符合最佳模型的樣本點認為是精確的樣本點（內點），不符合最佳模型的樣本點則認為是存在誤差的樣本點（外點）。在進行隨機采樣時有個隱含的假設：每次采樣時每個樣本被抽取的概率是相同的。

本文使用SIFT描述子生成的描述矢量進行匹配，經過粗匹配得到的匹配點對的距離可以作為其屬于內點的置信度。當點對距離很大時，其是內點的概率低；當點對距離很小時，其是內點的概率高。本文對兩對已知變換模型的待匹配圖像使用SIFT描述子進行特征描述，然后進行粗匹配，根據匹配點對的距離對點對排序，距離越小，序號越靠前。如圖1中內點概率曲線所示，橫軸為經過排序的匹配點對的數量，縱軸為內點存在的概率。

圖1 內點概率曲線

從圖1可以看到，一般地，匹配點對的距離越小，其是內點的概率就越高。因此本文提出了一種改進的RANSAC算法，稱之為PESAC算法，算法可以根據匹配點對的距離設置匹配點對的置信度。同時為了保證隨著迭代進行，距離大的內點被抽中的概率增加，距離小的外點被抽中的概率減小，使用每次迭代驗證中匹配點對與估計模型的誤差對匹配點對的抽取概率進行更新。

1．2 PESAC算法實現

步驟1 設置樣本初始的置信度τi為

式中，i＝1，2，…，n，n為樣本總數；Di為第i個匹配點對的距離；D′k為按從小到大排序后第k個距離。當k越小，距離小的樣本置信度越大；當k越大，樣本的置信度趨于平均。

步驟2 使用輪盤賭的方式抽取樣本，如圖2所示，抽取時生成0～1之間隨機數，隨機數落在的置信度區間所屬的樣本被抽中。置信度越高，抽中的概率越高。根據抽取樣本估計變換矩陣，計算樣本與變換矩陣的誤差erri，當erri≤β時則將該點統計為內點，反之則統計為外點，并根據新的內點更新最優矩陣。

圖2 輪盤賭抽樣

步驟3 更新樣本的抽取概率，特別地，被抽取樣本的概率不做更新：

步驟4 轉步驟2，直到滿足設置的迭代次數終止條件N。

設樣本中內點個數為nI；外點個數為no；當前內點被抽中概率為pI；當前外點被抽中概率為po；正確模型被內點檢驗時誤差為δ，被外點檢驗時誤差為T；錯誤模型被內點檢驗時誤差為e1，被外點檢驗時的誤差為e2。

當抽樣得出錯誤模型時，內點被抽取概率更新為

外點被抽取概率更新為

當抽樣得出正確模型時，內點被抽取概率更新為

外點被抽取概率更新為

因此隨著迭代次數增加，內點被抽取的概率逐漸增加，外點被抽取的概率逐漸減小。為了驗證PESAC算法的性能，分別用RANSAC算法和PESAC算法對使用的3對待配準圖像進行粗匹配點對提純，迭代總數為N＝500次實驗的平均值，其中β＝0．002為判斷內點和外點的門限值，如表1所示。

表1 PESAC算法和RANSAC算法迭代時間比較s

表1的數據顯示PESAC算法大大減少了迭代次數，相比RANSAC算法減少了60%左右。定義樣本置信度和更新樣本置信度，對PESAC算法的實時性起了很好的作用。

2 定制化L1范數最優化

規律的相機運動軌跡和平滑的運動軌跡過渡能直接帶來穩定的圖像效果。卡爾曼濾波或者高斯平滑雖然能夠去除相機運動軌跡中的毛刺，但是不能重新構建相機的運動軌跡，對于相機運動中的突變往往會帶來穩像誤差。本文采用四參數二維運動模型來表征相鄰幀圖像之間的變換關系，設第i幀和第i＋1幀圖像之間的變換矩陣為Mi，i＋1，則

式中，s為縮放因子；x和y分別表示水平和垂直方向的平移；θ表示旋轉角度。

分別定義四參數的相機運動軌跡S（i）、X（i）、Y（i）和Θ（i），表示從第1幀到第i幀的運動積累：

為了重新構建相機的運動軌跡，每一幀在4個參數上可分別添加一個矯正變量Δsi、Δxi、Δyi和Δθi。相機運動軌跡可由下面3種不同的獨立部分組成：

（1）固定軌跡，等同于固定相機的拍攝效果。使用一階前向差分P1作為優化標準

其中，pt為相機路徑，L1范數約束設為ei1，權重設為ω1。

（2）勻速軌跡，等同于架設在勻速的移動車上的相機拍攝效果。使用二階前向差分P2作為優化標準

L1范數約束設為ei2，權重設為ω2。

（3）勻加速軌跡，這一部分是固定軌跡和勻速軌跡的平滑轉換。使用三階前向差分P3作為優化標準

L1范數約束設為ei3，權重設為ω3。

后期根據新的相機軌跡進行圖像矯正時，矯正變量越大，每一幀圖像損失邊角面積越大，穩像后的視頻視野越小。因此對矯正變量本身也需要進行最小化，L1范數約束設為ei4，權重設為ω4。

本文在原L1范數最優化方法［13－14］的基礎上，加上了定制化的權重設計，削弱旋轉角度的影響，被稱之為L1范數定制化，如式（5）所示。對不同軌跡下四參數模型分別設置L1范數約束eikx，eiky，eiks，eikθ和其相應權重ωikx，ωiky，ωiks，ωikθ。其中，i表示幀號，k的值從1～4分別表示固定軌跡、勻速軌跡、勻加速軌跡和矯正變量參數軌跡。通過離散化的權重設置削弱了旋轉和縮放因子在四參數運動模型中的影響，有利于最優運動路徑的平滑。此時，其原優化問題變為

對不同L1范數約束的權重做了多組實驗，圖3是幾種不同權重組合優化前后的路徑曲線效果圖，曲線橫坐標表示視頻序列在不同時刻的幀數，縱坐標為二維運動模型不同的路徑參數，其中x為水平方向的位移，y為垂直方向的位移，s為縮放因子，θ表示旋轉角度，x＿op，y＿op，s＿op，θ＿op分別為其相應的最優化路徑。

圖3 最優路徑權重優化

圖3中的最優路徑權重優化表明加大某一個L1范數的約束權重，最后的優化路徑便更多顯示出相應路徑的特性。權重的大小并不是決定優化結果的直接原因，不同運動之間的權重比例決定了所構建的相機路徑的準確性。通過圖3中不同實驗參數的對比，權重比例的選擇基于不同的數量級對路徑優化更有意義。由于本文的算法針對的是運動相機中視頻的隨機抖動和低頻晃動問題，對于相機旋轉只在一定范圍內考慮，假設旋轉角度參數可有效估計的幀間旋轉角度一般不超過10°，因此當ω1∶ω2∶ω3∶ω4＝100∶10∶10∶1，優化后路徑是由多條直線加上平滑的曲線過渡而成，模擬了固定相機的拍攝效果。采用ω1∶ω2∶ω3∶ω4＝10∶10∶10∶1則兼顧了3種拍攝效果，從圖3可以看出ω1∶ω2∶ω3∶ω4＝10∶10∶10∶1具有更好的平滑效果，能更好地表示相機的實際運動路徑，因此在式（5）中的eikx，eiky，eiks取ω1∶ω2∶ω3∶ω4＝10∶10∶10∶1的權重系數比。另外對四參數采用相同的L1范數約束權重會產生不好的視覺體驗。原因在于拍攝過程中由于抖動產生的旋轉體現在四參數的旋轉角度路徑中，達到拍攝要求的視頻是不會產生頻繁的左右旋轉，而是平穩地隨視角推進。為了減小旋轉角度的影響，則可增大固定軌跡中相應的旋轉角度權重，本文將旋轉角度eikθ權重設置為ω1θ∶ω2θ∶ω3θ∶ω4θ＝100∶10∶10∶1，則可得到最終的定制化L1范數最優化效果，如圖4所示。

圖4 最優化權重路徑

3 實驗結果及分析

假定運動相機不穩定導致的幀間縮放比例不超過30%，旋轉角度不超過10°。圖5給出了對分辨率為640像素×360像素的視頻序列1進行穩像處理前后的比較，該視頻中幀間不僅存在全局運動，還存在著相機拍攝時的在水平和垂直方向的小幅度隨機抖動，其中圖5（a）、圖5（c）、圖5（e）為原始視頻中第200幀至第202幀，圖5（b）、圖5（d）、圖5（f）為穩定視頻中同時刻圖像。由圖5（g）、圖5（h）中序列差圖像可以看出，穩定視頻能夠去除抖動，水平和垂直方向上可估計出的平移量可達50個像素，保持補償后圖像與基準圖像具有較好的相似度，實現視頻的穩定輸出。

圖5 視頻序列1穩像效果

圖6是經圖像矯正補償后的穩像效果，圖7為視頻序列2中本文方法的連續幀穩像精度與文獻［4］和文獻［5］的方法進行的定量比較結果，可以看出本文提出的算法與文獻［4］和文獻［5］的方法在穩像效果上相當。

圖6 視頻序列2穩像效果對比

圖7 視頻序列2穩像精度對比

圖8中本文方法與基于特征匹配的穩像算法進行了比較，左列為特征匹配算法效果，右列為本文算法效果，可以看出本文提出的算法在穩像效果上優于特征匹配的方法。

圖8 本文方法與特征匹配穩像算法對比

定制化參數使得L1范數最優化發揮了更好的效果，去除了視頻拍攝過程中視角左右旋轉的不穩定因素，實驗證明本文提出的穩像算法可以解決視頻抖動中的平移、旋轉和縮放所帶來的影響，且基本不會引起視覺失真，從而保證整個視頻序列的完整流暢。另外本文利用峰值信噪比（peak signal to noise ratio，PSNR）值作為評價準確度的品質因子，PSNR值越大，說明穩定后圖像幀間灰度偏差量越小，圖像穩定效果越好。其定義如下：

其中

均方誤差（mean square error，MSE）是圖像fk和fk－1間像素值的均方誤值，反映了兩幅圖像的差異大小。兩圖像的相似度越高，則MSE值就越小，其PSNR值就越高。圖9給出了原始視頻序列1中連續30幀的幀間逼真度PSNR和不同算法穩像后序列的PSNR的比較結果，穩定序列的幀間逼真度有了很大的提高，說明穩定后的圖像序列幀間灰度偏差量變小，達到了一定程度的穩定效果。由圖9中PSNR可以看出，本文提出的算法與文獻［4］和文獻［5］的方法在穩像效果上相當，而優于基于特征匹配的方法，但是文獻［4］的方法需要預先計算特征點，文獻［5］的方法在針對非剛性目標的最優化路徑求取過程中易產生不穩定，另外本文的方法在時間性能上優于前兩種方法。

圖9 原始序列與穩像后序列的PSNR比較

由于無法獲得實際拍攝視頻的準確運動補償向量，通常使用輸出視頻的幀間保真度［15］（interframe transformation fidelity，ITF）作為總體評價指標來衡量算法的穩像效果。其定義如下：

表2為不同算法幀間保真度的比較，從表中不同算法的幀間保真度也可以看出本文算法優于基于特征匹配的穩像方法，并且與文獻［4］和文獻［5］的算法相當，從而驗證了本文算法的有效性。

表2 不同算法幀間保真度比較

4 結 論

本文提出了一種基于范數優化路徑的視頻穩像算法。求取相鄰幀變換關系時，本文提出的PESAC算法顯著地減少了抽樣迭代次數，減少了計算時間，使得本文的算法能夠達到實時應用的要求。定制化使得L1范數最優化發揮了更好的效果，去除了視頻拍攝過程中視角左右旋轉的不穩定因素，實驗證明本文提出的穩像算法可以解決視頻抖動中的平移、旋轉和縮放所帶來的影響，穩像的畫面自然，沒有明顯失真和像素不連續情況。

［1］Xu L D，Lin X G．Global motion estimation for video stabilization［J］．Journal of Tsinghua University（Science and Technology），2007，47（1）：92－95．（徐理東，林行剛．視頻抖動矯正中全局運動參數的估計［J］．清華大學學報（自然科學版），2007，47（1）：92－95．）

［2］Davision A J，Reid I D，Molton N D，et al．MonoSLAM：realtime single camera SLAM［J］．IEEE Trans．on Pattern Analysis and Machine Intelligence，2007，26（6）：1052－1067．

［3］Gleicher M L，Liu F．Re－cinematography：improving the camera work of causal video［J］．ACM Trans．on Multimedia，Computing Communications and Applications，2008，5（1）：1－28．

［4］Liu F，Glercher M，Wang H，et al．Subspace video stabilization［J］．ACM Trans．on Graphics，2011，30（1）：1－10．

［5］Grundmann M，Kwatra V，Essa I．Auto－directed video stabilization with robust L1optimal camera paths［C］∥Proc．of the Computer Vision and Pattern Recognition，2011：225－232．

［6］Lee K Y，Chuang Y Y，Chen B Y，et al．Video stabilization using robust feature trajectories［C］∥Proc．of the IEEE Conference on Computer Vision，2009：1397－1404．

［7］Liu F，Gleicher M，Jin H L，et al．Content preserving warps for 3Dvideo stabilization［J］．ACM Trans．on Graphics，2009，44：1－9．

［8］Liu Z L，Liu F，Zhu Z F．Image stabilization algorithm based on processing in frequency－space domain for large motion offset and its real time implementation［J］．Systems Engineering and Electronics，2012，34（12）：2423－2427．（劉忠領，劉峰，朱振福．頻域與空域處理相結合的大運動偏移穩像算法及其實時實現［J］．系統工程與電子技術，2012，34（12）：2423－2427．）

［9］Rafael C G，Richard E W．Digital image processing［M］．2nd ed．Ruan Q Q，Ruan Y Z，trans．Beijing：Publishing House of Electronics Industry，2004．（Rafael C G，Richard E W．數字圖像處理［M］．2版．阮秋琦，阮宇智，譯．北京：電子工業出版社，2004．）

［10］Lowe D G．Distinctive image features from scale－invariant key points［J］．International Journal of Computer Vision，2004，60（2）：91－110．

［11］Shi J，Tomasi C．Good features to track［C］∥Proc．of the Computer Vision and Pattern Recognition，1994：593－600．

［12］Fisher M A，Bolles R C．Random sample consensus：aparadigm for model fitting with applications to image analysis and automated cartography［J］．Communications of the ACM，1981，24（6）：381－395．

［13］Xie Z，Li J P．Nonlinear optimization［M］．Changsha：National University of Defense Technology Press，2003．（謝政，李建平．非線性最優化［M］．長沙：國防科技大學出版社，2003）

［14］Kim S J，Koh K，Boyd S，et al．L1trend filtering［J］．SIAM Review，2009，51（2）：339－360．

［15］Mercenaro L，Vernazza G，Regazzoni C S．Image stabilization algorithms for video－surveillance applications［C］∥Proc．of the IEEE International Conference of Image Processing，2001：349－352．

E－mail：13810311626＠126．com

楊文佳（1983－），男，高級工程師，博士，主要研究方向為光電信號處理、模式識別。

E－mail：ywjowen＠163．com

黃培康（1935－），男，院士，博士研究生導師，主要研究方向為雷達目標特性、微波遙感。

E－mail：peikanghuang＠vip．sina．com

Video stabilization algorithm based on norm optimal paths

SHI Chun－lei1，2，YANG Wen－jia2，HUANG Pei－kang3
（1．Science and Technology on Optical Radiation Laboratory，Beijing 100854，China；2．Beijing Institute of Environmental Features，Beijing 100854，China；3．Science and Technology on Electromagnetic Scattering Laboratory，Beijing 100854，China）

To deal with the problem of random shakiness and low frequency bounces，an improved video stabilization method based on norm optimal camera paths is proposed．Probability evolution sample consensus algorithm is used to eliminate the error matching points after coarse matching of feature points，avoiding the interference of local motion．Then camera paths are gained by L1norm optimization．Finally，image warp is computed to get stabilized video sequences．Experimental results for different video sequences show the proposed method has a better veracity of stabilized results．

video stabilization；probability evolution sample；L1norm optimization；camera moving paths

TP 391．41

A

10．3969／j．issn．1001－506X．2015．06．28

石春雷（1975－），男，研究員，博士研究生，主要研究方向為光電信號處理、目標檢測與跟蹤。

1001－506X（2015）06－1411－06

2014－11－15；

2015－03－29；網絡優先出版日期：2015－05－04。

網絡優先出版地址：http：／／www．cnki．net／kcms／detail／11．2422．TN．20150504．0941．005．html