计算机视觉大型攻略 —— 光流（1）基本原理和经典算法

这篇写光流基本原理，及经典算法Lucas-Kanade，Horn-schunk。大量图片和公式出自LearnOpen3和下面几个PPT。

https://download.csdn.net/download/plateros/11961100

https://download.csdn.net/download/plateros/11961087

相关论文，

[1] An Iterative Image Registration Technique with an Application toStereo Vision

[2] Determining optical flow

[3] Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the algorithm

光流

光流算法寻找一张图片上的像素在另一张图片的位置。这两张图片一般是时间序列图片。算法输出了像素的速度，也可以说是像素在这两张图片的相对位置变化。计算图片中每个像素的光流，称为稠密光流，而只对特定像素点计算光流的算法就是稀疏光流。

如上图，光流问题就是估计连续图像像素的运动，等价于寻找连续图像中像素的相关性。

关键假设

经典光流算法使用了如下假设

• 颜色/亮度恒定假设(Color Constancy/Brightness Constancy)
• 小运动假设

Brightness Constancy可知，

在小运动的假设下，我们用泰勒公式将函数展开，做线性化近似，

令

， 联立上面两个方程，

当u, v趋近于0时，

可以替换成

 。

这个公式的具体含义请见下图，                         

• Ix, Iy是I(x, y)在空间上的导数，即图像的梯度。通过Sobel filter等就可以获得。
• It为时间上的导数，可以通过两帧图像做减法获得。

• u, v代表光流，是未知量。这个方程有两个未知数，仅由一个像素是无法求解这个方程的。后续出现很多求近似解的算法，最有代表性的就是Lucas-Kanade与Horn-schunck

Lucas-Kanade算法

1981年，论文[1]提出了Lucas-Kanade算法。该算法引入一个新的假设求解上面这个方程 ——空间一致性假设。假设同一平面上邻近的点具有相似的运动，具体来说就是选取一个mxn的窗口，在此窗口内假定光流值相同，所以这种算法也被称为constant flow。举个例子，假设我们选取5x5的窗口，如果在此窗口内光流相同，我们就可以得到25个公式，

                                                             ......

写成矩阵的形式，

  采用最小二乘法求解这个方程组的近似解,     

       ,

最小化此方程，等价于求解                  

如果

可逆，可以求出x,

将光流公式代入，

可以看到

秩为2，当其满秩时，矩阵可逆，也即

有两个较大的特征向量时。图像中纹理至少有两个方向的区域，这个条件不难满足，联想到Harris角点检测算法， 当跟踪窗口的中心在图像的角点区域时，

的特性最好。

传送门:  Harris角点

LK算法最初用于求稠密光流，但是由于其对角点有较多要求，因此通常只能应用于稀疏光流。

这个算法假设窗口内光流一致，然而这样的窗口不易选择。窗口越小，越容易出现孔径问题， 窗口越大，越无法保证窗口内光流的一致性。

举一个孔径问题的例子，

这个窗口内所有x轴方向的梯度为0(Ix(i,j)=0)，只能算出v，而无法算出u。

Horn-Schunck算法

Horn-Schunck算法引入了另一种假设 - 平滑性。与LK的光流一致性不同，他认为相邻像素的运动是相近的，平滑的。                                                         

光强一致性

与LK算法相同，HS算法同样建立在光强一致性假设上。事实上，HS算法是最早提出亮度恒定假设和推导出基本亮度恒定方程的方法之一。 与LK不同，HS是一种全局约束算法，也就是说，对每一个像素来说，都需要满足寻找最优的光流值u,v， 使得

的模最小。

平滑性     

在平滑性假设下，相邻像素的光流变化越小越好，

完整能量函数

全局约束算法需要引入能量函数E，算法的目的是获取合适的参数使得E最小 ，

是能量函数的数据项，约束了光强一致性，

是平滑项，约束了相邻像素光流的平滑性。这一部分与原始论文有点不一样，原始论文采用了拉普拉斯模板计算像素的二阶微分。这里的

定义如下，其实也是像素的二阶导数，这里u, v表示的是光流，光流的导数其实就是像素的二阶微分。

优化过程

求解这个能量函数的最小值。

首先对能量函数的u, v求偏导，

   E的极值意味着导数0，可以令这两个偏导数为0。得到两个新的公式，仔细看一下，这是一个线性系统。

写成矩阵的形式，

可以把ukl和vkl解出来，

我后来发现上面推荐的卡内基梅隆大学的讲义有一个笔误，求逆的时候行列式是对的，伴随矩阵写错了，但是资源传上去了貌似 没法修改了。在这里更正一下，                               

应该是，

换个形式，

,          

这两个公式中，

,均是未知数，需要用迭代法求解这个线性方程组，

整个算法流程非常简单，

1. 计算图像梯度Ix, Iy
2. 计算前后两帧图像差It
3. 初始化光流，比如说u=0, v=0
4. 迭代求解上面两个方程，直到收敛。

光流金字塔

无论是Lucas-kanade还是Horn-schunck算法，均有小运动的假设。然而在实际场景的下，无法保证这个假设。Jean-Yves Bouguet在论文[3]中提出了光流金字塔算法，以改善小运动假设带来的弊端。

前后两帧图片(image1, image2)按照一定的比例缩放，最下面一层为原始大小图片。算法从最顶端开始计算光流，将上一层估计的结果作为下一层估计的起始输入进行估计，直到最后一层。因此这个过程也称为coarse-to-fine。

图像金字塔

首先看如何生成各层图像。令

为图像I的第0层。也即最高分辨率的原始图像。L定义为层数。

表示第L-1层的图像。

定义

表示第L-1层初始的光流。

表示第L层估计出来的光流。

论文中指出一般情况下不需要超过4层金字塔，这个说法可能有点随意。层数应该跟图像分辨率有关。分辨率越大，同样幅度的运动导致的像素位移就会越大，层数需要的就越多。

当获取某一层的光流后，就可以把这个结果作为下一层的初始输入。原始论文每一层采用LK迭代光流。类似的，HS光流算法同样可以采用这种方式获得改善。

代码

Github上关于LK和HS的代码，对论文还原的最好的来自Eric yuan。可以通过代码进一步理解论文。

https://github.com/xingdi-eric-yuan/optical-flow.git