本文最后更新于：14 天前
特征匹配
【基本问题】
特征点匹配
暴力搜索与2NN判据
设两帧图像中的对应特征点集${𝑥𝑖,𝑦_𝑖}$和${𝑥_𝑖^′,𝑦_𝑖^′}$，共N个特征点 对应点 $𝐱_𝒋=(𝑥_𝑗,𝑦_𝑗)$，匹配点为距离最小点 $𝐱_𝑗^′=𝑥_𝑗^′∗,𝑦_𝑗^′∗=𝑚𝑖𝑛{𝑘=1}^𝑁||x_𝑗−𝑥_𝑘^′||$ ，对应距离$𝑑_𝑗^∗$ 进一步得到次小点𝐱′′，对应距离$𝑑_𝑗^{∗′}$, 则匹配点满足：$𝑑_𝑗^∗<𝛼∗𝑑_𝑗^{∗′}$, 认为正常匹配.
【特征点匹配方法】
快速搜索方式—-二叉树
- 算法复杂度o(N2)。特征点数量多时，匹配效率低。
- 二叉搜索树(BST)提供了高效搜索方式
- 以下是一颗一维的二叉搜索树，尝试搜索和11最近的点。
K-D树
对于每一层，可以指定一个划分维度（轴垂直分区面axis-aligned splitting planes）。最简单的就是按照关键字轮流划分（例如：奇数层按照x轴划分，也即第一个关键字；偶数层按照y轴划分，也即第二个关键字）。
K-D树的建立方式
对于所有的样本点，统计它们在每个维上的方差，挑选出方差中的最大值，对应的维就是分裂域的值。数据方差最大表明沿该维度数据点分散得比较开，这个方向上进行数据分割可以获得最好的分辨率；然后再将所有样本点按其第该维的值迕行排序，位于正中间的那个数据点选为分裂结点对应域。重复上述过程直至获得所有叶子节点显示了构建返棵二叉树的所有步骤。
下面以一个简单的例子来解释上述k-d tree的构建过程。
假设样本集为：{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}。
K-D树最近邻查询算法
- 首先通过将查找点数据根结点数据对应维 上的值相比较，按照二叉搜索的方式，顺着“搜索路径”找到最近邻的近似点，也就是 与查询点处于同一个子空间的叶子节点；
- 为了防止漏查与查找点 跟进的距离的点，回溯搜索路径，并且判断搜索路径上节点的其他子节点空 间中是否还有距离查询点更近的数据点，如果有，则需要跳到其他子节点空间中去搜索。
- 重复返个过程直到搜索路径为空。
BBF(Best Bin First)
BBF的查询思路就是将“查询路径”上的节点进行排序，如按各自分割超平面（称为Bin）与查询点的距离排序,优先考虑距离小的点。BBF还设置了一个运行超时限制，当优先级队列中的所有节点都经过检查或者超出时间限制时，算法返回当前找到的最好结果作为近似的最近邻。
随机化K-D森林
同时独立建立多个k-d树，每棵树在具有大方差的各维中(如top-5)随机选择。查询时，并行查询多个k-d树，按照BBF准侧将候选节点放在同一队列中。
【RANSAC】
稳健(robust): 对数据噪声的敏感性
基本思想
RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证：
- 有一个模型适应于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。
- 用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。
- 如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。
- 然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。
- 最后，通过估计局内点与模型的错误率来评估模型。
这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为比现有的模型更好而被选用
SIFT和RANSAC结合
RANSAC算法在SIFT特征筛选中的主要流程：
- 从样本集中随机抽选一个RANSAC样本，即4个匹配点对
- 根据返4个匹配点对计算变换矩阵M
- 根据样本集，变换矩阵M，和误差度量函数计算满足当前变换矩阵的一致集consensus，并返回一致集中元素个数
- 根据当前一致集中元素个数判断是否最优(最大)一致集，若是则更新当前最优一致集
- 更新当前错误概率p，若p大于允许的最小错误概率则重复(1)至(4)继续迭代，直到当前错误概率p小于最小错误概率
结果比较：2NN vs 2NN+RANSAC
【总结】
- 特征匹配是立体视觉、全景视觉、由运动到结构的重要环节
- 使用基于k-d树的特征匹配方法，能有效提高搜索效率
- RANSAC是一类随机稳健估计方法，可有效滤除误配点
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0协议 。转载请注明出处！