動機
劃痕或傳感器故障可能使部分像素缺失,而附近像素仍可使用。若直接用零填補,就等於把沒有測量誤當作測得黑色。另一種做法是尋找與已知數據一致、同時變化平緩的圖像。對於像素圖,最簡單的平滑度指標是相鄰像素差的平方和;使它最小的圖像便把觀測值延伸到損壞區域。
常見錯誤
(用零填補缺失像素)
零是一個測得的亮度,不是「未知」的代號。在路徑 上觀測值為 ,零填補 製造了兩條人為邊緣,能量為 ;常數填補 與所有觀測一致,能量為 。
這個模型的好處是條件清楚:若預期亮度逐漸變化,它可能合理;但它不知道劃痕後面是否有邊緣或紋理。以下在有限加權圖上討論,不把離散結論直接當成連續模型的結論。圖和權重決定何謂「相鄰」。
定義
設 是有限無向圖。每條邊 的權重滿足 ;不存在的邊權重為零。把頂點分為已觀測像素 和未知像素 ,在 上固定測量值 。對任意滿足 ()的延拓定義 Dirichlet 能量
每條無向邊只計一次。若頂點的加權度 ,其鄰居加權平均為 。未知頂點滿足 時稱為調和的;等價地,。孤立的未知頂點沒有這樣的平均值,而且其取值不影響能量。
定理/命題
定理 1.5.1
(存在性、唯一性與邊界條件)
假設 的每個連通分量都含至少一個已觀測頂點,則滿足觀測值約束的能量最小解存在且唯一;它也是每個未知頂點都調和的唯一延拓。在每個連通分量內,解的值介於該分量已觀測值的最小值和最大值之間。
定理 1.5.2
(能量比較)
在相同假設下,設 是調和延拓,另一個可行延拓寫為 ,其中 於 。則
除非 ,右邊嚴格為正。因此調和方程給出的是全局最優證書,不只是駐點條件。
證明或證明思路
證明
(存在性、唯一性與能量恆等式)
對在 上為零的 ,令 。若 ,由權重為正可知每條邊兩端的 值相同,因此每個連通分量上的 是常數。每個分量都含一個 的觀測點,故 處處為零。所以 在自由變量空間上正定。該空間有限維,其單位球面緊緻, 在其上的最小值為正;由此能量具有強制性,必達到最小值。正定性又給出嚴格凸性和唯一性。若 為空,唯一可行圖像就是 ,其餘結論顯然成立。
對自由變量求偏導,得到 ,所以最小解必須調和。反過來,對 展開平方:
交叉項按頂點收集後是 。未知頂點處內和為零,觀測頂點處 ,所以交叉項消失。這證明了能量恆等式及全局最優性,並說明調和延拓是唯一的。
證明
(離散最大值原理)
假設 在某連通分量的最大值 大於該分量所有觀測值。取得 的頂點必為未知頂點;由於其分量含觀測點,它必有鄰居。它等於鄰居的正權平均,而鄰居均不大於 ,所以每個鄰居也取得 。沿路徑重複這一論證,最終到達觀測頂點,產生矛盾。對 使用相同推理即得下界。
證明透視
為何每個分量都需要觀測值
錨定假設被使用了三次,每次作用不同。在唯一性證明中,它消去唯一的不可見方向:能量只衡量差值,所以在一個分量上統一加常數不會改變任何量,除非有觀測值把這個常數固定。能量恆等式本身對任何調和 都成立;錨定只用來保證其右邊在 時嚴格為正,正因如此,調和性是全局證書,而不只是駐點檢驗。在最大值原理中,它使傳播論證得以終止:沿邊追蹤相等的最大值,必須到達固定的觀測值,否則論證甚麼也證明不了。
正權重亦在同樣的地方使用。零或負權重會破壞「零能量迫使相鄰值相等」這一步,也會破壞「若不大於某值的數的平均等於最大值,則全部相等」這一步。
例題
例題 1.5.3
(一段受損的線)
四個頂點構成單位權路徑 ,其中 、,頂點 1、2 的值缺失。調和方程為 和 ,解得 、。三條邊的差值均為 1,所以 。能量比較恆等式保證其他填法的能量更大。這裏得到線性插值是因為路徑權重和間隔均勻,並非所有圖像座標上的調和延拓都是線性的。
例題 1.5.4
(權重不同的連接)
一個未知頂點 與已知值 0、6 相連,權重分別是 2、1。方程 給出 。較強的連接把解拉向零。若直接取算術平均 3,就忽略了所選圖的權重,並非能量最小解。
例題 1.5.5
(邊界也可能有噪聲)
若第一例右端測量值從 3 變成 4,精確插值所得為 。被當作可靠邊界的像素若有誤差,誤差會傳到填補區域。精確匹配是一種建模選擇;若觀測有噪聲,可考慮對觀測像素加入數據保真項,但那時不必精確匹配觀測值,上述定理也須相應調整。
常見誤區
反例模式
平滑填補未必恢復邊緣
假設四頂點路徑的真實圖像是 ,卻只觀測到兩個端點。調和填補為 ,沒有恢復真實的突變。另一幅真實圖像 卻給出完全相同的端點觀測;僅憑數據無法區分二者,二次模型選擇的是平滑解。最大值原理不保證所選圖像就是事實。
反例關乎模型選出甚麼;下一個錯誤則關乎它是否選得出任何東西。
常見錯誤
(把定理用於沒有錨定的分量)
若某分量沒有觀測頂點,定理不適用。例如兩個未知頂點由一條邊連接,則每個常數對 都是最小解;孤立的未知像素更沒有約束。加入一個小的對角懲罰項會選定某個值,但它改變了模型,不能把選出的值誤認為數據提供的資訊。
下面的視角把調和方程與求解它的任何程序區分開來。
概念視角幾何
平均關係是方程,本身還不是算法
在解上,每個自由像素等於鄰居的加權平均。不斷用當前鄰居平均更新缺失像素是一種可能的迭代方法,但其收斂性取決於更新規則和圖;單有平均方程並不能證明迭代收斂。迭代中也必須保持邊界觀測值固定。
總結
二次圖像修補是邊值問題:每個缺失像素平衡它與鄰居之間的加權差。每個圖分量至少有一個邊界觀測值,便可保證存在性、唯一性、全局能量證書及最大值原理。這些保證屬於所選平滑模型;要保留尖銳邊緣或準確恢復未觀測結構,還需其他假設或先驗。
練習
練習 1.5.6
(單位權路徑 的兩端分別固定為 和 。求缺失的中點及其能量。)
基礎
解答(2)
- 1
使用調和關係
。
- 2
計算能量
。
練習 1.5.7
(一個缺失頂點連接到值為 和 的頂點,權重分別為 和 。求其值;當第二條邊的權重從正值趨於零時,解趨於甚麼?)
基礎
解答(2)
- 1
解加權方程
給出 。
- 2
改變權重
若第二權重為 ,則 。權重恰為零時第二條邊不存在,圖本身已改變。
練習 1.5.8
(一條路徑兩端固定為 和 ,中間只有一個缺失像素。直接證明中點從最優值改變 時能量增加 。)
基礎
解答(2)
- 1
求最優值
調和關係給出 ,能量為 。
- 2
加入擾動
當 時,能量是 ,恰好增加 ,與比較恆等式 一致。
練習 1.5.9
(一個圖有兩個連通分量,只有其中一個包含觀測點。解釋為何填補不唯一,並描述沒有觀測點的分量上的全部最小解。)
核心
解答(3)
- 1
分開兩個分量
兩個分量之間沒有邊,能量是兩者能量之和,可以分別最小化。
- 2
在無觀測分量上最小化
關鍵一步
該分量上的最小解恰為所有常數向量,而任意常數都允許。
依據: 連通分量的能量為零,當且僅當相鄰值都相等。
- 3
結論
無論已錨定分量的唯一解是甚麼,全圖都有無窮多個全局最小解。