DeepFlow高效的光流匹配算法（上）

本周主要介绍一篇基于传统光流法而改进的实现快速的稠密光流算法。该算法已经集成到OpenCV中，算法介绍网址：http://lear.inrialpes.fr/src/deepmatching/

在介绍该高效的算法之前，我们先介绍一下经典的LK光流算法，所以这篇文章将分为上下两篇。

第一篇主要介绍光流算法的基础知识,以及理论推导。

第二篇将介绍改进的稠密光流算法匹配算法DeepFlow，并展示windows下OpenCV中集成代码和在linux下源码的运行效果。

LK光流大揭秘

光流算法基础

光流（Optical Flow）是目前运动图像分析的重要方法，它的概念是由 James J. Gibson于20世纪40年代首先提出的，是空间运动物体在观察成像平面上的像素运动的瞬时速度。这种运动模式是有一个观察者在一个视角下，评估两幅图像之间的变形

光流计算基于物体移动的光学特性提出2个假设

（1）亮度恒定不变，就是同一点随着时间的变化，其亮度不会发生改变。这是基本光流法的假定（所有光流法变种都必须满足），用于得到光流法基本方程；

（2）时间连续性或者运动时小运动，这个也必须满足，就是时间的变化不会引起位置的剧烈变化，这样灰度才能对位置求偏导（换句话说，小运动情况下我们才能用前后帧之间单位位置变化引起的灰度变化去近似灰度对位置的偏导数），这也是光流法不可或缺的假定；

首先我们需要对光流有一个基本认识：

连续帧的图像

特征点（角点）提取

特征点跟踪

光流跟踪效果图

在基于以上的前提下，我们假设有两帧图像，如下点（x,y）经过（u，v）的位移对应第二帧图像上的（x+u,y+v）

根据亮度不变性，以及小位移有以下公式（1）：

用泰勒公式展开右侧有公式（2）

根据公式（1）（2）得到公式（3）

Ix和Iy就是该点在x轴方向上和y方向的导数。It是该点对时间的求导，在极小时间内图像亮度恒定的条件下It为两帧图像上灰度值之差。因此有公式（4）

这就就是基本的光流约束条件，Ix,Iy,It均可由图像数据求得，而(u,v)即为所求光流矢量。但是光流的约束方程只有一个，而需要求出x,y方向的速度u和v(两个未知量)，一个方程两个未知量是没有办法求解的，所以下文介绍的LK光流法考虑到了像素点的领域，将问题转变成了计算这些点集的光流，联立多个方程，从而解决这个问题。

LK光流

LK( Lucas–Kanade )光流算法是一种两帧差分的光流估计算法。它由Bruce D. Lucas 和 Takeo Kanade提出。

光流分为稠密光流法和稀疏光流法,稀疏光流主要是跟踪特征点，稠密光流是跟踪图像中的每个像素，由这篇文章延伸出来的下篇文章DeepFlow就是稠密光流中目前为止最为高效的稠密光流算法。

LK光流算法加了一个更加严格的条件---空间一致性，一个场景上邻近的点投影到图像上也是邻近点，且邻近点速度一致。这是Lucas-Kanade光流法特有的假定，因为光流法基本方程约束只有一个，而要求x，y方向的速度，有两个未知变量。我们假定特征点邻域内做相似运动，就可以联立n多个方程求取x，y方向的速度（n为特征点邻域总点数，包括该特征点）。

领域内光流一致，一个场景中的同一个表面的局部领域内具有相似的运动，在图像平面上的投影也在邻域区域，且临近点速度一致，认为邻域内所有像素点的运动一致的，这是LK光流特有的假定。

具体到图像中，所以下图所示，Wx,Wy是块区域的大小。

根据以上的区域灰度值不变且邻域内的所有像素点运动一致的。可以得出以下

该方程中只有两个未知数，u和v,却有n个方程也是不合理的，说明这个方程中也有多余的，怎么样才能得到最优解呢？可以将上式整理为

简单写为，其中A是在x,y方向上导数，x为要求的u和v向量。

最终得出

所以这里我们列出了这些方程的残差函数

那么最终只需要求得到该残差方程的偏移量最小，也就是使用了最小二乘法求出这个方程组的最优解。

上面提到了LK光流的假定是小运动，可是运动较快的时候应该怎么办呢？考虑到两帧之间的物体的位移比较大，且运动快速时，算法会出现较大的误差，那么就希望减少图像中物体的运动位移，怎么做的？那就要缩小图像的尺寸，假设当图像为400*400，物体的位移为【16,16】那么当图像缩小为200*200位移就变成了[8,8] 缩小为100*100 位移缩小为[4,4]，所以在原图像缩放了很多以后，LK光流法又变得适用了。所以LK光流引入了图像金字塔，上层金字塔（低分辨率）中的一个像素可以代表下层的两个像素，这样利用金字塔的结构，将图像逐层的分解，自上而下修正的运动量。

加入图像金字塔光流的计算

（1）图像金字塔，首先对每一帧图像建立一个高斯金字塔，最低分辨率图像在最顶层，原始图像在底层。

（2）计算光流使用顶层（Lm）层开始，通过最小化每个点领域范围内的匹配误差和，得到每个顶层图像中每个点的光流。该步骤主要是求解上述的残差函数，不再赘述。

假设图像的尺寸每次缩放为原来的一半，一共缩放了Lm层，则第0层为原始图像，设已知原图的位移为d,则每一层的位移可以表示为

所以顶层的光流计算结果，也就是位移，反应到Lm-1层，作为该层初始时的光流值的估计g表示为：

沿着金字塔向下反馈，重复估计每一层的位移，直到最底层也就是原始图像计算像素的位移：

可以理解为 准确值=估计值+残差，对于每一层L，每个点的光流的计算都是基于邻域内所有点的匹配误差和最小化

这样的搜索方式，不仅可以解决大运动目标跟踪，也可以在一定程度上解决孔径问题（相同大小的窗口能覆盖大尺度图片上尽可能多的角点，而这些角点无法在原始图像上被覆盖）由于金字塔的缩放减小了物体的位移，也就减小了光流，其中顶层图像中的光流的估计值设置为0

光流残差方程推导

求解光流最重要的是最小化上文提到的残差方程：

为最小化上式我们对该方程求导有

使用一阶泰勒展开B(x+vx,y+vy)，并替换上式有

所以细分表达式有：

残差函数表示为：

最终展开求解如下

Refernce

• Jean-Yves Bouguet, “Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the algorithm”, Intel Corporation Microprocessor Research Labs.
• http://www.ces.clemson.edu/~stb/klt/ C++ code
• KLT: An Implementation of the Kanade-Lucas-Tomasi Feature Tracker