RexKing6's Note

Geometric Verification几何验证

发表于 更新于 分类于 ， 阅读次数：
4k 4 分钟

简介

几何验证，用于图像检索。

综合转载以下文章：

RANdom SAmple Consensus (RANSAC)

RANSAC是“RANdom SAmple Consensus（随机抽样一致）”的缩写。它可以从一组包含“局外点”的观测数据集中，通过迭代方式估计数学模型的参数。它是一种不确定的算法——它有一定的概率得出一个合理的结果；为了提高概率必须提高迭代次数。该算法最早由Fischler和Bolles于1981年提出。

RANSAC的基本假设是：

  1. 数据由“局内点”组成，例如：数据的分布可以用一些模型参数来解释；
  2. “局外点”是不能适应该模型的数据；
  3. 除此之外的数据属于噪声。

局外点产生的原因有：噪声的极值；错误的测量方法；对数据的错误假设。

RANSAC也做了以下假设：给定一组（通常很小的）局内点，存在一个可以估计模型参数的过程；而该模型能够解释或者适用于局内点。

示例

一个简单的例子是从一组观测数据中找出合适的2维直线。假设观测数据中包含局内点和局外点，其中局内点近似的被直线所通过，而局外点远离于直线。简单的最小二乘法不能找到适应于局内点的直线，原因是最小二乘法尽量去适应包括局外点在内的所有点。相反，RANSAC能得出一个仅仅用局内点计算出模型，并且概率还足够高。但是，RANSAC并不能保证结果一定正确，为了保证算法有足够高的合理概率，我们必须小心的选择算法的参数。


图：包含很多局外点的数据集


图：RANSAC找到的直线（局外点并不影响结果）

概述

RANSAC算法的输入是一组观测数据，一个可以解释或者适应于观测数据的参数化模型，一些可信的参数。

RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证：

  1. 有一个模型适应于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。
  2. 用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。
  3. 如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。
  4. 然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。
  5. 最后，通过估计局内点与模型的错误率来评估模型。

这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为比现有的模型更好而被选用。

以直线为例

  1. 从数据中采集最小子集（最小子集的大小由所研究的问题决定，如拟合直线，则最小子集数目为2，因为两点确定一条直线），然后用这个最小子集拟合一条直线$l_i$（得到 $\tilde{H}$）；
  2. 计算每个点到直线$l_{1}$的距离 $d_{\bot}$ （在拟合直线的情况下，我采用的是点 $x_{i}$ 通过$\tilde{H}$ 得到的 $\tilde{y_{i}}=\tilde{H}x_{i}$ 与真值的差的绝对值 $|y_{i}-\tilde{y_{i}}|$ ），如果 $d_{\bot}T$ ， $T$ 是内点数目阈值，则说明当前所估计的 $\tilde{H}$ 足够好，利用这些内点再重新估计$\tilde{H}$ ，然后返回 $\tilde{H}$ ，退出。否则返回 1. 继续执行。
  3. 不停地重复上面两步，直到估计的 $\tilde{H}$ 可以得到最大的内点数，然后利用这些内点再重新估计$\tilde{H}$ 即可。但有一个问题还没有解决，那就是我们究竟需要重复上面步骤多少次？即采集多少次子集？一种最直观的想法就是遍历数据中的所有点，这固然是一个容易想到的方法，但是，如果数据集非常大，则这种方法就是非常费时间的了，效率会变低。为了解决这个问题，给出了这样的一个公式，用来决定需要采样次数 $N$：其中，$S$子集的大小，$p$表示由$S$个点组成的随机样本中至少有一次没有外点的概率，通常取 $p=0.99$ ， $t$ 表示数据集中出现内点的概率（我们可以用数据集中内点所占数据集的比例来近似）。有了这个公式我们就可以估计出我们需要采样多少次了。

参数推导

假设内点在整个数据集中的概率为$t$，即：

确定该问题的模型需要$n$个点，这个$n$是根据问题而定义的，例如拟合直线时$n$为2，平面拟合时$n=3$，求解点云之间的刚性变换矩阵时$n=3$，求解图像之间的射影变换矩阵是$n=4$，等等。$k$表示迭代次数，即随机选取$n$个点计算模型的次数。$P$为在这些参数下得到正确解的概率。为方便表示，我们可以得到，$n$个点都是内点的概率为$t^n$，则$n$个点中至少有一个是外点的概率为

