動機
平滑一幅有限圖像時,邊緣像素在記錄範圍以外沒有鄰居。算法必須決定邊界怎樣處理:連接相對邊會構造週期圖像;指定外部為零,代表它接觸一個黑色儲庫;零通量則把強度留在圖像範圍內。這些是不同的模型,不是可互換的填邊方法。非零的均勻灰度在零通量模型中應保持不變,但邊緣接觸零儲庫時,它並非平衡狀態。
先研究一行像素。完整的有限維分析能清楚展示邊界的作用,而不必假設連續偏微分方程的存在定理。同樣的圖構造可推廣至矩形圖像,只須把每一對水平及垂直相鄰像素各計一次;零儲庫模型還要為每個邊界面加一條外部邊,因此角落像素有兩條。像素值取實數;雖然實際強度可能有較窄的範圍,負值在數學上是允許的。以下時間尺度取網格間距及擴散係數皆為一。
定義
定義 9.1.1
(離散零通量(Neumann)模型)
設 ,其中 。零通量,也稱離散 Neumann 模型的能量為
像素 與像素 之間沒有邊,也沒有涉及外部值的項。能量的負梯度給出 ,其中
中間式適用於 。
等價地,在端點使用中心二階差分時,可設虛擬值 及 ,令外側面的差值為零。端點方程因此為 和 。此約定把邊界面放在端點中心以外半個網格間距;邊界位置的其他選擇可能改變端點係數。
定義 9.1.2
(離散零儲庫(Dirichlet)模型)
對齊次離散 Dirichlet 模型,以相同權重的邊將兩端各接到一個固定為零的外部節點。定義
其中 是 的梯度矩陣。其內部各行與 相同,但 及 。
Dirichlet 算子相當於固定虛擬值 的中心差分。指定的零值位於外部節點,即端點中心以外一整個網格間距;若改在半步邊界面指定零值,端點係數便不同。兩個外部節點表示指定的數據,不計入圖像總量。若實際間距為 、擴散係數為 ,將矩陣乘以 便改變演化速率;若能量也乘上相同因子,所列的梯度流恆等式仍然成立。為簡潔起見,以下求和不加權。
定理 / 命題
定理 9.1.3
(全局解與能量恆等式)
對 或 ,以及任意 ,解在所有 唯一存在,並滿足
兩種邊界模型在這些恆等式上一致;分別在於總強度的變化及長時間極限。
命題 9.1.4
(總量平衡與長時間極限)
零通量模型的總量 不變,且 趨向所有分量均等於初始平均值的向量。零儲庫模型則有
而且 。因此 Dirichlet 總量不一定守恆;變化率的符號取決於邊界值。
證明思路
證明
(分解、譜解與能量定律)
設 的各行分別取差值 ,則 。對 ,在 加上分別取出 和 的兩行,所得矩陣 滿足 。故兩個矩陣皆為實對稱半正定矩陣,且 。
依有限維譜定理,,其中 正交,對角元素 非負。明確公式 給出全局可微解。要證唯一性,將任何另一個解投影至各特徵向量,並解具有相同初值的純量方程 。由對稱性和求導,
證明
(列和與核)
每行之和為零;由對稱性,其每列之和亦為零,即 ,因此 。滿足 的向量必有所有相鄰分量相等,因此其核為 的生成空間。其他特徵值皆嚴格為正,譜公式遂趨向 在該核上的正交投影,即初始平均值。對 Dirichlet 模型,各內部邊對總量的貢獻相消,只剩外部邊的 。此外, 強迫每個分量為零:兩個端點項及所有相鄰差值的平方均須為零。因此 所有特徵值嚴格為正,譜公式趨向零。
證明透視
總量去了哪裏?
分解 用了兩次。對稱性使譜定理可用,從而得到明確解及唯一性;半正定性使每個 ,沒有模式增長,所以解對所有正時間存在。能量恆等式則只需對稱性。
總量部分的關鍵一步是看列和而非行和。每條內部邊在兩端之間轉移大小相等、符號相反的量,所以加總時相消。Neumann 模型完全移除外部邊,給出 ;Dirichlet 模型保留兩條邊,其另一端固定在圖像以外, 第 行及第 行之和為 ,於是剩下 。能量遞減本身不能保證總量守恆。
極限部分用到像素行的連通性。相鄰分量相等能推出常數向量,只因每個像素都連到下一個。若圖像圖有兩個互不相連的分支,Neumann 核便包含每個分支的指示向量,極限是各分支各自的平均值。同樣,Dirichlet 極限為零,是因為每個分支都接觸儲庫邊。
以上是離散方程的定義,並非已證明取樣解收斂至某個連續邊界值問題。合適的網格位置及尺度可使它們與常見零通量及指定值的解釋一致,但收斂定理仍須指定區域、取樣方法、範數及邊界處理。尤其虛擬點的約定必須與物理邊界的位置一同說明。
概念視角代數
兩種邊界模型即餘弦模態與正弦模態
兩個譜都可以明確寫出。對 ,Neumann 的特徵向量是 ,特徵值為 ,;Dirichlet 的特徵向量是 ,特徵值為 ,。餘弦模態在半格位置的邊界面上斜率為零,正弦模態則在外部節點處為零,正好對應兩種虛擬點約定。只有 Neumann 有 的常數模態;而所有特徵值都小於 ,所以對任何 , 都滿足 Euler 的能量準則。
例題詳解
例題 9.1.5
(兩個像素、兩個邊界模型)
取 、。常數向量 及對比向量 均為特徵向量。Neumann 的相應特徵值為 和 ,故
總量恆為 ,而對比衰減。Dirichlet 的相應特徵值是 和 ,因此
此時總量為 ,趨向零。初始時 ,與 一致。相同的初始圖像在兩種邊界假設下,長期亮度不同。
例題 9.1.6
(一次顯式時間步及其能量)
前向 Euler 法以 代替精確流。特徵值為 的特徵向量經一步後,振幅乘上 ,相應能量則乘上 。因此,對每個初始狀態能量皆不增加,當且僅當每個特徵值均滿足 。兩像素 Dirichlet 模型的 ,故能量條件是 。等號時對比模式交替變號而不衰減:不增加不等於收斂至平衡。
例題 9.1.7
(保持非負需要更強的條件)
零通量端點更新為 ;內部更新為 。零儲庫內部公式相同,端點更新則為 。故 時,每個更新都是舊像素值及 Dirichlet 零儲庫值的非負組合,非負輸入保持非負。這個充分界是正性結論,與精確的譜能量界不同。
常見錯誤
反例模式
看似穩定的公式可以增加能量
三像素 Neumann 模型中, 是特徵值為 的特徵向量。若 ,一步 Euler 法將 變成 ,使 增加至四倍。連續流永遠耗散能量,但時間離散法未必如此。此外,能量穩定也不足以保證像素非負:兩像素 Dirichlet 模型中, 符合能量界 ,卻將 變成 。
兩個失效都關乎時間步,而非流本身。以下兩個錯誤則關乎流本身。
常見錯誤
(能量、強度平方與總量是不同的量)
量度粗糙程度及可能的儲庫懲罰,而 量度強度平方;兩者的導數不同,前者減少 ,後者減少 。兩者一般都不是總強度 。不要因為數據被平滑,就假設總量守恆;守恆與否取決於邊界模型。
常見錯誤
(零儲庫不一定移走強度)
容許實數輸入時, 的符號並不固定。兩像素 Dirichlet 模型取 ,解為 ,故 ,且 。儲庫從兩側都把總量拉向零。
總結
以邊為基礎的二次能量同時給出清晰的邊界約定及擴散方程。省略外部邊得到守恆總量的零通量模型;將外部值固定為零則引入儲庫,容許總量交換。兩種有限維流皆全局存在並耗散能量,但數值時間步仍須獨立檢查穩定性及正性。這些結果只針對所指定的離散模型,並未證明一般連續邊界定理。
練習
練習 9.1.8
(寫出三像素 Neumann 矩陣 ,求特徵值及互相正交的特徵向量,並用它們求初值 的流。)
基礎
解答(3)
- 1
寫出矩陣及特徵對
矩陣為 。特徵對分別是 、、;直接相乘可驗證,三個向量互相正交。
- 2
分解初值
關鍵一步
。
- 3
附上指數因子
,極限為 。
練習 9.1.9
(兩像素 Dirichlet 模型中,取 。求 、 和 ,並驗證兩條能量恆等式。)
基礎
解答(3)
- 1
求解流
初值為 的特徵向量,故 。內部差值為零,兩個邊界平方給出 。
- 2
核對能量恆等式
由於 ,;又 ,其導數為 。
- 3
核對總量平衡
,所以 。
練習 9.1.10
(證明前向 Euler 法對任意步長都保持 Neumann 總量。對 ,找一個非負初值,說明 時非負性可能失效。)
核心
解答(2)
- 1
對一步 Euler 求和
對 求和,任意實數 均得到原來總量。
依據: 。
- 2
給出負向超調
初值 經一步後中央分量為 ,當 即為負。總量守恆不能阻止這個負向超調。
練習 9.1.11
(在兩像素 Dirichlet 模型中,求所有使每個初值經前向 Euler 迭代後均收斂至零的 ,並解釋端點情況。)
核心
解答(3)
- 1
化為兩個特徵模式
特徵值為 和 ,乘數分別為 與 。
- 2
要求兩個乘數的絕對值小於一
關鍵一步
與 的交集為 。
- 3
檢查端點
時沒有模式衰減; 時對比模式的乘數為 ,永遠振盪。更大的正步長令此乘數絕對值大於一,因而某些初值會發散。