光流

光流算法第1页共6页视觉心理学认为人与被观察物体发生相对运动时，被观察物体表面带光学特征的部位的移动给人们提供了运动和结构的信息。当相机与场景目标间有相对运动时所观察到的亮度模式运动称之为光流(opticalflow)，或者说物体带光学特征部位的移动投影到视网膜平面(也即图像平面)上就形成了光流。光流场的计算一般分为四类：基于梯度的方法(Horn-Schunck和Lucas-Kanade算法都是基于梯度的算法)；基于匹配的方法；基于能量的方法；基于相位的方法。基于梯度的方法利用图像灰度的梯度来计算光流，是研究最多的方法。基于梯度的方法根据运动前后图像灰度保持不变这个基本假设，导出光流约束方程。由于光流约束方程并不能唯一的确定光流，因此需要导入其他的约束。根据引入的约束不同，基于梯度的方法又可以分为全局约束方法和局部约束方法。全局约束的方法假定光流在整个图像范围内满足一定的约束条件；而局部约束的方法假定在给定点周围的一个小区域内，光流满足一定的约束条件。基于匹配的方法，这类方法是将速度mv定义为视差(,)Tdxdyd，使得两个时刻的图像区域的匹配最佳。为了找到最佳匹配，我们可以对定义在d上的相似度量，如规一化的互相关系数，进行最大化，也可以对某一距离度量，如光强度差的平方和，进行最小化。基于梯度的光流场算法介绍梯度光流法又分为全局约束方法和局部约束方法。全局约束方法假定光流在整个图像范围内满足一定的约束条件，而局部约束的方法假定在给定点周围的一个小区域内，光流满足于一定的约束条件。下面先导出光流约束方程。然后给出两种比较典型的基于梯度的方法。1、光流约束方程假定图像上点(,)Txym在时刻t的灰度值为(,,)Ixyt，经过时间间隔dt后，对应点的灰度为(,,)Ixdxydytdt，当0dt时，可以认为两点的灰度不变，也就是：(,,)(,,)IxdxydytdtIxyt(1)如果图像灰度随,,xyt缓慢变化，可以将(1)式左边泰勒级数展开：(,,)(,,)IIIIxdxydytdtIxytdxdydtxyt(2)其中代表二阶无穷小项。由于0dt，忽略，可以得到：0IIIdxdydtxyt(3)令dxudt，dyvdt代表,xy方向上的光流，xIIx，yIIy，tIIt分别代表图像灰度相对于,,xyt的偏导，式(3)可以写成：0xytIuIvI(4)此式即光流场的基本方程。写成向量形式，即：0mtIIv(5)光流算法第2页共6页其中(,)xyIII是图像在点m处的梯度，(,)muvv是点m的光流。上式称为光流约束方程，是所有基于梯度的光流计算方法的基础。图1基本等式所确定的约束线考虑u和v组成的二维空间，那么式(5)定义了一条直线，所以满足约束方程的mv都在该直线上，图1，该直线和图像梯度I垂直，因而仅仅能够解决沿梯度方向的分量，也就是等灰度轮廓的法线分量nsvn，其中：(实际上，式(5)光流约束方程产生的是恒值亮度轮廓图像运动的法向分量nsvn),tInIsII(6)光流约束方程包含u和v两个未知量，显然由一个方程并不能唯一确定，这就是孔径问题。为了解决孔径问题，必须找新的约束。2、Horn-Schunck算法光流约束方程不能唯一确定图像光流，需要引入新的约束条件。Horn-Schunck算法提出了光流的平滑性约束。即：图像上任一点的光流并不是独立的，光流在整个图像范围内平滑变化。因此Horn-Schunck算法是一种全局约束的方法。设平滑性约束项为极小化：2222sxyxyEuuvvdxdy(7)由基本等式，显然要求极小化：2cxytEIuIvIdxdy(8)于是，由(7)和(8)式可知，最后求得光流应满足(9)式：22222minxyxyxytuuvvIuIvIdxdy(9)这里的取值要考虑图中的噪声情况，如果噪声较强，说明图像数据本身的置信度较低，需要更多的依赖光流约束，所以可以取较大的值；反之，取较小的值。光流算法第3页共6页为了满足(9)，可将该式对u和v分别求导，并取导数为0。这样就得到：22xxyxtIuIIvuII(10)22yxyytIvIIuvII(11)以上两式也称为Euler方程。如果令u和v分别表示u邻域和v邻域中的均值(可用图像平滑算子求得)，并令uuu和vvv，则式(10)和(11)改写成：,,11,,1,1,11,1,1,,1,,,1,1,1,1144tijkijkijkijkijkijkijkijkIIIIIIIII222xxyxtIuIIvuII(12)222yxyytIvIIuvII(13)从上式解得：222xxytxyIIuIvIuuII(14)222yxytxyIIuIvIvvII(15)式(14)和(15)提供了用迭代法求解u和v的基础。实际中，常用松弛迭方程进行求解：()()(1)()222kkxytkkxxyIuIvIuuIII(16)()()(1)()222kkxytkkyxyIuIvIvvIII(17)其中k是循环数，(0)u和(0)v是初始值，可以取为0。u和v是局部平均，为权重系数，根据导数求取的精确度确定。上述迭代过程有一个简单的几何解释，参考图2所示：图2用迭代法求解光流的几何解释光流算法第4页共6页在实际求解过程中，需要估计亮度的时间和空间微分。这可在图像点的一个2×2×2立方邻域中估计，如果下标,,ijk分别对应,,xyt，那么3个一阶偏导分别是：1,,1,1,1,,11,1,1,,,1,,,1,1,11144xijkijkijkijkijkijkijkijkIIIIIIIII(18),1,1,1,,1,11,1,1,,1,,,,11,,11144yijkijkijkijkijkijkijkijkIIIIIIIII(19),,11,,1,1,11,1,1,,1,,,1,1,1,1144tijkijkijkijkijkijkijkijkIIIIIIIII(20)也就是用一阶差分来替代灰度I关于,,xyt轴的偏导。上述算法的实现相对简单，计算复杂性较低。但是这种技术存在着严重缺陷。首先，图像灰度保持假设对于许多自然图像序列来讲都是不合适的，尤其是在图像的遮合边缘处和(或)当运动速度较高时，基于灰度保持假设的约束存在较大误差。其次，在图像的遮合区域，速度场是突变的，而总体平滑约束则迫使所估计的光流场平滑地穿过这一区域，此过程平滑掉了有关物体形状的非常重要的信息。第二，微分技术的一个要求是I(x，y，t)必须是可微的，这暗示着需对图像数据进行时空预平涓·以避免混叠效应;而且数值微分的求取具有病态性，如果处理不当将对最终的速度估计产生显著影响。(本段内容参考：基于光流场的视频运动检测)3、Lucas-Kanade算法与Horn方法不同，Lucas-Kanade方法是基于局部约束的。假定以p点为中心的一个小区域内各点的光流相同，对区域内不同的点给予不同的权重，这样光流的计算就转化为最小化如下的方程：22,,txWxxtxtIvI(21)上式中，代表以p点为中心的一个小的区域，Wx为窗函数，代表区域中各点的权重，离p点越近，权重越高。(21)的解可以由下面的方程得到：222TAWAvAWb(22)对于邻域内的n个点im，其中，12,,...,TnAIxIxIx(23)12,,...,ndiagWWxWxWx(24)12,,...,TtttnbIxIxIx(25)最后，方程的解为：122TTvAWAAWb(26)实际上，2TAWA为2×2矩阵：光流算法第5页共6页2222222xxyTyxyWxIxWxIxIxWxIxIxWxIxAWA(27)上式中所有的求和都是在的所有点上进行的。假设2TAWA的特征值为1和2，并且12，则：1)、如果12,，则利用(27)计算v;2)、如果12,，则不能得到光流的完整信息；3)、如果1，则认为数据不可靠，不能计算光流。在Lucas-Kanade算法的具体实现中，为3×3，则可以得到一个超定的图像流约束方程：129129129.........TTTxxxtttyyyIIIuvIIIIII(28)图像流约束方程实际是速度平面,uv上的直线方程，如果考虑图像序列中连续的J2J帧图像，并假定目标的运动速度在J帧图像里近似保持不变，对于运动目标而言，其在连续J帧图像里的J条运动约束直线，必在速度平面近似交于一点。为了进一步提高Lucas一Kanade方法的准确度以及运算速度，在实际应用中，又将高斯金字塔分层与Lucas一Kanade方法结合起来，采用了由粗到精的分层策略将图像分解成不同的分辨率，随着级别的增加，分辨率越来越低，并将在粗尺度下得到的结果作为下一尺度的初始值，在不同的分辨率上对图像序列进行流速计算，这是计算大的运动速度的有效的技术手段。本文试验中采用的高斯金字塔层次L=4。并且在算法中嵌入了一个线性尺度函数。(本段内容参考：基于光流场的视频运动检测)基于微分法的光流计算方法仅适用于小图像运动的问题，金字塔光流法[17]可以解决此问题。该方法的基本思想是构造图像序列的一个金字塔，较高的层是下层平滑后的下采样形式，原始图像层数等于零。当图像分解到一定的层后，相邻帧间图像运动量将变得足够小，满足光流计算的约束条件，可以直接进行光流估计。在实际计算时，由高层到低层进行，当某一级的光流增量计算出来后，将加到其初始值上，再进行投影重建，作为其下一层的光流计算初值。这一过程不断进行，直至估计出原始图像的光流。(本段参考：基于光流的运动目标检测与跟踪技术2.3.1)LK算法堪称一次飞跃，不仅在算法精度上提高了很多，而且提高了运算速度，使光流法可以应用在实时系统中成为可能。通过预测运动值提高了运算精度，它抗噪能力也比较好。(本段内容参考：基于光流场的视频运动检测)4、Nagel方法(内容参考：基于光流场的视频运动检测)(论文中不写)Nagel方法使用二阶导数(Second-orderderivatives)来估计光流[10,11]。和Horn-Schunck法一样，Nagel也使用了全局平滑约束来建立光流误差测度函数，与Horn-Schunck测度函数不同的是，Nagel提出的一种面向平滑的约束(Oriented-SmoothnessConstraint)，并不是强加在亮度梯度变化最剧烈的方向(即边缘方向)上，这样做的目的是为了处理遮挡光流算法第6页共6页(ocdusion)问题。该方法的误差测度函数为:22222222222xytxyyxxyyxxyxyIuIvIuIuIvIvIuuvvdxdyI(3.3.22)相对于(,)Tuvv求上式的极小化会削弱垂直梯度方向上的光流变化。Nagel[10]建议取1，0.5。使用Gauss-Seidel迭代，(3.3.22)的解可表示为：12221222()()()()()()kkxxytkkxykkyxytkkxyIIuIvIuuIIIIuIvIvvII(3.3.23)其中，k表示迭代次数，()