$(1-t^n)^k$表示$k$次随机抽样中都没有找到一次全是内点的情况，这个时候得到的是错误解，也就是：

内点概率$t$是一个先验值，可以给出一些鲁棒的值。同时也可以看出，即使t给的过于乐观，也可以通过增加迭代次数$k$，来保证正确解的概率$P$。同样的，我们可以通过上面式子计算出来迭代次数k，即我们假设需要正确概率为$P$（例如我们需要99%的概率取到正确解），则对两边求对数，解$k$，

自适应决定采样次数版本

  • $N=\infty$ （或者取100000，总之很大就行），sample_count = 0
  • 当sample_count< $N$
  1. 选取一个样本，估计 $\tilde{H}$，并计算内点数。若内点数大于阈值，则利用这些内点重新估计 $\tilde{H}$，然后返回 $\tilde{H}$，终止。
  2. 令 $t =$ （内点数）/（总点数）
  3. 取 $p=0.99$ ，由 $N=log(1-p)/log(1-t^S)$ ，求出$N$
  4. sample_count++

用得到的最多的内点，重新估计 $\tilde{H}$，然后返回，终止。

优缺点

RANSAC的优点是它能鲁棒的估计模型参数。例如，它能从包含大量局外点的数据集中估计出高精度的参数。RANSAC的缺点是它计算参数的迭代次数没有上限；如果设置迭代次数的上限，得到的结果可能不是最优的结果，甚至可能得到错误的结果。RANSAC只有一定的概率得到可信的模型，概率与迭代次数成正比。RANSAC的另一个缺点是它要求设置跟问题相关的阀值。

RANSAC只能从特定的数据集中估计出一个模型，如果存在两个（或多个）模型，RANSAC不能找到别的模型。

Weak geometric constraint (WGC)

由于RANSAC计算成本较高，提出了弱几何约束(WGC)作为一种有效的求解方法，没有重建整个线性变换模型。$s_i$和$θ_i$是一张图像的描述子$x\in X$的尺度和主方向。$s_j$和$θ_j$是另一张图像的描述子$y\in Y$的尺度和主方向。由以下变量生成直方图，$iff \space q(x) = q(y)$

当一张图像经历一些旋转或者尺度变化后，这些特征就会相应地发生一致性的变化。弱几何一致方法正好利用了这种一致的变化来重排。一个视觉单词匹配为每个bin中的一个假设投票。一个bin收集的票数越多，其假设置信度就越高。 一个直方图中的峰值区间表示两个图像之间最可能的转换。 换句话说，峰值区的情况最有可能是正确的。 将两个直方图的最高置信度分数考虑在内，下面等式给出了两个BoVW之间正确匹配数的保守估计

其中，$H(\Delta s)$和$H(\Delta \theta)$分别为$\Delta s$和$\Delta \theta$的直方图。之后将WGC分数作为相似度的乘法因子进行重排。

Reciprocal geometry verification (RGC)

利用匹配特征的X-Y位置信息，还有另一种估计变换参数的风法，缩放和旋转。 给定来自特征集$X$和$Y$的两个匹配的特征点$x$和$y$，它们之间的缩放$\hat s$和旋转角$\hat θ$可以通过参考另外一对匹配特征，来自$Q$的$x’$和来自$R$的$y’$来近似，其中

请注意，$\hat s$和$\hat θ$可能与通过特征检测估计的值$\Delta θ$和$\Delta s$不同。 但是，通常它们的值越接近，$x$和$y$之间的匹配正确的可能性就越大。 因此，我们将它们之间的差异定义为$\Delta = max\{|\hat θ -\Delta θ|,|\hat s-\Delta s|\}$。 基本上，值越小，特征$x$和$y$之间匹配的置信度越高。 根据此差异分数，重新排名定义为

其中$α$是阈值。 对于任何$\Delta \ge α$的值，该匹配将直接从相似性度量中移除，使得等式将永远产生正值。返回时，通过基于汉明距离和匹配置信度对匹配词汇的重要性进行加权来修改两个图像之间的相似性。

其中$U$和$V$是特征集$X$和$Y$的BoVW。这种方法称为交互几何验证（RGV）。 与WGC相比，RGV显示出更好的滤除错误匹配的能力，同时需要额外的内存来保X-Y信息。

相关文章
一分一毛，也是心意。