同一幅圖像的兩個問題
去噪模型要為每個像素求出一個實數強度;二元分割則要決定哪些像素屬於物件。兩者的輸出不同,但水平集的邊界把它們連繫起來。若一條邊兩端的強度分別是 和 ,它恰好在 時跨過水平 。這條邊的對比度因此等於它所跨水平的區間長度。把這個觀察加總至所有邊,便能把全變分寫成邊界代價的積分。
定義 2.4.1
(圖全變分與割)
設 是頂點集 非空的有限無向圖,每條邊 有非負權重 。對 和 ,定義
每條跨越邊界的無向邊只計一次。允許空邊集及零權重。令 ,並始終採用嚴格不等號。
以下有限維結論無須假設幾何網格、光滑性或概率模型。
定理 2.4.2
(有限圖餘面積公式)
對每個 ,
被積函數是有界階梯函數,並且除了恆為零的情況外有有界支集,故這是普通有限積分。
證明
(逐邊寫成對水平的積分)
對任意實數 ,指示函數 和 恰好在 之間的半開區間取不同值。因此
對每條邊應用此式,再交換有限和與積分。固定 時,加權指示函數差的絕對值之和恰好是 。端點的選擇只改變有限多個水平,不影響積分。證畢。
常見錯誤
(把每條跨界邊算了兩次)
對有序對 (其中 、)求 的和是正確的;但若對所有有序對求 的和,每條跨界邊都會算兩次,而對有序對求 的和亦有同樣問題。若只把其中一個量加倍,餘面積恆等式看來便差了因子二。這裏兩個和都對無向邊求和,每條邊只計一次。
例題 2.4.3
(加權三角形上的餘面積公式)
取頂點 及全部三條邊,權重 、、,並令 。則
當 ,;當 , 為空集;兩者的割均為零。當 ,,跨界邊為 和 ,所以割值 維持一段長度 的區間。當 ,,跨界邊為 和 ,所以割值 維持一段長度 的區間。積分為 。邊 跨過 中每個水平,正好是它的貢獻 ;圖不必是鏈。
一幅去噪圖像提供許多最優割
固定數據 和 ,考慮二次全變分問題
目標函數連續、強制且嚴格凸,因此存在唯一最小解。
定義 2.4.4
(水平 的二元目標)
對水平 ,定義二元目標
選入滿足 的像素會減少數據項;選入及未選入像素之間的邊界則產生代價。
此二元目標依賴 :我們並沒有聲稱去噪圖像的閾值集合會使任意分割能量最小。
定理 2.4.5
(閾值最優性)
對每個實數 ,嚴格上水平集 都在所有 的子集之中使 最小。 的最小解未必唯一。隨 變化所得集合互相嵌套,因為它們來自同一個 。
證明
(在每個上水平集邊界都取等號的邊證書)
每條邊任選一個方向;對方向為 的邊定義 。圖全變分的最優性證書給出邊向量 ,使
為說明證書的來源,可把 正交投影到緊緻凸集 。投影不等式給出最小解 ,並使全變分的支撐函數表示逐邊取等號。反過來,證書配合次梯度不等式亦證明最優性。
對任意子集 ,盒約束給出 。對 則取等號:跨界邊的強度差非零,其方向符號與指示函數差相同;證書迫使 等於相應帶符號權重。非跨界邊則貢獻零。因此對每個 ,
第一個不等式成立,是因為 恰好選入所有負項 ,排除所有正項;零項可選入或排除。第二個不等式使用 及盒約束。這證明結論對每個 均成立,包括等於某個像素值的水平。
證明透視
一張證書,為每個水平提供下界
把 代入二元目標,對每個子集 得
證書的每一部分各有職責。駐點條件令這個改寫成立。盒約束 使括號對每個 都非負,這是權重唯一出現的地方。符號條件使括號對所有上水平集同時為零,因為跨過 某個水平集的每條邊都有 ,且其符號與 相同。剩下的 恰好在選入所有負項時最小,這正是上水平集的定義;零項就是並列的來源。整個證明沒有用到餘面積公式:對 平均的恆等式無法說明每一個水平各自最優。
非嚴格集合 也是最小解。只需選取略低於 的水平,使兩者之間沒有像素值,再對有限多個仿射目標值取極限。相等時其他最小解未必是這兩個集合之一。
三像素計算
例題 2.4.6
(一條有兩條邊的鏈)
考慮單位權重鏈 ,令 、。邊由左指向右,取 和 。則 ,且 。 的兩個分量皆為正,所以 滿足邊證書。故此 是唯一全變分最小解。
當 ,上水平集是 。割只含邊 ,而
例如 、、。定理比較的是全部八個子集,而不只這幾個。當 ,嚴格閾值給出 ,非嚴格閾值則給出 ;兩者的值均為 。中間像素恰好等於閾值,於是出現真正的分割並列。
第二個例子顯示,水平等於最大去噪值時會出現並列。
例題 2.4.7
(對比度部分收縮的兩像素)
取一條權重為 的邊,、。邊方向為 ,取 得 。其差分為 且 ,證書成立,故 是最小解。對比度由 收縮至 ,均值 不變。
當 ,。在 ,四個子集給出 、、 及 ,所以 是唯一最小解。在邊界情況 ,嚴格集合為空集,;非嚴格集合 的 。另外兩個子集分別給出 和 。正如定理及關於非嚴格集合的說明所預期,兩種閾值約定都給出最小解。
反例模式
閾值化去噪圖像不等於閾值化原數據
兩個頂點之間有一條單位權重邊,令 、。全變分最小解為 。在 ,嚴格集合是空集,非嚴格集合是兩個頂點;兩者的 都是零且最小。直接閾值化數據給出 ,其目標值 ,此例中也碰巧最小。但在 ,數據閾值集合仍為 ,其值為 ;兩個頂點一起選入的值卻是 。因此直接閾值化含噪數據一般不等同閾值化全變分解。
練習
練習 2.4.8
(四頂點單位權重鏈上,。列出各像素值之間開區間上的不同嚴格上水平集,並以數值驗證餘面積公式。)
基礎
解答(3)
- 1
列出上水平集
當 時集合為 ;在 時為 ;在 時為 ;在 時為 ; 時為空集。
- 2
計算它們的割
割值依次為 ;例如 被全部三條邊跨過。
- 3
比較積分與全變分
積分為 ,等於 。孤立端點對積分沒有貢獻。
練習 2.4.9
(兩頂點以權重 的一條邊連接,數據為 ,其中 ,且 。求去噪圖像,以及其嚴格上水平集只有一個頂點的閾值範圍。)
核心
解答(2)
- 1
求去噪圖像
均值 保持不變,輸出對比度為 ,因此 。當 ,證書為 ;當 , 可行。
- 2
讀出單點閾值
嚴格上水平集為單點 當且僅當 且 。若 ,就沒有單點嚴格上水平集。
練習 2.4.10
(在 、 的鏈例子中,求 的所有最小解,並解釋為何只看嚴格上水平集會遺漏一個。)
核心
解答(3)
- 1
列出數據項
在 ,各像素的項 為 ,每條跨界邊代價為 。
- 2
枚舉八個子集
,。其餘六個子集的值為 (空集)、()、()、()、()及 ()。
- 3
確定最小解
最小解恰好是 和 。嚴格集合 排除了去噪值等於 的像素,所以只找到其中一個。
練習 2.4.11
(對任意數據,證明當 時 使 最小,而當 時 使其最小。第二個範圍的端點是否必有唯一最小解?)
基礎
解答(2)
- 1
應用閾值定理
若 ,每個 ,故 ;若 ,沒有 ,故 。閾值定理說明這些集合使 最小。
- 2
檢驗端點的唯一性
在 可以不唯一:在 、、 的雙頂點例子中, 時空集與 的 都是 。