光流算法研究

张 拯，贾鹤萍

（1.太原理工大学材料科学与工程学院，太原 030024；2.山西大学物理电子工程学院，太原 030006）

光流算法研究

张 拯1，贾鹤萍2

（1.太原理工大学材料科学与工程学院，太原 030024；2.山西大学物理电子工程学院，太原 030006）

光流的测量是视频序列处理和视频挖掘中的基本问题。首先简述了光流法的基本原理，即物体亮度不变特性；然后阐述了计算光流的4类算法：微分方法、区域匹配方法、基于能量的方法和基于相位的方法，并对当前主流的能量算法进行了详细探讨；最后对各种光流算法的评测方法与测试集进行了说明。

光流法，运动检测，能量法，视频挖掘

0 引言

光流是指空间运动物体在观测成像面上的像素运动的瞬时速度。光流的测量是视频序列处理和视频挖掘中的基本问题，它主要用于运动物体检测、识别与跟踪等。光流的思想最早由Gibson在1950年提出，而对光流的计算，则源于Horn、Schunck［1］和 Lucas、Kanade［2］等人的研究。但Horn-Schunck和Lucas-Kanade算法局限性较大，抗噪能力不强，因此，作为一个被广泛关注的研究领域，几十年来一直有改进算法和新算法出现。

1 光流法基本原理

光流法的基本原理是物体亮度的不变特性，即对于空间移动物体上的一个点，在时间序列的不同时刻上，该点的亮度是不变的。对于一个二维的图像，可以用表示图像上坐标为的点在t时刻的亮度值。在t时刻，空间中移动的物体上有一点，经过一段时间δt，该点在图像平面上位移到了，根据亮度不变特性可以得到：

利用泰勒展开式可以得到：

由泰勒公式知，高阶微量ε是趋向于0的，于是有：

即有

可以简化写成

式中，Ix、Iy表示图像平面相对x、y轴方向的强度变化，It表示同一个像素点在相邻时刻（连续图像上同一个像素点）的强度变化

2 光流算法

光流的计算方法大多数是建立在Horn-Schunck算法和Lucas-Kanade算法基础之上，其基本假设一般为：亮度不变和图像全局平滑。改进算法的研究主要集中在如何削弱以上假设以及提高算法的抗噪性。按照Barron［4］在1994年提出的分类方法，光流算法可以分为微分方法、区域匹配方法、基于能量的方法和基于相位的方法等4类。

2.1 微分方法

微分方法是利用视频序列中图像灰度（或其滤波形式）的时空微分，计算像素瞬时速度的方法。其典型代表是Horn-Schunck算法，它结合亮度不变假设和图像全局平滑假设，估算光流场

基于此思想，一些改进算法不断提出：Nagel［7］采用有条件的平滑约束，通过约束条件构造加权矩阵，利用加权矩阵的控制对梯度进行不同平滑处理；Black 和 Anandan［8］针对多运动的估计问题，提出了分段平滑的计算方法。Lucas-Kanade算法则是假设在一个很小的临近范围内光流为常数，由此通过最小二乘法解出超正定方程组的解。Jodoin［9］提出了一个忽略边缘的算法，利用最小二乘法计算出了一个小运动区域，可以证明该区域是多峰区域，合理地处理了锐利边缘的情况。Bruhn［10］等提出将Horn-Schunck算法中的全局方法与Lucas-Kanade算法中的局部方法结合起来，即将全局方法中的稠密光流和局部方法的鲁棒性结合起来。

微分方法大多根据亮度不变和平滑假设得出光流方程，因此，比较容易受到光照的影响，抗噪能力不足，此外还存在相关参数的选取比较困难等问题。

2.2 区域匹配方法

在区域匹配方法中，光流被定义为不同时刻图像区域之间所产生最佳拟合的位移。区域匹配则是通过诸如 SSD（Sum-of-Squared Difference）、互信息或相关系数等相似度测量的最大化，实现区域的最优匹配。

