随机样本一致性
用于参数估计的经典技术，例如最小二乘法，优化（根据指定的目标函数）功能描述（模型）对所有呈现数据的拟合。这些技术没有检测和拒绝严重错误的内部机制。它们是依赖于假设（平滑假设）的平均技术，即任何数据与假设模型的最大预期偏差是数据集大小的直接函数，因此无论数据集大小如何，都有总是有足够好的价值来消除任何严重偏差。
RANSAC使用尽可能小的初始数据集，并在可能的情况下使用一致的数据扩大该数据集。
RANSAC范式更正式地表述如下：
给定一个模型，它需要最少\(n\)个数据点来实例化其自由参数，以及一组数据点\(P\)，使得\(P\)中的点数大于\(n[\sharp(P)\geq n]\)，随机选择一个子集来自\(P\)的\(n\)个数据点的\(S1\)并实例化模型。使用实例化模型\(M1\)来确定\(P\)中的点的子集\(S1^*\)，这些点在\(M1\)的某个容错范围内。集合\(S1^*\)称为\(S1\)的共识集（consensus set）。
如果\(\sharp(S1^*)\)大于某个阈值\(t\)，它是\(P\)中粗差1数估计值的函数，则使用\(S1^*\)计算（可能使用最小二乘法）新模型\(M_1^*\)。
如果\(\sharp(S1^*)\)小于\(t\)，随机选择一个新的子集\(S2\)，重复上述过程。如果经过预先确定的试验次数后，没有找到具有\(t\)个或更多成员的共识集，则要么解决找到的最大共识集的模型，要么以失败告终。
上述算法有两个明显的改进：首先，如果选择点形成\(S\)的基本原理存在问题，请使用确定性选择过程而不是随机选择过程；其次，一旦找到合适的共识集\(S^*\)并实例化模型\(M^*\)，将\(P\)中与\(M^*\)一致的任何新点添加到\(S^*\)并基于这个更大的集合计算新模型。
A. 建立基准/模型兼容性的容错
基准与模型的偏差是与基准相关的误差和与模型相关的误差的函数（其部分是与用于实例化模型的数据相关的误差的函数）。如果模型是数据点的简单函数，则可以通过分析建立合理的容错界限。然而，这种直截了当的方法通常是行不通的。对于这种情况，通常可以通过实验估计容错范围。样本偏差可以通过扰动数据、计算模型和测量隐含误差来产生。然后可以将误差容限设置为超出测量的平均误差一或两个标准偏差。
基准与假设模型的预期偏差通常是基准的函数，因此每个基准的误差容限应该不同。然而，与粗差的大小相比，误差容限的变化通常相对较小。因此，所有数据的单一错误容限通常就足够了。
B. 寻找共识集的最大尝试次数
假设某一次采样的最小子集中所有数据都是内点的概率为\(b\)，那么在第\(k\)次第一次出现所有点都是内点的概率情况如下：
| \(k\) | 1 | 2 | 3 | 4 | \(\cdots\) | \(k\) | \(\cdots\) |
|---|---|---|---|---|---|---|---|
| \(P\) | \(p\) | \((1-p)p\) | \((1-p)^2p\) | \((1-p)^3p\) | \(\cdots\) | \((1-p)^{k-1}p\) | \(\cdots\) |
停止选择\(P\)的新子集的决定可以基于选择\(n\)个好的数据点的子集所需的预期试验次数\(k\)。令\(w\)为任何选定数据点在模型容错范围内的概率。然后我们有：
\[ \begin{align} E(k)=&b+2*(1-b)*b+3*(1-b)^2*b+\\ &\cdots+i*(1-b)^{i-1}*b+\cdots, \\ E(k)=&b*[1+2*a+3*a^2+\cdots+i*a^{i-1}+\cdots], \end{align} \]
其中\(E(k)\)为\(k,b=w^n\)的期望值，同时\(a=(1-b)\)
几何级数和的恒等式是：
\[ a/(1-a)=a+a^2+a^3+\cdots+a^i+\cdots \]
将上述恒等式关于\(a\)进行微分，我们有：
\[ 1/(1-a)^2=1+2*a+3*a^2+\cdots+i*a^{i-1}+\cdots \]
因此
\[ E(k)=1/b=w^{-n} \]
以下是对应于\(n\)和\(w\)值的\(E(k)\)的一些值的列表：
| w | n=1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 0.9 | 1.1 | 1.2 | 1.4 | 1.5 | 1.7 | 1.9 |
| 0.8 | 1.3 | 1.6 | 2.0 | 2.4 | 3.0 | 3.8 |
| 0.7 | 1.4 | 2.0 | 2.9 | 4.2 | 5.9 | 8.5 |
| 0.6 | 1.7 | 2.8 | 4.6 | 7.7 | 13 | 21 |
| 0.5 | 2.0 | 4.0 | 8.0 | 16 | 32 | 64 |
| 0.4 | 2.5 | 6.3 | 16 | 39 | 98 | 244 |
| 0.3 | 3.3 | 11 | 37 | 123 | 412 | —— |
| 0.2 | 5.0 | 25 | 125 | 625 | —— | —— |
一般来说，在我们放弃之前，我们可能希望超过\(E(k)\) 次试验一到两个标准差。 请注意，\(k\)的标准偏差\(SD(k)\)由下式给出：
\[ SD(k)=sqrt[E(k^2)-E(k)^2] \]
\[ \begin{align} E(k^2)&=\sum_{i=0}^{\infty}(b*i^2*a^{i-1})\\ &=\sum_{i=0}^{\infty}(b*i*(i-1)*a^{i-1}) + \sum_{i=0}^{\infty}(b*i*a^{i-1})\\ \end{align} \]
但是（使用几何级数恒等式和两个差分）：
\[ 2a/(1-a)^3=\sum_{i=0}^{\infty}(i*(i-1)*a^{i-1}) \]
因此
\[ E(k^2)=(2-b)/(b^2) \]
同时
\[ SD(k)=[sqrt(1-w^n)]*(1/w^2) \]
请注意，通常\(SD(k)\)将大约等于\(E(k)\)，因此，例如，如果\((w = 0.5)\)和\((n = 4)\)，则\(E(k) = 16\)和\(SD(k) = 15.5\)。这意味着一个人可能想要尝试两倍或三倍于\(k\)所暗示的预期随机选择数量（如上表所示）以获得超过\(t\)个成员的共识集。
从稍微不同的角度来看，如果我们想以概率\(z\)确保我们的随机选择中至少有一个是\(n\)个数据点的无错误集合，那么我们必须期望至少做出\(k\)个选择（每次选择\(n\)个点数据），其中
\[ (1-b)^k=(1-z) \]
\[ k=[\log(1-z)]/[\log(1-b)] \]
要求采样次数中至少有一次采样全部都是内点概率\(\eta\)推导方法：
\[ p(1+(1+p)+(1-p)^2+\cdots+(1-p)^{k-1})>\eta \]
\[ 1-(1-p)^k>\eta \]
\[ k>\frac{\log(1-\eta)}{\log(1-p)} \]
例如，如果\((w = 0.5)\)和\((n = 4)\)，则\((b = 1/16)\)。为了获得90%的保证至少做出一次无误的选择
\[ k=\log(0.1)/\log(15/16)=35.7 \]
注意，如果\(w^n\ll 1\)，那么\(k\approx\log(1-z)E(k)\)。因此如果\(z=0.90\)同时\(w^n\ll 1\)，那么\(k\approx 2.3E(k)\)；如果\(z=0.95\)同时\(w^n\ll 1\)，那么\(k\approx 3.0E(k)\)
C. 可接受共识集大小的下限
阈值\(t\)是 RANSAC 范式的正式声明中的一个未指定参数，它被用作确定\(P\)的\(n\)个子集已被发现的基础，这意味着足够大的共识集以允许算法终止。 因此，必须选择足够大的\(t\)以满足两个目的：为数据找到正确的模型，以及找到足够数量的相互一致的点来满足最终平滑过程的需要（计算改进的估计值用于模型参数）。
为了确保最终共识集与不正确模型兼容的可能性，并假设\(y\)是任何给定数据点在不正确模型的容错范围内的概率，我们希望\(y^{t- n}\)非常小。虽然没有精确确定\(y\)的通用方法，但假设它小于\(w\)肯定是合理的（\(w\)是给定数据点在正确模型的容错范围内的先验概率）。假设 \(y < 0.5\)，\(t-n\) 的值等于5将提供高于95%的概率，即不会发生与不正确模型的兼容性。
为了满足最终平滑程序的需要，必须指定要采用的特定程序。 如果要使用最小二乘平滑，在许多情况下可以调用形式方法来确定产生所需精度所需的点数。
D. 例子
LDP问题
图像分析中的一个基本问题是在给定场景的两个表示的元素之间建立对应关系。通过图像和相机内参计算图像里面实体的大小和位置信息。
LDP正式的定义：
给定一组\(m\)个控制点，其3维坐标在某个坐标系中已知，并且给定一个图像，其中\(m\)个控制点的某个子集是可见的，确定位置（相对于控制点的坐标系） 从中获得图像。
我们首先假设我们知道\(n\)个图像点和控制点之间的对应关系；稍后我们考虑其中一些对应无效的情况。我们还将假设成像系统的像平面中的主点（相机的光轴穿过像平面的位置）和焦距（从透视中心到像平面中的主点的距离）已知；因此（参见图 2）我们可以轻松地计算从透视中心 (CP) 到任何一对控制点的角度。最后，我们假设相机位于包围控制点的凸包的外部和上方。
我们稍后将演示（附录 A），如果我们可以计算从CP到三个控制点的光线长度，那么我们可以直接求解CP的位置（如果需要，还可以求解像平面的方向）。因此，一个等价的但在数学上更简洁的LDP陈述是：
给定n个控制点的相对空间位置，并给定从称为透视中心 (CP) 的附加点到每对控制点的角度，找出将 CP 连接到每个控制点的线段（“腿”）的长度 的控制点。我们称之为“透视H点”问题 (PnP)。
为了应用RANSAC范式，我们希望确定可以解决PnP问题的\(n\)的最小值。
A. PnP问题的解决方案
PnP（Perspective-n-Point）
P1P问题 (n = 1) 不提供约束信息，因此可能有无限的解决方案。 图 3 所示的 P2P 问题 (n = 2) 也有无限的解决方案； CP 可以位于直径为\(Rab/sin(\theta ab)\)的圆上的任何位置，围绕连接两个控制点A和B的弦（线）在空间中旋转。
\[ \sin \theta ab=\frac{Rab/2}{D/2} \]
\[ D=\frac{Rab}{\sin\theta ab} \]
P3P问题\((n = 3)\)要求我们在给定基本尺寸和相对三面角的面角的情况下确定四面体的三个腿的长度（见图 4）。这个问题的解由三个方程 [\(A^*\)] 给出：
\[ \begin{align} (Rab)^2=a^2+b^2-2*a*b[\cos(\theta ab)]\\ (Rac)^2=a^2+c^2-2*a*c[\cos(\theta ac)]\\ (Rbc)^2=b^2+c^2-2*b*c[\cos(\theta bc)] \end{align} \]
众所周知，在\(n\)个未知数中，\(n\)个独立多项式方程的解不能多于它们各自度数的乘积 [2]。 因此，系统 A* 最多可以有八个解。然而，因为系统\(A^*\)中的每一项要么是常数，要么是二阶的，所以对于每个实正解，都有一个几何同构的负解。 因此，\(A^\*\)最多有四个正解，在图5中，我们展示了一个示例，证明了四个解的上限是可以达到的。