動機
兩張圖像不一致,可能因為物件或相機移動,也可能只是亮度與噪聲改變。配準估計幾何對應,分割把像素分成區域,特徵偵測尋找適合匹配或描述的位置。三者互相影響,但未知量和失敗原因不同。一條清晰邊緣可很好地界定區域,卻可能完全無法提供沿邊移動的資訊。
本節為三類任務建立初等模型,再說明多尺度處理的作用。少數公式不能解決一般視覺問題;精確的小例題卻可揭示模型到底用了甚麼資訊、留下甚麼歧義,以及最優化結論的真正範圍。
必須先交代變形方向。我們以固定圖 比較移動圖的取樣 ,所以正的平移參數表示在 中向右取樣。重新取樣後,顯示物件可能看似向左移動。直接寫出比較方程,可避免口頭方向約定變成程式符號錯誤。
定義
設 為取樣位置, 在其附近可微。平移配準最小化
這假設平移與近似亮度不變是合理描述。旋轉、遮擋、對比改變及非剛性變形需要其他模型或額外變量。離開像素網格的值須用插值定義,而插值方式也決定算法應使用哪個導數。
在目前參數 ,令 ,令 的第 行為 。一階模型是 ,Gauss–Newton 增量最小化 。局部結構張量為
其特徵值量度不同位移方向能否在一階改變取樣亮度。張量依圖像尺度、噪聲與亮度單位而變,不宜把固定數值閾值當作普遍的「好特徵」標準。
對分割,設觀測亮度為 ,二元標記 ,固定區域亮度為 。數據能量是
若加入鄰接邊上的 ,便懲罰標記變化、鼓勵較短的離散邊界。這也耦合本來可獨立決定的像素。二元問題與把標記放寬至 的凸鬆弛是不同問題,不應略過這項改動。
在 的高斯(Gauss)尺度空間定義
假設圖像有界,或滿足使卷積及求導合法的條件。尺度改變平均的範圍,並非只把畫面放大縮小。有限圖像要先選擇邊界延拓,才可把此無限域公式離散化。
定理 / 命題
定理 3.1.1
(線性化平移何時可辨認?)
有唯一極小解當且僅當 正定,亦即沒有非零向量同時垂直於所有取樣梯度。此時
這只描述在 的線性化問題,不保證原能量 有唯一全局配準。
定理 3.1.2
(固定區域亮度的最優二元標記)
若 且無空間懲罰,最優標記把各像素分給較接近的亮度。當 必取一,小於中點必取零,相等時兩者皆可。對固定的非空區域,使平方誤差和最小的常數亮度是其算術平均。
非空假設避免計算均值時除以零。交替更新標記與均值可逐步降低能量,卻仍依賴初始值;能量下降不等於達到全局最優。空區域如何處理亦是算法定義的一部分,不能藏在一條沒有意義的均值公式內。
證明思路
證明
(線性化增量的可辨認性)
任意位移 滿足 ,所以其為零當且僅當全部梯度投影為零;因此 正定,恰好表示沒有非零 同時垂直於所有取樣梯度。展開得
若 正定, 嚴格凸,其唯一極小解滿足法方程 ,即得 。反之,若非零 滿足 ,則對任意實數 ,,故極小解不可能唯一。最小二乘極小解仍然存在;使用偽逆能選出某一解,卻不能使原來不可見的方向變成有資訊。
證明透視
唯一性需要每個方向都有資訊
整個證明建基於恆等式 :結構張量是 Gram 矩陣,其正定性是對取樣梯度的生成條件,正如線性方程組的列互相獨立才能確定未知量。反方向更具啟發性:它不需要任何估計,只要有一個非零 使 ,就得到一整條極小解直線,因為二次模型完全看不見沿 的移動。直邊的梯度只沿法向,沿切向移動不可見;稱該邊「對比高」只會放大 ,不能補足其秩。不同方向的邊或角點才可提供缺失方向。最後,論證完全沒有涉及 本身:結論只對 處的模型成立,所以定理明確排除全局唯一性。
證明
(中點規則與均值)
分割能量是各像素獨立項的總和,所以每個標記可以獨立選擇。把標記一的代價減去標記零的代價,得
由於 ,此值為負恰好當 ;其零點給出平手。對大小 的區域 ,令 ,配方得
最後一項唯一在均值處最小。
即使使用最好的常數擬合,區域內變化與噪聲仍可留下正殘差,不能把所有殘差都解讀成分割失敗。
例題詳解
例題 3.1.3
(孔徑問題是一個精確零空間)
取 ,固定圖為 。殘差為 ,每個梯度都是 ,故 。水平位移必為 ,但任意 產生相同數據與能量。此線性圖像有全局歧義,不只是局部最優化困難。多取同一斜坡上的像素可改善水平方向精度,卻不能增加垂直資訊。
例題 3.1.4
(兩個梯度方向決定局部增量)
兩個取樣梯度是 與 ,殘差為 。因此 、、,增量為 ,使線性化殘差為零。這並不保證完整變形後的真殘差也為零,因為二階項可能重要。實際算法應重新計算原能量,必要時縮短步長。
例題 3.1.5
(邊界代價刪除孤立區域)
三像素路徑的亮度為 ,固定 。無懲罰時,標記 唯一最優,數據代價為零,但有兩次標記變化,總能量為 。全零標記數據代價為一,沒有邊界。枚舉八個標記向量可知: 時中間孤立區域最優;在 與全零平手;大於此值時全零唯一最優。正則化可能刪除真實小物件,也可能刪除噪聲,兩者不能由公式自動區分。
高斯平滑滿足 。在卷積積分配方即可證明;也可用獨立中心高斯位移的協方差相加理解。相同標準差平滑兩次,結果標準差為 ,並非 。在可交換導數與積分時,,可先平均再微分,以減低高頻誤差的影響,但同時帶來隨尺度而定的細節損失。
若 ,平滑後乘以 。大頻率比小頻率衰減更快,因此高頻噪聲受抑制,但真實細條紋也以同一因子衰減。亮度模式本身沒有標記說明它究竟是噪聲還是物件細節,故平滑仍包含建模取捨。
概念視角幾何
特徵值如何區分平坦、邊與角?
兩個特徵值都小,表示一階紋理資訊少;一大一小,表示邊狀結構及一個模糊方向;兩者都足夠大,才提供局部二維位移資訊。這些是亮度模型的定量描述,並非物件的語義標籤。閾值須相對噪聲、尺度及亮度單位解讀。
由粗到細配準先平滑、降取樣,在粗層估位移,再逐層細化,可能把大位移帶入線性近似有效的範圍。若粗網格間距為細網格的兩倍,粗像素單位的位移須乘二才可用於細網格。降取樣前平滑可減少混疊,但不能保證正確匹配:重複紋理有多個對齊,粗平滑也可能刪去原本可辨認的特徵。
圖上的邊界計數與連續周長模型有關,但未指定極限過程便不能當作完全相同。軸向鄰接可能對斜邊收取不同代價。特徵偵測的梯度幅值主要強調邊,而結構張量檢驗方向多樣性;幾何配準即使用了特徵對應,仍須按變換參數個數與退化幾何檢查可辨認性。
常見錯誤
反例模式
局部滿秩不保證全局唯一
對週期圖像 ,適當區域內可有滿秩梯度集合,但相差 的平移仍產生同一圖像。正定張量只排除該點附近的無窮小歧義,不能分辨重複的全局圖樣;可能需要限定搜尋域或加入外部資訊。
其餘錯誤都源於把結論帶到證明所用假設之外。空區域不能求均值,交替能量下降亦不是全局最優證書。
常見錯誤
(加入邊界懲罰後仍用中點規則)
閾值定理假設沒有空間項。在三像素例子中取 ,中間亮度 高於中點 ,唯一最優解卻把它標為零。鄰接標記一旦耦合,像素的最佳標記便取決於鄰居的標記。
常見錯誤
(平滑兩次時把標準差相加)
先以 再以 平滑,等於以 平滑,而不是 :相加的是方差。報告 會誇大平均程度;對角頻率為 的正弦,它預測乘數 ,正確值卻是 。
常見錯誤
(把線性化殘差小當作配準誤差小)
配準中,線性化殘差小與非線性殘差小是不同事實;完整步長必須回到 中評估。插值、遮擋、邊界及亮度變化也可能主導誤差,即使法方程解得很準確亦然。報告位移時應交代變形方向與圖像尺度,否則正確數值也會因單位不同而看似矛盾。
總結
配準估計幾何參數,分割估計區域標記,特徵描述局部結構。結構張量指出線性化平移可見的方向。固定亮度分割只在無空間耦合時有精確中點規則。高斯平滑組合時方差相加,多尺度可改善起點與噪聲處理,卻不能消除根本歧義或恢復已被平滑刪除的特徵。
練習
練習 3.1.6
(若全部取樣梯度為 ,求 及零空間,說明哪個位移方向一階不可見。)
基礎
解答(3)
- 1
寫出張量
。
- 2
求特徵向量
沿 的特徵值為 ,沿 為零,故零空間由 生成。
- 3
解讀
只有位移分量的和改變線性化亮度;沿 的位移使所有梯度投影為零,增加對比或同向樣本數也無法使該方向可見。
練習 3.1.7
(固定 ,對亮度 求全部無懲罰最優標記。再求包含亮度一與四的區域之最佳常數。)
基礎
解答(2)
- 1
應用中點規則
中點為四,第一個必標零、第三個必標一,中間兩種皆可。由於代價按像素分開,全部最優標記恰為 、。
- 2
擬合區域亮度
指定區域的均值為 ,平方殘差為 ;配方證明此值最小。
練習 3.1.8
(先後用標準差三及四的高斯平滑,求總標準差與對單一座標角頻率 的衰減因子。)
基礎
解答(2)
- 1
方差相加
關鍵一步
,故結果等於標準差為五的平滑。
- 2
計算乘數
衰減因子為 ,亦等於兩個原因子 與 的乘積。把標準差直接加成七會給出另一個較強的平滑操作。
練習 3.1.9
(粗網格間距為目標的四倍,粗像素位移為 ,換算成細像素單位。為何換算不保證估計正確?給出重複圖樣例子。)
核心
解答(3)
- 1
換算單位
細像素位移是 。
- 2
區分單位與證據
換算只改變座標單位,沒有增加對應的證據。
- 3
舉出歧義
例如每八個細像素重複的條紋,沿重複方向移動整數個週期會給相同匹配。粗取樣還可能增加歧義,所以須回到原比較模型與幾何約束檢查。