Singh［11］提出了一种两步骤的区域匹配方法。第1步对视频中相邻的3张通过带通滤波处理 过 的图像 I-1、I0、I1进行 SSD 计 算；然后将转换到概率分布。光流可被估算为该分布的均值。Anandan［12］提出的方法是基于拉普拉斯金字塔和由粗到细的SSD匹配策略。

在基于区域匹配的方法中，如何选择区域问题，目前尚无明确的标准；而计算的复杂度也和选取区域的大小有关；由于SSD是单峰的，选取区域的大小还会影响最终的估计效果。

2.3 基于能量的方法

基于能量的方法是目前光流计算的主流算法。其基本思路是将光流计算转化为一个全局能量函数在一系列约束条件下的最优化问题。通常还会采用罚函数法将有约束的优化问题进一步转化为无约束的优化问题。

能量函数一般表达式为：

其中，EData为数据项，用于表征输入图像中光流的不变性，如亮度不变、梯度不变等。由于EData中约束条件较少，故需要增加其他先验的约束条件才可以解出。故式（3）中引入先验项EPrior。一般而言，EPrior为平滑约束。基于能量方法的研究，实质上就是围绕EData、EPrior的选取与能量函数的最优化进行，以下分别阐述之。

2.3.1 数据项选择

数据项定义了各种不变性的假设：亮度不变、梯度不变、Hessian矩阵不变、梯度范数不变、Hessian范数不变、Hessian行列式不变等［13］。此外，部分文献［14-15］提出时空信号（即图像）在时间t和t+1是高度相关的，由此来定义数据项的不变约束［16］。Xiang［17］等则将图像LUV色彩信息与亮度不变约束结合起来，以加权邻域最小二乘法求解光流，同时利用LUV中的U和V来确定加权系数。

最常用的光流计算的不变性为亮度不变假设和梯度不变假设。其中，亮度不变假设是指像素在画面中移动时，其强度或颜色保持不变，即其约束方程为式（2）。

亮度不变假设容易受到光照的影响，但是光照的变化只会改变光流梯度的大小，而不会改变光流梯度的方向。基于此，可以根据光流梯度方向的不变性，给出如下的约束条件：

各种不变性假设均有其优点与局限性，因此，Papenberg［13］等对多种不变性的线性组合进行研究。

不变性假设是针对各个像素点定义的，由此也在像素点上引入误差。因此，数据项的定义需要将各个像素点的误差叠加起来。在Horn-Schunck算法中，数据项采用2范数定义为：

但采用2范数隐含了误差呈高斯分布的假设，这一点在实际中未必成立。Black［8］等提出一种基于鲁棒估计，他使用具有鲁棒性的罚函数的算法。在各类罚函数中，当前被广泛接受的是［18-21］采用1范数或其变体：

式中，E为误差Ex，y的向量，ε为一个小的正数，可以取为一个固定的值。

根据处理思想的不同，式（5）可以变换出很多其他的罚函数方程。如Brox［18］等认为二次的罚函数对最后的估计结果影响较大，提出了凹函数作为罚函数，具体的数据项能量函数为

主要试验如下：①膨胀试验，包括自由膨胀和限制膨胀试验；②压汞试验，通过计算汞压入量间接确定孔隙的孔径大小，适合干燥试样；③核磁共振试验，通过核磁共振技术测定含水状态下的孔隙分布，测试原理见参考文献[13]；④XRD试验，通过XRD方法确定晶体矿物；⑤SEM试验，观察试样的微观形貌。

2.3.2 先验项选择

一个最简单的先验项就是依据光流场中的一阶微分来计算。例如Horn-Schunck算法中就是利用2范数表示先验项：

先验项的罚函数构造方法与数据项类似。Black［22］假设光流场中梯度遵循高斯独立同分布，采用了二阶范数作为罚函数；当前更为被广泛接受的是一阶范数，如 Brox［18］、Wedel［19］等就采用了一阶范数。

在确定罚函数后，一般是对每个导数各自使用罚函数，然后将其相加；或先将梯度的平方或绝对值相加，然后对其使用罚函数。

