为何让扩散依赖对比?
线性热流沿每条边传送亮度,速率与两端的差成正比。因此即使大跳跃代表有意义的边界,也会产生相应的大通量。为减轻这种倾向,可以选择一个随对比增长较慢的通量。这是一项建模选择,并不能告诉我们某个跳跃是物体还是噪声;细小的特征仍可能消失。
我们在有限图上精确描述这个选择,此时边界约定就是所列的边:除非明确加入,否则没有边越过图像边界。这给出无通量模型,但并非连续偏微分方程的证明。以下构造光滑化的是各向异性图全变分,即各条边上差分绝对值之和,而不是将每个像素的方向差分组合成欧氏(Euclidean)范数的各向同性全变分。
正则化图能量
定义 2.2.1
(光滑化图全变分能量及其梯度流)
设 是有 个顶点的有限简单无向图(没有自环或重复边)。任意选择每条边的方向,以 表示关联矩阵:若边 由 指向 ,则 。正权重 表示所选各边的相对强度。对 ,定义
减去常数使常数图像的能量为零,却不影响方程。负欧氏梯度流为
反转一条边的方向会同时改变 的相应行及奇函数通量的符号,因此方程不变。在顶点 ,同一方程可写成
对比小时,导通系数趋近 ;对比大时则较小。通量的绝对值趋近 ,而不是无界增长。若图有多个连通分支,以下关于均值及最终常数的叙述分别适用于每个分支。
存在性、守恒与稳定性
定理 2.2.2
(全局有限维流)
对每个初始图像 ,方程在所有 都有唯一解。每个连通分支的总和守恒,其最小值不会下降,最大值不会上升。此外,
允许初始数据不同的两个解 满足 。在每个连通分支上,解趋向该分支的初始均值。这些结论需要上述的正 和正权重,且针对此有限图。
证明
(Lipschitz 向量场、边的抵消与谱隙)
导数 属于 。其 Hessian 满足 ,故沿线段积分梯度可知向量场全局 Lipschitz,其 Lipschitz 常数至多为 。有限维常微分方程的标准定理给出唯一全局解。对分支指示向量 ,有 ,故其总和守恒。能量恒等式则由链式法则及 得出。
为证明最大值原理,注意任意时刻在某连通分支中达到当前最大值的每个顶点,其导数都非正,因为邻点的值不更大。有限个可微坐标的最大值之右上导数,是达到最大值的坐标导数中最大的一个,故非正。由 Dini 导数的单调性引理,该分支的最大值不增;对 使用相同论证便得最小值的结论。
由于 递增,令 、,有
因此流不扩张,但未必严格收缩:两个不同的常数图像始终不同。为证明连通分支上的收敛性,以下把 限制在此分支 ,令 为其守恒均值, 亦为该分支上的向量。令 为 限制在此分支的加权拉普拉斯(Laplace)矩阵。该分支的初始极差 对所有时间的每条边差分给出上界。所以
矩阵 的核恰为常数向量:由 及正权重可知核中的向量沿每条边相等,再用连通性得到常数。若分支至少有两个顶点,其最小非零特征值 因而为正。由 与常数向量正交,。由 Grönwall 不等式,。孤立顶点本来就是常数,故收敛得证。这个估计是界,并非对比衰减的精确公式。
证明透视
向量场的哪个性质给出哪项结论
定理包含五项结论,证明分别从向量场的四个不同性质得到。全局存在性只用到界 :它使向量场全局 Lipschitz,因此解不会在有限时间内爆破;这是 不可缺少的第一处。守恒只用到代数恒等式 ,对任何边通量向量都成立。最大值原理用到导通系数 的符号,不扩张性则用到 的单调性。下面的反例保留了正的导通系数,却失去单调性,收缩估计也随之失效。相反,仅靠能量耗散推不出这四项中的任何一项。
收敛的论证是唯一非常规的一步。它需要导通系数的下界,而对比增大时导通系数会变小。最大值原理恰好提供这个下界:极差始终不超过初始值 ,所以每个导通系数至少为 。于是可以与线性拉普拉斯矩阵比较;连通性使其核恰为常数向量,正的谱隙 迫使相对于守恒均值的偏差衰减。顺序很重要:若不先证明最大值原理,速率常数就不能对所有时间一致成立。
安全的显式步
令 、,以及 。对至少有一条边的图,前向 Euler 法为
这个格式的两种不同性质,分别由两个不同的步长界保证。
命题 2.2.3
(两个充分的步长条件)
设图至少有一条边,并令 。
- 若 ,则每个 都是 与 的邻点值 的凸组合。因此每个分支的极差不会扩大,各分支总和守恒。
- 若 ,则对每个状态 都有 。
证明
(凸组合与下降不等式)
令 ,则 ,且
邻点系数非负,其和至多为 ,所以第一个系数也非负,这就是凸组合的结论。把更新式在一个分支上求和,总变化为零,因为每条边的通量以正负号各出现一次。
至于能量,Hessian 为 ;由 ,其算子范数至多为 。沿线段对梯度积分可得下降不等式 。取 ,得到
而当 时括号非负。
两个界都只是充分条件,对某幅特定图像未必最精确。能量界取等号时,不能仅凭此证明迭代收敛;极差保持与能量下降是不同的性质,应分别检验。没有边的图,其向量场为零,不需要步长限制。
常见错误
(沿用热方程的步长)
对权重为 的线性热流,显式步长 使每次更新都是凸组合。这里导通系数可高达 ,安全界因此是 ,会随 缩小。在一条单位边上取 、、,通量为 ,故 ,极差由 增至约 。步长必须随 调整。
例题详解
例题 2.2.4
(两像素的一步)
取一条单位权重边,,。对比为 ,初始速率为 。取 ,一步 Euler 法得到 。总和仍为 ,两个值都在 与 之间。更新后对比为 ,而非零:一步既不会完全保留,也不会完全消除边缘。
对连续流,写 得 。在 时,瞬时速率为 。单位系数的二次热流模型则给出 。这只是特定尺度下的速率比较;改变 也会改变小对比时的速率。
常见错误
(通量有界不等于保留边缘)
边上通量的绝对值永远不超过 ,所以大跳跃被平滑得比热流慢,但仍然会被平滑。由定理,每个连通分支都收敛到其均值;在上例中,只要 就有 。在有限图上,这个流只是推迟边缘消失,并不能阻止它。若要用此流保留边缘,就取决于在有限时间停止。
例题 2.2.5
(带权的三像素行)
边 的权重为 , 的权重为 ,取 、。第一条边的通量为零,第二条为 。因此 ,速率之和为零。带权最大度数为 ,故 足以使每个状态的显式步保持极差。
直觉何时会失效
反例模式
递减导通系数未必产生不扩张流
改在一条单位权重边上考虑通量 。其导通系数随对比下降,但当 , 为负。以两个均值为零的图像作初值,其正对比分别为 、。初始时 、,故 :两解的欧氏距离初时增加。不扩张性证明所用的单调性已失效;这个计算并没有宣称此替代模型的每条轨迹都无界增长。
过大的 Euler 步也可能破坏平滑效果,下面的计算说明这一点。
例题 2.2.6
(同时超出两个界的一步)
取一条单位权重边,、、。此时 的特征值为 和 ,故 ,能量界要求 ;极差界 也是 。对比 满足 ,所以
其绝对值大于 ,因此能量 增加,尽管连续流会耗散能量。新值 也离开了初始范围 。命题的两项结论在此都不成立,而这一步也同时违反了两个假设。
此有限例子和光滑能量都不能证明 时奇异连续全变分流的存在性、唯一性或收敛性。
练习
练习 2.2.7
(两像素单位权重边取 、初值 。求瞬时导数,并说明均值守恒。极限图像是什么?)
基础
解答(3)
- 1
计算导数
差为 ,且 ,故 。
- 2
检验均值
在每个时刻,两个导数都是 ,由边的抵消其和为零,所以均值保持初值 。
- 3
确定极限
图是连通的,由定理,解趋于以守恒均值为值的常数图像,即 。
练习 2.2.8
(图有两条不相连的边 和 ,初值为 。求极限图像,并说明为何仅靠全局均值不足以确定它。)
基础
解答(2)
- 1
分别处理两个分支
没有边连接 与 ,两者之间不交换亮度。它们的守恒均值为 和 。
- 2
写出极限
每个分支趋于自己的均值,故极限为 。全局均值 虽然守恒,却不能确定两个各自的总和 和 。
练习 2.2.9
(对上述带权三像素行,从 以 计算一步 Euler 法,并检验极差和总和。)
基础
解答(3)
- 1
检验步长界
带权最大度为 ,且 ,故 满足命题的极差条件。
- 2
走一步
例题中的导数为 ,所以新图像为 。
- 3
检验极差与总和
三个值都在 内,总和为 ,与命题的预测一致。
练习 2.2.10
(证明二次型不等式 ,并由它推出上面使用的 Hessian 界。解释为何不能在证明中代入 。)
核心证明
解答(3)
- 1
证明二次型不等式
由于 ,而每条边都有 ,每一项至多为 。求和即得 。
- 2
过渡到算子范数
Hessian 对称半正定,其算子范数就是最大特征值,即单位向量上二次型的最大值;这个最大值至多为 。
- 3
说明 的作用
∎当 时,界 没有定义,且 在零处不可微,那里根本没有 Hessian,必须改用非光滑论证。