為何讓擴散依賴對比?
線性熱流沿每條邊傳送亮度,速率與兩端的差成正比。因此即使大跳躍代表有意義的邊界,也會產生相應的大通量。為減輕這種傾向,可以選擇一個隨對比增長較慢的通量。這是一項建模選擇,並不能告訴我們某個跳躍是物件還是噪聲;細小的特徵仍可能消失。
我們在有限圖上精確描述這個選擇,此時邊界約定就是所列的邊:除非明確加入,否則沒有邊越過圖像邊界。這給出無通量模型,但並非連續偏微分方程的證明。以下構造光滑化的是各向異性圖全變分,即各條邊上差分絕對值之和,而不是將每個像素的方向差分組合成歐氏(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,必須改用非光滑論證。