Graph-Cut RANSAC:一种高效稳健的几何模型估计算法

graph-cut-ransac

Graph-Cut RANSAC简介

Graph-Cut RANSAC(GC-RANSAC)是由Daniel Barath和Jiri Matas在2018年CVPR会议上提出的一种新型鲁棒估计算法。该算法旨在解决计算机视觉中的几何模型估计问题,如基础矩阵、单应性矩阵和本质矩阵的拟合等。

与传统RANSAC相比,GC-RANSAC的主要创新点在于其局部优化(LO)步骤。当找到目前最佳模型时,算法会运行图割算法来分离内点和外点,这种方法在概念上简单,易于实现,且能达到全局最优。

算法优势

根据作者的实验结果,GC-RANSAC在多个问题上都表现出了比现有方法更高的几何精度,包括:

直线拟合
单应性矩阵估计
仿射变换估计
基础矩阵估计
本质矩阵估计

同时,GC-RANSAC能够在许多问题上实现实时运行,其速度与精度较低的替代方法相当(在标准CPU上仅需几毫秒)。

算法实现

GC-RANSAC的官方实现已开源在GitHub上,提供了C++和Python两个版本。主要特性包括:

支持多种几何模型估计:基础矩阵、单应性矩阵、本质矩阵、刚体变换等
集成了多种采样方法:均匀采样、PROSAC、NAPSAC、Progressive NAPSAC等
提供了基于FLANN和网格的邻域图构建方法
实现了SPRT预验证策略以加速收敛
支持多线程并行计算

安装使用

对于C++用户,可以通过CMake构建项目:

git clone https://github.com/danini/graph-cut-ransac
cd build
cmake ..
make

Python用户可以直接通过pip安装预编译的wheel:

pip install pygcransac

示例代码

以下是使用GC-RANSAC进行基础矩阵估计的Python示例:

import pygcransac
import numpy as np

# 加载对应点
src_pts = np.loadtxt('src_points.txt')
dst_pts = np.loadtxt('dst_points.txt')

# 估计基础矩阵
F, mask = pygcransac.findFundamentalMatrix(
    src_pts, dst_pts, 
    img1_height, img1_width, img2_height, img2_width,
    threshold = 1.0, 
    conf = 0.999,
    spatial_coherence_weight = 0.975, 
    neighborhood_size = 4
)

# 获取内点
inliers = src_pts[mask.astype(bool)]

应用场景

GC-RANSAC可以应用于多个计算机视觉任务中,包括但不限于:

图像配准:通过估计单应性矩阵实现图像对齐
3D重建:利用基础矩阵和本质矩阵进行立体视觉重建
相机姿态估计:通过PnP问题求解相机外参
运动估计:估计相机或物体的刚体运动
全景图拼接:利用多幅图像间的单应性关系进行拼接

这些应用涵盖了计算机视觉、机器人导航、增强现实等多个领域。

算法原理

GC-RANSAC的核心思想是在RANSAC框架中引入基于图割的局部优化。其主要步骤如下:

采样:使用Progressive NAPSAC等方法从数据中采样极小子集
模型拟合:利用采样得到的数据拟合几何模型
验证:计算模型与所有数据的一致性得分
局部优化:对当前最佳模型进行局部优化
- 构建邻域图:基于空间位置关系构建点的邻域图
- 图割:将点分为内点和外点两类
- 重新拟合:使用分类后的内点重新估计模型参数
迭代:重复上述步骤直到满足终止条件

其中,图割算法在局部优化中起到了关键作用。它能够有效地考虑数据点之间的空间相关性,从而提高了模型估计的鲁棒性和精度。