We present an efficient deterministic hypothesis generation algorithm for robust fitting of multiple structures based on the maximum feasible subsystem (MaxFS) framework. Despite its advantage, a global optimization method such as MaxFS has two main limitations for geometric model fitting. First, its performance is much influenced by the user-specified inlier scale. Second, it is computationally inefficient for large data. The presented MaxFS-based algorithm iteratively estimates model parameters and inlier scale and also overcomes the second limitation by reducing data for the MaxFS problem. Further it generates hypotheses only with top-n ranked subsets based on matching scores and data fitting residuals. This reduction of data for the MaxFS problem makes the algorithm computationally realistic. Our method, called iterative MaxFS with inlier scale estimation and subset updating (IMaxFS-ISE-SU) in this paper, performs hypothesis generation and fitting alternately until all of true structures are found. The IMaxFS-ISE-SU algorithm generates substantially more reliable hypotheses than random sampling-based methods especially as (pseudo-)outlier ratios increase. Experimental results demonstrate that our method can generate more reliable and consistent hypotheses than random sampling-based methods for estimating multiple structures from data with many outliers.

本文介绍了一种有效的确定性假设生成算法，用于基于最大可行子系统（MaxFS）框架的多结构稳健拟合。所提出的IMaxFS-ISE-SU算法通过降低MaxFS问题的数据量来克服计算效率低下的问题，并利用排名最高的子集和数据拟合残差来生成假设，从而比基于随机抽样的方法更可靠地估计具有许多离群值的数据的多个结构。

使用迭代的最大FS算法进行多结构确定性拟合，同时进行内点尺度估计和子集更新