动机
二次平滑把相邻像素的大差异视为特别昂贵,因此能抑制噪声,也会抑制真正的陡峭边缘。全变分改变惩罚的增长速度:差异加倍,成本只加倍而非变成四倍。这导出一个凸最小化问题,极小解可能有完全平坦的区域及其间的跳跃。
“保留边缘”不能理解成辨认每条真实边界。全变分也会降低边缘对比、删去细小物体,甚至把渐变斜坡变成阶梯。本节从有限图模型出发,证明能量真正保证的性质,并展示其局限。有限维存在性不需要借用无限维的紧致性理论;稍后的连续偏微分方程只在明确的光滑假设下推导。
变分法与偏微分方程密切相关,但极小值、梯度流和离散算法是不同对象。能量给出最优条件,梯度流提供下降方向,而时间离散另有稳定性限制。连续方程会消散能量,并不能保证任意步长的数值计算也会如此。
定义
把像素看作有限无向图的 n 个顶点,m 条边各选一个方向。关联矩阵 D∈Rm×n 对由 i 指向 j 的边定义 (Du)e=uj−ui。图全变分为
TV(u)=∥Du∥1=e∑∣(Du)e∣.
反转边的方向只改变绝对值内的符号,故不改变惩罚。在连通图上,Du=0 当且仅当图像为常数。方格上逐条水平、垂直边取绝对值的和常称为各向异性离散全变分;各向同性版本则在每个像素将两个方向差分组合后取欧氏(Euclidean)长度。两者并不相同,尤其对斜边的代价会不同。
对数据 f∈Rn、α>0,考虑
E(u)=21∥u−f∥22+α∥Du∥1.
这是正向算子为恒等映射的去噪模型。去模糊要把拟合项换成 ∥Ku−f∥2/2,唯一性亦须重查。此处容许任意实亮度;若施加物理范围限制,最优条件必须加入约束的影响。
凸函数 g 在 u 的次梯度 q 满足:对所有 v,都有 g(v)≥g(u)+qT(v−u)。绝对值在正数的次梯度为一,在负数为负一,在零则是整个区间 [−1,1]。
这个区间正好描述像素融合;把它随意换成零会漏掉真正的极小解。
定理 / 命题
任意数据与正参数都给出唯一极小解。向量 u 为极小解当且仅当存在 p∈Rm 使
u−f+αDTp=0,pe∈∂∣⋅∣((Du)e).因此 ∣pe∣≤1;差分非零时,pe 必须等于该差分的符号。
在相同图及参数下,若 u,v 分别是数据 f,g 的去噪解,则
∥u−v∥2≤∥f−g∥2.此外 i∑ui=i∑fi;若图不连通,此等式在每个连通分支上分别成立。
均值守恒只适用于此无约束、恒等拟合的差分模型。任意模糊算子、边界处理、亮度惩罚或约束模型未必有相同性质。精确列出假设,可避免把一个特例的优点错误推广到所有复原方法。
证明思路
当 ∥u∥→∞,拟合项趋向无限,而全变分连续且非负。因此在足够大的闭球上可达到极小值。二次项严格凸,全变分凸,故总能量严格凸,解唯一。逐边使用绝对值的次梯度公式即得证书。充分性亦可直接验证:把各次梯度不等式加入 E(v)−E(u),用驻点式消去一次项,留下非负的 ∥v−u∥2/2。
第二个定理对两组数据各使用一次第一个定理的证书。
取 q∈∂TV(u)、r∈∂TV(v),使 u−f+αq=0、v−g+αr=0。把两个次梯度不等式相加得 (q−r)T(u−v)≥0。将两个驻点式相减并与 u−v 取内积,便有
∥u−v∥2≤(f−g)T(u−v)≤∥f−g∥∥u−v∥.若解相同结论显然,否则除以差的范数即可。均值守恒则由 D1=0:把证书左乘全一行向量,惩罚项的和为零。用各连通分支的指示向量可得分支版本。
证明透视
各项控制分别从何而来
每项结论依赖不同的性质,而且都不需要全变分可微。存在性只用到强制性:拟合项无界增长而全变分非负,所以极小值在某个闭球上取得。唯一性用到严格凸性,而严格凸性完全来自恒等拟合项,全变分本身只是凸的。正向算子不是单射时失效的正是这个假设,见“常见错误”中的反例。证书用 ∣⋅∣ 的标量次梯度刻画极小点;零点处的区间 [−1,1] 使融合的边仍能承载力。
稳定性需要第三种性质:次微分的单调性 (q−r)T(u−v)≥0,由两个次梯度不等式相加得到。与两个驻点方程结合后化为 ∥u−v∥2≤(f−g)T(u−v),再用 Cauchy–Schwarz 不等式即可完成。守恒既不用凸性也不用单调性,只用到每个分支指示向量都满足的代数事实 D1C=0。用光滑近似代替全变分或许能简化数值方法,但这些步骤没有一步依赖光滑性。
证书也导出有限维对偶问题。由 ∥Du∥1=∣pe∣≤1maxpTDu,对 u 配方,可得在盒形约束内最大化
αpTDf−2α2∥DTp∥2.
在对偶最优点,原图为 u=f−αDTp。只检查盒形约束并不足以证明某个候选对正确;还须核对其与差分相容的符号条件,或核对原、对偶值相等。
概念视角几何
有界边力与散度
每条边的对偶变量可视为幅度不超过一的力,DTp 将亮度在相邻像素间重新分配。非零差分使力依符号饱和,融合处则可由未饱和的力平衡数据。所有边贡献相加为零,因而均值守恒不是偶然的数值现象。
例题详解
单边由第一像素指向第二,数据为 (0,2)T。若解仍递增,取 p=1,则 DTp=(−1,1)T,证书给 u=(α,2−α)T,在 0<α<1 有效。当 α≥1,改取 u=(1,1)T、p=1/α。此时差分为零,p∈[−1,1] 合法,驻点式也成立。取 α=1/2 得 (1/2,3/2)T:均值保持,但跳跃由二降成一。保留边缘并非精确保留其对比。
若 f=c1,取 u=f、p=0,拟合和全变分同时为零,故为唯一解。更一般地,若 u 是数据 f 的解,u+c1 就是数据 f+c1 的解,因为差分不变、拟合误差亦不变。这说明全变分惩罚的是变化而非亮度本身。改成 ∥u∥1 会抑制大幅常数背景,代表另一种完全不同的先验假设。
两像素图的拉普拉斯(Laplace)矩阵为 L=DTD=(1−1−11)。对 ut=−Lu 作前向 Euler 步得 uk+1=(I−τL)uk。均值不变,差值乘以 1−2τ。初值 (0,2)T、τ=1/4 给下一步 (1/2,3/2)T;若 τ=3/2,差值反号且幅度加倍。连续热流耗散,并不保证这个过大步长也稳定。
一般图上,uTLu=∥Du∥2,所以 L 对称半正定。沿特征向量,Euler 因子为 1−τλ。若最大特征值为正,欧氏不扩张条件是 0≤τ≤2/λmax。对无权图,τ≤1/dmax 则足以令每个更新值成为旧像素与邻居的凸组合。保持非负与范数稳定是不同要求,不应以其中一项代替另一项。
为连接偏微分方程,可取光滑近似
TVε(u)=∫Ω∣∇u∣2+ε2dx,ε>0.
在图像及变分足够光滑、边界条件令分部积分边界项消失时,Euler 方程为
u−f−αdiv(∣∇u∣2+ε2∇u)=0.
负梯度流的右端是 f−u+αdiv(∇u/∣∇u∣2+ε2)。沿满足上述条件的光滑流,能量导数等于负的梯度之 L2 范数平方。这可核对符号,却不是非光滑连续全变分流的存在性证明;后者需要另一套分析工具。
常见错误
零点没有普通导数。若把次梯度区间只保留零,两像素例题中融合状态所需的 p=1/α 就被排除,即使那正是唯一极小解。次梯度不是含糊近似,而是精确描述非光滑平衡的工具。
各向同性与各向异性惩罚不能共用一个未加说明的公式。差分与伴随也须有相容的边界定义;凭外观猜散度可能导致符号相反或引入边界源。实现时可以用任意测试数组核对 ⟨Du,p⟩=⟨u,DTp⟩。
全变分偏好少量非零差分,可能把斜坡变成阶梯,或因小物体的拟合收益不足以抵消边界代价而将其删除。不扩张性比较的是两组数据的输出,并不保证输出比原始数据更接近每一种未知真实图像;这样的断言需要统计模型或指定的信号类别。
调整亮度单位时也应重新解读参数:把数据乘以 s>0,二次拟合项乘以 s2,全变分却只乘以 s,因此同一数值的 α 并不代表相同的权衡。
去模糊时若 K 不是单射,二次拟合项失去严格凸性,而全变分一般也不严格凸;本节的去噪唯一性不能直接照搬,须分析具体的算子与可行集。即使算法可靠地收敛,也可能只收敛到非唯一解集中的某一个。
反例模式
正向算子漏掉一个像素时唯一性失效
待检验的说法:唯一性定理对任何拟合项 21∥Ku−f∥2 都成立。取路径 1−2−3,即 TV(u)=∣u2−u1∣+∣u3−u2∣,并令 K 只观测两端像素:Ku=(u1,u3)T,f=(0,1)T,α=1/4。由三角不等式,
E(u)≥21(u12+(u3−1)2)+41∣u3−u1∣,且等号成立当且仅当 u2 介于 u1 与 u3 之间。右端就是数据为 (0,1)T 的两像素问题,其唯一极小点为 (u1,u3)=(1/4,3/4),值为 21(161+161)+41⋅21=163。因此每个 u=(1/4,s,3/4)T(1/4≤s≤3/4)都是极小点。未被观测的中间像素是 kerK 中的一个方向,全变分沿此方向不变,所以能量不是严格凸的。若 K 是单射,严格凸性及唯一性便得以恢复。
总结
有限图全变分去噪有唯一解、次梯度证书、数据不扩张性及均值守恒。对偶变量解释了像素如何精确融合。二次扩散和光滑全变分流都来自能量下降,但时间离散必须另查步长及边界。这些性质属于指定模型,并不自动把每条输出边缘认定为真实物体边界。
练习
练习 2.1.8
(对单边数据 (a,b)T、a≤b,求分离与融合两种情形的解,并指出参数分界。)
基础
解答(3)
1处理分离情形
令 m=(a+b)/2。若 α<(b−a)/2,取 p=1,证书给出 u=(a+α,b−α)T;其差 b−a−2α 为正,符号条件成立。
2处理融合情形
若 α≥(b−a)/2,取 u=(m,m)T、p=(b−a)/(2α)∈[0,1],则 u−f+αDTp=0;平坦的边允许 [−1,1] 中的任何 p。
3核对分界
当 α=(b−a)/2 时两式都给出 (m,m)T,唯一性排除了其他解。参数分界为 (b−a)/2。
练习 2.1.9
(在任何有限图上,证明数据加上常数后,去噪解也加上同一常数。若图不连通,为何每个连通分支可以分别加常数?)
基础证明
解答(3)
1比较两个能量
令 v=u+c1。v 对数据 f+c1 的拟合项等于 u 对 f 的拟合项;又因 D1=0,有 Dv=Du。
2转移极小点
映射 u↦u+c1 是候选图像之间保持能量值的双射,所以把极小点映到极小点。
3推广到分支
在每个连通分支上分别为常数的向量也属于 kerD,同样的代换即证明分支版本。
∎
练习 2.1.10
(设 D=(−1,1)、f=(0,2)T、α=2。检验 u=(1,1)T、p=1/2 是否满足原始证书及对偶盒形约束,并计算原始与对偶目标值。)
基础
解答(3)
1检验证书
此时 DTp=(−1/2,1/2)T,故 u−f+2DTp=(1,−1)T+(−1,1)T=0。复原后的差分为零,所以 p=1/2∈[−1,1] 是合法的次梯度。
2计算两个目标值
原始值为 21(12+(−1)2)=1;对偶值为 2⋅21⋅2−24((1/2)2+(1/2)2)=2−1=1。
练习 2.1.11
(对拉普拉斯矩阵正特征值 λ 的特征向量,求使其幅度不增加的所有非负 Euler 步长。两个端点处发生什么?并与严格衰减相区分。)
核心
解答(3)
1化为幅度因子
一步把该模态乘以 1−τλ,故条件为 ∣1−τλ∣≤1,即 0≤τ≤2/λ。
2检查端点
τ=0 时模态不变;τ=2/λ 时符号反转而幅度不变。恰在 0<τ<2/λ 时严格衰减。
3说明正性的作用
零特征值对应分支常数模态,任何步长下都不变,因此假设 λ>0 不可省略。