征匹配中的几何约束#上一篇我们梳理了 SIFT 的多种变体与改进方向现在再回到拼接管线本身之前我们利用 SIFT 完成了特征匹配拿到了初步的匹配点对但即使经过比率测试结果中仍然存在误匹配。原因是比率测试只关心描述子空间的数值接近性不关心两张图像之间的几何一致性。比如一对双胞胎站在一起我们凑近为其中一人拍了一张单人照然后又拉远镜头拍了一张合照那么这两幅图像间的特征就很容易匹配到另外一个人上。换句话说比率测试只能回答“这两个局部纹理看起来很相似。”但无法回答“这两个点在真实三维空间中是否对应同一个位置”这就引出了拼接管线中的下一步几何验证其核心思路是利用匹配点对之间的几何约束关系识别并剔除那些看起来像但实际位置不对应的误匹配。在图像拼接场景中若场景近似平面这个几何约束通常是单应性矩阵。而求解单应性矩阵并同时剔除误匹配的最化改进。不过与 SIFT 不同RANSAC 的职责十分明确它并不负责提取或匹配特征而只是在已有匹配点的基础上完成几何验证。因此它的发展并没有形成像 SIFT 那样庞杂的谱系而是不断结合新技术实现一个目标如何更高效准确地从包含误匹配的数据中估计正确的几何模型。具体内容之后会再详细展开。2. 单应性矩阵#RANSAC 的前置内容是单应性矩阵Homography虽然是矩阵形式但其实使用函数来概括说明可以更好地理解它的作用描述同一场景的特征点在两幅图像中对应关系的函数变换矩阵输入特征点坐标输出在另一角度图像中的对应坐标。大致明确其作用后再来展开原理2.1 什么是单应性#理论证明两个视角拍摄同一平面其对应关系可以由一个单应性矩阵描述。因此单应性描述的是同一平面场景在两幅图像之间的投影变换关系。展开来假设场景中存在一个平面比如农田、墙面、地面等相机从两个不同角度拍摄那么两幅图像之间的对应点满足[′′1]∝[1]其中 就是 3×3 的单应性矩阵[ℎ11ℎ12ℎ13ℎ21ℎ22ℎ23ℎ31ℎ32ℎ33]这里有一个细节单应性矩阵是齐次坐标下的变换基础线代这意味着 乘以任意非零常数后表示的是同一个变换。因此 的自由度实际上只有8最后一个元素通常固定为 1即 ℎ331。全是参数看起来十分复杂但其实这类变换并不突兀摆几个例子变换类型矩阵形式自由度效果平移[1001001]2横向/纵向移动旋转[cos−sin0sincos0001]1绕原点旋转缩放[0000001]2放大缩小仿射[111213212223001]6平行四边形变换透视全 8 参数8任意四边形变换可以看到平移、旋转、缩放、仿射变换都可以表示为单应性矩阵的特殊形式这也是为什么单应性矩阵能够描述相机旋转、平移、视角变化等复杂场景下的图像关系。而结合到这个系列来说在无人机航拍拼接中由于地面近似平面且无人机通常在同一高度飞行单应性矩阵可以很好地描述相邻航带图像之间的几何关系。现在把矩阵运算展开成公式从 (,) 到 (′,′) 的实际映射关系是这样的′ℎ11ℎ12ℎ13ℎ31ℎ321′ℎ21ℎ22ℎ23ℎ31ℎ321显然问题在于求解参数。2.2 如何求解单应性矩阵#这部分其实就是矩阵形式的解方程一对匹配点 (,) 和 (′,′) 提供了两个方程。将上面的映射关系改写为线性形式′(ℎ31ℎ321)ℎ11ℎ12ℎ13′(ℎ31ℎ321)ℎ21ℎ22ℎ23再写成矩阵形式可以发现每对点贡献 2×9 的行[1000−′−′−′0001−′−′−′][ℎ11ℎ12ℎ13ℎ21ℎ22ℎ23ℎ31ℎ32ℎ33][00]这代表每对匹配点可以提供 2 个约束 有 8 个自由度理论上只需要 4 对不共线的匹配点即可求解整个单应性矩阵。这种求解方法叫直接线性变换Direct Linear TransformDLT把原本非线性的几何关系通过齐次坐标改写成关于未知参数的线性方程组然后利用线性代数求解。前置内容就到这里现在问题来了我们经过比率测试后有几十甚至上百对匹配点其中还混有误匹配。用哪些点来解单应性矩阵这正是 RANSAC 要解决的问题。3. RANSAC 算法#RANSAC 的核心思想很朴素流程也较为简单但却十分有效与其试图一次性用所有数据拟合模型容易被少量错误数据严重带偏不如反复随机采样最小子集来拟合模型然后看每个模型能获得多少其他数据的支持最终选择支持度最高的那个模型。3.1 算法流程#RANSAC 的完整步骤如下随机采样从当前的匹配点集中随机选取 4 对匹配点进行退化检查重复点共线近似共线等直至取点合理使用最小集是为了满足求解条件的同时尽可能防止被误匹配点污染模型。拟合模型用第一步得到的 4 对匹配点通过 DLT 求解单应性矩阵 。内点判定用 将所有匹配点中图像 A 的特征点映射到图像 B 的坐标系中计算映射点与实际匹配点之间的重投影误差判定内外点并记录。这里的重投影误差其实就是映射坐标和真实坐标间的距离之所以称为重投影是因为单应性矩阵根据图像 A 的点重新预测了其在图像 B 中的位置相当于再次投影到图像 B 上因此称为重投影误差(′−^′)2(′−^′)2其中 (′,′) 是第 对匹配点在图像 B 中的原始坐标(^′,^′) 是 映射后的坐标。而内外点的定义是这样的我们根据对精度的要求设置距离阈值 通常取 3∼5 像素。如果 则判定该匹配为内点inlier否则为外点outlier。最后记录这次采样的内点数量进入下一步重复迭代重复步骤 1~3 共 次。 次迭代结束后选取内点数量最多的那次结果对应的 作为最优模型。最终优化对最优模型得到的所有内点在 基础上使用最小二乘法迭代优化总的重投影误差重新估计单应性矩阵得到更精确的 利用更多样本降低随机误差。RANSAC 的过程其实类似抽签经过足够多次的随机抽样抽到一组全内点的最小集从而定位到正确的模型。3.2 迭代次数与置信度#一个涉及实现的问题是需要迭代多少次才能保证找到较准确的模型而这和数据本身相关不能去盲目寻找“官方配置”一个重要因素是数据中外点的比例也就是 SIFT 本身得到的匹配质量。我们可以进行如下推导假设外点比例为 则一次采样中 4 个点全部为内点的概率为(1−)4如果我们希望以概率 至少找到一组全是内点的采样则需要进行 次迭代1−(1−(1−)4)整理得到log(1−)log(1−(1−)4)代几个值看看外点比例 单次采样全内点概率0.990.99910%65.6%4630%24.0%172550%6.25%7210760%2.56%17926870%0.81%56785080%0.16%2876431390%0.01%4599668995可以看到两个结论外点比例在 50% 以内时RANSAC 是高效的几十到一百多次迭代就能以 99% 的置信度找到较准确内点组合。一旦外点比例超过 70%所需的迭代次数会急剧上升。到 90% 时已经需要近 5 万次迭代。这说明提高初始匹配质量十分重要。比例测试能够有效降低外点比例从而显著减少 RANSAC 所需迭代次数因此二者具有很强的互补性。
高光谱拼接算法（六）RANSAC 误匹配剔除
征匹配中的几何约束#上一篇我们梳理了 SIFT 的多种变体与改进方向现在再回到拼接管线本身之前我们利用 SIFT 完成了特征匹配拿到了初步的匹配点对但即使经过比率测试结果中仍然存在误匹配。原因是比率测试只关心描述子空间的数值接近性不关心两张图像之间的几何一致性。比如一对双胞胎站在一起我们凑近为其中一人拍了一张单人照然后又拉远镜头拍了一张合照那么这两幅图像间的特征就很容易匹配到另外一个人上。换句话说比率测试只能回答“这两个局部纹理看起来很相似。”但无法回答“这两个点在真实三维空间中是否对应同一个位置”这就引出了拼接管线中的下一步几何验证其核心思路是利用匹配点对之间的几何约束关系识别并剔除那些看起来像但实际位置不对应的误匹配。在图像拼接场景中若场景近似平面这个几何约束通常是单应性矩阵。而求解单应性矩阵并同时剔除误匹配的最化改进。不过与 SIFT 不同RANSAC 的职责十分明确它并不负责提取或匹配特征而只是在已有匹配点的基础上完成几何验证。因此它的发展并没有形成像 SIFT 那样庞杂的谱系而是不断结合新技术实现一个目标如何更高效准确地从包含误匹配的数据中估计正确的几何模型。具体内容之后会再详细展开。2. 单应性矩阵#RANSAC 的前置内容是单应性矩阵Homography虽然是矩阵形式但其实使用函数来概括说明可以更好地理解它的作用描述同一场景的特征点在两幅图像中对应关系的函数变换矩阵输入特征点坐标输出在另一角度图像中的对应坐标。大致明确其作用后再来展开原理2.1 什么是单应性#理论证明两个视角拍摄同一平面其对应关系可以由一个单应性矩阵描述。因此单应性描述的是同一平面场景在两幅图像之间的投影变换关系。展开来假设场景中存在一个平面比如农田、墙面、地面等相机从两个不同角度拍摄那么两幅图像之间的对应点满足[′′1]∝[1]其中 就是 3×3 的单应性矩阵[ℎ11ℎ12ℎ13ℎ21ℎ22ℎ23ℎ31ℎ32ℎ33]这里有一个细节单应性矩阵是齐次坐标下的变换基础线代这意味着 乘以任意非零常数后表示的是同一个变换。因此 的自由度实际上只有8最后一个元素通常固定为 1即 ℎ331。全是参数看起来十分复杂但其实这类变换并不突兀摆几个例子变换类型矩阵形式自由度效果平移[1001001]2横向/纵向移动旋转[cos−sin0sincos0001]1绕原点旋转缩放[0000001]2放大缩小仿射[111213212223001]6平行四边形变换透视全 8 参数8任意四边形变换可以看到平移、旋转、缩放、仿射变换都可以表示为单应性矩阵的特殊形式这也是为什么单应性矩阵能够描述相机旋转、平移、视角变化等复杂场景下的图像关系。而结合到这个系列来说在无人机航拍拼接中由于地面近似平面且无人机通常在同一高度飞行单应性矩阵可以很好地描述相邻航带图像之间的几何关系。现在把矩阵运算展开成公式从 (,) 到 (′,′) 的实际映射关系是这样的′ℎ11ℎ12ℎ13ℎ31ℎ321′ℎ21ℎ22ℎ23ℎ31ℎ321显然问题在于求解参数。2.2 如何求解单应性矩阵#这部分其实就是矩阵形式的解方程一对匹配点 (,) 和 (′,′) 提供了两个方程。将上面的映射关系改写为线性形式′(ℎ31ℎ321)ℎ11ℎ12ℎ13′(ℎ31ℎ321)ℎ21ℎ22ℎ23再写成矩阵形式可以发现每对点贡献 2×9 的行[1000−′−′−′0001−′−′−′][ℎ11ℎ12ℎ13ℎ21ℎ22ℎ23ℎ31ℎ32ℎ33][00]这代表每对匹配点可以提供 2 个约束 有 8 个自由度理论上只需要 4 对不共线的匹配点即可求解整个单应性矩阵。这种求解方法叫直接线性变换Direct Linear TransformDLT把原本非线性的几何关系通过齐次坐标改写成关于未知参数的线性方程组然后利用线性代数求解。前置内容就到这里现在问题来了我们经过比率测试后有几十甚至上百对匹配点其中还混有误匹配。用哪些点来解单应性矩阵这正是 RANSAC 要解决的问题。3. RANSAC 算法#RANSAC 的核心思想很朴素流程也较为简单但却十分有效与其试图一次性用所有数据拟合模型容易被少量错误数据严重带偏不如反复随机采样最小子集来拟合模型然后看每个模型能获得多少其他数据的支持最终选择支持度最高的那个模型。3.1 算法流程#RANSAC 的完整步骤如下随机采样从当前的匹配点集中随机选取 4 对匹配点进行退化检查重复点共线近似共线等直至取点合理使用最小集是为了满足求解条件的同时尽可能防止被误匹配点污染模型。拟合模型用第一步得到的 4 对匹配点通过 DLT 求解单应性矩阵 。内点判定用 将所有匹配点中图像 A 的特征点映射到图像 B 的坐标系中计算映射点与实际匹配点之间的重投影误差判定内外点并记录。这里的重投影误差其实就是映射坐标和真实坐标间的距离之所以称为重投影是因为单应性矩阵根据图像 A 的点重新预测了其在图像 B 中的位置相当于再次投影到图像 B 上因此称为重投影误差(′−^′)2(′−^′)2其中 (′,′) 是第 对匹配点在图像 B 中的原始坐标(^′,^′) 是 映射后的坐标。而内外点的定义是这样的我们根据对精度的要求设置距离阈值 通常取 3∼5 像素。如果 则判定该匹配为内点inlier否则为外点outlier。最后记录这次采样的内点数量进入下一步重复迭代重复步骤 1~3 共 次。 次迭代结束后选取内点数量最多的那次结果对应的 作为最优模型。最终优化对最优模型得到的所有内点在 基础上使用最小二乘法迭代优化总的重投影误差重新估计单应性矩阵得到更精确的 利用更多样本降低随机误差。RANSAC 的过程其实类似抽签经过足够多次的随机抽样抽到一组全内点的最小集从而定位到正确的模型。3.2 迭代次数与置信度#一个涉及实现的问题是需要迭代多少次才能保证找到较准确的模型而这和数据本身相关不能去盲目寻找“官方配置”一个重要因素是数据中外点的比例也就是 SIFT 本身得到的匹配质量。我们可以进行如下推导假设外点比例为 则一次采样中 4 个点全部为内点的概率为(1−)4如果我们希望以概率 至少找到一组全是内点的采样则需要进行 次迭代1−(1−(1−)4)整理得到log(1−)log(1−(1−)4)代几个值看看外点比例 单次采样全内点概率0.990.99910%65.6%4630%24.0%172550%6.25%7210760%2.56%17926870%0.81%56785080%0.16%2876431390%0.01%4599668995可以看到两个结论外点比例在 50% 以内时RANSAC 是高效的几十到一百多次迭代就能以 99% 的置信度找到较准确内点组合。一旦外点比例超过 70%所需的迭代次数会急剧上升。到 90% 时已经需要近 5 万次迭代。这说明提高初始匹配质量十分重要。比例测试能够有效降低外点比例从而显著减少 RANSAC 所需迭代次数因此二者具有很强的互补性。
