光流算法研究

收稿日期：2016-05-05修回日期：2016-07-08作者简介：张拯（1970-），男，山西浑源人，工程师。研究方向：光流算法在材料工业中的应用及电化学储能器件。摘要：光流的测量是视频序列处理和视频挖掘中的基本问题。首先简述了光流法的基本原理，即物体亮度不变特性；然后阐述了计算光流的4类算法：微分方法、区域匹配方法、基于能量的方法和基于相位的方法，并对当前主流的能量算法进行了详细探讨；最后对各种光流算法的评测方法与测试集进行了说明。关键词：光流法，运动检测，能量法，视频挖掘中图分类号：TP391文献标识码：ADOI：10.3969/j.issn.1002-0640.2017.07.023光流算法研究张拯1，贾鹤萍2（1.太原理工大学材料科学与工程学院，太原030024；2.山西大学物理电子工程学院，太原030006）ASurveyonOpticalFlowAlgorithmsZHANGZheng1，JIAHe-ping2（1.CollegeofMaterialsScienceandEngineering,TaiyuanUniversityofTechnology，Taiyuan030024，China；2.CollegeofPhysicsandElectronicEngineering,ShanxiUniversity，Taiyuan030006，China）Abstract：Themearsurementofopticalflowisthefundamentalissueofimagesequenceprocessingandvideomining.Inthispaper，theprincipleofopticalflowmethodisintroducedfirst.Fourmaincataloguesofopticalflowalgorithms，includingthedifferentialtechnique，region-basedmatching，energy-basedmethodandphase-basedmethod，aredisscussedindetail，especiallythecommonlyusedenergy-basedmethod.Theevaluationmethodsandcollectionofopticalflowmethodsarealsointroducedinthispaper.Keywords：opticalflow，motiondetection，energy-basedmethod，videomining0引言光流是指空间运动物体在观测成像面上的像素运动的瞬时速度。光流的测量是视频序列处理和视频挖掘中的基本问题，它主要用于运动物体检测、识别与跟踪等。光流的思想最早由Gibson在1950年提出，而对光流的计算，则源于Horn、Schunck［1］和Lucas、Kanade［2］等人的研究。但Horn-Schunck和Lucas-Kanade算法局限性较大，抗噪能力不强，因此，作为一个被广泛关注的研究领域，几十年来一直有改进算法和新算法出现。1光流法基本原理光流法的基本原理是物体亮度的不变特性，即对于空间移动物体上的一个点，在时间序列的不同时刻上，该点的亮度是不变的。对于一个二维的图像，可以用表示图像上坐标为的点在t时刻的亮度值。在t时刻，空间中移动的物体上有一点，经过一段时间啄t，该点在图像平面上位移到了，根据亮度不变特性可以得到：（1）利用泰勒展开式可以得到：由泰勒公式知，高阶微量着是趋向于0的，于是有：文章编号：1002-0640（2017）07-0105-05Vol.42，No.7Jul，2017火力与指挥控制FireControl&CommandControl第42卷第7期2017年7月105··（总第42-）火力与指挥控制2017年第7期即有可以简化写成（2）式中，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-SquaredDifference）、互信息或相关系数等相似度测量的最大化，实现区域的最优匹配。Singh［11］提出了一种两步骤的区域匹配方法。第1步对视频中相邻的3张通过带通滤波处理过的图像I-1、I0、I1进行SSD计算；然后将转换到概率分布。光流可被估算为该分布的均值。Anandan［12］提出的方法是基于拉普拉斯金字塔和由粗到细的SSD匹配策略。在基于区域匹配的方法中，如何选择区域问题，目前尚无明确的标准；而计算的复杂度也和选取区域的大小有关；由于SSD是单峰的，选取区域的大小还会影响最终的估计效果。2.3基于能量的方法基于能量的方法是目前光流计算的主流算法。其基本思路是将光流计算转化为一个全局能量函数在一系列约束条件下的最优化问题。通常还会采用罚函数法将有约束的优化问题进一步转化为无约束的优化问题。能量函数一般表达式为：（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）。亮度不变假设容易受到光照的影响，但是光照的变化只会改变光流梯度的大小，而不会改变光流梯度的方向。基于此，可以根据光流梯度方向的不变性，给出如下的约束条件：（4）106··1216（总第42-）各种不变性假设均有其优点与局限性，因此，Papenberg［13］等对多种不变性的线性组合进行研究。不变性假设是针对各个像素点定义的，由此也在像素点上引入误差。因此，数据项的定义需要将各个像素点的误差叠加起来。在Horn-Schunck算法中，数据项采用2范数定义为：但采用2范数隐含了误差呈高斯分布的假设，这一点在实际中未必成立。Black［8］等提出一种基于鲁棒估计，他使用具有鲁棒性的罚函数的算法。在各类罚函数中，当前被广泛接受的是［18-21］采用1范数或其变体：（5）式中，E为误差Ex，y的向量，着为一个小的正数，可以取为一个固定的值。根据处理思想的不同，式（5）可以变换出很多其他的罚函数方程。如Brox［18］等认为二次的罚函数对最后的估计结果影响较大，提出了凹函数作为罚函数，具体的数据项能量函数为式中，r为权重。对于罚函数，由于着为固定值，同时罚函数中没有添加其他额外的参数，所以很方便求出能量的最小值。Wedel［19］等提出用线性的罚函数代替Horn-Schunck算法中的二次函数。设光流为，则能量函数定义为i为p1，p2的权重。罚函数是一个线性表达式，这样造成的误差必然小于二次函数。2.3.2先验项选择一个最简单的先验项就是依据光流场中的一阶微分来计算。例如Horn-Schunck算法中就是利用2范数表示先验项：先验项的罚函数构造方法与数据项类似。Black［22］假设光流场中梯度遵循高斯独立同分布，采用了二阶范数作为罚函数；当前更为被广泛接受的是一阶范数，如Brox［18］、Wedel［19］等就采用了一阶范数。在确定罚函数后，一般是对每个导数各自使用罚函数，然后将其相加；或先将梯度的平方或绝对值相加，然后对其使用罚函数。对罚函数赋予空间各异和各向异性权重是先验项细化的常用手段。例如在Horn-Schunck算法中对罚函数赋予空间各异的权重：式中，权重函数具体值和该点亮度有关，这样在图像边缘处，其亮度值较低，权重也低，而边缘处一般最容易受到噪声的影响，这样通过权重函数便可以降低对图像全局平滑的要求。修正过的先验项，降低了对图像全局光滑的依赖性，但各向异性的权重函数有可能取得更高的精度。如Werlberger［23］提出的基于各向异性的Huber范数的光流计算方法，其权重分配在沿光流梯度方向小于其垂直方向；Sun［24］则通过可控随机场的学习来定义权重；Zimmer［25］在其提出的互补光流法（ComplementaryOpticalFlow，COF）中，也采用了各向异性权重。此外，在先验项中，除了一阶微分外，高阶微分可能会带来更精确的运动估计。如Trobin［26］引入二阶微分，采用圆谐函数将二阶微分算子变换到一个正交空间，在此基础上对能量进行优化。与此相关的，过参数化（Over-parameterized）在光流计算中也得到了应用，如Nir［27］等。2.3.3最优化最优化算法可分为连续优化与离散优化两大类。常见的连续优化算法有梯度下降算法和变分法等。梯度下降算法中以梯度函数作为衡量计算精确度的标准，如果迭代使得梯度函数下降，那么计算结果就更加精确。为了达到一定的精确度，可以通过设定一个阈值，作为迭代终止的条件。例如Baker［28］介绍了高斯牛顿法、牛顿法和Levenberg-Mar-quardt等。最为常用的连续优化算法为变分法［1，10，18，25，27］，即假设全局能量函数可写为如下形式：问题转化为取何值时使得能量函数达到最小值。这个问题可以通过Euler–Lagrange方程解决。张拯，等：光流算法研究107··1217（总第42-）火力与指挥控制2017年第7期除了以上介绍的两种主要算法，其他文献也提出了一些独特的方法。如Wedel［19］采取了分步优化的策略：首先可以假设先验项为恒定值，求数据项和第三项之和的最小值；然后假设数据项为恒定值，求先验项和第三项之和的最小值。而对于离散优化，一般采用的方法有融合方法［26，29-30］和稀疏状