为什么使用隐式步?
上一节的光滑边扩散用可微函数近似 ;但未经光滑化的绝对值在边差为零处没有普通导数。除以边差,或者硬性规定该处导数为零,都不能解决这个奇异点。另一种做法是一次求出整幅下一步图像:在贴近旧图像与减小全变分之间取得平衡。即使某些边恰好变平,我们仍能证明这个有限维的一步存在且唯一。
定义 2.3.1
(图全变分隐式步)
设 为有 个顶点的有限无向图,边权 。给每条边取定一个方向;若边从 指向 ,令 。定义
其中 是旧图像, 是新图像, 控制这一步的强度。改变边的方向不会改变 或 。这是逐边求和的各向异性图全变分,其他离散方式的最优性条件可能不同。允许边集为空,此时 。
存在性与边力证书
定义 2.3.2
(次梯度与次微分)
对凸函数 ,若对每个 都有 ,就称 。标量绝对值的次微分在 时是 ,在 时是 ,在 时是整个区间 。
这个区间不可省略:平坦的边可以传递非零的力,而边差仍为零。
定理 2.3.3
(唯一的一步及其证书)
对每个 及 ,上述最小化问题恰有一个解。 是这个解,当且仅当存在边力 满足
也就是说,非平坦边上 ;平坦边上可取任意 ,但仍须满足顶点方程。图像 唯一,证书 却未必唯一。
证明
(由强制性得存在,由投影得证书)
目标函数连续;当 时二次项趋于无穷,而非负权重保证 ,所以目标函数是强制的,从而取得最小值。二次项严格凸, 是凸函数,故最小值点唯一。
为了在不对 求普通导数的情况下证明证书,设 、。两者都是紧致凸集,并且
令 为 在 上的欧氏(Euclidean)投影。投影不等式给出:对所有 ,。设 ,则 使 在 上取得最大值。取 使 。由于 使 最大,有 。每条边都满足 ;求和后取等号,所以每一项都取等号,这就得到证书。对任意 ,支撑函数公式给出 。展开二次项并利用 ,可知 处的目标值至少比 处大 。所以 是唯一解。反过来,任何具有证书的 也满足同样的不等式,因而就是解。这同时证明了 。
证明透视
什么取代了缺失的导数?
三个要素承担了导数通常的作用。支撑函数表示 把不光滑的和写成紧致凸集上线性函数的最大值;这里需要非负权重,因为若某个 为负, 就是空集。其次,在 上的投影不等式扮演驻点方程的角色:它说明 使 最大,这正是 为次梯度的含义。最后,由顶点力还原边力依靠一个求和论证:逐边的界 加起来是等式,所以每一条都是等式。这就是非平坦边上的符号条件;在平坦边上它不施加任何限制,盒子允许整个区间。
二次项提供余量 ,同时给出图像的唯一性和反方向的结论。可能不唯一的是满足 的边向量 :两种选择相差 的核中的一个元素,而这个核非零恰好当图中有圈。若图是森林, 是单射,即使存在平坦边,边力也唯一。
能量、守恒及对数据的依赖
以 作为比较对象,得到基本能量不等式:
因此全变分不增,但仅凭这一点无法推断各个像素值的变化。证书给出更多结论。
命题 2.3.4
(一步的能量、守恒与稳定性)
设 是由 以参数 得到的一步。
- 。
- 对正权边子图的每个连通分量 ,。
- 若 是在同一图、同一权重和同一 下由 得到的一步,则 。
证明
(证书的三个推论)
能量估计:对 的次梯度不等式取 ,得到
守恒:用示性向量 乘顶点方程,得 。分量 只在恰有一个端点属于 的边上非零,而这样的边权重为零,所以 。因此 。孤立顶点也是连通分量。
稳定性:对两个输入 及其输出 ,记 与 。把两个次梯度不等式相加,得 ,所以
因此 。
第二条说明,不存在或权重为零的边不传递任何强度。第三条就是非扩张性,它比较的是相同 、图和权重下的两次运算;它并不保证严格收缩,因为常数输入保持不变。
两个像素:精确阈值
例题 2.3.5
(边何时变平)
取一条权重 的边, 且 。均值 守恒。记 、,目标函数化为 ,其唯一最小值点为
当 时,边力 ,对比度减少 。若 ,两个像素恰好在均值处汇合,相容的平坦边力为 ;取等号时同一公式仍然适用。例如 、、、 时,;改用 则得 ,且 。
在更大的图上,平坦边并不与相邻的边脱钩。
例题 2.3.6
(被相邻边拉动的平坦像素对)
取单位权重路径 ,边的方向为 和 ,、。此时 ,顶点方程为
尝试“第一条边平坦、第二条边递增”的模式。第二个条件迫使 ,故 、。平坦条件 给出 ,所以 。第二个边差为 ,与 相容,证书成立,这就是所求的一步。总和 守恒。能量估计也可以验证:、、,故 。
常见错误
(以为平坦像素对会在自身均值处汇合)
在上面的路径例子中,像素 和 在 处合并,而不是在它们旧值的均值 处。这对像素的总和并不守恒,因为通往像素 的非平坦边把边力 传入了这一对。守恒只对正权图的连通分量成立,而不对任意一组合并的像素成立。
反例模式
零边差不代表零边力
取 、、,上面的解为 ,但顶点方程要求 。若仅因输出边差为零就令边力为零,会得到 ,它并不是最小值点。不可微性要靠一个可供选择的力的集合来处理,而不是一律取零。
例题 2.3.7
(证书构成整个区间的三角形)
取单位权重三角形,边的方向为 、、,常数图像 。这一步是 ,因为所有边差为零,顶点方程变为 。在顶点 它是 ,在顶点 是 ,在顶点 是 。因此每个环流 ()都是证书。图像唯一,证书却构成一个区间,因为圈使 具有非零的核。
可以反复令 ,用同一个正数 计算下一步。每一步都存在且唯一,使全变分不增,并保持每个正权连通分量的总和。这些离散结论本身并不能建立连续时间的奇异全变分流、光滑化极限或连续偏微分方程的结果。
练习
练习 2.3.8
(单条边权重为 ,,。求新图像和一个有效的边力。)
基础
解答(2)
- 1
比较边差与阈值
初始边差 ,,故新边差为 。
- 2
求图像与边力
均值为 ,得 。取从 到 的方向,顶点方程 给出 ,它满足 及符号条件。
练习 2.3.9
(图有两个连通分量,它们之间没有边:单位权重的边 与 。取 、,求这一步的结果并解释各分量的均值。)
基础
解答(2)
- 1
分别处理每个分量
两个分量互不影响,每个分量上 。边差 和 都不超过 ,所以两条边都变平。
- 2
在每个分量上使用守恒
结果是 。两个分量的均值 和 (总和 和 )都保持不变;仅知道全图均值 不足以恢复两者。
练习 2.3.10
(证明若 在每个正权连通分量上都是常数,则这一步恰为 。非扩张性能否保证任意两个不同输入之间的距离严格减小?)
核心
解答(2)
- 1
在 处计算目标函数
所有正权边差都为零,所以 。目标函数非负,且在 处为零,因此唯一最小值点就是 。
- 2
回答收缩的问题
不能。两幅不同的常数图像在这一步下都不变,所以它们的距离不减小。
练习 2.3.11
(直接用证书证明 ,并解释它为什么比比较目标值所得的估计更强。)
核心证明
解答(2)
- 1
在 处使用次梯度不等式
由于 ,有 。
- 2
比较系数
∎只比较 与 处的目标值,得到的系数是 。证书把它加倍,因此 的同样减少量只允许图像移动一半的平方距离。