同一幅图像的两个问题
去噪模型要为每个像素求出一个实数强度;二元分割则要决定哪些像素属于目标物体。两者的输出不同,但水平集的边界把它们联系起来。若一条边两端的强度分别是 和 ,它恰好在 时跨过水平 。因此这条边的对比度等于它所跨过的水平区间的长度。把这一观察对所有边求和,就能把全变分写成边界代价的积分。
定义 2.4.1
(图全变分与割)
设 是顶点集 非空的有限无向图,每条边 有非负权重 。对 和 ,定义
每条跨越边界的无向边只计一次。允许边集为空,也允许权重为零。记 ,并始终使用严格不等号。
下面的有限维结论不需要假设几何网格、光滑性或概率模型。
定理 2.4.2
(有限图余面积公式)
对每个 ,
被积函数是有界阶梯函数,并且除恒为零的情形外具有有界支撑,所以这是普通的有限积分。
证明
(逐边写成对水平的积分)
对任意实数 ,示性函数 与 恰好在 之间的半开区间上取值不同。因此
对每条边应用此式,再交换有限和与积分。固定 时,加权示性函数差的绝对值之和恰好是 。端点的取法只改变有限多个水平,不影响积分。证毕。
常见错误
(把每条跨界边算了两次)
对满足 、 的有序对 求 的和是正确的;但若对所有有序对求 的和,每条跨界边都会被算两次,对有序对求 的和也有同样问题。如果只把其中一个量加倍,余面积恒等式看上去就差了一个因子二。这里两个和都对无向边求和,每条边只计一次。
例题 2.4.3
(加权三角形上的余面积公式)
取顶点 及全部三条边,权重 、、,并令 。则
当 时 ,当 时 为空集,两者的割都为零。当 时 ,跨界边为 和 ,所以割值 持续一段长度为 的区间。当 时 ,跨界边为 和 ,所以割值 持续一段长度为 的区间。积分为 。边 跨过 中的每个水平,这正是它的贡献 ;图不必是链。
一幅去噪图像提供许多最优割
固定数据 和 ,考虑二次全变分问题
目标函数连续、强制且严格凸,因此存在唯一的极小点。
定义 2.4.4
(水平 的二元目标)
对水平 ,定义二元目标
选入满足 的像素会减小数据项;被选像素与未选像素之间的边界则带来代价。
这个二元目标依赖于 :我们并不声称去噪图像的阈值集合能使任意分割能量最小。
定理 2.4.5
(阈值最优性)
对每个实数 ,严格上水平集 在 的所有子集中使 最小。 的极小点未必唯一。随 变化得到的集合相互嵌套,因为它们来自同一个 。
证明
(在每个上水平集边界上都取等号的边证书)
给每条边取定一个方向;对方向为 的边定义 。图全变分的最优性证书给出边向量 ,满足
为说明证书从何而来,可把 正交投影到紧致凸集 上。投影不等式给出极小点 ,并使全变分的支撑函数表示逐边取等号。反过来,证书结合次梯度不等式也能证明最优性。
对任意子集 ,盒约束给出 。对 则取等号:跨界边的强度差非零,其方向符号与示性函数差相同,证书迫使 等于相应的带符号权重;非跨界边的贡献为零。因此对每个 ,
第一个不等式成立,是因为 恰好选入所有负项 ,并排除所有正项;零项选入与否均可。第二个不等式利用 和盒约束。这就证明了结论对每个 都成立,包括等于某个像素值的水平。
证明透视
一张证书,为每个水平提供下界
把 代入二元目标,对每个子集 得到
证书的每一部分各司其职。驻点条件使这个改写成立。盒约束 使括号对每个 都非负,这是权重唯一出现的地方。符号条件使括号对所有上水平集同时为零,因为跨过 的某个水平集的每条边都有 ,且符号与 相同。剩下的 恰在选入全部负项时最小,这正是上水平集的定义;零项就是并列的来源。整个证明没有用到余面积公式:对 取平均的恒等式无法说明每个水平各自最优。
非严格集合 也是极小点。只需取一个略低于 的水平,使两者之间没有像素值,再对有限多个仿射目标值取极限。出现相等时,其他极小点未必是这两个集合之一。
三像素计算
例题 2.4.6
(有两条边的链)
考虑单位权重的链 ,令 、。边从左指向右,取 和 。则 ,且 。 的两个分量都为正,所以 满足边证书,因此这个 就是唯一的全变分极小点。
当 时,上水平集为 。割只含边 ,且
作为比较,、、。定理比较的是全部八个子集,而不只是这几个。当 时,严格阈值给出 ,非严格阈值给出 ,两者的值都是 。中间像素恰好等于阈值,于是出现真正的分割并列。
第二个例子说明,水平等于最大去噪值时会出现并列。
例题 2.4.7
(对比度部分收缩的两像素)
取一条权重为 的边,、。边的方向为 ,取 ,得 。其差分为 且 ,证书成立,所以 是极小点。对比度从 收缩到 ,均值 不变。
当 时 。在 ,四个子集给出 、、 和 ,所以 是唯一的极小点。在边界情形 ,严格集合为空集,;非严格集合 的 。另外两个子集分别给出 和 。正如定理及关于非严格集合的说明所预言,两种阈值约定都给出极小点。
反例模式
对去噪图像取阈值不等于对原数据取阈值
两个顶点之间有一条单位权重的边,令 、,全变分极小点为 。在 ,严格集合是空集,非严格集合是两个顶点;两者的 都为零,都是极小点。直接对数据取阈值给出 ,其目标值为 ,在此例中也碰巧最小。但在 ,数据阈值集合仍是 ,其值为 ,而两个顶点一起选入的值为 。因此,直接对含噪数据取阈值一般并不等同于对全变分解取阈值。
练习
练习 2.4.8
(四顶点单位权重链上,。列出各像素值之间开区间上的不同严格上水平集,并用数值验证余面积公式。)
基础
解答(3)
- 1
列出上水平集
当 时集合为 ;当 时为 ;当 时为 ;当 时为 ;当 时为空集。
- 2
计算它们的割
割值依次为 ;例如 被全部三条边跨过。
- 3
比较积分与全变分
积分为 ,等于 。孤立端点对积分没有贡献。
练习 2.4.9
(两个顶点由一条权重为 的边相连,数据为 ,其中 ,且 。求去噪图像,以及使其严格上水平集只含一个顶点的阈值范围。)
核心
解答(2)
- 1
求去噪图像
均值 保持不变,输出对比度为 ,因此 。当 时证书为 ;当 时 可行。
- 2
读出单点阈值
严格上水平集为单点 当且仅当 且 。若 ,则不存在单点的严格上水平集。
练习 2.4.10
(在 、 的链例子中,求 的所有极小点,并解释为什么只看严格上水平集会漏掉一个。)
核心
解答(3)
- 1
列出数据项
在 ,各像素的项 为 ,每条跨界边的代价为 。
- 2
枚举八个子集
,。其余六个子集的值为 (空集)、()、()、()、()和 ()。
- 3
确定极小点
极小点恰好是 和 。严格集合 排除了去噪值等于 的像素,因此只找到其中一个。
练习 2.4.11
(对任意数据,证明当 时 使 最小,当 时 使其最小。第二个范围的端点处极小点是否一定唯一?)
基础
解答(2)
- 1
应用阈值定理
若 ,则每个 ,故 ;若 ,则没有 ,故 。阈值定理说明这些集合使 最小。
- 2
检验端点处的唯一性
在 处可能不唯一:在 、、 的双顶点例子中, 时空集与 的 都等于 。