第23讲:计算机视觉中的光流估计详解
流估计
主要概念:
- 亮度08好恒定方程
- 孔径问题
- Lucas-Kanade算法
回顾:由于自身运动产生的场
流(Flow):
旋转分量不依赖于场景结构。平移分量随场景 Z 值的变化而变化。也就是说,它显示出运动视差(parallax)。
特例:纯平移
为了更好地理解流场是什么样子,让我们只考虑纯平移运动的情况。
然后,在场景中通过平行速度矢量的投影形成流
特例1:纯平移
假设 Tz 不等于 0
定义:
假如 Tz = 0 则
所有运动场矢量彼此平行,并且与深度成反比!(与简单的立体视觉联系起来)
此情况下的运动场是径向的:
- 它由通过 po=(xo,yo)的向量组成
- 假如:
1)Tz > 0 (相机向物体移动)
向量远离po
po是扩展点 POINT OF EXPANSION
2)Tz < 0 (相机远离物体)
向量指向po
po是收缩点 POINT OF CONTRACTION
纯旋转:运动场的性质
假如 Tz 不等于0,则运动场是径向的,所有向量都指向(或远离)单个点po。如果Tz=0,则运动场是平行的。
运动场向量的长度与深度Z成反比。如果Tz≠0,它也与p和po之间的距离成正比
po是平移方向的灭点(vanishing point)
po是平行于平移向量的光线与图像平面的交点
运动场Motion Field和光流Optic Flow
运动场:三维相对速度矢量在二维图像平面上的投影
光流:在图像中观察到的亮度模式(brightness patterns)的二维位移
运动场是我们想知道的。
光流是我们可以估计的。
注意:光流不等于运动场
考虑一个移动的光源:
MF=0,因为场景中的点没有移动
OF不等于0,因为图像中存在移动模式
用OF近似MF
不过,我们将估计 OF(因为 MF 不能被真正观察到!)。
为了避免由于改变光照而产生的视在流(apparent flow),假设移动对象的视在亮度(apparent brightness)保持不变。
亮度恒定方程
考虑场景点在图像序列中移动
假设:它的亮度/颜色将保持不变(部分原因是我们可以认识到它是同一点)
两边同时对 t 求导
使用链式法则
空间梯度,我们可以计算
光流,我们希望得到的
帧间导数。也是知道的,例如帧差
可以写为
光流被限制在一条线上!(方程是 a u+b v+c=0 这样的形式)
绿色圈:已知(空间和时间梯度)
红色方框:未知(光流矢量部分)
意义
直觉上,这个约束意味着
– 梯度方向的光流部分是被确定的(称为垂直光流)
– 平行于边缘的光流部分是未知的
孔径问题 The Aperture Problem
图像亮度恒定假设只提供空间图像梯度方向上的OF分量
另一个例子是理发杆错觉。
考虑一个点
视在的运动是往上
真实的运动是往左
光流不等于运动流
孔径问题再一次提醒我们光流和运动流是不一样的
- 在边缘附近,我们只能观察(测量)垂直于边缘的光流分量
- 不能够测量平行于边缘的光流分量
- 光流不可观测的另一个例子是在恒定灰度的区域。没有观察到流。
计算光流
计算光流的算法有两种形式:
- 差分方法
在所有像素上的图像亮度基于空间和时间的变化。
用于计算稠密光流 - 匹配方法
类似于立体特征匹配,计算视差
用于计算稀疏光流
一种差分方法:恒定光流,也就是Lucas-Kanade光流
Lucas-Kanade光流动机
我们需要两个或者更多的像素去解决
由于孔径问题,我们希望包括不同梯度方向的像素。
解决孔径问题
使用两个或多个方向的梯度
单个梯度方向的孔径问题
用两个或更多方向能够推导出正确的结果
如何为一个像素得到更多的方程?
- 基本思想:引入额外的约束
• 最常见的是假设流场是局部平滑的(假设某一个窗口内的像素具有相同的运动)
• 例如,假设像素领域内的像素都具有相同的位移(u,v)
—如果我们使用一个 5x5 的窗口,每个像素就会有25个方程!
Lucas-Kanade 光流
我们有比未知数更多的方程:解最小二乘问题,也就是:
对 K×K 窗口内的所有像素求和得到
可解的条件
最优(u,v)满足Lucas-Kanade方程
什么时候有解?
- ATA应该是可逆的
- 由于噪声,ATA不应该太小
– ATA 的特征值 λ1 和 λ2 不应该太小
- ATA应该 well-conditioned
– λ1 / λ2 不应该太大(λ1 是较大的特征值)
ATA看起来相似?
观察矩阵:
Harris角点检测矩阵
回顾:Harris角点检测算子
在 Lecture 6,我们通过考虑偏移灰度图像块的SSD导出了Harris角点检测算子
结合Harris进行运动分析
之前这里是单帧的空间偏移。现在是一段时间内两帧之间的位移。
当前帧
前一帧
边缘,大的梯度, λ1 大,λ2 小 ——将会有孔径问题
纹理弱(平坦)的区域,梯度的幅值小,λ1 小,λ2 小——Ill-conditioned 矩阵,可能计算垃圾答案
角点,梯度在各个方向上是不同的并且具有较大的幅值,λ1 大,λ2 大——很好的角点特征。也是估计光流的好地方!
意义
• 角点是当 λ1 和 λ2 都较大时;这也是 Lucas-Kanade 光流最有效的时候。
• 角点是具有(至少)两个不同梯度方向的区域。
• 角点处的孔径问题是会消失的。
• 角点是计算光流的好地方!
基于特征点的方法
稀疏光流的特征匹配
基本思想:
在第一幅图像中找到角点(因为角点是估计光流的好区域)
在第二幅图像中搜索对应的灰度图像块
KLT算法
http://www.ces.clemson.edu/~stb/klt/
通过2帧或更多帧图像跟踪角点特征
KLT算法
- 在第一幅图像中找到角点
- 提取每个角点处的灰度图像块
- 用 Lucas-Kanade 算法估计图像块像素的恒定位移
细节:
- 运用迭代和多分辨率来处理大运动
- 亚像素位移估计(双线性插值变换)
- 可以通过整个帧序列跟踪特征点
- 具备旧的特征点“丢失”时添加新特征点的能力
基于互相关性的匹配
另一种方法是使用互相关性(correlation)或 NCC 来匹配灰度图像块。(之前有讨论过)
- 在第一幅图像中找到角点
- 提取每个角点处的灰度图像块
- 使用 NCC 计算第二幅图像中搜索窗口内的匹配分数
- 识别最高得分(最佳匹配)
关于效率的重要说明
一幅图像中给定的图像块
我们不想在第二张图片中到处搜索匹配块。
在立体视觉中我们有一个极线约束
但这里我们不知道相对的 R,T,所以没有对极约束
但是…运动是已知比较“小”的,所以仍然可以限制搜索区域。
关于使用归一化互相关的说明
如果我们使用归一化互相关性来匹配特征块,我们可以放松(relax)恒定亮度假设!
因此,我们可以消除了一些潜在的误差源(光照或摄像机增益的变化)
另一个基于互相关性的算法
Due to David Nister, “Visual Odometry”, CVPR 2004
观察:一张图片中的角点在短时间内倾向于停留在角点上
因此,我们只需要匹配角点到角点
Nister 的算法
- 在第一幅图像中找到角点
- 在第一幅图像中提取每个角点处的灰度图像块
- 在第二幅图像中找到角点
- 在第二幅图像中提取每个角点处的灰度图像块
- 找到匹配对 (c1, c2)
• C1 是图像1的一个角点块
• C2 是图像2的一个角点块
• C2 是 C1 的最佳匹配
• C1 是 C2 的最佳匹配 ——为什么还要这么做?因为这是线性分配问题 (linear assignment problem) 的近似解——你会得到更好的匹配。
线性分配问题Linear Assignment Problem
又被称为婚姻问题“Marriage Problem”
最简单的形式:
1) 给定 k 个男孩和 k 个女孩
2) 让每个男孩按希望和其结婚程度给女孩排序
3) 让每个女孩也给男孩排序
4) 婚姻问题决定了男孩和女孩的配对,使总体配对排名之和最大化
说明:一般来说,你可能得不到你最想要的配偶,但平均来说,你几乎不会得到最不想要的。
线性分配问题Linear Assignment Problem
LAP的最优解对于实时特征匹配/跟踪来说计算量太大。
因此,我们使用一个启发式的解决方案,其中特征只有在彼此最匹配的情况下才能配对(即,男孩-女孩匹配对中彼此都将对方排序为第一)
这会丢弃掉很多潜在有用的得分匹配对,但剩下的通常都很好。
推荐阅读