配準變換之後還要做甚麼?
配準求出的是座標之間的關係;顯示圖像則需要在新網格的每個像素指定數值。設 把移動圖像座標映到固定圖像座標,固定網格點 的值應從移動圖像的 取樣。這稱為反向映射:若直接把原像素向前推,輸出網格可能有空洞,也可能有多個像素落到同一位置。這裏假設所考慮區域的變換可逆;即使如此,裁切和遮擋仍可能令對應不存在。逆映射通常落在像素之間,因此還須選擇插值與圖像外的邊界規則。
常見錯誤
(把像素向前推,而不是把網格拉回)
取一維放大 ,移動像素為 。向前推會把它們的值放到 ,輸出像素 甚麼也收不到,事後還要修補。反向映射則為每個輸出像素賦值: 從 讀取,即移動像素 與 之間。把 誤寫成 ,即使沒有空洞,讀取的位置也是錯的。
雙線性插值
單位方格四個角的值依次為 ;點 從左下角起計,且 。定義
可以先在上下兩邊分別做水平線性插值,再在所得兩值之間做垂直插值;先垂直後水平也得到同一式子。四個權重非負且和為一,所以結果介於四個角值的最小值和最大值之間。這依賴點在方格內:外插可能出現負權重,不能直接使用這個界。
常見錯誤
(在方格外使用最小最大值界)
角值取 、、,點取 ,權重為 ,得 ,大於所有角值。方格以外的點必須歸入包含它的方格,或交由邊界規則處理;一個方格的公式不是有效的外插器。
定理 3.3.1
(雙線性函數的精確重建)
若方格上的連續圖像是 ,從四個角構造的雙線性插值在整個方格都等於 。相鄰方格若使用相同的共邊樣本,其插值在共邊連續;一階導數卻未必連續。
證明
(精確性、共邊連續與導數跳變)
插值式對角值線性。直接代入可知它精確重現 :例如 的角值為 ,給出 。因此它也精確重現這四者的任意線性組合。在共邊上,對邊兩個角的權重均為零,兩側均退化為同一對端點的線性插值,所以數值一致。但導數可以跳變:一維網格 上的值為 ,兩段斜率分別為 ;把這組值複製到兩行便得到二維例子。
導數跳變在配準中有實際影響:若以圖像梯度優化目標函數,網格線上的導數可能不存在;改用更平滑的插值器亦會改變目標函數。
例題 3.3.2
(一個平移後的輸出像素)
設 ,固定網格點 ,則 。移動圖像該方格依 排列的角值為 時,插值為 。若誤用 ,取樣位置就不同;必須先寫清變換方向。
若逆映射落在圖像外,補零、延用最近邊界值及週期延拓都會得到不同結果,也可能引入不同的人造邊緣。插值不能憑空還原遮擋部分或視野之外的資訊。
例題 3.3.3
(同一邊界點的三種邊界規則)
考慮一行圖像,儲存值為 ,逆映射點為 ,位於缺失樣本 與 的正中。線性插值給出 ,所以結果完全取決於 的規則:
- 補零,:值為 ;
- 延用邊界值,:值為 ;
- 週期延拓,:值為 。
在內部點如 ,三種規則都給出 。 處的三個答案是建模選擇,並非同一真值的近似。
降取樣與有限傅立葉混疊
圖像金字塔減少像素數,令搜尋大位移較容易,但隔點取樣會丟失資訊。考慮長度 的複數週期序列 ,使用未正規化的離散傅立葉(Fourier)變換和以下逆變換:
定理 3.3.4
(隔點降取樣的二對一混疊)
設 ,對 令 ,並以 表示 長度為 的未正規化變換。則對 ,
證明
(代入逆變換)
在偶數索引,逆變換給出
代入 ,並交換兩個有限和,
內層和是公比為 的等比級數。若 ,則 ,和為 ;否則 而 ,和為 。當 ,在 中與 同餘的索引恰為 和 。故 ,而 。
證明透視
兩個頻率為何摺疊成一個?
關鍵在第一行:在偶數索引,指數 等於 ,所以細網格上的頻率 在粗網格上表現為頻率 。其後只用到長度 指數函數的正交性,它像濾波器一樣只保留與 同餘的索引。存活索引的數目正好用到 :每個同餘類有兩個索引,因此有係數 和 的配對。逆變換對任何長度 的陣列都是精確恆等式,所以沒有引入對底層連續圖像的頻帶限制假設。證明從未使用實數值,故對複數數據同樣成立;過程中也沒有近似,摺疊是精確的。
因此粗網格只確定每對係數的和,不能分別確定兩者。選定保留索引時,每對最多保留一個;若要保持實值,集合還須對共軛對稱封閉。若已知所有捨棄係數都為零,保留係數便是對應粗網格變換係數的兩倍,再用逆變換即可重建這個受限制的原序列。這是有條件的重建,並非任意數據均可重建。截止頻率的索引需要清楚規定;偶數長度的 Nyquist 頻率是自身共軛的,處理截止頻率時須維持實值所需的對稱性。
例題 3.3.5
(重建取決於假設哪個夥伴為零)
設 、,。則 ,故 。偶數樣本為 ,,與定理一致:,。
若保留集合為 ,即假設 ,則 、,逆變換返回 ,正是原序列。序列 有相同的偶數樣本;若保留 ,同一個 會返回它。數據無法在兩者之間作出選擇,決定的是假設。
邊界情況:實序列 的 ,配對 的兩個成員都非零。每對只保留一個的任何集合都返回複數序列 或 ,因此都不能重建它。
反例模式
兩個不同訊號有相同粗樣本
當 , 與 在奇數位置不同,但 。降取樣後,高低頻率無法區分。即使運算完全精確、沒有量測噪聲,這個歧義仍然存在。
降取樣前可先用低通濾波器壓低每對中將被捨棄的頻率。理想週期頻域遮罩若保留一個共軛對稱集合,且每對至多選一個,就能消除已捨棄頻率的摺疊貢獻;但那些係數已被移除,不是被還原。高斯(Gauss)平滑能衰減高頻,卻不是精確的頻帶限制。二維兩軸長度皆為偶數並各降取樣一半時,每個粗頻率格會摺合四個原頻率格;沿用相應的變換慣例,係數為 。真實照片有限且通常不具週期性,濾波的邊界及截斷選擇都會影響結果。
概念視角幾何
插值和抗混疊回答不同問題
插值按選定模型定義樣本之間的值;抗混疊濾波則在採用較疏網格之前限制高頻。雙線性插值本身不保證消除所有會摺疊到同一粗頻率的成分。
練習與解答
快速檢查
(方格角值依 次序為 。求 的雙線性插值;在方格內可能大於 嗎?)
先計算四個權重。
解答 · 答案
權重為 、、、,結果為 。方格內不可能大於 :權重非負且和為一。
快速檢查
(設 ,。計算降取樣後序列及其長度二的 DFT,並與長度四的係數核對混疊公式。)
長度為二時,,。
解答 · 答案
,。原變換為 ,即 ,公式分別給出 和 。
快速檢查
(長度八的 ,直接保留偶數樣本會怎樣?若先取週期兩點平均 又會怎樣?)
分別在一個偶數索引和一個奇數索引計算 。
解答 · 答案
直接選取會得到四個一,快速振盪看似常數。先平均則各點 ,粗樣本也全為零;這個濾波器消除了此特定振盪,但未必消除所有會混疊的頻率。