動機
特徵偵測器找出兩幅圖像中可能重複出現的位置,卻沒有告訴我們第一幅圖的某個點對應第二幅圖的哪一點。描述子把點附近的外觀概括成一個向量;比較向量後,我們得到的仍只是候選配對。相似的外觀也可能來自另一個相似物件,所以配準還要檢驗多個配對在幾何上是否一致。本節建立一個簡單流程,並釐清其取樣概率究竟保證了甚麼。
定義
定義 5.2.1
(描述子距離)
設兩幅圖的偵測位置分別為 和 ,描述子分別為 。對實數向量,一個選擇是歐氏(Euclidean)距離 。描述子不是點的位置:其座標記錄的是所選的局部圖像量。比較前,兩邊必須用相容的方式構造及縮放。二進制描述子一般可用漢明(Hamming)距離;任意編碼後使用歐氏距離不一定有意義。
定義 5.2.2
(比值檢查)
固定一個來源描述子,把目標距離連同其索引排序為 。若至少有兩個目標描述子、,選定 ,只有在下式成立時才接納最近的目標:
這個比值衡量的是最近候選相對於其他候選有多獨特,並非配對正確的概率。嚴格不等式會拒絕正距離的平手。若兩個最近距離均為零,比值沒有定義,我們把情況視為模糊並拒絕;若候選不足兩個,也無法計算比值。若只有第一個距離為零而 ,它會通過,但仍可能配錯。
常見錯誤
(把比值閾值直接用於距離平方)
許多程式儲存的是距離平方。若最近兩個距離為 和 、,比值為 ,配對應被拒絕;若把平方比值 與同一 比較,卻會接納它。等價的平方距離條件是 ,此處為 ,並不成立。
定義 5.2.3
(互為最近鄰檢查)
互為最近鄰檢查還要求:所選目標的最近來源也包括原來的來源;遇到平手時須先訂明處理規則。
它能排除部分多對一配對,卻不能證明配對正確。亦可加入絕對距離上限,排除雖然相對獨特、但其實並不相似的候選;上限的尺度取決於描述子及數據。重複紋理、遮擋,或真正對應點根本不在候選集合中,都可能令這些檢查失效。
幾何一致集合
定義 5.2.4
(前向殘差與一致集合內點)
對候選配對 和變換 ,定義前向殘差 ,單位是目標圖像的座標單位。指定閾值 後,若 ,便稱該配對是這個模型的一致集合內點。
這標籤只表示它與某模型相符,並不表示它的真實身分已被證實。閾值應考慮量測噪聲和座標單位;改變圖像解析度卻不調整閾值,檢驗的意義也會改變。
考慮平移 ,一對點已可提出候選 。用全部候選配對評分,保留有較多一致配對的模型,再用選中的配對重新擬合。對二維保方向相似變換,兩個來源點不同、目標點也不同的配對可確定一個候選;退化樣本必須排除。其他模型有各自最少樣本數及退化條件。擬合後應檢查殘差在圖像中的分布,並用未參與選模型的數據檢驗對齊:某個重複圖案形成龐大一致集合,仍可能不是我們希望配準的物件。
概念視角幾何
外觀和幾何回答不同問題
描述子距離比較局部外觀;幾何殘差則檢查一個整體變換能否解釋點的位置。可靠流程需要兩者,但若另一組錯配支持另一個變換,它仍可能同時通過兩種檢查。
定理或命題
定理 5.2.5
(抽中全內點樣本的概率)
設 是整數,且 、、、。固定 個候選配對,其中恰有 個是真正內點。每次試驗從中均勻、不放回地選出 個不同配對;各次試驗互相獨立,而且每次都重新從全部 個配對取樣。一次試驗全是內點的概率為
其中 時分子視為零。進行 次後,至少一次抽到全內點的概率為 。當 ,要使這概率至少為 ,充要條件是
若 ,任何有限次數都不夠;若 ,一次便足夠。這是取樣保證,並不保證所得變換準確,也不保證它最後被選中。
選定一致集合之後,平移模型的重新擬合有封閉形式。
命題 5.2.6
(平移的最小二乘重新擬合)
設 是非空有限的候選配對 集合,位移為 。使 最小的平移唯一,且等於平均位移 。
證明思路
證明
(計算子集與獨立試驗)
所有 個子集等可能,其中全由內點構成的恰有 個。一次失敗的概率為 ;由各次試驗之間的獨立性,全部失敗的概率是 。取補事件便得到結論。當 ,取對數後除以負數 ,不等號方向反轉;最後向上取整,便得到所需最小整數。
證明透視
取樣概率沒有涵蓋甚麼
定理中的每個假設各用一次。均勻選取 元子集,使計數比值成為概率,共有 個等可能結果。不放回取樣,使有利結果恰為內點集合的 元子集。若可放回並計次序,計數便是 中的 ;這正是常見近似 的來源,而它在此一般並非精確值。獨立性只用於試驗之間,即乘積 ;同一次試驗內的配對並不獨立,也不需要獨立。
上界中的關鍵一步是除以 :當 它是負數,不等號因此反轉。 時此對數為零, 時它無定義,所以兩種情況須另行說明。被計算的事件是抽到全內點樣本;退化、噪聲、閾值篩選及模型選擇都在證明範圍以外。
重新擬合只是一次初等的配方。
證明
(用配方求平均位移)
由於 ,在 附近展開:
因為交叉項 為零。第二個和與 無關,第一項恰在 時為零。
例子
例題 5.2.7
(獨特的描述子仍可能配錯)
設 ,目標描述子為 、、。最近兩個距離是 和 ;取 時,因 ,第一個通過。假設 實際屬於另一個重複物件,而真正對應點被遮擋,檢查仍會通過,因為它只比較給定候選。若用距離平方 ,等價判斷是 ,不是 。
例題 5.2.8
(含一個離群配對的平移一致集合)
考慮四對候選:、、 和 。它們提出的位移依次是 。取 ,第一個候選模型得到三個內點,最後一個得到一個。對前三個位移做最小二乘平移擬合,即取平均,得到 ,三個殘差都是零。若四個都使用,平均則是 ,可見一個嚴重錯配的影響。一致性方法並沒有證明前三對是真配對,只找到一個受到它們支持的模型。
例題 5.2.9
(有限取樣的精確概率)
若 、、,一次成功概率為 ,不是 。三次獨立試驗至少成功一次的概率為 。若要求至少 ,需七次:,而 。
常見誤解
反例模式
龐大的錯誤一致集合
假設四對正確配對共有平移 ,另有六對錯配共有平移 。取 ;兩個位移相距 ,所以沒有平移能同時接納兩組。兩組都完全符合各自的變換,但最大一致集合會選擇六個錯配。幾何一致本身不能辨認我們想要的是哪個實體;還需要先驗資訊、較大範圍的圖像背景或獨立驗證。
取樣信心是另一個容易把正確公式過度解讀的地方。
常見錯誤
(把取樣界讀成配準保證)
把估計的內點比例代入置信度公式,不能自動得到無條件保證:比例估計和各次均勻獨立取樣的假設都要有依據。增加 也不能修復不合適的變換、過大的閾值,或缺乏代表性的候選集合。重新擬合可能改變哪些配對落在閾值內;若反覆重新分類,就要訂明停止規則,不能自動假設每項想改善的指標都會單調變好。
小結
描述子提供局部候選,比值和互為最近鄰檢查可減少部分模糊性。幾何一致集合檢查候選是否支持共同變換,再擬合利用選出的配對。在明確假設下,取樣信心只量度抽到全內點子集的機會,不等於正確配準的確定性。
練習
練習 5.2.10
(最近兩個距離為 和 ,。判斷是否接納;再用距離平方判斷,並寫出正確閾值。)
基礎
解答(2)
- 1
應用比值檢查
,故接納。
- 2
改寫為距離平方
,同樣接納;平方距離的閾值是 。
練習 5.2.11
(三個目標距離為 。比值檢查能否區分最近的兩個?若距離變為 又如何?)
基礎
解答(2)
- 1
檢查兩個零距離
比值為 ,無定義,應視為模糊並拒絕。
- 2
檢查單一零距離
比值為 ,通過任何正閾值,但配對仍不一定正確。
練習 5.2.12
(五個候選平移為 。取 ,求候選 和 的分數,再分別求較大一致集合及全部五個位移的最小二乘擬合。)
核心
解答(2)
- 1
為兩個候選評分
兩個不同位移相距五,大於 ;分數分別為四和一。
- 2
以平均位移重新擬合
選出的四個位移平均為 ;全部五個平均為 。
依據: 最小二乘平移等於平均位移。
練習 5.2.13
(六對候選中有四對是真正內點,每次均勻選取兩個不同配對,各次試驗獨立。求兩次中至少一次全是內點的概率,並解釋它為何不是最終正確配準的概率。)
核心
解答(3)
- 1
計算一次試驗的概率
。
- 2
合併兩次獨立試驗
。
- 3
說明未涵蓋的部分
退化樣本、噪聲、模型選擇和另一個錯誤一致集合仍可能妨礙正確配準。