Energy-Based Geometric Multi-model Fitting

Hossam Isack

doi:10.1007/s11263-011-0474-7

Return

Energy-Based Geometric Multi-model Fitting

2011-07-12

237

Hossam Isack

Yuri Boykov *

DOI：10.1007/s11263-011-0474-7

Original

Original request for help

Save

Abstract

En 中文

Geometric model fitting is a typical chicken-&-egg problem: data points should be clustered based on geometric proximity to models whose unknown parameters must be estimated at the same time. Most existing methods, including generalizations of RANSAC, greedily search for models with most inliers (within a threshold) ignoring overall classification of points. We formulate geometric multi-model fitting as an optimal labeling problem with a global energy function balancing geometric errors and regularity of inlier clusters. Regularization based on spatial coherence (on some near-neighbor graph) and/or label costs is NP hard. Standard combinatorial algorithms with guaranteed approximation bounds (e.g. alpha-expansion) can minimize such regularization energies over a finite set of labels, but they are not directly applicable to a continuum of labels, e.g. R-2 in line fitting. Our proposed approach (PEaRL) combines model sampling from data points as in RANSAC with iterative re-estimation of inliers and models' parameters based on a global regularization functional. This technique efficiently explores the continuum of labels in the context of energy minimization. In practice, PEaRL converges to a good quality local minimum of the energy automatically selecting a small number of models that best explain the whole data set. Our tests demonstrate that our energy-based approach significantly improves the current state of the art in geometric model fitting currently dominated by various greedy generalizations of RANSAC.

Keywords:

Geometric models

alpha-Expansion

Graph cuts

Sampling

Labeling

Parameter estimation