对罚函数赋予空间各异和各向异性权重是先验项细化的常用手段。例如在Horn-Schunck算法中对罚函数赋予空间各异的权重：

式中，权重函数具体值和该点亮度有关，这样在图像边缘处，其亮度值较低，权重也低，而边缘处一般最容易受到噪声的影响，这样通过权重函数便可以降低对图像全局平滑的要求。

此外，在先验项中，除了一阶微分外，高阶微分可能会带来更精确的运动估计。如Trobin［26］引入二阶微分，采用圆谐函数将二阶微分算子变换到一个正交空间，在此基础上对能量进行优化。与此相关的，过参数化（Over-parameterized）在光流计算中也得到了应用，如 Nir［27］等。

2.3.3 最优化

最优化算法可分为连续优化与离散优化两大类。常见的连续优化算法有梯度下降算法和变分法等。梯度下降算法中以梯度函数作为衡量计算精确度的标准，如果迭代使得梯度函数下降，那么计算结果就更加精确。为了达到一定的精确度，可以通过设定一个阈值，作为迭代终止的条件。例如Baker［28］介绍了高斯牛顿法、牛顿法和Levenberg-Marquardt等。

最为常用的连续优化算法为变分法［1，10，18，25，27］，即假设全局能量函数可写为如下形式：

除了以上介绍的两种主要算法，其他文献也提出了一些独特的方法。如Wedel［19］采取了分步优化的策略：

而对于离散优化，一般采用的方法有融合方法［26，29-30］和稀疏状态空间动态重参数化方法［31-32］。在采用离散优化后，还可以继续采用连续优化来进一步精细结果。

一些其他的处理思路也值得借鉴。Xu［33］给出了一个鲁棒的全变差方法，这种算法不要求光流场是全局平滑的，并且允许光照的变化，它能够有效地克服噪声的影响。Figueira［34］利用光流法从人机混合环境中分析出人物，改进了以前的光流法，提出一种标准化光流向量，根据现实生活中人的动作在图像中的映射关系，另外通过对目标在空间域上的位移来进行时间采样，从而克服了噪声的影响，保持了系统的稳定性。

2.4 基于相位的方法

Fleet［35］提出了利用相位信息来计算光流。光流可以从带通滤波器输出的相位特性来确定，因此，被称为相位法。相位模型实际上是将问题转化到频域上研究。光流的分速度为垂直与带通速度滤波器输出中的等相位轮廓瞬时运动，带通速度滤波器按照尺度、速度和方向分离输入信号。带通速度滤波器的输出为：为输出信号的幅值，为输出的信号的相位。

相位方法有一定的复杂度，同时，虽然带通滤波器输出的相位分量比幅值分量更稳定，但在相位奇点的邻域内，也可能不稳定。此外，相位方法对图像序列中的时间混叠比较敏感。

2.5 其他方法与实现技术

除了以上提到的主要方法，还有一些其他的解决思路。如Fay［36］等模拟视网膜中时空处理和大脑视觉运动，基于并联动力学提出一个多层神经网络用于提取画面边缘的法向速度；Tagliasacchi［37］提出利用进化计算进行光流估算；Seitz［38］则将光流计算转变为寻找一张图像到另一张图像的时空线性滤波，通过对亮度、模糊以及其他外观变化，建模为不同的滤波器，采用线性规划对此进行全局优化。

3 光流法性能比较

光流法性能评测的规范化与标准化最早由Barron［4］等人在1994年提出，共针对9种算法及其变体以及不同的参数进行了评测，评测采用的测试集包括已知运动场的人造视频序列和真实的视频场景，评测标准为角度差（AE），统计量为均值与标准差。此后，2007 年，Baker［6］等设计了新的测试数据库，对近年来出现的几十种主要光流算法进行了评测，其评测标准增加了光流终点差（EE）以及归一化插值误差（NE），在统计量上增加了对鲁棒性的重视和基于百分比的精确度，并通过遮罩对图像中感兴趣区域的误差进行测量与统计。其测试结果在互联网上（http：//vision.middlebury.edu/flow/data/）公布。此后，很多关于光流法的论文都将Middlebury测试集作为标准并将测试结果提交更新。目前，已有超过50种光流算法的具体实现参与了评测。

