基于范数优化路径的视频稳像算法

石春雷，杨文佳，黄培康

（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