动机
划痕或传感器故障可能使部分像素缺失,而附近像素仍可使用。若直接用零填补,就等于把没有测量误当作测得黑色。另一种做法是寻找与已知数据一致、同时变化平缓的图像。对于像素图,最简单的平滑度指标是相邻像素差的平方和;使它最小的图像便把观测值延伸到损坏区域。
常见错误
(用零填补缺失像素)
零是一个测得的亮度,不是“未知”的代号。在路径 上观测值为 ,零填补 制造了两条人为边缘,能量为 ;常数填补 与所有观测一致,能量为 。
这个模型的好处是条件清楚:若预期亮度逐渐变化,它可能合理;但它不知道划痕后面是否有边缘或纹理。以下在有限加权图上讨论,不把离散结论直接当成连续模型的结论。图和权重决定何谓“相邻”。
定义
设 是有限无向图。每条边 的权重满足 ;不存在的边权重为零。把顶点分为已观测像素 和未知像素 ,在 上固定测量值 。对任意满足 ()的延拓定义 Dirichlet 能量
每条无向边只计一次。若顶点的加权度 ,其邻居加权平均为 。未知顶点满足 时称为调和的;等价地,。孤立的未知顶点没有这样的平均值,而且其取值不影响能量。
定理/命题
定理 1.5.1
(存在性、唯一性与边界条件)
假设 的每个连通分量都含至少一个已观测顶点,则满足观测值约束的能量最小解存在且唯一;它也是每个未知顶点都调和的唯一延拓。在每个连通分量内,解的值介于该分量已观测值的最小值和最大值之间。
定理 1.5.2
(能量比较)
在相同假设下,设 是调和延拓,另一个可行延拓写为 ,其中 于 。则
除非 ,右边严格为正。因此调和方程给出的是全局最优证书,不只是驻点条件。
证明或证明思路
证明
(存在性、唯一性与能量恒等式)
对在 上为零的 ,令 。若 ,由权重为正可知每条边两端的 值相同,因此每个连通分量上的 是常数。每个分量都含一个 的观测点,故 处处为零。所以 在自由变量空间上正定。该空间有限维,其单位球面紧致, 在其上的最小值为正;由此能量具有强制性,必达到最小值。正定性又给出严格凸性和唯一性。若 为空,唯一可行图像就是 ,其余结论显然成立。
对自由变量求偏导,得到 ,所以最小解必须调和。反过来,对 展开平方:
交叉项按顶点收集后是 。未知顶点处内和为零,观测顶点处 ,所以交叉项消失。这证明了能量恒等式及全局最优性,并说明调和延拓是唯一的。
证明
(离散最大值原理)
假设 在某连通分量的最大值 大于该分量所有观测值。取得 的顶点必为未知顶点;由于其分量含观测点,它必有邻居。它等于邻居的正权平均,而邻居均不大于 ,所以每个邻居也取得 。沿路径重复这一论证,最终到达观测顶点,产生矛盾。对 使用相同推理即得下界。
证明透视
为何每个分量都需要观测值
锚定假设被使用了三次,每次作用不同。在唯一性证明中,它消去唯一的不可见方向:能量只衡量差值,所以在一个分量上统一加常数不会改变任何量,除非有观测值把这个常数固定。能量恒等式本身对任何调和 都成立;锚定只用来保证其右边在 时严格为正,正因如此,调和性是全局证书,而不只是驻点检验。在最大值原理中,它使传播论证得以终止:沿边追踪相等的最大值,必须到达固定的观测值,否则论证什么也证明不了。
正权重也在同样的地方使用。零或负权重会破坏“零能量迫使相邻值相等”这一步,也会破坏“若不大于某值的数的平均等于最大值,则全部相等”这一步。
例题
例题 1.5.3
(一段受损的线)
四个顶点构成单位权路径 ,其中 、,顶点 1、2 的值缺失。调和方程为 和 ,解得 、。三条边的差值均为 1,所以 。能量比较恒等式保证其他填法的能量更大。这里得到线性插值是因为路径权重和间隔均匀,并非所有图像坐标上的调和延拓都是线性的。
例题 1.5.4
(权重不同的连接)
一个未知顶点 与已知值 0、6 相连,权重分别是 2、1。方程 给出 。较强的连接把解拉向零。若直接取算术平均 3,就忽略了所选图的权重,并非能量最小解。
例题 1.5.5
(边界也可能有噪声)
若第一例右端测量值从 3 变成 4,精确插值所得为 。被当作可靠边界的像素若有误差,误差会传到填补区域。精确匹配是一种建模选择;若观测有噪声,可考虑对观测像素加入数据保真项,但那时不必精确匹配观测值,上述定理也须相应调整。
常见误区
反例模式
平滑填补未必恢复边缘
假设四顶点路径的真实图像是 ,却只观测到两个端点。调和填补为 ,没有恢复真实的突变。另一幅真实图像 却给出完全相同的端点观测;仅凭数据无法区分二者,二次模型选择的是平滑解。最大值原理不保证所选图像就是事实。
反例关乎模型选出什么;下一个错误则关乎它是否选得出任何东西。
常见错误
(把定理用于没有锚定的分量)
若某分量没有观测顶点,定理不适用。例如两个未知顶点由一条边连接,则每个常数对 都是最小解;孤立的未知像素更没有约束。加入一个小的对角惩罚项会选定某个值,但它改变了模型,不能把选出的值误认为数据提供的信息。
下面的视角把调和方程与求解它的任何程序区分开来。
概念视角几何
平均关系是方程,本身还不是算法
在解上,每个自由像素等于邻居的加权平均。不断用当前邻居平均更新缺失像素是一种可能的迭代方法,但其收敛性取决于更新规则和图;单有平均方程并不能证明迭代收敛。迭代中也必须保持边界观测值固定。
总结
二次图像修复是边值问题:每个缺失像素平衡它与邻居之间的加权差。每个图分量至少有一个边界观测值,便可保证存在性、唯一性、全局能量证书及最大值原理。这些保证属于所选平滑模型;要保留尖锐边缘或准确恢复未观测结构,还需其他假设或先验。
练习
练习 1.5.6
(单位权路径 的两端分别固定为 和 。求缺失的中点及其能量。)
基础
解答(2)
- 1
使用调和关系
。
- 2
计算能量
。
练习 1.5.7
(一个缺失顶点连接到值为 和 的顶点,权重分别为 和 。求其值;当第二条边的权重从正值趋于零时,解趋于什么?)
基础
解答(2)
- 1
解加权方程
给出 。
- 2
改变权重
若第二权重为 ,则 。权重恰为零时第二条边不存在,图本身已改变。
练习 1.5.8
(一条路径两端固定为 和 ,中间只有一个缺失像素。直接证明中点从最优值改变 时能量增加 。)
基础
解答(2)
- 1
求最优值
调和关系给出 ,能量为 。
- 2
加入扰动
当 时,能量是 ,恰好增加 ,与比较恒等式 一致。
练习 1.5.9
(一个图有两个连通分量,只有其中一个包含观测点。解释为何填补不唯一,并描述没有观测点的分量上的全部最小解。)
核心
解答(3)
- 1
分开两个分量
两个分量之间没有边,能量是两者能量之和,可以分别最小化。
- 2
在无观测分量上最小化
关键一步
该分量上的最小解恰为所有常数向量,而任意常数都允许。
依据: 连通分量的能量为零,当且仅当相邻值都相等。
- 3
结论
无论已锚定分量的唯一解是什么,全图都有无穷多个全局最小解。