［1］HORN B K P，SCHUNCK B G.Determining optical flow［J］.Artificial intelligence，1981，17（1-3）：185-203.

［2］LUCAS B D，KANADE T.An iterative image registration technique with an application to stereo vision［C］//IJCAI'81 Proceedings of the 7th international joint conference on Artificial intelligence.Citeseer，1981：674-679

［3］AGGARWAL J，NANDHAKUMAR N.On the computation of motion from sequences of images-a review［J］.Proceedings of the IEEE，1988，76（8）：917-935.

［4］BARRON J L，FLEET D，BEAUCHEMIN S.Performance of optical flow techniques［J］.International Journal of Computer Vision，1994，12（1）：43-77.

［5］STILLER C，KONRAD J.Estimating motion in image sequences［J］.IEEE Signal Processing Magazine，1999，16（4）：70-91.

［6］BAKER S，ROTH S，SCHARSTEIN D，et al.A database and evaluation methodology for optical flow［C］//2007 IEEE 11th International Conference on Computer Vision，2007：

［7］NAGEL H H.On the estimation of optical flow：Relations between different approaches and some new results［J］.Artificial intelligence，1987，33（3）：299-324.

［8］BLACK M J，ANANDAN P.The robust estimation of multiple motions：Parametric and piecewise-smooth flow fields［J］.Computer Vision and Image Understanding，1996，63（1）：75-104.

［9］JODOIN P M，MIGNOTTE M.Optical-flow based on anedge-avoidance procedure［J］.Computer Vision and Image Understanding，2009，113（4）：511-531.

［10］BRUHN A，WEICKERT J，SCHN C，et al.Lucas/Kanade meets Horn/Schunck：Combining local and global optic flow methods ［J］.International Journal of Computer Vision，2005，61（3）：211-231.

［11］SINGH A.An estimation-theoretic framework for image-flow computation［C］//Computer Vision，1990.Proceedings， Third InternationalConference on，1989：168-177.

［12］ANANDAN P.A computational framework and an algorithm for the measurement of visual motion ［J］.International Journal of Computer Vision，1989，2（3）：283-310.

［13］PAPENBERG N，BRUHN A，BROX T，et al.Highly accurate optic flow computation with theoretically justified warping［J］.International Journal of Computer Vision，2006，67（2）：141-158.

［14］BURT P J，YEN C，XU X.Local correlation measures for motion analysis：a comparative study［C］//IEEE CPRIP，1982：274.

［15］PRATT W K.Correlation techniques of image registration［J］.Aerospace and Electronic Systems，IEEE Transactions on，1974（3）：353-358.

［16］SUN C.Fast optical flow using cross correlation and shortest-path techniques［C］//Proceedings of Digital Image Computing：Techniques and Applications，1999：143-148.

［17］XIANG X，PENG Y，ZHANG L.A method of optical flow computation based on LUV color space［C］//Test and Measurement，2009.ICTM'09.International Conference on，IEEE，2009：378-381.

［18］BROX T，BRUHN A，PAPENBERG N.et al.High accuracy optical flow estimation based on a theory for warping［C］//Computer Vision-ECCV 2004，2004：25-36.

［19］WEDEL A，POCK T，BRAUN J，U.et al.Duality TV-L1 flow with fundamental matrix prior［C］//Image and Vision Computing New Zealand，2008.IVCNZ 2008.23rd International Conference，2008：1-6.

［20］WEDEL A，POCK T，ZACH C，et al.An improved algorithm for TV-L 1 optical flow［J］.Statistical and GeometricalApproaches to VisualMotion Analysis， 2009，5064/2008：23-45.

［21］ZACH C，POCK T，BISCHOF H.A duality based approach for realtime TV-L 1 optical flow［C］//Proceedings of the 29th DAGMconferenceon Pattern recognition，2007：214-223.

