為甚麼使用隱式步?
前一節的光滑邊緣擴散以可微函數近似 ;但未經光滑化的絕對值在邊差為零時沒有普通導數。除以邊差,或硬把該處導數定為零,都不能解決這個奇異點。另一種方法是一次求出整幅下一步圖像:在貼近舊圖像與減少全變分之間取得平衡。即使某些邊恰好變平,我們仍可證明這個有限維步驟存在而且唯一。
定義 2.3.1
(圖全變分隱式步)
令 為有 個頂點的有限無向圖,邊權 。任選每條邊的方向;若邊由 指向 ,令 。定義
其中 是舊圖像, 是新圖像, 控制一步的強度。反轉邊的方向不改變 或 。這是逐邊相加的各向異性圖全變分,其他離散化方式的最優條件可能不同。允許空邊集,此時 。
存在性與邊力證書
定義 2.3.2
(次梯度與次微分)
對凸函數 ,若每個 都滿足 ,便稱 。純量絕對值的次微分在 時是 ,在 時是 ,在 時則是整個區間 。
這區間不可省略:平坦的邊可以傳遞非零的力,而邊差仍為零。
定理 2.3.3
(唯一的一步及其證書)
對每個 及 ,上述最小化問題恰有一個解。 是解,當且僅當存在邊力 滿足
換言之,非平坦邊上 ;平坦邊上可取任何 ,但仍須滿足頂點方程。圖像 唯一,證書 卻未必唯一。
證明
(由強制性得存在,由投影得證書)
目標函數連續,二次項在 時趨向無窮,而非負權重保證 ,故目標函數強制增大,因此具有最小值。二次項嚴格凸, 是凸函數,故最小值點唯一。
為了不對 求普通導數而證明證書,設 、。兩者均緊緻且凸,並且
令 為 在 上的歐氏(Euclidean)投影。投影不等式給出對所有 ,。設 ,則 使 在 上達到最大值。選取 使 。由於 令 最大,。每條邊都滿足 ;加總後相等,所以每一項必相等,得到證書。對任意 ,支撐函數公式給出 。展開二次項並使用 ,可知 的目標值至少比 的大 。所以 是唯一解。反過來,任何具有證書的 也滿足相同不等式,必為解。這同時證明 。
證明透視
甚麼取代了缺失的導數?
三個要素完成了導數平常的工作。支撐函數表示 把不光滑的和寫成緊緻凸集上線性函數的最大值;這裏需要非負權重,因為若某個 為負, 便是空集。其次,在 上的投影不等式擔當駐點方程的角色:它說明 使 最大,這正是 為次梯度的意思。最後,由頂點力取回邊力靠的是一個相加論證:逐邊的界 加起來是等式,所以每一條都是等式。這就是非平坦邊上的符號條件;在平坦邊上它沒有任何限制,盒子容許整個區間。
二次項提供餘量 ,同時給出圖像的唯一性與反方向的結論。可能不唯一的是滿足 的邊向量 :兩個選擇相差 核中的一個元素,而這個核非零恰好當圖中有環。若圖是森林, 是單射,即使存在平坦邊,邊力也唯一。
能量、守恆及對數據的依賴
以 作比較,可得基本能量不等式:
因此全變分不增,但單靠這句話並不能推斷每個像素值的變化。證書給出更多結論。
命題 2.3.4
(一步的能量、守恆與穩定性)
設 是由 以參數 得到的一步。
- 。
- 對正權邊子圖的每個連通分量 ,。
- 若 是在同一圖、同一權重及同一 下由 得到的一步,則 。
證明
(證書的三個推論)
能量估計:對 的次梯度不等式取 ,得到
守恆:以指示向量 乘頂點方程,得 。分量 只在恰有一個端點屬於 的邊上非零,而這種邊權重為零,所以 。因此 。孤立頂點亦是連通分量。
穩定性:對兩個輸入 及其輸出 ,記 和 。將兩個次梯度不等式相加,得 ,所以
因此 。
第二項說明,不存在或權重為零的邊不傳遞任何強度。第三項就是不擴張性,它比較的是相同 、圖與權重下的兩次運算;它並不保證嚴格收縮,因為常數輸入保持不變。
兩個像素:精確閾值
例題 2.3.5
(邊何時變平)
取一條權重 的邊, 且 。均值 守恆。寫 、,目標函數化為 ,唯一最小值點為
當 ,邊力 ,對比度減少 。若 ,兩像素恰好在均值相遇,相容的平坦邊力為 ;等號情況同樣適用。例如 、、、 時,;改用 則 ,且 。
在較大的圖上,平坦邊並不與其鄰邊脫鉤。
例題 2.3.6
(被鄰邊拉動的平坦像素對)
取單位權重路徑 ,邊的方向為 和 ,、。此時 ,頂點方程為
試用「第一條邊平坦、第二條邊遞增」的模式。第二個條件迫使 ,故 、。平坦條件 給出 ,所以 。第二個邊差為 ,與 相容,證書成立,這就是所求一步。總和 守恆。能量估計亦可驗算:、、,故 。
常見錯誤
(以為平坦像素對會在自身均值相遇)
在上面的路徑例子中,像素 和 在 合併,而不是在它們舊值的均值 。這對像素的總和並不守恆,因為通往像素 的非平坦邊把邊力 傳入這一對。守恆只對正權圖的連通分量成立,不對任意一組合併了的像素成立。
反例模式
零邊差不代表零邊力
取 、、,上述解為 ,但頂點方程要求 。若只因輸出邊差為零便令邊力為零,會得到 ,它並非最小值點。不可微性需要一個可選的力的集合,而不是普遍指定零。
例題 2.3.7
(證書成一整個區間的三角形)
取單位權重三角形,邊的方向為 、、,常數圖像 。這一步是 ,因為所有邊差為零,頂點方程變成 。在頂點 它是 ,在頂點 是 ,在頂點 是 。因此每個環流 ()都是證書。圖像唯一,證書卻構成一個區間,因為環令 有非零的核。
可以反覆令 ,以同一正數 計算下一步。每一步都存在且唯一,使全變分不增,並保持每個正權連通分量的總和。這些離散結論本身並未建立連續時間奇異全變分流、光滑化極限或連續偏微分方程的結果。
練習
練習 2.3.8
(單邊權重為 ,,。求新圖像與一個有效邊力。)
基礎
解答(2)
- 1
比較邊差與閾值
初始邊差 ,,故新邊差為 。
- 2
求圖像與邊力
均值為 ,得 。以 至 為方向,頂點方程 給出 ,它滿足 及符號條件。
練習 2.3.9
(圖有兩個連通分量,其間沒有邊:單位權重邊 與 。取 、,求一步結果並解釋各分量均值。)
基礎
解答(2)
- 1
分別處理每個分量
兩個分量互不影響,每個分量上 。邊差 和 都不超過 ,所以兩條邊都變平。
- 2
在每個分量上使用守恆
結果是 。兩分量的均值 和 (總和 和 )都保持不變;只知道全圖均值 不足以恢復兩者。
練習 2.3.10
(證明若 在每個正權連通分量上均為常數,這一步便是 。不擴張性能否保證任何兩個不同輸入的距離嚴格減少?)
核心
解答(2)
- 1
在 處計算目標函數
所有正權邊差均為零,所以 。目標函數非負,在 時等於零,因此唯一最小值點為 。
- 2
回答收縮的問題
不能。兩幅不同的常數圖像都在這一步下不變,故它們的距離不減少。
練習 2.3.11
(直接用證書證明 ,並解釋它為何比比較目標值所得的估計強。)
核心證明
解答(2)
- 1
在 使用次梯度不等式
由於 ,有 。
- 2
比較係數
∎只比較 和 的目標值,得到的係數是 。證書把它加倍,因此 的同一減少量只容許圖像移動一半的平方距離。