DeepFlow高效的光流匹配算法(下)

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

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

第一篇DeepFlow高效的光流匹配算法(上)主要介绍光流算法的基础知识,以及理论推导。

第二篇将介绍改进的稠密光流算法匹配算法DeepFlow,并展示Demo效果。

DeepMatching是jerome revaud在2013年开发的一种匹配算法。其目的是计算两幅图像之间的密集对应关系。深度匹配依赖于为匹配图像而设计的深层、多层、卷积结构。它可以处理非刚性变形和重复纹理,因此可以在图像之间存在显著变化的情况下有效地确定稠密对应关系。

在这个匹配算法的基础上又改进了很多其他方面的计算,相关论文主要有:

《DeepMatching: Hierarchical Deformable Dense Matching》

《DeepFlow:Large displacement optical flow with deep matching》

《EpicFlow: Edge-Preserving Interpolation of Correspondences for Optical Flow》

《Fast Optical Flow using Dense Inverse Search》

论文贡献

在经典的光流算法中,在计算小位移的光流算法中在过去几十年中得到了广泛的研究。每个像素的运动被限制在几个像素以内。大位移问题是近几年才引起人们的关注,至今仍是一个悬而未决的问题。大位移光流覆盖了运动不受限制且比物体尺寸更大的更真实情况。为了改善类似问题,正如上一篇文章所述,LK光流又增加了图像金字塔来针对处理大位移的光流的情况。而本文主要的是介绍一种,稠密光流的算法。

DeepFlow可以说是DeepMatching算法的改进算法,将匹配算法与变分方法相结合,应用于光流的计算,是一种适应光流问题的描述子匹配算法,可以提高光流法在快速运动的表现。匹配算法建立在更多层数层,交错卷积和最大池的多层架构之上,这种结构类似于深度卷积网络。同时基于DeepMatching的改进算法还有EpicMatching,以及改进光流计算效率的算法Fast Optical Flow using DIS。

这篇文章做了两个贡献:首先,提出了一种新的匹配算法,称为深度匹配。其次它建立在一个多阶段的架构之上,交错卷积和最大池,就像在深卷积神经网络中那样。深度匹配具有平滑效果,即便在两帧图像之间存在显著变化的情况下,也能够有效的确定稠密对应集。最后,利用brox和malik的方法在大位移光流中进行深度匹配。

这是一种新的匹配算法—-深度匹配

1, 多层结构、交织卷积和最大池

2, 自平滑匹配

3, 大位移光流:集成变分方法中深度匹配对大位移显示出很好的鲁棒性

该算法的相比经典光流

经典的光流估计的基本准则是在满足一定前提条件下,最小化能量值。这部分内容可以细细阅读上一篇文章DeepFlow高效的光流匹配算法(上)

一般情况下,大位移的光流依赖于刚性匹配或者小区域的匹配算法,所用的特征点一般是基于Hog或者sift描述子,采用最近邻方法匹配。

缺点是

1,基于块区域内是光流的一致性,如果在这个块区域内有着不同方向的位移像素,此时这种方法是无法解决的。

2,在纹理不明显的地方这种方法是不可靠的。

该论文里提出的深度匹配算法,介绍如何生成稠密的光流,并且相比较经典算法更能解决以上的一些缺点。

该算法优点有

1,可以应用块区域内的子区域的在一定区域内可以按照不同方向的独立运动

2,使用卷积和最大池快速计算

3,使用了递归的方法

算法的具体步骤

模块一

1,给定两幅图像,我们首先从第一幅图像中提取小的4×4块。

2,使用第一幅图中的patch与第二幅图patch进行卷积

3,此时我们得到了这个patch的响应Map

4,对所有的图像中的patch重复此过程。得到论文中称之为响应图像。

模块二

在模块一得到的响应图上再继续一下操作

1,应用一个max pooling操作符。允许该结果的响应图与patch移动1像素时的响应图相同。

2,由于响应图现在在空间上变化缓慢,这里增加了一个下采样步骤。该步骤可以减少后面步骤的复杂性。

3,然后利用4个响应图的稀疏卷积,即4个位移响应图之和,计算较大patch的响应图。

4, 最后加入一个非线性滤波,以避免过快的收敛到1。结果,得到了虚拟8×8块的响应图,