［22］BLACK M J，ANANDAN P.Robust dynamic motion estimation over time［C］//Computer Vision and Pattern Recognition，1991.Proceedings CVPR'91.，IEEE Computer Society Conference on，1991：296-302.

［23］WERLBERGER M，TROBIN W，POCK T，et al.Anisotropic Huber-L1 optical flow［C］//Proceedings of the British machine vision conference，2009.

［24］SUN D，ROTH S，LEWIS J，et al.Learning optical flow［J］.Computer Vision-ECCV 2008，2008，5304/2008：83-97.

［25］ZIMMER H，BRUHN A，WEICKERT J，et al.Complementary optic flow［Z］.International Conference on Energy Minimization Methods in Computer Vision& Pattern Recognition，2009.

［26］TROBIN W，POCK T，CREMERS D.et al.An unbiased second-order prior for high-accuracy motion estimation［J］.Pattern Recognition，2008：396-405.

［27］NIR T，BRUCKSTEIN A M，KIMMEL R.Over-parameterized variational optical flow ［J］.International Journal of Computer Vision，2008，76（2）：205-216.

［28］BAKER S，MATTHEWS I.Lucas-kanade 20 years on：a unifying framework ［J］.International Journal of Computer Vision，2004，56（3）：221-255.

［29］JUNG H，LEE K，LEE S.Toward global minimum through combined local minima［J］.Computer Vision– ECCV 2008，2008：298-311.

［30］LEMPITSKY V，ROTH S，DARMSTADT T，et al.Fusion-Flow：discrete-continuous optimization for optical flow estimation［C］//Proceedings of the IEEE conference on computer vision and pattern recognition，2008.

［31］GLOCKER B，PARAGIOS N，KOMODAKIS N，G.et al.Optical flow estimation with uncertainties through dynamic MRFs［C］//2008 IEEE Conference on Computer Vision and Pattern Recognition，2008：1-8.

［32］LEI C，YANG Y H.Optical flow estimation on coarse-to-fine region-trees using discrete optimization ［C］//Computer Vision，2009 IEEE 12th International Conference on，2009：1562-1569.

［33］XU L，CHEN J，JIA J.A segmentation based variational model for accurate optical flow estimation［C］//Proceedings of the European conference on computer vision，2008：671-684.

［34］FIGUEIRA D，MORENO P，BERNARDINO A，et al.Optical flow based detection in mixed human robot environments［J］.Advances in Visual Computing，2009：223-232.

［35］FLEET D J，JEPSON A D.Computation of component image velocity from local phase information ［J］.International Journal of Computer Vision，1990，5（1）：77-104.

［36］FAY D，WAXMAN A.Real-time early vision neurocomputing［C］//Neural Networks，1991.，IJCNN-91-Seattle International Joint Conference on，IEEE，1991：621-626.

［37］TAGLIASACCHI M.A genetic algorithm for optical flow estimation［J］.Image and Vision Computing，2007，25（2）：141-147.

［38］SEITZSM，BAKERS.Filterflow［C］//ComputerVision，2009 IEEE12thInternationalConferenceon，2009：143-150.

A Survey on Optical Flow Algorithms

ZHANG Zheng1，JIA He-ping2
（1.College of Materials Science and Engineering,Taiyuan University of Technology，Taiyuan 030024，China；2.College of Physics and Electronic Engineering,Shanxi University，Taiyuan 030006，China）

The mearsurement of optical flow is the fundamental issue of image sequence processing and video mining.In this paper，the principle of optical flow method is introduced first.Four main catalogues of optical flow algorithms，including the differential technique，region-based matching，energy-based method and phase-based method，are disscussed in detail，especially the commonly used energy-based method.The evaluation methods and collection of optical flow methods are also introduced in this paper.

optical flow，motion detection，energy-based method，video mining

TP391

A

10.3969/j.issn.1002-0640.2017.07.023

1002-0640（2017）07-0105-05

2016-05-05

2016-07-08

张 拯（1970- ），男，山西浑源人，工程师。研究方向：光流算法在材料工业中的应用及电化学储能器件。