动机
运动估计与分割都从图像证据推断隐藏量,却需要不同算法。光滑运动模型可能导出正定线性系统,二元区域模型则可能导出网络最小割。把两者都称为能量最小化,不代表可以交换它们的保证:前者用二次谱分析,后者用非负容量及流量守恒。
本节把两种方法推导到可核对的程度。光流显示貌似物理的方程如何留下不可辨认的方向;图割显示受限制的非凸二元搜索也能有精确的全局证书。每个构造也给出一个反例,提醒不可随意推广。
亮度不变、运动光滑、固定区域亮度及有理容量都是下文明确使用的假设。它们是建模选择,不是对所有图像的断言。
定义
定义 7.1.1
(光流约束)
若可微图像序列 沿运动点 保持亮度,速度为 ,链式法则给出光流约束
每点只有一个方程,却有两个速度分量。小窗口若假定共同速度,可用行向量 及右端 做加权最小二乘,权重 。未正则化解唯一需要加权梯度张成平面。
定义 7.1.2
(正则化稠密光流能量)
稠密场把水平及垂直分量分组堆成 。 逐像素作梯度与速度的内积, 收集时间导数, 分别计算两分量的空间差分。正则化能量为
幅值惩罚保证唯一性,也引入偏差,不能称作测量到的运动信息。令 ,完整的梯度算法为 。
定义 7.1.3
(二元分割能量及其割网络)
设 ,固定非负一元代价 及非负邻边权重 。二元能量为
网络有源点 、汇点 及每像素一个节点,标记零代表源侧。弧 容量为 , 容量为 ;每个邻对加双向、容量各为 的弧。割容量只计由源侧指向汇侧的弧。
这一步优化期间,用来计算一元代价的区域亮度固定不变。
定理 / 命题
定理 7.1.4
(有限光流求解的收敛)
对称正定,唯一极小解为 。若 ,则任意初值的梯度迭代收敛,且
这是固定线性化亮度模型的保证,不是原非线性变形的全局结论。
第二个结果不再依靠谱控制,而是在刚才定义的网络上给出组合证书。
定理 7.1.5
(精确二元割与有限最大流证书)
上述网络每个二元标记的割容量正好等于 ,每个割也决定一个标记。有理容量先同乘公分母变成整数,再沿剩余源汇路径增广,必在有限步内停止。停止时的剩余可达集合给出最小割,其容量等于可行流值,故对应标记是固定二元能量的全局极小解。
这限制在非负、偏好相同标记的邻边作用。任意多标记或运动能量未必能如此表示;固定区域亮度的全局割,也不等于同时把亮度与标记全局优化。
零容量弧是合法情形,剩余搜索只沿严格正的剩余容量前进;保留这一区别,才能正确处理平局与已饱和的边。
证明思路
证明
(正定性与谱收缩)
对非零 ,,求导即得唯一解。从更新式减去其法方程,误差满足 。谱定理在正交特征基中给出全部因子 ,步长条件使它们都严格落在 内;取最大绝对值便得到几何收敛。若删除幅值项,且 ,唯一性改为需要 ;光滑性本身不能保证。
证明
(割容量、流量下界与有限停止)
标记零的节点在源侧,只付指向汇的 ;标记一的节点只付源指向它的 。邻对同侧付零,异侧恰有一条弧跨割,付 。逐项相加便得能量等式。
可行流不超过容量,且在各非端点守恒。对任意源侧节点集合求和,流值等于离开该集合的净流,不超过外向割容量,这就是下界证书。从零流开始,在正剩余容量中搜索源汇路径,例如用广度优先搜索,再沿路径增加最小剩余容量。正向剩余弧使用未用容量,反向弧允许取消已有流。增广保持容量约束与守恒;整数情形每次至少增加一,而总流以源点外向总容量为上界,因此在有限步内停止。有理容量可先缩放;这个简单论证并不声称对输入位数有良好的复杂度。
停止时取由源点经正剩余弧可达的节点为源侧。所有原来离开该集合的弧已饱和,所有进入该集合的弧流量为零,否则其反向剩余弧会扩大可达集。因此净外向流等于割容量。任意流不超过任意割,这一界便同时证明两者最优。这解释了为何须同时给出流与割,而不是只凭标记的外观判断。
证明透视
割证书在哪里使用每个假设
证明分为三部分,各用不同的假设。能量等式只用标记约定:标记零在源侧,才使 承载 。流量下界用非负性:零流可行,是因为每个容量至少为零;“流值不超过割容量”这一步舍去内向跨割流,是因为它非负。有限停止用整数性:每次增广至少加一,而流值有界,计数论证便能收尾;对任意实数容量,这个计数给不出界。
唯一不显然的一步是停止时割的选法。证明不搜索全部割,而直接取剩余可达集 。关于 的两个事实把不等式变成等式:离开 的弧已饱和,否则正向剩余弧会离开 ;进入 的弧没有流,否则反向剩余弧会离开 。一个流与一个割相等之后,普遍下界同时使该流最大、该割最小,而能量等式把最小性转移到标记上。负容量在第一步就破坏论证,所以下文真正重要的条件是保证 的次模性。
相比之下,运动部分的证明较短:正定性给出唯一性,步长条件给出每个特征方向上的收缩。
例题详解
例题 7.1.6
(平滑不能辨认均匀切向运动)
取 ,亮度方程只有 ,不含 。即使加入空间平滑,任意常数垂直速度的差分都是零,仍然不可分辨。单像素若取 ,最小化 得 。先验带来唯一性,同时水平分量也有偏差;垂直方向的零值不能报告成物体没有垂直运动的测量证据。
例题 7.1.7
(匹配流量的明确二像素割)
两像素亮度为零与二,区域亮度为零与二,用平方误差得到代价对 、,邻权重为一。四个标记 的能量依次为四、一、九、四。源至第一点容量四,第二点至汇容量四,像素间双向容量一,另两条端点弧为零。沿源、第一点、第二点、汇送一单位流;把两像素分在两侧的割容量也是一。匹配的流与割证明 全局最优,不必依靠穷举。
例题 7.1.8
(不对称次模邻对的表示)
若 ,令 、、。则 ,逐一代入可核对。线性项加到一元代价;若一元项为负,从该像素两种代价中都减去较小者,并记录移出的常数,就得到非负容量而不改变最优标记。
一般只要 ,便可解四个标量方程得 、、。次模条件恰好保证边容量非负。先累加所有一元项和常数再建图;忘记常数即使没有改变标记,也会使流值与原能量的证书比较失真。
进一步的配准可取仿射变形 ,参数顺序为 。残差 的 Jacobian 行为
导数在变形后的点计算。加权行向量须张成六维参数空间,才有唯一的未正则化增量。只选三个不共线位置不足以保证强度配准:每个亮度残差只提供一个标量,梯度方向也很重要。每次增量后重新变形、计算导数,并检查原残差;线搜索可拒绝使能量增加的步。由粗到细可改善起点,却不能消除重复纹理与遮挡造成的歧义。
概念视角结构
固定证据与改变未知量的分别
割是在固定一元数据下优化标记,之后重估区域均值就改变了代价,产生新问题。交替进行精确割与非空区域的精确均值,使联合平方误差能量不增加;若区域为空,保留之前的亮度值。这种不增序列仍不保证全局最优。同样地,精确求解线性化配准并不等于全局求解原来的非线性变形。
常见错误
反例模式
排斥邻对不能直接用非负割边
若 、,公式要求 。负容量不符合最大流证明,不能直接放进此网络。这只说明指定标记约定下的吸引式构造失效,并非所有改写都不可能。单个邻对可翻转一个变量的标记来转换作用,但多个相互耦合的邻对未必能用一致的重标记同时修补。
光流测量的是表观亮度运动,反射与光照变化可使它不同于表面的物理运动。光滑惩罚也可能把误差传过真实的运动边界。
常见错误
(交换端点弧的约定)
标记零在源侧时, 必须承载 。若改用 建 ,实际最小化的是每对一元代价互换后的能量。在二像素例中,互换后第一像素的端点容量为 ,第二像素为 ;最小割容量为一并给出 ,而它的真实能量是九,是四个标记中最差的。
常见错误
(迭代上限不是最优证书)
增广程序只有确认不存在正剩余路径,才有停止证书。达到任意迭代上限后,当前流值仍是有效下界,已找到的最佳标记是上界;如实的报告是两者的差距。只有差距为零才证明该标记最优。
总结
亮度不变导出局部与稠密光流,可辨认性须与正则化分开。正定有限二次模型有可证收敛的梯度算法。二元吸引式分割有精确的割表示及最大流证书;次模条件保证本构造的边权非负。非线性变形、变动的区域均值、排斥作用及采样误差仍须各自处理。
练习
练习 7.1.9
(小窗口方程为 、,求未正则化最小二乘速度与结构张量。为何这不同于把第一个方程重复两次?)
基础
解答(2)
- 1
解两个独立方程
两行为 与 ,故 、,解为 。结构张量是 之和,即 。
- 2
与重复约束比较
两个方向各有独立约束。只重复水平方程得到 ,垂直分量仍任意;样本增加不一定增加秩。
练习 7.1.10
( 的特征值为一、四,求合法的常数步长区间,计算步长 的收缩因子,并说明步长 时的情况。)
基础
解答(3)
- 1
代入步长条件
,故条件为 。
依据: 定理要求 。
- 2
计算 的模态因子
因子为 与 ,所以范数收缩因子为 。
- 3
检查端点
第二个因子为 ,该方向的非零误差只反号而不衰减。定理中的上端点必须严格排除。
练习 7.1.11
(邻对值为 ,求非负边权与一元系数,并验证全部四个值。)
核心
解答(2)
- 1
计算系数
,,。
- 2
核对四个标记
故 ,依次给出零、三、一、二。常数为零,此例中所有边及一元容量均非负。
练习 7.1.12
(证明对任意可行流与任意割,割容量减流值非负。若某标记能量为五而某可行流值为四,能证明什么,还有什么未知?)
核心
解答(3)
- 1
写出跨割的流值
流值等于外向跨割流减内向跨割流。
依据: 对源侧节点把守恒式求和。
- 2
逐项估计
关键一步
外向流不超过外向容量,内向流非负,故流值不超过割容量。
- 3
解读数值
最优能量位于四与五之间,候选标记距最优至多一个能量单位。两值相等才证明精确最优;目前不相等,不能确定哪个中间值可以达到。