動機
二次平滑把相鄰像素的大差異視為特別昂貴,因此能抑制噪聲,也會抑制真正的陡峭邊緣。全變分改變懲罰的增長速度:差異加倍,成本只加倍而非變成四倍。這導出一個凸最小化問題,極小解可能有完全平坦的區域及其間的跳躍。
「保留邊緣」不能理解成辨認每條真實邊界。全變分也會降低邊緣對比、刪去細小物件,甚至把漸變斜坡變成階梯。本節從有限圖模型出發,證明能量真正保證的性質,並展示其局限。有限維存在性不需要借用無限維的緊緻性理論;稍後的連續偏微分方程只在明確的光滑假設下推導。
變分法與偏微分方程密切相關,但極小值、梯度流和離散算法是不同對象。能量給出最優條件,梯度流提供下降方向,而時間離散另有穩定性限制。連續方程會消散能量,並不能保證任意步長的數值計算也會如此。
定義
把像素看作有限無向圖的 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 不可省略。