此部分是 計算機視覺中的信号處理與模式識别
與其說是講述，不如說是一些經典文章的羅列以及自己的簡單點評。與前一個版本不同的是，這次把所有的文章按類别歸了類，并且增加了很多文獻。分類的時候并沒有按照傳統的分類方法，而是劃分成了一個個小的門類，比如SIFT，Harris都作為了單獨的一類，雖然它們都可以劃分到特征提取裡面去。這樣做的目的是希望能突出這些比較實用且比較流行的方法。為了以後維護的友善，按照字母順序排的序。
15. RANSAC
随機抽樣一緻性方法，與傳統的最小均方誤差等完全是兩個路子。在Sonka的書裡面也有提到。
[1981 ACM] Random Sample Consensus: A Paradigm for Model Fitting with Apphcatlons to Image Analysis and Automated Cartography
[2009 BMVC] Performance Evaluation of RANSAC Family
若引用文獻：
翻譯
随機樣本共識：使用模型拟合圖像分析和自動制圖的範例——
作者：
摘要 -引入了一種新的範例，即随機樣本共識(RANSAC)，用于将模型拟合到實驗資料。 RANSAC能夠解釋/平滑包含很大百分比的總體錯誤的資料，是以非常适合自動圖像分析中的應用，在這些應用中，基于容易出錯的特征檢測器提供的資料進行解釋。本文的主要部分描述了RANSAC在位置确定問題(LDP)中的應用：給定一個圖像，該圖像描述了一組具有已知位置的地标，請确定從中擷取圖像的空間點。響應于RANSAC的要求，新的結果從獲得解決方案所需的最小地标數中得出，并提出了用于以封閉形式計算這些最小地标解決方案的算法。這些結果為可以在困難的檢視和分析條件下解決LDP的自動系統提供了基礎。還介紹了實作細節和計算示例。
關鍵詞和短語：模型拟合，場景分析，相機校準，圖像比對，位置确定，自動制圖。
CR類别：3.60、3.61、3.71、5.0、8.1、8.2
1 引言
我們引入了一種新的範例，即随機樣本共識(RANSAC)，用于将模型拟合到實驗資料。并說明其在場景分析和自動制圖中的用途。讨論的應用程式(位置确定問題(LDP))的處理水準超出了僅使用RANSAC範式的示例；介紹了有關可以解決LDP的條件的新的基本發現，并描述了解決該問題的綜合方法，我們預計該方法将在近期得到實際應用。
在很大程度上，場景分析(實際上是科學)實際上是根據一組預定義的模型來解釋感測資料。從概念上講，解釋涉及兩個不同的活動：首先，存在在資料與可用模型之一之間找到最佳比對的問題(分類問題)；其次，存在為所選模型的自由參數計算最佳值的問題(參數估計問題)。實際上，這兩個問題不是獨立的，通常需要解決參數估計問題以解決分類問題。
用于參數估計的經典技術(例如最小二乘法)(根據指定的目标函數)優化功能描述(模型)對所有呈現資料的拟合。這些技術沒有用于檢測和拒絕重大錯誤的内部機制。它們是平均技術，其依賴于以下假設(平滑假設)：任何資料與假設模型的最大預期偏差是資料集大小的直接函數，是以，無論資料集大小如何，總是會有足夠好的值來消除任何明顯的偏差。
在許多實際的參數估計問題中，平滑假設不成立。即資料包含未補償的嚴重錯誤。為了應對這種情況，已經提出了幾種試探法。通常采用的技術是一種變體，首先使用所有資料來推導模型參數，然後找到與執行個體化模型一緻的資料最遠的位置，假設這是一個嚴重錯誤，将其删除，然後重複此過程，直到出現一個錯誤為止。最大偏差小于某個預設門檻值，或者直到不再有足夠的資料可進行。
可以很容易地證明，一個總的錯誤(“中毒點”)與一組良好的資料混合在一起，會導緻上述啟發式方法失敗(例如，參見圖1)。我們的争論是，将平均值不适用于未經驗證的資料集是不合适的技術。
圖1.最小二乘(和“抛出最壞的殘差”啟發式算法)無法處理錯誤的資料點。
問題：給定圖中顯示的七對(x，y)對，找到一條最佳拟合線，并假設沒有有效基準從該線偏離超過0.8個機關。
評論：七個點中的六個是有效資料，可以通過實線拟合。 使用最小二乘(和“抛出最差殘差”啟發式方法)，我們在四次疊代後終止，剩下四個點，包括虛線拟合的(10,2)處的總誤差。
最小二乘成功逼近
疊代 資料集 拟合的直線
殘差計算
第1項剩餘
在以下部分中，我們介紹RANSAC範例，該範例能夠對包含很大百分比的總體錯誤的資料進行平滑處理。該範例特别适用于場景分析，因為經常犯錯誤的局部特征檢測器是提供給解釋算法的資料的來源。局部特征檢測器會産生兩種類型的錯誤-分類錯誤和測量錯誤。
當特征檢測器錯誤地将圖像的一部分識别為特征的出現時，就會發生分類錯誤。當特征檢測器正确識别特征，但略微錯誤計算其參數之一(例如，其圖像位置)時，就會發生測量錯誤。測量誤差通常遵循正态分布，是以平滑假設适用于它們。但是，分類錯誤是嚴重錯誤，其影響要比測量錯誤大得多，并且不會平均。
在本文的最後部分中，讨論了RANSAC在位置确定問題中的應用：
給定一組在某些坐标系中位置已知的“地标”(“控制點”)，請确定從中擷取地标圖像的空間中該點的位置(相對于地标的坐标系) 。
為了響應RANSAC的要求，在獲得解決方案所需的最小地标數量上得出了一些新結果，然後提出了用于以封閉形式計算這些最小地标解決方案的算法。 (正常技術是疊代的，并且需要很好的初始猜測以確定收斂。)這些結果構成了可以在惡劣的檢視和分析條件下解決LDP的自動系統的基礎。 尤其是，即使由于可見度低，地形變化或圖像分析錯誤而導緻大量地标位置錯誤時，系統也可以正常運作。 給出了實作細節和實驗結果以完善我們對LDP應用程式的描述。
2 随機樣本共識
RANSAC過程與正常平滑技術相反：RANSAC使用盡可能少的初始資料集并擴大其範圍，而不是使用盡可能多的資料來擷取初始解，然後嘗試消除無效資料點。盡可能設定一緻的資料。例如，給定将圓弧拟合到一組二維點的任務，RANSAC方法将選擇一組三個點(因為需要三個點來确定一個圓)，計算中心并隐含圓的半徑，并計算與該圓足夠接近的點數以表明它們與該圓的相容性(即，它們的偏差足夠小以至于會引起測量誤差)。如果有足夠的相容點，則既然已經确定了一組互相一緻的點，則RANSAC将采用平滑技術(例如最小二乘法)為圓的參數計算一個改進的估計。
RANSAC範式更正式地表示如下：
給定一個需要最少n個資料點以執行個體化其自由參數的模型，以及一組資料點P，以使P中的點數大于n [#(P)> =n]，則随機選擇一個子集S1 P中的n個資料點的集合并執行個體化模型。使用執行個體化的模型M1确定在M1的一定容錯範圍内的P中的點的子集S1 *。集SI *被稱為S1的共識集。
如果#(SI *)大于某個門檻值t，該門檻值是P中嚴重錯誤數量估計的函數，則使用S1 *計算(可能使用最小二乘)新模型MI *。
如果#(SI *)小于t，則随機選擇一個新的子集S2并重複上述過程。 如果在經過預定數量的試驗後，未找到具有t個或多個成員的共識集，則可以求解找到的最大共識集的模型，或者終止于失敗。
上述算法有兩個明顯的改進：首先，如果存在與選擇點形成S的原理相關的問題，請使用确定性選擇過程，而不是随機選擇過程。 其次，一旦找到合适的共識集S *并執行個體化了模型M *，則将P中與M *一緻的任何新點添加到S *，然後基于這個更大的集合計算新模型。
RANSAC範式包含三個未指定的參數：(1)用于确定點是否與模型相容的容錯能力；(2)要嘗試的子集數量；以及(3)門檻值t，即數量 用來暗示已找到正确模型的相容點。 在以下小節中讨論了為這些參數計算合理值的方法。
A.建立基準/模型相容性的容錯
基準與模型的偏差是與基準相關聯的誤差和與模型相關聯的誤差的函數(部分是與用于執行個體化模型的資料相關聯的誤差的函數)。如果模型是資料點的簡單函數，那麼通過分析在容錯上建立合理的邊界可能是可行的。但是，這種簡單的方法通常不可行。對于這種情況，通常可以通過實驗估計容錯範圍。樣本偏差可以通過擾動資料，計算模型并測量隐含誤差來産生。然後可以将誤差容限設定為超出測得的平均誤差的一兩個标準偏差。
基準相對于假定模型的預期偏差通常是基準的函數，是以，每個基準的容錯性應該不同。但是，與總誤差的大小相比，誤差容限的變化通常相對較小。是以，針對所有資料的單個錯誤容忍度通常就足夠了。
B.找到共識集的最大嘗試次數
停止選擇P的新子集的決定可以基于選擇n個良好資料點的子集所需的預期試驗次數k。 令w為任何標明資料點在模型的誤差範圍内的機率。 然後我們有：
其中E(k)是k的期望值，b = w n，a =(1-b)。
幾何級數和的辨別為
區分以上關于a的身份，我們有：
進而，
以下是對應于n和w的一些E(k)值的清單：
通常，在放棄之前，我們可能希望将E(k)試驗超出一兩個标準偏差。 請注意，k的标準偏差SD(k)由下式給出：
然後
但是(使用幾何級數恒等式和兩個微分)：
進而，
和
注意，通常SD(k)大約等于E(k)； 是以，例如，如果(w = 0.5)和(n = 4)，則E(k)= 16且SD(k)= 15.5。 這意味着可能要嘗試使用k隐含的預期随機選擇數的兩倍或三倍(如上表所示)，以獲得超過t個成員的共識集。
從稍微不同的角度來看，如果我們要以機率z確定至少一個随機選擇是n個資料點的無錯誤集合，那麼我們必須期望至少進行k個選擇(每n個資料點 選擇)，其中
例如，如果(w = 0.5)和(n = 4)，則(b = 1/16)。為了獲得90％的保證至少做出一個無差錯的選擇，
C.可接受的共識集的大小的下界
門檻值t是RANSAC範式的形式聲明中未指定的參數，用作确定已發現P的n個子集的基礎，該子集暗示有足夠大的共識集以允許算法終止。是以，必須選擇足夠大的t以滿足以下兩個目的：已經為資料找到了正确的模型，并且已經找到足夠數量的互相一緻的點來滿足最終平滑過程的需要(該過程可以計算出改進的估計值)用于模型參數)。
為了確定最終的共識集與錯誤的模型相容，并假設y是任何給定資料點在錯誤模型的容錯範圍内的機率，我們希望.yt-n非常小。盡管沒有通用的方法可以精确地确定y，但可以合理地假設它小于w(w是給定資料點在正确模型的誤差範圍内的先驗機率)。假設y <0.5，則t-n等于5的值将提供大于95％的機率，即不會出現與錯誤模型的相容性。
為了滿足最終平滑過程的需要，必須指定要使用的特定過程。如果要使用最小二乘平滑法，則在許多情況下可以調用形式方法來确定産生所需精度所需的點數[10]。
D.例子
讓我們将RANSAC應用于圖1所示的示例。w的值(任何標明資料點在模型的誤差容差之内的機率)等于0.85與資料一緻，并且容差(用于建立基準/問題陳述中提供了0.8個機關的模型相容性)。無需外部平滑最終共識集即可接受由RANSAC提供的模型；是以，我們希望獲得一個包含所有七個資料點的共識集。由于這些要點之一是嚴重錯誤，很明顯，我們找不到所需大小的共識集，是以我們将以能夠找到的最大集終止。先前提出的理論表明，如果我們一次擷取兩個資料點，通過它們計算線并測量剩餘點與該線的偏差，那麼我們應該期望在兩三個試驗中找到合适的共識集；但是，由于資料量有限，我們可能願意嘗試所有21種組合以找到最大的共識集。無論哪種情況，我們都可以輕松找到包含六個有效資料點及其所暗示的線的共識集。
3 位置确定問題(LDP)
圖像分析中的一個基本問題是在給定場景的兩種表示形式的元素之間建立對應關系。這個問題的一個變體，在制圖學中尤其重要，是通過識别圖像中出現的一組界标(控制點)來确定從中獲得圖像或照片的位置(這又稱為确定元素的問題)外部相機方向，相機校準問題或圖像與資料庫的對應問題)。通常使用最小二乘法[11，8]與人類操作員解決，以互動方式建立圖像點與相應控制點的三維坐标之間的關聯。但是，在全自動系統中，對應關系必須基于邊緣勝任的特征檢測器的決策，是以最小二乘法通常無法處理可能導緻的嚴重誤差； 在第二節中對此進行了詳細讨論，在第四節介紹的示例中為LDP進行了說明。
在本節中，将基于RANSAC範式介紹LDP的新解決方案，該解決方案在承受輸入資料中的嚴重錯誤方面具有獨特的能力。我們将首先研究可以解決LDP的條件，并描述有關該問題的新結果。然後，我們對基于RANSAC的算法進行完整描述，最後，描述通過使用該算法獲得的實驗結果。
LDP的正式定義如下：
給定一組m個控制點，在某個坐标系中已知其3維坐标，并給出一個圖像，其中可見m個控制點的某些子集，請确定位置(相對于控制點的坐标系)從中獲得圖像。
我們首先假設我們知道n個圖像點和控制點之間的對應關系；稍後我們考慮其中某些對應關系無效的情況。我們還将假設成像系統的像平面中的主點(相機的光軸刺穿像平面)和焦距(從透視中心到像平面中的主點的距離)衆所周知是以(參見圖2)，我們可以輕松地從透視中心(CP)計算與任何一對控制點的角度。最後，我們假設攝像頭位于包圍控制點的凸包的外部和上方。
圖2.位置确定問題的幾何形狀。
稍後我們将示範(附錄A)，如果我們可以計算從CP到三個控制點的光線的長度，那麼我們可以直接求解CP的位置(以及圖像平面的方向(如果需要))。 是以，LDP的等效但在數學上更簡潔的陳述是
給定n個控制點的相對空間位置，并給與稱為“視點中心(CP)”的附加點到每對控制點的角度，找到将CP連接配接到每個控制點的線段(“腿”)的長度 控制點。 我們稱其為“透視n點”問題(PnP)。
為了應用RANSAC範式，我們希望确定可以解決PnP問題的n的最小值。
A.透視點問題的解決方案
P1P問題(n = 1)不提供任何限制資訊，是以解決方案的無限性是可能的。 如圖3所示，P2P問題(n = 2)也承認了解決方案的無限性。 CP可以駐留在直徑為Rab / sin(θab)的圓上的任何位置，并圍繞連接配接兩個控制點A和B的弦(線)在空間中旋轉。
圖3. P2P問題的幾何形狀。
圖4. P3P問題的幾何形狀(L是透視中心)。
P3P問題(n = 3)要求我們在給定基本尺寸和相對的三面角的面角的情況下确定四面體的三個支腿的長度(請參見圖4)。 三個方程[A *]暗示了這個問題的解決方案：
衆所周知，在n個未知數中，n個獨立的多項式方程所具有的解數不能超過其各自階數的乘積[2]。 是以，系統A *最多可以有八個解決方案。 但是，由于系統A *中的每個項都是常數或二次度，是以對于每個實數正解，都有一個幾何同構的負解。是以，對于A *，最多有四個正解，在圖5中， 顯示一個示例，證明四個解決方案的上限是可以達到的。
圖5.一個示例，顯示了四個不同的P3P問題解決方案。
考慮圖5(a)中的四面體。基本ABC是等邊三角形，并且“腿”(即LA，LB和LC)都相等。是以，L處的三個面角(即＜ALB，＜ALC和＜BLC)都相等。根據餘弦定律，我們有：
Cos(α)= 5/8。
該四面體定義了一種解決P3P問題的方法。第二種解決方案如圖5(b)所示。它是通過從L繞BC旋轉開始而獲得的。給定剛性三角形ABC和角度α，有必要驗證L'A的長度可以為1。根據餘弦定律，我們有：
減少到：
是以，L'A可以為1或4。圖5(a)示出L'A = 4的情況，圖5(b)示出L'A = 1的情況。
請注意，重新放置基礎三角形以使其頂點移動到腿上的不同位置等效于重新放置L。圖5(c)顯示了對應于第二個解的基礎三角形的位置。
由于圖5(a)中的四面體是三重旋轉對稱的，是以可以通過圍繞AB和AC旋轉三角形來獲得兩個以上的解決方案。
圖6.具有兩個解決方案的P4P問題的示例。
圖6(a)指定了P4P問題并示範了一種解決方案。 第二種解決方案可以通過繞BC旋轉底座，使A放置在其腿上的不同點來實作(參見圖6(b))。 為了驗證這是一個有效的解決方案，請考慮X = O平面，該平面垂直于BC并包含點L，A和D。圖6(c)顯示了此平面中的重要特征。 alpha的餘弦為119/169。 β圍繞BC的旋轉将A重新定位在A'。 餘弦定律可用于驗證A'的位置。
要完成此解決方案，必須驗證D的旋轉位置在LD上。 考慮圖6(c)中的點D'。 它與P的距離與D的距離相同，并且根據餘弦定律，我們可以證明γ等于β。 是以，LD上的D'是D的旋轉位置。點A'，B，C和D'構成了問題的第二種解決方案。
在附錄A中，我們導出了系統A *的顯式代數解。 這是通過将A *簡化為一個表示四面體兩邊之比的未知數的二次(四次)多項式，然後直接求解該方程來實作的(我們還提供了一種非常簡單的疊代方法來從給定問題中獲得解) 資料)。
對于n = 4的情況，當所有四個控制點都位于同一平面(不包含CP，并且在任何一條線上不超過兩個控制點)時，我們在附錄B中提供一種技術 總是産生獨特的解決方案。 出乎意料的是，當所有四個控制點都不在同一平面上時，就無法始終確定獨特的解決方案。 例如，圖6顯示，在控制點處于“正常位置”的情況下，對于P4P問題至少有兩種解決方案是可能的。
為了在四個非平面控制點的情況下求解CP的位置，我們可以在一次三個控制點的兩個不同子集的控制點上使用附錄A中介紹的算法；兩個子集共有的解決方案将CP定位在給定資訊固有的歧義之内。
用于建構圖6中所示示例的方法可以擴充到任意數量的附加點。它基于圖3所示的原理：如果CP和任意數量的控制點位于同一圓上，則任意一對控制點與CP之間的角度将與CP圓上的位置無關(是以無法确定CP的位置)。是以，我們能夠建構圖7所示的示例，其中五個控制點在一般位置暗示了P5P問題的兩個解決方案。盡管相同的技術将适用于六個或更多控制點，但是這些點中的四個或更多現在必須位于同一平面上，是以不再處于一般位置。
圖7.一個帶有兩個解的P5P問題的示例。
為了證明六個(或多個)控制點在總位置上始終可以産生唯一的P6P問題解決方案，我們注意到，在這種情況下，我們始終可以求解指定映射的3 x 4矩陣T的12個系數( 在同構坐标中)從3空間到2空間； 六個對應關系中的每個對應關系提供了三個新方程式，并引入了一個附加的未知量(齊次坐标比例因子)。 是以，對于六個控制點，我們有18個線性方程來求解18個未知數(實際上，可以證明，至多17個未知數是獨立的)。 給定變換矩陣T，我們可以構造一個與其他三個給定控制點位于同一平面的附加(合成)控制點，并計算其在圖像平面中的位置； 現在可以使用附錄B中描述的技術來找到獨特的解決方案。
4 實施細節和實驗結果
A.RANSAC / LD算法
RANSAC / LD算法接受以下資料作為輸入：
(l)m個6元組的清單L-每個6元組包含一個控制點的3D空間坐标，其對應的2D圖像平面坐标以及給出預期誤差的可選數字(以像素為機關) 圖像平面中給定位置的位置。
(2)成像系統的焦距和主要點的像平面坐标。
(3)6元組包含嚴重不比對的機率(1-w)。
(4)一個“置信度”數G，用于設定内部門檻值，以接受有助于求解的中間結果，其中一個的置信度數使算法具有非常保守的行為； 置信度為零将幾乎調用任何有效的解決方案。
此示例與圖6中描述的P4P示例相同，不同之處在于，已添加了第五個控制點E。 E的初始位置及其旋轉位置E'如圖7所示。點E和E'被構造為A'和A圍繞線LP的鏡像； 是以，α圍繞P的旋轉将E重新定位到E'。 P5P問題的一種解決方案由點A，B，C和D(如圖6(a)所示)加上點E構成。第二種解決方案由點A'，B，C，D'和E形成 '。 是以，L有兩個不同的位置，是以所有五個點都位于其适當的邊上。
RANSAC / LD算法産生以下資訊作為輸出：
(l)鏡頭中心(即透視中心)的3-D空間坐标，以及相應誤差的估計值。
(2)圖像平面的空間方向。 RANSAC / LD算法的操作如下：
(1)通過準随機方法從清單L中選擇三個6元組，該方法確定了相應控制點的合理空間分布。此初始選擇稱為S1。
(2)使用附錄A中提供的閉式解确定對應于選擇項S1的CP(稱為CP1)；在以下步驟中，将多個解決方案視為從單獨的選擇中擷取。
(3)通過擾動三個標明控制點的給定像平面坐标(通過6元組指定的數量或通過一個像素的預設值)，然後重新計算，可以估算CP 1的導出位置中的誤差。這将對CP1的位置産生影響。
(4)給定CP1的誤差估計，我們使用[1]中描述的技術來确定清單L中指定的每個控制點在圖像平面中的誤差橢圓(基于提供的置信度的尺寸)； 如果關聯的圖像坐标位于相應的誤差橢圓内，則将6元組附加到共識集S1 / CP1。
(5)如果S1 / CP1的大小等于或超過某個門檻值t(名義上等于7和行之間的值)，則将共識集S1 / CP1提供給最小二乘例程(請參見[l]或 [7])用于最終确定CP位置和圖像平面方向。 1否則，将使用新的随機選擇S 2，S 3重複上述步驟...
(6)如果上述步驟的疊代次數超過k = [log(l-G)] / [log(1- w3)]，則使用迄今為止找到的最大共識集來計算最終解(或 如果此最大共識集包含少于六個成員，則我們将以失敗告終)。
1 最小二乘的一種替代方法是對根據共識集内的随機三元組計算的參數取平均值，該參數位于(例如)相關直方圖的中心50％之内。
B.實驗結果
為了證明我們的理論結果的有效性，我們進行了三個實驗。在第一個實驗中，我們發現了一個特定的LDP，其中常見的最小二乘修剪啟發式方法失敗，并表明RANSAC成功解決了此問題。在第二個實驗中，我們将RANSAC應用于50個綜合問題，以便在廣泛的參數值範圍内檢查該方法的可靠性。在第三個實驗中，我們使用标準的特征檢測技術來定位航空圖像中的地标，然後使用RANSAC确定相機的位置和方向。
C.最小二乘修剪誤差的位置确定問題示例
此實驗中的LDP基于20個界标及其在圖像中的位置。 20封信函中有5封屬于嚴重錯誤；也就是說，它們在圖像中的給定位置距離其實際位置至少10個像素。良好對應關系的圖像位置通常圍繞它們的實際位置分布，标準偏差為一個像素。
修剪嚴重錯誤的啟發式方法如下：
*使用所有對應關系來執行個體化模型。
*在該模型的基礎上，删除與其預測圖像位置有最大偏差的對應關系。
*執行個體化沒有該對應關系的新模型。
*如果新模型暗示删除的對應關系的标準化誤差大于三個标準偏差，則假定它是一個嚴重誤差，将其排除在外，然後繼續删除對應關系。否則，假設這是一個很好的對應關系，然後傳回包含它的模型作為問題的解決方案。
這種啟發式方法成功删除了兩個重大錯誤；但是在删除了第三個後，它決定新模型并不意味着很大的錯誤，是以它傳回了基于18個對應的解決方案，其中三個是嚴重錯誤。當将RANSAC應用于此問題時，它将正确的解決方案放在所選點的第二個三元組上。最終共識集包含所有良好的對應關系，沒有任何重大錯誤。
D.50綜合位置确定問題
在該實驗中，RANSAC被應用于50個合成LDP。每個問題都基于30個地标與圖像的對應關系。使用了一系列機率來确定問題中嚴重錯誤的數量。大錯誤的圖像位置距離其實際位置至少10個像素。良好對應關系的位置圍繞其實際位置分布，其标準偏差為一個像素。使用了兩個不同的攝像頭位置-一個直接在地标上向下看，另一個從傾斜角度看它們。本節前面介紹的RANSAC算法已應用于這些問題。但是，附錄A中描述的簡單疊代技術用于定位P3P問題的解決方案來代替該附錄中也描述的閉式方法，并且使用第二個最小二乘拟合來擴充最終共識集(如Sec中所建議)本文二)表一總結了十個典型問題的結果(RANSAC成功地避免了在所有問題的最終共識中都包含嚴重錯誤)；在其中五個問題中，良好對應的機率為0.8，在其他五個問題中，機率為0.6。對于所考慮的每個錄影機位置，目前程式的執行時間約為1秒。
表I.使用RANSAC的典型實驗結果。
良好通信數量、最終共識集中的信函數量、考慮的三元組數、考慮的錄影機位置數
E.“真實”位置确定問題
使用互相關來在使用6英寸鏡頭從大約4,000英尺拍攝的航拍圖像中定位25個界标。 圖像在2,000 x 2,000像素的網格上被數字化，這意味着每個像素大約2 ft的地面分辨率。 相關特征檢測器産生了三個總體誤差。 當将RANSAC應用于此問題時，它在選擇的第一個三元組中找到了17個共識集，然後将其擴充為包括最初最小二乘拟合後的所有22個良好對應。 有關錄影機參數的最終标準偏差如下：
5 結論意見
在本文中，我們介紹了一種新的範例，即随機樣本共識(RANSAC)，用于将模型拟合到實驗資料。 RANSAC能夠解釋/平滑包含很大百分比的總體錯誤的資料，是以非常适合自動圖像分析中的應用，在這些應用中，基于容易出錯的特征檢測器提供的資料進行解釋。
本文的主要部分描述了RANSAC在位置确定問題(LDP)中的應用：給定一個圖像，該圖像描述了一組具有已知位置的地标，請确定從中擷取圖像的空間點。我們提供的有關解決方案技術和LDP問題的幾何形狀的大多數結果都是新的，或者是未知的。目前的攝影測量文獻除了最小二乘法的變體和用于解決透視點問題的丘奇方法外，沒有提供任何解析解決方案。提出的Church方法為P3P問題提供了一種疊代解決方案[3，11]，但沒有任何迹象表明可能有多個實體上的實際解決方案。當然，沒有迹象表明有人意識到，對于一般位置上的三個以上控制點，實體上實際的多種解決方案是可能的。 (應注意，由于可以将多個解任意任意地靠近在一起，即使将疊代技術初始化為接近正确解的值，也無法保證會收斂到所需值。)
在有關LDP問題(及相關附錄)的部分中，我們已完全表征了P3P問題并提供了封閉形式的解決方案。我們已經表明，對于P4P和P5P問題，可以存在多個實體上實際的解決方案，而且還證明了當四個控制點位于同一平面上時，可以確定獲得唯一的解決方案(每種情況都提供了解決方法)。确定P4P和P5P問題可能的最大解決方案數目的問題仍然懸而未決，但是我們已經表明，當控制點處于一般位置時，P6P問題存在唯一的解決方案。
附錄A.視角三點問題的解析解決方案
本文的主體确定了P3P問題可以有多達四個解決方案。 在本附錄中，導出了用于擷取這些解決方案的閉式表達式。 我們的方法涉及三個步驟：
(1)根據給定的基數(由三個控制點定義)和相對的三面角的面角(相對于三對控制點的三個角度)，找到(“透視”)四面體的腿長 來自CP)； (2)相對于最初指定了控制點的3-D參考系定位CP； (3)計算像平面相對于參考架構的方向。
1.透視四面體的解決方案(見圖4)
給定四面體基部的三個側面的長度(Rab，Rac，Rbc)，并給定相對的三面角的相應面角(θab，θac，θbc)，求出四面體的其餘三個側面的長度 四面體(a，b，c)。
可以通過同時求解方程組來解決上述問題：
現在，我們進行如下操作：
從等式 (A5)和(A7)
從等式 (A6)和(A7)
從等式 (A8)和(A9)
從等式 (A9)和(A10)
公式(A11)和(A12)具有以下形式：
将(A13)和(A14)分别乘以m'和m，然後減去，
分别将方程式(A13)和(A14)乘以q'和q，分别減去并除以y，
假設
則等式(A15)和(A16)等于等式(A13)和(A14)。 現在，我們将方程式(Al5)乘以(m'* q-m * q')，并将方程式(A16)乘以(p * m'-p'* m)，然後減去以獲得
擴充等式(A17)并分組項，我們在x中獲得一個雙二次(四次)多項式：
式(A18)的根可以以閉合形式[5]或通過疊代技術[4]找到。 對于等式(A18)的每個正實根，我們為邊a和b的每一個确定單個正實值。 從等式(A6)
并從等式 (A4)我們獲得
如果
然後從等式 (A16)我們有
如果
，然後等式 (A26)是未定義的，我們從等式(A5)獲得兩個y的值：
對于y的每個真實正值，我們從公式(A4)獲得c的值：
當從等式(A5)而不是等式(A26)獲得y值時，所得解可能無效； 必須先證明它們滿足等式(A3)，然後再接受它們。
應該注意的是，因為等式(A 18)的每個根都可以導緻兩個不同的解決方案，是以雙二次方程式的存在本身并不意味着最多可以解決P3P問題的四個解決方案。 為了确定四個解的上限，還需要一些其他論點，例如本文的主體中給出的論點。
2.例子
對于圖5中所示的透視四面體，我們具有以下參數：
将這些值代入公式(A19)至(A23)，我們得到公式(A18)中定義的雙二次系數：
[-0.5625, 3.515625, -5.90625, 3.515625, -0.5625]
上式的根是[1，1，4，0.25]
對于每個根
3.一種透視四面體的替代解決方案(請參見圖8)
圖8. P3P問題疊代解決方案的幾何。
定位P3P問題解決方案的簡單方法(有時可以代替前面小節中介紹的更複雜的過程)是将控制點三角形的一個頂點滑到四面體的邊上并查找其位置的簡單方法。其他兩個頂點分别位于其腿上的三角形。如果頂點A與L的距離為a(L是透視中心)，則邊Rab和Rac的長度會将三角形限制在四個可能的位置。給定腿LA和LB之間的角度，計算點A與直線LB的距離，然後計算LB上的點B1和B2，即距A的适當距離，以插入長度為Rab的線段。類似地，我們在其腿上最多計算兩個位置。是以，給定A的位置，我們發現三角形的一個側面的長度為Rab且長度為Rac的三角形至多為四個。随着點A向下移動，四個三角形的第三邊(BC)的長度呈非線性變化。通過疊代地重新放置A以暗示所需長度的第三面，可以解決該問題。
4.計算透視中心的3D位置(見圖9)
圖9計算透視中心的3-D位置(L)。
給定透視四面體的三個控制點的三維位置以及三個支腿的長度，可以按如下方式計算透視中心的3D位置：
(1)構造一個垂直于A B并穿過透視中心L的平面P 1。可以在不知道L位置的情況下構造該平面，這就是我們試圖計算的位置。考慮包含頂點A，B和L的四面體的面。知道邊LA，LB和A B的長度後，我們可以使用餘弦定律找到角度LAB，然後找到LA在AB上的投影QA。 (請注意，角度LQA是直角，點Q是線AB上最接近L的點)。構造一個垂直于AB并通過Q的平面；這架飛機也穿過L。
(2)類似地構造垂直于A C d穿過L的平面P2。
(3)構造由點A，點B和點C定義的平面P3。
(4)相交平面P1，P2和P3。通過構造，交點R是P3上最接近L的點。
(5)計算線AR的長度，并将其與LA的長度結合使用以計算線RL的長度，即線L與平面P3的距離。
(6)計算向量AB和A C的叉積，以形成垂直于P3的向量。然後将該矢量按RL的長度進行縮放，并将其添加到R中，以擷取透視圖中心L的3-D位置。
如果知道相機的焦距和像平面中的主要點，則可以計算像平面相對于世界坐标系的方向；即，原點的位置和圖像平面坐标系相對于3D參考系的方向。可以按照以下步驟進行：
(1)計算透視中心的3D參考幀坐标(如上所述)。
(2)計算三個控制點的圖像位置的3-D坐标：由于我們知道了CP和控制點的3-D坐标，是以我們可以計算CP之間的三個射線的3-D坐标和控制點。知道了成像系統的焦距，我們可以計算每條射線從CP到沿着射線的像平面的距離，并從中減去。
(3)使用在步驟(2)中找到的三個點計算包含圖像的平面的方程。穿過CP的該平面的法線為我們提供了圖像平面坐标系的原點(即主點的3D位置)以及該系統的Z軸。
(4)可以通過計算從主點到在步驟(2)中找到的任何一個點的矢量的3-D坐标來獲得像平面繞Z軸的取向。
附錄B.透視4點問題的解析解決方案(所有控制點都位于同一平面内)
在本附錄中，提出了一種分析技術，用于在四個給定的控制點都位于同一平面上時獲得P4P問題的唯一解決方案。
1.問題陳述(參見圖10)
圖10. P4P問題的幾何形狀(所有控制點都位于同一平面中)。
給定：位于3D空間中的平面中的四個點(稱為對象平面)與位于不同平面中的四個點(稱為圖像平面)之間的對應關系； 并給出透視中心與像平面之間的距離(即成像系統的焦距)； 并且還給出了像平面中的主要點(即，在像平面坐标中，鏡頭的光軸刺穿像平面的點的位置)。
查找：透視中心相對于物平面坐标系的3-D位置。
2.記法
*标記四個給定的圖像點(Pi)，并标記四個對應的對象點{Qi}。
*我們将假定二維圖像平面坐标系的原點為主要點(PPI)。
*我們将假設在參考坐标系中物平面的方程Z = 0。 可使用标準技術從該坐标系轉換為地面參考系(例如，參見[61或[91])。
*将假設為同質坐标[12]。
*帶撇号的符号表示轉置的結構。
3.解決程式
(a)計算将點從物平面映射到像平面的3×3排列矩陣T(稍後将給出計算T的過程)：
(b)通過變換将物平面中坐标為[0，0，1]'的理想線映射到圖像平面[VLI]中的消失線：
(c)确定從像面原點(PPI)到消失線的距離D1 [VLI] =[al, a2, a3]':
(d)求解像平面和物平面之間的二面角(傾斜角)θ：
其中f =焦距。
(e)通過變換将圖像平面中坐标為[0，0，1]'的理想線映射到物體平面[VLO]中的消失線
(f)計算點[PPO]在物平面中的位置([PPO]是鏡頭光軸穿透物平面的點)：
(g)計算物平面中從[PPO] = [cl，c2，c3]'到消失線[VLO] = [b1，b2，b3]'的距離DO：
(h)求出“平移”角$作為[VLO] = [bl，b2，b3]'的法線與物平面中X軸之間的夾角：
(i)确定XSGN和YSGN：如果穿過[PPO]的線(與物平面中的X軸平行)與[PPO]右側的[VLO]相交，則XSGN =1。否則，XSGN = -1。進而，
(j)解決CP在物平面坐标系中的位置：
注意：如果(b)中确定的[VL1]具有坐标[0，0，k]，則圖像平面和物平面平行(θ = 0)。現在，我們不再使用上述過程，而是使用相似的三角形和歐幾裡得幾何來求解所需的資訊。
4.計算歸類矩陣T
讓