其中每个子块的位置在3×3像素附近优化。

5,然后,从这个第二级响应映射的计算,获取虚拟16×16响应映射。

6,重复以上过程

最终迭代过程的结果是一个多尺寸的响应金字塔。在其中扩展了尺度的局部最大值。

对于每个最大值,算法都会回溯到允许获得该最大值的配置,从而产生准密集的对应关系。它是使用动态编程完成的。其中,金字塔是使用自下而上的方法构建的,而提取对应关系则使用自上而下的方法。

上图是论文中如何检索对应关系的示例。

考虑金字塔上的红点是一个局部最大值。

然后它对应于一个叫大的Patch移动。这个最大值是使用4个较小的Patch构建的,检索它们并获得较小的patch匹配。不断的继续下去,就会出现像右边一样出现的小patch。

下面是从重复纹理图像中,利用深度匹配算法提取的对应关系的示例,其中每个颜色都指一个局部最大值。

深度匹配会产生稠密对应点。它使用多尺度的Patch,允许匹配不同比例的对象。成功地处理了纹理重复的图像,而不能处理标准刚性匹配或小patch之间的匹配,也不能处理非刚性变形。最后,允许的变换集提供了一个内置的平滑效果。实际上,局部最大值会导致许多匹配,由于对可行变换集的约束,这些匹配几乎相同。

结论

deepflow使用ldof方法将深度匹配集成到变分方法中。

在经典的数据项和平滑项的基础上,增加了一个匹配项,对输入匹配项和光流估计项之间的差异进行了计算。然后,使用从粗计算到细计算的策略、定点迭代和经典线性系统求解器(如sor)对其进行优化。

DeepFlow拓展算法

以上主要是介绍匹配的方法,能够处理大位移以及块区域中像素不满足光流一致性的前提条件。同时在论文中《Fast Optical Flow using Dense Inverse Search》详细的介绍了如何更加高效的计算光流的值,是一种更为高效的优化方法。

论文中计算光流的步骤:

(1)初始化:对两幅图像构建图像金字塔,以及一些计算量进行初始化

(2)for循环:这一步与LK光流一致,都是从最顶层到最低层的迭代求解的过程

1 根据当前层的梯度图像计算图像的块状积分图

2 逆向搜索求解稀疏的图像光流场,(这一步是这篇论文的核心和关键,提出了完全不同于传统光流不一样的求解方法)

3,根据稀疏光流场计算稠密光流。

(3)最底层的光流resize到跟原始图像一样大小并乘以相应的放大比例,得到最后的光流。

分解这三个部分

1) 图像块状积分图,用于逆向搜索,输入为图像的x,y方向上的梯度Ix,Iy,一般通过soble 算子卷积得到,这一步骤,其实与LK光流求块区域的积分图像没有任何区别。

2)将步骤1)中的输出结果作为这一步的输入,逆向搜索得到稀疏光流场,这一步就是这篇论文的核心所在,是作者创造性的将每一层的光流的迭代量(deltaU,DeltaV)放到了能量最小化公式的左边,从上一篇文章中我们知道传统的光流求解方程为

每一层图像上的光流结果为初始值+迭代量

u += delU, v+= delV

最终的求解并优化的残差函数为

在最小化该函数时,需要根据泰勒展开迭代的求解一阶导数S和二阶导数H,就是要多次求解S,H效率低下

而逆向搜索是将上面的公式中写成了

I(x-delU,y-delV,t-1) = I(x+u,y+v,t)

并且最终的残差函数为变成求解

所以与传统光流不同的是,最终求得到光流位移量为

u -= delU, v-= delV

使用一阶泰勒展开后得到

此时最小化的残差函数变成了

此时从这个残差函数中我们可以得到,每次迭代只需要计算一次S和H,计算速度提升很多,而且精度相差不大。这就是本篇文章的核心。

3)计算稠密光流,输入稀疏光流场,当前层的每一个像素对应的光流等于所有包含该点的图像块对应的稀疏光流的加权求和

以下demo是集成在OpenCV4.0以上版本的DIS光流算法:(说明:将光流场转换到HSV空间中显示,光流的数值用不同颜色来区分,色斑颜色深浅代表运动速率,白色代表物体无运动。)