【原】多视角几何3-2D射影变换估计-鲁棒性估计

目前为止，始终假设存在对应点关系集合{x_i<->x'_i}，并且唯一的误差是服从高斯分布的点位置的测量。但实际情况中，这种假设并不成立，因为对应点可能误匹配。这种误匹配是高斯误差分布的离群值。这种离群值会严重影响单应估计值，因此应当确认离群值。显然目标是，根据已得到的对应关系确定离群值集合，以保证根据前文所述算法通过合群值计算单应最优估计值，这就是鲁棒性估计，因为估计可以排除离群值(测量值服从一个不同并且可能无法建模的误差分布)的影响。

4.7.1 RANSAC

我们从一个简单例子开始，该例子易于可视化--估计一条直线以拟合2维点集。该例子也可视作估计两条直线上对应点间一维仿射变换，x'=ax+b。

该问题如图所示，给定2D数据点集，寻找直线以最小化所有点到直线距离的平方和最小化，同时满足所有有效点偏离该直线不超过t个单位。

这实际是两个问题：直线拟合数据；合群值和离群值的分类。尺度界限t应根据测量噪声(如t=3σ)进行设定，会在后文讨论。实际上存在多种鲁棒性算法，但具体采用哪种程度取决于离群值所占比例。例如，如果已知仅有一个离群值，那么可以轮流删除每个点，利用剩余点计算直线估计值。这里，我们会详细介绍通用且有效的鲁棒股计算法-RANSAC(随机抽样一致算法)，该算法能应对离群值比例较大的情况。

思路很简单：随机选择两个点；这些点定义一条直线。该直线的支持证据是一定距离阈值内的点数度量。重复这种随机选择若干次，支持证据最强的直线被认为是鲁棒拟合。在阈值距离内的点是合群值。直觉上，如果某一个点是离群值，那么直线并不会得到最强支持。

对直线打分的另一好处是可以有利于选择更好的拟合。例如图4.7中，直线<a,b>支持点数10，而直线<a,d>只有4。因此，尽管两次计算都不包含离群值，还是选择直线<a,b>。

一般来说，我们希望利用数据拟合模型，本例是直线，随机采样的数据由最小数据组成，本例是两个点，就足以决定模型。如果模型是平面单应，那么对于2D对应点，最小几何需要四对点。单应的RANSAC估计应用会在下面描述。

如Fischler和Bolles所述，RANSAC过程不同于传统平滑计算方法：不同于采用尽可能多的数据获得初始解然后尝试消除无效数据点，RANSAC是使用较小的数据集得到可行解，并在可能时用一致性数据集扩大它。

RANSAC算法参考算法4.4。有三个疑问随之出现：

11111

1.什么是距离阈值？我们需要选择距离阈值t，使点是合群点的概率为α。这种计算要求清楚合群点到模型的距离概率分布。实际中，距离阈值靠经验选择。但是，如果假设测量误差服从高斯分布，零均值均方差σ，那么可以计算t。这种情况下，点的距离的平方，d²_⊥是高斯变量的平方和，它服从χ²_m分布，m是自由度，m等于模型的共轭维度。对于直线，共轭维度是1--只需测量到直线的垂直距离。如果模型是一个点，共轭维度是2，距离的平方是测量误差x和y的平方和。随机变量χ²_m的值小于k²的概率根据累计χ²_m分布

F(k²)=∫^k2₀χ²_m(ζ)dζ确定。根据分布累计，(4.17)

通常α选择设定为0.95，即点是合群点的概率是95%。这表示，合群点被错误排斥的概率是5%。下表列出本书中涉及模型在α=0.95时的t值。

2.采样次数?尝试所有采样通常计算上是不可行也没有必要。当采样次数N足够大，以保证由s个点组成的随机样本中至少有一次没有离群值的概率为p。通常p设定为0.99，假设w是任意选择的点是合群点的概率，因此ε=1-w表示点是离群点的概率。那么至少需要N次选择(每次s个点)，其中(1-w^s)^N=1-p，

所以，(4.18)

表格举例在给定s和ε时并保证至少有一次没有离群值的概率是0.99时所需采样数N；

例4.4.对于图4.7中12个数据点的直线拟合问题，其中有两个点是离群点，所以ε=2/12=1/6。根据表格，当最小数据集大小s=2，至少N=5次采样才能满足要求。如果与每对点均计算的花费相比，需进行66次采样。

注意：

i.采样次数与离群值比例有关而不是数量。这代表，所需采样次数可能比离群数量要小。所以，即使离群值数量非常大时，采样的计算花费也可接受。

ii.对于给定s和ε，采样数量随最小数据集增大而增加。可能会有人认为采用大于最小数据集的数量会更具优势，例如本例直线拟合时采用三个或更多的点，因为这样会获得更好的直线估计，并且测量的支持数更加准确的反应真实的真实数量。但是，增加采样数量会导致计算花费一般远超过测量支持带来的好处。

3.可接受的一致集大小是多少？在给定离群值比例时，如果一致集大小接近于合群值数量时，终结迭代，也就是说对于n个数据，T=(1-ε)n。对于图4.7直线拟合例子，ε的保守估计使ε=0.2，因此T=(1-0.2)12=10。

自适应决定采样次数.通常来说，离群值数据的比例是未知的，在这种情况下，使用最糟糕情况的ε估计值初始化算法，随着更大的一致集被发现而更新估计值。例如，如果最糟糕的情况是ε=0.5，但如果发现合群点的一致集站数据的80%时，那么估计更新为ε=0.2。

反复通过一致集“查询”数据，实现自适应决定采样次数N。为继续上面例子，通过(4.18)，最糟糕的估计ε=0.5决定初始值N。当一致集包含超过50%的数据时，我们知道合群值的比例。更新后估计值ε根据(4.18)得到变小的N。无论何时一致集ε小于当前估计值时，每次采样重复更新减小N。一旦完成N此采样则算法结束。也可能出现，由ε确定的N小于已经执行采样数量，这说明采样数量已足够，算法可结束。自适应决定N的伪码如图。

这种自适应方法非常起作用，实际中也能覆盖采样次数和终结算法的问题。初始ε可以选择1.0，这种情况下初始N是无穷大。所以，在(4.18)使用一个保守的概率p如0.99是非常明智的。

4.7.2鲁棒最大似然估计

RANSAC算法将数据集分成合群数据和离群两部分，也产生了一个模型估计M₀，可根据最小数据集计算获得最多支持的。RANSAC的最后一步是使用所有合群数据重新估计模型。这个重新估计应该是最优的，并涉及最小化最大似然损失函数，如4.3部分所介绍。在直线示例中，最大似然估计等同于正交回归，并存在封闭形式的解。但是，最大似然估计一般涉及迭代最小化，并以最小数据集估计M₀作为初始点。

这一过程中唯一的缺点是，合群和离群数据的分类是不可更改的。当模型最优化满足一致集时，如果把距离阈值应用到该新模型，很可能又有一些点称为合群点。例如，图4.8中根据RANSAC选择的直线<a,b>，有四个支持点，在最优拟合这四个点后，现在有10个点被正确分类为合群点。这两步：最优拟合合群点；使用4.17重新分类合群点；然后不断迭代直到合群点数收敛。根据合群点到模型的距离来加权最小二乘的拟合方法经常在该步骤使用。

鲁棒损失函数.最小化关于合群点的C=∑id²_⊥i的另一鲁棒方法是，最小化包含所有数据。合适的鲁棒损失函数是，(4.19)

这里，d_⊥i是点误差，γ(e)是鲁棒损失函数，其中给离群值赋予固定代价。阈值用χ²确定与(4.17)一致。合群点的平方损失根据高斯分布模型产生。鲁棒损失函数中离群点的常数损失是因为假设离群点服从扩散或均匀分布而产生的，这些分布的对数似然是一个常数。有人可能认为，直接对d_⊥i取阈值，离群点可以从损失函数中剔除。单独使用阈值的问题是，它会造成最后仅留下离群值，因为它们不存在损失。

损失函数D使最小化基于所有点，无论是合群点还是离群点。在迭代最小化的开始，D和C的不同仅在与一个常数(利用离群值数量的四倍)。但是，随着最小化的进行，离群点可能被重新指定为合群点，并且这种情况可能发生在实际中。

4.7.3其他鲁棒算法

在RANSAC中，根据最小集合得到的模型，以数据点在距离阈值中的数量给予分数。另一种方法是通过数据中所有点的距离中位值打分，然后选择中位值最小的模型。这就是最小中位值平方估计LMS，同RANSAC方法一样，最小子集的采样是根据(4.18)得到的采样次数选择的。LMS的优势在于，它对于误差变量不需要设置阈值或者先验。LMS的劣势在于，如果超过一半的数据都是离群，它将失败，因为中位距离是离群值。解决的办法是，使用离群比例决定所选择的距离。例如，如果有超过50%的离群点，那么在中位值以下的距离都应当被使用。

RANSAC和LMS算法都能够处理离群值比例较大的情况。如果离群点数量很小，那么其他鲁棒方法也是足够有效。这包括删短板方法，即每个点轮流被删除并且拟合模型满足剩余数据；迭代加权最小二乘，数据点对拟合的影响需要其残差进行加权。一般来说，这些方法并不推荐。