動機
假設兩幅圖像都含有可辨認的點,例如校準板的角。即使亮度不同,這些點的對應位置仍可提供對齊圖像的線索。我們擬合一個平移、一個旋轉及共同的尺度。正尺度的相似變換保留角度與距離之比,卻不能表示剪切或透視變形;選擇這個模型,等於對可能的幾何變化作了限制。
以下假設點的對應關係已知。錯配可以嚴重影響最小二乘擬合,少數點上的小殘差亦不能保證整幅圖像都對齊。我們求的是所述有限問題的全局最優解,並未解決配對問題。
定義
設 分別是互相對應的來源與目標特徵點,固定權重 且 。最小化
向量均為列向量。 由滿足 、 的實二階矩陣組成,故排除反射。允許 會包括將所有點壓到一點的情況。若物理模型要求變換可逆,便須要求 ,但此時最小值未必取得。
定義加權重心 、,以及中心化點 、。令
的符號取決於約定:。在精確可逆的情況下,若反過來擬合目標到來源,旋轉方向亦會反轉。
定理/命題
定理 3.2.1
(加權相似變換的全局擬合)
假設 ,記 。若 ,在 下唯一的最優解為
若 ,則 、 配任意旋轉均為最優,且 。若改要求 ,此情況下下確界仍為 ,但沒有最小解。若 ,所有正權重來源點都重合;平移可吸收任意 ,故數據不能辨認旋轉或尺度。
證明與思路
證明
(先中心化,再解一維尺度問題)
固定 ,把殘差寫成 。由於 和 的加權和均為零,求和後交叉項消失,因此
第二項唯一的最小化平移是 。旋轉保持長度,且 ,展開其餘平方得到
對每個 ,柯西–施瓦茨(Cauchy–Schwarz)不等式給出括號至多為 ;當 ,等號要求 。所以全局問題化為在 上最小化 。配方得 ,即證明公式,並在 時給出唯一性。若 ,尺度唯一取零;此時變換不再依賴旋轉。若 ,每個正權重點的 都為零,故任意尺度與旋轉下的中心化殘差均為 ,配上上述平移即可達到。證明檢查了所有容許的旋轉,而不只是某個初始值附近。
證明透視
三次精確消元
證明逐一消去未知量,而每一步都是精確的。先是平移:加權重心恆等式使平移項與每個中心化殘差在加權平方和中正交。重心必須使用與目標函數相同的權重;若權重不等卻用不加權的重心,交叉項便不會消失。其次是旋轉:固定 時,目標函數對單位向量 是仿射的,柯西–施瓦茨不等式在整個圓上找到全局最大值,而非局部最大值。限制在 正是固定 符號的原因;若容許反射,會出現另一個帶自身相關量的候選。最後是尺度:這是一元二次函數,其頂點 自動可行,因為 。假設 只在這裏使用,用以保證這個二次函數嚴格凸。
這個論證也顯示了它的界限:若擬合後按殘差改變權重,目標函數也會改變;這次一步推導不能證明迭代重加權方法收斂。
例題
例題 3.2.2
(四分之一圈旋轉、放大與平移)
等權來源點 分別對應目標點 。重心為 、。代入得 、、、。故 、, 是逆時針四分之一圈,。代回三組原始配對可驗證殘差為零;最小值公式同樣給出 。
例題 3.2.3
(模型無法表示的拉伸)
四個等權來源點 對應目標 :水平軸放大一倍,垂直軸不變。兩個重心均為 ,故 、。於是 、、,而 的每一項都為零,故 。因此 、、、,且 。
直接驗證:擬合點為 與 ,四個特徵點的平方誤差各為 ,總和為 。擬合尺度介於兩條軸的真實尺度之間,誤差平均分攤。這類殘差反映模型不匹配,而非噪聲;柯西–施瓦茨不等式亦確認 。
例題 3.2.4
(塌縮的情況沒有正尺度最小解)
等權來源點 都對應目標點 。則 、。最佳非負尺度擬合以 、 將兩點壓到目標,旋轉任意。若要求 ,殘差是 ,當 趨近零卻始終大於零。聲稱角度唯一或正尺度下已取得最小值,都是虛構了數據沒有提供的結論。
反例模式
旋轉不能修復反射
來源三角形 的目標為反射後的 。此時 、、,故最佳保持方向的相似變換有 ,殘差為 。反射本身可完全擬合,但其行列式為 ,並不屬於 。若求解器默許反射,解的就是另一個配準問題。
常見錯誤
實際應用中,對上述公式有兩種常見誤讀。
常見錯誤
(把 當作擬合良好的保證)
非零只表示正權重的來源點不全重合,並不保證 、配對正確、擬合良好或外推穩健。大權重只表示該點對目標函數有較大影響,並不自動是概率或已證實的精度。若權重取決於目標座標,統計解釋也可能受到影響。
常見錯誤
(在有錯配時仍信任最小二乘)
最小二乘會平方放大大錯配的影響。例如只擬合一維平移時,偏移 的平均值為 ,雖然其中兩個偏移為零。應檢查殘差與配對;若預期有離群值,可考慮另行明確定義的穩健估計法。上述公式精確解決的是加權平方誤差問題,不保證免於錯配。
兩種錯誤都把計算的性質誤當作圖像的性質。
概念視角幾何
對齊與可辨認性是不同問題
算出的變換可以唯一,卻對觀測配對擬合得差;相反,塌縮或重合點可產生小殘差,但參數仍無法確定。應同時檢查原始座標單位中的殘差與特徵點的幾何分布;任何一項都不足以獨自證明整幅圖像已正確對齊。
總結
加權中心化精確消去平移。兩個相關量 決定旋轉,其長度相對於來源點分散程度的比值給出最佳尺度。全局公式依賴固定配對與權重、保持方向的相似模型,以及對零尺度的明確處理;必須對照實際成像任務檢查假設與殘差。
練習
練習 3.2.5
(等權來源點 分別對應 。求最佳 及最小殘差。)
基礎
解答(3)
- 1
中心化數據
兩重心分別是 、,故 、。
- 2
計算相關量
、、,故 。
- 3
讀出變換
、、。兩點均精確對應,殘差為零。
練習 3.2.6
(等權來源點 對應 。求 與變換。若對調兩個目標點的順序,估計角度如何改變?)
基礎
解答(3)
- 1
計算相關量
兩重心均為零。;由於每個 都與其 垂直,;;故 。
- 2
讀出變換
、、:逆時針四分之一圈。
- 3
對調目標點
對調目標點後 ,得到順時針四分之一圈。配對順序是數據的一部分。
練習 3.2.7
(所有正權重來源點均為 ;等權目標點為 、。求最小誤差,並舉出兩組不同的最優參數。)
核心
解答(3)
- 1
計算目標點的分散程度
目標重心是 ,。
- 2
使用退化情況
關鍵一步
最小值為 ,只要把共同來源點送到 即可取得。
依據: ,故對任意 與 ,中心化殘差都等於 。
- 3
舉出兩組最優解
及 均把 映至 。尺度和旋轉都不能辨認。
練習 3.2.8
(假設中心化數據給出 、、、。求最優解與殘差。真正的特徵點數據能否得到負殘差?)
核心
解答(3)
- 1
計算最優解
,,、,而 。
- 2
計算殘差
。
- 3
殘差的符號
殘差是加權平方和,不可能為負。等價地,真正的點數據滿足柯西–施瓦茨不等式 ,此處 ;違反此式的任意數字不能代表這類數據。